I've read that $2^{\aleph_0} \geq \aleph_1$ by Cantor's theorem. Can someone please elaborate further?

I know that $|\mathbb{R}| = 2^{\aleph_0}$ but I cannot find a connection to $\aleph_1$ especially not with Cantor's theorem.


Chris Eagle's answer is correct, but there are subtleties around it which are worth mentioning.

First of all, we have to actually prove that there is a smallest uncountable cardinal before we can call it $\aleph_1$, and this is nontrivial. This breaks into two pieces, and the key to the second one is the axiom of choice, $\mathsf{AC}$:

  • Without using $\mathsf{AC}$ we can show that the ordinals are well-(pre)ordered by cardinality and that there is an uncountable ordinal. Consequently "the least uncountable ordinal" makes sense, and this is what we call $\aleph_1$ or $\omega_1$ (the notations mean the same thing but serve as context clues due to an obnoxious overload of notation - see cardinal arithmetic vs. ordinal arithmetic, and become sad).

  • $\mathsf{AC}$ then tells us that every set is in bijection with some ordinal. So in fact we are justified in referring to $\aleph_1$ as "the least uncountable cardinal:" if $X$ is an uncountable set, then there must be an injection of $\aleph_1$ into $X$.

Note that the first bulletpoint above concretely describes $\aleph_1$; however, that description is rather technical. Basically, $\mathsf{CH}$ is the hypothesis that we can replace the ordinals-based description of $\aleph_1$ with a much more intuitive one, namely "the cardinality of $\mathbb{R}$."

Second, the use of choice above suggests an immediate question: what if we don't assume choice? That is, what if we work in $\mathsf{ZF}$ instead of $\mathsf{ZFC}$?

In this case things become much more complicated. $\aleph_1$ still makes sense, but it's possible that it's incomparable with $\mathbb{R}$: it could be the case that neither injects into the other. (Interestingly, $\mathsf{ZF}$ does prove that there is a surjection from $\mathbb{R}$ onto $\omega_1$, but we don't want to compare set sizes via surjections: unlike with injections, given surjections $A\rightarrow B$ and $B\rightarrow A$ we cannot in general recover a bijection $A\leftrightarrow B$ without the axiom of choice.)

In the choiceless context therefore we also get a "weak continuum hypothesis:" this is the hypothesis that every uncountable set of reals is in bijection with $\mathbb{R}$. Assuming a certain natural alternative to choice, we have in fact that $\aleph_1$ and $\mathbb{R}$ are incomparable but the weak continuum hypothesis is true.

In summary, Cantor's theorem shows that there is no surjection from $\aleph_0$ to $2^{\aleph_0}$. However, the inequality $$2^{\aleph_0}\ge\aleph_1$$ is somewhat deeper than that: even if we assume the axiom of choice it takes some work to derive it from Cantor's theorem (indeed, much more work than it takes to prove Cantor's theorem itself), and without the axiom of choice it may be false (whereas Cantor's theorem doesn't use the axiom of choice).

  • $\begingroup$ I've written at least one answer on each of those points, and you did too, probably. How about some in-site links? $\endgroup$ – Asaf Karagila Aug 18 '20 at 23:22

By definition, $\aleph_1$ is the smallest uncountable cardinal. Cantor proved that $\mathbb{R}$ is uncountable, thus $|\mathbb{R}|$ is at least as big as the smallest uncountable cardinal, so $2^{\aleph_0} \geq \aleph_1$.

  • $\begingroup$ Makes sense. Thanks. $\endgroup$ – Quotenbanane Aug 18 '20 at 19:16
  • 1
    $\begingroup$ @Quotenbanane Basically, a different way of stating $2^{\aleph_0}>\aleph_0$, the exact same way $n\geq 1$ is the same as $n>0$ when talking about integers. $\endgroup$ – Arthur Aug 18 '20 at 19:23

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.