On the Partition Principle

Last Wednesday I gave a talk about the Partition Principle in our students seminar. This talk covered the historical background of the oldest open problem in set theory, and two proofs that for a long time I avoided learning. I promised to post a summary of the talk here. So here it is. The historical data was taken from the paper by Banaschewski and Moore, "The dual Cantor-Bernstein theorem and the partition principle." (MR1072073) as well Moore's wonderful book "Zermelo’s Axiom of Choice" (which has a Dover reprint!).

We begin with two definitions. We write \(A\leq B\) to say that there is an injection from \(A\) into \(B\), and \(A\leq^* B\) to say that if \(A\) is not empty, then there is a surjection from \(B\) onto \(A\). These orders are usually defined for cardinals, we will often confuse a set with its cardinality here. Additionally we define two cardinal functions, given a set \(A\) the Hartogs number of \(A\), denoted by \(\aleph(A)=\min\{\alpha\in\Ord\setminus\omega\mid\alpha\nleq A\}\) is the least infinite ordinal which cannot be mapped into \(A\) injectively; and the Lindenbaum number of \(A\), denoted by \(\aleph^*(A)=\min\{\alpha\in\Ord\setminus\omega\mid\alpha\nleq^* A\}\) is the least infinite ordinal that \(A\) cannot be mapped onto.

(Two minor remarks, in some places \(\aleph\) and \(\aleph^*\) are allowed to be finite, I prefer to think about it as a function into \(\aleph\) numbers. It also helps to characterize finiteness; the second is that we don't use \(\aleph^*\) here at all, I just found it fitting to add the definition and push even more the efforts to establish the terminology "Lindenbaum number".)

The Partition Principle (PP) is the principle stating that if \(A\leq^*B\) then \(A\leq B\), or in words if there is a surjection \(f\colon B\to A\), then there is an injection \(g\colon A\to B\). In other words, if we partition the set \(A\) into \(B\) parts, we could only decrease the cardinality.

This is a weakening of the axiom of choice, which can be phrased as the following: if there is a surjection \(f\colon A\to B\), then there is an injection \(g\colon B\to A\) such that \(f\circ g=\operatorname{id}_B\). So clearly \(\AC\) implies \(\sf PP\).

The partition principle was almost formulated by Burali-Forti in the late 19th century. Almost because Burali-Forti's formulation had a mistake. The formulation was that \(S\leq\bigcup S\). Russell noted that this is false, unless we require that \(S\) is a collection of pairwise disjoint sets, in which case we really do say that a partition of \(\bigcup S\) can only decrease in size.

This principle was used by Bernstein in 1901, and in 1902 Beppo Levi formulated it explicitly to point out the problem with Bernstein's proof. Bernstein argued that this is an important principle of mathematics, and indeed one of the motivations given by Zermelo for the axiom of choice was that it proves this principle. Russell claimed that \(\sf PP\) proves the axiom of choice, although he did not give proof of that (the claim was indirect, Russell claimed this is equivalent to a different axiom which he proved to be equivalent to \(\AC\)).

The Polish school of Warsaw had its share of related works. In 1918 Sierpinski reformulated the principle as \(f''A\leq A\), for every function \(f\) and set \(A\). In the same year, Sierpinski proved that from the assumption that \([\RR]^\omega\) and \(\RR\) have the same cardinality - something which follows from \(\sf PP\) - the existence of a Lebesgue non-measurable set can be proven. Lebesgue disagreed with the proof, and the two had an argument over that topic for several more years.

Lindenbaum and Tarski defined \(\leq^*\) in 1926, and formulated the Weak Partition Principle (WPP): \[A\leq^*B\implies B\nless A\] Namely, we cannot partition a set into strictly more parts than elements (curiously this is a consequence of having all sets Lebesgue measurable, something equally perplexing as the Banach-Tarski theorem).

We can include an intermediate weakening of PP, the dual Cantor-Bernstein theorem, (CB*) which states that \(\leq^*\) is antisymmetric as an ordering of cardinals. Namely, if there are surjections from \(A\) onto \(B\) and vice versa, then there is a bijection between \(A\) and \(B\).

As remarked \(\AC\) implies \(\sf PP\), which itself implies \(\sf CB^*\) (by reducing it to the Cantor-Bernstein theorem), and \(\sf CB^*\) implies \(\sf WPP\) (via a similar proof).

In 1965, Levy pointed out that whether or not any of the three implications is reversible is still open (this is actually a paper from a conference in 1963). In 1978 Pelc published a paper which included an equivalence between \(\sf PP\) and \(\sf CB^*\) under some additional conditions, as well the following theorem by Pincus:

Theorem. (Pincus, 1978) \(\sf PP\) implies that for every \(\aleph\)-number \(\kappa\), \(\AC_\kappa\) holds. (Namely, choice from families of size \(\leq\kappa\).)

Proof. We will show that from \(\sf PP+\AC_{\lt\kappa}\) we can prove \(\AC_\kappa\), and then by transfinite induction we can prove that for every \(\aleph\) number \(\kappa\), \(\AC_\kappa\) holds.

Let \(\langle X_\alpha\mid\alpha\lt\kappa\rangle\) be a family of non-empty sets. By our assumptions, for each \(\gamma<\kappa\), the set \(C_\gamma=\prod_{\alpha\lt\gamma}X_\alpha\) is non-empty. We define by induction \(\aleph\) numbers, \(\lambda_\gamma\) and sets \(D_\gamma\):

• \(\lambda_\gamma=\aleph\left(\bigcup_{\delta\lt\gamma}D_\delta\right)+\sup_{\delta\lt\gamma}\lambda_\delta^+\).
• \(D_\gamma=C_\gamma\times\lambda_\gamma\).

Finally, let \(\lambda=\sup_{\gamma\lt\kappa}\lambda_\gamma\) and \(D=\bigcup_{\gamma\lt\kappa}D_\gamma\). There is a natural surjection from \(D\) onto \(\lambda\), the projection map. Using the Partition Principle, we have that there is an injection \(F\) from \(\lambda\) back into \(D\). Naively we might be tempted to think that this injection reverses this surjection, so it chooses \((h_\gamma,\gamma)\) from each \(D_\gamma\). But this need not be the case, we are only guaranteed an injection. However, by noting that \(\lambda\) is at least as large as \(\alpha(D_\gamma)\) for any \(\gamma\), we have that the range of \(F\) meets arbitrarily high \(D_\gamma\)'s. This allows us to define a choice function from the original \(X_\alpha\)'s. Denote \(F(\delta)\) by \((h_\delta,\delta)\), then we define \(H(\alpha)=x_\alpha\) if and only if \(h_\delta(\alpha)=x_\alpha\), and \(\delta=\min\{\delta'\lt\lambda\mid\alpha\in\dom h_{\delta'}\}\). \(\qquad\square\)

This shows that \(\sf PP\) gives us a substantial amount of choice. But unfortunately, not that substantial. In 1964 Levy showed that choice from well-orderable families doesn't have to imply \(\sf DC_{\omega_1}\). Pincus transferred the proof from permutation models to \(\ZF\) in 1969. But we can do better, as Jensen showed.

Theorem. (Jensen, 1968) Suppose that for every \(\aleph\) number \(\kappa\), \(\AC_\kappa\) holds. Then \(\DC\) holds.

Proof. Recall that \(\DC\) can be formulated as the statement "Every tree of height \(\omega\) without leaves has a branch". So let \((T,\lt_T)\) be a tree of height \(\omega\) and without leaves. We first observe that it suffices to find a well-orderable set \(A\subseteq T\) such that \((A,{}_T\gt\restriction A)\) is not well-founded (here well-founded means every non-empty set has a minimal element), since we assume that \(A\) can be well-ordered this is equivalent as saying there is a decreasing chain which is a branch through \(T\). Assume towards contradiction that there is no such subset of \(T\).

Let \(\mathcal W=\{A\subseteq T\mid A\text{ can be w.o., and }(A,{}_T\gt)\text{ is well-founded}\}\). For each \(A\in\mathcal W\) define \(\rho_A\) to be the rank function for \((A,{}_T\gt)\). Finally, \(\lambda(x)=\sup\{\rho_A(x)\mid x\in A\in\mathcal W\}\).

Now we claim that for every \(x\in T\) there is some \(A\in\mathcal W\), such that \(\lambda(x)=\rho_A(x)\). Namely, \(\sup\) is in fact \(\max\), if it happened to be a successor ordinal then this obviously true. To prove that in the case of a limit ordinal, define \(R_\alpha=\{(A,<)\mid\rho_A(x)=\alpha,\text{ and }<\text{ is a well-ordering of }A\}\) then for all \(\alpha\lt\lambda(x)\) this is non-empty. Using \(\AC_{|\lambda(x)|}\) we can choose from each \(R_\alpha\) a pair, \((A_\alpha,<_\alpha)\), and define \(A=\bigcup_{\alpha<\lambda(x)}A_\alpha\). Then \(A\) can be well-ordered, and \(\rho_{A_\alpha}(x)\leq\rho_A(x)\leq\lambda(x)\), so \(\rho_A(x)=\lambda(x)\).

Let \(x\) be such that \(\lambda(x)\) is minimal, and let \(y\) be a successor of \(x\) in \(T\). Let \(A\) be such that \(y\in A\) and \(\lambda(y)=\rho_A(y)\), and let \(A'=A\cup\{x\}\). Then \(\lambda(y)=\rho_A(y)=\rho_{A'}(y)<\rho_{A'}(x)\leq\lambda(x)\). This is a contradiction to the minimality of \(\lambda(x)\). \(\qquad\square\)

So we have some provable results. The Partition Principle implies choice from well-ordered families, and therefore \(\DC\). It implies the existence of non-measurable sets, and it doesn't give us a whole lot to work with in terms of trying to prove the axiom of choice from it. Since the 1970's there was the Banaschewski-Moore paper cited above, as well Higasikawa's paper "Partition principles and infinite sums of cardinal numbers" (MR1351415) from 1995. But here we are, nearly two decades later, and nothing changed in the questions above.

The question \(\sf PP\rightarrow\AC\) is simple to formulate, and simple to understand. But much like many other problems in mathematics, it is incredibly difficult to solve.