Past exam of the model theory and Gödel's incompleteness theorems course of the University of Oxford / 2007 / B / 6

A first-order theory is a set of first-order sentences in a fixed first-order language, often identified with its deductive closure. It is $\kappa$-categorical if it has a first-order model of cardinality $\kappa$ and all first-order models of that cardinality are isomorphic as first-order structures in that same first-order language. In particular, an isomorphism must preserve the named constants as well as the order.

A first-order theory is complete if it is first-order consistent and decides every first-order sentence: for each $\sigma$ it entails either $\sigma$ or $\neg \sigma$. Equivalently all its first-order models satisfy exactly the same first-order sentences. First-order consistency is included to exclude the vacuous first-order theory with no first-order models. The distinctions matter here: naming infinitely many ordered points changes countable categoricity without destroying completeness.

Use two expansions of the rational order. In the first interpret $c_n=n$, so the named sequence is unbounded above. In the second interpret $c_n=-1/n$, so the named sequence is strictly increasing but has upper bounds in the rational order. Both expansions are countably infinite first-order models of the specified first-order theory.

An isomorphism preserving each $c_n$ would preserve the existence of an element greater than all the named constants, since any such element in one first-order structure would map to such an element in the other. The first first-order structure has none and the second has, for instance, $0$. They cannot be isomorphic. ThusThe property of lying above all $c_n$ is an infinite partial type rather than a single first-order sentence. This is why its realization can distinguish the two first-order models without contradicting the completeness established in (iv).

In a countable first-order model, the finitely many named constants split the order into the open intervalstogether with the $n$ named points. Each interval is a countable dense linear order without endpoints in its induced order. It is nonempty and infinite by density and the absence of endpoints.

Use Cantor's classification of countable dense linear orders without endpoints: each such interval is isomorphic to the rational order. It follows by a back-and-forth method extending finite increasing partial bijections alternately along enumerations of the two orders. Given two first-order models of ${\mathrm{DLO}}_n$, choose isomorphisms between their corresponding intervals and send each named point to its counterpart. Their union is an increasing bijection preserving all constants, hence an isomorphism in $L_n$.

There are countable first-order models, for example any finite increasing list in the rational order. ThereforeFor $n=0$, the same argument is just the classification theorem for the whole order.

Use the completeness of the first-order theory of dense linear orders without endpoints and its quantifier elimination. After naming finitely many increasing constants, quantifier elimination still holds in the expanded first-order language: treat these constants as fixed parameters when eliminating quantifiers. Every quantifier-free sentence is a Boolean combination of logical equalities and order comparisons of the named constants, all decided by their stated strict increasing order. Hence ${\mathrm{DLO}}_n$ is complete.

An alternative formal proof of this finite case uses the stated general theorem that a first-order theory in a countable first-order language with only infinite first-order models and a unique countable first-order model is complete: if first-order models disagreed on a first-order sentence, downward Löwenheim-Skolem would give disagreeing countable first-order models. Part (iii) supplies the uniqueness.

Every first-order sentence of $L_{\omega }$ mentions only finitely many constant symbols, hence belongs to some $L_n$. Its truth is decided by ${\mathrm{DLO}}_n$, and every first-order model of ${\mathrm{DLO}}_{\omega }$ has a reduct satisfying that finite first-order theory. Thus the larger first-order theory also decides every first-order sentence. The rational-order examples in (ii) establish first-order consistency. ConsequentlyThere is no contradiction with (ii): completeness is agreement on individual finite first-order sentences, while categoricity requires a global isomorphism respecting all constants simultaneously.