# Countable ordinals

• Mar 5th 2010, 05:43 AM
KSM08
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.
• Mar 5th 2010, 09:26 AM
emakarov
Well, what you need to show is that countable ordinals are closed under product and countable union.
• Mar 5th 2010, 01:08 PM
KSM08
Quote:

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.
• Mar 5th 2010, 01:54 PM
emakarov
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.