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

Question

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

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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.

Answer 5

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.

Answer 6

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

Answer 7

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$