4
$\begingroup$

Many books describe how one can construct "by hand" a table of ordinals $1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega +2,\ \ldots,\ \omega\cdot 2,\ \omega\cdot 2 +1,\ \ldots,\ \omega^{2},\ \ldots,\ \omega^{3},\ \ldots\ \omega^{\omega},\ \ldots,\ \omega^{\omega^{\omega}},\ \ldots, \epsilon_{0},\ \ldots$. But does this span the entire ordinal class? For some reason I can't seem to prove it. Is there an easy way to see that? Thanks!

$\endgroup$
7
  • 8
    $\begingroup$ There are uncountably many countable ordinals, so eventually you run out of descriptions. But not before you've got to some extraordinarily large and complicated ordinals ... $\endgroup$
    – gowers
    Jul 17, 2010 at 20:02
  • 15
    $\begingroup$ That rather depends on what your final ellipsis means ... :-) $\endgroup$ Jul 17, 2010 at 20:03
  • 4
    $\begingroup$ See en.wikipedia.org/wiki/Large_countable_ordinal. $\endgroup$ Jul 17, 2010 at 20:43
  • $\begingroup$ @Richard Thanks for the article reference. So apparently the table doesn't even exhaust countable ordinals... $\endgroup$
    – ashpool
    Jul 17, 2010 at 20:55
  • 2
    $\begingroup$ Sorry, Tim, I was referring to kwan's final ellipsis, not yours. $\endgroup$ Jul 18, 2010 at 7:26

1 Answer 1

6
$\begingroup$

Since ordinal numbers have a unique division, logarithm and subtraction properties, when given an ordinal $\alpha$ you can write any other ordinal as a finite polynomial in $\alpha$, when $\alpha = \omega$ you get what's known as "Cantor normal form of $\gamma$ for the base $\omega$".

I.e., any ordinal $\gamma$ can be written as a finite sum: $$\gamma = \sum_{i=0}^n \omega^{\alpha_i}\cdot\beta_i$$ Where $\alpha_i$ is a decreasing chain of ordinals, and $\beta_i$ is finite.

(More generally, you can take some base $\zeta$ and then $\beta_i < \zeta$)

Thing is that we only have a finite number of symbols, so at most we can represent (uniquely) a countable number of numbers, since we have a proper class of ordinals, which is a mind boggling concept of infinitude, you obviously can't write them all. But still, any given ordinal can be presented as a finite polynomial in $\omega$, thus spanning the table discussed.

$\endgroup$
11
  • 10
    $\begingroup$ For many ordinals $\alpha$, including all infinite cardinals (viewed as initial ordinals), the ordinal exponentiation $\omega^\alpha$ is just $\alpha$ again, meaning that the Cantor normal form of these ordinals $\alpha$ is just $\omega^\alpha\cdot 1$, which doesn't provide a representation of $\alpha$ in terms of smaller ordinals. That is, you need $\alpha$ to represent $\alpha$. These ordinals are called the $\epsilon$-numbers, and the smallest is known as $\epsilon_0$. The next is $\epsilon_1$ and so on. $\endgroup$ Jul 18, 2010 at 0:23
  • $\begingroup$ @Joel: More so, this "normal form" for these ordinals isn't unique. The CNFT only applies to ordinals less than epsilon-0. $\endgroup$ Jul 18, 2010 at 10:12
  • 4
    $\begingroup$ Charles, to my knowledge, it is unique, and it works for all ordinals, even uncountable ordinals. $\endgroup$ Jul 18, 2010 at 12:03
  • 1
    $\begingroup$ But I agree that the normal form below $\epsilon_0$ is indeed much nicer, because it is exactly in that region that the ordinals used in the CNF of an ordinal are always strictly less than the ordinal. Indeed, if one iterates the CNF by applying it also to the exponents, then one needs only finitely many natural numbers to represent any ordinal below $\epsilon_0$. This idea is central to the proof of Goodstein's theorem, mentioned in mathoverflow.net/questions/18100/…. $\endgroup$ Jul 18, 2010 at 14:19
  • 3
    $\begingroup$ Oh, I see now that you may have meant that this iterated representation is not unique, since for $\epsilon$-numbers, we have $\omega^\alpha=\omega^{\oemga^\alpha}$, precisely because $\omega^\alpha=\alpha$. I agree. $\endgroup$ Jul 18, 2010 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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