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.

How is the ordinal $\omega_1$ defined? I know that it is a supremum of all smaller ordinals, but then $\omega^\omega$ is also a supremum of all smaller ordinals. How can we distinguish these two numbers? Edit: changing the question into how $\omega^{\omega}$ can be shown countable, and how other countable ordinals can be shown to be countable.

share|improve this question
    
$\omega_1$ is the supremum of all countable ordinals. Have you read the Wikipedia article about this? –  MJD Sep 17 '12 at 4:06
    
@MJD I changed the question a bit. Would you answer this question also? thanks. –  John Natawabe Sep 17 '12 at 4:12
    
Now it's an interesting question! –  MJD Sep 17 '12 at 4:20
    
See also this question: Do $\omega^\omega=2^{\aleph_0}=\aleph_1$? –  Martin Sleziak Sep 17 '12 at 4:51
    
And also How is $\epsilon_0$ countable? –  Martin Sleziak Nov 6 '12 at 12:18

2 Answers 2

up vote 10 down vote accepted

$\omega^\omega$ is countable because it is a union of a countable collection of sets, each of which is itself countable: $$\omega^\omega = \bigcup_{i<\omega} \omega^i$$

So it suffices to show that:

  1. A union of a countable collection of countable sets is countable.
  2. $\omega^i$ is countable whenever $i$ is finite.

(1) should be familiar to you; it is the usual Cantor argument for showing that the rationals are countable. If the countable sets are $S_0, S_1\ldots$ with elements $S_i = \{s_{i0}, s_{i1}, \ldots\}$, then we can enumerate the union of the $S_i$ as $s_{00}; s_{10}, s_{01}; s_{20}, s_{11}, s_{02}; s_{30}, \ldots$.

(2) is not hard either; you can prove the the product of two countable sets is countable (essentially as in the previous paragraph) and then show that since $\omega^{i+1} = \omega\times\omega^i $, countability of $\omega^{i+1}$ follows from that of $\omega^i$, which is enough to establish the result.

(You may want to look up the notion of cofinality. An ordinal $X$ has countable cofinality if it is a countable union of smaller ordinals. If those smaller ordinals are themselves countable, then $X$ is countable. So to show that $\omega^\omega$ is countable, it is enough to show that it has countable cofinality, which we can do by observing that it is the union of the countable ordinals $\omega^i$ for finite $i$.)

Then similarly if $C$ is some countable ordinal, $\omega^C$ is countable. For we can write some countable sequence $c_0, c_1,\ldots$ whose limit is $C$, and then $\omega^C = \bigcup \omega^{c_i}$ expresses $\omega^C$ as a countable union of countable sets. So not only are $\omega$ and $\omega^\omega$ countable, so are $\omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$. And then we can take the union of countable the sequence of countable sets $\omega, \omega^\omega, \omega^{\omega^\omega}, \omega^{\omega^{\omega^\omega}} \ldots$ and conclude that this union, usually written $\epsilon_0$, is countable as well.

$\epsilon_0$ has the property that it is the smallest ordinal $x$ for which $x=\omega^x$. There is an infinite sequence of countable ordinals with this property, and their union is still countable.

There are quite a few countable ordinals, and some of them are very strange monsters. See for example Church–Kleene ordinal and the Feferman–Schütte ordinal.

share|improve this answer
2  
Importantly, there is an explicit sequence of countings of $\:\left\langle \omega^0,\omega^1,\omega^2,\omega^3,...\right\rangle\:$. $\hspace{1.5 in}$ (This allows the proof to go through in ZF.) $\;\;$ –  Ricky Demer Sep 17 '12 at 4:43
    
Did I miss something? I would have said this is exactly what I am saying in the paragraph that points out that the product of countable sets is countable. –  MJD Sep 17 '12 at 4:47
    
I would think you should say that "an explicit counting of $\omega^i$ yields an explicit counting of $\omega^{i+1}$". –  Ricky Demer Sep 17 '12 at 5:11
    
If one is lazy, one can avoid worrying about verifying that there are explicit countings of these ordinals, by noting that their definitions are absolute, and they are countable in $L$. –  Andres Caicedo Nov 5 '12 at 23:31

Generally speaking, the best course of action when trying to show that $\alpha$ is a countable ordinal, is to show that:

  1. $\alpha = \delta+n$ where $\delta$ is a limit ordinal (if $n=0$ then $\alpha=\delta$);
  2. $\delta$ is the limit of $\{f(\beta)\mid \beta<\gamma\}$ for some countable $\gamma$; and
  3. $f(\beta)$ is countable is countable whenever $\beta$ is countable.

For example, $\epsilon_0$ is the limit of $\omega^\omega,\omega^{\omega^\omega},\omega^{\omega^{\omega^\omega}},\ldots$. We can show that this is the limit of the recursive function $f(n+1)=\omega^{f(n)}$ and $f(0)=\omega$. We can further show that if $\beta$ is countable then $\omega^\beta$ is also countable (note that this is ordinal exponentiation) and therefore $\epsilon_0$ is the countable limit of countable ordinals and thus countable.

The same method can be applied to general ordinals, although obtaining such $f$ is often harder than it is in the case of $\epsilon_0$.

One caveat is that this is true in ZFC but not necessarily in ZF, where a countable union of countable ordinals may be countable.

share|improve this answer

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.