# Prove using transfinite induction that if ordinals $\alpha$ and $\beta$ are countable, then so is $\alpha + \beta$.

This question requires using transfinite induction. I plan to fix $\alpha$ and then do transfinite induction on $\beta$.

Recall that an ordinal $\alpha$ is countable if $\alpha < \omega_1$, where $\omega_1$ is the first uncountable ordinal.

The successor of an ordinal $\alpha$ is the smallest ordinal number greater than $\alpha$. An ordinal number that is a successor is called a successor ordinal. An ordinal that is not a successor ordinal is either a limit ordinal or 0.

By the definition of ordinal addition, if $\beta$ is a successor ordinal then $\beta = \gamma + 1$ and so $\alpha + \beta = (\alpha + \gamma) + 1$. If $\beta$ is a limit ordinal, then $\alpha + \beta = \sup \{\alpha + \gamma \mid \gamma < \beta\}$.

Recall that transfinite induction is made up of three parts: Base case: Set $\beta = 0$. Successor case: Set $\beta = \gamma + 1$ for an ordinal $\gamma$. Limit case: Let $\beta$ be a limit ordinal.

I have managed to prove the base case (trivial) and the limit case, since this follows from the fact that the union of two countable sets is countable. However, I am stuck on proving the successor case.

Any help would be greatly appreciated and thanks in advance.

HINT: $\alpha+\beta+1$ is $\alpha+\beta\cup\{\alpha+\beta\}$.

• I think I made an error. I meant to say $\alpha + \beta = (\alpha + \gamma) +1$ for successor ordinal $\beta = \gamma + 1$. So then do I have $(\alpha + \gamma) + 1 = \alpha + \gamma \cup \{\alpha + \gamma\}$? – Math Student 91 Mar 15 '14 at 19:29
• Yes, simply replace $\beta$ by $\gamma$. – Asaf Karagila Mar 15 '14 at 19:30
• Sorry I'm still unsure about the successor case. Would you be able to give another hint please? – Math Student 91 Mar 15 '14 at 19:32
• If $A$ is countable, then for every $a$, $A\cup\{a\}$ is countable. – Asaf Karagila Mar 15 '14 at 19:33
• Does this assume that $\alpha + \gamma$ is countable? – Math Student 91 Mar 15 '14 at 19:34

This question does not need transfinite induction other than maybe in the definition of addition. Recall that $\alpha+\beta$ is the order type of a well-ordering whose underlying set is the disjoint union of $\alpha$ and $\beta$. So if $\alpha,\beta$ are countable, their disjoint union is and hence $\alpha+\beta$ is too. Similarly the product of two countable ordinals is countable too. It is also true for exponentiation: $\alpha^\beta$ is the order type of a certain well-ordering on the set of maps $\beta\to\alpha$ with finite support which is a countable set if $\alpha$ and $\beta$ are.

• If you haven't proved that addition can be defined using partition into initial/end segments, then this question very much needs transfinite induction. Moreover, multiplication and exponentiation follow immediately from addition using the transfinite definitions as well. (I do agree it's simpler to use the "direct" definitions, but not everyone are given those definitions.) – Asaf Karagila Mar 15 '14 at 19:29

For the successor case: Assuming $\alpha + \gamma$ is countable, prove that $\alpha + \gamma + 1$ is countable.

Proof: If $\alpha + \gamma$ is countable then there is a bijection $f: \mathbb N \rightarrow\alpha + \gamma$.

Define $g$ accordingly:

$g(0) = \alpha + \gamma + 1$; $g(n+1) = f(n)$ otherwise.

Then $g$ is a bijection from $\mathbb N$ to $\alpha + \gamma + 1$.

Thus, $\alpha + \gamma + 1$ is countable.