# A set $X$ is finite iff there is a function $f:X\to X$ which has only as stable subsets $\emptyset$ and $X$.

I'm trying to solve the following question:

Let $f:X\to X$ be a function. A subset $Y\subset X$ is stable relatively to $f$ when $f(Y)\subset Y$. Prove that a set $X$ is finite if and only if there is a function $f:X\to X$ which has only as stable subsets $\emptyset$ and $X$.

If $X$ is finite, say $X=\{x_1,x_2,...x_n\}$, define $f$ as $f(x_i)=f(x_{i+1})$, if $i=2,...,n-1$ and $f(x_{n})=x_1$. Then $f:X\to X$ has only as stable subsets $\emptyset$ and $X$.

I'm having troubles with the converse, I need help in this part.

Thanks a lot

-
Tip: use $\emptyset$ or $\varnothing$ instead of $\phi$. – wj32 Feb 24 '13 at 13:33
@wj32 thanks :) – user42912 Feb 24 '13 at 13:34

Let $X$ be an infinite set, and $f : X \to X$ an arbitrary function. Pick $x_{0} \in X$, define recursively $x_{i+1} = f(x_{i})$, and form $Y = \{ x_{i} : i \ge 1 \}$. Clearly $Y$ is stable and non-empty.
If $x_{0} \notin Y$, then $Y \ne X$.
If $x_{0} \in Y$, say $x_{0} = x_{n+1}$, then $Y = \{ x_{0}, \dots, x_{n} \}$ is finite, thus $Y \ne X$.
Why $\{ x_{0}, \dots, x_{n} \}$ is finite? thank you for your answer – user42912 Feb 24 '13 at 13:58
@user42912, it has at most $n+1$ elements. – Andreas Caranti Feb 24 '13 at 14:03
yes, I know, but why it has $n+1$ elements? – user42912 Feb 24 '13 at 14:05