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:

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.