Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
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.) –  Martin Sleziak Jan 16 '12 at 16:59

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.

share|improve this answer
    
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. –  Rudy the Reindeer Jan 16 '12 at 16:21
    
@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. –  Andres Caicedo Jan 16 '12 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.

share|improve this answer
    
Why is it possible that no injection exists in the absence of choice? –  Rudy the Reindeer Jan 17 '12 at 7:49
1  
@Matt: It is consistent with ZF that $\aleph_1\nleq2^{\aleph_0}$. –  Asaf Karagila Jan 17 '12 at 9:03

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.