5
$\begingroup$

I'm having a hard time with the functions defined by transfinite induction, in particular I have the sum of two ordinals defined as follows: \begin{align}\alpha+0&=\alpha \\ \alpha+s(\beta)&=s(\alpha+\beta)\\ \alpha+\beta&=\sup_{\gamma<\beta}(\alpha+\gamma)\quad \mbox{(if $\beta$ is a limit ordinal)} \end{align}

I've noticed that if $\alpha<\omega$ then $\alpha + \omega =\omega$ and it seems to me that if I replace $\omega$ by any other countable limit ordinal that assertion still holds, is this right? And, can it be generalized to any limit ordinal?

I feel I'm still not able to grasp the intuition behind it.

$\endgroup$
3
$\begingroup$

Yes, it is the case that if $\alpha < \omega$, then $\alpha + \omega = \omega$, and similarly for other countable limit ordinals $\beta$ that $\alpha + \beta = \beta$.

A way of thinking of this that may be more intuitive for you than the definition that you give is that the ordinal sum $\alpha + \beta$ is the order type that you get by ``gluing a copy of $\beta$ after $\alpha$''.

Formally, if we define the set $$ S_{\alpha, \beta} = \{(0, i) \mid i < \alpha\} \cup \{(1, j) \mid j < \beta\}, $$

and order $S_{\alpha, \beta}$ lexicographically, then $\alpha + \beta$ is exactly the order type of $S_{\alpha, \beta}$, which we can show by a transfinite induction on $\beta$:

If $\beta = 0$, then $S_{\alpha, \beta} = \{(0, i) \mid i < \alpha\}$, which has order type $\alpha$, as shown by the map $(0, i) \mapsto i$.

If $\beta = s(\gamma)$, then $S_{\alpha, \beta} = S_{\alpha, \gamma} \cup \{(1, \gamma)\}$, which has order type equal to ${\rm ot}(S_{\alpha, \gamma}) + 1$, which, by induction, is precisely $\alpha + \gamma + 1 = s(\alpha + \gamma)$.

If $\beta$ is limit, then we note that $S_{\alpha, \beta} = \bigcup\limits_{\gamma < \beta} S_{\alpha, \gamma}$, and since the $S_{\alpha, \gamma}$ are nested and increasing, we have easily that ${\rm ot}(S_{\alpha, \beta}) > {\rm ot}(S_{\alpha, \gamma})$ for all $\gamma < \beta$.

It therefore remains to show that this is the least upper bound. But if $\delta < {\rm ot}(S_{\alpha, \beta})$, then there is some $\gamma$ such that $\delta < {\rm ot}(S_{\alpha, \gamma})$, and so we have that ${\rm ot}(S_{\alpha, \beta}) = \alpha + \beta$.

$\endgroup$
10
$\begingroup$

Edit: There's an amusing generalization of all this at the bottom.

An ordinal determines an ordering. The ordering corresponding to the sum of two ordinals is "first an ordering like this one, followed by an ordering like that one".

So for example the ordinal $3$ corresponds to three things in a row: $xxx$ .

And $\omega$ corresponds to an infinite sequence: $xxxxxx\dots$ .

If you take three things in a row and follow them by an infinite sequence you get an infinite sequence: $$xxx,xxx\dots = xxx\dots$$So $3+\omega=\omega$.

If $n<\omega$ then $n+\alpha=\alpha$ for any infinite ordinal $\alpha$, nothing to do with whether it's a limit ordinal. Because $\alpha$ starts with an infinite sequence, then perhaps has more added on - that sequence eats the $n$, as in the example $3+\omega=\omega$ above.


Amusing Generalization. For $n<\omega$ define $\alpha n=\alpha+\dots+\alpha$. Define $\alpha\omega=\bigcup_{n<\omega}\alpha n.$

Theorem Suppose $\alpha$ and $\beta$ are ordinals. We have $\alpha+\beta=\beta$ if and only if $\alpha+\beta$ is obviously equal to $\beta$.

Or a little more explicitly,

Theorem Given two ordinals $\alpha$ and $\beta$, we have $\alpha+\beta=\beta$ if and only if $\beta\ge\alpha\omega$.

Proof: If $\alpha+\beta=\beta$ then $\alpha n+\beta=\beta$, and hence $\beta\ge\alpha n$, for every $n<\omega$. Hence $\beta\ge\alpha\omega$.

Otoh if $\beta\ge\alpha\omega$ then $\beta=\alpha\omega+\gamma$, hence $\alpha+\beta=\beta$.

$\endgroup$
  • $\begingroup$ Sorry, I missed it in the last paragraph somehow. $\endgroup$ – Ross Millikan May 18 '16 at 23:39
7
$\begingroup$

The intuition is actually quite a bit simpler than the recursive definition. For any linear orders $\langle A,\le_A\rangle$ and $\langle B,\le_B\rangle$, not necessarily well orders, we can define a linear order that is their sum: the underlying set is $(\{0\}\times A)\cup(\{1\}\times B)$, and the order $\le$ is lexicographic: $\langle i,x\rangle\le\langle j,y\rangle$ iff either $i<j$, or $i=j=0$ and $x\le_A y$, or $i=j=1$ and $x\le_B y$. Essentially we’re just putting $B$ with its given linear order after $A$ with its linear order:

$$\overset{A}\longrightarrow\overset{B}\Longrightarrow\;.$$

The bit with the $0$ and $1$ is a technical detail to ensure that we’re working with disjoint sets; it’s unnecessary if $A$ and $B$ are disjoint.

In the case of ordinals $\alpha$ and $\beta$, we can form a sum in just this fashion: the underlying set is $(\{0\}\times\alpha)\cup(\{1\}\times\beta)$, and we have $\langle i,\xi\rangle\le\langle j,\eta\rangle$ iff $i<j$, or $i=j$ and $\xi\le \eta$. It’s not at all hard to check that this order $\le$ is a well-order, so it is order-isomorphic to a unique ordinal $\gamma$, and we write $\alpha+\beta=\gamma$. Intuitively, $\gamma$ is the ordinal whose order type is obtained by sticking a copy of $\beta$ after a copy of $\alpha$.

It might be worthwhile to try proving to yourself that this more intuitive approach yields the same result as the recursive definition.

When $\alpha$ is finite and $\beta$ is not, $\alpha$ together with the first $\omega$ elements of $\beta$ still form just one copy of $\omega$, so — as you said — in this case $\alpha+\beta=\beta$. This can be generalized, but it takes a bit of care. Let $\alpha_0=\alpha$. Given $\alpha_n$ for some $n\in\omega$, let $\alpha_{n+1}=\alpha_n+\alpha$. Finally, let $\eta=\sup_n\alpha_n$. (In fact $\eta=\alpha\cdot\omega$, which the multiplication is ordinal multiplication.) Then $\alpha+\beta=\beta$ whenever $\beta\ge\eta$, because one more $\alpha$ just gets absorbed into the initial $\eta$ part of $\beta$.

$\endgroup$
3
$\begingroup$

Perhaps you can understand better if you compare it with a direct definition : the sum of $\alpha$ and $\beta$ is the unique ordinal isomorphic to the well-ordered set $\alpha \coprod \beta$ given the order the extends that of $\alpha$ and $\beta$ and such that every element of $\alpha$ is strictly inferior to any element of $\beta$ (so it's like you put a copy of $\alpha$ next to a copy of $\beta$).

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