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

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.

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.