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

A complete $n$-type over $T$ is a maximal set $p(\bar{x})$ of formulas in $n$ variables consistent with $T$; it decides each such formula or its negation. A partial type drops maximality. A tuple realizes the type if it satisfies every member. A complete type is principal, or isolated, if some formula $\theta (\bar{x})$ consistent with $T$ implies every member of the type modulo $T$; then $\theta$ itself belongs to that type.

The omitting types theorem says that in a countable first-order language, a consistent theory has a countable model omitting a specified nonprincipal type; more generally a countable family of nonprincipal types can be omitted simultaneously. In the present complete-theory setting it applies directly to complete nonisolated types. “Omitted” means that no tuple in the model realizes all formulas of the type, even though each finite subset is compatible with the theory.

A model is prime if it has an elementary embedding into every model of $T$. A model is atomic if every finite tuple realizes an isolated complete type over the empty set.

If $A$ is prime, the downward Löwenheim-Skolem theorem gives a countable model $M$ of $T$, and an elementary embedding $A\to M$ makes $A$ countable. If a tuple of $A$ realized a nonisolated type, the omitting types theorem would give a model of $T$ omitting that type. The prime embedding into it would preserve the tuple's full type and realize the omitted type, a contradiction. Thus a prime model is countable and atomic.

Conversely enumerate a countable atomic model as $a_0,a_1,\dots$, and take any $B\models T$. Build finite partial elementary maps into $B$. Suppose the current tuple $\bar{a}$ maps to $\bar{b}$. Choose a formula $\theta (\bar{x},y)$ isolating the type of $(\bar{a},a_n)$. The assertion $\exists y\theta (\bar{a},y)$ holds in $A$, so its counterpart holds at $\bar{b}$ in $B$ by partial elementarity. Choose a witness $b_n$. Since $\theta$ isolates the entire extended tuple type, the extended map is elementary on its finite domain; its equality formulas ensure distinct Elements remain distinct. The union is a total elementary embedding $A\to B$. The empty initial tuple works because $T$ is complete. Hence

An ${\aleph }_0$-saturated model realizes every complete type in finitely many variables over every finite parameter subset of itself. It suffices equivalently to require one-variable types and then realize finite tuples successively. The definition puts no countability restriction on the size of the model.

For any model $M$, collect all complete types over its finite parameter sets. Add to its elementary diagram, for each such type, a new tuple of constants satisfying all that type's formulas. Any finite selection of these requirements is realizable in $M$: each finite type fragment has its existential closure true there, since it is consistent with the complete theory of the corresponding named finite tuple. Distinct new tuples have no additional mutual restrictions. Compactness gives an elementary extension realizing all these types simultaneously.

Start from any model $M_0\models T$ and apply this construction repeatedly to obtain $M_0\preccurlyeq M_1\preccurlyeq \cdots$, with each successor realizing all types over finite subsets of its predecessor. The elementary-chain theorem makes $M_{\omega }={\bigcup }_n{M}_n$ a model of $T$ with every stage elementary in it. A finite parameter set $A\subseteq M_{\omega }$ lies in some $M_n$. Every type over $A$ consistent with $M_{\omega }$ is consistent with $M_n$, since the expanded complete theories at those parameters agree by elementarity. It is realized in $M_{n+1}$, hence in the union. Therefore an ${\aleph }_0$-saturated model always exists, possibly with uncountable cardinality.

For cut types over the named rational order, choose an irrational real cut, for example $r=\sqrt{2}$, and formEvery finite subset is realized by a rational between its finite lower and upper bounds, so compactness makes it a consistent partial type; quantifier elimination for dense linear orders without endpoints makes these comparisons determine a complete type in the language naming all rationals. No rational realizes the cut, so $Q^{+}$ omits it.

Add a new constant realizing this type and apply compactness, followed by downward Löwenheim-Skolem in the countable expanded language. This gives a countable model of $T$ realizing it. An isomorphism in $L_{\mathbb{Q}}$ fixes all named rationals and preserves realization of the cut, so it cannot be isomorphic to $Q^{+}$. Thus $T$ is not countably categorical. Omission by itself would need this additional realization-and-countable-model argument to establish noncategoricity.

No infinite cardinal is categorical for this theory, as described by no categorical cardinal for the complete named rational diagram. For an arbitrary infinite $\kappa$, choose a dense linear order $I_{\kappa }$ without endpoints of size $\kappa$; for example the lexicographic order on $\kappa \times \mathbb{Q}$ works, since every rational block is dense and has no endpoints.

Construct one order by inserting $I_{\kappa }$ into a fixed irrational cut of the named rational order. Every element of this order is bounded above by some named rational. Construct a second order by putting an $I_{\kappa }$ tail above all named rationals, as the ordered sum $\mathbb{Q}+I_{\kappa }$. Both are dense linear orders without endpoints, both have cardinality $\kappa$, and both contain the named rational copy as an elementary substructure by quantifier elimination. Hence both satisfy its complete diagram $T$.

They are not isomorphic over the named constants: the second has an element greater than every named rational, and the first has none. This property need not be expressible by a single sentence in the infinite language to be an isomorphism invariant. Finite cardinalities have no models at all because the constants name infinitely many distinct Elements, so the existence clause excludes categoricity there too.

Yes: $Q^{+}$ is prime. In any model of its complete diagram, map each rational to the interpretation of its named constant. The diagram ensures this is an embedding, and quantifier elimination for dense linear orders without endpoints makes it elementary. Alternatively every finite tuple of $Q^{+}$ has its complete type isolated by the conjunction equating its coordinates to their named rational constants. Thus it is a countable atomic model, and the earlier prime-model equivalence applies. A prime model may omit many types; primeness is not saturation.

There are $2^{{\aleph }_0}$ distinct irrational cuts of the named rational order. Each defines a consistent complete one-type as above, already over the empty additional parameter set, since the rational constants are part of the language. Different cuts cannot be realized by the same element: a named rational between two cuts gives contradictory required inequalities.

An ${\aleph }_0$-saturated model must realize every one of these types, so it has at least $2^{{\aleph }_0}$ Elements. Consequently there is no countable ${\aleph }_0$-saturated model of $T$. This does not contradict existence of a saturated model from the preceding construction, whose size was unrestricted, or existence of the countable prime model, whose requirement is different. No continuum-hypothesis assumption is involved.