Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 23 (Model Theory)

Let $R={\prod }_i{\mathcal{M}}_i/F$ be the reduced product by a proper filter on a set. Its underlying equivalence relation is $f\sim g$ when $\{i:f(i)=g(i)\}\in F$. Operations are interpreted coordinatewise, and a relation holds of the classes exactly when its coordinate truth set belongs to $F$.

Evaluation of a first-order term commutes with passage to the quotient, by mathematical induction on terms. Consequently the desired equivalence holds for every atomic formula, including logical equality. For a formula $\theta$ and representatives $\bar{f}$, write $S_{\theta }=\{i:{\mathcal{M}}_i\models \theta (\bar{f}(i))\}$.

For logical conjunction, $S_{\theta \wedge \psi }=S_{\theta }\cap S_{\psi }$. The filter on a set axioms giveThus the induction hypothesis transfers a conjunction in both directions.

For existential quantification, first suppose $R\models \exists y\theta (y,[\bar{f}])$. Choose a representative $g$ of a witness. Induction gives $S_{\theta (g,\bar{f})}\in F$, and this set is contained in $S_{\exists y\theta }$. Upward closure therefore gives $S_{\exists y\theta }\in F$.

Conversely, suppose $A=S_{\exists y\theta }\in F$. For each $i\in A$, choose a coordinate witness $g(i)$, and choose an arbitrary element of $M_i$ outside $A$. These simultaneous choices use the axiom of choice, as does the usual product construction. Then $A\subseteq S_{\theta (g,\bar{f})}$, so that truth set belongs to $F$. Induction gives $R\models \theta ([g],[\bar{f}])$, providing the required witness. Thereforefor every primitive positive formula. The exam's tame formulas are exactly this fragment, built using logical conjunction and existential quantification. No ultrafilter dichotomy was used.

Take $I=\{0,1\}$ and the proper filter on a set $F=\{I\}$. In the first-order language with unary predicates $P,Q$, let both factors be one-element first-order structures. Set $P$ true and $Q$ false in the first factor, and reverse these truth values in the second.

The reduced product also has one element $a$. Neither $P(a)$ nor $Q(a)$ holds there: their truth sets are $\{0\}$ and $\{1\}$, neither belonging to $F$. ThusLogical disjunction can therefore break the equivalence. A union can belong to a filter on a set without either summand belonging to it; the corresponding union property does hold for an ultrafilter.

Use the same two-index filter on a set $F=\{\{0,1\}\}$, with a unary predicate $P$ true only in the first one-element factor. In the reduced product, $P(a)$ is false, so $\neg P(a)$ is true. ButLogical negation also breaks the equivalence. For a general proper filter on a set, a set and its complement can both be absent. In an ultrafilter, exactly one belongs, which is the step used to transfer logical negation in the Łoś theorem.

An ultrafilter $U$ on $X$ is kappa-complete if, for every index set $J$ with $|J|<\kappa$ and every family $(A_j{)}_{j\in J}$ of members of $U$,The bound is strictly fewer than $\kappa$ sets. In particular every ultrafilter is ${\aleph }_0$-complete, since this requires only finite intersections; countably complete ultrafilters require intersections of countably many members, equivalently ${\aleph }_1$-completeness.

First use the fact that a small set is absent from a complete nonprincipal ultrafilter. Indeed, if $A\subseteq \kappa$ and $|A|<\kappa$, then every $\kappa \setminus \{\alpha \}$, $\alpha \in A$, belongs to $U$ by nonprincipality. Kappa-completeness gives $\kappa \setminus A\in U$, so $A\notin U$. In particular every final segment $\{i:i>\alpha \}$ belongs to $U$.

Suppose for contradiction that the ultrapower has at most $\kappa$ elements. List representatives $f_{\alpha }:\kappa \to M$ for all its classes, indexed by $\alpha <\kappa$; repetitions are allowed. At coordinate $i<\kappa$, fewer than $\kappa$ values occur among $f_{\alpha }(i)$ with $\alpha <i$. Since $|M|\ge \kappa$, chooseThis diagonal argument for ultrapower cardinality uses the axiom of choice. For each fixed $\alpha$, the functions $g$ and $f_{\alpha }$ disagree throughout the final segment $i>\alpha$, which belongs to $U$. Their equality set therefore cannot belong to $U$, and $[g]\ne [f_{\alpha }]$.

This contradicts the assumed enumeration of the ultrapower. HenceThe proof uses only that each ordinal $i<\kappa$ has cardinality below $\kappa$; it does not require a separate assumption of regularity.

Here is the existential common-substructure test for quantifier elimination. Use a first-order language with a constant symbol, as in the applications below, or the usual conventions for empty generated substructures and truth constants. Let $T$ be a first-order theory. Suppose that whenever $\mathcal{M},\mathcal{N}\models T$ have a common substructure $\mathcal{A}$, then, for every quantifier-free formula $\theta (x,\bar{y})$ and every finite tuple $\bar{a}\in A$,The condition is symmetric because it applies also with $\mathcal{M}$ and $\mathcal{N}$ exchanged. The conclusion is quantifier elimination for $T$: for every first-order formula $\phi (\bar{y})$ there is a quantifier-free formula $\psi (\bar{y})$ such thatThe common substructure need not itself satisfy $T$, and witnesses are sought in the whole models, not necessarily in $A$. This test is the QET1 version of the common-substructure test for quantifier elimination.

Let $T_{\forall }$ denote the universal consequences of a theory: all universal first-order sentences entailed by $T$. A first-order structure satisfies $T_{\forall }$ exactly when it embeds into a model of $T$, by the compactness theorem applied to its diagram of a structure.

The theory has algebraically prime models if, for every $\mathcal{A}\models T_{\forall }$, there are $\mathcal{P}\models T$ and a structure embedding $i:\mathcal{A}\to \mathcal{P}$ such that every structure embedding $j:\mathcal{A}\to \mathcal{N}$, $\mathcal{N}\models T$, factors as $j=h\circ i$ for some structure embedding $h:\mathcal{P}\to \mathcal{N}$. Neither $i$ nor $h$ is required to be elementary.

For $\mathcal{M}\subseteq \mathcal{N}$, simple closure means that every existential quantifier-free formula over $M$ which has a witness in $N$ has one in $M$:Now take two models $\mathcal{M},\mathcal{N}\models T$ with common substructure $\mathcal{A}$. Since $A$ embeds into $M$, it satisfies $T_{\forall }$. Choose its algebraically prime extension $\mathcal{P}$, and embed $P$ into both $M$ and $N$ over $A$.

If $\exists x\theta (x,\bar{a})$ holds in $M$, the image of $P$ in $M$ is a model of $T$. The assumed simple closure of this image transfers a witness from $M$ into $P$. Its embedding into $N$ then transfers the quantifier-free formula and its witness into $N$. Thus the hypothesis of QET1 is satisfied. The second test follows: $T$ has quantifier elimination.

A torsion-free divisible Abelian group is naturally a vector space over the rational numbers: for $m\in \mathbb{Z}$ and $n>0$, define $(m/n)a$ as the unique $b$ with $nb=ma$. Divisibility supplies existence and torsion-freeness supplies uniqueness.

In the usual group first-order language $\{+,-,0\}$, a model $A$ of the universal part of DAG is a torsion-free group which is Abelian. If the language instead uses only $\{+,0\}$, a substructure can be merely a torsion-free cancellative commutative monoid. Handle this convention by first taking its Grothendieck group $G(A)$: its elements are formal differences $a-b$, withThe cancellative commutative monoid condition makes $A\to G(A)$ injective. If $n(a-b)=0$, then $na=nb$, and torsion-freeness gives $a=b$; hence $G(A)$ is a torsion-free abelian group. In the full group language simply take $G(A)=A$.

For $A\ne \{0\}$ form its rational divisible hullConcretely its elements are fractions $g/n$ with $n>0$, where $g/n=h/m$ if $mg=nh$. The canonical embedding of $A$ into $P$ is injective, and $P$ is nontrivial, divisible, Abelian and torsion-free, so it satisfies DAG.

Let $j:A\to N$ be any structure embedding into a model of DAG. Extend it first to formal differences if necessary. Its unique extension to the rational divisible hull sends $g/n$ to the unique element $b\in N$ with $nb=j(g)$. This is a group homomorphism fixing the given copy of $A$. It is injective: an element mapped to zero has $j(g)=0$, hence $g=0$. Thus every embedding into a DAG model factors through $P$.

The zero case must be treated separately: its rational divisible hull is zero and does not satisfy DAG. Instead choose $P=(\mathbb{Q},+)$. Given any nontrivial DAG model $N$, choose $b\ne 0$; the map $q\mapsto qb$ embeds $P$ into $N$ over zero. Therefore DAG has algebraically prime models, including over the trivial base.

Both assertions are false. For simple closure, take the inclusionBoth satisfy DAG prime, but the quantifier-free formula $x\ne 0$ has a witness in $N$ and none in $M$. The same example works in the reduced language $\{+,0\}$.

For quantifier elimination, the first-order sentence $\exists x(x\ne 0)$ distinguishes these two models. Every closed group term is zero, so every atomic closed equality is true in both models. Every quantifier-free sentence, being a Boolean combination of such equalities, has the same truth value in both. The distinguishing sentence therefore has no equivalent quantifier-free sentence modulo DAG prime. HenceIncluding the trivial group is exactly what makes the proposed simple closure condition fail.

A first-order theory $T$ is model-complete if every structure embedding between models of $T$ is an elementary embedding. Equivalently, whenever $\mathcal{M}\subseteq \mathcal{N}$ and both satisfy $T$, one has $\mathcal{M}\preccurlyeq \mathcal{N}$:for every first-order formula $\phi$ and every finite tuple $\bar{a}\in M$. This is preservation of all formulas with parameters, rather than merely all first-order sentences.

Assume $T$ has quantifier elimination, and let $j:\mathcal{M}\to \mathcal{N}$ be a structure embedding between its models. For any first-order formula $\phi (\bar{x})$, choose a quantifier-free formula $\psi$ equivalent to it modulo $T$. A structure embedding preserves and reflects atomic formulas; induction through the Boolean connectives therefore preserves every quantifier-free formula. ThusThe embedding is elementary. Every theory with quantifier elimination is model-complete.

A model companion $T^{\ast }$ of a first-order theory $T$, in the same first-order language, is a model-complete theory with the same universal consequences of a theory as $T$:Equivalently, every model of $T$ embeds into a model of $T^{\ast }$, and every model of $T^{\ast }$ embeds into a model of $T$. The equivalence follows from the diagram embedding criterion for universal theories, which is an application of the compactness theorem. A model companion need not be a syntactic extension of $T$, and uniqueness is understood up to logical equivalence of theories.

Suppose $S$ and $R$ are model companions of $T$. Their universal consequences of a theory agree, so the diagram embedding criterion for universal theories permits embeddings in both directions between their model classes.

Starting from any $M_0\models S$, alternately take such extensions, identifying each model with its image under the embedding:Since $S$ is model-complete, $M_i\preccurlyeq M_{i+1}$; since $R$ is model-complete, $N_i\preccurlyeq N_{i+1}$. The two subsequences have the same union $U$. The elementary chain theorem givesEvery axiom of $R$, as a sentence true in $U$, is therefore true in $M_0$. Thus every model of $S$ is a model of $R$. Reversing their roles proves the converse. The model companion is unique up to logical equivalence. If $T$ is inconsistent, its only possible companion is likewise inconsistent, so the same uniqueness conclusion holds.

A formally real field is a field in which $-1$ is not a finite sum of squares. The theory of formally real fields consists of the field axioms and, for each $m\ge 1$, the sentenceA real closed field is a formally real field with no proper formally real algebraic extension. An equivalent first-order axiomatization of the Theory of real closed fields adds: every $a$ or its negative is a square, and every odd-degree polynomial has a root. Explicitly the square axiom isand the polynomial axioms say that every monic polynomial of degree $2d+1$ has a root, for each $d\ge 0$.

The Artin-Schreier ordering criterion says that every formally real field can be ordered, and the real closure theorem embeds each ordered field into an algebraic real closed field extension. Consequently every FRF model embeds into an RCF model. Conversely every RCF model is itself an FRF model, so the reverse embedding requirement is automatic.

It remains to establish model completeness. A real closed field has a unique order, definable in the field language byAny field embedding between real closed fields preserves this order: positive elements are nonzero squares, and negative elements have positive negatives. The quantifier elimination for ordered real closed fields theorem makes every such ordered embedding elementary, by the preceding part. Restricting to formulas of the field language makes the original embedding elementary as well. Thus RCF is model-complete in the field language.

The embedding conditions and model completeness proveThe quantifier elimination invoked here is in the ordered language. In the unordered field language, model completeness still holds, but full quantifier elimination does not follow from forgetting the order.

The quantifier rank measures maximum nesting depth:Two first-order structures are rank-n equivalent if they agree on all first-order sentences of quantifier rank at most $n$. For tuples one similarly compares all such formulas evaluated at the tuples.

In the $n$-round Ehrenfeucht-Fraïssé game, player I, the Spoiler, chooses an element from either structure each round; player II, the Duplicator, chooses an element in the other. After $n$ rounds the corresponding chosen tuples must define a partial isomorphism of structures: all atomic formulas, including equality and the interpretations of constants, have matching truth values. Repetitions must be respected. Failure of this condition is a loss for II.

The precise finite-vocabulary Ehrenfeucht-Fraïssé theorem is: for a finite relational language, allowing finitely many constants,The tuple version has the same conclusion when the corresponding tuples are fixed before play. The implication from a winning strategy to rank equivalence holds for arbitrary languages, by induction on formulas. For the converse, finite relational vocabulary ensures only finitely many rank-bounded types in a fixed tuple of variables; their defining formulas let one transfer the type of the next move. Without a finiteness hypothesis, the converse for the full atomic-diagram game need not hold. This qualification matters in the next part.

Under the finite relational vocabulary hypothesis of the Ehrenfeucht-Fraïssé theorem, II wins the timed game exactly when the structures are elementarily equivalent. If II wins, then for every choice of $n$ by I, its strategy restricts to a winning strategy in $G_n$. Hence the models agree on every sentence of quantifier rank at most $n$. Every first-order sentence has finite quantifier rank, so they agree on all sentences.

Conversely, elementary equivalence gives $\mathcal{M}{\equiv }_n\mathcal{N}$ for every $n$. Choose a winning strategy for each $G_n$, and use that strategy once I announces $n$. Unlike the infinite game, the timed game permits the strategy to depend on the announced horizon.

The PDF does not explicitly impose finite vocabulary. If an arbitrary language and the full partial isomorphism of structures winning condition are intended, the reverse assertion is false. Here is a failure of finite-round game equivalence in infinite languages. Let $L=\{P_i:i\in \mathbb{N}\}$ be unary relational. Letand obtain $N$ by adjoining one point $b$ satisfying every $P_i$.

For any finite sublanguage, every Boolean cell of predicates has infinitely many elements in both structures. Every finite partial isomorphism of structures of these reducts can therefore be extended in either direction. Induction on formulas, or a back-and-forth method, shows their reducts are elementarily equivalent. Since every sentence uses finitely many symbols, $M\equiv N$ in the whole language.

Nevertheless I wins $G_1(M,N)$ by choosing $b$: every point of $M$ fails some $P_i$, so no response preserves all atomic formulas. Thus the printed unrestricted equivalence requires the finite-vocabulary convention, or a game which additionally restricts each play to a finite vocabulary fragment.

Use the one-relation language $\{<\}$ and the total orderswhere the second is the order sum: every point in its natural-number block lies below every point in its integer block.

To show II wins every finite Ehrenfeucht-Fraïssé game, use the interval threshold strategy for discrete linear orders. With $k$ rounds left, corresponding open intervals and end rays between already matched points have either the same size below $h_k=2^k-1$, or both have at least $h_k$ elements. Their sizes may be infinite. The chosen-point correspondence is order preserving. Initially the unique interval is infinite in both orders, so the invariant holds.

If I chooses a repeated point, II repeats its counterpart. If I chooses in a short interval, II chooses the point with the same finite rank in the matching interval. In a long interval, let $h=h_{k-1}$. If one side of the chosen point has fewer than $h$ elements, reproduce that size in the other interval; the opposite sides then both have at least $h$ elements. Otherwise choose a response having at least $h$ elements on each side. Such a response exists because the interval has at least $2h+1=h_k$ elements. The endpoint and successor/predecessor properties of these two discrete orders allow the finite small-side counts to be reproduced. This establishes the invariant with $k-1$ rounds left and gives a finite-game winning strategy. Therefore II wins the timed game.

In the infinite Ehrenfeucht-Fraïssé game, I first chooses a point $b$ in the integer block of $N$. It has infinitely many predecessors. II must respond with some $m\in \mathbb{N}$, which has exactly $m$ predecessors. I then chooses $m+1$ distinct predecessors of $b$. To preserve order and equality, II would need $m+1$ distinct points below $m$, which is impossible. ThusI chooses the required finite length only after seeing II's first response, which explains why this does not contradict the timed-game result.

Take a rooted directed graph $G$ with one root $r$ and one terminal vertex $a$, with its sole edge $r\to a$. Let $H$ have a root $s$ and two terminal vertices $b,c$, with edges $s\to b$ and $s\to c$. The relationis a bisimulation. Each root move can be matched by a root move ending in a related terminal vertex. At all related terminal pairs there are no further edges, so both matching conditions are vacuous. Yet the directed graphs have two and three vertices and cannot be isomorphic. Bisimilarity need not preserve the number of successors.

Here and in the next part, the second graph's edge relation is $F$, and its response vertices belong to $H$. These are the corrections to the printed relation and vertex slips in the bisimulation clauses.

Suppose first that $Z$ is a bisimulation containing the root pair. II maintains the invariant that the current pair lies in $Z$. If I moves in the first rooted directed graph, the forth clause supplies a matching successor in the second; if I moves in the second, the back clause supplies a matching successor in the first. II can choose such a response every time I can move. Therefore II never loses after finitely many steps and wins the bisimulation game.

Conversely, let $\sigma$ be a winning strategy for II. Define $Z$ to consist of all endpoint pairs of finite legal plays starting at the roots and consistent with $\sigma$, including the initial root pair. This definition keeps every possible history; it does not assume that $\sigma$ depends only on the current position.

Take $(g,h)\in Z$ and a finite history realizing it. For any successor $g^{\prime }$ of $g$, extend that history by having I choose the edge $g\to g^{\prime }$. Since $\sigma$ is winning, it supplies a successor $h^{\prime }$ of $h$. The new endpoint pair $(g^{\prime },h^{\prime })$ belongs to $Z$, proving forth. Letting I choose any successor of $h$ proves back in the same way. Hence $Z$ is a bisimulation andConnectedness ensures that both projections of $Z$ cover all vertices: I can walk any finite directed path from either root and II's strategy supplies the matching path. The equivalence itself only concerns the rooted reachable behaviour and remains valid without connectedness.

Expand the language by constants for $A$ and write $T_A=\mathrm{Th}(\mathcal{M},a{)}_{a\in A}$. An A-type over a structure is a set of formulas in a fixed finite tuple $\bar{x}$, with parameters from $A$, consistent with this complete theory.

Let $Q=\{{\phi }_1(\bar{x}),\dots ,{\phi }_m(\bar{x})\}\subseteq P$. If no tuple of $M$ realized $Q$, thenThat sentence belongs to $T_A$ and contradicts the consistency of $T_A\cup P$. ConsequentlyFor $Q=\varnothing$, any tuple works because domains are nonempty. This proves finite satisfiability; realization of the entire partial type may require an elementary extension.

The Stone topology on a type space has basic open setswhere $\phi$ ranges over formulas with parameters in $A$ and $n$ free variables. Here points are complete types consistent with $T_A=\mathrm{Th}(\mathcal{M},a{)}_{a\in A}$. Arbitrary open sets are unions of these basic sets.

The identitiesshow that the basic sets are clopen sets and form a basis. Distinct complete types contain opposite choices for some formula, so this topology is Hausdorff. The compactness theorem gives compactness: a family of basic closed sets with the finite intersection property determines a consistent set of formulas, which extends to a complete type. Thus logical formulas provide a basis of clopen tests for distinguishing points of the type space.

A precise countable-language form of the omitting types theorem is the following. Let $T$ be a consistent first-order theory in a countable first-order language, and let $(p_j({\bar{x}}_j){)}_{j\in \mathbb{N}}$ be a countable family of nonprincipal partial types, each in finitely many variables. Then there is a finite or countably infinite model of $T$ omitting all the $p_j$.

A partial type is a set of formulas jointly consistent with $T$. It is principal if there is a formula $\theta (\bar{x})$ such that $T\cup \{\exists \bar{x}\theta \}$ is consistent andFor a complete type, this is exactly being an isolated type. Nonprincipal means that no such formula exists. A model omits $p$ if no tuple in that model satisfies every formula in $p$; different tuples may fail different members of the type. The model in the theorem need not omit each individual formula everywhere.

For parameter types, use the expanded language naming the parameters. Countability then applies to that expanded language, and hence requires a countable parameter set as well. There is no countability restriction in the finite-satisfiability argument of part (a).

Let $p(\bar{x})$ be an isolated type over $A$, with isolating formula $\theta (\bar{x})$ over $A$. Its consistency with $T_A$ and the complete theory property implyotherwise $\neg \exists \bar{x}\theta$ would belong to $T_A$, contradicting consistency. Choose a tuple $\bar{b}\in M$ satisfying $\theta$. By isolation,so $\bar{b}$ satisfies every member of $p$. Therefore every isolated A-type is realized in the original structure. The same reasoning works for a principal partial type whose isolating formula need not itself be a member of the type.

Use the first-order language with one constant $c$, take $\mathcal{M}=(\mathbb{N},c=0)$ with equality only, and let $A=\varnothing$. SetThis complete type contains $x=c$ and is isolated by that formula. In any first-order structure, at most one element can satisfy $x=c$. In every $\mathcal{N}\equiv \mathcal{M}$, its interpretation of $c$ realizes $P$, by elementary equivalence. Hence no elementarily equivalent model has infinitely many realizations of $P$. An algebraic type can have a fixed finite number of realizations in every model.

A counterexample can even use a nonalgebraic isolated type. Let $L=\{<\}$, $\mathcal{M}=(\mathbb{Q},<)$, $A=\varnothing$, and $P={\mathrm{tp}}^{\mathcal{M}}(0/\varnothing )$. The quantifier elimination for dense linear orders without endpoints shows that all elements have the same complete type over the empty set: a one-variable quantifier-free formula has no order information except $x=x$ and $x<x$.

Thus $x=x$ isolates $P$. Every $\mathcal{N}\equiv \mathcal{M}$ is a dense linear order without endpoints, and every element of $N$ realizes $P$. Such a model cannot omit it. Even a type with infinitely many realizations need not be omittable; isolation is the relevant obstruction.

Use the countable-language hypothesis of the omitting types theorem, which is the usual convention for this prime-model result. Let $\mathcal{M}$ be a prime model of $T$ and $a\in M$.

First, $T$ is complete up to logical consequence: every model $\mathcal{N}\models T$ receives an elementary embedding of $\mathcal{M}$, so it satisfies exactly the same sentences as $\mathcal{M}$. We may therefore replace $T$ by $\mathrm{Th}(\mathcal{M})$ without changing its model class or the prime model property.

Suppose $p={\mathrm{tp}}^{\mathcal{M}}(a/\varnothing )$ were not isolated. The omitting types theorem, applied to this single complete type, would produce $\mathcal{N}\models T$ omitting $p$. By primality choose an elementary embedding $j:\mathcal{M}\to \mathcal{N}$. For every $\phi (x)\in p$,Then $j(a)$ realizes $p$, contradicting omission. ConsequentlyThe same proof applies to every finite tuple, giving an atomic model. Countability of the language is a hypothesis of this argument, not a restriction on parameter sets in the separate parts (a) and (d). The PDF does not state that standing hypothesis explicitly; it must be included when invoking this version of the theorem.