22
$\begingroup$

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)?

$\endgroup$
  • 5
    $\begingroup$ No, because it follows from BPIT (say, using the compactness theorem). $\endgroup$ – Emil Jeřábek Apr 20 at 12:18
  • 3
    $\begingroup$ In that case, is it equivalent to BPIT? $\endgroup$ – Todd Trimble Apr 20 at 12:31
  • 4
    $\begingroup$ Another question: can it be proved in ZF? Note: BPIT = Boolean algebra prime ideal theorem en.wikipedia.org/wiki/Boolean_prime_ideal_theorem $\endgroup$ – Gerald Edgar Apr 20 at 12:36
  • 2
    $\begingroup$ Another related question: If this cannot be proven in ZF, maybe a version with some higher but fixed number of sets can be? $\endgroup$ – JoshuaZ Apr 20 at 13:02
  • 9
    $\begingroup$ Although the proof of the 3-sets theorem in my thesis (math.lsa.umich.edu/~ablass/thesis.pdf) used AC quite generously, it seems that it can be reformulated to use only choice from arbitrary families of finite sets, namely the sets partitions of individual components of the graph depicting $f$ that use one of the colors just once in the components that contain odd cycles. In fact, it seems sufficient to have choice from families of finite-sets-with-cyclic-orderings. $\endgroup$ – Andreas Blass Apr 20 at 14:31
34
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
22
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for this valuable addition @emiljerabek! $\endgroup$ – Dominic van der Zypen Apr 25 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.