3
$\begingroup$

I have seen some other questions about the proofs around ordinals and $\omega$ and $\omega_1$, but some of the answers have confused me.

An ordinal $\alpha$ is countable if $\alpha < \omega_1$.

$\omega_1$ is the first uncountable ordinal and it is assumed that for $\alpha, \beta < \omega_1$, $\alpha + \beta < \omega_1$.

Now, my initial thought, similar to the answers in the 'Prove $\omega + \omega_1 = \omega_1$' style of questions is that we substitute $\omega$ and $\omega_1$ as $\alpha$ and $\beta$ respectively. Then I would obtain $\omega + \omega_1 < \omega_1$.

Similarly, I could substitute again into $\alpha + \beta \geq max \{\alpha, \beta \}$ to get $\omega + \omega_1 \geq max \{\omega, \omega_1 \} = \omega_1$. So we have an upper and lower bound and can claim $\omega + \omega_1 = \omega_1$.

But my question is, how does this work since $\omega_1$ is uncountable (and so we cannot say $\omega_1 < \omega_1$)?

$\endgroup$
3
$\begingroup$

HINT: Use the definition of ordinal addition, and the fact that adding two countable ordinals is countable.

$\endgroup$
  • $\begingroup$ $\alpha + \beta = sup \{\alpha + \gamma | \gamma < \beta \}$. $\omega + \omega_1 = sup \{\omega + \gamma | \gamma < \omega_1 \}$. And since $\gamma < \omega_1$ it is countable, and the supremum is the same as $\bigcup \{\omega + \gamma | \gamma < \omega_1 \}$, which is a union of countable ordinals. Is that right? $\endgroup$ – Math Student 91 Mar 16 '14 at 17:25
  • $\begingroup$ Yes. And what can be the supremum of uncountably many different countable ordinals? $\endgroup$ – Asaf Karagila Mar 16 '14 at 17:27
  • $\begingroup$ would this be $\omega_1$? $\endgroup$ – Math Student 91 Mar 16 '14 at 17:49
  • $\begingroup$ What could it be? $\endgroup$ – Asaf Karagila Mar 16 '14 at 18:45
  • 1
    $\begingroup$ Don't guess. Look at the definitions. What could be the supremum of a set of countable ordinals? $\endgroup$ – Asaf Karagila Mar 17 '14 at 11:30
3
$\begingroup$

You should really think of $\alpha+\beta$ as the result of "concatenating" an order of type $\alpha$ with one of type $\beta$. Formally, this is the ordinal corresponding to the well-order on $(\alpha\times\{0\})\cup(\beta\times\{1\})$, ordered by $(a,i)<(b,j)$ iff $i=j$ and $a<b$, or else $i<j$. Think of this as putting $\alpha$ dots in a row, and then $\beta$ additional dots.

To show $\omega+\omega_1=\omega_1$, it is enough to see that, in fact, already $\omega+\omega^2=\omega^2$ (and therefore $\omega+\beta=\beta$ for any $\beta\ge\omega^2$). For this, note that $1+\omega=\omega$, which should be clear from the "dots description": You have $\omega$ dots in a row, if you add an extra dot at the beginning, that is still just $\omega$ dots in a row. Now, $\omega^2$ is simply the result of replacing each of these dots with $\omega$ many.

$\endgroup$
0
$\begingroup$

"Pictorially", the result is clear. If you draw a line, mark the points of $\omega$ on this line from left to right and then mark the points of $\omega_1$, it is more or less obvious that the resulting (well) ordered set is isomorphic to $\omega_1$.

One may explain this as follows.

The countable ordinals start like this: $0, 1, 3,\dots ,\omega, \omega+1, \omega+2, \omega+3,\dots ,\omega+\omega=\omega\cdot 2, \omega\cdot 2+1, \omega\cdot 2+2,\omega\cdot 2+3,\dots ,\omega\cdot 2+\omega=\omega\cdot 3,\dots ,\omega\cdot n,\dots , \omega\cdot\omega, \dots $

If you add $\omega=\{ 0,1,2, 3,\dots \}$ on the left; this gives you the "sequence" $0,1,2,\dots , 0,1,2,\dots ,\omega, \omega+1,\omega+2,\dots ,\omega\cdot 2, \dots $.

Now relabel your sequence in the obvious way: the second "$0$" is relabelled "$\omega$", the second "$1$" is relabelled "$\omega+1$", ..., "$\omega$" is relabelled "$\omega\cdot 2$", ..., "$\omega\cdot 2$" is relabelled "$\omega\cdot 3$" and so on.

The transfinite sequence thus obtained is exactly $\omega_1$, i.e. $\omega+\omega_1=\omega_1$.

A more "formal" proof would consist in doing what Asaf suggests.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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