Class-theoretic division paradox

Question

The Division Paradox is the fact that there are models of ${\sf ZF \neg C}$ in which a set can be partitioned into a set that is bigger than it — equivalently, in which there are sets $X$ and $Y$ such that $|X| < |Y|$ yet there is a surjection from $X$ onto $Y$. For example, there are models of ${\sf ZF \neg C}$ in which $\mathbb{R}$ can be partitioned into a set that is bigger than it. Taylor & Wagon's "A Paradox Arising from the Elimination of a Paradox" describe a number of other examples as well.

My question is: can an analogous phenomenon arise for proper classes in standard class theories without class-theoretic analogues of choice — for example, ${\sf NBG}$ or ${\sf MK}$ without global choice or limitation of size?

While there's not a direct class-theoretic analogue of the notion of a "partition" for proper classes — after all, it's not sensible to speak of a class of proper classes — we can nonetheless "encode" cardinality comparisons between proper classes by understanding injections, surjections, and bijections simply as classes of ordered pairs — instead of sets of ordered pairs — with the relevant properties. So we can ask whether there are models of (say) ${\sf NBG}$ without global choice in which there are proper classes $X$ and $Y$ such that: (1) there is an injection from $X$ to $Y$, but not vice versa, and (2) there is a surjection from $X$ to $Y$. If there are such models, then these would be class-theoretic instances of the Division Paradox.

I was looking at Theorems 5 and 6 of Wagon & Taylor's paper in particular and wondering if the examples they describe (provided by Asaf Karagila) admit of a class-theoretic analogue, but I couldn't work this out for myself. One thing that is shown there is that ${\sf ZF}$, in conjunction with dependent choice and the claim that all sets of reals are Lebesgue measurable, proves that $|\mathbb{R} \cup \omega_1| < |\mathbb{R} \times \omega_1|$, yet there is a surjection from $\mathbb{R} \cup \omega_1$ to $\mathbb{R} \times \omega_1$. Can we prove a class-theoretic analogue of this result (or something similar) in a choiceless setting — e.g., if we replaced $\omega_1$ with the class of all ordinals?

Answer 1

The answer is yes.

First, let us observe the following lemma. Let us work in GBc, that is, Gödel-Bernays set theory with the axiom of choice, but only choice for sets, and not global choice.

Lemma. If global choice fails, then there is a proper class $A$ with no class injection $F:\newcommand\Ord{\text{Ord}}\Ord\hookrightarrow A$.

Proof. Suppose global choice fails. Let $A$ be the class of all well-orderings of any rank-initial segment $V_\alpha$ of the universe. Any injection of $\newcommand\Ord{\text{Ord}}\Ord$ into $A$ would have to hit arbitrarily large $V_\alpha$, and from it we could therefore define a well ordering of the universe. Namely, $x<y$ when the rank of $x$ is below the rank of $y$ or they have the same rank and the first order in the injection that puts them in an order places $x<y$. $\Box$

Meanwhile, every proper class maps surjectively onto $\Ord$, since it must contain sets of arbitrarily large ranks, and so we can map surjectively to an unbounded subclass of $\Ord$, but by omitting the missing elements, we get a copy of $\Ord$.

Theorem. If global choice fails, then there are classes $X$ and $Y$ such that

1. $X$ injects into $Y$, but not conversely. i.e. $X<Y$.
2. $X$ surjects onto $Y$.

Proof. Let $X=\omega\times A$ and $Y=X\sqcup\Ord$, where $A$ is as in the lemma. It is clear that $X$ injects into $Y$ since it is a subclass. The class $X$ also surjects onto $Y$, because we can use $\{0\}\times A$ to map onto the ordinals, since $A$ has elements of unbounded rank, and then shift $\{n+1\}\times A$ to $\{n\}\times A$. But there is no injection of $Y$ to $X$, since I claim indeed that there is no injection of $\Ord$ to $X$. Any such injection would have to pick elements of the form $(n,a)$ for $a\in A$, and from it we could define an injection $\Ord\hookrightarrow A$ by looking at the first ordinal which hits any $(n,a)$ and deleting other uses of $a$ (and then reindexing the domain). $\Box$

Another way to state the example is as follows.

Theorem. If global choice fails, then there is a class $X$ with an equivalence relation $\sim$, such $X$ has strictly more equivalence classes than elements. That is,

1. There is a class function $X$ to $X$ such that distinct elements map to $\sim$-inequivalent elements, but
2. There is no class function $F:X\to X$ that is constant on $\sim$-classes with a different value on different classes.

Proof. Use the same $X$ as in the previous theorem, and define $\sim$ to make all $(0,a)$ of the same rank equivalent, but all others inequivalent. That is, in the first section only, we identify the elements of $A$ by rank. This amounts to putting a copy of $\Ord$ into the quotient, as in $Y$. We can map $X$ injectively to the quotient by shifting sections, but there is no function $F$ from the quotient to $X$ since that would provide a map from Ord to $X$, which is impossible as we have argued. $\Box$

Since global choice implies that all proper classes are equinumerous, what the theorem shows in consequence is that the class partitition paradox phenomenon is simply equivalent to the failure of global choice.

Finally, let me pull the analysis back to ZFC.

Theorem. The following are equivalent in ZFC.

1. There is no definable global well order (with parameters).
2. The partition paradox holds for some definable classes. That is, there is a definable class $X$ having a equivalence relation $\sim$ so that $X$ has strictly more $\sim$-equivalence classes than elements.

Proof. Note first that by equipping any ZFC model with its definable classes, we get a model of GBc. If there is such a definable global well order, and this implies that all proper classes are definably equinumerous with $\Ord$. In this case, the partition paradox does not occur.

If there is no such definable global well order, then we can run the counterexample above, which involves definable classes only. $\Box$

Let me clarify the formalism of the statement of the theorem, since these statements are not directly first-order assertions in set theory. The situation is that if there is a definable global well order, then one can prove in each case separately that no definable class is an instance of the partition paradox. And if there is no definable global well order, then we get the specific definable instance of the proof. In other words, if that instance is not a paradoxical case, then we can deduce the scheme for all other definitions that they are also are not paradoxical.

Answer 2

Let me just add one small example to Joel's very good answer, which deals with the a case where $\sf AC$ fails (for sets).

In your typical model of the form $L(\Bbb R)$ we will usually have the failure of the ordering principle. Namely, some sets cannot be linearly ordered, this is because if we can linearly order $[\Bbb R]^\omega$, the countable subsets of reals, then there are sets without the Baire property and sets which are not Lebesgue measurable, etc., and the typical $L(\Bbb R)$ is a Solovay model.

On the other hand, there is a definable surjection from $\Bbb R\times\rm Ord$ onto $L(\Bbb R)$. The former class can be linearly ordered, therefore there is no injection in the other direction, which means that there is a partition of $\Bbb R\times\rm Ord$ into strictly more parts.