Countable ordinals are embeddable in the rationals $\Bbb Q$ -- proofs and their use of AC

Yesterday, Asaf Karagila's answer to my question sparked an extensive discussion on ways of proving that all countable ordinals are embeddable in $\Bbb Q$, and whether particular solutions to this use the Axiom of Choice.

Since the arguments used to prove this can be shady on their use of Choice when formulated tersely, fully fleshed out answers are appreciated.

To be concrete, this question asks for proofs of the following fact:

All countable ordinals $\alpha < \omega_1$ are order-embeddable in the rationals $\Bbb Q$.

Especially answers avoiding the Axiom of Choice are appreciated.

Of relevance and related interest is #123969 (but it's not a duplicate, since that question asks for explicit embeddings).

Solution 1:

Finite linear orders are no problem, so let $\langle X,\preceq\rangle$ be any countably infinite linear order, and fix an enumeration $X=\{x_k:k\in\omega\}$. Also fix an enumeration of the rationals, $\Bbb Q=\{p_k:k\in\omega\}$. Define $f:X\to\Bbb Q$ as follows.

Let $f(x_0)=p_0$. Suppose that $0<n\in\omega$, and $f(x_k)$ has been defined for each $k<n$. Let $L_n=\{k<n:x_k\prec x_n\}$ and $R_n=\{k<n:x_n\prec x_k\}$.

• If $L_n\ne\varnothing\ne R_n$, let $\ell(n)=\max\{x_k:k\in L_n\}$ and $r(n)=\min\{x_k:k\in R_n\}$. Then $x_{\ell(n)}\prec x_{r(n)}$, so $f(x_{\ell(n)})<f(x_{r(n)})$, and we can set $f(x_n)=p_m$, where $$m=\min\{k\in\omega:f(x_{\ell(n)})<p_k<f(x_{r(n)})\}\;.$$

• If $L_n=\varnothing\ne R_n$, let $r(n)=\min\{x_k:k\in R_n\}$, and set $f(x_n)=p_m$, where $$m=\min\{k\in\omega:p_k<f(x_{r(n)})\}\;.$$

• And if $L_n\ne\varnothing=R_n$, let $\ell(n)=\max\{x_k:k\in L_n\}$, and set $f(x_n)=p_m$, where $$m=\min\{k\in\omega:f(x_{\ell(n)})<p_k\}\;.$$

Given the enumerations, everything is explicitly defined.

Solution 2:

The trick, as the discussion in the comments to my answer, is to notice the order of the quantifiers.

Given $\alpha<\omega_1$ we construct an embedding by transfinite recursion, from $\alpha$ into $\omega_1$. Actually we construct a bit more, we construct a sequence of embeddings $\langle f_\beta\mid\beta\leq\alpha\rangle$, such that $f_\beta\colon\beta\to\Bbb Q$ is an order embedding, and its range is bounded.

• $f_0=\varnothing$.
• Suppose that $f_\beta$ were defined (we don't care about the entire sequence at this point), and $q\in\Bbb Q$ is some upper bound to $\operatorname{rng}f_\beta$. Then $f_{\beta+1}=f_\beta\cup\{\langle\beta,q\rangle\}$ is an order embedding, as wanted.

• Suppose that $\beta$ is limit, and $\langle f_\gamma\mid\gamma<\beta\rangle$ were defined. We write $\beta$ as the union of intervals $[\gamma_n,\gamma_{n+1})$, each of order type $\beta_n$. Trivially, $\beta_n<\beta$, so we can embed it into $\Bbb Q$ using $f_{\beta_n}$.

  Let $g_n$ be the composition of $f_{\beta_n}$ with an order isomorphism of $\Bbb Q$ with $(0,1)\cap\Bbb Q$. We define the follow $g\colon\beta\to\Bbb Q$: $$g(\delta)=n+g_n(\varepsilon),\qquad\delta\in[\gamma_n,\gamma_{n+1}),\ \varepsilon<\beta_n,\ \delta=\gamma_n+\varepsilon.$$

  This is well-defined because each $\delta$ appears in a unique interval, and can be written uniquely as such sum of two ordinals. It is not hard to see that $g_n$ is indeed injective, and order preserving, but it is unbounded. Let $f_\beta$ be the composition of $g$ with the order-isomorphism of $\Bbb Q$ with $(0,1)\cap\Bbb Q$, then $f_\beta$ is an embedding whose range is bounded.