0
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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... $\endgroup$ – Alex Kruckman Oct 13 '18 at 14:51
  • $\begingroup$ @AlexKruckman Deleted answer and moved argument into question asking something different. $\endgroup$ – CopyPasteIt Oct 14 '18 at 23:47
  • $\begingroup$ 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). $\endgroup$ – Noah Schweber Oct 15 '18 at 16:31
  • $\begingroup$ @NoahSchweber Sounds like you are saying that my proof is not direct - just another version of back-n-forth... $\endgroup$ – CopyPasteIt Oct 15 '18 at 17:03
  • 1
    $\begingroup$ @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. $\endgroup$ – Noah Schweber Oct 15 '18 at 17:07
0
$\begingroup$

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)}<p_i\}$$

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)}<p_{g(n+1)}$ and thus $f_1$ is injective. Let $A:=f_1[\Bbb N]$.

$p_0=f_1(0)<f_1(1) \implies A$ 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)}<p_{n+1} \implies$ $\min \{i\in\Bbb N\mid p_{g(n_0)}<p_i\}=n+1 \implies g(n_0+1)=n+1 \implies$ $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<x$. 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}<z<\dfrac{m+1}{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}})<p_i<F_k(\frac{m+1}{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})<p_{n+1}<F_k(\frac{m+1}{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}})<p_i<F_k(\frac{m+1}{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})<p_{n+1}<F_k(\frac{m+1}{2^{k}}) \implies n+1\in \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}})<p_i<F_k(\frac{m+1}{2^{k}})\}$ $\implies n+1=\min \{i\in\Bbb N\mid F_k(\frac{m}{2^{k}})<p_i<F_k(\frac{m+1}{2^{k}})\} \implies F_{k+1}(z)=p_{n+1}$ where $z\in U_{k+1}\setminus U_k$ such that $\dfrac{m}{2^k}<z<\dfrac{m+1}{2^k} \implies p_{n+1}\in F_{k+1}[U_{k+1}] \implies p_{n+1}\in P'$.

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.