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)?
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.
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.
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 was proved 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.) Let me sketch the argument here. Consider a connected component $C\subseteq X$ of the graph of $f\colon X\to X$, i.e., an equivalence class of the equivalence relation $$x\sim y\iff\exists n,m\in\omega\:f^n(x)=f^m(y).$$ Also, let $\approx$ denote the similar equivalence relation induced by $f^2$, i.e., $$x\approx y\iff\exists n,m\in\omega\:f^{2n}(x)=f^{2m}(y).$$ For a given $C$, there are two cases:
Case (a): $x\not\approx f(x)$ for all $x\in C$. Since for all $x,y\in C$, $x\approx y$ or $x\approx f(y)$, $C$ consists of two equivalence classes of $\approx$. We may pick one of them and include it in $X_1$, and include the other one in $X_2$.
Case (b): $x\approx f(x)$ for some $x\in C$. Then $f^n(x)=f^{n+k}(x)$ for some $n$ and odd (hence nonzero) $k$, i.e., starting from $x$, $f$ eventually reaches a finite (odd) cycle $c\subseteq C$. The same cycle is reached from any other element of $C$. We may pick $a\in c$ and then define a suitable splitting of $C$ into three sets as follows: for any $x\in C$, let $n\in\omega$ be the least such that $f^n(x)=a$. If $n=0$ (i.e., $x=a$), put $x$ in $X_3$; otherwise, put $x$ in $X_1$ or $X_2$ according to $n\bmod2$.
Thus, all in all, in order to define $X_1,X_2,X_3$ such that $X=\bigcup_iX_i$ and $X_i\cap f[X_i]=\varnothing$, it is enough to choose one of the two equivalence classes of $\approx$ from each class of $\sim$ satisfying (a), and to choose one element from each odd cycle of $f$.
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:
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$.
The axiom of choice for families of two-element sets.
