Skip to main content
2 of 5
added 536 characters in body

A weakening of the $3$-set-lemma provable in ${\sf (ZF)}$

The number $3$ plays an interesting role in the following statement:

$\newcommand{\S}{\sf(S_3)}\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. (Although the full force of (AC) is not needed as the strictly weaker Boolean Prime Ideal Theorem (BPI) is sufficient, but it appears that the $\S$ is not a theorem of $\newcommand{\ZF}{{\sf (ZF)}}\ZF$.)

The motivation of this question is to find a weakening of $\S$ that is a theorem of $\ZF$.

Question. Is one of the following statements a theorem of $\ZF$?

If $f:\mathbb{N}\to\mathbb{N}$ is fixed-point free, then there is a finite set ${\frak S}\subseteq {\cal P}(\mathbb{N})$ with $\bigcup{\frak S} = \mathbb{N}$ and $S\in {\frak S}$ with $S\cap f(S) = \emptyset$.

It would also be interesting to know whether this stronger statement holds in $\ZF$.

If $X\neq \emptyset$ is a set with more than $1$ element and $f:X\to X$ is fixed-point free, then there is ${\frak S}\subseteq {\cal P}(X)$ with $\bigcup {\frak S} = X$ such that a) is no injection $\iota:{\frak S} \to X$, and b) there is $S\in {\frak S}$ with $S\cap f(S) = \emptyset$.

Note that if we allow ${\frak S}$ to be as big as $X$ then we just can take ${\frak S} = \big\{\{x\}:x\in X\big\}$ and get a boring "theorem".)