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.

  • 2
    $\begingroup$ If you're allowed to use Axiom of Choice, you can choose $f(\alpha)$ as an arbitrary element of $\mathbb R\setminus \{f(\gamma); \gamma<\alpha\}$. (This set is non-empty, it is even uncountable.) $\endgroup$ Commented Jan 16, 2012 at 16:59
  • $\begingroup$ See also this question, this question and other posts linked there. $\endgroup$ Commented May 8, 2016 at 12:00

2 Answers 2


[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.

  • $\begingroup$ Thank you! Now I'm trying to figure out in which part of the definition of $f$ I went wrong. The comment in the notes I linked to seems misleading given your answer since it asks to construct $f$ using transfinite induction. $\endgroup$ Commented Jan 16, 2012 at 16:21
  • $\begingroup$ @Matt, I was confused. I'll have to think more to see if your construction can work. What you have described does not seem enough, though. One would have to be careful about the choice of cofinal sequences at limit stages to ensure injectivity. $\endgroup$ Commented Jan 16, 2012 at 16:33

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.

  • $\begingroup$ Why is it possible that no injection exists in the absence of choice? $\endgroup$ Commented Jan 17, 2012 at 7:49
  • 1
    $\begingroup$ @Matt: It is consistent with ZF that $\aleph_1\nleq2^{\aleph_0}$. $\endgroup$
    – Asaf Karagila
    Commented Jan 17, 2012 at 9:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .