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

A complete theory is $\kappa$-categorical when it has a model with underlying cardinality $\kappa$ and any two of its models of that cardinality are isomorphic structures. Thus categoricity means uniqueness up to isomorphism at the specified cardinal, not a unique underlying set or a unique isomorphism.

For the infinite cardinals relevant here, the existence clause is automatic from the stated infinite model and the Löwenheim-Skolem theorem. One may equivalently require exactly one isomorphism class of models of size $\kappa$.

An $n$-type over the empty set is a set $p(x_1,\dots ,x_n)$ of formulas of the language, with no additional parameters, jointly consistent with $T$. Equivalently every finite set is simultaneously satisfiable with $T$. A complete type decides every formula in these variables: for each $\phi$, exactly one of $\phi$ and $\neg \phi$ belongs to $p$.

A principal type has an isolating formula $\theta (x)$ consistent with $T$, such that $T\models \forall x(\theta (x)\to \phi (x))$ for every $\phi \in p$. For a complete type this is an isolated type; its isolator determines the entire type. A principal partial type may be weaker than a complete type, so its isolator need not decide all formulas.

A tuple $a\in A^n$ realizes $p$ if $\mathcal{A}\models \phi (a)$ for every formula in $p$. The model omits $p$ if it contains no such tuple. Thus omission is a simultaneous failure of realizing the whole type, even though each finite fragment can be realized.

Let $\theta (x)$ isolate the principal type. Consistency with $T$ means $T\cup \{\exists x\theta (x)\}$ is satisfiable. Because $T$ is a complete theory, it must imply $\exists x\theta (x)$; the alternative would make that extension inconsistent.

Therefore every model of $T$ has a tuple $a$ satisfying $\theta$. Each implication $T\models \theta \to \phi$ then makes $a$ satisfy every member of the type. HenceCompleteness is what turns possible realization of the isolating formula into realization in every model.

Add constants $c_1,\dots ,c_n$ and form $T\cup \{\phi (c):\phi \in p\}$. Every finite set has a model by consistency of the type. The compactness theorem gives a model $\mathcal{M}$ realizing the whole expanded theory, so $c^{\mathcal{M}}$ realizes $p$.

Apply the downward Löwenheim-Skolem theorem to the countable expanded language, retaining these finitely many named elements. The resulting countable elementary substructure still satisfies every formula of $p$ at the same tuple. Its reduct to the original language is a countable model of $T$ realizing $p$. Since $T$ has no finite models, this model is countably infinite.

The countable omitting types theorem says that for a consistent theory in a countable language and countably many nonprincipal types of finite arities, there is a countable model omitting all those types. In particular a nonisolated complete type of $T$ can be omitted in a countable model.

Interpret “definable” here as without parameters. If parameters were allowed freely, every infinite structure would have infinitely many definable singleton sets, and the claimed implication would be false even for a dense linear order without endpoints.

Infinitely many distinct parameter-free definable subsets of $A^n$ imply infinitely many complete $n$-types: if there were only $r$ such types, each formula would select a subset of those $r$ types, giving at most $2^r$ distinct definable subsets. There must also be a nonisolated complete type. To see this, suppose each complete type $p$ had an isolator ${\theta }_p$. The family of their basic open sets covers the type space. Its compactness theorem gives a finite subcover, which would account for only finitely many complete types, a contradiction. Equivalently apply logical compactness theorem to $T\cup \{\neg {\theta }_p(c):p\text{ complete}\}$.

Choose a nonisolated type $p$. The omitting types theorem gives a countable model omitting it, while part (d) gives a countable model realizing it. An isomorphism of structures preserves realization of parameter-free types, so these models are not isomorphic. Thus $\boxed{T\text{ is not }{\aleph }_0\text{-categorical}}$.

No. In the standard successor structure, every element other than the named zero has a predecessor:The proposed structure fails this first-order sentence at the integer $-1$. Its nonnegative elements map to positive elements, while every negative element maps to an integer at most $-2$; hence no element maps to $-1$. This gives a direct first-order distinction, without treating the negative branch as a two-sided successor chain.

Take the standard successor structure and its disjoint union with one two-sided integer successor chain:Both interpret the named zero in the natural-number component. The classification of models of the successor theory describes every model as this distinguished one-sided chain together with an arbitrary collection of two-sided chains. Its axioms are injectivity of $s$, zero outside its range, a predecessor for every nonzero element, and absence of finite cycles. These axioms are complete; equivalently the theory has the successor quantifier-elimination property explained in the concept proposal.

Consequently both displayed structures are models of the standard complete theory. They are not isomorphic: any isomorphism must fix zero and hence every element $s^n(0)$. The first structure has no other elements; the second has the entire extra integer chain. Being in that additional component is an isomorphism invariant even though being outside all standard iterates of zero is not expressible by one first-order formula.

For each natural number $n$, the formula $x=s^n(0)$ defines the singleton $\{n\}$ in the standard successor structure. These are pairwise distinct parameter-free definable subsets. ThereforeIn particular the criterion in part (e) applies already at arity one.

Consider the partial typeEach finite fragment is realized by a sufficiently large standard natural number, so it is consistent. It is omitted in the standard successor structure, since each of its elements equals one of the named iterates.

There is exactly one complete type extending this partial type. By classification of models of the successor theory and its quantifier-elimination property, a parameter-free one-variable formula is equivalent to a Boolean combination of finitely many equalities $x=s^n(0)$ and sentences whose truth is fixed by the theory. For a point on an extra integer chain every displayed equality is false, so all such points have the same complete type. Thusis the required omitted complete type. More formally take all formulas true at such a point; $p_{\infty }$ axiomatizes that type modulo the theory, and its deductive closure is complete.

The distinguished chain generated by zero is countable, and every other component in the classification of models of the successor theory is a countable copy of the integer successor chain. A model of cardinality ${\aleph }_1$ therefore has exactly ${\aleph }_1$ additional components: a finite or countable collection would be countable, while the union of $\kappa$ countable components has size $\max (\kappa ,{\aleph }_0)$.

Given two such models, match their zero chains in the forced way and choose a bijection between their additional components. On each component choose an origin and match corresponding integer iterates; this commutes with successor. The union of these maps is an isomorphism of structures. Existence is given by a disjoint union with ${\aleph }_1$ integer chains. HenceThe same argument works at every uncountable cardinal. Countable models can still differ by the number of extra components, as part (ii) shows.

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.

Expand the language by a constant $c_a$ for every element of the structure. Its diagram of a structure consists of all atomic and negated atomic sentences true in this expanded structure. Its elementary diagram, also called the complete diagram, consists of all first-order sentences true in the expansion.

For a model $M$ of the diagram, the map $a\mapsto c_a^M$ is injective because the diagram includes all required inequalities. It preserves functions and constants by the corresponding equations, and it preserves and reflects relations by the positive and negative atomic sentences. Thus it is a structure embedding onto a substructure of the reduct of $M$. Conversely, a structure containing an isomorphic copy of the original as a substructure can interpret the new constants at that copy and satisfy its diagram.

For the elementary diagram the same argument works for every formula, not just atomic ones. The map is therefore an elementary embedding. Conversely any elementary embedding gives an expansion satisfying the elementary diagram. These are characterizations up to the named copy; a model of either diagram may have additional unnamed elements.

For a structure in a countable language and any subset $C$ of its domain, there is an elementary substructure containing $C$ of cardinality at most $\max (|C|,{\aleph }_0)$. In particular a finite or countable $C$ lies in a countable elementary substructure. This is the downward Löwenheim-Skolem theorem.

Construct it directly inside the given structure $A$. Start with $C_0$ containing $C$, the interpretations of the constants, and one element if needed to ensure a nonempty domain. Given $C_n$, for every formula $\exists x\phi (x,a)$ with its finite parameter tuple from $C_n$ that is true in $A$, choose one actual witness in $A$ and place it in $C_{n+1}$. Retain $C_n$ as well. There are at most $\max (|C|,{\aleph }_0)$ choices at each stage. Let $B={\bigcup }_{n<\omega }{C}_n$.

The construction closes $B$ under every function of the language: for a tuple in $C_n$, the formula $x=f(a)$ forces its unique value into the next stage. Thus $B$ carries the induced substructure, and it has the asserted cardinal bound.

Prove elementarity by structural induction. Atomic formulas agree by the induced-substructure construction; logical connectives preserve agreement. For an existential formula with parameters in $B$, if it is true in $A$, all its parameters occur in some $C_n$, so the chosen witness lies in $C_{n+1}\subseteq B$. The induction hypothesis makes its matrix true in $B$. In the other direction a witness in $B$ is also a witness in $A$, again by induction. This is the Tarski-Vaught test, with its witness argument proved explicitly. No completeness or compactness theorem theorem enters the construction.

Skolem's paradox is the apparent conflict between a countable model of a sufficiently strong set theory and that model's theorem asserting the existence of uncountable sets. Downward Löwenheim-Skolem theorem gives a countable elementary model whenever an appropriate infinite model exists; internally the same model still proves, for example, that its real-number set is uncountable.

The two uses of “countable” quantify over different collections of functions. Externally the whole model, and therefore the elements it regards as members of its real-number set, can be enumerated. Internally a set is countable only if an enumerating function exists among the sets of the model. The external enumeration need not be an element of the model.

Thus there is no contradiction: the model's assertion is that no function it contains is the required enumeration. Cantor's theorem remains valid inside the model. The model need not be transitive or have the actual standard natural numbers for this explanation; the essential issue is the restriction of internal quantifiers to its own domain.

For the pure orders, yes. Both structures satisfy the theory of dense linear orders without endpoints. By quantifier elimination for dense linear orders without endpoints, each formula is equivalent to a quantifier-free order formula. Inclusion of the rationals into the reals preserves and reflects all such formulas, hence is elementary:

With a common named unit, yes. In general an elementary substructure remains elementary when elements already in the substructure are named by new constants. A formula using the new constant is just an old-language formula with that common element as a parameter. Since $1\in \mathbb{Q}$, this applies directly.

With the real constant interpreted by $\pi$, no choice inside the rationals works for inclusion. A substructure embedding must preserve every constant. The inclusion would send a rational interpretation $q$ to that same real $q$, whereas the target constant is $\pi \notin \mathbb{Q}$. Thus the expanded rational structure is not even a substructure of the expanded real one.

This last failure concerns the specified inclusion. There is an abstract elementary embedding carrying a chosen rational $q$ to $\pi$: the increasing map $r\mapsto r+\pi -q$ has that property, and its image is a dense order without endpoints inside the reals. Quantifier elimination makes the embedding elementary, but its image is a translated copy of the rationals rather than the original rational subset.