Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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). –  Andres Caicedo Dec 29 '12 at 17:08
2  
"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. –  Andres 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+ –  Andres Caicedo Dec 29 '12 at 19:21

2 Answers 2

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

share|improve this answer
    
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$.

share|improve this answer
    
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 at 4:07

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.