# Is there an element with no fixed point and of infinite order in $\operatorname{Sym}(X)$ for $X$ infinite?

Let $X$ be an infinite set. Let $\operatorname {Sym}(X)$ denote the group of all bijections from $X$ onto itself. I have been thinking about the existence of elements of infinite order in this group.

For $\operatorname{card}(X)=\aleph_0,$ I've found the following construction. Let us identify $X$ and $\mathbb{N}.$ Let

$$\operatorname{Sym}(\mathbb N)\ni\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & ...\\ 2 & 1 & 4 & 5 & 3 & 7 & 8 & 9 & 6 & 11 & ... \end{pmatrix}.$$

It is clear that for any natural number $n$ there exists another natural number $k$ such that

$$\alpha^n(k)\neq k.$$

This is an example of an element of infinite order in $\operatorname{Sym}(\mathbb N).$ I was thinking if I could find such an element for any infinite set $X.$ I found this. Let $\leq$ be a well-ordering of $X.$ Let $x_0$ be the least element of $X.$ Let $x+n$ denote the successor of $x+(n-1)$ if such exists, and $x_0+0=x_0.$ Let $$Y=\{x_0+n\,|\,n\in \mathbb{N}\cup\{0\}\}.$$

This is well-defined because $X$ is an infinite well-ordered set. We define $\beta\in\operatorname{Sym}(X)$ as follows.

$$\begin{array} & \beta(x_0+n)=x_0+\alpha(n+1)-1 & \mbox{for } n\in \mathbb N\cup \{0\}\\ \beta(x)=x & \mbox {for } x\not\in Y \end{array}$$

This, if I'm not mistaken, is an example of an element of infinite order in $\operatorname{Sym}(X).$ However, it doesn't meet my needs. I would like to find an example with few or no fixed points. I'm having trouble with formalizing my reasoning here.

I would like to partition the set $X$ into copies of $\mathbb{N}$ and essentially use the first example on every one of them. To my understanding, any well-ordered set consists of, possibly unimaginably many, copies of $\mathbb N$ put one after the other, then copies of the result of the previous operation put one after the other, and so on, with possible tails of smaller "order" (or whatever it is called) at the end. Even if something is wrong with my understanding, I'm quite sure the partition I'd like to have exists. But I'm having a lot of trouble writing down a formal proof of this because I have never done anything with ordinals at all.

So my first question is if you could help me formalize this reasoning. I'm not asking for a very formal proof of course. Just something that would convince me, because what I have written does not.

My second question is if this can be done without the use of the axiom of choice. More precisely:

1) Is it possible to prove without assuming the axiom of choice that for any infinite set $X,$ there is an element $\alpha\in\operatorname{Sym}(X)$ of infinite order?

2) Is it possible to prove without assuming the axiom of choice that for any infinite set $X,$ there is an element $\alpha\in\operatorname{Sym}(X)$ of infinite order, such that the set of fixed points of $\alpha$ has cardinality lesser than $\operatorname{card}(X)?$

I would be very grateful if the answerers would kindly use simple language if it's possible. I'm very far from knowing much about these things.

-
I think your intuition works in the presence of AC. In that case you can biject X to a cardinal. Then write all the ordinals in that cardinal as $\alpha + \beta$ where $\alpha$ is the infinite part and $\beta$ is the finite part (essentially a simplification of Cantor Normal Form). Keep $\alpha$ the same, apply your function to $\beta$ and there you are. –  Ross Millikan Jan 28 '12 at 2:08

If $X$ is countably infinite, let $\varphi:X\to\mathbb{Z}$ be any bijection. Then

$$\sigma:X\to X:x\mapsto \varphi^{-1}(\varphi(x)+1)$$

does the trick.

More generally, let $X$ be any infinite set. Assuming that there is a bijection between $X$ and a set of the form $Y\times\mathbb{Z}$, just use the permutation $\langle y,n\rangle\mapsto\langle y,n+1\rangle$ of $Y\times\mathbb{Z}$ and pull it back to $X$ via the bijection. There will always be such a bijection if $X$ can be well-ordered.

Proof: If $X$ can be well-ordered, there is a bijection between $X$ and some infinite cardinal $\kappa$. Let $\Lambda$ be the set of ordinals in $\kappa$ having no immediate predecessor (i.e., the limit ordinals and $0$); then each ordinal in $\kappa$ can be written uniquely in the form $\lambda+n$ for some $\lambda\in\Lambda$ and $n\in\omega$. Let $\varphi:\omega\to\mathbb{Z}$ be any bijection. Then the map $$\kappa\to\Lambda\times\mathbb{Z}:\lambda+n\mapsto\langle\lambda,\varphi(n)\rangle$$ is clearly a bijection. $\dashv$

Added: I don’t know how much choice is entailed by the assumption that if $X$ is an infinite set, there is a bijection between $X$ and a set of the form $Y\times\omega$. It implies that every infinite set is Dedekind-infinite, but that’s not saying much: every infinite set is Dedekind-infinite is a very weak condition, weaker than the axiom of choice for countable sets.

-
Thanks for this great answer. The idea of using $\mathbb{Z}$ instead of $\mathbb N$ is very simple and very nice. –  user23211 Jan 28 '12 at 11:42

Indeed, as some of the other answers have mentioned it is consistent that without the axiom of choice that the first answer is negative.

The culprit is the fact that not every infinite set contains a copy of $\mathbb N$. These sets are called Dedekind-finite (often abbreviated as D-finite or DF), and while the assumption that every infinite set is Dedekind-infinite is not a very strong form of choice - it is still some assumption.

Dedekind-finite sets can be also defined as $A$ such that $f:A\to A$ is injective iff it is surjective iff it is bijective. Of course every finite set has this property, but as I say without the axiom of choice we may have that there are infinite sets which are Dedekind-finite.

Fact I: If $A$ is Dedekind-finite and $B\subsetneq A$ then $B$ has cardinality strictly less than $A$.

In more specifics, we can have a special kind of D-finite set called amorphous which is a very peculiar set: It is infinite, but every subset is either finite or its complement is finite.

Fact II: If $A$ is amorphous, and $U$ is a partition of $A$ into infinitely many parts then all but finitely many have the same size which is a finite number.

Fact III: If $A$ is amorphous then there is no binary relation $R$ such that $(A,R)$ is a linearly ordered set.

If $A$ is an amorphous set and $f\colon A\to A$ is a bijection consider the orbit of every element, if there is an element with an infinite orbit then $f^n(a)\neq f^j(a)$ for $n\neq j$, therefore we have a copy of $\mathbb N$ in $A$ which contradicts the fact that $A$ is amorphous. This means that every element has a finite orbit.

The partition of $A$ into the different orbits must have, if so, some $n$ such that for almost all $a\in A$ the orbit of $a$ is of size $n$, there might be finitely many points with different orbit sizes $k_1,\ldots,k_l$.

Take $k=\mathrm{lcm}(n,k_1,\ldots,k_l)$ and now I claim that $f^k$ is the identity function. Since for every $a\in A$ we have that $f^k(a)$ completes a full cycle on its orbit and thus returns to $a$.

We therefore cannot even prove that for every infinite $X$ there is an element of $Sym(X)$ which has an infinite order, so the second question is negated already.

Note, however, that if $X$ is Dedekind-finite then for every nontrivial permutation $\pi\in Sym(X)$ the set $\{x\in X\mid \pi x=x\}$ has cardinality strictly less than $|X|$.

-
Thanks for this answer! –  user23211 Jan 28 '12 at 12:04

Using the Axiom of Choice definition, let $\: f : X\to |X| \:$ be a bijection. $\;\;$ Using Ordinal Arithmetic, define $\: g : X\to X \:$ by $\: g(x) = f^{-1}((\omega \times (f(x) \div \omega))+\alpha(f(x)-(\omega \times (f(x) \div \omega)))) \:$.
$g$ is a bijection with no fixed points and of infinite order.

From www.maths.qmul.ac.uk/~pjc/preprints/amorph.ps,

"Corollary 1.3: For any amorphous set $U$, the group $\operatorname{Sym}(U)$ is a torsion group."

(So, the answers to 1 and 2 are "no".)

-
Wow, strange. The more I learn about mathematics without AC, the more I respect it as a deep and interesting field...and the more confident I am that in "real mathematics" one should always assume AC. –  Pete L. Clark Jan 28 '12 at 4:58
Thank you very much, Ricky Demer. –  user23211 Jan 28 '12 at 11:50
With regard to my above comment, "real mathematics" now seems unnecessarily provocative. I would like to replace it with "mainstream mathematics"...and if that still seems too provocative, with "conventional mathematics". –  Pete L. Clark Jan 28 '12 at 16:40
@Pete: When I was a freshman (or maybe sometime later in my undergrad?) I asked one of my teachers why do we always deal with separable or finite things and he said that finite things can understand well, and separable things we can approximate with finite things but beyond that it's harder to understand. Now I find myself flopping between non-well orderable sets and large cardinals. Two impossible things to the imagination and it just makes me get a better grasp on how mathematics works, in terms of why exactly we need AC, or infinitary combinatorics for non-separable spaces, etc. –  Asaf Karagila Jan 29 '12 at 0:09

Any infinite set contains a countable infinite set which can be identified with the integers $\mathbb{Z}$, giving you a simple infinite-order bijection $i \mapsto i+1$ on that copy of $\mathbb{Z}$ and all other elements stay put.

(this answers your first question; for the second, I imagine you could cover most of your set with disjoint copies of $\mathbb{Z}$ but not sure how much choice is required for that).

-
No that does not answer his first question, since you used Countable Choice. $\;$ –  Ricky Demer Jan 28 '12 at 2:15