Does the "three-set-lemma" imply the Axiom of Choice?

Question

Consider the following curious statement:

$(S)$ $\;$ Let $X$ be a non-empty set and let $f:X \to X$ be fixpoint-free (that is $f(x) \neq x$ for all $x\in X$). Then there are subsets $X_1, X_2, X_3 \subseteq X$ with $X_1\cup X_2\cup X_3 = X$ and $$X_i \cap f(X_i) = \emptyset$$ for $i \in \{1,2,3\}$.

There are easy examples showing that one cannot get by using $2$ subsets only. Statement $(S)$ can be proved using the axiom of choice.

Question. Does $(S)$ imply (AC)?

Answer 1

The three-set lemma is listed as form 285 in Howard and Rubin's "Consequences of the axiom of choice". According to their book, the earliest appearance seems to be a problem in a 1963 issue of the American Mathematical Monthly (problem 5077).

As mentioned already in the comments by Emil Jerabek, this form of choice is not equivalent to full AC, but already follows from the Boolean prime ideal theorem (BPI). However, it is not equivalent to BPI either, since it already follows from the ordering principle (every set can be linearly ordered), which readily implies the axiom of choice for families of finite sets, and this latter implies the three-set lemma in question as shown by Wisniewski ("On functions without fixed points", Comment. Math. Prace Mat vol 17, pp. 227-228, 1973); as proved by Mathias turning a Fraenkel-Mostowski model into a model of ZF, the ordering principle does not imply BPI.

Answer 2

To complement godelian’s answer, the three-set lemma is not provable in ZF alone, as it implies the axiom of choice for families of pairs. This holds even if we allow any finite (or even just well ordered) number of sets instead of three.

If $\{P_i:i\in I\}$ is a family of disjoint two-element sets, put $X=\bigcup_{i\in I}P_i$, and let $f\colon X\to X$ be defined such that it maps each element to the other element in the same pair. Then if $\alpha$ is an ordinal and $X=\bigcup_{\beta<\alpha}X_\beta$ where $f[X_\beta]\cap X_\beta=\varnothing$ for each $\beta$, we have $|X_\beta\cap P_i|\le1$ for all $\beta<\alpha$ and $i\in I$, thus the following is a selector: $s(i)=$ the unique element of $X_\beta\cap P_i$, where $\beta<\alpha$ is the least such that the intersection is nonempty.

---

EDIT: Here is an exact characterization. (Again, the argument also applies if we allow any well-ordered number of sets instead of three.)

Theorem. Over ZF, the three-set lemma is equivalent to the axiom of choice for families of finite sets.

As mentioned in godelian’s answer, the right-to-left implication can be found in

K. Wiśniewski: On functions without fixed points, Commentationes Mathematicae 17 (1973), no. 1, pp. 227–228. DML-PL

See also Andreas Blass’s comment above.

For the left-to-right implication, let $F$ be a family of nonempty finite sets. We may assume $F$ is closed under (nonempty) subsets. Put $$C=\{\langle A,h\rangle:A\in F,|A|\ge2,h\text{ is a cyclic ordering of }A\},$$ where a cyclic ordering of $A$ is a permutation $h\colon A\to A$ which forms a single cycle of length $|A|$. Let $X$ be the disjoint union $\sum_{\langle A,h\rangle\in C}A$, and define $f\colon X\to X$ as the corresponding union $\sum_{\langle A,h\rangle\in C}h$. Let us fix $X_1,X_2,X_3\subseteq X$ as given by the three-set lemma.

By induction on $n$, we will construct a selector $s_n$ on $F_n=\{A\in F:|A|=n\}$. Then $\bigcup_ns_n$ will be the desired selector on $F$.

The base case $n=1$ is trivial. Assume that $n\ge2$, and we have already constructed $\{s_m:m<n\}$. Given $A\in F_n$, we define a permutation $g\colon A\to A$ by $$g(a)=s_{n-1}(A\smallsetminus\{a\}).$$ We define $s_n(A)\in A$ by considering two cases:

Case 1: $g$ is an $n$-cycle. Then $\langle A,g\rangle\in C$, hence at least two of the sets $X_i$ (nontrivially) intersect the $\langle A,g\rangle$-indexed copy of $A$ inside $X$; let $i$ be the least such that $X_i$ intersects it, and let $B\subsetneq A$ be the intersection. Put $s_n(A)=s_{|B|}(B)$.

Case 2: $g$ is not an $n$-cycle. Since $g$ is fixed-point free, it has less than $n$ cycles, thus $S=\{s_{|c|}(c):c\subseteq A\text{ is a cycle of }g\}$ is a proper subset of $A$, and we may define $s_n(A)=s_{|S|}(S)$. QED

Let me mention that there is also a similar two-set lemma:

Theorem. The following are equivalent over ZF:

1. If $f\colon X\to X$ is such that $f^n(x)\ne x$ for all $x\in X$ and odd $n$, then there exist $X_1,X_2$ such that $X=X_1\cup X_2$ and $X_i\cap f[X_i]=\varnothing$ for $i=1,2$.

2. The axiom of choice for families of two-element sets.