# Thread: Countable ordinal mapping w/ order preserving function

1. ## Countable ordinal mapping w/ order preserving function

Here's the problem as stated:
Show if $\alpha$ is any countable ordinal, then $\exists f:\alpha \rightarrow \Re$ (to the reals) where $f$ is order preserving... So $\beta \epsilon \gamma \epsilon \alpha \Rightarrow f(\beta) < f(\alpha)$.

Now, the only idea I have is to create a function that will map any countable ordinal to $\Re$, for instance:

$1 \rightarrow .1$

$2 \rightarrow .12$

$3 \rightarrow .123$

$:$

$\omega \rightarrow .12345...$

So this cover through $\omega$. Do I need it to cover through $\omega_{1}$, the first uncountable ordinal? If so, what is an example of something that can get that large? Maybe all the irrationals, mapped similarly as above? Any help would be appreciated.

Note: I'm trying to avoid using the continuum hypothesis.

2. Can you use transfinite induction to beef up your construction, so that instead of just going up to $\omega$ it goes up to any countable ordinal $\alpha$?

3. Transfinite induction seems to be the way to go on this one.

In case anyone comes across this same sort of problem, I found the following at http://www.math.niu.edu/~rusin/known-math/00_incoming/countable_ord and it appears to have been posted by Dave Seaman of Purdue.

Lemma. Let Q(0,1) be the set of rationals in the interval (0,1). Then there is an order-preserving map f: Q -> Q(0,1).

Proof. Divide (0,1) into a countable number of subintervals such that the set of subintervals has the same order type as Z. For example, the partition points may be 1/2 +/- 1/2^k for k = 2, 3, 4, .... For each n, construct an order-preserving map of the rationals in [n,n+1) into the n-th subinterval of (0,1), where [1/2,3/4) is the zeroth subinterval.

Proposition. Let alpha be a countable ordinal. Then there is an order-preserving map f: alpha -> Q.

Proof. By transfinite induction. The case for successor ordinals follows immediately from the lemma.

Suppose gamma is a countable limit ordinal, and suppose { alpha_k } is a countable sequence of ordinals with lim_k alpha_k = gamma, where for each alpha_k we have an order-preserving f_k : alpha_k -> Q. Using the lemma, we may construct an order-preserving g_k : alpha_k -> Q(k,k+1), where the range is the set of rationals in the interval (k,k+1). Then we define f: gamma -> Q such that for each beta < gamma, we let k be the least index such that beta < alpha_k, and then define f(beta) = f_k(beta). The resulting map is clearly order-preserving, Q.E.D.

Notice it does not follow from this that there is an order-preserving map defined on the union of all the countable ordinals, since that is an uncountable set and any partition of the reals or rationals into nondegenerate intervals is necessarily a countable collection. In fact omega_1, the first uncountable ordinal, is the smallest ordinal that cannot be so mapped onto the rationals (or the reals).