Cantor's diagonalization argument shows that the power set of natural numbers is larger than $\aleph_0$, that is, it has a larger cardinality. Every natural number could either be in any given set of the superset, or it could be out of said set. So, that gives two possibilities for every natural number. Since there are infinite natural numbers, that is $2^\omega$ different sets. Therefore, the superset of the natural numbers has an order of $2^\omega$. Therefore, $2^\omega$ has a larger cardinality than $\omega$ because it can not be counted, as it is equal to the superset of natural numbers, which is of a larger cardinality then the set of all natural numbers.

If this were a valid proof, then $\omega_1$ would not be the first ordinal that is higher than $\omega$, as is the current mathematical consensus, as far as I know. Why is this not a valid proof, or what have I misunderstood about ordinals and cardinals?

  • $\begingroup$ Context needed: what is your basis for calling this proof invalid? $\endgroup$ – Eric Towers Dec 27 '19 at 7:27
  • $\begingroup$ Eric Towers, ω1 is the first ordinal with a larger cardinality than aleph-zero, at least from what I have heard. $\endgroup$ – Electro-blob Dec 27 '19 at 7:34
  • $\begingroup$ You have not used "$\omega_1$" nor have you compared it with $\aleph_0$ in the Question. So, right now, your comment is unrelated to your Question. $\endgroup$ – Eric Towers Dec 27 '19 at 7:36
  • $\begingroup$ Don't mix operations on ordinals with those on cardinals. $\endgroup$ – Henno Brandsma Dec 27 '19 at 7:38

$2^\omega$ is exponentiation of ordinals, while $2^{\aleph_0}$ is exponentiation of cardinals (and that does give a larger cardinal than $\aleph_0$ corresponding to the power set of $\aleph_0$, that is what Cantor's argument is.)

$2^\omega$ is defined as the limit of the finite ordinals $2^n$ (because $\omega$ is the limit of the finite ordinals), and so is just $\omega$ again. Note that ordinal exponentiation works quite differently from the cardinal one, see here, e.g. or any good set theory text book.

Indeed $\omega_1$ is by definition the first uncountable (not in bijection with a subset of $\omega$) ordinal and hence (as cardinals are special ordinals) equal to $\aleph_1$. Operations on ordinals produce ordinals, and e.g. $\omega+1 \neq 1+\omega$ in ordinals, while in cardinals $\aleph_0 + 1 = 1 + \aleph_0 = \aleph_0$, etc. As sets $\aleph_0$ and $\omega$ are the same but the operations are different. One is used to measure sizes of sets, the other "measures" well-orders on sets. Beware of the differences!


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.