# Uncountable collection of cardinals, without the axiom of choice

I think that it is possible to have a countable collection of sets, in $\sf ZF$, such that they all have different cardinalities, namely $\{E_n \mid n ≥ 1\}$ with $E_0 = \Bbb N, E_{n+1}=\mathcal P(E_n)$. However, I was wondering:

Is it possible to construct, in $\sf ZF$, an uncountable collection of sets such that they all have different cardinalities?

(This is possible with the axiom of choice, we just take $\{\aleph_{\alpha} \mid \alpha < \omega_1\}$). I could take the union of all the $E_n$'s, which has cardinality greater than any of the $E_n$, and apply $\mathcal P(\cdot)$ again and again, but I always stay with countably many sets, in my opinion.

The axiom of choice is not needed at all: $\{\aleph_\alpha: \alpha<\omega_1\}$ provably exists in ZF alone. Recall that $\aleph_\alpha$ is defined as follows:

• $\aleph_0=\omega$,

• $\aleph_\lambda=\sup\{\aleph_\alpha: \alpha<\lambda\}$ for $\lambda$ a limit, and

• $\aleph_{\alpha+1}$ is the least ordinal $>\aleph_\alpha$ which is not in bijection with $\aleph_\alpha$.

The proof that $\aleph_\alpha$ exists for each ordinal $\alpha$ (and that $\{\aleph_\alpha: \alpha<\beta\}$ exists for each ordinal $\beta$, and that $\aleph_\alpha\equiv\aleph_\beta\iff\alpha=\beta$) doesn't use anything outside of ZF (indeed, it uses much less than ZF).

• Thank you for your answer. But for me the definition of aleph numbers requires Zermelo's theorem, a.k.a. AC. How can we define $\aleph_{\alpha}$ ($\alpha<\omega_1$) in ZF (this has probably already been asked on M.SE…). – Watson Aug 21 '16 at 16:40
• @Watson Choice simply plays no role here; the crucial axiom is Replacement, which gets invoked to show that $\aleph_\lambda$ exists for limit $\lambda$. The role of choice is to show that every set is in bijection with some $\aleph_\alpha$, but it has nothing to do with constructing the $\aleph_\alpha$s in the first place. – Noah Schweber Aug 21 '16 at 16:45
• To see it in detail, recall that ZF alone proves that the class of ordinals is well-ordered. So say that an ordinal $\alpha$ is tame if there is a sequence of sets $\{A_\beta: \beta<\alpha\}$ such that $A_0=\omega$, $A_\lambda=\bigcup_{\gamma<\lambda} A_\alpha$ for $\lambda\le\alpha$ a limit, and $A_{\gamma+1}$ is the least ordinal $>A_\gamma$ not in bijection with $A_\gamma$ for $\gamma<\alpha$. It's easy to show that such a sequence is unique if it exists. Since the ordinals are well-founded, if $\aleph_\alpha$ doesn't always exist then there is some least such $\alpha$. (cont'd) – Noah Schweber Aug 21 '16 at 16:48
• Could this $\alpha$ be a successor? No - Hartog's theorem. Could this $\alpha$ be a limit? No - use Replacement. Replacement, not choice, is the crucial axiom in transfinite recursion/induction arguments (it's what makes the limit stages work); choice only comes into play in such arguments when you don't have an explicit way to build $X_\gamma$ given $\{X_\beta: \beta<\gamma\}$, but that's not the case here. Does this make sense? – Noah Schweber Aug 21 '16 at 16:49
• By the way, for a taste of just how weird set theory without replacement can be, see my answer to math.stackexchange.com/questions/1402271/…. – Noah Schweber Aug 21 '16 at 16:56

The definition of the aleph numbers does not hinge on the axiom of choice. Rather it hinges on Hartogs theorem and Replacement. Both follow from $\sf ZF$, of course.

We define $\aleph_0$ to be $\omega$, and at successor steps we take the least ordinal which has a strictly larger cardinality than the previous step---such ordinal exists due to Hartogs theorem and Replacement. At limits we take the limits, of course.

But you can also just define by transfinite recursion a sequence of power sets, and it's fine. You don't need choice to prove $\omega_1$ exists. (At limits, take unions, of course.)

• Note to the OP: of course, we also need replacement to do the iterated powerset construction. No getting away from replacement! – Noah Schweber Aug 21 '16 at 16:55
• Yes, it seems you can't quite get away from Replacement here. – Asaf Karagila Aug 21 '16 at 16:59