# Prove that every set with more than one element has a permutation without fixed points

I cannot prove this statement so need help. This problem is one of exercises right after the chapter about Hausdorff's maximal principle and Zorn's Lemma. Thus, you cannot use the concept of cardinal number. I found the exact same question on this website, but the proof is done by using the concept of cardinal number. Please make sure that this question is at right after introducing the axiom of choice and Zorn's lemma.

Let $A$ be any set with more than one element. Prove that there exists a bijective function $f:A \to A$ such that $f(x)\neq x$ for every element $x$ in $A$.

Order the bijective functions $f\colon A\to A$ such that $f\le g$ if all fixed points of $g$ are fixed points of $f$ and $f$ and $g$ agree on all elements that aren't fixed points of $f$. Given a chain with respect to this partial order, an upper bound is given by the function that has fixed points where all elements of the chain have fixed points and maps every other element to the unique element that some elements of the chain map it to. Thus by Zorn's lemma there is a maximal element with respect to this partial order. If this maximal element had at least two fixed points, we could map those two fixed points to each other to create a greater element. Thus the maximal element $f$ has at most one fixed point $x$, and if so we can choose some other element $a$ and define $g$ to coincide with $f$ except $g(a)=x$ and $g(x)=f(a)$. Then $g$ has no fixed points.

• Perfect! Thank you! Have a good day sir Commented Apr 20, 2012 at 1:47
• @Katlus: You too! You're welcome. I think Robert's solution is a bit easier, though. Commented Apr 20, 2012 at 1:48

If $A$ is infinite it is equipotent to $A\times\mathbb F_2$, and $(a,x)\mapsto(a,1+x)$ does the job.

• That is very nice! Commented Apr 20, 2012 at 7:51
• Dear @Bruno: Thanks! This is completely unrelated, but I liked very much you blog post A divisibility identity for Euler’s totient function! And I recommend it to MSE readers. Commented Apr 20, 2012 at 8:14
• Dear Pierre-Yves, thank you! I'm glad you enjoyed reading it, and thank you for reading my blog. Commented Apr 20, 2012 at 8:16
• Pierre, nice answer. Essentially this the content of the final remark in my answer. Commented Apr 20, 2012 at 10:10
• Dear @Asaf: I agree. I overlooked the final remark in your answer. Sorry. I up-voted the question and all answers (except of course mine). Thanks for your comment. Commented Apr 20, 2012 at 11:05

Here is another proof for fun. It can easily be shown that the axiom of choice is equivalent to the statement that every nonempty set admits a group structure. Give $A$ a group structure, and let $f:A \to A$ be left multiplication by a non-identity element of $A$.

• Very nice! Although probably useless to the OP... :-) Commented Apr 20, 2012 at 10:08
• Thanks @AsafKaragila. Yes, completely useless most likely. :) Commented Apr 20, 2012 at 17:15

Hint: consider collections $\{S_i: i \in I\}$ of subsets of $A$ each containing two elements. Use Zorn to get such a collection which is maximal.

• Just a comment, to fill in a minor detail. The maximal system either covers the whole set $A$, or precisely one element is missing, i.e. it covers $A\setminus\{a\}$. In both cases it is relatively easy to find a wanted permutation (it consists only of transpositions and perhaps one cycle of length 3).\\ I've posted the comment because if someone reads your hint not carefully enough, he might think that the maximal collection necessarily contains all elements of $A$. Commented Apr 20, 2012 at 7:36
• Yes, that's what I meant. Commented Apr 20, 2012 at 19:00

Here is a somewhat convoluted proof which I am adding since it might have some value to it:

If $A$ is finite then it is obvious how to do it via finite combinatorics. Suppose that $A$ is infinite.

Lemma: For every element $a\in A$ there is a bijection between $A$ and $A\setminus\{a\}$.

It is enough to show that $A$ contains a countably infinite subset, if it does we can write $A=\{a_i\mid i\in\mathbb N\}\cup A'$ and without loss of generality $a=a_0$ now take $a_i\mapsto a_{i+1}$ and the identity on $A'$, this would be our wanted bijection.

Proof. Consider $A_n = \{X\subseteq A\mid X\text{ has exactly }n\text{ members}\}$, since $A$ is infinite all of those are non-empty. Using the axiom of choice choose exactly one from each $A_n$, denoted by $X_n$ and for each $X_n$ choose a bijection with $\{0,\ldots,n-1\}$. Now the union $\bigcup X_n$ can be enumerated by the natural numbers and is not finite. $\square$

Now to actually prove the claim we want to prove:

We define a partially ordered set $(P,\leq)$. Let $P$ be the set of triplets $\langle X,Y,f\rangle$ such that $X,Y$ are disjoint subsets of $A$ and $f\colon X\to Y$ is a bijection. We say that $\langle X,Y,f\rangle\leq\langle X',Y',f'\rangle$ if and only if $X\subseteq X'$, $Y\subseteq Y'$, and $f\subseteq f'$.

If $\{\langle X_i, Y_i, f_i\rangle\mid i\in I\}$ is a chain then $\langle\bigcup X_i,\bigcup Y_i,\bigcup f_i\rangle$ is an upper bound of this chain. There are details to verify (disjointness, the fact that the union of the $f_i$ is still a bijection) but those follow from the fact that this is a chain. I leave these details for you to verify.

Let $\langle X,Y,f\rangle$ be a maximal element whose existence is guaranteed by Zorn's lemma. If $A\setminus (X\cup Y)$ contains at least two elements we can add one to $X$ and another to $Y$ and extend $f$ accordingly and thus contradict the fact that we have a maximal element.

If there is only one element $a$ by the lemma we can find a bijection $g\colon X\cup Y\to A$, since $g$ is a bijection we have that $g[X]\cup g[Y]=A$ and $g[X]\cap g[Y]=\varnothing$. Also note that $g\circ f\circ g^{-1}$ is a bijection between $g[X]$ and $g[Y]$. So we can assume without loss of generality that $X\cup Y=A$.

Now let $h\colon A\to A$ be the function $f\cup f^{-1}$. To see that this is a function note first that $f^{-1}$ is a function since $f$ is a bijection between $X$ and $Y$ and the domains of $f$ and its inverse are disjoint, therefore the union is a function. It is not very hard to verify that $h$ is indeed a bijection from $A$ to itself and that for every $a\in A$ we have $h(a)\neq a$ since if $a\in X$ then $h(a)\in Y$ and vice versa.

One additional remark is that Sageev proved in the 70's that the assumption that for every infinite set $A$ we have a bijection from $A$ to $A\times\{0,1\}$ (i.e. $|A|=2|A|$) is strictly weaker than the axiom of choice. One can see immediately that this assumption is in fact enough in order to ensure such a derangement exists.

• I assume that when you're defining $P$, you're requiring that the sets $X,Y$ be subsets of $A$, yes? Without restriction, of course, $P$ isn't a set. Commented May 3, 2012 at 19:45
• @CameronBuie: Obviously. I'll correct the post. Also note that I required $P$ to be a set, while I did not explicitly mention where the $X,Y$ are from by requiring the collection is a set this is no longer my problem! :-) Commented May 3, 2012 at 19:49
• Aha! Disjointness, too. I hadn't considered that. Very nice. Commented May 3, 2012 at 19:53
• @CameronBuie: In all fairness, I required disjointness before the edit! :-) Commented May 3, 2012 at 20:18

We first prove it can be done for the natural numbers $$\Bbb N = \{0,1,2,\dots\}$$, a well ordered set.

Using the familiar successor function $$\sigma$$ on $$\Bbb N$$, we define a bijective transformation $$\beta$$ on $$\Bbb N$$ as follows:

$$\beta(x) = \left\{\begin{array}{lr} \sigma^{2k+2}(0) & \text{when } k \ge 0 \text{ and } x = \sigma^{2k}(0) \\ 0 & \text{when } x = \sigma(0) \\ \sigma^{2k-1}(0) & \text{when } k \ge 1 \text{ and } x = \sigma^{2k+1}(0) \end{array}\right\}$$

Now let $$A$$ be any infinite set. It can be shown (see this) that $$A$$ can be partitioned into blocks with each block being countably infinite. So we can use the $$\beta$$ mapping technique on each of these blocks to define a bijective transformation $$f$$ satisfying $$f(x) \ne x$$ for every $$x \in A$$.

If $$A$$ is finite, the result is trivial. If $$A$$ is infinite, we can put it in bijection with some limit ordinal $$\lambda$$. We can express every ordinal below $$\lambda$$ in the form $$\alpha+n$$, where $$\alpha$$ is a limit ordinal (or zero) and $$n$$ is an integer. Sending $$\alpha+n$$ to $$\alpha+(n+1)$$ for $$n$$ even, and $$\alpha+n$$ to $$\alpha+(n-1)$$ for $$n$$ odd, we obtain a derangement. $$\blacksquare$$