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.

Thank you for your help!


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).

  • $\begingroup$ 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…). $\endgroup$ – Watson Aug 21 '16 at 16:40
  • 3
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Aug 21 '16 at 16:45
  • 1
    $\begingroup$ 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) $\endgroup$ – Noah Schweber Aug 21 '16 at 16:48
  • 2
    $\begingroup$ 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? $\endgroup$ – Noah Schweber Aug 21 '16 at 16:49
  • 1
    $\begingroup$ 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/…. $\endgroup$ – 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.)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.