Universality of $(\mathbb Q,<)$

Question

I have few questions to the proof on Universality of linearly ordered sets. Could anyone advise please? Thank you.

Lemma: Suppose $(A,<_{1})$ is a linearly ordered set and $(B,<_{2})$ is a dense linearly ordered set without end points. Assume $F\subseteq A$ and $E\subseteq B$ are finite and $h:F \to E$ is an isomorphism from $(F,<_{1})$ to $(E,<_{2})$. If $a\in A-F$, then $\exists b\in B-E$ such that $h\cup \left\{(a,b)\right\}$ is an isomorphism from $F \cup \left\{a\right\}$ to $E \cup \left\{b\right\}$.

Theorem: Every countable linearly ordered set is embeddable into the linearly ordered set $(\mathbb{Q},<)$

Proof: Let $(A,<_{1})$ be countably linearly ordered set. Let $f:\mathbb{N}\to A$ be a bijection. Fix bijection $g:\mathbb{N} \to \mathbb{Q}$. Define an embedding $h:A\to \mathbb{Q}$. Let $h(f(0))=g(0).$

The Induction hypothesis:$h:\left\{f(i): i<n\right\} \to \left\{h(f(i)): i<n\right\}$ is an isomorphism. Let $a=f(n)$, $F=\left\{f(i): i<n\right\},$ $E= \left\{h(f(i)): i<n\right\} ,D=h:\left\{m\in \mathbb{N}: g(m) \not\in E \wedge h\cup\left\{(a,g(m)) \right\}\right\}$, where $ h\cup\left\{(a,g(m)) \right\}$ is an isomorphism. By Lemma, $D\neq\varnothing$. Let $m*=min(D)$ and define $h(f(n))=g(m*)$. done

My questions: What is the role of $h(f(0))=g(0) ?$ How does it follow that $h: A =F \cup \left\{f(n)\right\} \cup (A-F \cup \left\{f(n)\right\}) \to \mathbb{Q}=E\cup\left\{g(m*)\right\} \cup (\mathbb{Q}-(E \cup \left\{g(m*)\right\}))$ is an isomorphism?

Answer 1

There is no particular role of $h(f(0)) = g(0)$ except to start the inductive argument, which traditionally begins with a base case $n=1$. (Although one could start with the case $n=0$, where the base case starts with the function on the empty set. Possibly the author and/or instructor thought that starting off with a vacuous case would be distracting or confusing, and so opted to go with $n=1$.)

What this proof does is construct a injective function that preserves the order (a bijective function to the image $I$ that preserves the order); given that the domain and the image are totally ordered, it may be shown that the inverse function from image to domain must also be order-preserving. To show it is injective and order-preserving, take any two elements $a, b \in A$ with $a < b$ and verify that $f(a) < f(b)$. But since $a, b$ belong to some finite subset $\{f(i): i < n\}$ (by taking $n$ large enough), this should be clear from the inductive argument.

Answer 2

First I’ll explain the proof and some of the motivation for it in greater detail, and then I’ll answer your specific questions.

For greater readability let $a_k=f(k)$ and $q_k=g(k)$ for each $k\in\Bbb N$, so that $F=\{a_k:k<n\}$, the subset of $A$ on which $h$ has already been defined. $E=\{h(a_k):k<n\}=h[F]$, the copy of $F$ in $\Bbb Q$. Now we want to extend $h$ to $a_n$ (called $a$ in the proof) by defining $h(a_n)$ to be some rational number that occupies the same position relative to the members of $E$ as $a_n$ occupies relative to the members of $F$. In other words, if $k,\ell<n$, and $a_k<_1 a_n<_1 a_\ell$, we want $h(a_n)$ to satisfy $h(a_k)<h(a_n)<h(a_\ell)$ in $\Bbb Q$. The lemma says that this is always possible. Specifically, it says that there is a $q\in\Bbb Q\setminus E$ such that $h\cup\{\langle a_n,b\rangle\}$ is an isomorphism from $F\cup\{a_n\}$ to $E\cup\{q\}$. In other words, if $$B=\big\{q\in\Bbb Q:h\cup\{\langle a_n,q\rangle\}\text{ is an isomorphism from }F\cup\{a_n\}\text{ to }E\cup\{q\}\big\}$$ is the set of possible choices for this $q$, the lemma says that $B\ne\varnothing$. For technical reasons the proof that you have says this a little indirectly: instead of using $B$, the actual set of candidates for $h(a_n)$, it uses the of indices of those candidates in the enumeration of $\Bbb Q$ by $g$. That set is

$$D=\big\{m\in\Bbb N:h\cup\{\langle a_n,q_m\rangle\}\text{ is an isomorphism from }F\cup\{a_n\}\text{ to }E\cup\{q\}\big\}\;.$$

The advantage to using $D$ instead of $B$ is that we can now make a non-arbitrary choice of an element of $B$: we let $m^*=\min D$, thereby choosing $q_{m^*}$ from $B$, instead of just picking any old element of $B$. From the definition of $D$ we know that $h\cup\{\langle a_n,q_{m^*}\rangle\}$ is an isomorphism from $F\cup\{a_n\}$ to $E\cup\{q_{m^*}\}$, so we extend $h$ to $h\cup\{\langle a_n,q_{m^*}\rangle\}$ by defining $h(a_n)=q_{m^*}$. We now have an isomorphism from $\{a_k:k\le n\}$ to $\{h(a_k):k\le n\}$, and we can continue the inductive construction of $h$.

In the end we have a function $h:A\to\Bbb Q$ defined on all of $A$. Suppose that $a,a'\in A$. There are $k,\ell\in\Bbb N$ such that $a=a_k$ and $a'=a_\ell$; let $n=\max\{k,\ell\}$. In the construction above we ensured that $h(a_n)$ was ‘in the right place’ relative to all $h(a_i)$ with $i<n$: if $a_i<_1 a_n$, then $h(a_i)<h(a_n)$, and if $a_n<_1 a_i$, then $h(a_n)<h(a_i)$. Thus, once $h(a_n)$ was chosen, we were assured that if $a<_1 a'$, then $h(a)=h(a_k)<h(a_\ell)=h(a')$, and similarly, if $a'<_1 a$, then $h(a')=h(a_\ell)<h(a_k)=h(a)$. Thus, $h$ is an isomorphism: it preserves the ordering. The key idea here is that $h$ is an isomorphism iff its restriction to every two-element subset of $A$ is an isomorphism: if $h$ preserves the order of each pair of elements of $A$, it preserves the entire order. This is why we can construct it one point at a time: if we correctly place the image of each new point with respect to all of the earlier points, then in the end we’ve preserved the order of every pair of points and therefore the entire ordering of $A$.

Now for your specific questions:

1. $\Bbb Q$ is homogeneous: it ‘looks the same’ at every point. More technically, if $q_0$ and $q_1$ are distinct points of $\Bbb Q$, there is an isomorphism of $\Bbb Q$ onto itself that sends $q_0$ to $q_1$; the map $q\mapsto q+(q_1-q_0)$ works, for instance. This means that it doesn’t matter where we start embedding $A$ into $\Bbb Q$: if we have one embedding $h:A\to\Bbb Q$, we can ‘slide’ the embedding within $\Bbb Q$ just by adding a rational constant to each image. That is, if $r\in\Bbb Q$, the map $h_r:A\to\Bbb Q:a\mapsto h(a)+r$ is also an isomorphism from $A$ into $\Bbb Q$, but instead of sending to $a_0$ to $q_0$, it sends it to $q_0+r$. In short, it really doesn’t matter where we send $a_0$, but we have to send it somewhere, and if we follow the rule used in the induction step of picking the first available rational in the enumeration of $\Bbb Q$ by $g$, we’ll send $a_0$ to $q_0$.

2. What you’ve written is not a correct description of $h$ after the induction step. At that point, as I said above, $h:F\cup\{a_n\}\to E\cup\{q_{m^*}\}$, and $H$ is an isomorphism between $F\cup\{a_n\}$ and $E\cup\{q_{m^*}\}$. In the notation of your proof those sets are $F\cup\{f(n)\}$ and $E\cup\{g(m^*)\}$.

Added: I forgot to mention another reason for using $D$ instead of $B$: if $\langle A,<_1\rangle$ is a dense order without endpoints, the construction will produce an isomorphism from $A$ onto $\Bbb Q$, thereby showing that up to isomorphism there is just one countable dense linear order without endpoints. If $\Bbb Q\setminus h[A]\ne\varnothing$, let $m\in\Bbb N$ be minimal such that $q_m\notin h[A]$. A bit of thought should convince you that there must have been some stage $n$ in the construction when $\{q_k:k<m\}\subseteq E$ (since all $q_k$ with $k<m$ are in the range of $h$) and $q_m$ was in the same place relative to the members of $E$ as $a_n$ was relative to the members of $F$. That means that $q_m\in B$ at stage $n$, and $m\in D$. And since at that point we’d already ‘used’ all $q_k$ with $k<m$, $m$ must have been the smallest member of $D$, and we’d have set $m^*=m$. But then we’d have set $h(a_n)=q_m$, putting $q_m\in h[A]$ after all. This contradiction shows that $h[A]$ must be all of $\Bbb Q$.