1. Let $f:X\rightarrow X $ be a function. A subset Y of X is called
invariant if $f(Y) \subseteq Y$. An invariant subset $Y$ is called
irreducible if no proper subset of $Y$ is also invariant. An
invariant subset $Y$ is called decomposable if its complement is
also invariant.
Now let $f:X\rightarrow X$ be an injection.
(i) if $X$ is infinite, then there are infinitely many non-trivial
invariant subsets of $Y$. However, there may not be any
decomposable or irreducible subsets.
(ii) if $X$ is finite, then $X$ is the disjoint union of a finite
number of irreducible decomposable subsets.
2. Let $f:X\rightarrow X$ be a bijection on a finite set. The
cycle representation of $f$ consists of a listing of the chains
for the equivalence class $\tilda_f $. Thus for example, the
function $f(i) =2*i \mod 5$, has the cycle representation
$(0)(1,2,4,3)$.
(i) Show that any function $f$ is constructible from its cycle
representation.
(ii) Show that $f^k =$identity for some $k\geq 1$. If the cycle
representation of $f$ is known, can the smallest such $k$ be
calculated?
3. Show that the reals have the same cardinality as $2^N $, the
power-set of the natural numbers.
4. This is to illustrate that dove-tailing is specific to the
natural numbers. Let $I$ denote the interval $[0,1]$.
What is the cardinality of $I\times I$?