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