# Back-n-Forth or a Direct Isomorphism Between A Countable DLO Without Endpoints and $U = \{ \frac{m}{2^n} \}$

Note: I changed this question and deleted my answer, bringing it into the question for quick review. The proof now has the same brevity as the back-and-forth method found in wikipedia.

Let $$P$$ be a Countable DLO Without Endpoints.

Let $$U = \{m2^{-n} \; | \; \text{ with } m \in \mathbb Z \text{ and } n \in \mathbb N\}$$

Here is proof showing that there is a order-preserving bijection $$\tau$$ of $$P$$ onto $$U$$.

Let $$P$$ be bijectively enumerated by $$(p_n)_{n \ge 0}$$. We will define the mapping $$\tau$$ by 'running' through this sequence one term at a time.

We map $$p_0 \mapsto 0$$. Suppose we've injectively mapped (order preserving) the terms $$(p_j)_{j \lt k}$$ into $$U$$. If $$p_k$$ is 'outside' the interval range of $$(p_j)_{j \lt k}$$ in $$P$$, then we select the extreme $$p_{j_0}$$ and map $$p_k$$ to either $$\tau(p_{j_0}) + 1$$ or $$\tau(p_{j_0}) - 1$$ thereby keeping $$\tau$$ order-preserving. If $$p_k$$ is 'inside' the current $$\tau$$ range, it has a predecessor $$p_{j_0}$$ and a successor $$p_{j_1}$$, so that we can satisfactorily map $$p_k$$ to

$$\quad \frac{\tau(p_{j_0}) + \tau(p_{j_1})}{2}$$

Using the hypotheses on $$P$$ and properties of $$U$$, we can easily see that the mapping $$\tau$$ extends to a surjection making $$\tau$$ an isomorphism.

As a disclaimer I know nothing about model theory (see first comment below this question), but

Can a different proof than the back-and-forth method be of use in the field of model theory?

Is their a simple/universal/canonical example that one learns about in model theory?

Note: The proof technique gives corresponding constructs when $$P$$ has a maximum or minimum - all the stuff in $$U$$ bounded by any maximum or minimum still gets filled in.

• In my opinion, the clearest way to prove this is to first prove that any two countable DLOs without endpoints are isomorphic by the back-and-forth method, and then note that $U$ is a countable DLO without endpoints... – Alex Kruckman Oct 13 '18 at 14:51
• @AlexKruckman Deleted answer and moved argument into question asking something different. – CopyPasteIt Oct 14 '18 at 23:47
• I'd say that the $\aleph_0$-categoricity of DLOWE (that is: the proof that any two countable dense linear orders without endpoints are isomorphic) is the canonical example of a back-and-forth argument. As to "Can a different proof than the back-and-forth method be of use in the field of model theory?," I do not know of any non-back-and-forth way to prove this specific fact (although I have to point out that the way this question is phrased makes it sound more general: there are of course techniques in model theory other than the back-and-forth method). – Noah Schweber Oct 15 '18 at 16:31
• @NoahSchweber Sounds like you are saying that my proof is not direct - just another version of back-n-forth... – CopyPasteIt Oct 15 '18 at 17:03
• @CopyPasteIt Yes, you've just written a back-and-forth argument. But I wouldn't say that makes it not direct; rather, I'd say that back-and-forth arguments are direct. They're as computable and explicit as one could hope for. The map so produced may be ugly, but it's totally concrete. – Noah Schweber Oct 15 '18 at 17:07

Let $$(p_n\mid n\in\Bbb N)$$ be a enumeration of $$P$$.

Lemma: Let $$(P,<)$$ be countable, dense, and linearly ordered set without endpoints. Then there is a order embedding $$f:\Bbb Z \to P$$ such that $$f[\Bbb Z]$$ is unbounded from above and from below in $$P$$.

Proof:

We define a mapping $$g:\Bbb N \to \Bbb N$$ recursively by $$g(0)=0 \text{ and }g(n+1)=\min \{i\in\Bbb N\mid p_{g(n)}

We define a mapping $$f_1:\Bbb N \to P$$ by $$f_1(n)=p_{g(n)}$$

It follows from the definition of $$f_1$$ that $$\forall n\in\Bbb N:p_{g(n)} and thus $$f_1$$ is injective. Let $$A:=f_1[\Bbb N]$$.

$$p_0=f_1(0) is unbounded above by $$p_0$$. Assume that $$A$$ is unbounded above by $$p_i$$ for all $$i\le n$$. Then $$\exists n_0\in \Bbb N,\forall i\le n:p_i \le f_1(n_0)= p_{g(n_0)}$$.

• If $$p_{n+1}\le p_{g(n_0)}=f_1(n_0)$$: $$A$$ is unbounded above by $$p_{n+1}$$.

• If $$p_{n+1} > p_{g(n_0)}$$: We have $$\forall i\le n:p_i\le p_{g(n_0)}$$ and $$p_{g(n_0)} $$\min \{i\in\Bbb N\mid p_{g(n_0)} $$p_{g(n_0+1)} = p_{n+1} \implies f_1(n_0+1)=p_{n+1}$$. Thus $$A$$ is unbounded above by $$p_{n+1}$$.

Hence $$f_1[\Bbb N]$$ is unbounded from above in $$P$$.

We define a reverse-order $$<^*$$ on $$P$$ by $$\forall x,y\in P:x <^* y \iff y. Then $$(P,<^*)$$ is a countable, dense, and linearly ordered set without endpoints.

In a similar manner, we obtain $$f_2:\Bbb N \to P$$ which is an order embedding from $$\Bbb N$$ to $$P$$ such that $$f_2(0)=p_0$$ and that $$f_2[\Bbb N]$$ is unbounded from above in $$P$$ with respect to $$<^*$$. Thus $$f_2[\Bbb N]$$ is unbounded from below in $$P$$ with respect to $$<$$.

Let $$f=f_1\cup f_2$$. It is easy to verify that $$f:\Bbb Z \to P$$ is order embedding from $$\Bbb Z$$ to $$P$$ such that $$f[\Bbb Z]$$ is unbounded from above and from below in $$P$$.$$\quad \blacksquare$$

Theorem: There exists an order isomorphism between $$U = \left\{\dfrac{m}{2^n} \mid m \in \mathbb Z \text{ and } n \in \mathbb N\right\}$$ and $$P$$.

Proof:

Let $$U_k = \left\{\dfrac{m}{2^k} \mid m \in \mathbb Z\right\}$$ for all $$k\in\Bbb N$$. It's clear that $$U_0=\Bbb Z$$, that $$U_k\subsetneq U_{k+1}$$ for all $$k\in\Bbb N$$, and that $$U_k$$ is unbounded from above and from below in $$\Bbb Q$$.

We define recursively a family of mappings $$(F_k\mid k\in\Bbb N)$$ such that $$F_k$$ is an order embedding from $$U_k$$ to $$P$$, and that $$F_k\subsetneq F_{k+1}$$ for all $$k\in\Bbb N$$.

Let $$F_0=f$$ where $$f$$ is generated by Lemma.

Assume that we have defined $$F_k$$, we define $$F_{k+1}$$ as follows:

• $$F_{k+1}\restriction U_k:=F_k$$.

• For each $$z\in U_{k+1}\setminus U_k$$, there is a unique $$m\in\Bbb Z$$ such that $$\dfrac{m}{2^k} since $$U_k$$ is unbounded from above and from below in $$\Bbb Q$$. Let $$F_{k+1}(z):=p_{i_0}$$ where $$i_0=\min \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}}). Since $$P$$ is dense, such $$i_0$$ does exists. Thus $$F_{k+1}(z)$$ is well-defined for all $$z\in U_{k+1}\setminus U_k$$.

Let $$F=\bigcup_{k\in\Bbb N}F_k$$. It is easy to verify that $$F$$ is an order embedding from $$\bigcup_{k\in\Bbb N}U_k=U$$ to $$P$$.

Let $$\bigcup_{k\in\Bbb N}F_k[U_k]=P'$$. We next prove that $$\forall n\in\Bbb N:p_n\in P'$$ by strong induction on $$n$$.

It's clear that $$p_0\in f[\Bbb Z]=F_0[U_0]$$. Thus $$p_0\in P'$$. Assume that $$p_i\in P'$$ for all $$i\le n$$. Then there exists $$k\in\Bbb N$$ such that $$p_i\in F_k[U_k]$$ for all $$i\le n$$.

1. $$p_{n+1} \in F_k[U_k]$$

Then $$p_{n+1}\in P'$$.

1. $$p_{n+1} \notin F_k[U_k]$$

Then there is a unique $$m\in\Bbb Z$$ such that $$F_k(\frac{m}{2^k}) where$$\frac{m}{2^k}\in U_k$$ by the fact that $$F_k[U_k]$$ is unbounded from above and from below in $$P$$.

We have $$\forall i\le n:p_i\in F_k[U_k] \implies \forall i\le n:i\notin \{i\in\Bbb N \mid F_k(\frac{m}{2^{k}}) by the fact that $$F_k$$ is an order isomorphism between $$U_k$$ and $$F_k[U_k]$$, and that $$\frac{m}{2^{k}}$$ and $$\frac{m+1}{2^{k}}$$ are two consecutive members of $$U_k$$.

Moreover, $$F_k(\frac{m}{2^k}) $$\implies n+1=\min \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}}) where $$z\in U_{k+1}\setminus U_k$$ such that $$\dfrac{m}{2^k}.

By principle of strong induction, $$P\subseteq P'$$. Furthermore, $$P'\subseteq P$$. Thus $$P=P'$$. Hence $$F$$ is an order isomorphism between $$U$$ and $$P$$.$$\quad \blacksquare$$

• We want the $U_k$ to be finite here - a 'one-pass' recursive solution. – CopyPasteIt Oct 13 '18 at 8:20
• @CopyPasteIt I got it. – Akira Oct 13 '18 at 8:27