Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

1 Answer 1

up vote 7 down vote accepted

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$.

share|improve this answer
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
I mean, this function could goes recursively and never stops –  user42912 Feb 24 '13 at 14:06
@user42912, sorry, there was a confusing misprint in my answer, please reread it now. I am distinguishing two cases, the second one is the one you mention. –  Andreas Caranti Feb 24 '13 at 14:57

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.