Injection from the set of countable ordinals $\Omega$ into $\mathbb{R}$

Question

I'm reading through this and I'd like to define an injective function from the set of countable ordinals $\Omega$ into $\mathbb{R}$ using transfinite induction (or maybe transfinite recursion?).

Clearly, $\emptyset \in \Omega$ will be defined to map to zero: $f(\emptyset) := 0$. Next one would probably make a distinction between limit ordinals and successor ordinals.

For successor ordinals $\beta$ one would probably assume that if $f(\alpha)$ is defined for all $\alpha < \beta$ and if $\beta = \alpha + 1$ then one can define $f(\beta) := f(\alpha) + 1$.

I'm not sure this is right but I'm even less sure about the case for limit ordinals. Now let $\beta$ be a limit ordinal and assume $f(\alpha)$ is defined for all $\alpha < \beta$. We have $\beta = \sup \{ \alpha \mid \alpha < \beta \}$ by the definition of limit ordinal and because $\beta$ is countable we can write this as $\beta = \sup \{ \alpha_i \mid \alpha_i < \beta , i \in \mathbb{N} \}$. Now I was thinking that maybe $f$ could be defined as $ f(\beta) := \sum_{i=0}^\infty 10^{-i} f(\alpha_i)$.

To show that this is injective it's probably enough to show that different limit ordinals map to different reals.

What do you think of this? Am I on the right track? Thanks for your help.

Answer 1

[Edit: I misunderstood your definition, and read as describing an injective function. The "solution" below explains why this cannot work.]

What you are suggesting is interesting. The question is whether we can assign to each limit ordinal a cofinal sequence in such a way that the $f$ you describe ends up being injective. I do not know off hand whether this is possible, but it is a nice problem (it is not clear yet whether $f$ is well-defined, i.e., whether one can arrange so that all the relevant series actually converge). Sorry for the original confusion.

---

The argument you are giving cannot work. This is because in your construction you are not only trying to define an injection, but in fact a strictly increasing function.

But if $f:\Omega\to{\mathbb R}$ is increasing, then for each $\alpha$ there will be rational in the interval between $f(\alpha)$ and $f(\alpha+1)$, and different values of $\alpha$ will correspond to different rationals. Of course, this is impossible as $\Omega$ is uncountable but ${\mathbb Q}$ is countable.

In fact, you will not be able to define an injection $f$ by any explicit procedure. This is because it is consistent with the axioms of set theory without choice that no such injections exist, and it is consistent with set theory plus choice that no such injection is definable.

One way to show that there are such injections is to use Zorn's lemma on the collection of injections $f$ whose domain is an ordinal. This is a partial order: $f\le g$ if $g$ extends $f$ as a function, i.e., iff $g$ has a larger domain than $f$, and the restriction of $g$ to the domain of $f$ is just $f$. Clearly a maximal element in this poset must have uncountable domain, since the reals are uncountable.

Answer 2

First, note that without the axiom of choice it is perfectly possible that no injection like this exists. This is a strong hint that a rather explicit definition is impossible.

Assuming the axiom of choice showing such injection exists is immediate since $2^{\aleph_0}\ge\aleph_1$. However if we wish to be slightly more explicit then we can do the following:

Let $Q:\mathbb Q\to\omega$ be an enumeration of the rationals. For every $\beta<\omega_1$ let $f_\beta:\beta\to\mathbb Q$ be an order embedding which exists since even without the axiom of choice $\mathbb Q$ embeds every countable linear order.

Now let $F:\omega_1\to 2^\omega$ be defined as $F(\beta)=Rng(Q\circ f_\beta)$, that is a subset of $\omega$ which has order type $\beta$ in the enumeration $Q$.

We use the axiom of choice in order to choose $f_\beta$'s for the ordinals below $\omega_1$. If, for example, the real numbers are countable unions of countable sets then there is no such sequence of bijections.

To see a slightly more explicit embedding of every ordinal in $\mathbb Q$ one can consider an Aronszajn tree and choose your embedding from the relevant branches, using this you can use the same trick to generate a subset of $\omega$ as before.