How does the Axiom of Choice affect the ability to determine that $|\mathcal{P}(\omega)|$ is an uncountable cardinal

Question

Kunen in his "Foundations of Math" p.$53$ https://www.math.wisc.edu/~miller/old/m771-10/kunen770.pdf says that under the Axiom of Choice (i.e., every set can be well-ordered), the continuum $|\mathcal{P}(\omega)|$ is an uncountable cardinal.

[Yet] by Cohen, ZF does not prove $\mathcal{P}(\omega)$ is well-orderable.

How does well-orderable or not well-orderable come to affect the ability to determine that $|\mathcal{P}(\omega)|$ is an uncountable cardinal?

(Ironically, he subsequently goes on to say: By the following one is able to produce uncountable cardinals without using AC.

He is referring to his proof of Hartogs theorem: For every set $A$ there is a cardinal $\kappa$ such that $\kappa\npreceq A$.

Yet in that proof he says :$W$ is the set of all well-orderings of all subsets of $A$.

But I just mention this as an aside.)

Thanks

Answer 1

There is no tension between these facts, although if you say them quickly they sound contradictory for a while.

The key word here is "cardinal" - in the absence of choice, we have to be careful about what we mean by this! Or rather, we (this isn't universal, but let's follow Kunen for now) still define a cardinal to be "an ordinal not in bijection with any smaller ordinal" (= an initial ordinal), but we now have to be careful:

If choice fails, some sets are not in bijection with any cardinal!

(This is less mysterious than it may sound: being well-orderable is the same as admitting a bijection with some ordinal, and every ordinal is in bijection with some cardinal, namely the largest initial ordinal $\le$ it.)

Put another way:

Without choice, the "cardinality" of a set need not be a cardinal.

Let's leave aside the task of defining "cardinality," as opposed to "cardinal," without choice; it can easily be done, but it's a bit of a digression here. Your real question is about the following three principles:

• $(1)$ $\mathcal{P}(\omega)$ is uncountable.

• $(2)$ There is an uncountable cardinal.

• $(3)$ $\mathcal{P}(\omega)$ is in bijection with an uncountable cardinal (this is what "$\vert\mathcal{P}(\omega)\vert$ is an uncountable cardinal" really means for us at the moment, having not defined "$\vert \cdot\vert$" in the absence of choice).

The point here is:

$(1)$ and $(2)$ are provable without choice, but $(3)$ requires choice.

• The proof of $(1)$ is just Cantor's diagonal argument, and nowhere invokes choice.

• To prove that $(3)$ needs choice, we construct a model of ZF in which $\mathcal{P}(\omega)$ is not well-orderable, hence not in bijection with any cardinal (uncountable or countable). This was done by Cohen via forcing, and is too complicated to explain here.

• Finally, to prove $(2)$ without choice, we reason as follows:

  • Let $W$ be the set of equivalence classes of well-orderings with domain $\subseteq\omega$ under "is order-isomorphic to." We can prove that $W$ is a set using the ZF axioms, the key ones being Powerset and Separation.

  • By transfinite induction, every well-ordering is order-isomorphic to a unique ordinal (note: this crucially uses Replacement), and clearly order-isomorphic well-orderings are isomorphic to the same ordinal. So we get a "definable map" from $W$ to the ordinals, hence since $W$ is a set we get by Replacement the set $S$ of ordinals corresponding to elements of $W$.

  • $S$ is closed downwards (exercise) hence an ordinal itself. But every countable ordinal is order-isomorphic to a well-ordering with domain $\subseteq\omega$ (exercise), so if $S$ were countable we would have $S\in S$, violating Foundation; so $S$ must be an uncountable ordinal. We could also avoid using Foundation and just argue directly that $S$ is uncountable; Foundation here is a bit wasteful.

Incidentally, the relationship between $\omega_1$ - the supremum of the countable ordinals, or equivalently the first uncountable ordinal (in fact, $\omega_1$ is our $S$ above) - and $\mathcal{P}(\omega)$ is complicated: it is consistent with ZF (and a consequence of certain natural anti-choice axioms like AD) that $\omega_1$ and $\mathcal{P}(\omega)$ are incomparable in the sense that neither admits an injection into the other. Meanwhile, ZF proves of course that there is a surjection from $\mathcal{P}(\omega)$ onto $\omega_1$, and it is consistent even with ZFC that there is no surjection from $\omega_1$ to $\mathcal{P}(\omega)$ (consider a model where the continuum hypothesis fails).

Answer 2

This is a quirk in the definitions Kunen uses.

If we say that "$|A| = |B|$" if there is a bijection from $A$ to $B$, then ZF already proves that $|\omega| \not = |P(\omega)|$, as Kunen notes. So the cardinality of $P(\omega)$ is not countable.

But on p. 51, Kunen defines a "cardinal" to be an ordinal number $\alpha$ such that $\alpha = \min\{ \beta : |\beta| = |\alpha|\}$. As such, all "cardinals" in Kunen's definition are well orderable.

So, in ZF alone, we cannot prove that $P(\omega)$ has the same cardinality as any cardinal, although we can prove in ZF that if $P(\omega)$ has the same cardinality as a cardinal then that cardinal is uncountable.

This choice of definitions by Kunen is not universal - there are ways to define cardinals for all sets in ZF, as described at this answer and the answers linked at the bottom of it. For people who work in ZF routinely, rather than ZFC, it seems to be more useful to distinguish between "well ordered cardinals" and "non well ordered cardinals" than to say that some sets have no cardinal at all, as Kunen seems to.

Answer 3

Kunen is doing that unfortunate thing, where you define cardinals only for well-ordered sets without choice.

And I say unfortunate, since it causes unnecessary confusion. While I agree that in order to define cardinals without choice we need to talk about the von Neumann hierarchy first, and this might not be the best starting point for a student, it is also possible to remark that we will address this definition in the future. But most people, when thinking about the foundation of set theory, are so immersed in the "lack of importance of non-AC to the discussion", that by the time they reached this point of the von Neumann hierarchy, the axiom of choice is deeply ingrained into their text and they forgot all about those "silly, non-well orderable sets".

Moving on. Yes. According to the approach taken by Kunen, the axiom of choice is needed to prove that $|\mathcal P(\omega)|$ is an uncountable cardinal, because cardinal means necessarily well-orderable.

But choice is only needed to show that $|\mathcal P(\omega)|$ is even a thing, not that it is uncountable. The fact is that $\sf ZF$ proves quite directly Cantor's theorem, so $\omega\prec\mathcal P(\omega)$, which means that the latter is most definitely uncountable. It just might not have a cardinal, when going with Kunen's approach here.

 

So what about uncountable cardinals in general? Well, the [well-ordered] cardinals are generated by means of Hartogs' theorem, unions, and transfinite recursion. They are always ordinals. They only exits, as follows from the axioms of $\sf ZF$.

So we get two ways of generating larger and larger sets: Hartogs' operation, and the power set operation. Even assuming choice these may give us two different functions ($\aleph$ and $\beth$ numbers).