Embedding ordinals in $\mathbb{Q}$

Question

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$

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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

Answer 5

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

Answer 6

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.