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

A term-generated model is a structure in which every element is the value of a closed term of the original language. Equivalently its substructure generated by the empty set, including interpretations of named constants, is the entire structure. This is the relevant meaning of “term model” for a model of an arbitrary complete theory, rather than a claim about one particular syntactic construction.

Each closed term $t$ gives the parameter-free defining formula $x=t$. ThusThe next parts show that pointwise definability implies atomicity, and countable atomicity is equivalent to primeness. Therefore property (i) implies all three other properties.

An element $a$ is parameter-free definable if some formula $\theta (x)$ of the original language has $a$ as its unique solution in the structure. Saying this for every element makes the model pointwise definable.

If a finite tuple has individually defining formulas, their conjunction uniquely defines that tuple. Its complete type is isolated by this conjunction: for each formula $\phi$, the sentence saying the unique tuple does or does not satisfy $\phi$ is decided by the complete theory. ThusIt follows that the countable model is also prime. The converse implication to property (i) fails. In $(\mathbb{N},<,0)$ every element is defined by having exactly $n$ predecessors, but the only closed term in this language is the constant $0$. This infinite model is pointwise definable and is not term-generated.

An atomic model is a model in which every finite tuple realizes an isolated complete type over the empty set. For a complete theory in a countable language, every countable atomic model is prime. The underlying argument is a back-and-forth method in the one-sided form needed for an embedding: enumerate the atomic model, and extend a finite partial elementary map one element at a time using an isolating formula for the enlarged tuple. The target model has the required witness because the already matched tuple has the same complete type.

Thus property (iii) implies property (iv). It need not imply pointwise definability or term-generation. The countable dense linear order without endpoints with a single named point, for example $(\mathbb{Q},<,0)$, is atomic: quantifier elimination for dense linear orders without endpoints isolates a tuple by its finite order-and-equality pattern relative to zero. But order structure automorphisms fixing zero move every nonzero rational. Such elements are not parameter-free definable, and no closed term names them. This supplies the failed implications (iii)$\nRightarrow$(ii) and (iii)$\nRightarrow$(i).

A prime model admits an elementary embedding into every model of its complete theory. In the countable setting a prime model is atomic. If a tuple in the prime model had a nonisolated complete type, the omitting types theorem would give a model omitting that type; an elementary embedding of the prime model into it would realize the omitted type, a contradiction.

Combining the four parts, all positive implications are exactly those generated byThe structure $(\mathbb{N},<,0)$ refutes (ii)$\Rightarrow$(i). The structure $(\mathbb{Q},<,0)$ is a countable atomic and hence prime model of its complete theory, while failing both (i) and (ii); it refutes every remaining reverse arrow, including (iv)$\Rightarrow$(i) and (iv)$\Rightarrow$(ii). The counterexamples therefore cover all ordered pairs of distinct properties not forced by the boxed chain.

An omega-saturated model realizes every complete type of a finite tuple over every finite set of its domain. It suffices to require this for one-variable types: realize the coordinates successively, enlarging the finite parameter set at each step.

Every complete theory here has such a model, with no countability requirement on its size. Start with a model of size at most $\lambda =2^{{\aleph }_0}$. There are at most $\lambda$ types over its finite sets, because the language is countable and each such type is a set of formulas in a countable collection. By the compactness theorem and the elementary diagram construction, pass to an elementary extension realizing all these types, keeping size at most $\lambda$ by the Löwenheim-Skolem theorem.

Repeat this for stages $0,1,2,\dots$ and take the union of the elementary chain. Any finite parameter set in the union lies in some stage, and every type over it is realized at the next stage. The union is therefore omega-saturated. Countable language does not by itself guarantee that a countable saturated model exists.

Yes. The pure order on the reals is a dense linear order without endpoints and has quantifier elimination for dense linear orders without endpoints. Over a finite parameter set $a_1<\cdots <a_m$, a complete one-variable type either specifies equality to one of these points or specifies one of the open intervals and exterior rays they determine.

Each such interval or ray contains a real number. Hence every complete one-variable type over a finite parameter set is realized. The successive-coordinate characterization gives saturation for all finite tuples. This uses finite parameter sets; it does not say that arbitrary types over a countably infinite set of parameters are realized.

Yes. As an Abelian group, the reals are a nontrivial torsion-free divisible group, equivalently a vector space over the rationals. Rational scalar multiplication is uniquely definable by equations such as $ny=mx$, so adding those operations is a definitional expansion.

In this language, quantifier elimination for torsion-free divisible Abelian groups reduces formulas to Boolean combinations of rational linear equations. Over finitely many parameters, a complete one-variable type either fixes a value in their linear span or excludes every value in that span. The first kind is realized in the span itself; the second is realized by any real number outside it. That span is countable, while the reals are uncountable. Thus every such type is realized and the additive real group is an omega-saturated model.

For finite tuples, the same argument successively supplies any required finite number of new rationally linearly independent elements. The order and multiplication of the real field are absent from this language, so they cannot impose additional type conditions.

No. The parameter-free partial typeis finitely satisfiable in the ordered real field: choose a number larger than the finitely many bounds. By compactness theorem it extends to a complete type over the empty set. But no real number realizes it, by the Archimedean property. Therefore the ordered real field is not an omega-saturated model.

The named unit and addition make every integer bound expressible, even without extra parameters. This is why the obstruction is present in the ordered-field language and absent in the two reducts above.

Suppose $T$ is an omega-categorical theory. By the Ryll-Nardzewski theorem, every finite-arity complete type over the empty set is isolated. Let $p(x,a)$ be a complete type over a finite tuple in the unique countable model $M$, and take an elementary extension realizing it at $b$. The joint type of $(b,a)$ is isolated by a formula $\theta (x,y)$.

The complete type of $a$ contains $\exists x\theta (x,y)$, since this formula is true of $a$ in the extension. Hence it is true of $a$ in $M$, and some $b^{\prime }\in M$ satisfies $\theta (b^{\prime },a)$. Isolation of the joint type implies that $b^{\prime }$ realizes $p$. Thus the countable model is an omega-saturated model.

The converse fails. The complete successor theory from question 4 has a countable modelwith countably infinitely many two-sided successor components. It is omega-saturated. Over finitely many parameters, a complete one-variable type either fixes a finite successor/predecessor translate of a parameter or zero, or asks for a point in no component represented by those parameters and zero. The first kind is realized in the named component, and the second in an unused integer component. The quantifier-elimination description of classification of models of the successor theory shows there are no other cases.

Nevertheless this theory is not omega-categorical: $M$ and its standard model $\mathcal{N}$ are countable and not isomorphic. Thus existence of a countable saturated model is strictly weaker than countable categoricity.