Dense Linear Orders: Completeness and Aleph0-Categoricity

Setup

Work in first-order logic with a countable language $L$. Two structures are isomorphic ($\cong$) if there is a bijection of their domains preserving all relations and functions. A theory $T$ is:

• $\kappa$-categorical if all its models of cardinality $\kappa$ are isomorphic (for the countable case $\kappa = \aleph_0$, also written $\aleph_0$-categorical or $\omega$-categorical);
• complete if for every sentence $\sigma$ exactly one of $T \vdash \sigma$ or $T \vdash \neg\sigma$ holds.

The Los-Vaught test (categoricity gives completeness)

Theorem (Los-Vaught). If $T$ is consistent, has no finite models, and is $\kappa$-categorical for some infinite $\kappa \ge |L|$, then $T$ is complete.

Idea of the proof: if $T$ were incomplete, some sentence $\sigma$ would be true in one model and false in another, giving two models that are not elementarily equivalent. Take models of $T + \sigma$ and of $T + \neg\sigma$; by Lowenheim-Skolem pull both down to size $\kappa$. Categoricity makes them isomorphic, hence elementarily equivalent -- contradiction. (No finite models rules out the degenerate case where the only models are finite of differing sizes.)

So for a theory of this shape, completeness comes for free once you prove categoricity.

Proving categoricity: the back-and-forth method

To show two countable structures $\mathcal{A}, \mathcal{B}$ are isomorphic, enumerate both domains $a_0, a_1, \dots$ and $b_0, b_1, \dots$ and build a chain of finite partial isomorphisms $f_0 \subseteq f_1 \subseteq \cdots$. At even steps (forth) ensure $a_n \in \operatorname{dom}(f)$; at odd steps (back) ensure $b_n \in \operatorname{ran}(f)$, each time extending $f$ by one matched pair. The structure's axioms guarantee a valid match always exists. The union $\bigcup_n f_n$ is a bijection preserving structure, i.e. an isomorphism.

Two canonical examples

1. Dense linear orders without endpoints (DLO). In $L = \{\le\}$, the theory $\Sigma_{DLO}$ axiomatizes a total order that is dense, $\forall x\,\forall y\,(x < y \to \exists z\,(x < z < y))$, with no least and no greatest element. The model is $(\mathbb{Q}, \le)$. Cantor's back-and-forth shows any two countable DLOs without endpoints are isomorphic (density supplies an interior match; no-endpoints supplies matches beyond the current extremes). So $\Sigma_{DLO}$ is $\aleph_0$-categorical; density forces every model to be infinite; therefore by Los-Vaught it is complete.

2. The Rado / random graph. In the language of graphs, the extension axioms $\varphi_n$ say: for any disjoint vertex sets $A, B$ with $|A| = |B| = n$ there is a vertex joined to every vertex of $A$ and to none of $B$. The family $\{\varphi_n : n > 0\}$ axiomatizes the countable Rado graph $R$. The same back-and-forth (now using an extension axiom at each step to find a vertex with the exact required adjacencies) proves $\omega$-categoricity, so its theory is complete too. Consequence: $T^*$ has a countable model and that model is unique up to isomorphism -- there are no two non-isomorphic countable models.

Mini-example

Is $(\mathbb{Q}, \le)$ elementarily equivalent to $(\mathbb{R}, \le)$? Both are DLOs without endpoints, so both model the complete theory $\Sigma_{DLO}$; a complete theory has all its models elementarily equivalent. Hence yes, they satisfy exactly the same first-order sentences -- even though $\mathbb{R}$ is uncountable and not isomorphic to $\mathbb{Q}$ (categoricity is only at $\aleph_0$ here).

Exam trick: Reduce these problems to a two-line checklist: (1) $\aleph_0$-categorical? -- yes, by back-and-forth (Cantor for DLO, extension axioms for the Rado graph), so "any two countable models are isomorphic" is TRUE and "two non-isomorphic countable models exist" is FALSE. (2) Complete? -- consistent + no finite models + categorical $\Rightarrow$ complete by Los-Vaught, so that statement is TRUE. Pitfall: $\aleph_0$-categoricity does not imply categoricity at larger cardinals -- distinct uncountable models can exist; categoricity still buys completeness, but not a single model overall.