1
$\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

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

  • 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