0
$\begingroup$

Every countable ordinal $\alpha$ can be written uniquely in Cantor canonical form as a finite arithmetical expression, say $C(\alpha)$. We thus have the 1-1 correspondence between the countable ordinals and their corresponding finite Goedel (ordinal) numbers:

$C(\alpha) \leftrightarrow \lceil C(\alpha) \rceil$

Since the set of Goedel numbers $\{\lceil C(\alpha) \rceil\}$ is denumerable, shouldn't the set $\{C(\alpha)\}$ of countable ordinals also be denumerable, with cardinality $\aleph_{0}$?


Let me re-phrase my query:

Conventional wisdom argues (correctly if the set theory ZF is consistent) that the cardinality of the countable ordinals---which is the set of all the ordinals below the first uncountable ordinal $\varepsilon_{0}$, each of whom can be written in Cantor canonical (not normal) form as a finite arithmetical expression---is $\aleph_{1}$.

However, the equally well-defined set-theoretic 1-1 correspondence that I detailed above seems to imply that this cardinality is $\aleph_{0}$.

So, which is it?

For the meaning of 'Cantor canonical form' as used here and another, albeit more convoluted, 1-1 correspondence, see http://alixcomsi.com/45_Countable_Ordinals_Update.pdf

  • 3
    The Cantor normal form of $\epsilon_0$ is $\omega^{\epsilon_0}$. How does this fit into your scheme?2012-12-29
  • 0
    $\aleph_1$${}{}{}{}$2012-12-29
  • 0
    You have stumbled upon an interesting issue: As long as we have a "natural" way of representing all members of an initial segment of the ordinals, we have only represented countably many. One can go way beyond $\epsilon_0$, and pushing the boundary is an interesting (and useful) problem. You may want to look for the following article: "Natural well-orderings", by John N. Crossley, and Jane Bridge Kister. Archiv für mathematische Logik und Grundlagenforschung, 1987, Vol. 26 (1), pp 57-76. MR0881280 (88g:03079).2012-12-29
  • 3
    "Conventional wisdom argues (correctly if the set theory ZF is consistent) that the cardinality of the countable ordinals---which is the set of all the ordinals below ε0, each of whom can be written in Cantor canonical (not normal) form as a finite arithmetical expression---is ℵ1." No, it doesn't. The set of ordinals below $\epsilon_0$ is not the set of countable ordinals.2012-12-29
  • 1
    "Conventional wisdom argues (correctly if the set theory ZF is consistent) that the cardinality of the countable ordinals---which is the set of all the ordinals below the first uncomputable ordinal ε0, each of whom can be written in Cantor canonical (not normal) form as a finite arithmetical expression---is ℵ1." Again, no. $\epsilon_0$ is not the first uncomputable ordinal. You may want to check out the paper I suggested in a comment above. All the ordinals mentioned there are much much larger than $\epsilon_0$, and still countable. Or check the posts on #bigness by John Baez on Google+2012-12-29
  • 0
    You may also want to register and *edit* your question, rather than posting an edit/follow up as an answer to the question.2012-12-29

2 Answers 2

7

It is true that every ordinal can be written in a unique Cantor normal form, but in many cases this is a vacuous form. For example $\varepsilon_0$ is a countable ordinal such that $\omega^{\varepsilon_0}=\varepsilon_0$. Therefore the Cantor normal form of $\varepsilon_0$ is... $\omega^{\varepsilon_0}$.

Besides that the set of countable ordinals is a transitive set, and it is well-ordered by $\in$. It follows that it is an ordinal itself, denote it $\alpha$. However $\alpha$ cannot be countable, because then $\alpha\in\alpha$ which implies it is not well-ordered by $\in$ (and contradicts the axiom of regularity). Therefore $\alpha$ is uncountable.

But we note that every uncountable ordinal is strictly larger than all countable ordinals, and therefore $\alpha$ is the least uncountable ordinal. That is, $\alpha=\omega_1$ and therefore its cardinality is $\aleph_1$.

  • 0
    The Cantor normal form of $\varepsilon_0$ is not $\varepsilon_0$. It is $\omega^{\varepsilon_0}$.2012-12-29
  • 0
    @Chris: Thanks.2012-12-29
7

The cardinality of the set of countable ordinals is $\omega_1$ (or $\aleph_1$, if you prefer the $\aleph$ notation). Note that $\omega_1=\{\alpha:\alpha\text{ is an ordinal and }|\alpha|\le\omega\}$; if $\omega_1$ were countable, it would be a member of itself, violating the axiom of regularity.

Your first sentence is false: Cantor normal form does not allow you to write every countable ordinal as a finite arithmetical expression. The ordinals with such expressions are those below $\epsilon_0$, which is defined as the smallest fixed point of the map $\alpha\mapsto\omega^\alpha$.

  • 0
    Question: Take the set of all *finite* ordinal numbers $\{1,2,3,\dots\}$. Its cardinality is $\aleph_0$ right? Now, the set of all *countable* ordinal numbers includes exactly all finite ordinal numbers plus the element $\aleph_0$, right? IOW, the set of all countable ordinals is $\{1,2,3,\dots\}\cup\{\aleph_0\}$. It seems to me that the cardinality of this set is the sum of the cardinality of each part, which is $\aleph_0 + 1$, which is still $\aleph_0$. So why is it $\aleph_1$?2014-08-15
  • 1
    @chharvey Wrong: there are many more countable infinite ordinal numbers, for example the one you mentioned: $\{1,2,3,\ldots\}\cup\{\aleph_0\}$. When talking about ordinal numbers, it's a custom to write $\omega$ or $\omega_0$ instead of $\aleph_0$. Your number $\{1,2,3,\ldots\}\cup\{\aleph_0\}$ is actually $\omega+1\neq\omega$. You may find [this article](http://en.wikipedia.org/wiki/Ordinal_number) useful.2015-01-08