Is it consistent without the axiom of choice that every permutation of some infinite set have fixed points?

Question

A "permutation" of a non-empty set means an injective mapping of the set onto itself. Let $S(1)$ be the statement "There exists a permutation of every set containing at least two elements, which has no fixed points". Let $S(2)$ be the statement "There exists an infinite set, all of whose permutations have at least one fixed point". All the proofs I have seen of $S(1)$ make use of Zorn's Lemma, which is equivalent to the Axiom of Choice. Is it possibe that the consistency of ZF-without the Axiom of Choice-implies the consistency of ZF $+S(2)$?

Answer 1

Yes, it is very much possible to have $S(2)$ without the axiom of choice.

Suppose that $X$ is a set such that:

1. $X$ is infinite Dedekind-finite, so every countable subset is finite.
2. If $\mathcal S$ is a partition of $X$, so that every part is finite, then all but finitely many parts are singletons.

Then I claim that every permutation of $X$ has co-finitely many fixed points (and in particular a fixed point). To see why note that if $\pi$ is a permutation of $X$, then it defines an equivalence relation by the orbits of each element. And orbits are either finite, or countably infinite.

By the first condition we know that all the orbits are finite. So this defines a partition of $X$, and all its parts are finite, which means that only finitely many elements have nontrivial orbits, which means that only finitely many elements are moved at all.

(Note that these two conditions are not necessary, just sufficient. If $X$ satisfies the above conditions, then $X\cup\Bbb N$ is also a set which every permutation of it has a fixed point.)

---

So, can there be such set $X$? Yes, there can. We have two easy examples:

1. In Cohen's first model, the Dedekind finite set of reals added satisfies this property, this is a technical check, but it's not difficult if you're familiar with symmetric extensions.

2. We say that a set $X$ is amorphous if $X$ cannot be partitioned into two infinite subsets, and $X$ is strongly amorphous if every partition of $X$ into finite parts has all but finitely many parts as singletons. In Fraenkel's first model (with atoms) he constructs a strongly amorphous set; and using various embedding theorems we can have such set in $\sf ZF$ (without atoms).

3. Similar but different example, is a strong $\kappa$-amorphous set. Which is a set $X$ such that $|X|\nleq\kappa$, and every $A\subseteq X$ has either $|A|<\kappa$ or $|X\setminus A|<\kappa$; the strongness condition is the same as before, every partition into well-ordered parts has $<\kappa$ parts which are non-singletons.

   The same arguments as before work out. But the existence of such set is consistent with $\sf DC_{<\kappa}$.

Let me point out that the failure of $S(2)$ is much weaker than the axiom of choice itself. If for every infinite set $X$ we have that $|X|=|X\times\{0,1\}|$, then every infinite set has a permutation without fixed points. Simply fix such partition of $X$ into $|X|$-many pairs, and cycle each pair.

Sageev showed that the above assumption is much weaker than the axiom of choice in full.