# What is the cardinality of the countable ordinals?

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

-
The Cantor normal form of $\epsilon_0$ is $\omega^{\epsilon_0}$. How does this fit into your scheme? – Chris Eagle Dec 29 '12 at 16:57
$\aleph_1$${}{}{}{}$ – André Nicolas Dec 29 '12 at 16:57
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). – Andrés Caicedo Dec 29 '12 at 17:08
"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. – Andrés Caicedo Dec 29 '12 at 19:20
"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+ – Andrés Caicedo Dec 29 '12 at 19:21

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

-
The Cantor normal form of $\varepsilon_0$ is not $\varepsilon_0$. It is $\omega^{\varepsilon_0}$. – Chris Eagle Dec 29 '12 at 17:02
@Chris: Thanks. – Asaf Karagila Dec 29 '12 at 17:05

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

-
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$? – chharvey Aug 15 '14 at 4:07
@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 useful. – Heimdall Jan 8 '15 at 16:32