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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.