Contents / Mathematical Logic / Model Theory

Chapter 5

Model Theory

Structures, satisfaction, elementary equivalence, substructures, ultraproducts, and the completeness theorem.

Introduction

A formal language is a supply of marks on paper: symbols, formulas, proofs. A mathematical structure is a set with some operations and relations on it. Model theory is the systematic study of the map between the two — which structures make which sentences true, and what that correspondence can and cannot see.

The subject's characteristic discovery is that the correspondence is lossy in a precisely measurable way. First-order logic cannot count past the finite: a theory with arbitrarily large finite models has an infinite one, a theory with one infinite model has models of every infinite size, and no first-order theory pins down $N$ up to isomorphism. Those limitations are not defects to be patched; they are theorems, and each of them is a tool. Compactness manufactures infinite integers; Löwenheim–Skolem manufactures countable models of set theory; ultraproducts manufacture a single structure out of infinitely many and prove compactness as a by-product.

This chapter builds the machinery in order: structures and the maps between them, elementary equivalence and elementary substructures, the two Löwenheim–Skolem theorems, compactness and its standard harvest, filters and the ultraproduct construction with Łoś's theorem, the completeness theorem in its model-existence form, and finally categoricity and quantifier elimination — the tools that let you prove a theory complete and then decide its sentences.

5.1Structures, Homomorphisms and Embeddings

Everything begins with a choice of vocabulary. A signature (or language) $L$ is a set of constant symbols, function symbols and relation symbols, each function and relation symbol carrying an arity, the number of arguments it takes. The signature of ordered rings is ${0, 1, +, \cdot, -, <}$ ; the signature of graphs is a single binary relation $E$ ; the signature of pure set theory is a single binary relation $\in$ . Nothing in the signature has meaning yet: $+$ is a mark with arity $2$ .

Definition 5.1 (Structure). An $L$ -structure $M$ consists of a non-empty set $M$ , called the domain or universe, together with an interpretation of each symbol of $L$ :

each constant symbol $c$ receives an element $c^{M} \in M$ ;
each $n$ -ary function symbol $f$ receives a function $f^{M} : M^{n} \to M$ ;
each $n$ -ary relation symbol $R$ receives a set $R^{M} \subseteq M^{n}$ .

The cardinality of $M$ is $∣ M ∣$ .

The non-emptiness requirement is not cosmetic. Classical first-order semantics validates $\exists x (x = x)$ , and a great many derivations silently instantiate a universal quantifier to obtain an element; both fail over an empty domain. Free logics drop the requirement and pay for it with a more complicated deduction system.

Interpretations of the symbols propagate to interpretations of terms. Given an assignment $s$ of domain elements to variables, define $t^{M} [s]$ by recursion: a variable $x$ denotes $s (x)$ , a constant $c$ denotes $c^{M}$ , and $f (t_{1}, \dots, t_{n})$ denotes $f^{M} (t_{1}^{M} [s], \dots, t_{n}^{M} [s])$ . Formulas are then evaluated by a second recursion.

Definition 5.2 (Satisfaction). The relation $M ⊨ ϕ [s]$ (" $M$ satisfies $ϕ$ under the assignment $s$ ") is defined by recursion on the structure of $ϕ$ :

$M ⊨ (t_{1} = t_{2}) [s]$ iff $t_{1}^{M} [s]$ and $t_{2}^{M} [s]$ are the same element;
$M ⊨ R (t_{1}, \dots, t_{n}) [s]$ iff $(t_{1}^{M} [s], \dots, t_{n}^{M} [s]) \in R^{M}$ ;
$M ⊨ \neg ϕ [s]$ iff $M ⊨ ϕ [s]$ fails, and the clauses for $\land, \lor, \to$ follow the truth tables;
$M ⊨ \exists x ϕ [s]$ iff $M ⊨ ϕ [s^{'}]$ for some assignment $s^{'}$ agreeing with $s$ off $x$ ;
$M ⊨ \forall x ϕ [s]$ iff $M ⊨ ϕ [s^{'}]$ for every such $s^{'}$ .

The value of $M ⊨ ϕ [s]$ depends on $s$ only through its values on the free variables of $ϕ$ — an easy induction. A sentence has no free variables, so for sentences we drop $s$ and write $M ⊨ ϕ$ . A theory $T$ is a set of sentences; $M ⊨ T$ means $M$ satisfies every member, and then $M$ is a model of $T$ . We write $T ⊨ ϕ$ when every model of $T$ satisfies $ϕ$ , and $Th (M)$ for the set of all sentences true in $M$ — the complete theory of $M$ .

Intuition. A signature is a list of names with no meanings attached. A structure hands out the meanings: here is the set of things we are talking about, here is what " $+$ " does to two of them, here is which pairs count as " $<$ ". Satisfaction is then nothing more than reading a sentence aloud with those meanings substituted and checking whether what you said is true.

Structures over the same signature are compared by maps that respect the interpretations.

Definition 5.3 (Homomorphism, embedding, isomorphism). Let $M, N$ be $L$ -structures. A homomorphism $h : M \to N$ is a function $h : M \to N$ with

h (c^{M}) = c^{N}, h (f^{M} (a_{1}, \dots, a_{n})) = f^{N} (h (a_{1}), \dots, h (a_{n})),

and $(a_{1}, \dots, a_{n}) \in R^{M} \Rightarrow (h (a_{1}), \dots, h (a_{n})) \in R^{N}$ for every relation symbol $R$ .

It is an embedding if moreover $h$ is injective and the relational condition holds in both directions:

(a_{1}, \dots, a_{n}) \in R^{M} ⟺ (h (a_{1}), \dots, h (a_{n})) \in R^{N} .

An isomorphism is a surjective embedding; $M ≅ N$ means one exists.

The one-directional relational clause is what separates a homomorphism from an embedding, and the separation is real: the identity map from $(Z, R)$ with $R$ interpreted as the empty relation into $(Z, <)$ is a bijective homomorphism that is not an embedding, because it does not reflect the relation. Algebra usually escapes the distinction because groups, rings and fields have purely functional signatures, where an injective homomorphism is automatically an embedding.

Definition 5.4 (Substructure). $N$ is a substructure of $M$ , written $N \subseteq M$ , if $N \subseteq M$ , every $c^{M}$ lies in $N$ and equals $c^{N}$ , each $f^{N}$ is the restriction of $f^{M}$ to $N^{n}$ (so $N$ must be closed under $f^{M}$ ), and each $R^{N} = R^{M} \cap N^{n}$ .

Substructures and embeddings are two views of one notion: $h : M \to N$ is an embedding exactly when it is an isomorphism onto a substructure of $N$ . The next lemma records precisely which formulas a substructure inherits, and it is the reason "substructure" is a far weaker relation than it looks.

Lemma 5.5 (Embeddings preserve quantifier-free formulas). Let $h : M \to N$ be an embedding and $ϕ (x_{1}, \dots, x_{n})$ a quantifier-free formula. Then for all $a_{1}, \dots, a_{n} \in M$ ,

M ⊨ ϕ [a_{1}, \dots, a_{n}] ⟺ N ⊨ ϕ [h (a_{1}), \dots, h (a_{n})] .

Proof. First, terms: induction on $t$ gives $h (t^{M} [a]) = t^{N} [h (a)]$ . For a variable this is trivial, for a constant it is the clause $h (c^{M}) = c^{N}$ , and for $f (t_{1}, \dots, t_{k})$ it is the function clause applied to the inductive hypotheses.

Now induct on $ϕ$ . If $ϕ$ is $t_{1} = t_{2}$ , then $M ⊨ ϕ [a]$ says $t_{1}^{M} [a] = t_{2}^{M} [a]$ ; applying $h$ and the term identity gives $t_{1}^{N} [h (a)] = t_{2}^{N} [h (a)]$ , and injectivity of $h$ gives the converse direction. If $ϕ$ is $R (t_{1}, \dots, t_{k})$ , the two-directional relational clause is exactly what is needed. The Boolean cases are immediate, since a biconditional is preserved by negation and conjunction. There is no quantifier case, which is the whole point: the argument collapses the moment a quantifier appears, because a witness in $N$ need not lie in the image of $h$ .∎

Example 5.6 (Counting structures on a fixed domain). How many distinct $L$ -structures are there on the fixed three-element domain $M = {0, 1, 2}$ , where $L$ has one constant symbol $c$ , one unary function symbol $f$ and one binary relation symbol $R$ ?

Solution. A structure is exactly a choice of interpretation for each symbol, and the choices are independent, so count each and multiply.

Step 1 (the constant). $c^{M}$ is any element of $M$ : $3$ choices.

Step 2 (the function). $f^{M}$ is any map $M \to M$ : $3^{3} = 27$ choices.

Step 3 (the relation). $R^{M}$ is any subset of $M^{2}$ , a nine-element set: $2^{9} = 512$ choices.

Step 4 (multiply). $3 \cdot 27 \cdot 512 = 41472$ .

Sanity check: dropping $R$ leaves $3 \cdot 27 = 81$ structures, and each of those is refined by one of $512$ relations, reproducing the same total. This counts labelled structures on a fixed domain, not isomorphism types — of the latter there are far fewer.□

Example 5.7 (Evaluating satisfaction step by step). Let $M$ have domain ${0, 1, 2}$ , constant $c^{M} = 0$ , and unary $S^{M}$ the successor modulo $3$ . Does $M ⊨ \forall x (S (S (S (x))) = x)$ ?

Solution. Step 1 (unfold the quantifier). By the clause for $\forall$ , the sentence holds iff $M ⊨ (S (S (S (x))) = x) [b]$ for every $b \in {0, 1, 2}$ .

Step 2 (evaluate the term). Applying $S^{M}$ three times cycles all the way around: $0 \to 1 \to 2 \to 0$ , $1 \to 2 \to 0 \to 1$ , $2 \to 0 \to 1 \to 2$ . In each case the value returns to $b$ .

Step 3 (check the atomic formula). The atomic clause for $=$ asks whether both sides denote the same element, which Step 2 confirms for all three $b$ . Hence $M ⊨ \forall x (S (S (S (x))) = x)$ .

The same sentence is false in $(N, S)$ , where the successor function is injective but not surjective. Satisfaction is a relation between a sentence and a world, never a property of the sentence alone.□

Pitfall. " $N \subseteq M$ " constrains the atomic data only, and by Lemma Embeddings preserve quantifier-free formulas that is exactly as far as the guarantee reaches. $(Z, +, \cdot)$ is a substructure of $(Q, +, \cdot)$ , yet "every non-zero element has a multiplicative inverse" is false in the first and true in the second.

Notation. $M, N$ denote structures and the matching italic letters $M, N$ their domains. $L_{M}$ denotes $L$ enlarged by a fresh constant symbol $\underline{a}$ for every $a \in M$ , and $M$ is read as an $L_{M}$ -structure by interpreting $\underline{a}$ as $a$ . This device — naming the elements — is used constantly from the next section onward. The atomic diagram $Diag (M)$ is the set of atomic and negated atomic $L_{M}$ -sentences true in $M$ ; the elementary diagram $Diag_{el} (M)$ is the set of all $L_{M}$ -sentences true in $M$ .

Exercises for §5.1 →

5.2Elementary Equivalence and Elementary Substructures

Isomorphism is the strongest comparison between structures and is usually out of reach; first-order logic offers a coarser one that is often exactly the right granularity.

Definition 5.8 (Elementary equivalence). Structures $M$ and $N$ are elementarily equivalent, written $M \equiv N$ , if they satisfy exactly the same $L$ -sentences:

M \equiv N iff for every sentence ϕ, M ⊨ ϕ ⟺ N ⊨ ϕ,

equivalently $Th (M) = Th (N)$ .

Proposition 5.9 (Isomorphism implies elementary equivalence). If $M ≅ N$ then $M \equiv N$ .

Proof. Let $h$ be an isomorphism. Extend Lemma Embeddings preserve quantifier-free formulas by induction through the quantifiers, which is now legitimate because $h$ is onto. For $\exists x ψ$ : if $M ⊨ \exists x ψ [a]$ with witness $b \in M$ , then by the induction hypothesis $N ⊨ ψ [h (b), h (a)]$ , so $N ⊨ \exists x ψ [h (a)]$ . Conversely a witness $d \in N$ is $h (b)$ for some $b \in M$ by surjectivity, and the induction hypothesis pulls it back. The universal case is the same argument, or the existential one applied to $\neg ψ$ . Taking $ϕ$ a sentence gives the claim.∎

The converse fails badly, and the failure is the engine of the whole subject: first-order logic cannot see cardinality.

Example 5.10 (Elementary equivalence without isomorphism). Show that $(Q, <)$ and $(R, <)$ are elementarily equivalent but not isomorphic, in the language with the single binary symbol $<$ .

Solution. Step 1 (no isomorphism). An isomorphism is in particular a bijection of domains, and $Q$ is countable while $R$ is not. So none exists.

Step 2 (both are models of DLO). Each is a linear order; between any two elements lies a third, namely $\frac{p + q}{2}$ ; and neither has a least or a greatest element. These are exactly the axioms of DLO, the theory of dense linear orders without endpoints.

Step 3 (DLO is complete). The section Categoricity and Quantifier Elimination proves DLO is $ℵ_{0}$ -categorical and deduces completeness from Vaught's test. A complete theory decides every sentence, so any two of its models agree on every sentence.

Conclusion. $(Q, <) \equiv (R, <)$ while $(Q, <) \neq ≅ (R, <)$ . The cardinality gap is invisible to first-order sentences over $<$ .□

Inside a fixed $M$ the corresponding refinement of "substructure" is the central notion of the chapter.

Definition 5.11 (Elementary substructure). A substructure $N \subseteq M$ is an elementary substructure, written $N ⪯ M$ , if for every formula $ϕ (x_{1}, \dots, x_{n})$ and every tuple $a$ from $N$ ,

N ⊨ ϕ [a] ⟺ M ⊨ ϕ [a] .

An embedding $h : N \to M$ whose image is an elementary substructure is an elementary embedding.

Note the quantifier order. Elementary equivalence compares two structures on sentences; elementary substructure demands agreement on all formulas with parameters from the small structure. The second is strictly stronger than $N \subseteq M$ together with $N \equiv M$ : there are structures $N \subseteq M$ with $N ≅ M$ , hence $N \equiv M$ , and still $N \neq ⪯ M$ — for instance $(2 Z, <) \subseteq (Z, <)$ , which is isomorphic to the whole but omits the element $1$ lying strictly between the parameters $0$ and $2$ .

Verifying the definition directly means checking infinitely many formulas of unbounded quantifier depth. The following test reduces the work to a single quantifier alternation, and is the workhorse behind every construction in the next two sections.

Theorem 5.12 (Tarski–Vaught test). Let $N \subseteq M$ be a substructure. Then $N ⪯ M$ if and only if:

for every formula $ψ (x, y)$ and every tuple $a$ from $N$ , if there is $b \in M$ with $M ⊨ ψ [b, a]$ , then there is $b^{'} \in N$ with $M ⊨ ψ [b^{'}, a]$ .

Proof. ( $\Rightarrow$ ) Suppose $N ⪯ M$ and $M ⊨ ψ [b, a]$ for some $b \in M$ . Then $M ⊨ \exists x ψ [a]$ , so by elementarity $N ⊨ \exists x ψ [a]$ , giving some $b^{'} \in N$ with $N ⊨ ψ [b^{'}, a]$ ; elementarity again lifts this to $M ⊨ ψ [b^{'}, a]$ .

( $\Leftarrow$ ) Assume the condition and prove $N ⊨ ϕ [a] ⟺ M ⊨ ϕ [a]$ by induction on $ϕ$ .

Atomic. This is the substructure hypothesis: constants, functions and relations agree by restriction, so Lemma Embeddings preserve quantifier-free formulas applies to the inclusion embedding.

Negation. If the equivalence holds for $ϕ$ , negating both sides preserves it.

Conjunction. $N ⊨ (ϕ_{1} \land ϕ_{2}) [a]$ iff both conjuncts hold in $N$ , iff (induction) both hold in $M$ , iff $M ⊨ (ϕ_{1} \land ϕ_{2}) [a]$ . The other connectives are definable from $\neg, \land$ .

Existential. Let $ϕ = \exists x ψ (x, y)$ with $a$ from $N$ . If $N ⊨ ϕ [a]$ , take $b^{'} \in N$ with $N ⊨ ψ [b^{'}, a]$ ; the induction hypothesis for $ψ$ — applicable since $b^{'}$ and $a$ all lie in $N$ — gives $M ⊨ ψ [b^{'}, a]$ , so $M ⊨ ϕ [a]$ . Conversely, if $M ⊨ ϕ [a]$ there is $b \in M$ with $M ⊨ ψ [b, a]$ ; the test supplies $b^{'} \in N$ with $M ⊨ ψ [b^{'}, a]$ , and the induction hypothesis converts this to $N ⊨ ψ [b^{'}, a]$ , whence $N ⊨ ϕ [a]$ .

Since $\forall x ψ$ is $\neg\exists x \neg ψ$ , the universal case is covered. This completes the induction, so $N ⪯ M$ .∎

Intuition. Read the test as: $N$ never has to leave home. Whenever the big structure can satisfy an existential demand using parameters $N$ already owns, $N$ owns a witness too. If that is true for every demand, $N$ can simulate $M$ 's entire first-order reasoning internally, and the two agree on everything expressible.

Example 5.13 (A substructure that is not elementary). Show $(Z, <) \neq ⪯ (Q, <)$ , using the Tarski–Vaught test.

Solution. Step 1 (it is a substructure). $Z \subseteq Q$ , the language has no constants or function symbols, and $<^{Z}$ is the restriction of $<^{Q}$ . So the inclusion is a substructure.

Step 2 (produce a failing witness demand). Take $ψ (x, y_{1}, y_{2})$ to be $y_{1} < x \land x < y_{2}$ and the parameters $a_{1} = 0$ , $a_{2} = 1$ , both in $Z$ . In $Q$ the element $b = \frac{1}{2}$ satisfies $Q ⊨ ψ [b, 0, 1]$ .

Step 3 (no witness at home). No integer lies strictly between $0$ and $1$ , so no $b^{'} \in Z$ satisfies $ψ [b^{'}, 0, 1]$ . The test fails, hence $(Z, <) \neq ⪯ (Q, <)$ .

Step 4 (in fact they are not even elementarily equivalent). The density sentence $\forall y_{1} \forall y_{2} (y_{1} < y_{2} \to \exists x (y_{1} < x \land x < y_{2}))$ is true in $Q$ and false in $Z$ , so $(Z, <) \neq \equiv (Q, <)$ .□

Figure 5.14. The Tarski–Vaught failure for

(Z, <) \subseteq (Q, <)

. The parameters

0

and

1

lie in the substructure, but the only witnesses to

0 < x < 1

— the shaded rational gap, with

1/2

marked — lie outside it.

Pitfall. $N \equiv M$ together with $N \subseteq M$ does not give $N ⪯ M$ , as $(2 Z, <) \subseteq (Z, <)$ shows. Elementary equivalence quantifies over sentences with no parameters; elementary substructure demands agreement on formulas with parameters, which is a strictly stronger requirement.

Example 5.15 (A substructure that is elementary). Show that $(Q, <) ⪯ (R, <)$ .

Solution. Step 1 (it is a substructure). $Q \subseteq R$ and the order is inherited; there is nothing to close under.

Step 2 (reduce the witness demand to inequalities). Let $ψ (x, y)$ be any formula and $a$ a tuple of rationals, and suppose some real $b$ has $R ⊨ ψ [b, a]$ . By quantifier elimination for DLO — proved in the section Categoricity and Quantifier Elimination — $ψ$ is equivalent over $R$ to a quantifier-free formula, that is a Boolean combination of the atomic statements $x < a_{i}$ , $a_{i} < x$ and $x = a_{i}$ .

Step 3 (describe the solution set). A Boolean combination of those conditions defines a set that is a finite union of the points $a_{i}$ and of open intervals whose endpoints lie in $a$ or are $\pm \infty$ . It is non-empty, since $b$ belongs to it.

Step 4 (find a rational in it). A point $a_{i}$ is already rational. A non-empty open interval with rational or infinite endpoints contains a rational, by density of $Q$ in $R$ . Either way there is a rational witness $b^{'}$ with $R ⊨ ψ [b^{'}, a]$ .

Step 5 (apply the test). Theorem Tarski–Vaught test now gives $(Q, <) ⪯ (R, <)$ — a strictly stronger statement than the elementary equivalence established above, and the reason $Q$ may be used as a "small copy" of $R$ for any question expressible in the order alone.□

Exercises for §5.2 →

5.3Löwenheim–Skolem: Shrinking and Growing Models

The Tarski–Vaught test does more than diagnose; run as a construction, it builds elementary substructures to order. Given $M$ and any subset $A \subseteq M$ , close $A$ under witnesses for every existential demand, repeat countably many times, and the union satisfies the test automatically. Controlling the cardinality of the result is what makes the theorem sharp.

Definition 5.16 (Skolem function). Fix a well-ordering of $M$ . For each formula $ψ (x, y)$ with $y$ of length $n$ , define $F_{ψ} : M^{n} \to M$ by: $F_{ψ} (a)$ is the $<$ -least $b \in M$ with $M ⊨ ψ [b, a]$ if any exists, and the $<$ -least element of $M$ otherwise. These are the Skolem functions of $M$ .

Theorem 5.17 (Downward Löwenheim–Skolem). Let $M$ be an $L$ -structure and $A \subseteq M$ . Then there is $N ⪯ M$ with $A \subseteq N$ and

∣ N ∣ \leq ∣ A ∣ + ∣ L ∣ + ℵ_{0} .

In particular, if $L$ is countable, every structure has a countable elementary substructure containing any prescribed countable set.

Proof. Write $κ = ∣ A ∣ + ∣ L ∣ + ℵ_{0}$ . There are exactly $∣ L ∣ + ℵ_{0} \leq κ$ formulas, hence at most $κ$ Skolem functions $F_{ψ}$ .

Set $A_{0} = A \cup {c^{M} : c \in L}$ if $A$ is empty, and $A_{0} = A$ otherwise, so $A_{0} \neq = \emptyset$ and $∣ A_{0} ∣ \leq κ$ . Define recursively

A_{k + 1} = A_{k} \cup {F_{ψ} (a) : ψ a formula, a a tuple from A_{k}},

and put $N = ⋃_{k < ω} A_{k}$ .

Cardinality. If $∣ A_{k} ∣ \leq κ$ then the set of tuples from $A_{k}$ has size at most $κ$ , and there are at most $κ$ Skolem functions, so at most $κ \cdot κ = κ$ new elements appear; hence $∣ A_{k + 1} ∣ \leq κ$ . A countable union of sets of size at most $κ$ has size at most $ℵ_{0} \cdot κ = κ$ , so $∣ N ∣ \leq κ$ , and $A \subseteq N$ by construction.

$N$ carries a substructure. For a function symbol $f$ and $a$ from $N$ , all of $a$ lies in some single $A_{k}$ (the chain is increasing and $a$ is finite). Taking $ψ (x, y)$ to be $x = f (y)$ , the value $F_{ψ} (a) = f^{M} (a)$ lands in $A_{k + 1} \subseteq N$ . Constants are handled by $ψ (x)$ equal to $x = c$ . So $N$ is closed, and we give it the induced structure $N$ .

Tarski–Vaught. Let $ψ (x, y)$ be a formula, $a$ a tuple from $N$ , and suppose some $b \in M$ has $M ⊨ ψ [b, a]$ . Again $a$ lies in some $A_{k}$ , so $F_{ψ} (a) \in A_{k + 1} \subseteq N$ , and since a witness exists, $F_{ψ} (a)$ is one. The test is met, so by Theorem Tarski–Vaught test, $N ⪯ M$ .∎

Note where the axiom of choice enters: the well-ordering of $M$ used to define the Skolem functions. Without choice one selects witnesses ad hoc and the theorem becomes delicate.

The other direction grows models instead, and its proof runs through compactness — stated in the next section and proved in the one after that, so no circularity arises.

Theorem 5.18 (Upward Löwenheim–Skolem). Let $M$ be an infinite $L$ -structure and let $κ \geq ∣ M ∣ + ∣ L ∣ + ℵ_{0}$ . Then there is $N$ of cardinality exactly $κ$ with $M ⪯ N$ (more precisely, with an elementary embedding of $M$ into $N$ ).

Proof. Work in the language $L_{M}$ with a constant $\underline{a}$ for each $a \in M$ , and add $κ$ further fresh constants ${d_{i} : i < κ}$ . Let

T = Diag_{el} (M) \cup {\neg (d_{i} = d_{j}) : i \neq = j < κ} .

Every finite subset of $T$ has a model. A finite subset mentions only finitely many of the $d_{i}$ , say $d_{i_{1}}, \dots, d_{i_{n}}$ . Interpret those as $n$ distinct elements of $M$ — possible because $M$ is infinite — and interpret each $\underline{a}$ as $a$ . The resulting expansion of $M$ satisfies the elementary diagram (it is $M$ ) and the finitely many inequations.

Apply compactness. By Theorem Compactness, $T$ has a model $N_{0}$ . The map $a \mapsto \underline{a}^{N_{0}}$ is an elementary embedding of $M$ into the $L$ -reduct, precisely because $N_{0}$ satisfies every sentence of the elementary diagram, and it is injective because $Diag_{el} (M)$ contains $\neg (\underline{a} = \underline{b})$ for distinct $a, b$ . The $κ$ constants $d_{i}$ are pairwise distinct, so $∣ N_{0} ∣ \geq κ$ .

Trim to size exactly $κ$ . The language $L_{M} \cup {d_{i}}$ has cardinality at most $∣ L ∣ + ∣ M ∣ + κ = κ$ . Apply Theorem Downward Löwenheim–Skolem inside $N_{0}$ to the subset $A = {\underline{a}^{N_{0}} : a \in M} \cup {d_{i}^{N_{0}} : i < κ}$ , of size $κ$ : it yields $N ⪯ N_{0}$ containing $A$ with $∣ N ∣ \leq κ + κ = κ$ , and $∣ N ∣ \geq κ$ since $A \subseteq N$ . So $∣ N ∣ = κ$ , and composing the two elementary maps embeds $M$ elementarily into $N$ .∎

Corollary 5.19 (No infinite structure is determined up to isomorphism). If a theory $T$ in a countable language has an infinite model, it has models of every infinite cardinality $κ \geq ℵ_{0}$ , and hence models that are elementarily equivalent but not isomorphic.

Proof. Downward Löwenheim–Skolem gives a countable model; upward gives one of each larger size. Structures of different cardinality cannot be isomorphic, yet all are models of the complete theory of the original, so all are elementarily equivalent to it.∎

Example 5.20 (The Skolem paradox). ZFC proves the existence of uncountable sets. If ZFC is consistent, it has a countable model $M$ . How can a countable $M$ contain an element it believes to be uncountable?

Solution. Step 1 (both halves are genuine). If ZFC is consistent it has a model, and its language is countable, so Theorem Downward Löwenheim–Skolem yields a countable elementary substructure — a countable $M ⊨ ZFC$ . Meanwhile ZFC proves $\exists x (" x is uncountable")$ , so there is $u \in M$ with $M ⊨$ " $u$ is uncountable".

Step 2 (unfold what "uncountable" says). " $u$ is uncountable" is the sentence: there is no bijection between $u$ and $ω$ . That is a statement quantifying over the elements of $M$ only. So $M$ asserts that no member of $M$ codes such a bijection.

Step 3 (the bijection lives outside). The set ${v \in M : M ⊨ v \in u}$ is a subset of the countable set $M$ , hence countable in the real world, so a bijection with $ω$ exists externally. It is simply not an element of $M$ . The model is missing the very function that would refute it.

Step 4 (diagnosis). "Uncountable" is not an absolute property; it is relative to which functions a model possesses. The paradox dissolves once one notices that $M$ 's quantifiers range over $M$ , not over the universe. Nothing is contradictory: $u$ is uncountable in $M$ and countable outside it.□

Pitfall. The Skolem paradox is often misread as "Löwenheim–Skolem refutes Cantor's theorem". It does not. Cantor's theorem holds inside every model of ZFC — the model contains no surjection from $u$ onto its power set. What varies between models is which external functions have been admitted as elements, and first-order set theory cannot say "all functions", only "all functions that are elements of me".

Intuition. Downward Löwenheim–Skolem is a closure argument: keep throwing in one witness per existential demand until nothing new is demanded. Upward Löwenheim–Skolem is a padding argument: ask for $κ$ pairwise distinct new constants, note that each finite portion of the demand is satisfiable inside the old infinite model, and let compactness grant the whole demand at once.

Exercises for §5.3 →

5.4Compactness and What It Builds

Theorem 5.21 (Compactness). A set of first-order sentences $T$ has a model if and only if every finite subset of $T$ has a model.

The left-to-right direction is trivial: a model of $T$ is a model of each subset. The content is the converse, and this chapter proves it twice — once from ultraproducts in the section Filters, Ultraproducts and Łoś's Theorem, and once from the Henkin construction in The Completeness Theorem Revisited. Until then it is used as a stated theorem, not assumed silently.

Intuition. Read compactness as a finiteness of evidence principle. A proof is a finite object, so it can only appeal to finitely many axioms; therefore an inconsistency, if one exists, is already visible in a finite subtheory. Contrapositively, if no finite subtheory is inconsistent, the whole theory is satisfiable. That is exactly why a compactness argument can grant infinitely many demands at once: nothing can go wrong globally that was not already wrong locally.

The standard use is a two-step template: to build a model with a strange property, write down a theory whose models must have it, then verify finite satisfiability inside an ordinary structure.

Theorem 5.22 (Non-standard models of arithmetic). Let $Th (N)$ be the complete theory of the standard model $(N, 0, S, +, \cdot, <)$ — true arithmetic. Then there is a model $N ⊨ Th (N)$ containing an element larger than every standard natural number. Hence $N \equiv N$ but $N \neq ≅ N$ .

Proof. Add one fresh constant $c$ and set

T = Th (N) \cup {\underline{n} < c : n \in N},

where $\underline{n}$ is the numeral $S (S (\dots S (0)))$ with $n$ occurrences of $S$ .

A finite subset $T_{0} \subseteq T$ mentions only finitely many numerals, so there is a largest $n_{0}$ with $\underline{n_{0}} < c$ in $T_{0}$ . Interpret $c$ as $n_{0} + 1$ in the standard model: every sentence of $Th (N)$ is true there, and each of the finitely many inequations holds. So $T_{0}$ has a model.

By Theorem Compactness, $T$ has a model $N$ . Its interpretation $c^{N}$ exceeds every $\underline{n}^{N}$ , so it is not equal to any numeral value and $N$ is not isomorphic to $N$ (in $N$ , every element is a numeral value). But $N ⊨ Th (N)$ , so it satisfies exactly the same sentences as $N$ .∎

Every non-standard $N$ has a rigid shape. Its standard part — the numeral values — forms an initial copy of $N$ . Above it, each non-standard element $a$ has a predecessor and a successor, all still non-standard, so the non-standard elements fall into $Z$ -shaped blocks. The blocks are densely ordered without endpoints, since between blocks $[a]$ and $[b]$ with $a$ far below $b$ lies the block of $⌊(a + b) /2 ⌋$ . For a countable $N$ the block order is a countable DLO, hence a copy of $Q$ : the order type is $N + Z \cdot Q$ .

Figure 5.23. The order type of a countable non-standard model of arithmetic: an initial copy of

N

, then

Z

-shaped blocks of non-standard elements ordered like

Q

. No block is first, and between any two blocks lies another.

Theorem 5.24 (Arbitrarily large finite models give an infinite model). If a theory $T$ has finite models of unboundedly large size, then $T$ has an infinite model. Consequently, the class of finite structures is not the class of models of any first-order theory, and "finite" is not first-order expressible.

Proof. For each $n \geq 2$ let $λ_{n}$ be the sentence "there exist at least $n$ distinct elements", namely $\exists x_{1} \dots \exists x_{n} ⋀_{i < j} \neg (x_{i} = x_{j})$ . Put $T^{'} = T \cup {λ_{n} : n \geq 2}$ .

A finite subset of $T^{'}$ contains finitely many $λ_{n}$ , with a largest index $n_{0}$ . By hypothesis $T$ has a model with at least $n_{0}$ elements, and that model satisfies $λ_{2}, \dots, λ_{n_{0}}$ . So every finite subset of $T^{'}$ is satisfiable, and Theorem Compactness gives a model of $T^{'}$ . It satisfies every $λ_{n}$ , so it is infinite, and it models $T$ .

For the consequence: if some theory had exactly the finite structures as models, it would have arbitrarily large finite models and therefore an infinite one, a contradiction.∎

The same template yields non-standard analysis. Adjoin a constant $ϵ$ to the complete theory of the ordered field $R$ with a symbol for every real, together with ${0 < ϵ} \cup {ϵ < \underline{1/ n} : n \geq 1}$ . Every finite subset is satisfiable in $R$ itself by choosing $ϵ$ small enough, so compactness delivers an ordered field elementarily equivalent to $R$ containing a positive infinitesimal.

Definition 5.25 (Order indiscernibles). Let $M$ be a structure and $(I, <)$ a linear order. A family $(a_{i})_{i \in I}$ of elements of $M$ is a set of order indiscernibles if for every formula $ϕ (x_{1}, \dots, x_{n})$ and all increasing tuples $i_{1} < \dots < i_{n}$ and $j_{1} < \dots < j_{n}$ from $I$ ,

M ⊨ ϕ [a_{i_{1}}, \dots, a_{i_{n}}] ⟺ M ⊨ ϕ [a_{j_{1}}, \dots, a_{j_{n}}] .

That is, the truth of a formula depends only on the relative order of the arguments, not on which elements were chosen.

Theorem 5.26 (Ehrenfeucht–Mostowski: existence of indiscernibles). Every theory with an infinite model has, for each linear order $(I, <)$ , a model containing a set of order indiscernibles indexed by $I$ .

Proof (Sketch). This is a sketch; it rests on two results proved elsewhere — Ramsey's theorem for $n$ -tuples (see the combinatorics chapter) and Theorem Compactness.

Take $T$ with an infinite model. Add constants ${d_{i} : i \in I}$ and let

T^{'} = T \cup {\neg (d_{i} = d_{j}) : i \neq = j} \cup {ϕ (d_{i_{1}}, \dots, d_{i_{n}}) \leftrightarrow ϕ (d_{j_{1}}, \dots, d_{j_{n}})},

the last family taken over all formulas $ϕ$ and all pairs of increasing tuples. By compactness it suffices to model each finite subset $T_{0}$ , which mentions finitely many formulas $ϕ_{1}, \dots, ϕ_{m}$ , each of arity at most $n$ , and finitely many constants — say $N$ of them.

Inside an infinite model $M ⊨ T$ , colour each increasing $n$ -tuple from an infinite subset by the tuple of truth values of $ϕ_{1}, \dots, ϕ_{m}$ on it: finitely many colours, namely $2^{m}$ . Ramsey's theorem yields an infinite monochromatic set $H$ : on increasing $n$ -tuples from $H$ , every $ϕ_{k}$ has constant truth value. Interpreting the $N$ constants as increasing elements of $H$ models $T_{0}$ .

Compactness then gives a model of $T^{'}$ , in which the interpretations of the $d_{i}$ are indiscernible by construction.∎

Example 5.27 (Compactness fails for second-order logic). Show that the compactness theorem is genuinely a first-order phenomenon by exhibiting a second-order theory each of whose finite subsets is satisfiable, but which has no model.

Solution. Step 1 (second-order logic can say "finite"). In second-order logic one can write a sentence $σ$ asserting the Dedekind-finiteness of the universe: every injective function from the universe to itself is surjective. This quantifies over functions, so it is not first-order.

Step 2 (build the theory). Let $T = {σ} \cup {λ_{n} : n \geq 2}$ with $λ_{n}$ as in Theorem Arbitrarily large finite models give an infinite model.

Step 3 (finite subsets are satisfiable). A finite subset involves $λ_{2}, \dots, λ_{n_{0}}$ at most; any finite set of size $n_{0}$ satisfies those and is Dedekind-finite, so it models the subset.

Step 4 (the whole theory is not). A model of all the $λ_{n}$ is infinite, and an infinite set admits an injective non-surjective self-map, contradicting $σ$ . So $T$ has no model, and compactness fails.

This also re-proves that $σ$ cannot be first-order expressible: if it were, Theorem Compactness would be contradicted.□

Exercises for §5.4 →

5.5Filters, Ultraproducts and Łoś's Theorem

Compactness produced models by a soft existence argument. Ultraproducts produce them explicitly: they take a family of structures and a notion of "large index set", and build one structure whose truths are the truths holding on large sets of coordinates. The notion of largeness is what a filter formalises.

Definition 5.28 (Filter and ultrafilter). A filter on a non-empty set $I$ is a family $F$ of subsets of $I$ such that $I \in F$ , $\emptyset \in / F$ , $F$ is closed under finite intersections, and $F$ is closed upward ( $A \in F$ and $A \subseteq B \subseteq I$ imply $B \in F$ ).

An ultrafilter is a filter $U$ with the maximality property

for every A \subseteq I, A \in U or I ∖ A \in U .

Since $\emptyset \in / U$ and $U$ is closed under intersection, exactly one of the two holds.

$U$ is principal if $U = {A \subseteq I : i_{0} \in A}$ for some fixed $i_{0} \in I$ , and non-principal otherwise.

Proposition 5.29 (Non-principal ultrafilters contain the cofinite sets). An ultrafilter $U$ on $I$ is non-principal if and only if it contains no finite set. In that case $U$ contains every cofinite subset of $I$ .

Proof. If $U$ contains a finite set, take one of least size, $A = {i_{1}, \dots, i_{k}}$ . For each $j$ , either ${i_{j}} \in U$ or its complement is. If some ${i_{j}} \in U$ , then upward closure makes $U$ principal at $i_{j}$ . Otherwise every complement $I ∖ {i_{j}}$ is in $U$ , and intersecting all $k$ of them with $A$ gives $\emptyset \in U$ , a contradiction. So a non-principal $U$ contains no finite set; and conversely a principal $U$ contains the singleton ${i_{0}}$ .

If $A$ is cofinite then $I ∖ A$ is finite, hence not in $U$ , hence $A \in U$ by maximality.∎

Theorem 5.30 (Ultrafilter lemma). Every filter on $I$ extends to an ultrafilter on $I$ . In particular, on an infinite $I$ the Fréchet filter of cofinite sets extends to a non-principal ultrafilter.

Proof. Order the filters on $I$ extending the given $F$ by inclusion. The union of a chain of such filters is again a filter — closure under finite intersection involves only two members, which lie in a common link of the chain, and $\emptyset$ is in no link. So Zorn's lemma gives a maximal filter $U \supseteq F$ .

Maximality gives the ultrafilter property. Suppose $A \in / U$ and $I ∖ A \in / U$ . If $A \cap B \neq = \emptyset$ for every $B \in U$ , then ${C : C \supseteq A \cap B for some B \in U}$ is a filter properly containing $U$ , contradicting maximality. So $A \cap B = \emptyset$ for some $B \in U$ , i.e. $B \subseteq I ∖ A$ , whence $I ∖ A \in U$ by upward closure — a contradiction. Applying this to the Fréchet filter on an infinite $I$ yields an ultrafilter containing all cofinite sets, hence non-principal by Proposition Non-principal ultrafilters contain the cofinite sets.∎

Pitfall. The ultrafilter lemma is a genuine use of choice: it is not provable in ZF alone. No non-principal ultrafilter on $N$ can be exhibited by an explicit rule, so "take a non-principal $U$ " is always an appeal to Zorn's lemma, never a construction.

Definition 5.31 (Ultraproduct and ultrapower). Let ${M_{i}}_{i \in I}$ be $L$ -structures and $U$ an ultrafilter on $I$ . On the Cartesian product $\prod_{i} M_{i}$ define

(a_{i}) \sim_{U} (b_{i}) iff {i \in I : a_{i} = b_{i}} \in U .

This is an equivalence relation, by the filter axioms. The ultraproduct $\prod_{U} M_{i}$ has domain the set of classes $[a] = [(a_{i})]$ , with

c^{\prod_{U} M_{i}} = [(c^{M_{i}})], f ([a^{1}], \dots, [a^{n}]) = [(f^{M_{i}} (a_{i}^{1}, \dots, a_{i}^{n}))],

([a^{1}], \dots, [a^{n}]) \in R iff {i : (a_{i}^{1}, \dots, a_{i}^{n}) \in R^{M_{i}}} \in U .

When all $M_{i}$ are the same $M$ , the result is the ultrapower $M^{I} / U$ .

The definitions are well posed: if $(a_{i}) \sim_{U} (a_{i}^{'})$ then the agreement sets intersect, and a finite intersection of $U$ -sets is in $U$ , so the value of a function or the truth of a relation does not depend on the representatives chosen.

Theorem 5.32 (Łoś's theorem). For every formula $ϕ (x_{1}, \dots, x_{n})$ and all classes $[a^{1}], \dots, [a^{n}]$ in the ultraproduct,

U \prod M_{i} ⊨ ϕ [[a^{1}], \dots, [a^{n}]] iff {i \in I : M_{i} ⊨ ϕ [a_{i}^{1}, \dots, a_{i}^{n}]} \in U .

In particular, a sentence holds in the ultraproduct exactly when it holds in $U$ -almost all factors.

Proof. Induction on $ϕ$ . Write $[[ϕ (a)]]$ for the index set on the right.

Atomic. A term induction shows $t^{\prod_{U}} [[a]] = [(t^{M_{i}} [a_{i}])]$ , using the coordinatewise definition of the functions. The clauses for $=$ and $R$ then read off the definition of $\sim_{U}$ and of $R$ in the ultraproduct, which are stated exactly as membership of the relevant index set in $U$ .

Negation. By the induction hypothesis, $\prod_{U} ⊨ \neg ϕ$ iff $[[ϕ]] \in / U$ , and by the ultrafilter property this holds iff $I ∖ [[ϕ]] \in U$ ; but $I ∖ [[ϕ]] = [[\neg ϕ]]$ . This is the only step using maximality of $U$ , and it is the step that fails for a general filter.

Conjunction. $[[ϕ \land ψ]] = [[ϕ]] \cap [[ψ]]$ . Closure under finite intersection gives one direction and upward closure the other.

Existential. Suppose $\prod_{U} ⊨ \exists x ψ [[a]]$ , witnessed by a class $[b]$ . By the induction hypothesis $[[ψ (b, a)]] \in U$ , and this set is contained in $[[\exists x ψ (a)]]$ , which is therefore in $U$ by upward closure.

Conversely let $J = [[\exists x ψ (a)]] \in U$ . For each $i \in J$ choose (axiom of choice) some $b_{i} \in M_{i}$ with $M_{i} ⊨ ψ [b_{i}, a_{i}]$ , and for $i \in / J$ let $b_{i}$ be arbitrary. Then $J \subseteq [[ψ (b, a)]]$ , so that set is in $U$ , and the induction hypothesis gives $\prod_{U} ⊨ ψ [[b], [a]]$ , hence $\prod_{U} ⊨ \exists x ψ [[a]]$ .

The universal quantifier is $\neg\exists\neg$ , already covered.∎

Corollary 5.33 (Ultrapowers are elementary extensions). The diagonal map $d : M \to M^{I} / U$ sending $a$ to the class of the constant sequence is an elementary embedding.

Proof. For a formula $ϕ$ and $a$ from $M$ , the index set $[[ϕ (a)]]$ is either all of $I$ (if $M ⊨ ϕ [a]$ ) or empty (if not). The first is in $U$ and the second is not, so Łoś's theorem gives $M^{I} / U ⊨ ϕ [d (a)]$ iff $M ⊨ ϕ [a]$ .∎

Theorem 5.34 (Compactness via ultraproducts). If every finite subset of a theory $T$ has a model, then $T$ has a model.

Proof. Let $I$ be the set of finite subsets of $T$ , and for each $i \in I$ pick a model $M_{i} ⊨ i$ . For $ϕ \in T$ put

\hat{ϕ} = {i \in I : ϕ \in i} .

The family ${\hat{ϕ} : ϕ \in T}$ has the finite intersection property: $\hat{ϕ_{1}} \cap \dots \cap \hat{ϕ_{n}}$ contains the index ${ϕ_{1}, \dots, ϕ_{n}}$ , so it is non-empty. Hence it generates a filter, which by Theorem Ultrafilter lemma extends to an ultrafilter $U$ on $I$ .

Fix $ϕ \in T$ . For every $i \in \hat{ϕ}$ we have $ϕ \in i$ and $M_{i} ⊨ i$ , so $M_{i} ⊨ ϕ$ . Thus $\hat{ϕ} \subseteq {i : M_{i} ⊨ ϕ}$ , and the latter is in $U$ by upward closure. By Theorem Łoś's theorem, $\prod_{U} M_{i} ⊨ ϕ$ . As $ϕ \in T$ was arbitrary, the ultraproduct models $T$ .∎

Intuition. An ultraproduct is a majority vote across infinitely many worlds, with the ultrafilter deciding which coalitions count as a majority. Maximality — $A$ or its complement, never both, never neither — is what makes the vote decide every question, which is why the new world is a structure at all and not a partial one.

Example 5.35 (Building an infinite natural number). Let $U$ be a non-principal ultrafilter on $N$ and form the ultrapower $N^{N} / U$ . Show that the class $α = [(0, 1, 2, 3, \dots)]$ of the identity sequence exceeds every standard natural number.

Solution. Step 1 (translate via Łoś). Write $\underline{n} = [(n, n, n, \dots)]$ for the diagonal image of $n$ . By Theorem Łoś's theorem, $N^{N} / U ⊨ \underline{n} < α$ iff ${i : n < i} \in U$ .

Step 2 (the index set is cofinite). ${i : i > n}$ omits only $0, 1, \dots, n$ , so it is cofinite.

Step 3 (apply non-principality). By Proposition Non-principal ultrafilters contain the cofinite sets, every cofinite set belongs to $U$ . Hence $\underline{n} < α$ for every standard $n$ .

Step 4 (and the ultrapower still satisfies true arithmetic). By Corollary Ultrapowers are elementary extensions, $N ⪯ N^{N} / U$ , so every sentence of $Th (N)$ survives. This is an explicit non-standard model — the same object Theorem Non-standard models of arithmetic produced abstractly, now written down.

Contrast with the principal case: if $U$ is generated by ${i_{0}}$ , Łoś reduces every formula to its truth at coordinate $i_{0}$ , the map $[a] \mapsto a_{i_{0}}$ is an isomorphism, and no new element appears.□

Example 5.36 (An ultraproduct of finite fields). What is the characteristic of $\prod_{U} F_{p_{i}}$ , where $p_{1} < p_{2} < \dots$ enumerates the primes and $U$ is non-principal on $N$ ?

Solution. Step 1 (each candidate characteristic is a sentence). For a fixed prime $q$ , "characteristic $q$ " is the sentence $χ_{q}$ saying $q 1 + \dots + 1 = 0$ .

Step 2 (count the large index sets). $F_{p_{i}} ⊨ χ_{q}$ only when $p_{i} = q$ , so $[[χ_{q}]]$ is a single index — a finite set, hence not in the non-principal $U$ .

Step 3 (apply Łoś). So $\prod_{U} F_{p_{i}} ⊨ \neg χ_{q}$ for every prime $q$ : the characteristic is $0$ .

Step 4 (what else survives). Every field axiom holds in every factor, so it holds in the ultraproduct: an infinite field of characteristic $0$ built entirely out of finite fields. Since each $F_{p_{i}}$ satisfies "every element has a $p$ -th root" only for its own $p$ , one must check sentence by sentence which properties transfer — that is exactly the content of Łoś's theorem, and it is the mechanism behind the Ax–Kochen transfer principles.□

Exercises for §5.5 →

5.6The Completeness Theorem Revisited

Compactness and Löwenheim–Skolem were semantic. The completeness theorem connects them to syntax: it says the proof system and the class of structures measure the same thing.

Theorem 5.37 (Model existence / completeness, semantic form). A theory $T$ is consistent — no derivation of a contradiction from $T$ exists — if and only if $T$ has a model. Equivalently, $T ⊢ ϕ$ if and only if $T ⊨ ϕ$ .

The easy half is soundness: every rule of the proof system preserves truth in a structure, so a model of $T$ cannot also model a derived contradiction. The hard half builds a model out of syntax itself, and the idea is Henkin's: let the domain consist of the closed terms of the language, so every element is literally named by a term. One obstacle stands in the way — a consistent theory may assert $\exists x ψ (x)$ while no term provably witnesses it — so the construction manufactures the missing names first.

Definition 5.38 (Henkin theory). A theory $T$ in a language $L$ is a Henkin theory if for every formula $ψ (x)$ with one free variable there is a constant $c_{ψ} \in L$ with

T ⊢ \exists x ψ (x) \to ψ (c_{ψ}) .

Such a $c_{ψ}$ is a witness constant for $ψ$ .

Method 5.39 (Henkin construction).

Add witnesses. For each formula $ψ (x)$ add a fresh constant $c_{ψ}$ and the Henkin axiom $\exists x ψ (x) \to ψ (c_{ψ})$ . Iterate $ω$ times, since each round creates new formulas needing witnesses, and take the union $L^{*}, T_{0}^{*}$ .
Complete it. Extend $T_{0}^{*}$ to a maximal consistent $L^{*}$ -theory $T^{*}$ by Lindenbaum's lemma: enumerate the $L^{*}$ -sentences and add each one, or its negation, whichever keeps the theory consistent.
Build the term model. Let the domain be the closed $L^{*}$ -terms modulo the relation $t \sim u$ iff $(t = u) \in T^{*}$ . Interpret each constant by its own class, each function symbol by $f ([t_{1}], \dots, [t_{n}]) = [f (t_{1}, \dots, t_{n})]$ , and each relation by $([t_{1}], \dots, [t_{n}]) \in R$ iff $R (t_{1}, \dots, t_{n}) \in T^{*}$ .
Verify. Prove by induction on $ϕ$ that the term model satisfies $ϕ$ exactly when $ϕ \in T^{*}$ ; conclude it models $T \subseteq T^{*}$ .

Lemma 5.40 (Adding a witness preserves consistency). If $T$ is consistent and $c$ is a constant not occurring in $T$ , then $T \cup {\exists x ψ (x) \to ψ (c)}$ is consistent.

Proof. Suppose not. Then $T ⊢ \neg (\exists x ψ (x) \to ψ (c))$ , hence $T ⊢ \exists x ψ (x)$ and $T ⊢ \neg ψ (c)$ . Since $c$ does not occur in $T$ , a derivation of $\neg ψ (c)$ from $T$ can be converted into one of $\neg ψ (y)$ for a fresh variable $y$ — replace $c$ by $y$ throughout, which leaves every axiom of $T$ unchanged and every rule valid. Generalising, $T ⊢ \forall y \neg ψ (y)$ , that is $T ⊢ \neg\exists x ψ (x)$ . Together with $T ⊢ \exists x ψ (x)$ this contradicts consistency of $T$ .∎

Proof (Sketch). Proof sketch of Theorem "Model existence / completeness, semantic form". This sketch fills in the two steps of the Henkin recipe that are not immediate, and rests on Lemma Adding a witness preserves consistency and on Zorn's lemma (or, for a countable language, a plain enumeration).

Step 1 preserves consistency: a single witness is safe by the lemma, a finite iteration by induction, and the $ω$ -limit because any derivation of a contradiction is finite and so lives at a finite stage. Step 2 preserves consistency by the same finiteness argument applied to Lindenbaum's chain. For step 4 one proves the truth lemma by induction on $ϕ$ : the atomic case is the definition of the term model; the Boolean cases use that $T^{*}$ is maximal consistent, so it contains exactly one of $ϕ, \neg ϕ$ and contains $ϕ \land χ$ iff it contains both; and the existential case is where the witnesses pay off — if $\exists x ψ (x) \in T^{*}$ then the Henkin axiom and maximality put $ψ (c_{ψ}) \in T^{*}$ , so the class $[c_{ψ}]$ is a genuine witness inside the term model. Finally, the $L$ -reduct of the term model is a model of $T$ .

The one further wrinkle: if the language has no constants, the term model could be empty, which structures may not be. Adding the witness constants in step 1 removes that possibility.∎

Corollary 5.41 (Compactness from completeness). Theorem Compactness follows from Theorem Model existence / completeness, semantic form.

Proof. Suppose every finite subset of $T$ has a model. If $T$ were inconsistent, there would be a derivation of a contradiction from $T$ ; a derivation is a finite object and cites only finitely many members $T_{0} \subseteq T$ . Then $T_{0}$ is inconsistent, so by soundness $T_{0}$ has no model — contradicting the hypothesis. Hence $T$ is consistent, and by model existence it has a model.∎

This is the second, independent proof of compactness promised earlier; the ultraproduct proof in the previous section used no proof system at all.

Intuition. Think of a theory as a wish list for a world. Soundness says a world cannot grant contradictory wishes. Completeness says the converse: if the wish list never contradicts itself on paper, some world granting all of it exists. The Henkin trick is to build that world out of the wish list's own vocabulary — every object in it is a phrase, and the theory's job is to decide which phrases name the same thing.

Example 5.42 (Consistency gives a model, traced through Henkin). Let $T = {\exists x P (x), \exists x \neg P (x)}$ in a language with one unary predicate $P$ and nothing else. Trace the Henkin construction to produce a model.

Solution. Step 1 (witnesses). $T$ needs witnesses for $P (x)$ and for $\neg P (x)$ : add fresh constants $c_{1}, c_{2}$ with axioms $\exists x P (x) \to P (c_{1})$ and $\exists x \neg P (x) \to \neg P (c_{2})$ . By Lemma Adding a witness preserves consistency the enlarged theory is consistent.

Step 2 (complete). Extend to a maximal consistent $T^{*}$ . Since $\exists x P (x) \in T^{*}$ , modus ponens and maximality give $P (c_{1}) \in T^{*}$ ; likewise $\neg P (c_{2}) \in T^{*}$ .

Step 3 (term model). The closed terms are $c_{1}$ and $c_{2}$ . Nothing in $T^{*}$ forces $c_{1} = c_{2}$ — indeed $P (c_{1}) \land \neg P (c_{2})$ refutes it — so the domain is ${[c_{1}], [c_{2}]}$ , of size $2$ , and $P$ is interpreted as ${[c_{1}]}$ .

Step 4 (check). $[c_{1}]$ satisfies $P$ , so $\exists x P (x)$ holds; $[c_{2}]$ satisfies $\neg P$ , so $\exists x \neg P (x)$ holds. Both axioms are true, giving $M ⊨ T$ with $∣ M ∣ = 2$ .□

Pitfall. Completeness says some model exists, never that it is the model you had in mind. The theory of true arithmetic is consistent, and among its models are the non-standard ones of Theorem Non-standard models of arithmetic. Consistency buys satisfiability, not standardness — and by Corollary No infinite structure is determined up to isomorphism, no first-order theory can buy standardness.

Remark. Completeness and Gödel's incompleteness theorems are different statements about different objects and are consistent with one another. Completeness says: what is true in all models is provable. Incompleteness says: for a theory like Peano arithmetic there are sentences true in the standard model but false in another model, so they are true in some models and false in others, hence not provable and not refutable. The gap between "true in $N$ " and "true in all models of PA" is exactly where independent sentences live.

Exercises for §5.6 →

5.7Categoricity and Quantifier Elimination

Corollary No infinite structure is determined up to isomorphism says no first-order theory determines an infinite model up to isomorphism. The best available substitute is determination within a cardinality, and it turns out to be strong enough to prove completeness.

Definition 5.43 (Categoricity). A theory $T$ is $κ$ -categorical, for an infinite cardinal $κ$ , if $T$ has a model of cardinality $κ$ and any two models of $T$ of cardinality $κ$ are isomorphic.

Theorem 5.44 (Vaught's test). Let $T$ be a theory in a language $L$ with no finite models, and suppose $T$ is $κ$ -categorical for some $κ \geq ∣ L ∣ + ℵ_{0}$ . Then $T$ is complete: for every sentence $ϕ$ , either $T ⊨ ϕ$ or $T ⊨ \neg ϕ$ .

Proof. Suppose not: there are models $A ⊨ T \cup {ϕ}$ and $B ⊨ T \cup {\neg ϕ}$ . Both theories are satisfiable, and neither has a finite model, so both $A$ and $B$ are infinite.

By Theorem Downward Löwenheim–Skolem and Theorem Upward Löwenheim–Skolem applied to each, there are $A^{'} \equiv A$ and $B^{'} \equiv B$ both of cardinality exactly $κ$ — shrink if the model is larger than $κ$ , grow if smaller, which is legitimate since $κ \geq ∣ L ∣ + ℵ_{0}$ .

Now $A^{'}$ and $B^{'}$ are models of $T$ of the same cardinality $κ$ , so $κ$ -categoricity makes them isomorphic, and by Proposition Isomorphism implies elementary equivalence, $A^{'} \equiv B^{'}$ . But $A^{'} ⊨ ϕ$ and $B^{'} ⊨ \neg ϕ$ — a contradiction. Hence $T$ decides every sentence.∎

Example 5.45 (DLO is $ℵ_{0}$ -categorical, hence complete). Prove that any two countable dense linear orders without endpoints are isomorphic, and deduce that DLO is complete.

Solution. Step 1 (set up the back-and-forth). Let $A = {a_{0}, a_{1}, \dots}$ and $B = {b_{0}, b_{1}, \dots}$ be countable models of DLO, enumerated. Build an increasing chain of finite partial order-isomorphisms $p_{0} \subseteq p_{1} \subseteq \dots$ .

Step 2 (the forth step). Given a finite order-preserving $p_{n}$ , take the least-indexed $a$ not yet in its domain. The elements already matched split $A$ into finitely many intervals, and $a$ sits in one of them; the corresponding interval of $B$ is non-empty — if the interval is bounded on both sides, density supplies a point; if unbounded on one side, "no endpoint" supplies one. Choose such a $b$ and extend.

Step 3 (the back step). Symmetrically, take the least-indexed $b$ not in the range and find a matching $a$ the same way.

Step 4 (union). Alternating the two steps ensures every $a_{n}$ enters the domain and every $b_{n}$ the range, so $p = ⋃_{n} p_{n}$ is an order-preserving bijection: $A ≅ B$ .

Step 5 (completeness). DLO has no finite models — density forces infinitude — and the language ${<}$ is finite, so Theorem Vaught's test with $κ = ℵ_{0}$ gives completeness. This is the fact the section Elementary Equivalence and Elementary Substructures borrowed to conclude $(Q, <) \equiv (R, <)$ .□

Categoricity at one cardinal and at another are not independent, which is one of the deepest results in the subject.

Theorem 5.46 (Morley's categoricity theorem (quoted)). Let $T$ be a complete theory in a countable language. If $T$ is $κ$ -categorical for some uncountable $κ$ , then it is $κ$ -categorical for every uncountable $κ$ .

We quote Morley's theorem without proof: it depends on the machinery of stability theory and totally transcendental theories, well beyond this chapter. The four possible categoricity patterns it leaves — categorical in all infinite powers, only in $ℵ_{0}$ , only above $ℵ_{0}$ , or in none — are realised, for instance, by the theory of an infinite set with no structure, by DLO, by ACF $_{0}$ , and by true arithmetic respectively.

The second route to completeness is syntactic and gives much more: an algorithm.

Definition 5.47 (Quantifier elimination). A theory $T$ admits quantifier elimination if for every formula $ϕ (x)$ there is a quantifier-free formula $ϕ^{*} (x)$ in the same free variables with

T ⊨ \forall x (ϕ (x) \leftrightarrow ϕ^{*} (x)) .

Lemma 5.48 (One existential over a conjunction suffices). To prove that $T$ admits quantifier elimination, it is enough to eliminate the quantifier from every formula of the form $\exists x (ψ_{1} \land \dots \land ψ_{m})$ where each $ψ_{k}$ is atomic or negated atomic.

Proof. Argue by induction on quantifier depth. Take a formula with at least one quantifier and consider an innermost one; its scope is quantifier-free, so it can be put in disjunctive normal form. Since $\exists x$ distributes over $\lor$ — $\exists x (α \lor β)$ is equivalent to $\exists x α \lor \exists x β$ — the problem reduces to a single disjunct, a conjunction of literals. Eliminating there produces a quantifier-free equivalent, lowering the depth by one. A universal quantifier is handled as $\neg\exists\neg$ . Iterate.∎

Example 5.49 (Quantifier elimination for dense linear orders). Eliminate the quantifier from $\exists x (a_{1} < x \land a_{2} < x \land x < b_{1} \land \neg (x = c))$ over DLO, and describe the general procedure.

Solution. Step 1 (classify the literals). In the language ${<}$ every literal involving $x$ is one of $x < t$ , $t < x$ , $x = t$ , or a negation of these. Negations collapse: $\neg (x < t)$ is $t < x \lor x = t$ , and $\neg (x = t)$ is $x < t \lor t < x$ . So after re-applying the distribution of Lemma One existential over a conjunction suffices, each disjunct is a conjunction of positive literals $t_{i} < x$ , $x < u_{j}$ , $x = v$ .

Step 2 (kill any equality). If some conjunct is $x = v$ , substitute $v$ for $x$ throughout and drop the quantifier entirely. Nothing quantified remains.

Step 3 (the remaining case). Otherwise the disjunct reads $⋀_{i} (t_{i} < x) \land ⋀_{j} (x < u_{j})$ . Such an $x$ exists in a dense linear order without endpoints exactly when every lower bound is below every upper bound:

\exists x (i ⋀ t_{i} < x \land j ⋀ x < u_{j}) ⟷ i, j ⋀ t_{i} < u_{j},

with the convention that an empty conjunction is $⊤$ — if there are no $t_{i}$ the "no least element" axiom provides $x$ , and if there are no $u_{j}$ the "no greatest element" axiom does. The right-hand side is quantifier-free.

Step 4 (the given formula). Rewrite $\neg (x = c)$ as $x < c \lor c < x$ and distribute, giving two disjuncts:

$\exists x (a_{1} < x \land a_{2} < x \land x < b_{1} \land x < c)$ , which by Step 3 becomes $a_{1} < b_{1} \land a_{1} < c \land a_{2} < b_{1} \land a_{2} < c$ ;
$\exists x (a_{1} < x \land a_{2} < x \land c < x \land x < b_{1})$ , which becomes $a_{1} < b_{1} \land a_{2} < b_{1} \land c < b_{1}$ .

The answer is the disjunction of the two, entirely free of quantifiers.

Step 5 (completeness again). A sentence has no free variables, so its quantifier-free equivalent is a Boolean combination of atomic sentences in a language with no constants — there are none, so the equivalent is $⊤$ or $⊥$ , decided the same way in every model. Hence DLO is complete and, since the elimination is an algorithm, decidable.□

Theorem 5.50 (Quantifier elimination for algebraically closed fields (quoted)). The theory ACF of algebraically closed fields admits quantifier elimination in the ring language ${0, 1, +, -, \cdot}$ . Consequently ACF $_{p}$ , for each fixed characteristic $p$ (prime or zero), is complete, and the image of a constructible set under a projection is constructible — Chevalley's theorem.

Proof (Sketch). A sketch; the algebraic input is the theory of resultants, which is not developed here. By Lemma One existential over a conjunction suffices it is enough to eliminate $x$ from a conjunction of polynomial equations $p_{k} (x, y) = 0$ and inequations $q_{l} (x, y) \neq = 0$ . Repeated division reduces the system to a single equation and a single inequation; "these have a common root" is then expressed by the vanishing of a resultant, a polynomial in the coefficients alone, and "the equation has a root not shared with the inequation" is a further resultant condition. Every such condition is quantifier-free in $y$ .

Completeness of ACF $_{p}$ then follows as in Step 5 above, since a quantifier-free sentence in the ring language is a Boolean combination of numerical identities among integers, decided by the characteristic alone.∎

Remark. ACF $_{p}$ is also $κ$ -categorical for every uncountable $κ$ : an algebraically closed field is determined up to isomorphism by its characteristic and its transcendence degree over the prime field, and for $∣ K ∣ = κ > ℵ_{0}$ the transcendence degree equals $κ$ . Vaught's test therefore gives completeness a second way. It is not $ℵ_{0}$ -categorical — the countable models have transcendence degrees $0, 1, 2, \dots, ℵ_{0}$ , pairwise non-isomorphic.

Theorem 5.51 (Ryll-Nardzewski (quoted)). A complete theory $T$ in a countable language with only infinite models is $ℵ_{0}$ -categorical if and only if for every $n$ there are only finitely many formulas in $n$ free variables up to $T$ -equivalence.

We quote this without proof; it rests on the omitting types theorem. It explains why $ℵ_{0}$ -categoricity is rare: it demands that the language, modulo the theory, be able to describe only finitely many kinds of $n$ -tuple. DLO passes — an $n$ -tuple is described entirely by which of its coordinates are equal and how the rest are ordered, giving finitely many possibilities. The theory of an infinite set with one unary predicate splitting it into two infinite pieces also passes. Most theories of algebraic interest fail.

Summary.

$κ$ -categoricity plus "no finite models" gives completeness (Vaught's test), and by Morley's theorem uncountable categoricity does not depend on which uncountable $κ$ is chosen.
Quantifier elimination gives completeness and decidability, by reducing every sentence to a quantifier-free one that every model evaluates identically.
DLO is $ℵ_{0}$ -categorical and eliminates quantifiers; ACF $_{p}$ is uncountably categorical and eliminates quantifiers; true arithmetic is categorical in no infinite cardinal and eliminates nothing.

Exercises for §5.7 →

Common Mistakes

Elementary equivalence is not isomorphism. $M \equiv N$ only says no first-order sentence separates them. Cardinality, well-foundedness and "being standard" are invisible to first-order logic; by Corollary No infinite structure is determined up to isomorphism every infinite structure has non-isomorphic elementary equivalents.
Substructure is not elementary substructure. $N \subseteq M$ constrains only the atomic data. Use Theorem Tarski–Vaught test to check elementarity, and remember that $(Z, <) \subseteq (Q, <)$ fails it.
Forgetting that domains are non-empty. Classical first-order semantics requires $M \neq = \emptyset$ ; $\exists x (x = x)$ is valid. This is why the Henkin construction must supply at least one constant.
Believing ultraproducts are always exotic. If $U$ is principal at $i_{0}$ , Łoś's theorem collapses to evaluation at coordinate $i_{0}$ and the ultraproduct is isomorphic to $M_{i_{0}}$ . Non-principality is what buys new elements, and it costs an appeal to Zorn's lemma.
Using Łoś's theorem with a mere filter. The negation step of the proof needs " $A \in U$ or $I ∖ A \in U$ ". With a filter that is not maximal, the reduced product satisfies only the positive Horn part of the theory, not every formula.
Reading the Skolem paradox as a refutation of Cantor. A countable model of ZFC still satisfies Cantor's theorem internally; it merely lacks, as an element, the external bijection that would witness countability of its "uncountable" set.
Expecting completeness to deliver the intended model. Consistency yields some model. True arithmetic is consistent and has non-standard models; PA is consistent and has models of $\neg Con (PA)$ .
Applying Vaught's test without excluding finite models. The empty theory in the empty language is $κ$ -categorical for every infinite $κ$ — any two infinite sets of the same size are isomorphic as bare sets — yet it is plainly incomplete, since "there are at least two elements" is true in some of its models and false in the one-element model. The proof of Theorem Vaught's test breaks exactly there: the Löwenheim–Skolem step needs both counterexample models to be infinite before it can resize them.

About the practice questions. They check that you can carry out this chapter's computations correctly, and each one is graded on a single answer. They are not proof exercises: working through them confirms the mechanics, not that you could prove the results yourself. For that, re-read the statements above and try to reconstruct their proofs with the page closed.

Practice this chapter