Thread: Countable 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.

Well, what you need to show is that countable ordinals are closed under product and countable union.

Originally Posted by emakarov

Well, what you need to show is that countable ordinals are closed under product and countable union.

How do I do that by induction? I don't really know where to start.

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.