# Logic: existence of a certain type of a bijective function on an infinite set

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.

-
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

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.

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

-