Showing any countable, dense, linear ordering is isomorphic to a subset of $\mathbb{Q}$

Question

I'm trying to knock out a few of the later exercises from Enderton's Elements of Set Theory. This problem is #17, found on page 227.

A partial ordering $R$ is said to be dense iff whenever $xRz$, then $xRy$ and $yRz$ for some $y$. Assume $(A,R)$ is a linearly ordered structure with $A$ countable and $R$ dense. Show that $(A,R)$ is isomorphic to $(B,<_Q)$ for some subset $B$ of $\mathbb{Q}$.

I had an idea, but I'm not sure how to communicate it formally, so I'm hoping to get some help on this. First, since $A$ is countable, I can list it as a sequence, $A=\{a_0,a_1,a_2,\ldots\}$, even if this isn't the actual linear ordering dictated by $R$. The text suggests that I define some order isomorphism $f$ by defining $f(a_i)$ by recursion on $i$.

I began by letting $f(a_0)=q_0$ for some arbitrary rational. I then look at $a_1$, if $a_0Ra_1$, I would then let $q_0<f(a_1)$, and if $a_1Ra_0$, I instead choose $f(a_1)<q_0$. This continues, so for example, if $a_2Ra_1\land a_0Ra_2$, I would then want to choose $f(a_2)$ such that $q_0<f(a_2)<q_1$ and so on.

Since $\mathbb{Q}$ is dense, I just want to choose some rational to preserve the order as I go along sequentially in $A$, and figure out the order as I go. Is this right? If so, what's the rigorous way to state this idea? I'm particularly concerned about how $f$ can respond to where the next element $a_{i+1}$ might be in relation to the previous $a_0,\ldots, a_i$, and how to decide which element to pick out. Thank you.

Answer 1

what you are doing by building $f$ step-by-step is called building a partial map. Having already picked $b_{i}$ ($=f(a_{i})$) for $i<m$, you pick $b_{m}$ so that it preserves the relations that $a_{m}$ has with the $a_{i}$ for $i<m$. This is possible because $\mathbb{Q}$ is dense and has no endpoints. So, at every state you can enlarge the partial isomorphism. After $\omega$-many steps, the domain of the map will be all of $A$, and the $f$ you will have built will be an order preserving injection of $(A,R)$ into $\mathbb{Q}$.

To see that you can always extend the partial map, note that you only have to meet finitely many conditions each time. So your $a_{i}$ will atmost be between some two previous elements, or larger than all of them or greater than all of them. But since $\mathbb{Q}$ is dense and has no endpoints, in each case we can pick a corresponding $b_{i}$.

Also, notice that I made no assumptions here about $(A,R)$ here, except that it is a countable linear order. In case $(A,R)$ is countable, dense and has no endpoints, you can do even better, ie you can in a similar way build an isomorphism between $(A,R)$ and $(\mathbb{Q},<)$. The way to do this is similar to the above one, except you enumerate $A$ and $\mathbb{Q}$ and then build a isomorphism element by element such that it respects the orderings and has range $\mathbb{Q}$ and domain $A$. One way to do this is to first map an element of $A$ to an element of $\mathbb{Q}$ and then map the least unmapped element of $\mathbb{Q}$ in the enumeration to an element of $A$.

Keywords for what you are looking for are: Back-and-forth method, Ehrenfeucht-Fraïssé game. Any model theory text book (Hodges, Marker, Poizat etc) should have a detailed account of this method.

Answer 2

In fact, there is no need to assume that $R$ is dense. The fact is that every countable linear order embeds into the rational line. Another way to say this is that the rational line (or any countable dense linear order) is universal for countable linear orders.

The proof is just as you describe. Given a countable order $\langle A,R\rangle$, enumerate $A=\{a_0,a_1,\ldots\}$ and build the full isomorphism of $A$ into $\mathbb{Q}$ by successively defining $f(a_n)$. At any stage of the construction, we have a partial isomorphism defining the images of $a_i$ for $i\lt n$, and we want to define $f(a_n)$. The images $f(a_i)$ form a finite subset of $\mathbb{Q}$, which divides $\mathbb{Q}$ into finitely many intervals. So we look at how $a_n$ sits with respect to the $a_i$ for $i\lt n$, that is, at which interval in $A$ it sits in among those finitely many endpoints, and then choose any point in $\mathbb{Q}$ that fits in the corresponding interval in the image, and let that point be $f(a_n)$. Thus, we have made an order-preserving map at each stage, and so the full map is an order-isomorphism of $A$ with a subset of $\mathbb{Q}$ as desired.

Cantor proved also that in the case $R$ is dense and the order $\langle A,R\rangle$ has no endpoints, then in fact $\langle A,R\rangle$ is isomorphic to $\mathbb{Q}$, and one can prove this by using the back-and-forth technique, using the same idea, but now one must also ensure not only that the $n$-th point of the domain gets added to the isomorphism, but also that the $n$-th point of the range is added. To prove the property you requested, however, you only need the "forth" part of the back-and-forth construction.