Embedding ordinals in $\mathbb{Q}$

All countable ordinals are embeddable in $\mathbb{Q}$.

For "small" countable ordinals, it is simple to do this explicitly. $\omega$ is trivial, $\omega+1$ can be e.g. done as $\{\frac{n}{n+1}:n\in \mathbb{N}\} \cup \{1\}$.

$\omega*2$ can be done as $\{\frac{n}{n+1}:n\in \mathbb{N}\} \cup \{1+\frac{n}{n+1}:n\in \mathbb{N}\}$, and $\omega*n$ as $\bigcup_{i\le n} \{i+\frac{n}{n+1}:n\in \mathbb{N}\}$

That immediately also gives $\omega^2$ as $\bigcup_{i \in \mathbb{N}} \{i+\frac{n}{n+1}:n\in \mathbb{N}\}$

And going further is still relatively easy: We can biject the above embedding of $\omega^2$ onto a single interval $(0,1)$, e.g. through $f(x)=1-\frac{1}{x+1}$ since this is an order preserving bijection from $\mathbb{Q}^+$ to $(0,1)$, allowing us to get $\omega^2+n$, $\omega^2*n$ etc. And by iterating that process, we can get any ordinal below $\omega^\omega$.

But this sort of embedding fails at $\omega^\omega$ as the iteration of $f$ doesn't seem compatible with taking the infinite union - figuratively speaking, we'd squish things to $0$. So what would an explicit embedding of $\omega^\omega$ look like? And the question, then, is if it is possible to give an explicit embedding of $\epsilon_0$? Is the fact that Peano arithmetic cannot prove well-foundedness of $\epsilon_0$ an indication that it cannot be embedded by such elementary functions and their iterations?

And what about even bigger countable ordinals such as the Veblen ordinals, Feferman-Schütte, Bachmann-Howard? From its definition, even if the above all are possible, I assume that the definitive bound of where one can define an effective procedure for the embedding must be Church–Kleene - is that a correct conclusion?

Lastly, does the situation change when we use $\mathbb{R}$ instead of $\mathbb{Q}$, which would allow us to use, perhaps, more easily understood yet inherently complex functions?

Edited because $\omega^2 \neq \omega^\omega$

-
I cannot answer about $\epsilon_0$ and larger "large countable ordinals", but I can remark that using $\mathbb R$ instead of $\mathbb Q$ would change nothing because $\mathbb Q$ is dense in $\mathbb R$ and we can transfer every countable set into $\mathbb Q$, or perhaps you meant that by moving to $\mathbb R$ we can use other elementary functions which do not preserve rationality? – Asaf Karagila Mar 24 '12 at 16:08
Yes, the thought was using functions that don't preserve rationality. For instance, it is at least not immediately clear to me that using exp or related functions couldn't give us more "power" to squish previous constructions. That's not to say I'm convinced that gains anything, but it seemed worth asking if there was a decent argument either way. – Desiato Mar 24 '12 at 16:31
It seems to me that between any two 'effectively specified' real numbers $r_0$ and $r_1$ (for any reasonable definition of 'effectively specified') one can find an 'effectively specified' rational - either via binary search on the interval $(\lfloor r_0\rfloor, \lceil r_1\rceil)$ or via an online means of computing their continued fractions. – Steven Stadnicki Mar 24 '12 at 16:47
@StevenStadnicki: That is a good argument why it won't give new things beyond $\omega_1^CK$, but it may possibly be easier to explicitly construct the embedding for lower ordinals. – Desiato Mar 24 '12 at 17:14
Too late to the party, but I think I have one for $\omega^\omega$. $a_n\omega^n+a_{n-1}\omega^{n-1}+\dotsb+a_0$ gets mapped to $0.\underbrace{1\dots1}_n0\underbrace{1\dots1}_{a_n}0\underbrace{1\dots1}_{a_{n-‌​1}}0\dots0\underbrace{1\dots1}_{a_0}$. I'm fairly sure this is order preserving. (That number may or may not be in binary, it really doesn't matter.) – Akiva Weinberger Jan 13 at 20:59

Since $\epsilon_0$ is still an $\omega$-sequence, it seems to me that an embedding is relatively straightforward; take it as the sequence $\left\{\omega, \omega^\omega, \omega^{\omega^\omega}, \ldots\right\}$ and embed each of those in a unit interval. Each has an easy explicit embedding, and for any '$\omega$-polynomial' that you give me I can give you the rational in my embedding that corresponds to it. I suspect that things break down, as you say, not too many steps up in the hierarchy - but that starts to get to questions of what an 'explicit specification' is.

EDIT: And to answer the question about embedding $\omega^\omega$, the same can easily be done; to make it more straightforward and highlight my mapping above, I'll pack it into the unit interval $\left[1,2\right)$. Map $\omega$ onto $\left[1,1+\frac{1}{2}\right)$, $\omega^2$ onto $\left[1+\frac{1}{2}, 1+\frac{3}{4}\right)$, etc; then our effective procedure for 'decoding' a polynomial $\sum_{i=0}^na_i\omega^i$ to a rational produces the rational $1+(1-2^{-n})+2^{-(n+1)}\left(1-2^{-(a_n-1)}\right)+2^{-(n+1)}2^{-a_n}\left(1-2^{-(a_{n-1}-1)}\right)+\cdots$ — we 'chop off' the largest term so that we're working in the interval $\left[1+(1-2^{-n}), 1+(1-2^{-(n+1)})\right)$ of length $2^{-(n+1)}$, use $a_n$ to find the point in that interval representing $a_n\omega^n$ (and implicitly, the next 'mapped-down' interval), and repeat the procedure. As long as there's an explicit means of specifying an $\omega$-sequence for the ordinal, this general mechanism will work.

-
That makes a lot of sense. It at very least allows the above construction to get to $\epsilon_0$ (it did not in the original version, which is now corrected). I'll need to think on what happens beyond that and will edit the question appropriately. – Desiato Mar 24 '12 at 17:10
Actually, a (hopefully easily fixed) detail niggle: When talking about a "union of ordinals" in set theory, this is typically explicitly not a disjoint union - in fact, all ordinals are initial segments of bigger ordinals there. While I think this will fix itself because the initial segments in this type of definition will get absorbed upwards, anyway. Alternatively, I could also imagine a somewhat more technical notion that does things the "set theoretic" way by having the initial segments of later ordinals identical with their representation. – Desiato Mar 25 '12 at 0:17

Church-Kleene is clearly the limit of the order types of well-ordered recursively decidable suborders of $(\mathbb Q,{<})$:

If you have a recursive (and infinite) $A\subseteq \mathbb Q$, then it's easy to compute an explicit bijection between $A$ and $\mathbb N$; so $(A,{<})$ is order isomorphic to some recursive ordering of $\mathbb N$. Conversely, every decidable total order on $\mathbb N$ is order isomorphic to some recursive subset of $((0,1)\cap \mathbb Q,{<})$ -- you can choose to map each $i$ to $\frac{2a_i+1}{2^i}$ where $a_i$ is selected purely on the basis on the ordering between $i$ and the earlier numbers.

(Incidentally, the "conversely" argument above also provides a non-constructive proof that every countable ordinal can be embedded into $\mathbb Q$ in at least one way).

Hovever "recursive" is arguably a stronger requirement than "explicit". For example, we can define an "explicit" embedding of $\omega_1^{CK}$ itself:

• Enumerate all recursive countably infinite ordinals as $(\alpha_i)_i$ in some canonical way, such as by the size of the smallest WHILE program that decides an ordering of $\mathbb N$ of each order type, and lexicographically in case of a tie.
• Embed $\alpha_i$ in $(i,i+1)\cap \mathbb Q$ using the above procedure.
• Remove from the resulting subset of $(i,i+1)$ every point that corresponds to a member of $\bigcup_{j<i}\alpha_j$.
• Take the union of the resulting partial embeddings.

This is "explicit", in the sense that there is provably one and only one subset of $\mathbb Q$ that is the result of the construction. But it is not decidable because (among other things) it is not decidable whether any given WHILE program decides a well-ordering of $\mathbb N$.

-
The vagueness of "explicit" certainly makes this a bit tricksy. Originally, I had in mind for this to mean that the deciding algorithm can actually be stated (as is the case for my simple construction in the question, and further up to some other ordinal as per Steven's reply below) in the sense that given a rational, we're able to definitely say "that's this ordinal" and vice versa. That doesn't make this less interesting, though. – Desiato Mar 25 '12 at 0:10

No need to squish everything to 0.

Every countable limit ordinal $\alpha$ is the limit of a sequence of ordinals $\alpha_1, \alpha_2, \alpha_3, \cdots$. For $i \in \mathbb{N}$, embed $\alpha_i$ by induction into $(i, i+1)$. The union of all these embeddings gives an embedding of an ordinal at least as large as $\alpha$, since it is larger than every $\alpha_i$. I believe we can actually assert that it is exactly $\alpha$, but that would take a bit more work.

-
That looks like it simply a version of the proof that such embeddings exist, but it does not allow for an explicit construction that I can see. An explicit construction in the sense of the question would need you to be able to say, for instance $\omega ^{\omega^2}+\omega+25$ is mapped to $54/88$ or, worse, $\epsilon_23+2$ is mapped to $14$. – Desiato Mar 24 '12 at 17:03
Why can't you just use a sequence leading up to $\epsilon_0$, like Steven says? – Dustan Levenstein Mar 24 '12 at 17:04

Here's a proof using continuum theory: Let $\alpha>0$ be a countable ordinal, and consider the initial interval $[0,\alpha]$ of the closed long ray. Since $[0,\alpha]$ is a closed subset of a compact Hausdorff space, it is compact Hausdorff, hence normal and regular. It is second-countable: a basis is formed by the intervals of the form $[0,q), (q,r)$ or $(r,\alpha]$ where $q$ and $r$ are rationals within each interval strictly between successive ordinals in $[0,\alpha]$. By Urysohn's metrization theorm, $[0,\alpha]$ is metrizable.

$[0,\alpha]$ is also connected because it is an initial interval or the long ray. But this means $[0,\alpha]$ is a metric continuum containing exactly two non-cut points, hence is homeomorphic to the unit interval. Let $h:[0,\alpha]\to [0,1]$ be such a homeomorphism. The ordinals within $[0,\alpha]$ are mapped into the unit interval by $h$.

-
(+1) Nice proof! – Asaf Karagila Nov 28 '12 at 8:20
Not quite. I've embedded the countable ordinal into the unit interval, but I still have to map it to the rationals. You probably need an induction argument for that. – Syd Henderson Nov 28 '12 at 8:23
Syd, two main points: (1) You are probably right, and it is probably impossible to escape an induction. I'm just not used to seeing such arguments given. (2) If you register your account you can delete the answer, then [if you want to] edit it and undelete again. If you don't register your account you could still edit it and add an induction argument to complete the proof. – Asaf Karagila Nov 28 '12 at 8:26
Also, no need for induction. For $\beta<\alpha$ send $\beta$ to a rational which lies in $h([\beta,\beta+1))$. Now I invalidated the need for induction and my first point in the previous comment. :-) – Asaf Karagila Nov 28 '12 at 8:27

It is easy to prove that every countable dense linear order embeds into $\mathbb{Q}$. [Proof here.]

Let $\alpha$ be a countable ordinal, or indeed any countable linear order.

Order $\alpha \times \mathbb{Q}$ lexicographically. This is a countable dense linear order, so it embeds into $\mathbb{Q}$ via a map $i : \alpha \to \mathbb{Q}$ say. Then $$\{ i(x, 0)\, :\, x \in \alpha \}$$ is an embedding of $\alpha$ into $\mathbb{Q}$.

That is, we line up $\alpha$ copies of $\mathbb{Q}$, embed them into $\mathbb{Q}$ and then pick the zeros from each.

-
The usual back-and-forth argument for DLOs doesn't give a very 'friendly' explicit mapping, though, which is what the original poster seems to be after... – Steven Stadnicki Nov 28 '12 at 18:37
@StevenStadnicki: The lack of explicitness is fair enough, but if you step back then it's not far from our intuition to see why it should be true. It then proves a more general result and avoids nasty inductive proofs [which, of course, isn't to say it's a better way of proving the result]. – Clive Newstead Nov 29 '12 at 1:12

What I was thinking of: You can map [0 ω] to [0, 1] by mapping 0 to 0, r to r/(r+1) and ω to 1.

Suppose you can map [0,β] onto [0,1] for all infinite ordinals β < α such that the ordinals map to the rationals. If α is a successor ordinal. map [0,α-1] to [0,1/2] and α to 1.

If α is a countable limit ordinal, let d be a metric on [0,α]. Define α1 to be the smallest ordinal larger than 0 such that d(α,α1)<1, α2 to be the smallest ordinal larger than α1 such that d(α,α2)<1/2, etc. Thus α1<α2<α3... converges to α. You now map [0,α] to [0,1] piecewise as you did, mapping [0,α1] onto [0,1/2], [α1,α2] onto [1/2,2/3] etc, (making sure you map ordinals to rationals at each step) and α itself to 1.

Of course, now I don't need continuum theory anymore.

[The reason this doesn't work when α is an uncountable ordinal is [0,α] isn't metrizable.]

-
You should have edited the previous answer. Also see the last comment I left for how to avoid the induction process. – Asaf Karagila Nov 28 '12 at 18:06