Notes - Logic MT24, Unbounded dense linear orders
The key result is “Cantor’s isomorphism theorem”, namely that any two countable unbounded dense linear orderings are isomorphic, so e.g. $(\mathbb Q, <)$ is isomorphic to $(\mathbb Z[1/2], <)$ where $\mathbb Z[1/2]$ denotes the set of dyadic rationals.
This is also covered in [[Notes - Logic and Proof MT24, Unbounded dense linear orders]]U but the proof here is a lot more rigourous.
Flashcards
@Define $\sigma _ \text{DLO}$ over the language $\mathcal L _ < := \{<\}$, the sentence whose models are dense linear orderings without endpoints.
- 1, 2, 3 imply the models are linear (i.e. total) orderings
- 4 implies density
- 5, 6 imply the models are without endpoints
Suppose:
\[\begin{aligned}
\sigma_\text{DLO} := \forall x \forall y \forall z (&\lnot x < x \\\\
&\land (x < y \lor x = y \lor y < x) \\\\
&\land ((x < y \land y < z) \to x < z) \\\\
&\land (x < y \to \exists w (x < w \land w < y)) \\\\
&\land \exists w ( w < x ) \\\\
&\land \exists w (x < w ))
\end{aligned}\]
@Prove that $\sigma _ \text{DLO}$ has a unique countable model up to isomorphism (so that in particular, any countable model is isomorphic to $\langle \mathbb Q; < \rangle$), and that as a consequence $\sigma _ \text{DLO}$ is complete.
Suppose $\mathcal M$ and $\mathcal N$ be two countable models.
Let a partial isomorphism $\theta : \mathcal M \dashrightarrow \mathcal N$ be a partially defined injective map such that for all $a, b \in \text{dom}(\theta)$,
\[\mathcal M \models a < b \iff \mathcal N \models \theta(a) < \theta(b)\]Since the domains of $\mathcal M$ and $\mathcal N$ are countable, we can enumerate them as $(m _ i) _ {i \in \mathbb N}$ and $(n _ i) _ {i \in \mathbb N}$.
We recursively construct a chain of partial isomorphisms
\[\theta_i : \mathcal M \dashrightarrow \mathcal N\]such that we meet the conditions:
- $\text{dom}(\theta _ i)$ is finite, and
- for all $j < i$, we have $m _ j \in \text{dom}(\theta _ i)$ and $n _ j \in \text{im}(\theta _ i)$
Let $\theta _ 0 := \emptyset$. Inductively assume that we have $\theta _ i$ satisfying the above conditions. Extend $\theta _ i$ by finding $n \in \mathcal N$ such that setting
\[\theta_i'(m_i) := n\]yields a partial isomorphism
\[\theta_i' : \mathcal M \dashrightarrow \mathcal N\]with $\text{dom}(\theta _ i’) = \text{dom}(\theta) \cup \{m _ i\}$.
Suppose
- $\text{dom}(\theta _ i) = \{a _ 1, \ldots, a _ s\}$ with $\mathcal M \models a _ k < a _ l$ for $1 \le k < l \le s$, and similarly
- $\text{im}(\theta _ i) = \{b _ 1, \ldots, b _ s\}$ with $\mathcal N \models b _ k < b _ l$ for $1 \le k < l \le s$
There are four cases to consider:
Case 1: $m _ i = a _ k$ for some $k \in [1, s]$: Set $n := b _ k$.
Case 2: $m _ i < a _ 1$: Let $n \in \mathcal N$ be such that $n < b _ 1$ ($n$ exists since $\mathcal N$ has no endpoint).
Case 3: $m _ i > a _ s$: Let $n \in \mathcal N$ be such that $n > b _ s$ ($n$ exists since $\mathcal N$ has no endpoint).
Case 4: $a _ j < m _ i < a _ {j+1}$ for some $j \in [1, s-1]$: Let $n \in \mathcal N$ be such that $a _ i < n < a _ {i+1}$ ($n$ exists since $\mathcal N$ is dense).
In all cases, $\theta _ i’$ is a partial isomorphism.
Symmetrically, $(\theta’ _ i)^{-1}: \mathcal M \dashrightarrow \mathcal N$ is a partial isomorphism satisfying the conditions.
Then
\[\theta := \bigcup_{i} \theta_i : \mathcal M \to \mathcal N\]is an isomorphism, so $\sigma _ \text{DLO}$ has a unique countable model up to isomorphism.
But then by the result that if a theory has a unique countable model up to isomorphism, then it is complete, it follows that $\sigma _ \text{DLO}$ is complete and hence axiomatises $\langle \mathbb Q; <\rangle$.