Embedding ordinals in $\mathbb{Q}$

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.

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

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

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.

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.