Can anyone help with the following problem:

If a and b and countable ordinals, prove by induction that a^b is a countable ordinal. (Usual recursive definition of ordinal exponentiation). You're allowed to assume the Axiom of Choice...

Many thanks.

Printable View

- Mar 5th 2010, 06:43 AMKSM08Countable ordinals
Can anyone help with the following problem:

If a and b and countable ordinals, prove by induction that a^b is a countable ordinal. (Usual recursive definition of ordinal exponentiation). You're allowed to assume the Axiom of Choice...

Many thanks. - Mar 5th 2010, 10:26 AMemakarov
Well, what you need to show is that countable ordinals are closed under product and countable union.

- Mar 5th 2010, 02:08 PMKSM08
- Mar 5th 2010, 02:54 PMemakarov
These two facts you prove without induction. After that, if you know that a^n is countable and a^{n+1}=a^n * a, you apply the first fact to show that a^{n+1} is countable. Similarly, when (a) is the union of a^n, each of which is countable by induction hypothesis, you apply the second fact to show that (a) is countable.

One way of proving that a * b is countable when a and b are is to write an infinite grid with elements of a labeling rows and elements of b labeling columns. Then, starting from a corner, it is possible to draw a line that goes back and forth and eventually goes through each point in the grid. There is probably a picture of this in Wikipedia in the discussion of countability.