Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $X$ be an infinite set. Prove that there is a bijective function $f: X \rightarrow X$ with the property that for every $x \in X$ and all $n > 0$: $f^n(x) \neq x$.

I've tried to proved this by considering a bijective function $g: \mathbb{Z} \times X \rightarrow X$ in a certain way (by the composition of a function $f: \mathbb{Z} \times X \rightarrow \mathbb{Z} \times X$), but that's all i've got at the moment.

share|cite|improve this question
Can't you partition $X$ into countable sets, identify each piece with $\mathbb{Z}$ and on each piece let $f$ be a shift? – Owen Sizemore Aug 22 '13 at 23:41
up vote 1 down vote accepted

You actually do have some very useful pieces; you just have to put them together properly.

  • Since $X$ is infinite, there is a bijection $f:X\to X\times\Bbb Z$. (This actually requires some part of the the axiom of choice.)
  • Find a bijection $h:X\times\Bbb Z\to X\times\Bbb Z$ that has the desired property; use the fact that $\Bbb Z$ has a bijection of the desired type.
  • Consider the map $f^{-1}\circ h\circ f$.

Note: Some nonsense deleted.

share|cite|improve this answer
Dedekind-infiniteness is not enough here. You need the fact that $X+X=X$. – Asaf Karagila Aug 22 '13 at 23:47
@Asaf: Yes, the second half of that comment was very badly placed. I’ve fixed it now. – Brian M. Scott Aug 23 '13 at 0:09
No, Brian, it is not enough to require Dedekind infiniteness. Consider an uncountable set that the every subset is countable or co-countable, and in every partition into countable parts, all but countably many are singletons. Such set can exist with $\sf DC$. This set have no such permutation. – Asaf Karagila Aug 23 '13 at 0:28
Moreover, consider th sum of an amorphous set and a countable set. Every permutation of an amorphous set has a finite order, but the sum is certainly Dedekind infinite. – Asaf Karagila Aug 23 '13 at 0:35
@Asaf: You should have realized from my addition that I'd misread the question! :-) I read it as wanting one $x$ with that property, for which Dedekind-infiniteness is indeed enough. – Brian M. Scott Aug 23 '13 at 1:04

You're on the right track.

Consider the permutation of $\Bbb Z\times X$ defined by $(k,x)\mapsto(k+1,x)$. Now pull that to a permutation of $X$.

Do note that the axiom of choice is needed here, and in particular the fact that $\Bbb Z\times X\sim X$.

share|cite|improve this answer

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.