Introduction to Model-theory and Mathematical Logic

David Pierce

2005.01.13

Contents

1 Introduction 4 1.1 Building-blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Propositional logic . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Propositional model-theory 10 2.1 Formal proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Logical consequence . . . . . . . . . . . . . . . . . . . . . . . . . 16 2.3 Soundness and Completeness . . . . . . . . . . . . . . . . . . . . 19 2.4 Additional exercises . . . . . . . . . . . . . . . . . . . . . . . . . 22

3 First-order logic 23 3.1 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Formulas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.3 Logical consequence . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.4 Additional exercises . . . . . . . . . . . . . . . . . . . . . . . . . 35

4 Quantifier-elimination 36

5 Relations between structures 41 5.1 Fundamental definitions . . . . . . . . . . . . . . . . . . . . . . . 41 5.2 Additional definitions . . . . . . . . . . . . . . . . . . . . . . . . 42 5.3 Implications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.4 Categoricity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

6 Compactness 48 6.1 Additional exercises . . . . . . . . . . . . . . . . . . . . . . . . . 53 7 Completeness 55

7.1 Logic in general . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 7.2 Propositional logic . . . . . . . . . . . . . . . . . . . . . . . . . . 57 7.3 First-order logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 7.4 Tautological completeness . . . . . . . . . . . . . . . . . . . . . . 59 7.5 Deductive completeness . . . . . . . . . . . . . . . . . . . . . . . 61 7.6 Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

8 Numbers of countable models 67 8.1 Three models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 8.2 Omitting types . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 8.3 Prime structures . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 8.4 Saturated structures . . . . . . . . . . . . . . . . . . . . . . . . . 74 8.5 One model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 8.6 Not two models . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

Chapter 1

Introduction

These notes are based on lectures given for Math 406, ‘Introduction to Mathematical Logic and Model-theory’, at METU in 2004. I have expanded on a few points and rearranged some topics.

Background reading includes [7]. Exercises appear here and there, emphasized with bold type; and there are some sections comprising exercises, as you can see from the table of contents.

1.1 Building-blocks

An ordered pair (a, b) is the set {{a}, {a, b}}. Then the Cartesian product A × B of the sets A and B is the set

{(a, b) : a ∈ A & b ∈ B}.

To express that f is a function from A to B, we can just write

f : A ⟶ B.

This means f is a subset of A × B with a certain property (namely, for every a in A, there is a unique b in B such that (a, b) ∈ f; then we write f(a) = b). The set of all functions from A to B can be denoted

B^{A}.  (1.1)

(Some people write ^{A}B.) Let ω be the set of natural numbers:

ω = {0, 1, 2, 3, … }
= {0, 0′, 0′′, 0′′′, … }.

It is notationally convenient to treat 0 as ∅, and x′ as x ∪ {x}. Then

n = {0, …, n − 1}

for all n in ω. Under this understanding of the natural numbers, the nth Cartesian power of A is precisely

A^{n}, in the notation introduced on line (1.1) above: the nth Cartesian power of A is the set of functions from n to A. An element of A^{n} can be written as

(a_{0}, …, a_{n−1})

or a or a⃗; the function is then, in any case,

i ⟼ a_{i} : n ⟶ A,

and it can be called an (ordered) n-tuple from A.

Note well that A^{0} = {∅} = {0} = 1; this is true even if A is empty. Also, every element of A^{1} is {(0, a)} for some a in A. So we have a bijection

a ⟼ {(0, a)} : A ⟶ A^{1}.  (1.2)

We may sometimes treat this bijection as an identification; that is, we may decide not to distinguish between a and {(0, a)}.

For any m and n in ω, we have a bijection

(a⃗ , b⃗) ⟼ a⃗ ˆ b⃗ : A^{m} × A^{n} ⟶ A^{m+n}  (1.3)

where a⃗ˆ b⃗ is the (m + n)-tuple (a_{0}, …, a_{m−1}, b_{0}, …, b_{n−1}); this is the (m + n)- tuple c⃗ such that

c_{k} = \begin{cases}a_{k}, & if k < m; \\ b_{k−m}, & if m ⩽ k < m + n. \end{cases}

We always treat the bijection in (1.3) as an identification.

An n-ary operation on A is a function from A^{n} to A. The set of these can be denoted

A^{A^{n}}.

In particular, a 0-ary or nullary operation on A is an element of A^{1}; by the bijection in (1.2) then, we may identify a nullary operation on A with an element of A.

An n-ary relation on A is a subset of A^{n}; the set of these is 𝒫(A^{n}).

An n-ary operation on A is then a (certain kind of) subset of A^{n} × A, and this product can be identified with A^{n} × A^{1} and hence with A^{n+1}; so an n-ary operation on A can be thought of as an (n + 1)-ary relation on A.

1.2 Structures

Our fundamental object of study will be structures. The notion of a structure provides a way to unify the treatment of many mathematical ideas. By our official definition, a structure is an ordered pair (A, ℐ), also referred to as 𝔄, where:

(∗) A is a non-empty set, called the universe of the structure;

(†) ℐ is a function, written also

s ⟼ s^{𝔄},

whose domain L is called the signature of the structure; (‡) s^{𝔄} is either an element of A or an n-ary operation or relation on A for

some positive n, for each s in L. If L = {s_{0}, s_{1}, … }, then 𝔄 can be written

(A, s_{0}^{𝔄}, s_{1}^{𝔄}, …).

Examples 1.1. The following are structures:

(1) (ω,′, 0);

(2) a group (G, ·,^{−1}, 1);

(3) an abelian group (G, +, −, 0);

(4) a ring (R, +, −, ·, 0, 1);

(5) the ring ℤ or (ℤ, +, −, ·, 0, 1);

(6) the field ℝ or (ℝ, +, −, ·, 0, 1);

(7) a partial order (X, ⩽);

(8) a vector-space V over a field K; here the signature of V is {+, −, 0} ∪ {a · : a ∈ K}, where a · is the unary operation of multiplying by a;

(9) the power-set structure on a non-empty set Ω, namely

(𝒫(Ω), ∩, ∪,^{c}, ∅, Ω, ⊆);

(10) the truth-structure

(𝔹, ∧, ∨, ¬, 0, 1, ⊨),

where 𝔹 = {0, 1}, and ⊨ is the binary relation {(0, 0), (0, 1), (1, 1)}. (The name ‘truth-structure’ is my invention.)

The last two examples are the same if Ω = 1. Propositional logic studies the truth-structure; model-theory studies all structures. With ℐ as above in the structure (A, ℐ): (∗) s^{𝔄} is the interpretation in 𝔄 of s; (†) s is a symbol for s^{𝔄}. So s is one of the following: (∗) a constant; (†) an n-ary function-symbol for some positive n in ω; (‡) an n-ary predicate (or relation-symbol) for some positive n in ω. Since nullary operations on A can be considered as elements of A, a constant can be considered as a nullary function-symbol. Here are some observations about our definition of structure: (∗) I am following the old convention (used for example in [1]) of denoting the

universe of a structure by a Roman letter, and the structure itself by the corresponding Fraktur or Gothic letter. Recent writers (as in [6] or [9]) use ‘calligraphic’ letters, not Fraktur:

For a structure with universe: A B C … M N …
I write: 𝔄 𝔅 ℭ … 𝔐 𝔑 …
Others may write: A B C … M N …

Another option (taken in [5]) is to use an ordinary letter like A for a structure, and then dom(A) for its universe. (Here ‘dom’ stands for domain.) Finally, one might not bother to make a typographical distinction between a structure and its universe. Indeed, as suggested in the examples, the distinction is not easy to make with standard structures like ℤ or ℝ.

(†) Similarly, it is not always easy or convenient to distinguish between a symbol and its interpretation. A homomorphism from a group G to a group H is usually described as a function f from G to H such that

f(g_{0} · g_{1}) = f(g_{0}) · f(g_{1})

for all g_{e} in G. If we are trying to be precise, we should call the groups 𝔊 (or (G, ·^{𝔊})) and ℌ (or (H, ·^{ℌ})), and we should say that f is such that

f(g_{0} ·^{𝔊} g_{1}) = f(g_{0}) ·^{ℌ} f(g_{1})

for all g_{e} in G. But writing this way soon becomes tedious. (‡) In a structure (A, ℐ), the interpretation-function ℐ could be considered

to carry, within itself, the identity of the universe A. This is certainly true if the signature L of the structure contains a unary function-symbol f, since then ℐ determines the function f^{𝔄} and hence its domain, A. In any case, A and ℐ work together to provide interpretations of the symbols in L as elements of, or operations or relations on, a certain set, namely A itself. That’s all a structure is: something that provides a mathematical interpretation for certain symbols. We shall develop this idea later. What makes model-theory interesting is that the same symbols can have different interpretions. Here begins the distinction between syntax (formal symbolism) and semantics (mathematical meaning).

1.3 Propositional logic

Of the so-called truth-structure given in the Examples 1.1, the signature is {∧, ∨, ¬, 0, 1, ⊨}. Besides the binary predicate ⊨ (which could also be written ⩽), the symbols are Boolean connectives. Other Boolean connectives are also used. Each Boolean connective is an n-ary function-symbol for some n in ω, and each has a standard interpretation as an operation on 𝔹. For example:

(0) 0 and 1 are nullary connectives;

(1) ¬ is a singulary or unary connective;

(2) ∧, ∨, → and ↔ are binary connectives.

To give the interpretations of the connectives, we can understand 𝔹 as a twoelement abelian group with the addition-table

+ 0 1 0 0 1 1 1 0 .

Then one way to give the standard interpretations is:

(0) the nullary connectives 0 and 1 are interpreted as themselves;

(1) ¬ is interpreted as the singulary operation x ↦ x + 1 on 𝔹

(2) ∧, ∨, → and ↔ are interpreted as the binary operations on 𝔹 taking (x, y) to xy, xy + x + y, xy + x + 1 and x + y + 1 respectively.

These interpretations can be given in other (but equivalent) ways: For example, we can define → by

(x → y) = 1 ⟺ x ⊨ y.

In general, a signature for propositional logic is a set of Boolean connectives. Let L be such. The formulas of L are certain strings of:

(∗) symbols from L;

(†) propositional variables P_{0}, P_{1}, P_{2}, ….

In particular:

(∗) P is a formula, if P is a variable.

(†) ∗F_{0} ⋯ F_{n−1} is a formula, if ∗ is an n-ary connective from L, and the F_{i} are formulas. (If n = 0, then ∗ by itself is a formula.)

Commonly, if ∗ is binary, then, instead of ∗F_{0}F_{1}, one writes

(F_{0} ∗ F_{1}).

A formula is n-ary if its variables belong to the set {P_{0}, …, P_{n−1}}. (Alternatively, one may want to refer to a formula as n-ary if it contains no more than n distinct variables.)

Since each Boolean connective ∗ has a standard interpretation, also denoted ∗, every n-ary formula F represents an n-ary operation

x⃗ ⟼ F̂(x⃗) : 𝔹^{n} ⟶ 𝔹

as follows:

(∗) If k < n, then P_{k} is an n-ary formula and, as such, represents the operation

x⃗ ⟼ x_{k} : 𝔹^{n} ⟶ 𝔹

(which can be denoted P̂_{k}).

(†) If ∗ is n-ary, and F_{0}, …, F_{n−1} are k-ary, then ∗F_{0} ⋯ F_{n−1} represents

x⃗ ⟼ ∗ (F̂_{0}(x⃗), …, F̂_{n−1}(x⃗)) : 𝔹^{k} ⟶ 𝔹.

The notion that a propositional formula represents an operation will be developed further in the next chapter in case L is {¬, →}. We shall be able to restrict ourselves to this signature, because it is adequate. In general, a signature for propositional logic is adequate if, for each n-ary operation f on 𝔹, there is an (n + k)-ary formula F of L (for some k) such that

f(x⃗) = F̂(x⃗ , y⃗)

for all x⃗ in 𝔹^{n} and y⃗ in 𝔹^{k}: that is, every operation f on 𝔹 is represented in L by some formula F. We allow the arity of F to be larger than that of f, since we want it to be possible for signatures without nullary connectives to be adequate. (If something is n-ary, then its arity is n.) The following is proved in [8]:

Theorem 1.2. A signature of propositional logic is adequate, provided that in it are represented:

(∗) the constant functions 0 and 1;

(†) the ternary function f given by

\begin{matrix}e_{0} & e_{1} & e_{2} & f(e⃗) \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{matrix} .

Proof. By induction. The nullary operations are represented by assumption. Suppose all n-ary operations are represented, and g is (n + 1)-ary. Let h_{e} be the n-ary operation x⃗ ↦ g(x⃗ , e), if e ∈ 𝔹. Then g is

(x⃗ , y) ⟼ f(h_{0}(x⃗), h_{1}(x⃗), y).

Since the h_{e} are represented by inductive hypothesis, and f is represented by assumption, g is also represented. By induction, the operations of all arities are represented.

Example 1.3. The propositional signature {→, ¬} is adequate, because:

(∗) P_{0} → P_{0} represents 1;

(†) ¬(P_{0} → P_{0}) represents 0;

(‡) the operation f as in the theorem is represented by the formula

¬((¬P_{2} → P_{0}) → ¬(P_{2} → P_{1})),

since its truth-table is:

\begin{matrix}¬ & ((¬ & P_{2} & → & P_{0}) & → & ¬ & (P_{2} & → & P_{1})) \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \end{matrix} .

(See also [7, § 2.2–3]. This formula is logically equivalent—or truthequivalent in the sense of [7, § 2.4]—to (¬P_{2} → P_{0}) ∧ (P_{2} → P_{1}).)

Propositional model-theory

This chapter is inspired in part by [1, § 1.2]. Generally, the term model-theory refers to first-order model-theory, because the logic it uses is first-order logic. The notion of structure defined in ch. 1 is the notion as used in first-order model-theory. However, some model-theoretic ideas can be worked out in the simpler context of propositional logic. This is what is done here. In particular, a simpler notion of structure will be introduced, albeit one that retains the fundamental idea of providing an interpretation for symbols.

Our official signature for propositional logic will be

{→, ¬}.

Let V be our set {P_{k} : k ∈ ω} of propositional variables. For the sake of a precise definition of formula, let S be the set of all finite strings (or sequences) of symbols from the set

V ∪ {→, ¬} ∪ {(,)}.

Now let U be the subset of 𝒫(S) comprising the subsets N of S such that:

(∗) V ⊆ N, that is, N contains all elements of V (when these are considered as sequences of length 1);

(†) for all F in S, if F ∈ N, then ¬F ∈ N;

(‡) for all F and G in S, if F and G are in N, then (F → G) ∈ N.

Let Fm() = ⋂ U. This is just the set of propositional formulas in the signature {→, ¬}. Throughout this chapter, all formulas are elements of Fm().

In particular, by construction, Fm() is the smallest subset N of S with the properties above. We may say that the definition of Fm() is inductive, because it makes proof by induction on formulas possible: If N ⊆ Fm(), then, to prove N = Fm(), it is enough to show that N has the properties (∗, †, ‡) above.

As a first example of proof by induction on formulas, we have the next lemma below. We first make some (obvious) definitions:

If s_{0}, s_{1}, …, and s_{n−1} are symbols, then the length of the string s_{0}s_{1} ⋯ s_{n−1} is n; and the string begins with s_{0}. An initial segment of the string is one of the strings s_{0}s_{1} ⋯ s_{k−1}, where k ⩽ n. The initial segment is proper if k < n.

Lemma 2.1.

(∗) Every formula has positive length.

(†) Every formula of length 1 is a variable.

(‡) Every formula of length greater than 1 begins with ¬ or (.

(§) Every formula beginning with ¬ is ¬F for some formula F.

(¶) Every formula beginning with ( is (F → G) for some formulas F and G.

Proof. By induction on formulas. Let N be the set of formulas F such that:

(∗) F has positive length;

(†) if F has length 1, then F is a variable;

(‡) if F has length greater than 1, then F begins with ¬ or (;

(§) if F is ¬E for some string E, then E is a formula;

(¶) if F begins with (, then F is (G → H) for some formulas G and H.

Then N contains the variables, and N contains ¬F and (F → G) if it contains F and G. Hence N = Fm().

Definition of functions on Fm() by recursion is possible, because of the next theorem below. This will use another lemma. Now, because formulas have lengths, this lemma—and other facts about formulas—can be proved by induction (usually strong induction) on these lengths:

Lemma 2.2. No proper initial segment of a formula is a formula.

Proof. Let N be the set of formulas of which no proper initial segment is a formula. We shall prove by strong induction on the lengths of formulas that N = Fm(). Suppose N contains all formulas shorter than a formula F. By Lemma 2.1, we know that F is a variable P or a formula ¬G or (G → H), where G and H are formulas. The only proper initial segment of P is the empty string, which is not a formula. Any proper initial segment of ¬G is ¬G′ for some initial segment G′ of G; so G′ is not a formula, by strong inductive hypothesis; hence ¬G′ is not a formula. Finally, and similarly, any initial segment of (G → H) is (G′ → H′) for some formulas G′ and H′. Then one of G and G′ is an initial segment of the other. But each one is shorter than F; so by strong inductive hypothesis, G and G′ are the same formula. Then H′ is a proper initial segment of H; so these formulas must be the same. Thus, in all cases, F ∈ N. By strong induction, N = Fm().

We need not use induction again to prove the following:

Theorem 2.3 (Unique Readability). If F is a formula, then F satisfies exactly one of the following conditions:

(∗) F ∈ V;

(†) F is ¬G for some formula G;

(‡) F is (G → H) for some unique formulas G and H.

Proof. Every formula is a variable or is ¬F or (F → G) for some formulas F and G. Suppose (F → G) is also (F′ → G′), where F′ and G′ are also formulas. Then (as in the previous proof) one of F and F′ is an initial segment of the other. By the last lemma, this means F and F′ are the same, so G and G′ must be the same.

Corollary 2.4 (Recursion). Let f_{¬} be a unary, and f_{→} a binary, operation on some set. Let g be a function from V into that set. Then g extends uniquely to the domain Fm() so that

(∗) g(¬F) = f_{¬}(g(F)),
(†) g((F → G)) = f_{→}(g(F), g(G))

for all F and G in Fm().

Proof. Not important. The idea is to let G be the set of all relations with the desired properties of g (except the property of being a function), and then to show that ⋂ G is in G and is in fact a function. See [7, Theorem 5.2.1].

Notationally, we suppose:

(∗) P, Q, R, … are in V;

(†) F, G, H, … are in Fm();

These symbols can be called syntactical variables, since their possible values are symbols and strings of symbols in the formal logic that we are studying. (There is some discussion of this terminology in [2, §08].)

We also let e⃗ = (e_{0}, …, e_{n−1}) ∈ 𝔹^{n} for an appropriate n in ω, where 𝔹 = {0, 1}.

The formula F is n-ary if its variables come from {P_{k} : k < n}. Under this definition, the n-ary formulas are also (n + 1)-ary. The set of n-ary formulas can be denoted

Fm^{n}().

Note that this set has an inductive definition, and definition by recursion of functions on Fm^{n}() is possible. (Exercise: how can the inductive definition of Fm() be adapted to an inductive definition of Fm^{n}()?)

We can understand ¬ to be the unary operation on 𝔹 given by

\begin{matrix}e & ¬e \\ 0 & 1 \\ 1 & 0 \end{matrix} ,

and → to be the binary operation on 𝔹 given by

\begin{matrix}e_{0} & e_{1} & e_{0} → e_{1} \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \end{matrix} .

These agree with the definitions given on p. 8. Then we have a unique function F ↦ F̂ from Fm^{n}() into 𝔹^{𝔹^{n}} such that:

(∗) P̂_{k} is e⃗ ↦ e_{k}, if k < n;

(†) F̂(e⃗) = ¬(Ĝ(e⃗)), if F is ¬G;

(‡) F̂(e⃗) = Ĝ(e⃗) → Ĥ(e⃗), if F is (G → H).

A truth-assignment for an n-ary formula F is an element e⃗ of 𝔹^{n}; the element F̂(e⃗) of 𝔹 is the value of F at e⃗. The computation of this value is a finite procedure, and depends only on those e_{k} such that P_{k} actually appears in F.

Example 2.5. Let F be (P_{0} → (¬P_{1} → P_{2})). Let G be (¬P_{1} → P_{2}). Then

F̂(e⃗) = 1 ⟺ P̂_{0}(e⃗) ⩽ Ĝ(e⃗)
⟺ e_{0} ⩽ Ĝ(e⃗)
⟺ e_{0} = 0 or (e_{1} + 1) ⩽ e_{2}
⟺ e_{0} = 0 or e_{1} = 1 or e_{2} = 1.

We write

⊢ F

if F̂(e⃗) = 1 for all truth-assignments e⃗ for F; in this case, F is a tautology. Otherwise, we write

⊬ F.

The question of whether F is a tautology can be answered by computing its truth-table, namely:

\begin{matrix}P_{0} & … & P_{n−1} & F \\ ⋮ & & ⋮ & ⋮ \\ e_{0} & … & e_{n−1} & F̂(e⃗) \\ ⋮ & & ⋮ & ⋮ \end{matrix} .

(See also [7, § 2.3].)

2.1 Formal proofs

Let us use Σ as a syntactical variable for sets of formulas. For us, a formal proof or a deduction of F from Σ will be a finite sequence

G_{0}, …, G_{n}

of formulas, where:

(∗) G_{n} is F;

(†) for each k less than n + 1, G_{k} is a tautology, or G_{k} is in Σ, or there are i and j less than k such that G_{j} is (G_{i} → G_{k}).

In terms of [7, § 2.9], we are using the proof-system whose only axioms are the tautologies, and whose only rule of inference is modus ponens. If there is such a deduction, we write

Σ ⊢ F,

and we can say that F is deducible from Σ; we can also say that the elements of Σ are hypotheses in the deduction.

We may write deductions vertically, so as to justify each step; but the deduction itself is just a finite sequence of formulas:

Examples 2.6.

(∗) {F, (F → G)} ⊢ G, by the deduction

F  [hypothesis]
(F → G)  [hypothesis]
G  [modus ponens]

(†) If ⊢ (F → G), then {F } ⊢ G by the deduction

F  [hypothesis]
(F → G)  [axiom]
G  [modus ponens]

(The formal proof is the same, but the justifications are not.)

(‡) {(P → (Q → R)), (P → Q)} ⊢ (P → R); finding the deduction is an exercise.

Something to think about is whether there are procedures:

(∗) for determining whether Σ ⊢ F;

(†) for finding the proof, if it exists.

Lemma 2.7. If G_{0}, …, G_{n} is a formal proof, and k ⩽ n, then G_{0}, …, G_{k} is a formal proof.

Proof. Immediate from the definition.

Lemma 2.8. Σ ⊢ F just in case Σ_{0} ⊢ F for some finite subset Σ_{0} of Σ.

Proof. (⇒) Say there is a formal proof G_{0}, …, G_{n} of F from Σ. Let

Σ_{0} = Σ ∩ {G_{0}, …, G_{n}}.

Then G_{0}, …, G_{n} is a formal proof of F from Σ_{0}, and Σ_{0} is a finite subset of Σ.

(⇐) A formal proof from Σ_{0} is a formal proof from any set that includes Σ_{0}.

Lemma 2.9. ⊢ F ⟺ ∅ ⊢ F.

Proof. (⇒) If ⊢ F, then F is a one-step derivation of itself from ∅, so ∅ ⊢ F.

(⇐) We argue by strong induction on the lengths of deductions. Suppose that F is a tautology whenever F has a deduction from ∅ of length less than n + 1. Now suppose that

G_{0}, …, G_{n−1}, F

is a deduction (which has length n + 1) of F. Then either F is a tautology, or there are i and j less than n such that G_{j} is (G_{i} → F). In the latter case, by inductive hypothesis, both G_{i} and (G_{i} → F) are tautologies. But the value of (G_{i} → F) at e⃗ is just F̂(e⃗), if Ĝ_{i}(e⃗) = 1. Hence F is a tautology. By induction, all formulas deducible from ∅ are tautologies.

We are sometimes more interested in knowing whether a deduction exists than in what it is. Towards developing this knowledge, we have:

Lemma 2.10. Suppose {F : Σ ⊢ F } ⊢ G. Then Σ ⊢ G, that is, G is already in the set {F : Σ ⊢ F }.

Proof. Let Σ^{∗} = {F : Σ ⊢ F }. In a deduction of G from Σ^{∗}, if an element of Σ^{∗} appears, then replace it with its deduction from Σ. The result is then itself a deduction from Σ.

A useful application of the lemma is:

Theorem 2.11 (Modus Ponens). If Σ ⊢ F and Σ ⊢ (F → G), then Σ ⊢ G.

Proof. Let Σ^{∗} = {H : Σ ⊢ H}. If F and (F → G) are in Σ^{∗}, then G has a three-line proof from Σ^{∗} as in one of the Examples 2.6 above. Hence Σ ⊢ G, by the last lemma.

A set Σ of formulas is inconsistent if Σ ⊢ ¬F for some F in Σ; otherwise, Σ is consistent. A formula F is a contradiction if ¬F is a tautology. There are various ways to express inconsistency:

Lemma 2.12. The following are equivalent:

(∗) Σ is inconsistent;

(†) Σ ⊢ F and Σ ⊢ ¬F for some F;

(‡) Σ ⊢ F for all F;

(§) a contradiction is deducible from Σ.

Proof. (∗) ⇒ (†). If Σ is inconsistent, then Σ ⊢ ¬F for some F in Σ; but then Σ ⊢ F also.

(†) ⇒ (‡). Say Σ ⊢ F and Σ ⊢ ¬F. But ⊢ (F → (¬F → G)) for all G (by an exercise). By two applications of Modus Ponens, Σ ⊢ G.

(‡) ⇒ (§). Immediate.

(§) ⇒ (∗). Suppose F is a contradiction, and Σ ⊢ F. Then Σ ≠ ∅, since only tautologies are derivable from ∅. Hence there is G in Σ. But ⊢ (F → ¬G) (by an exercise), so Σ ⊢ ¬G by Modus Ponens.

Lemma 2.13.

(∗) Σ is inconsistent just in case some finite subset of Σ is inconsistent.

(†) Σ is consistent just in case {F : Σ ⊢ F } is consistent.

Proof. Exercise.

Theorem 2.14 (Deduction). Σ ⊢ (F → G) if and only if Σ ∪ {F } ⊢ G.

Proof. (⇒) Exercise.

(⇐) We use strong induction on the lengths of deductions. Suppose the claim holds when G has a formal proof of length less than n + 1. Suppose also that H_{0}, …, H_{n−1}, G is a formal proof of G from Σ ∪ {F }. Now,

⊢ (G → (F → G))

(by an exercise). Hence, if G ∈ Σ or G is a tautology, then

Σ ⊢ (F → G)

by Modus Ponens. The other possibility is that H_{j} is (H_{i} → G) for some i and j in n. Then Σ ⊢ (F → H_{i}) and Σ ⊢ (F → (H_{i} → G)) by inductive hypothesis. But also

⊢ ((F → H_{i}) → ((F → (H_{i} → G)) → (F → G)))

(exercise). By two applications of Modus Ponens, Σ ⊢ (F → G).

The Deduction Theorem gives a condition under which certain proofs exist. In particular, we have:

Corollary 2.15.

(∗) If Σ ∪ {F } is inconsistent, then Σ ⊢ ¬F. (†) If Σ ⊬ G, then Σ ∪ {¬G} is consistent.

Proof. Suppose Σ ∪ {F } is inconsistent. Then Σ ∪ {F } ⊢ ¬F by Lemma 2.12. Hence Σ ⊢ (F → ¬F). But also

⊢ ((F → ¬F) → ¬F)

(exercise). Hence Σ ⊢ ¬F by Modus Ponens.

The remainder is an exercise.

Recall the distinction on p. 7 between syntax and semantics. The notion of formal proof can be called syntactic because it involves formal manipulation of symbols. A good proof-system will capture the notion of logical consequence, a notion that can be called semantic. We now develop this notion:

2.2 Logical consequence

A structure for propositional logic is a function α (or P ↦ α(P)) from V to 𝔹. (Alternatively, the structure is not the function α, but the set {P ∈ V : α(P) = 1}; but such a definition can cause confusion. In any case, the set and the function determine each other.) Suppose F is n-ary, and e⃗ is the truth-assignment

(α(P_{0}), …, α(P_{n−1})).

If F̂(e⃗) = 1, then we say that F is true in α, and we write

α ⊨ F.

So far we have only introduced some new notation. Whether F is true in α can be determined by finite computation. In particular:

(∗) α ⊨ P ⟺ α(P) = 1; (†) α ⊨ ¬F ⟺ α ⊭ F; (‡) α ⊭ (F → G) ⟺ α ⊨ F & α ⊨ ¬G.

So truth can be computed as in the following (which can be compared with Example 2.5):

Example 2.16. The following are equivalent:

(∗) α ⊨ P → (¬Q → R);
(†) α ⊨ ¬P or α ⊨ (¬Q → R);
(‡) α(P) = 0 or α ⊨ Q or α ⊨ R;
(§) α(P) = 0 or α(Q) = 1 or α(R) = 1.

The notion of structures allows us to make the following definition. If Σ is a (possibly infinite) set of formulas, and if α ⊨ F for every F in Σ, then α is a model of Σ, and we can write

α ⊨ Σ.

Finally, F is a logical consequence of Σ, or Σ entails F, if F is true in every model of Σ. In this case, we can write

Σ ⊨ F.

Here, if Σ is a finite set {G_{0}, …, G_{n−1}}, then we can also write

G_{0}, …, G_{n−1} ⊨ F

(without braces). We consider logical consequence or entailment as a semantic notion, because, from its definition, it seems not to be determined by simple computation. Indeed, there are infinitely many (in fact, uncountably many) structures, and anyway a formula might be a logical consequence of an infinite set of formulas.

It is important to note that ⊨ is used in two completely different ways:

(∗) to express truth, which is a relation between a structure and a formula

(or set of formulas); (†) to express entailment, which is a relation between a set of formulas and

a formula.

The following is a semantic version of the Deduction Theorem; it is easier to prove:

Lemma 2.17. Σ ∪ {F } ⊨ G just in case Σ ⊨ (F → G).

Proof. Exercise.

Repeated application of the lemma gives

F_{0}, …, F_{n} ⊨ G ⟺ ⊨ F_{0} → ⋯ → F_{n} → G.  (2.1)

The notational convention here is that F → G → H at the end of a formula means (F → (G → H)); that is, grouping is from the right. Towards an alternative expression of this equivalence, let us note:

Lemma 2.18. Suppose F and G are both n-ary. The following are equivalent:

(∗) F ⊨ G;
(†) F̂(e⃗) ⩽ Ĝ(e⃗) for all e⃗.

Proof. Exercise.

We can now define F and G to be (logically) equivalent if they have the same truth-table, that is, F̂(e⃗) = Ĝ(e⃗) for all e⃗, equivalently, F ⊨ G and G ⊨ F; we can express this by

F ∼ G.

Note the truth-table

\begin{matrix}¬ & (P & → & ¬ & Q) \\ 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 1 \end{matrix} .

As an abbreviation of ¬(F → ¬H), let us write

F ∧ H;

this is the conjunction of F and H.

Lemma 2.19. Show that:

(∗) F ∧ G ∼ G ∧ F;
(†) (F ∧ G) ∧ H ∼ F ∧ (G ∧ H);
(‡) F ∧ G → H ∼ F → G → H (here ∧ has priority over →).

Proof. Exercise.

Now we can write the equivalence (2.1) as

F_{0}, …, F_{n} ⊨ G ⟺ ⊨ (F_{0} ∧ … ∧ F_{n} → G).

Alternatively, if {F_{0}, …, F_{n}} = Σ, then instead of F_{0} ∧ … ∧ F_{n}, we can write

⋀ Σ;

this is the conjunction of Σ. Then

Σ ⊨ G ⟺ ⊨ (⋀ Σ → G),

provided Σ is finite. So we have a procedure to determine whether Σ ⊨ G, provided also that Σ is finite: just check whether ⋀ Σ → G is a tautology. What if Σ is infinite?

2.3 Soundness and Completeness

We aim to reduce the semantic notion of entailment to the syntactic notion of deducibility, by proving that our proof-system has the properties of: (∗) soundness: if Σ ⊢ F, then Σ ⊨ F; (†) completeness: if Σ ⊨ F, then Σ ⊢ F. Let us write

⊨ F

if α ⊨ F for all structures α; in this case, F can be called a validity. In the finitary case, soundness and completeness are now easy to prove: Lemma 2.20. The tautologies are precisely the validities:

⊢ F ⟺ ⊨ F.

Proof. The following are equivalent:

(∗) ⊢ F;

(†) F̂(e⃗) = 1 for all e⃗;

(‡) α ⊨ F for all structures α; (§) ⊨ F.

This completes the proof.

The reverse direction of the following can be called weak completeness: Theorem 2.21. If Σ is finite, then

Σ ⊢ F ⟺ Σ ⊨ F.

Proof. Suppose {G_{0}, …, G_{n−1}} ⊨ F. Then

Σ ⊢ F ⟺ ⊢ G_{0} → ⋯ → G_{n−1} → F [by the Deduction Theorem]
⟺ ⊨ G_{0} → ⋯ → G_{n−1} → F [by the last lemma]
⟺ Σ ⊨ F

by Lemma 2.17.

Another connexion between deducibility and entailment is now the following: Corollary 2.22. Σ is consistent if and only if every finite subset of Σ has a model.

Proof. If Σ is not consistent, then, by Lemma 2.13, some finite subset Σ_{0} of Σ is inconsistent. Then Σ_{0} ⊢ ¬(P → P) by Lemma 2.12, so Σ_{0} ⊨ ¬(P → P). But ¬(P → P) has no model, so Σ_{0} has no model. Conversely, if Σ_{0} is a finite subset of Σ with no model, then Σ_{0} ⊨ ¬(P → P), so Σ_{0} ⊢ ¬(P → P), whence Σ_{0} is inconsistent by Lemma 2.12.

Both implications in Theorem 2.21 are true generally:

Theorem 2.23 (Soundness). If Σ ⊢ F, then Σ ⊨ F.

Proof. Proof by strong induction on the length of deductions. Suppose the claim is true when F has a deduction of length less than n + 1 from Σ. Suppose G_{0}, …, G_{n−1}, F is a formal proof of F from Σ.

(∗) If ⊢ F, then ⊨ F by Lemma 2.20, so Σ ⊨ F.

(†) If F ∈ Σ, then Σ ⊨ F trivially.

(‡) If G_{j} is (G_{i} → F) for some i and j less than n, then Σ ⊨ G_{i} and Σ ⊨ (G_{i} → F) by inductive hypothesis, whence also Σ ⊨ F.

This completes the induction.

Theorem 2.24 (Completeness). If Σ ⊨ F, then Σ ⊢ F.

Proof. Suppose Σ ⊬ F; we shall show Σ ⊭ F. By Corollary 2.15, Σ ∪ {¬F } is consistent. Our proof, in outline, has three parts:

(0) There is a set Σ^{∗} of formulas such that:

• Σ ∪ {¬F } ⊆ Σ^{∗};

• Σ^{∗} is consistent;

• if G ∉ Σ^{∗}, then ¬G ∈ Σ^{∗}.

(1) Let the structure α be given by

α(P) = 1 ⟺ P ∈ Σ^{∗}.

Then

α ⊨ G ⟺ G ∈ Σ^{∗}  (2.2)

for all formulas G.

(2) Hence α ⊨ Σ^{∗}, so α ⊨ ¬F. Therefore α ⊭ F. This shows Σ ⊭ F.

Details of (0) and (1) are as follows:

(0) The infinite set Fm() of formulas is countable, that is, it can be written as {G_{n} : n ∈ ω} (exercise). We now recursively define a sequence (Σ_{n} : n ∈ ω) of sets of formulas:

(∗) Σ_{0} = Σ ∪ {¬F }.

(†) Σ_{n+1} = \begin{cases}Σ_{n} ∪ \{G_{n}\}, & if this is consistent; \\ Σ_{n}, & otherwise. \end{cases}

Then Σ = Σ_{0} ⊆ Σ_{1} ⊆ · · ·. Let Σ^{∗} = ⋃_{n∈ω} Σ_{n}. We can now establish the desired points:

• Obviously Σ ∪ {¬F } ⊆ Σ^{∗}.

• Suppose if possible that Σ^{∗} is inconsistent. Then some finite subset {H_{0}, …, H_{k}} is inconsistent, by Lemma 2.8. Each formula H_{i} is in some set Σ_{m(i)}. Let n = max{m(0), …, m(k)}. Then Σ_{n} is inconsistent. However, by induction, each of the sets Σ_{n} is consistent. Therefore Σ^{∗} is consistent.

• Finally, suppose G ∉ Σ^{∗}. Now, G is G_{n} for some n. Then Σ_{n} ∪ {G} is inconsistent, by definition of Σ_{n+1} and Σ^{∗}. Hence: (∗) Σ_{n} ⊢ ¬G, by Corollary 2.15; (†) Σ^{∗} ⊢ ¬G; (‡) Σ^{∗} ∪ {¬G} is consistent, by Lemmas 2.10 and 2.12, since Σ^{∗} is

consistent; (§) Σ_{m} ∪ {¬G} is consistent for all m.

But ¬G is G_{m} for some m. Hence ¬G ∈ G_{m+1} ⊆ Σ^{∗}.

By the consistency of Σ^{∗}, we now have

G ∉ Σ^{∗} ⟺ ¬G ∈ Σ^{∗}.

(1) We prove the equivalence (2.2) by induction on Fm(). It is trivially true if G is a variable, by definition of α. Suppose it is true if G is H or K. Then

α ⊨ ¬H ⟺ α ⊭ H ⟺ H ∉ Σ^{∗} ⟺ ¬H ∈ Σ^{∗},

and also

α ⊭ (H → K) ⟺ α ⊨ H & α ⊨ ¬K
⟺ H ∈ Σ^{∗} & ¬K ∈ Σ^{∗}
⟺ (H → K) ∉ Σ^{∗}.

(Exercise: why does the last equivalence hold?)

This completes the proof.

Note well the method of the proof: Given a consistent set of formulas, we extended it to a larger consistent set, Σ^{∗}, that determined the structure, α, that we wanted.

A set Σ of formulas can be called maximally consistent if:

(∗) Σ is consistent; and

(†) if Σ ⊆ Γ and Γ is consistent, then Σ = Γ.

Lemma 2.25. Suppose Σ is consistent. The following are equivalent:

(∗) Σ is maximally consistent.

(†) If G ∉ Σ, then ¬G ∈ Σ.

Proof. Exercise.

Our proof of the Completeness Theorem established and used the following result:

Porism 2.26. Every consistent set of formulas is included in a maximally consistent set.

The following can be proved as a corollary of Completeness:

Theorem 2.27 (Compactness). If every finite subset of Σ has a model, then Σ has a model.

Proof. Suppose every finite subset of Σ has a model. Then Σ is consistent by Lemma 2.22. Let F be a contradiction. Then Σ ⊬ F. Hence Σ ⊭ F. In particular, there is a model of Σ in which F is false.

Conversely, Completeness can be proved as a corollary of the Compactness Theorem (exercise).

2.4 Additional exercises

(1) Give a formal proof of H from F, G and (¬(F → ¬G) → H).

(2) On Fm(), let F ↦ F′ be the operation of ‘reversing the arrows,’ so that, for example,

(P → ¬(¬Q → R))′ is (¬(R → ¬Q) → P).

What is the precise recursive definition of the function F ↦ F′?

(3) Prove or disprove: Either Σ ⊨ F, or Σ ⊨ ¬F.

(4) Prove or disprove: If Σ ⊨ (F → G), then either Σ ⊨ ¬F or Σ ⊨ G.

We have introduced ∧ so that (F ∧ G) is an abbreviation of ¬(F → ¬G).

(5) Show that

(F → G) ∼ ¬(F ∧ ¬G).  (2.3)

Let (¬F → G) be abbreviated

(F ∨ G).

We can develop propositional logic in the signature {∧, ∨, ¬}. Let Fm′ be the set of formulas in this signature.

(6) Give a precise definition of Fm′.

(7) Define A ⊨ F for structures A and F in Fm′.

The definition of Σ ⊨ F is exactly as before, when Σ is a set of formulas in Fm′.

(8) Prove or disprove: If Σ ⊨ F or Σ ⊨ G, then Σ ⊨ (F ∨ G).

(9) Prove or disprove: If Σ ⊨ (F ∨ G), then Σ ⊨ F or Σ ⊨ G.

(10) Show that {∧, ¬} is an adequate signature.

Informally, we can define a unary operation F → F^{∗} on Fm′ so that F^{∗} is the result of interchanging ∧ and ∨ in F and of replacing every variable P with ¬P.

(11) Give a precise recursive definition of F ↦ F^{∗}.

(12) Show that F^{∗} ∼ ¬F for all F in Fm′.

First-order logic

Recall from § 1.2 the definitions and examples involving structures; these are the kinds of structures that we shall now be dealing with.

Let 𝔄 be a structure with signature L. So 𝔄 has universe A. We use c, R and f as syntactical variables for the constants, n-ary predicates and n-ary relations of L, respectively.

3.1 Terms

If k < n, then there is an n-ary operation

a⃗ ⟼ a_{k} : A^{n} ⟶ A  (3.1)

on A. This operation is projection onto the kth coordinate, and it can be defined regardless of the operations symbolized in L. Also, each element b in A determines, for each positive n, the constant n-ary operation

a⃗ ⟼ b : A^{n} ⟶ A.  (3.2)

If b is the interpretation of a constant in L, then that constant can be understood to symbolize the constant operation. All of the operations that are symbolized in L can be composed with one another, and with projections, to give other operations on A. The terms of L symbolize these possibilities. The symbols used in terms of L are:

(∗) the function-symbols f of L;

(†) the constants c of L;

(‡) (individual) variables, say from the set {x_{k} : k ∈ ω}; these will symbolize the projections.

Then the terms of L are defined inductively thus:

(∗) Each individual variable is a term of L.

(†) Each constant in L is a term of L.

(‡) If f is an n-ary function-symbol of L, and t_{0}, …, t_{n−1} are terms of L,

then the string

ft_{0} ⋯ f_{n−1}

is a term of L. (This is not generally a string of length n + 1; it is a string whose length is 1 more than the sum of the lengths of the strings t_{k}. If f is binary, then we may unofficially write the term as (t_{0} f t_{1}) instead of ft_{0}t_{1}.)

Let the set of terms of L be denoted

Tm_{L} .

As in propositional logic, so here, definition by recursion is possible, because of the following:

Theorem 3.1 (Unique Readability). Every term of L is uniquely

st_{0} ⋯ t_{n−1}

for some n in ω, some terms t_{k} of L (if n ≠ 0), and some s in L. If n ≠ 0, then s is an n-ary function-symbol of L; if n = 0, then s is a constant of L or a variable.

Proof. Exercise. (The proof can be developed as for Theorem 2.3.)

Note well that, by our definition, none of the symbols used in terms is a bracket.

If the variables in a term t come from {x_{k} : k < n}, then t is n-ary; the set of n-ary terms of L can be denoted

Tm_{L}^{n} .

Note then

Tm_{L}^{0} ⊆ Tm_{L}^{1} ⊆ Tm_{L}^{2} ⊆ · · · .

An n-ary term t of L determines an n-ary operation t^{𝔄} on A. The formal definition is recursive:

(∗) x_{k}^{𝔄} is a⃗ ↦ a_{k}, if k < n (as in (3.1)).

(†) c^{𝔄} is a⃗ ↦ c^{𝔄} (as in (3.2); here c is understood respectively as term and constant).

(‡) (ft_{0} ⋯ t_{n−1})^{𝔄} is

a⃗ ⟼ f^{𝔄}(t_{0}^{𝔄}(a⃗), …, t_{k−1}^{𝔄}(a⃗)),
that is, f^{𝔄} ∘ (t_{0}^{𝔄}, …, t_{k−1}^{𝔄}).

We have just extended the interpretation-function ℐ of 𝔄 so as to include a function

t ⟼ t^{𝔄} : Tm_{L}^{n} ⟶ A^{A^{n}}.  (3.3)

If t ∈ Tm_{L}^{0}, then t^{𝔄} = {(0, a)} for some a in A; but (as in ch. 1) we can then identify t^{𝔄} with a, and we can call t a constant term.

Suppose L ⊆ L′. An expansion of 𝔄 to L′ is a structure 𝔄′ whose signature is L′, and whose universe is A, such that

s^{𝔄′} = s^{𝔄}

for all s in L. Then 𝔄 is the reduct of 𝔄′ to L.

Example 3.2. The ring (ℤ, +, −, ·, 0, 1) is an expansion of the abelian group (ℤ, +, −, 0); the latter is a reduct of the former.

We can treat the elements of A as new constants (not belonging to L); adding these to L gives the signature L(A). Then 𝔄 has a natural expansion 𝔄_{A} to this signature, so that

a^{𝔄_{A}} = a

for all a in A. (Some writers prefer to define L(A) as L ∪ {c_{a} : a ∈ A}, and then to define c_{a}^{𝔄_{A}} = a.)

In fact, when it comes to interpreting terms (and, later, formulas), we always treat 𝔄 as if it were 𝔄_{A}. This means that every n-ary term t of L(A) has an interpretation t^{𝔄} in 𝔄 according to the definition above, provided we understand a^{𝔄} as a itself when a ∈ A. In other contexts, however, it will be important to distinguish clearly between 𝔄 and 𝔄_{A}. We shall also want to speak of expansions 𝔄_{X} of 𝔄, where X is an arbitrary subset of A.

If t is an n-ary term of L (or L(A)), and a⃗ ∈ A^{n}, then the result of replacing each x_{k} in t with a_{k}, for each k in n, can be written

t(a⃗);

this is a constant term of L(A). For a recursive definition, we have that t(a⃗) is:

(∗) a_{k}, if t is x_{k};

(†) c, if t is c;

(‡) ft_{0}(a⃗) ⋯ t_{k−1}(a⃗), if t is ft_{0} ⋯ f_{k−1}.

Thus we have defined a function

t ⟼ t(a⃗) : Tm_{L}^{n} ⟶ Tm_{L(A)}^{0} .  (3.4)

The tuple a⃗ also determines the function

g ⟼ g(a⃗) : A^{A^{n}} ⟶ A.  (3.5)

We now have several functions, in (3.3), (3.4) and (3.5), fitting together into a square:

\begin{matrix}Tm_{L}^{n} & ⟶^{a⃗} & Tm_{L(A)}^{0} \\ ^{ℐ}↓ & & ↓^{ℐ} \\ A^{A^{n}} & ⟶_{a⃗} & A \end{matrix}.

It doesn’t matter which way you go around:

Lemma 3.3. t^{𝔄}(a⃗) = t(a⃗)^{𝔄_{A}} for all n-ary terms of L, all L-structures 𝔄, and all n-tuples a⃗ from A.

Proof. The claim is perhaps obvious; but there is a proof by induction:

If t is x_{k}, then t^{𝔄}(a⃗) = a_{k}, and t(a⃗)^{𝔄_{A}} = a_{k}^{𝔄_{A}} = a_{k}.

If t is c, then t^{𝔄}(a⃗) = c^{𝔄}, while t(a⃗)^{𝔄_{A}} = c^{𝔄_{A}} = c^{𝔄}.

Finally, if the claim holds when t is any of terms t_{i}, and now t is ft_{0} ⋯ f_{k−1}, then we have

t^{𝔄}(a⃗) = f^{𝔄}(t_{0}^{𝔄}(a⃗), …, t_{k−1}^{𝔄}(a⃗))
= f^{𝔄}(t_{0}(a⃗)^{𝔄_{A}}, …, t_{k−1}(a⃗)^{𝔄_{A}})
= (ft_{0}(a⃗) ⋯ t_{k−1}(a⃗))^{𝔄_{A}}
= t(a⃗)^{𝔄_{A}}.

This completes the induction.

As an exercise, you can give a recursive definition of

t(u_{0}, …, u_{n−1}),

where t is an n-ary term, and the u_{k} are terms. What is the arity of the resulting term? Show that

t(u_{0}, …, u_{n−1})^{𝔄}(a⃗) = t^{𝔄}(u_{0}^{𝔄}(a⃗), …, u_{n−1}^{𝔄}(a⃗)).

Note then that, if t is n-ary, then t is precisely the term denoted

t(x_{0}, …, x_{n−1}).

Example 3.4. Let L be the signature of rings (with identity), and let 𝔄 be ℤ (or ℚ or ℝ or ℂ or some other infinite integral domain or field). If t is a term of L(A), then t^{𝔄} is a polynomial over A. What if 𝔄 is finite, say the 2-element field 𝔽_{2}? In that case, if t is x_{0} · (x_{0} + 1) or 0, then t^{𝔄}(a) = 0 for all a in A. However, x_{0} · (x_{0} + 1) and 0 do not represent the same polynomial, since they have different interpretations in fields (like 𝔽_{4}) that properly include 𝔽_{2}. (Here, 𝔽_{4} can be defined as 𝔽_{2}[X]/(X^{2} + 1).)

3.2 Formulas

As terms symbolize operations, so formulas will symbolize relations. Each formula φ of L will have an interpretation φ^{𝔄} that is a relation on A. When this relation is nullary and is in fact {∅}, that is, 1, then φ will be called true in 𝔄, and we shall write

𝔄 ⊨ φ.

Conversely, it is possible to define truth in structures first, and then interpretations. We shall look at both approaches.

So-called polynomial equations are examples of atomic formulas, which are the first kinds of formulas to be defined. From these, we shall define open formulas, and then arbitrary formulas.

Atomic formulas and their interpretations

The atomic formulas of L are of two kinds:

(∗) If t_{0} and t_{1} are terms of L, then t_{0} = t_{1} is an atomic formula of L. (Some

writers prefer to use a symbol like ≡ instead of =.) (†) If R is an n-ary predicate of L, and t_{0}, …, t_{n−1} are terms of L, then

Rt_{0} ⋯ t_{n−1} is an atomic formula of L. (If R is binary, then we may unofficially write (t_{0} R t_{1}) instead of Rt_{0}t_{1}.)

An atomic formula α can be called k-ary if the terms it is made from are k-ary.

A polynomial equation in two variables over ℝ has a solution-set, which can be considered as the interpretation of the equation. Likewise, arbitrary atomic formulas have solution-sets, which are their interpretations: If α is a k-ary atomic formula of L, then the interpretation in 𝔄 of α is the k-ary relation α^{𝔄} on A defined as follows. (Strictly, the validity of the definition depends on Theorem 3.5 below.)

(t_{0} = t_{1})^{𝔄} = {a⃗ ∈ A^{k} : t_{0}^{𝔄}(a⃗) = t_{1}^{𝔄}(a⃗)};  (3.6)
(Rt_{0} ⋯ R_{n−1})^{𝔄} = {a⃗ ∈ A^{k} : (t_{0}^{𝔄}(a⃗), …, t_{n−1}^{𝔄}(a⃗)) ∈ R^{𝔄}}.  (3.7)

As a special case, if k = 0, we have

(t_{0} = t_{1})^{𝔄} = 1 ⟺ t_{0}^{𝔄} = t_{1}^{𝔄};  (3.8)
(Rt_{0} ⋯ t_{n−1})^{𝔄} = 1 ⟺ (t_{0}^{𝔄}, …, t_{n−1}^{𝔄}) ∈ R^{𝔄}.  (3.9)

Note that the atomic formula t_{0} = t_{1} can be considered as the special case of Rt_{0} ⋯ t_{n−1} when n = 2 and R is =. We treat the special case separately because we consider the equals-sign to be always available for use in formulas, and we always interpret it as true equality.

Open formulas and their interpretations

We can treat atomic formulas as propositional variables, combining them to get open (or quantifier-free) formulas:

(∗) atomic formulas are open formulas; (†) if φ and χ are open formulas, then so are ¬φ and (φ → χ).

As with atomic formulas, so with arbitrary open formulas: they are k-ary if the terms they are built up from are k-ary. Hence, if φ and χ are k-ary open formulas, then so are ¬φ and (φ → χ). We can now define interpretations of k-ary open formulas by adding to (3.6) and (3.7) the following rules (again, Theorem 3.5 is required):

(¬φ)^{𝔄} = A^{k} ∖ φ^{𝔄} = (φ^{𝔄})^{c};  (3.10)
(φ → χ)^{𝔄} = A^{k} ∖ (φ^{𝔄} ∖ χ^{𝔄}) = (φ^{𝔄} ∖ χ^{𝔄})^{c}.  (3.11)

In particular, if k = 0, then:

(¬φ)^{𝔄} = 1 ⟺ φ^{𝔄} = 0;
(φ → χ)^{𝔄} = 0 ⟺ φ^{𝔄} = 1 & χ^{𝔄} = 0.

Formulas in general

Formulas in general may contain the existential quantifier ∃. The inductive definition of formula is:

(∗) atomic formulas are formulas; (†) if φ and χ are formulas, then so are ¬φ and (φ → χ); (‡) if φ is a formula, and x is a variable, then ∃x φ is a formula.

The possibility of defining the foregoing interpretations of open formulas depends on the following:

Theorem 3.5 (Unique Readability). Every formula of L is uniquely one of the following:

(∗) an equation t_{0} = t_{1}, for some terms t_{e} of L;

(†) a relational formula Rt_{0} ⋯ t_{n−1} for some terms t_{k} and n-ary predicate R of L, for some positive n; (‡) a negation ¬φ for some formula φ; (§) an implication (φ → χ) for some formulas φ and χ; (¶) an existential formula ∃x φ for some formula φ and some variable x.

Proof. Exercise.

Towards interpretations in general

In order to define interpretations of arbitrary formulas, we can still use (3.10) and (3.11) above to define (¬φ)^{𝔄} and (φ → χ)^{𝔄} in terms of φ^{𝔄} and χ^{𝔄}. However, we also must define (∃x φ)^{𝔄} in terms of φ^{𝔄}; and we must first define the arity ∃x φ in terms of the arity of φ. This is not quite so easy. We shall do it presently. When we are done, then, for every n-ary formula φ of L, there will be an n-ary relation φ^{𝔄} on A; this relation is defined by φ, and the relation can be called a 0-definable relation of 𝔄. The definable relations are those defined by formulas of L(A); more generally, if X ⊆ A, then the X-definable relations are those defined by formulas of L(X). (Singulary definable relations can just be called definable sets.)

If X and Y are k-ary definable relations of 𝔄, then so are X^{c}, X ∩ Y, X ∪ Y, &c. In short, all Boolean combinations of definable relations are definable, since {¬, →} is an adequate signature for propositional logic.

Now, if φ is an n-ary formula, defining as such the n-ary relation X, then we can also treat φ as (n + 1)-ary, defining the relation X × A on A. This relation is the set

{(a⃗ , b) ∈ A^{n+1} : a⃗ ∈ X}.

This set is also π^{−1}(X), where π is the function

(a⃗ , b) ⟼ a⃗ : A^{n+1} ⟶ A^{n};  (3.12)

this map is projection onto the first n coordinates. In short then, inverse images of definable sets under projections are definable. Using the quantifier ∃ in formulas will allow images under projections to be definable.

Indeed, suppose φ is an (n + 1)-ary formula. Then we can define (∃x_{n} φ)^{𝔄} to consist of those a⃗ in A^{n} such that there exists b in A such that (a⃗ , b) ∈ φ^{𝔄}. Hence (∃x_{n} φ)^{𝔄} is π′′(φ^{𝔄}), the image of φ^{𝔄}, where π is the projection in (3.12).

But what is (∃x_{i} φ)^{𝔄} here, if i < n? Defining this takes a bit more work; see Remark 3.8 below. Meanwhile, we can give an alternative approach to interpreting formulas:

Truth

Let Fm(L) be the set of formulas of L. We recursively define a function

φ ⟼ fv(φ) : Fm(L) ⟶ 𝒫({x_{k} : k ∈ ω})

as follows:

(∗) fv(α) is the set of variables in α, if α is atomic (for an exercise, this can be given a recursive definition);

(†) fv(φ → χ) = fv(φ) ∪ fv(χ);

(‡) fv(∃x φ) = fv(φ) ∖ {x}.

Then fv(φ) is the set of free variables of φ.

If fv(φ) = ∅, then φ is a sentence. So an atomic sentence α is a nullary atomic formula; in this case, we can define

𝔄 ⊨ α ⟺ α^{𝔄} = 1;  (3.13)

in either case, α is true in 𝔄. Otherwise, α is false in 𝔄, and we can write

𝔄 ⊭ α.

We can also define

𝔄 ⊨ ¬σ ⟺ 𝔄 ⊭ σ;  (3.14)
𝔄 ⊭ (σ → τ) ⟺ 𝔄 ⊨ σ & 𝔄 ⊨ ¬τ;  (3.15)

provided σ and τ are sentences for which truth and falsity in 𝔄 have been defined. To define 𝔄 ⊨ ∃v φ, we should assume that we have been working with formulas of L(A) all along, and we should define a kind of substitution:

For formulas φ, if x is a variable and t is a term, we define the formula

φ_{t}^{x}

recursively:

(∗) If α is atomic, then α_{t}^{x} is the result of replacing each occurrence of x in α with t (as an exercise, you can define this recursively);

(†) (¬φ)_{t}^{x} is ¬(φ_{t}^{x});

(‡) (φ → χ)_{t}^{x} is (φ_{t}^{x} → χ_{t}^{x});

(§) (∃x φ)_{t}^{x} is ∃x φ (no change);

(¶) (∃u φ)_{t}^{x} is ∃u φ_{t}^{x}, if u is not x.

Then φ_{t}^{x} is the result of replacing each free instance of x in φ with t. Now we can define

𝔄 ⊨ ∃x φ ⟺ 𝔄 ⊨ φ_{a}^{x} for some a in A.  (3.16)

We have now completed the definition of truth; it is expressed by lines (3.8), (3.9), (3.13), (3.14), (3.15) and (3.16).

Interpretations

If fv(φ) ⊆ {x_{k} : k < n}, then φ can be called n-ary, and we can write φ as

φ(x_{0}, …, x_{n−1}).

Then, instead of φ_{a_{0}}^{x_{0}} ⋯_{a_{n−1}}^{x_{n−1}}, we can write

φ(a_{0}, …, a_{n−1})

or φ(a⃗). (Here, a⃗ is a tuple of constants. We could let it be a tuple (t_{0}, …, t_{n−1}) of arbitrary terms; but then we should have to ensure that φ(t_{0}, …, t_{n−1}) is the result of simultaneously substituting each t_{k} for the free instances of the corresponding variable x_{k}.)

Lemma 3.6. Let φ be an n-ary formula of L.

(∗) If φ is atomic, then φ^{𝔄} = {a⃗ ∈ A^{n} : 𝔄 ⊨ φ(a⃗)}.

(†) If φ is ¬χ, then {a⃗ ∈ A^{n} : 𝔄 ⊨ φ(a⃗)} = {a⃗ ∈ A^{n} : 𝔄 ⊨ χ(a⃗)}^{c}.

(‡) If φ is (χ → ψ), then

{a⃗ ∈ A^{n} : 𝔄 ⊨ φ(a⃗)} = {a⃗ ∈ A^{n} : 𝔄 ⊨ χ(a⃗)}^{c} ∪ {a⃗ ∈ A^{n} : 𝔄 ⊨ ψ(a⃗)}.

(§) If φ is ∃x_{n} χ, then

{a⃗ ∈ A^{n} : 𝔄 ⊨ φ(a⃗)} = π′′({(a⃗ , b) ∈ A^{n+1} : 𝔄 ⊨ χ(a⃗ , b)}),

where π (as in (3.12)) is projection onto the first n coordinates.

Proof. Exercise.

Now we can define

φ^{𝔄} = {a⃗ ∈ A^{n} : 𝔄 ⊨ φ(a⃗)}

for all formulas φ.

In a formula of L(A), any constants from A can be called parameters. So the definable relations of 𝔄 are, more fully, the relations definable with parameters.

Example 3.7. Algebraic geometry studies the definable relations of ℂ and of other algebraically closed fields. It can be shown that, on ℂ, all definable relations are definable by open formulas. The model-theoretic expression for this fact is that the theory of algebraically closed fields admits elimination of quantifiers.

As an exercise, you can think about what are the definable sets of (1) the field ℂ;

(2) (ω, <, 0);

(3) (ω, <);

(4) (ω, s), if s is x ↦ x + 1;

(5) a set (that is, a structure in the empty signature).

You probably will not be able to prove your answers at this point. Remark 3.8. To complete our first approach to definable sets, let us ignore the ordering of ω. If I is a finite subset of ω, and if {i : x_{i} ∈ fv(φ)} ⊆ I, let us say that φ is I-ary. Let A^{I} be the set of functions from I to A, a typical such function being denoted

(a_{i} : i ∈ I).

The definition of φ^{𝔄} as a subset of A^{I} starts out as before. To define (∃x_{j} φ)^{𝔄}, let π_{j}^{I} be the function

(x_{i} : i ∈ I) ⟼ (x_{i} : i ∈ I ∖ {j}) : A^{I} ⟶ A^{I∖{j}}.

Now we can define

(∃x_{j} φ)^{𝔄} = (π_{j}^{I})′′(φ^{𝔄}).

But this doesn’t allow ∃v φ to be treated as J-ary when J contains j. So we should say in addition that if φ is I-ary, and J is any finite subset of ω, then the set

φ^{𝔄} × A^{J∖I}

is the interpretation of φ when considered as (I ∪J)-ary. Also, suppose {i : x_{i} ∈ fv(∃x_{j} φ)} ⊆ J. Then φ is (J ∪ {j})-ary, and we can define

(∃x_{j} φ)^{𝔄} = (π_{j}^{J∪{j}})′′(φ^{𝔄}) × A^{{j}∩J}.

This formulation of definable relations is rather complicated to be useful; the main point is that a geometric characterization of definable relations is possible:

Theorem 3.9. The family of 0-definable relations of a structure 𝔄 of L is the smallest family of relations on A that is closed under Boolean operations, Cartesian products, projections and permutations of coordinates; that contains the diagonal {(a, a) : a ∈ A}; and that contains the sets {c^{𝔄}}, R^{𝔄} and {(a_{0}, …, a_{n}) : f^{𝔄}(a_{0}, …, a_{n−1}) = a_{n}}.

3.3 Logical consequence

Having defined truth, we can define logical consequence. Let Sn_{L} be the set of sentences of L. The L-structure 𝔄 is a model of a subset Σ of Sn_{L} if each sentence in Σ is true in 𝔄; then we can write

𝔄 ⊨ Σ.

If a sentence σ is true in every model of Σ, then σ is a (logical) consequence of Σ, and we can write

Σ ⊨ σ.

If ∅ ⊨ σ, then we can write just

⊨ σ;

in this case, σ is a validity.

Two sentences are (logically) equivalent if each is a logical consequence of the other.

Lemma 3.10. Let σ and τ be sentences of L.

(∗) σ ⊨ τ if and only if ⊨ (σ → τ), for all σ and τ in Sn_{L}.

(†) σ and τ are equivalent if and only if ⊨ (σ → τ) ∧ (τ → σ).

(‡) Logical equivalence is an equivalence-relation on Sn_{L}.

Proof. Exercise.

Instead of the formula (φ → χ) ∧ (χ → φ), let us write

φ ↔ χ.

By the lemma, σ and τ are logically equivalent if and only if (σ ↔ τ) is a validity. We may blur the distinction between logically equivalent sentences, identifying σ with ¬¬σ for example.

Instead of ¬∃v ¬φ, we may write

∀v φ.

Then ¬∀v φ is (equivalent to) ∃v ¬φ.

Example 3.11. The sentence

(∀x (P x → Qx) → (∀x P x → ∀x Qx))

is a validity, where P and Q are unary predicates. To prove this, note that, by (3.15), it is enough to show that 𝔄 ⊨ (∀x P x → ∀x Qx) whenever 𝔄 ⊨ ∀x (P x → Qx). So suppose

𝔄 ⊨ ∀x (P x → Qx).  (3.17)

It is now enough to show that, if also 𝔄 ⊨ ∀x P x, then 𝔄 ⊨ ∀x Qx. So suppose

𝔄 ⊨ ∀x P x.  (3.18)

Let a ∈ A. Then 𝔄 ⊨ P a, by (3.18). But 𝔄 ⊨ (P a → Qa), by (3.17). Hence 𝔄 ⊨ Qa. Since a was arbitrary, we have 𝔄 ⊨ ∀x Qx.

If fv(φ) = {u_{0}, …, u_{n−1}}, and 𝔄 ⊨ ∀u_{0} ⋯ ∀u_{n−1} φ, we may write just

𝔄 ⊨ φ.

Here, the sentence ∀u_{0} ⋯ ∀u_{n−1} φ is the (universal) generalization of φ. Now we can define Σ ⊨ φ for arbitrary formulas φ (although Σ should still be a set of sentences); we can also say that arbitrary formulas φ and χ are (logically) equivalent if

⊨ (φ ↔ χ).

For the formula φ with free variables x_{0}, …, x_{n−1}, if we have

𝔄 ⊨ ∃u_{0} ⋯ ∃u_{n−1} φ,

then we can say that φ is satisfied in 𝔄.

It can happen then that 𝔄 ⊭ φ and 𝔄 ⊭ ¬φ. However, if σ is a sentence, then either σ or ¬σ is true in 𝔄.

Example 3.12. Each of the following formulas is true in every group:

x · (y · z) = (x · y) · z,
\begin{aligned}x · 1 & = x, \\ 1 · x & = x, \end{aligned}  \begin{matrix}x · x^{−1} = 1, \\ x^{−1} · x = 1. \end{matrix}

If Σ ⊆ Sn_{L}, let

Con_{L}(Σ) = {σ ∈ Sn_{L} : Σ ⊨ σ}.

Lemma 3.13. Con_{L}(Con_{L}(Σ)) = Con_{L}(Σ).

Proof. Since Σ ⊆ Con_{L}(Σ), we have Con_{L}(Σ) ⊆ Con_{L}(Con_{L}(Σ)). Suppose σ ∈ Con_{L}(Con_{L}(Σ)). Then Con_{L}(Σ) ⊨ σ. But if 𝔄 ⊨ Σ, then 𝔄 ⊨ Con_{L}(Σ), so in this case 𝔄 ⊨ σ. Thus σ ∈ Con_{L}(Σ).

A subset T of Sn_{L} is a theory of L if Con_{L}(T) = T. A subset Σ of a theory T is a set of axioms for T if

T = Con_{L}(Σ);

we may also say then that Σ axiomatizes T.

Example 3.14. The theory of groups is axiomatized by

∀x ∀y ∀z x · (y · z) = (x · y) · z,
\begin{aligned}∀x x · 1 & = x, \\ ∀x 1 · x & = x, \end{aligned}  \begin{matrix}∀x x · x^{−1} = 1, \\ ∀x x^{−1} · x = 1. \end{matrix}

If 𝔄 is an L-structure, let

Th(𝔄) = {σ ∈ Sn_{L} : 𝔄 ⊨ σ}.

Lemma 3.15. Th(𝔄) is a theory.

Proof. Say Th(𝔄) ⊨ σ. Since 𝔄 ⊨ Th(𝔄), we have 𝔄 ⊨ σ, so σ ∈ Th(𝔄).

We can now call Th(𝔄) the theory of 𝔄. Note that, if T is Th(𝔄), then

T ⊨ σ ⟺ T ⊭ ¬σ

for all sentences σ. An arbitrary theory T need not have this property; if it does, then T is complete. So, the theory of a structure is always complete. The converse holds, by the next lemma; also, the set Sn_{L} is a theory, but it is not complete:

Lemma 3.16. Let T be a theory of L.

(∗) If T has no model, then T is Sn_{L} itself.

(†) If T is complete, then T is Th(𝔄) for some structure 𝔄, which is a model of T.

(‡) If T has a model 𝔄, then T is included in Th(𝔄), which is a complete theory: in particular

T ⊨ σ ⟹ T ⊭ ¬σ

for all σ in Sn_{L}.

(§) Hence, to prove that T is complete, it is enough to show that T has models and

T ⊭ σ ⟹ T ⊨ ¬σ

for all σ in Sn_{L}.

Proof. Consider the points in order:

(∗) If T is a theory with no models, and σ is a sentence, then σ is true in every model of T, so T ⊨ σ, whence σ ∈ T.

(†) If T is complete, then by definition it cannot contain all sentences, so it must have a model 𝔄. Then T ⊆ Th(𝔄). By this and completeness of T, we have

T ⊨ σ ⟹ α ⊨ σ ⟹ α ⊭ ¬σ ⟹ T ⊭ ¬σ ⟹ T ⊨ σ

for all σ in Sn_{L}. In short, T ⊨ σ ⟺ 𝔄 ⊨ σ, so T = Th(𝔄).

(‡) The set {σ, ¬σ} has no models.

(§) Obvious.

This completes the proof.

We can also speak of the theory of a class of L-structures. If K is such a class, then Th(K) is the set of sentences of L that are true in every structure in K.

In particular, if Σ ⊆ Sn_{L}, then we can define

Mod(Σ)

to be the class of all models of Σ. Then

Th(Mod(Σ)) = Con_{L}(Σ).

Example 3.17. By definition, a group is just a model of the theory of groups, as axiomatized in Example 3.14. Hence this theory is Th(K), where K is the class of all groups.

3.4 Additional exercises

(1) Letting P and Q be unary predicates, determine, from the definition of ⊨, whether the following hold. (A method is shown in Example 3.11.) (∗) (∃x P x → ∃x Qx) ⊨ ∀x (P x → Qx); (†) (∀x P x → ∃x Qx) ⊨ ∃x (P x → Qx); (‡) ∃x (P x → Qx) ⊨ (∀x P x → ∃x Qx); (§) {∃x P x, ∃x Qx} ⊨ ∃x (P x ∧ Qx); (¶) ∃x P x → ∃y Qy ⊨ ∀x ∃y (P x → Qy).

(2) Let L = {R}, where R is a binary predicate, and let 𝔄 be the L-structure (ℤ, ⩽). Determine φ^{𝔄} if φ is: (∗) ∀x_{1} (Rx_{1}x_{0} → Rx_{0}x_{1}); (†) ∀x_{2} (Rx_{2}x_{0} ∨ Rx_{1}x_{2}).

(3) Let L be {S, P }, where S and P are binary function-symbols. Then (ℝ, +, ·) is an L-structure. Show that the following sets and relations are definable in this structure: (∗) {0}; (†) {1}; (‡) {a ∈ ℝ : 0 < a}; (§) {(a, b) ∈ ℝ^{2} : a < b}.

(4) Show that the following sets are definable in (ω, +, ·, ⩽, 0, 1):

(∗) the set of even numbers; (†) the set of prime numbers.

(5) Let R be the binary relation

{(x, x + 1) : x ∈ ℤ}

on ℤ. Show that R is 0-definable in the structure (ℤ, <); that is, find a binary formula φ in the signature {<} such that φ^{(ℤ,<)} = R.

Quantifier-elimination

In general, if we have some sentences, how might we show that the theory that they axiomatize is complete? If the theory is not complete, this is easy to show:

Example 4.1. The theory of groups is not complete, since the sentence

∀x ∀y xy = yx

is true (by definition) only in abelian groups, but there are non-abelian groups (such as the group of permutations of three objects). The theory of abelian groups is not complete either, since (in the signature {+, −, 0}) the sentence

∀x (x + x = 0 → x = 0)

is true in (ℤ, +, −, 0), but false in (ℤ/2ℤ, +, −, 0).

Let TO be the theory of strict total orders; this is axiomatized by the universal generalizations of:

¬(x < x),
x < y → ¬(y < x),
x < y ∧ y < z → x < z,
x < y ∨ y < x ∨ x = y.

This theory is not complete, since (ω, <) and (ℤ, <) are models of TO with different complete theories (exercise).

Let TO^{∗} be the theory of dense total orders without endpoints, namely, TO^{∗} has the axioms of TO, along with the universal generalizations of:

∃z (x < z ∧ z < y),
∃y y < x,
∃y x < y.

The theory TO^{∗} has a model, namely (ℚ, <). We shall show that TO^{∗} is complete. In order to do this, we shall first show that the theory admits (full) elimination of quantifiers.

An arbitrary theory T admits (full) elimination of quantifiers if, for every formula φ of L, there is an open formula χ of L such that

T ⊨ (φ ↔ χ)

—in words, φ is equivalent to χ modulo T.

Lemma 4.2. An L-theory T admits quantifier-elimination, provided that, if φ is an open formula, and v is a variable, then ∃v φ is equivalent modulo T to an open formula.

Proof. Use induction on formulas. Specifically:

Every atomic formula is equivalent modulo T to an open formula, namely itself.

Suppose φ is equivalent modulo T to an open formula α. Then T ⊨ (¬φ ↔ ¬α); but ¬α is open.

Suppose also χ is equivalent modulo T to an open formula β. Then

T ⊨ ((φ → χ) ↔ (α → β));

but (α → β) is open.

Finally, T ⊨ (∃v φ ↔ ∃v α) (exercise); but by assumption, ∃v α is equivalent to an open formula γ; so T ⊨ (∃v φ ↔ γ) (exercise). This completes the induction.

The lemma can be improved slightly. Every open formula is logically equivalent to a formula in disjunctive normal form:

⋁_{i<m} ⋀_{j<n} α_{i}^{(j)},

where each α_{i}^{(j)} is either an atomic or a negated atomic formula. (See § 2.6 of this year’s notes for Math 111.) This formula in disjunctive normal form can also be written

⋁_{i<m} ⋀ Σ_{i}

where Σ_{i} = {a_{i}^{(j)} : j < n}. Note that

⊨ (∃v ⋁_{i<m} ⋀ Σ_{i} ↔ ⋁_{i<m} ∃v ⋀ Σ_{i})  (4.1)

(exercise). The formulas ∃v ⋀ Σ_{i} are said to be primitive. In general, a primitive formula is a formula

∃u_{0} ⋯ ∃u_{n−1} ⋀ Σ,

where Σ is a finite non-empty set of atomic and negated atomic formulas. (Remember that ⋀ Σ is just an abbreviation for φ_{0} ∧ … ∧ φ_{n−1}, where the formulas φ_{i} compose Σ; so Σ must be finite since formulas must have finite length. Also, formulas have positive length, so Σ must be non-empty. However, the notation ⋀ ∅ could be understood to stand for a validity.)

Using (4.1), we can adjust the induction above to show that T admits quantifierelimination, provided that every primitive formula with one (existential) quantifier is equivalent modulo T to an open formula.

Henceforth suppose L is {<}, and TO ⊆ T; so T is a theory of total orders. Then we can improve Lemma 4.2 even more. Indeed, the atomic formulas of L now are x = y and x < y, where x and y are variables. Moreover,

TO ⊨ (¬(x < y) ↔ (x = y ∨ y < x)),
TO ⊨ (¬(x = y) ↔ (x < y ∨ y < x)).

Hence, in L, any formula is equivalent, modulo TO, to the result of replacing each negated atomic sub-formula with the appropriate disjunction of atomic formulas. If this replacement is done to a formula in disjunctive normal form, then the new formula will have a disjunctive normal form that involves no negations. So T admits quantifier-elimination, provided that every formula

∃v ⋀ Σ

is equivalent, modulo T, to an open formula, where now Σ is a set of atomic formulas.

Using this criterion, we shall show that TO^{∗} admits quantifier-elimination:

Theorem 4.3. TO^{∗} admits (full) elimination of quantifiers.

Proof. Let Σ be a finite, non-empty set of atomic formulas (in the signature {<}). Let X be the set of variables appearing in formulas in Σ; that is,

X = ⋃_{α∈Σ} fv(α).

Then X is a finite non-empty set; say

X = {x_{0}, …, x_{n}}.

Suppose 𝔄 is an L-structure, and a⃗ ∈ A^{n+1}. If α is an atomic formula of L with variables from X, we can let α(a⃗) be the result of replacing each x_{i} in α with a_{i}. Then we can let

Σ(a⃗) = {α(a⃗) : α ∈ Σ}.

Suppose in fact

𝔄 ⊨ TO ∪ {⋀ Σ(a⃗)}.

Let us define Σ_{(𝔄,a⃗)} as the set of atomic formulas α such that fv(α) ⊆ X and 𝔄 ⊨ α(a⃗). Then

Σ ⊆ Σ_{(𝔄,a⃗)}.

Moreover, once Σ has been chosen, there are only finitely many possibilities for the set Σ_{(𝔄,a⃗)}. Let us list these possibilities as

Σ_{0}, …, Σ_{m−1}.

Now, possibly m = 0 here. In this case,

TO ⊨ (∃v ⋀ Σ ↔ v ≠ v),

so we are done. Henceforth we may assume m > 0. If 𝔅 ⊨ TO ∪ {⋀ Σ(b⃗)}, then

𝔅 ⊨ ⋀ Σ_{i}(b⃗)

for some i in m. Therefore

TO ⊨ (⋀ Σ ↔ ⋁_{i<m} ⋀ Σ_{i}),

and hence

TO ⊨ (∃v ⋀ Σ ↔ ⋁_{i<m} ∃v ⋀ Σ_{i}).

Therefore, for our proof of quantifier-elimination, we may assume that Σ is one of the sets Σ_{(𝔄,a⃗)} (so that, in particular, m = 1).

Now partition Σ as Γ ∪ Δ, where no formula in Γ, but every formula in Δ, contains v. There are two extreme possibilities:

(∗) Suppose Γ = ∅. Then X = {v} (since if x ∈ X∖{v}, then (x = x) ∈ Γ). Also, Σ = Δ = {v = v}, so

⊨ (∃v ⋀ Σ ↔ v = v),

and we are done in this case.

(†) Suppose Δ = ∅. Then v ∉ X, and

⊨ (∃v ⋀ Σ ↔ ⋀ Σ),

so we are done in this case.

Henceforth, suppose neither Γ nor Δ is empty. Then

⊨ (∃v ⋀ Σ ↔ ⋀ Γ ∧ ∃v ⋀ Δ).

We shall show that

TO^{∗} ⊨ (∃v ⋀ Σ ↔ ⋀ Γ),  (4.2)

which will complete the proof. To show (4.2), it is enough to show

TO^{∗} ⊨ (⋀ Γ → ∃v ⋀ Δ).

But this follows from the definition of TO^{∗}:

Indeed, remember that Σ is Σ_{(𝔄,a⃗)}. Hence, for all i and j in n + 1, we have

a_{i} < a_{j} ⟺ (x_{i} < x_{j}) ∈ Σ;
a_{i} = a_{j} ⟺ (x_{i} = x_{j}) ∈ Σ.

We have v ∈ X. We can relabel the elements of X as necessary so that v is x_{n} and

a_{0} ⩽ … ⩽ a_{n−1}.

(Here, a_{i} ⩽ a_{i+1} means a_{i} < a_{i+1} or a_{i} = a_{i+1} as usual.) Suppose 𝔅 ⊨ TO^{∗}, and B^{n} contains b⃗ such that 𝔅 ⊨ ⋀ Γ(b⃗). We have to show that there is c in B such that 𝔅 ⊨ ⋀ Δ(b⃗ , c). Now, for all i and j in n, we have

b_{i} < b_{j} ⟺ a_{i} < a_{j};
b_{i} = b_{j} ⟺ a_{i} = a_{j}.

Because 𝔅 is a model of TO^{∗} (and not just TO), we can find c as needed according to the relation of a_{n} with the other a_{i}:

(∗) If a_{n} = a_{i} for some i in n, then let c = b_{i}.
(†) If a_{n−1} < a_{n}, then let c be greater than b_{n−1}.
(‡) If a_{n} < a_{0}, then let c be less than b_{0}.
(§) If a_{k} < a_{n} < a_{k+1}, then we can let c be such that b_{k} < c < b_{k+1}.

This completes the proof that TO^{∗} admits quantifier-elimination.

We have proved more than quantifier-elimination: we have shown that, modulo TO^{∗}, the formula ∃v ⋀ Σ is equivalent to v ≠ v or v = v or an open formula with the same free variables as ∃v ⋀ Σ. In the proof, we introduced v ≠ v simply as a formula φ such that 𝔄 ⊭ φ for every structure 𝔄. Such a formula corresponds to a nullary Boolean connective, namely an absurdity (the negation of a validity). We used 0 as such a connective; but let us now use ⊥.

Likewise, instead of v = v, we can use, as a validity, the nullary Boolean connective ⊤. From the last proof, therefore, we have:

Porism 4.4. In the signature {<}, with the nullary connectives ⊥ and ⊤ allowed, every formula is equivalent modulo TO^{∗} to an open formula with the same free variables.

In a signature of first-order logic without constants, an open sentence consists entirely of Boolean connectives, with no propositional variables; so it is either an absurdity or a validity. As a consequence, we have:

Theorem 4.5. TO^{∗} is a complete theory.

Proof. By the porism, every sentence is equivalent to an open sentence; as just noted, such a sentence is an absurdity or a validity. Suppose TO^{∗} ⊨ (σ ↔ ⊥). But ⊨ (σ ↔ ⊥) ↔ ¬σ; so TO^{∗} ⊨ ¬σ. Similarly, if TO^{∗} ⊨ (σ ↔ ⊤), then TO^{∗} ⊨ σ. Hence, for all sentences σ, if TO^{∗} ⊭ σ, then TO^{∗} ⊨ ¬σ. Therefore TO^{∗} is complete by Lemma 3.16.

Relations between structures

There are several binary relations on the class of structures in a signature L. Some relations involve universes of structures; others do not.

Let 𝔄 and 𝔅 be L-structures.

5.1 Fundamental definitions

The structure 𝔄 is a substructure of 𝔅, or 𝔅 is an extension of 𝔄, if A ⊆ B and

(∗) c^{𝔄} = c^{𝔅} for all constants c of L;

(†) R^{𝔄} = A^{n} ∩ R^{𝔅} for all n-ary predicates R of L, for all positive n in ω;

(‡) f^{𝔄} = f^{𝔅} ∘ id_{A^{n}} for all n-ary function-symbols f of L, for all positive n in ω.

In this case, we write

𝔄 ⊆ 𝔅.

Immediately, 𝔄 ⊆ 𝔅 if and only if A ⊆ B and

𝔄 ⊨ σ ⟺ 𝔅 ⊨ σ  (5.1)

for all atomic sentences σ of L(A) of one of the forms

a_{0} = c,
Ra_{0} ⋯ a_{n−1},
fa_{0} ⋯ a_{n−1} = a_{n}.

The two structures 𝔄 and 𝔅 are called elementarily equivalent if (5.1) holds for all sentences σ of L (not L(A)). In this case, we write

𝔄 ≡ 𝔅.

Then the relation ≡ of elementary equivalence is in fact the equivalencerelation induced on the class of L-structures by the function 𝔐 ↦ Th(𝔐); that is,

𝔄 ≡ 𝔅 ⟺ Th(𝔄) = Th(𝔅).

All models of a complete theory are elementarily equivalent, and first-order logic provides no means to distinguish between elementarily equivalent structures. We shall see other possible ways to distinguish between them.

5.2 Additional definitions

The structure 𝔄 is an elementary substructure of 𝔅, and 𝔅 is an elementary extension of 𝔄, if A ⊆ B and 𝔄_{A} ≡ 𝔅_{A}. Then we write

𝔄 ≼ 𝔅.

(Some people prefer just to write 𝔄 ≺ 𝔅.) Note here that 𝔄_{A} ≡ 𝔅_{A} if and only if (5.1) holds for all sentences σ of L(A). In particular, elementary substructures are substructures.

Various functions between (universes of) structures are possible. To describe them, it is convenient to use the following convention. If h is a function from A to B, we also understand h as the function from A^{n} to B^{n} given by

h(a⃗) = h(a_{0}, …, a_{n−1}) = (h(a_{0}), …, h(a_{n−1})),  (5.2)

for each n in ω. In particular, as a function from A^{0} to B^{0}, h is {(0, 0)}.

The structure 𝔄 embeds in 𝔅 if there is an injection h from A to B such that:

(∗) h(c^{𝔄}) = c^{𝔅} for all constants c in L; (†) h′′(R^{𝔄}) = h′′(A^{n}) ∩ R^{𝔅} for all n-ary predicates R in L, for all positive n

in ω; (‡) h ∘ f^{𝔄} = f^{𝔅} ∘ h for all n-ary function-symbols f in L, for all positive n

in ω.

Then h is an embedding of 𝔄 in 𝔅; to express this, we can write

h : 𝔄 ⟶ 𝔅.

Immediately, h : 𝔄 → 𝔅 if and only if h : A → B and

𝔄 ⊨ φ(a⃗) ⟺ 𝔅 ⊨ φ(h(a⃗)), for all a⃗ from A,  (5.3)

for all atomic formulas φ of L of one of the forms

x_{0} = x_{1},
x_{0} = c,
Rx_{0} ⋯ x_{n−1},
fx_{0} ⋯ x_{n−1} = x_{n}.

If (5.3) holds for all formulas φ of L, then h is an elementary embedding of 𝔄 in 𝔅, and we can write

h : 𝔄 ⟶^{≡} 𝔅.

Example 5.1. The map x ↦ x/1 is an embedding of the ring ℤ in the field ℚ, but not an elementary embedding, since ℤ ⊨ φ(1), but ℚ ⊭ φ(1/1), where φ is ¬∃y y + y = x.

If h : 𝔄 → 𝔅 and h is a surjection onto B, then h is called an isomorphism from 𝔄 to 𝔅, and we can write

h : 𝔄 ⟶^{≅} 𝔅.

If an isomorphism from 𝔄 to 𝔅 exists, then 𝔄 is isomorphic to 𝔅, and we can write

𝔄 ≅ 𝔅;

the relation ≅ can be called isomorphism.

5.3 Implications

Lemma 5.2. Isomorphism is an equivalence-relation. If h : 𝔄 →^{≅} 𝔅, then

h^{−1} : 𝔅 →^{≅} 𝔄.

Proof. Exercise.

Isomorphic structures are practically the same. One way to make this precise is by means of the following:

Lemma 5.3. Suppose h : 𝔄 → 𝔅. Then (5.3) holds for all atomic formulas φ of L. If also h is onto B, then (5.3) holds for all formulas φ of L.

Proof. Note that (5.3) can be re-formulated in other ways, according to taste:

a⃗ ∈ φ^{𝔄} ⟺ h(a⃗) ∈ φ^{𝔅}, for all n-tuples a⃗ from A,  (5.4)

or more simply

h′′(φ^{𝔄}) = h′′(A^{n}) ∩ φ^{𝔅}.

To prove it, assuming h : 𝔄 → 𝔅, we first establish by induction that

h ∘ t^{𝔄} = t^{𝔅} ∘ h  (5.5)

for all terms t of L:

(∗) (5.5) is true by definition if t is a constant or variable;

(†) if (5.5) is true when t ∈ {u_{0}, …, u_{n−1}}, and now t is fu_{0} ⋯ u_{n−1}, then

h ∘ t^{𝔄} = h ∘ f^{𝔄} ∘ (u_{0}^{𝔄}, …, u_{n−1}^{𝔄})  [by def’n of t^{𝔄}]
= f^{𝔅} ∘ h ∘ (u_{0}^{𝔄}, …, u_{n−1}^{𝔄})  [by def’n of ⊆]
= f^{𝔅} ∘ (h ∘ u_{0}^{𝔄}, …, h ∘ u_{n−1}^{𝔄})  [by (5.2)]
= f^{𝔅} ∘ (u_{0}^{𝔅} ∘ h, …, u_{n−1}^{𝔅} ∘ h)  [by inductive hyp.]
= f^{𝔅} ∘ (u_{0}^{𝔅}, …, u_{n−1}^{𝔅}) ∘ h
= t^{𝔅} ∘ h.  [by def’n of t^{𝔄}]

Therefore (5.5) holds for all t. Now we turn to (5.4). To prove it for open formulas, we observe:

(∗) If φ is t_{0} = t_{1} for some terms t_{i}, then

a⃗ ∈ φ^{𝔄} ⟺ t_{0}^{𝔄}(a⃗) = t_{1}^{𝔄}(a⃗)  [by definition of φ^{𝔄}]
⟺ h(t_{0}^{𝔄}(a⃗)) = h(t_{1}^{𝔄}(a⃗))  [since h is injective]
⟺ t_{0}^{𝔅}(h(a⃗))) = t_{1}^{𝔅}(h(a⃗)))  [by (5.5)]
⟺ h(a⃗) ∈ φ^{𝔅}.  [by definition of φ^{𝔅}]

(†) If φ is Rt_{0} ⋯ t_{n−1} for some terms t_{i} and predicate R, then:

a⃗ ∈ φ^{𝔄} ⟺ (t_{0}^{𝔄}(a⃗), …, t_{n−1}^{𝔄}(a⃗)) ∈ R^{𝔄}  [by def’n of φ^{𝔄}]
⟺ h(t_{0}^{𝔄}(a⃗), …, t_{n−1}^{𝔄}(a⃗)) ∈ R^{𝔅}  [by def’n of isom.]
⟺ (t_{0}^{𝔅}(h(a⃗)), …, t_{n−1}^{𝔅}(h(a⃗))) ∈ R^{𝔅} [by (5.5)]
⟺ h(a⃗) ∈ φ^{𝔅}.  [by def’n of φ^{𝔅}]

(‡) If (5.4) holds when φ is χ, and now φ is ¬χ, then:

a⃗ ∈ φ^{𝔄} ⟺ a⃗ ∉ χ^{𝔄}  [by def’n of φ^{𝔄}]
⟺ h(a⃗) ∉ χ^{𝔅}  [by inductive hypothesis]
⟺ h(a⃗) ∈ φ^{𝔅}.  [by def’n of φ^{𝔅}]

(§) Similarly, if (5.4) holds when φ is χ or ψ, and now φ is (χ → ψ), then:

a⃗ ∉ φ^{𝔄} ⟺ a⃗ ∈ χ^{𝔄} & a⃗ ∉ ψ^{𝔄}  [by def’n of φ^{𝔄}]
⟺ h(a⃗) ∈ χ^{𝔅} & h(a⃗) ∉ ψ^{𝔅} [by inductive hypothesis]
⟺ h(a⃗) ∉ φ^{𝔅}.  [by def’n of φ^{𝔅}]

Finally, to establish (5.4) in case h is surjective, suppose (5.4) holds when φ is an (m + 1)-ary formula χ, and now φ is the m-ary ∃x_{m} χ. We have

a⃗ ∈ φ^{𝔄} ⟺ (a⃗ , b) ∈ χ^{𝔄} for some b in A
⟺ (h(a⃗), h(b)) ∈ χ^{𝔅} for some b in A
⟺ (h(a⃗), c) ∈ χ^{𝔅} for some c in A
⟺ h(a⃗) ∈ φ^{𝔅}

(Note how the surjectivity of h was used.) This completes the proof.

As an immediate consequence, we have:

Theorem 5.4. If 𝔄 ≅ 𝔅, then 𝔄 ≡ 𝔅.

For other consequences, we first observe:

Lemma 5.5. If h : 𝔄 → 𝔅, then h(A) is the universe of a structure h(𝔄) such

that h : 𝔄 →^{≅} h(𝔄) and h(𝔄) ⊆ 𝔅.

Proof. Exercise.

Theorem 5.6. Suppose h : 𝔄 → 𝔅. Then 𝔄 ⟶^{≡} 𝔅 if and only if h(𝔄) ≼ 𝔅.

Let the diagram of 𝔄 be the set of open sentences of Th(𝔄_{A}); this set can be denoted

diag 𝔄.

Then we can give the following characterization of the relations ⊆ and ≼:

Theorem 5.7. Suppose h : A → B, and 𝔅^{∗} is the expansion of 𝔅 to L(A) such that

a^{𝔅^{∗}} = h(a)  (5.6)

for all a in A. Then

𝔅^{∗} ⊨ diag 𝔄 ⟺ h : 𝔄 → 𝔅;  (5.7)
𝔅^{∗} ⊨ Th(𝔄_{A}) ⟺ h : 𝔄 →^{≡} 𝔅.  (5.8)

In particular, if A ⊆ B, then

𝔅 ⊨ diag 𝔄 ⟺ 𝔄 ⊆ 𝔅;
𝔅 ⊨ Th(𝔄_{A}) ⟺ 𝔄 ≼ 𝔅.

Proof. Note that 𝔅^{∗} ⊨ φ(a⃗) ⟺ 𝔅 ⊨ φ(h(a⃗)). The points about elementary embeddings and substructures follow from the definitions; about embeddings and substructures, from Lemma 5.3.

Corollary 5.8. If T is a theory admitting quantifier-elimination, then all embeddings of models of T are elementary embeddings.

Proof. If T admits quantifier-elimination and 𝔄 ⊨ T, then diag 𝔄 ⊨ Th(𝔄_{A}).

Model-theory is interesting because not all elementarily equivalent structures are isomorphic:

Example 5.9. We know that Th(ℚ, <) = TO^{∗}. Since also (ℝ, <) ⊨ TO^{∗}, we have (ℝ, <) ≡ (ℚ, <); however, (ℚ, <) ≅ (ℝ, <), simply because ℝ is uncountable, so there is no bijection at all between ℚ and ℝ.

5.4 Categoricity

The cardinality of a structure 𝔄 is the cardinality |A| of its universe A. Let κ be an infinite cardinality. A theory T is called κ-categorical if

(∗) T has a model of cardinality κ;

(†) all models of T of cardinality κ are isomorphic (to each other).

Example 5.10. We shall prove later, in Theorem 8.2, that TO^{∗} is ω-categorical.

A theory is totally categorical if it is κ-categorical for each κ.

Example 5.11. In the empty signature, structures are pure sets, and isomorphisms are just bijections. Hence, if L = ∅, then Con_{L}(∅) is totally categorical.

There are sentences σ_{n} (where n > 0) in the empty signature such that, for all theories T and structures 𝔄 of some common signature,

𝔄 ⊨ T ∪ {σ_{n} : n > 0} ⟺ 𝔄 ⊨ T & |A| ⩾ ω.

Indeed, let σ_{n} be

∃x_{0} ⋯ ∃x_{n−1} ⋀_{i<j<n} x_{i} ≠ x_{j}.

Moreover, for any formula φ with at most one free variable, x, if n > 1, we can form the sentence

∃x_{0} ⋯ ∃x_{n−1} ( ⋀_{i<j<n} x_{i} ≠ x_{j} ∧ ⋀_{i<n} φ(x_{i}));

this sentence can be abbreviated

∃^{⩾n}x φ.

Then

𝔄 ⊨ ∃^{⩾n}x φ ⟺ |φ^{𝔄}| ⩾ n.

Example 5.12. Suppose L = {E}, where E is a binary predicate, and let T be the theory of equivalence-relations with exactly two classes, both infinite. So T has the axioms:

∀x x E x;
∀x ∀y (x E y → y E x);
∀x ∀y ∀z (x E y ∧ y E z → x E z);
∃x ∃y ∀z (¬(x E y) ∧ (x E z ∨ y E z))
∀x ∃^{⩾n}y x E y

for each n greater than 1. Then T is ω-categorical. However, if κ is an uncountable cardinal, then T is not κ-categorical. For example, there is a model in which both E-classes have size ω_{1} (that is, ℵ_{1}), and a model in which one class has size ω_{1}, the other ω.

In a countable signature, there are at most |2^{ω}|—that is, continuum-many— structures with a given countable universe A, because each symbol in the signature will be interpreted as a subset of some A^{n}, and there are at most continuummany of these.

The spectrum-function is

(T, κ) ⟼ I(T, κ),

where T is a theory,κ is an infinite cardinal, and I(T, κ) is the number of nonisomorphic models of T of size κ. A theory in a countable signature is also called countable. If T is countable, then we have

1 ⩽ I(T, ω) ⩽ |2^{ω}|.  (5.9)

We’ve seen in Examples 5.10 and 5.11 that the lower bound cannot be improved. Vaught’s conjecture is that

I(T, ω) < |2^{ω}| ⟹ I(T, ω) ⩽ ω.

If the Continuum Hypothesis is accepted, than this implication is trivial; the Conjecture is that the implication holds even if the Continuum Hypothesis is rejected.

The upper bound of (5.9) cannot be improved:

Example 5.13. Let L be {P_{n} : n ∈ ω}, where each P_{n} is a unary predicate. Let T have the following axioms, where I and J are finite disjoint subsets of ω:

∃x (⋀_{i∈I} P_{i}x ∧ ⋀_{j∈J} ¬P_{j}x).

In the same way that we proved TO^{∗} admitted quantifier-elimination and was complete, we can prove that T admits QE and is complete. But T has continuum-many countably infinite models. Indeed, T has a model 𝔄, where A = 2^{ω}, and

P_{n}^{𝔄} = {σ ∈ A : s(n) = 1}.

We could replace A with the set A_{0} of σ in 2^{ω} such that, for some k, if n ⩾ k, then σ(n) = 0. This A_{0} is countable. In fact there is an injection from A_{0} into 2^{<ω}, where

2^{<ω} = ⋃_{n∈ω} 2^{n}.

This set is partially ordered by ⊆ and is a tree. A branch of this tree is a maximal totally ordered subset; the union of a branch is an element of 2^{ω}. If σ and τ are distinct elements of 2^{ω}, then σ(n) ≠ τ(n) for some n in ω, and then

σ ∈ P_{n}^{𝔄} ⟺ τ ∉ P_{n}^{𝔄}.

Hence, if also σ and τ are not in A_{0}, then A_{0} ∪ {σ} and τ ∪ {τ} determine non-isomorphic models of T. Hence T has at least (and therefore exactly) continuum-many countable models, since |2^{ω} ∖ A_{0}| = |2^{ω}|.

For those who know some algebra:

Examples 5.14. As examples of complete T where I(T, ω) = ω, we have:

(∗) the theory of torsion-free divisible abelian groups;

(†) ACF_{0}, the theory of algebraically closed fields of characteristic 0.

Compactness

We now aim to prove compactness for first-order logic. A subset Σ of Sn_{L} is

(∗) satisfiable if it has a model;

(†) finitely satisfiable if every finite subset of Σ has a model.

Compactness is that every finitely satisfiable set is satisfiable.

Lemma 6.1. If Σ is finitely satisfiable, but Σ ∪ {σ} is not, then Σ ∪ {¬σ} is.

Proof. Say Σ_{0} is a finite subset of Σ such that Σ_{0} ∪ {σ} has no model. Then Σ_{0} ⊨ ¬σ. Say Σ_{1} is another finite subset of Σ. Then Σ_{0} ∪ Σ_{1} has a model in which ¬σ is true.

In proving the Completeness Theorem for propositional logic, we start from a set Σ of propositional formulas from which a formula F cannot be derived. Then Σ∪{¬F } is consistent. We find a maximal consistent set Σ^{∗} that includes Σ ∪ {¬F }. From Σ^{∗} we define a structure A that is a model of Σ in which F is false.

We can try to do something similar to prove compactness for first-order logic. Suppose Σ is a maximal finitely satisfiable set of first-order formulas in some signature L. (In particular then, σ ∈ Σ ⟺ ¬σ ∉ Σ.) We can try to define an L-structure 𝔄 by letting:

(∗) A be the set of constants in L;

(†) c^{𝔄} = c for every constant c in L;

(‡) f^{𝔄}(c_{0}, …, c_{n−1}) = d ⟺ (fc_{0} ⋯ c_{n−1} = d) ∈ Σ;

(§) (c_{0}, …, c_{n−1}) ∈ R^{𝔄} ⟺ Rc_{0} ⋯ c_{n−1} ∈ Σ.

We want 𝔄 to be a model of Σ. There are three problems:

(∗) The signature L might not contain any constants.

(†) Suppose L does contain constants c and d. We have 𝔄 ⊨ (c = d) ⟺ c^{𝔄} = d^{𝔄} ⟺ c = d. So 𝔄 can’t be a model of Σ unless either Σ does not contain (c = d), or c and d are the same symbol.

(‡) If 𝔄 ⊨ ¬φ_{c}^{x} for every constant c in L, then 𝔄 ⊨ ¬∃x φ. However, possibly Σ contains all of the formulas ¬φ_{c}^{x}, but also ∃x φ.

The solution to these problems is as follows:

(∗) We expand L to a signature L′ that contains infinitely many constants. Then we enlarge Σ to a maximal finitely satisfiable subset Σ′ of Sn_{L′}.

(†) Letting C be the set of constants of L′, we define an equivalence-relation

E on C by

c E d ⟺ (c = d) ∈ Σ′.

Then we let A be, not C, but C/E.

(‡) In enlarging Σ to Σ′, we ensure that, if ∃x φ ∈ Σ′, then φ_{c}^{x} ∈ Σ′ for some c in C.

Theorem 6.2 (Compactness for first-order logic). Every finitely satisfiable set of formulas (in some signature) is satisfiable.

Proof. Suppose Σ is a finitely satisfiable subset of Sn_{L}. Let C be a set of new constants (so L ∩ C = ∅). For any L-structure 𝔄, there is some a in A; so we can expand 𝔄 to an L ∪ C-structure 𝔄′ by defining

c^{𝔄′} = a

for all c in C. In particular, Σ is still finitely satisfiable as a set of sentences of L′.

We’ll assume that L is countable (although the general case would proceed similarly). So we can enumerate Sn_{L∪C} as {σ_{n} : n ∈ ω}, and C as {c_{n} : n ∈ ω}. We shall define a chain

Σ_{0} ⊆ Σ_{1} ⊆ Σ_{2} ⊆ ⋯,

where each Σ_{k} is finitely satisfiable, and only finitely many constants in C appear in formulas in Σ_{k}. The recursive definition is the following:

(∗) Σ_{0} = Σ. (By assumption, Σ_{0} is finitely satisfiable, and it contains no constants of C.)

(†) Assume Σ_{2n} has been defined as required. Then define

Σ_{2n+1} = \begin{cases}Σ_{2n} ∪ \{σ_{n}\}, & if this is finitely satisfiable; \\ Σ_{2n}, & if not. \end{cases}

Then Σ_{2n+1} is as required.

(‡) Suppose Σ_{2n+1} has been defined as required. Suppose also σ_{n} ∈ Σ_{2n+1}, and σ_{n} is ∃x φ for some φ. The set of m such that c_{m} does not appear in a formula in Σ_{2n+1} has a least element, k. Then the set Σ_{2n+1} ∪ {φ_{c_{k}}^{x}} is finitely satisfiable. For, if Γ is a finite subset of Σ_{2n+1}, then it has a model 𝔄. Then 𝔄 ⊨ φ_{a}^{x} for some a in A; so we can expand 𝔄 to a model of Σ_{2n+1} ∪ {φ_{c_{k}}^{x}} by interpreting c_{k} as a. In this case we define

Σ_{2n+2} = Σ_{2n+1} ∪ {φ_{c_{k}}^{x}};

otherwise, let Σ_{2n+2} = Σ_{2n+1}. In either case, Σ_{2n+2} is as desired.

Now we define

Σ^{∗} = ⋃_{n∈ω} Σ_{n}.

This is finitely satisfiable, since each finite subset is a subset of some Σ_{n}. Suppose Σ^{∗} ∪ {σ} is finitely satisfiable. But σ is σ_{n} for some n, and Σ_{2n} ∪ {σ} is finitely satisfiable, so σ ∈ Σ_{2n+1}, and σ ∈ Σ^{∗}. So Σ^{∗} is a maximal finitely satisfiable set.

We now define a structure 𝔄 of L ∪ C that will turn out to be a model of Σ:

We first define

E = {(c, d) ∈ C^{2} : (c = d) ∈ Σ^{∗}}.

Then E is an equivalence-relation on C (exercise). So, we can let

A = C/E.

Let the E-class of c be denoted [c]. We can define

c^{𝔄} = [c].

If R is an n-ary predicate in L, we define

R^{𝔄} = {([c_{0}], …, [c_{n−1}]) ∈ A^{n} : (Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗}}.

This means

(Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗} ⟹ ([c_{0}], …, [c_{n−1}]) ∈ R^{𝔄}.

In fact the converse holds too; that is,

c_{0} E d_{0} & … & c_{n−1} E d_{n−1} & (Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗} ⟹ (Rd_{0} ⋯ d_{n−1}) ∈ Σ^{∗}

(exercise). If f is an n-ary function-symbol in L, then (∃x fc_{0} ⋯ c_{n−1} = x) ∈ Σ^{∗} (since the sentence is true in every structure), so (fc_{0} ⋯ c_{n−1} = d) ∈ Σ^{∗} for some d in C. Moreover,

c_{0} E c′_{0} & … & c_{n−1} E c′_{n−1} & (fc_{0} ⋯ c_{n−1} = d) ∈ Σ^{∗} & (fc′_{0} ⋯ c′_{n−1} = d′) ∈ Σ^{∗} ⟹ d E d′

(exercise). Hence we can define

f^{𝔄} = {([c_{0}], …, [c_{n−1}], [d]) ∈ A : (fc_{0} ⋯ c_{n−1} = d) ∈ Σ^{∗}}.

Note then

f^{𝔄}[c_{0}] ⋯ [c_{n−1}] = [d] ⟺ (fc_{0} ⋯ c_{n−1} = d) ∈ Σ^{∗}

(exercise). Finally, if c is a constant of L, we can consider it as a nullary function-symbol, obtaining the interpretation

c^{𝔄} = [d] ⟺ (c = d) ∈ Σ^{∗}.

So we have 𝔄. It remains to show 𝔄 ⊨ Σ^{∗}. We shall do this by showing

𝔄 ⊨ σ ⟺ σ ∈ Σ^{∗}  (6.1)

for all sentences σ of L ∪ C, by induction on the length of σ.

We need a preliminary observation: If t is a term with no variables, and c ∈ C, then

t^{𝔄} = [c] ⟺ (t = c) ∈ Σ^{∗}

(exercise). Now suppose σ is the atomic sentence Rt_{0} ⋯ t_{n−1}, and t_{i}^{𝔄} = [c_{i}] for each i in n. Then

𝔄 ⊨ σ ⟺ (t_{0}^{𝔄}, …, t_{n−1}^{𝔄}) ∈ R^{𝔄}
⟺ ([c_{0}], …, [c_{n−1}]) ∈ R^{𝔄}
⟺ (Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗}
⟺ σ ∈ Σ^{∗}.

If instead σ is the equation t_{0} = t_{1}, then

𝔄 ⊨ σ ⟺ t_{0}^{𝔄} = t_{1}^{𝔄}
⟺ [c_{0}] = [c_{1}]
⟺ (c_{0} = c_{1}) ∈ Σ^{∗}
⟺ σ ∈ Σ^{∗}.

Now suppose that (6.1) holds when σ has the length of τ, θ or φ:

(∗) If σ is ¬τ, then

𝔄 ⊨ σ ⟺ 𝔄 ⊭ τ ⟺ τ ∉ Σ^{∗} ⟺ σ ∈ Σ^{∗}

by maximality of Σ.

(†) If σ is (τ → θ), then

𝔄 ⊭ σ ⟺ 𝔄 ⊨ τ & 𝔄 ⊨ θ̸
⟺ τ ∈ Σ^{∗} & θ ∉ Σ^{∗}
⟺ σ ∈ Σ^{∗}

by maximality of Σ^{∗}.

(‡) If σ is ∃x φ, then

𝔄 ⊨ σ ⟺ 𝔄 ⊨ φ_{c}^{x} for some c in C
⟺ φ_{c}^{x} ∈ Σ^{∗} for some c in C
⟺ ∃x φ ∈ Σ^{∗}

by definition of Σ^{∗}.

By induction, (6.1) holds for all σ, so 𝔄 ⊨ Σ^{∗}.

In the proof, we introduced a set C of new constants such that |C| = |Sn_{L}|. We can denote |Sn_{L}| by |L|. For the model 𝔄 of Σ produced, we have |A| ⩽ |C| = |L|.

Theorem 6.3. If T is a theory such that, for all n in ω, there is a model of T of size greater than n, then T has an infinite model.

Proof. For each n in ω, introduce a new constant c_{n}. Every model of the theory T ∪ {c_{i} ≠ c_{j} : i < j < ω} is infinite. Also this theory has models, by Compactness, since the theory is finitely satisfiable. Indeed, every finite subset of the theory is a subset of T ∪ {c_{i} < c_{j} : i < j < n} for some n. We can expand a model of T of size greater than n to a model of the larger theory by interpreting each c_{i} by a different element of the universe.

Example 6.4. Let K be the class of finite fields (considered as structures in the signature {+, −, ·, 0, 1}). Then Th(K) has infinite models; these are called pseudo-finite fields. Every field F has a characteristic: If

F ⊨ \underbrace{1 + ⋯ + 1}_{p} = 0

for some prime number p, then p is the characteristic of F, or char F = p; if there is no such p, then char F = 0. The field F is perfect if either:

(∗) char F = 0; or

(†) char F = p and every element of F has a p-th root.

Then perfect fields are precisely the fields that satisfy the axioms

∀x ∃y (\underbrace{1 + ⋯ + 1}_{p} = 0 → y^{p} = x).

Now, if F is finite, then char F = p for some prime p, and the function x ↦ x^{p} is an automorphism of F, that is, an isomorphism from F to itself. This shows F is perfect. Therefore the pseudo-finite fields are also perfect. In fact, axioms can be written for the theory of pseudo-finite fields (James Ax, 1968).

Another field-theoretic application of Compactness is:

Example 6.5. An ordered field is a structure 𝔉 or (F, +, −, ·, 0, 1, <) such that:

(∗) (F, +, −, ·, 0, 1) is a field;

(†) (F, <) is a total order;

(‡) 𝔉 ⊨ ∀x ∀y (0 < x ∧ 0 < y → 0 < x + y ∧ 0 < x · y);

(§) 𝔉 ⊨ ∀x (x < 0 → 0 < −x).

An ordered field must have characteristic 0 (why?); hence ℚ can be treated as a sub-field of it. In an ordered field, the formula 0 < x defines the set of positive elements. The ordered field 𝔉 is Archimedean if, for all positive a and b in F, there is a natural number n such that

𝔉 ⊨ a < \underbrace{b + ⋯ + b}_{n} .

Then ℝ is an Archimedean ordered field. However, there is an ordered field 𝔉 such that 𝔉 ≡ ℝ, but 𝔉 is not Archimedean. Indeed, let c be a new constant. Then the theory

Th(ℝ) ∪ {n < c : n ∈ ω}

is finitely satisfiable, since for every finite subset Σ of this theory, ℝ itself expands to a model of Σ. So the theory has a model 𝔉, by Compactness; but

𝔉 ⊨ \underbrace{1 + ⋯ + 1}_{n} < c

for all n in ω.

Theorem 6.6 (Löwenheim–Skolem–Tarski). Suppose 𝔄 is an infinite Lstructure, and κ is an infinite cardinal such that |L| ⩽ κ. Then there is an L-structure 𝔅 such that |B| = κ and 𝔄 ≡ 𝔅.

Proof. Introduce κ-many new constants c_{α} (where α < κ). In the Compactness Theorem, let Σ be Th(𝔄)∪{c_{α} ≠ c_{β} : α < β < κ}. This set is finitely satisfiable. Indeed, any finite subset is included in a subset Th(𝔄) ∪ {c_{α_{i}} ≠ c_{α_{j}} : i < j < n} for some finite subset {α_{0}, …, α_{n−1}} of κ. Then 𝔄 expands to a model of this set of sentences, once we interpret each constant c_{α_{i}} as a different element of A. (Since A is infinite, we can do this.) Therefore Σ is finitely satisfiable. The proof of Compactness now produces a model of Σ of size κ.

Theorem 6.7 (Vaught). Suppose T is a finitely satisfiable theory of L, and |L| ⩽ κ. Then T is complete, provided:

(∗) T has no finite models;

(†) T is κ-categorical.

Proof. Suppose T is finitely satisfiable, but has no finite models, but is not complete. By Compactness, T does have models. Then for some sentence σ, neither σ nor ¬σ is a consequence of T. Hence, both T ∪ {¬σ} and T ∪ {σ} have models. By Löwenheim–Skolem–Tarski, they have models of size κ. These models are not elementarily equivalent, so they are not isomorphic; this means T is not κ-categorical.

Examples 6.8.

(∗) To prove that TO^{∗} is complete, it is enough to show that every model is infinite, and that every countable model is isomorphic to (ℚ, <).

(†) If a real vector-space V has positive dimension κ, then

|V | = κ · |2^{ω}| = max(κ, |2^{ω}|).

A space of dimension 0 is the the trivial space, namely the space containing only the 0-vector; this space has size 1. Real vector-spaces of the same dimension are isomorphic Hence the theory of real vector-spaces is κ-categorical if κ > |2^{ω}|. Therefore the theory of non-trivial real vectorspaces is complete.

6.1 Additional exercises

(1) Show that every Archimedean ordered field is elementarily equivalent to some countable, non-Archimedean ordered field.

(2) Show that every non-Archimedean ordered field contains infinitesimal elements, that is, positive elements a that are less than every positive rational number.

(3) Find an example of a non-Archimedean ordered field.

(4) The order of an element g of a group is the size of the subgroup {g^{n} : n ∈ ℤ} that g generates. In a periodic group, all elements have finite order. Suppose G is a periodic group in which there is no finite upper bound on the orders of elements. Show that G ≡ H for some non-periodic group H.

(5) Suppose (X, <) is an infinite total order in which X is well-ordered by <. Show that there is a total order (X^{∗}, <^{∗}) such that

(X, <) ≡ (X^{∗}, <^{∗}),

but X^{∗} is not well-ordered by <^{∗}.

Completeness

We now aim to establish a complete proof-system for first-order logic. The result is Theorem 7.19 on p. 65. The proof of this theorem follows the pattern of our proof of Compactness.

First-order logic is based on propositional logic. It will be useful to have a general description of logics that encompasses both propositional and first-order logic. So, this is where we begin. All sections following § 7.3 concern first-order logic, unless otherwise noted.

There are a few exercises, on pp. 56, 59, 60, 61, 61, 61 and 64.

7.1 Logic in general

A logic has an alphabet, which is just a certain non-empty set; the members of this set can be called the symbols of the logic. These symbols can be put together to form strings. If we want a formal definition, we can say that such a string is a finite, non-empty sequence of symbols of the logic; that is, the string is a function k ↦ s_{k} from {0, 1, …, n} into the alphabet, for some n in ω. We usually write this function as

s_{0}s_{1} ⋯ s_{n};

this the result of juxtaposing the symbols s_{k} in the prescribed order. Such a string has sub-strings, namely the strings

s_{ℓ}s_{ℓ+1} ⋯ s_{m},

where 0 ⩽ ℓ ⩽ m ⩽ n; the sub-string is proper if 0 < ℓ or m < n. Certain strings will be formulas of the logic. In particular, certain strings will be atomic formulas. Some rules of construction are specified for converting certain finite sets of strings into other strings. Then a formula of the logic is a member of the smallest set X of strings such that:

(∗) all atomic formulas are in X; and

(†) X contains every string that results from applying a rule of construction to a set of elements of X.

Hence properties of all formulas can be proved by induction.

Moreoever, it is required that, for every formula that is not atomic, there is exactly one rule of construction and one set of formulas such that the original formula results from applying that rule to that set. This is the principle of uniquely readability as formulas; it makes possible the recursive definition of functions on the set of formulas.

For any logic, a proof-system consists of:

(∗) axioms, which are just certain formulas of the logic;

(†) rules of inference, that is, ways of inferring certain formulas from certain finite sets of formulas.

So the notions of axiom and rule of inference are parallel to the notions of atomic formula and rule of construction. However, in a proof-system, there is no requirement corresponding to unique readability.

Let S be proof-system. A deduction or formal proof in S of the formula φ from the set Φ of formulas is a sequence

ψ_{0}, …, ψ_{n}

of formulas where ψ_{n} is φ, and for each k such that k ⩽ n, one of the following holds:

(∗) ψ_{k} ∈ Φ, or

(†) ψ_{k} is an axiom of S, or

(‡) ψ_{k} follows from some subset of {ψ_{j} : j < k} by one of the rules of inference of S.

To denote that such a deduction exists, we can write

Φ ⊢_{S} φ.

Then we can say that φ is deducible from Φ in S. In case Φ is empty, we can just write

⊢_{S} φ,

and we can call φ a theorem of S.

Here are some basic facts:

Lemma 7.1.

(∗) Every non-empty initial segment of a deduction is also a deduction;

(†) if Φ ⊢_{S} φ and Φ ⊆ Φ^{∗}, then Φ^{∗} ⊢_{S} φ;

(‡) if Φ ⊢_{S} φ, then Φ_{0} ⊢_{S} φ for some finite subset Φ_{0} of Φ;

(§) if Φ ⊢_{S} ψ for each ψ in Ψ, and Ψ ⊢_{S} χ, then Φ ⊢_{S} χ.

Proof. Exercise.

7.2 Propositional logic

We shall work here with the propositional logic whose alphabet consists of:

(∗) the propositional variables P_{k}, where k ∈ ω;

(†) the connectives ¬ and →;

(‡) the left bracket ( and the right bracket ).

The atomic formulas are then the propositional variables. There are two rules of construction:

(∗) From the string A, construct ¬A.

(†) From the strings A and B, construct (A → B).

Note that the same formula might be both (A → B) and (C → D) for some strings A, B, C and D such that A is not C. But if all of these strings are formulas, then (as one can prove) A must be C. We use F and G and H as syntactical variables for propositional formulas.

In propositional logic, there is a notion of truth, which we can develop as follows. If S ⊆ ω, let 2^{S} be the set of functions from S to 2. We can consider 2 as the universe of the field 𝔽_{2}; then a ring-structure on 2^{S} is induced. If F is a propositional formula, and all variables appearing in F are in S, then there is a function F̂ from 2^{S} into 2, as given by the following recursive definition:

(∗) If F is P_{k}, then F̂(α) = α(k) for all α in 2^{ω}.

(†) If F is ¬G, then F̂ = 1 + Ĝ.

(‡) If F is (G → H), then F̂ = 1 + Ĝ · (1 + Ĥ).

Suppose S is the set of variables actually appearing in F, and F̂(α) = 1 for all α in 2^{S}; then F is called a tautology.

An element α of 2^{ω} can be called a structure for propositional logic. (Alternatively, the set {P_{n} : α(n) = 1} can be called the structure; each one determines the other.) Then a formula F is true in α if F̂(α) = 1. If every formula in a set Φ of formulas is true in a structure α, then α is a model of Φ. If F is true in every model of Φ, then we say that F is a logical consequence of Φ, or that Φ entails F, and we write

Φ ⊨ F.

A formula F is valid, or is a validity, if it is true in all structures; in that case, we write

⊨ F.

A proof-system S for propositional logic is called:

(∗) sound, if Φ ⊨ φ whenever Φ ⊢_{S} φ;

(†) complete, if Φ ⊢_{S} φ whenever Φ ⊨ φ.

Lemma 7.2. Let S be a proof-system for propositional logic. Then S is sound if and only if:

(∗) each axiom of S is valid;

(†) Φ ⊨ φ whenever φ can be inferred from Φ by one of the rules of inference of S.

Proof. Suppose S is sound. If φ is an axiom of S, then the one-term sequence φ is a deduction of φ from ∅, so ⊢_{S} φ and therefore ⊨ φ. Suppose, instead, that φ can be inferred from Φ by one of the rules of inference of S. Then Φ is a finite set {ψ_{0}, …, ψ_{n}}, so the sequence

ψ_{0}, …, ψ_{n}, φ

is a deduction of φ from Φ in S. Hence Φ ⊢_{S} φ, and therefore Φ ⊨ φ.

The converse is proved by induction on the lengths of deductions. Suppose that each axiom of S is valid, and Φ ⊨ φ whenever φ can be inferred from Φ by one of the rules of inference of S. As an inductive hypothesis, suppose Φ ⊨ φ whenever φ has a deduction in S from Φ of length less than n + 1. Now say the sequence

ψ_{0}, …, ψ_{n−1}, φ

of length n+1 is a deduction in S from Φ. If φ ∈ Φ, then Φ ⊨ φ trivially. If φ is an axiom of S, then ⊨ φ by assumption, so Φ ⊨ φ. The remaining possibility is that φ can be inferred from some subset Γ of {ψ_{k} : k < n} by a rule of inference of S. Then Γ ⊨ φ by assumption. Also, Φ ⊨ ψ_{k} for each ψ_{k} in Γ by inductive hypothesis, since each ψ_{k} has a proof from Φ of length k + 1, namely

ψ_{0}, …, ψ_{k}.

Hence every model of Φ is a model of Γ, and so φ is true in this model; that is, Φ ⊨ φ.

Let us also note that if a proof-system is complete, then so is every proof-system obtained by addition of new axioms or rules of inference.

In the only proof-system for first-order logic that we shall consider,

(∗) the axioms are just the tautologies;

(†) the only rule of inference is modus ponens, that is, G can be inferred from {F, (F → G)}.

If, in this system, F is deducible from the set Φ of formulas, then we can just write

Φ ⊢ F

(since we shall consider no other proof-systems for propositional logic). We have proved (in class) that this system is sound and complete.

7.3 First-order logic

The foregoing notions in propositional logic generalize to first-order logic. For us, the alphabet for a first-order logic will consist of:

(∗) the symbols in a signature L for the logic;

(†) individual variables v_{k}, where k ∈ ω;

(‡) the Boolean connectives ¬ and →;

(§) the quantifier ∃; (¶) the brackets ( and ).

The set of formulas of the resulting logic can be denoted

Fm_{L} .

Certain formulas are sentences; the set of them is

Sn_{L} .

We do not have proof by induction on this set, since sentences can be constructed from formulas that are not sentences. However, we can still define proof-systems for Sn_{L}. (Alternatively, we could define a proof-system for Fm_{L}.)

There are L-structures 𝔄, and then for each sentence σ of L, there is an element σ^{𝔄} of 2. Then σ is true in 𝔄 if σ^{𝔄} = 1. The notions of model, entailment, validity, soundness and completeness can now be defined as for propositional logic. Hence we have Lemma 7.2 for Sn_{L} in addition to propositional logic.

To prove that a certain proof-system for Sn_{L} is complete, we shall use the method first expounded by Leon Henkin, in [3]. (Henkin’s proof was a part of his doctoral thesis; see [4]. We have already used Henkin’s method to prove Compactness.) The particular treatment in these notes owes something to Shoenfield’s in [10]. I introduce the notions of tautological and deductive completeness merely to make our ultimate proof-system seem natural.

If F is an n-ary formula F (P_{0}, …, P_{n−1}) of propositional logic, and σ_{k} ∈ Sn_{L}, then by substitution we can form the sentence

F (σ_{0}, …, σ_{n−1})

of L. If F is a tautology, then F (σ_{0}, …, σ_{n−1}) can be called a tautology of Sn_{L}.

Lemma 7.3. Tautologies of Sn_{L} are validities.

Proof. We can prove by induction on propositional formulas F that, if F is F (P_{0}, …, P_{n−1}), then for all sentences σ_{k} of Sn_{L}, and all L-structure 𝔄,

F (σ_{0}, …, σ_{n−1})^{𝔄} = F̂(σ_{0}^{𝔄}, …, σ_{n−1}^{𝔄}).

(Details are an exercise.) The claim follows immediately from this.

7.4 Tautological completeness

Suppose S is a proof-system for Sn_{L} such that, if F_{0}, …, F_{k} are n-ary propositional formulas, and

{F_{0}, …, F_{k−1}} ⊨ F_{k},  (7.1)

and σ_{0}, …, σ_{n−1} ∈ Sn_{L}, then

{F_{0}(σ_{0}, …, σ_{n−1}), …, F_{k−1}(σ_{0}, …, σ_{n−1})} ⊢_{S} F_{k}(σ_{0}, …, σ_{n−1});  (7.2)

let us say then that S is tautologically complete.

Lemma 7.4. Let S be a proof-system for Sn_{L}. Then S is tautologically complete if and only if:

(∗) ⊢_{S} σ for all tautologies σ of Sn_{L}, and

(†) {σ, σ → τ} ⊢_{S} τ for all σ and τ in Sn_{L}.

Proof. If S is tautologically complete, then immediately all tautologies are theorems; the other condition follows since {P_{0}, P_{0} → P_{1}} ⊨ P_{1}.

To prove the converse, we can use our complete proof-system for propositional logic: Suppose we have (7.1) above. Then F_{k} has a a formal proof from {F_{0}, …, F_{k−1}}. Say this proof is

G_{0}, …, G_{m}.

Then G_{m} is F_{k}. We proceed by induction on m. There are three possibilities:

(∗) If F_{k} ∈ {F_{0}, …, F_{k−1}}, then trivially (7.2) follows.

(†) If F_{k} is a tautology, then ⊢_{S} F_{k}(σ⃗) by assumption, so (7.2).

(‡) If G_{j} is (G_{i} → F_{k}) for some i and j in m, then, by inductive hypothesis, we have

{F_{0}(σ⃗), …, F_{k−1}(σ⃗)} ⊢_{S} G_{i}(σ⃗);
{F_{0}(σ⃗), …, F_{k−1}(σ⃗)} ⊢_{S} G_{j}(σ⃗);

hence (7.2) by assumption (and Lemma 7.1).

In all cases then, (7.2) follows.

It should be clear that a complete proof-system is tautologically complete. The converse fails:

Example 7.5. The proof-system in which all tautologies are axioms and modus ponens is the only rule of inference is not complete, since it cannot be used to prove the validity ∃x x = x. Indeed, the theorems of this proof-system are just the tautologies (as one can show); but ∃x x = x is not a tautology.

Let ⊥ be the negation of a tautology, say

¬(∃x x = x → ∃x x = x).

Henceforth, let Σ ⊆ Sn_{L} and σ ∈ Sn_{L}.

Lemma 7.6. In a tautologically complete proof-system S, the following are equivalent:

(∗) Σ ⊢ ¬σ for some σ in Σ;

(†) Σ ⊢ σ and Σ ⊢ ¬σ for some σ in Sn_{L};

(‡) Σ ⊢ σ for every σ in Sn_{L};

(§) Σ ⊢ ⊥.

Proof. Exercise. (There is a corresponding lemma for propositional logic.)

If Σ ⊢_{S} ⊥, then Σ is inconsistent in S; otherwise, it is consistent.

Lemma 7.7. In a complete proof-system, every consistent subset of Sn_{L} has a model.

Proof. If S is complete, but Σ has no model, then Σ ⊨ ⊥, so Σ ⊢_{S} ⊥ by completeness, so Σ is inconsistent.

The converse of the lemma may fail, even if the proof-system is required to be tautologically complete:

Example 7.8. Let the axioms of a proof-system S be the tautologies, and let the rules of inference be modus ponens, along with the rule that ⊥ can be inferred from every finite set that has no model. (Note however that this is not a syntactical rule: it is not based directly on the form of sentences.) By the Compactness Theorem of first-order logic, every set with no model is inconsistent in this theory; therefore all consistent sets have models. However, the validity ∃x x = x is not a theorem of S. (Exercise: show this.)

7.5 Deductive completeness

Let a proof-system S be called deductively complete if Σ ⊢_{S} (σ → τ) whenever Σ ∪ {σ} ⊢_{S} τ.

Lemma 7.9. A tautologically and deductively complete proof-system in which every consistent set has a model is complete.

Proof. Suppose S is such a system, and Σ ∪ {¬σ} is inconsistent in S. Then Σ ∪ {¬σ} ⊢_{S} σ by Lemma 7.6, so Σ ⊢_{S} (¬σ → σ) by deductive completeness. But (¬σ → σ) → σ is a tautology, so Σ ⊢_{S} σ by tautological completeness.

Therefore, if Σ ⊬_{S} σ, then Σ ∪ {¬σ} is consistent, so it has a model by assumption; this shows Σ ⊭ σ.

Lemma 7.10. A tautologically complete proof-system whose only rule of inference is modus ponens is deductively complete.

Proof. Exercise. (See the Deduction Theorem of propositional logic.)

Lemma 7.11. Suppose Σ ⊆ Sn_{L} and Σ is consistent in a tautologically and deductively complete proof-system. The following are equivalent:

(∗) If Σ ⊆ Γ ⊆ Sn_{L} and Γ is consistent, then Γ = Σ.

(†) ¬σ ∈ Σ ⟺ σ ∉ Σ for all σ in Sn_{L}.

Proof. Exercise.

A set Σ meeting one of the conditions in the lemma can be called maximally consistent.

7.6 Completeness

By Lemma 7.4, we know of one tautologically complete proof-system, namely, the system whose axioms are the tautologies, and whose rule of inference is modus ponens. Let S be this system. Then S is deductively complete, by Lemma 7.10, and is sound, by Lemmas 7.2 and 7.3. Moreover, soundness and deductive completeness are preserved if we add new valid axioms to S. Now we shall see which valid axioms we can add in order to ensure that every consistent set has a model; then we shall have a complete system by Lemma 7.9.

We follow the proof of the Compactness Theorem, replacing ‘finitely satisfiable’ with ‘consistent’. We assume that L is countable. Suppose Σ is a consistent subset of Sn_{L}. We introduce an infinite set C of new constants and enumerate Sn_{L∪C} as {σ_{n} : n ∈ ω}. We construct a chain

Σ = Σ_{0} ⊆ Σ_{1} ⊆ Σ_{2} ⊆ ⋯

where

Σ_{2n+1} = \begin{cases}Σ_{2n} ∪ \{σ_{n}\}, & if this is consistent; \\ Σ_{2n}, & otherwise. \end{cases}

If σ_{n} is ∃x φ, and this is in Σ_{2n+1}, then we want to define Σ_{2n+2} as

Σ_{2n+1} ∪ {φ_{c}^{x}},

where c is a variable not used in Σ_{2n+1}. But we need to know that this set is consistent. For this we assume, as axioms of S, the sentences

(φ_{c}^{x} → χ) → ∃x φ → χ,  (7.3)

where c is a variable not appearing in χ. Note that these axioms are valid. We now have:

Lemma 7.12. If Γ is consistent and contains ∃x φ, and c does not appear in Γ, then Γ ∪ {φ_{c}^{x}} is consistent.

Proof. Suppose it’s not. Then

{ψ_{0}, …, ψ_{k−1}} ∪ {φ_{c}^{x}} ⊢_{S} ⊥

for some ψ_{i} in Γ. By deductive completeness,

⊢_{S} φ_{c}^{x} → ψ_{0} → ⋯ → ψ_{k−1} → ⊥,  (7.4)

where the notational convention is that a terminal string χ_{0} → χ_{1} → χ_{2} stands for the formula (χ_{0} → (χ_{1} → χ_{2})). We can re-write (7.4) as

⊢_{S} φ_{c}^{x} → χ,  (7.5)

where χ is ψ_{0} → ⋯ → ψ_{k−1} → ⊥. Then from (7.3) we have

⊢_{S} ∃x φ → χ

by modus ponens; that is,

⊢_{S} ∃x φ → ψ_{0} → ⋯ → ψ_{k−1} → ⊥.

Then k + 1 applications of modus ponens show

Γ ⊢_{S} ⊥,

which contradicts the assumption that Γ is consistent.

So now, given a consistent subset Σ of Sn_{L}, we can construct a consistent subset Σ^{∗} of Sn_{L∪C} such that (∗) Σ ⊆ Σ^{∗}; (†) Σ^{∗} is maximally consistent; (‡) if (∃x φ) ∈ Σ, then φ_{c}^{x} ∈ Σ for some c in C, that is, Σ^{∗} has witnesses. As in the proof of Compactness, we want to use Σ^{∗} to define a model 𝔄 of itself. For the sake of defining the universe of 𝔄, we assume now that S has the axioms

c = c,  (7.6)
c = c′ → d = d′ → c = d → c′ = d′,  (7.7)

where c, c′, d and d′ range over C. Let E be the relation

{(c, d) ∈ C^{2} : (c = d) ∈ Σ^{∗}}.

We can now show: Lemma 7.13. The relation E is an equivalence-relation.

Proof. We first show

⊢_{S} c = c,  (7.8)
⊢_{S} c = d → d = c,  (7.9)
⊢_{S} c = d → d = e → c = e  (7.10)

for all constants c, d and e in C. Now, we have (7.8) trivially by (7.6). An instance of (7.7) is

c = d → c = c → c = c → d = c;

then (7.9) follows by tautological completeness. Another instance of (7.7) is

c = c → d = e → c = d → c = e;

then (7.10) follows by tautological completeness. By its maximal consistency then, Σ^{∗} contains c = c; and if Σ^{∗} contains c = d and d = e, then it contains d = c and c = e.

We define A to be C/E. We now define R^{𝔄} (for each n-ary predicate R in L) as the set

{([c_{0}], ⋯, [c_{n−1}]) ∈ A^{n} : (Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗}}.

Then we have

(Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗} ⟹ ([c_{0}], ⋯, [c_{n−1}]) ∈ R^{𝔄},

but perhaps not the converse. Possibly then both Rc_{0} ⋯ c_{n−1} and ¬Rc′_{0} ⋯ c′_{n−1} are in Σ^{∗}, although (c_{k} = c′_{k}) ∈ Σ^{∗} in each case. To prevent this, as as axioms of S we assume

c_{0} = c′_{0} → ⋯ → c_{n−1} = c′_{n−1} → Rc_{0} ⋯ c_{n−1} → Rc′_{0} ⋯ c′_{n−1}.  (7.11)

We now have:

Lemma 7.14. ([c_{0}], ⋯, [c_{n−1}]) ∈ R^{𝔄} ⟺ (Rc_{0} ⋯ c_{n−1}) ∈ Σ^{∗}.

Proof. Exercise.

Finally, suppose f is an n-ary function-symbol (where possibly n = 0, in which case f is a constant.) We want to be able to define f^{𝔄}. (If c ∈ C, then c^{𝔄} = [c]; but there might be constants of L as well.) To define f^{𝔄}, we first need some lemmas, which are based on another axiom:

φ_{t}^{x} → ∃x φ,  (7.12)

where fv(φ) ⊆ {x} and t is a term with no variables. Let us assume that this is an axiom of S. Then we have:

Lemma 7.15 (Substitution). If fv(φ) ⊆ {x}, and the constant c does not appear in φ, then

⊢_{S} φ_{c}^{x} → φ_{t}^{x}

for all constant terms t.

Proof. We have

⊢_{S} ¬φ_{t}^{x} → ∃x ¬φ,  [by (7.12)]
⊢_{S} ¬∃x ¬φ → φ_{t}^{x},  [by tautological completeness]
⊢_{S} (¬φ_{c}^{x} → ⊥) → ∃x ¬φ → ⊥,  [by (7.3)]
⊢_{S} φ_{c}^{x} → ¬∃x ¬φ,  [by tautological completeness]

and hence ⊢_{S} φ_{c}^{x} → φ_{t}^{x} by modus ponens.

Lemma 7.16. ⊢_{S} t = t for all terms t.

Proof. We have

⊢_{S} c = c,  [by (7.6)]
⊢_{S} c = c → t = t,  [by the Substitution Lemma]

and hence ⊢_{S} t = t by modus ponens.

Lemma 7.17. ⊢_{S} ∃x fc_{0} ⋯ c_{n−1} = x.

Proof. We have

⊢_{S} fc_{0} ⋯ c_{n−1} = fc_{0} ⋯ c_{n−1},  [by the last lemma]
⊢_{S} fc_{0} ⋯ c_{n−1} = fc_{0} ⋯ c_{n−1} → ∃x fc_{0} ⋯ c_{n−1} = x, [by (7.12)]

hence ⊢_{S} ∃x fc_{0} ⋯ c_{n−1} = x by modus ponens.

Finally, we assume as axioms of S the sentences

c_{0} = c′_{0} → ⋯ → c_{n−1} = c′_{n−1} → fc_{0} ⋯ c_{n−1} = fc′_{0} ⋯ c′_{n−1}.  (7.13)

This enables us to define f^{𝔄}:

Lemma 7.18. For each n-ary function-symbol f, there is an n-ary operation f^{𝔄} on A given by

f^{𝔄}([c_{0}], …, [c_{n−1}]) = [d] ⟺ (fc_{0} ⋯ c_{n−1} = d) ∈ Σ^{∗}.  (7.14)

Proof. Since Σ^{∗} is maximally consistent, we now have

∃x fc_{0} ⋯ c_{n−1} = x ∈ Σ^{∗}.

Since Σ^{∗} has witnesses, we have

fc_{0} ⋯ c_{n−1} = d ∈ Σ^{∗}

for some constant d. This gives us a value for f^{𝔄}([c_{0}], ⋯, [c_{n−1}]); we have to show that this value is unique. For this, it is enough to show

⊢_{S} c_{0} = c′_{0} → ⋯ → c_{n−1} = c′_{n−1} → d = d′ → fc_{0} ⋯ c_{n−1} = d → fc′_{0} ⋯ c′_{n−1} = d′

for all c_{k} and c′_{k} and d and d′ in C. By (7.13) and tautological completeness, it is enough to show

⊢_{S} fc_{0} ⋯ c_{n−1} = fc′_{0} ⋯ c′_{n−1} → d = d′ → fc_{0} ⋯ c_{n−1} = d → fc′_{0} ⋯ c′_{n−1} = d′.

In the axiom (7.7), we may assume that c is not one of the variables c′, d or d′. Then by the Substitution Lemma, we have

⊢_{S} fc_{0} ⋯ c_{n−1} = c′ → d = d′ → fc_{0} ⋯ c_{n−1} = d → c′ = d′.

We may also assume that c′ is not one of the variables c_{k}, d or d′. Applying the Substitution Lemma again gives what we want.

The structure 𝔄 is now determined and is a model of Σ, by the proof of the Compactness Theorem. In sum, what we have shown is:

Theorem 7.19 (Completeness for first-order logic). That proof-system for Sn_{L} is complete whose only rule of inference is modus ponens, and whose axioms are the following:

(∗) the tautologies; (†) (φ_{c}^{x} → χ) → ∃x φ → χ, where c does not appear in χ; (‡) c = c; (§) c = c′ → d = d′ → c = d → c′ = d′; (¶) c_{0} = c′_{0} → … c_{n−1} = c′_{n−1} → Rc_{0} ⋯ c_{n−1} → Rc′_{0} ⋯ c′_{n−1}; (∥) φ_{t}^{x} → ∃x φ; (∗∗) c_{0} = c′_{0} → ⋯ → c_{n−1} = c′_{n−1} → fc_{0} ⋯ c_{n−1} = fc′_{0} ⋯ c′_{n−1}.

Here the notation is as follows:

• x is a variable;

• φ is a formula such that fv(φ) ⊆ {x};

• χ is a sentence;

• t is a constant term;

• c, c′, c_{k}, c′_{k}, d and d′ are constants;

• n ∈ ω;

• R is an n-ary predicate if n > 0; and

• f is an n-ary function-symbol (or a constant, if n = 0).

Numbers of countable models

Our ultimate aim is to show that

I(T, ω) ≠ 2  (8.1)

whenever T is a countable, complete theory. The proof will require several interesting general results.

Note that proving (8.1) requires T to be complete:

Example 8.1. Let P be a singulary predicate, and in the signature {L}, let T be axiomatized by

∀x ∀y (P x ∧ P y → x = y).

Then T has non-isomorphic countably infinite models (ω, ∅) and (ω, {0}), and every countably infinite model is isomorphic to one of these.

8.1 Three models

In the signature {<} ∪ {c_{n} : n ∈ ω}, let T_{3} be the theory axiomatized by

TO^{∗} ∪ {c_{n+1} < c_{n} : n ∈ ω}.

We shall see that T_{3} is complete, and I(T_{3}, ω) = 3. Let

A_{0} = {a ∈ ℚ : 0 < a} = ℚ ∩ (0, ∞),
A_{1} = ℚ ∖ {0},
A_{2} = ℚ.

Then each A_{k} is the universe of a model 𝔄_{k} of T_{3}, where <^{𝔄_{k}} is the usual ordering <, and

c_{n}^{𝔄_{k}} = \frac{1}{n + 1}.

Then the set {c_{n}^{𝔄_{k}} : n ∈ ω}, in 𝔄_{k}, (∗) has no lower bound, if k = 0; (†) has a lower bound, but no infimum, if k = 1; (‡) has an infimum, if k = 2.

Hence the three structures are not isomorphic. However, we shall be able to show:

(∗) if 𝔅 ⊨ T_{3} and is countable, then 𝔅 ≅ 𝔄_{k} for some k in 3; (†) T_{3} is complete.

The proof of the first claim will be by the back-and-forth method. The following gives the prototypical example:

Theorem 8.2. TO^{∗} is ω-categorical.

Proof. Suppose 𝔄, 𝔅 ⊨ TO^{∗} and |A| = ω = |B|. We shall show 𝔄 ≅ 𝔅.

We can enumerate the universes:

A = {a_{n} : n ∈ ω}, B = {b_{n} : n ∈ ω}.

We shall recursively define an order-preserving bijection h from A to B. In particular, h will be ⋃{h_{n} : n ∈ ω}, where, notationally, we shall have

h_{n} = {(a_{k}, b′_{k}) : k < n} ∪ {(a′_{k}, b_{k}) : k < n}.

We let h_{0} = ∅. Suppose we have h_{n} so that the tuples

(a_{0}, a′_{0}, …, a_{n−1}, a′_{n−1}), and (b′_{0}, b_{0}, …, b′_{n−1}, b_{n−1})

have the same order-type. This means that, if we write these tuples as (c_{0}, …, c_{2n−1}) and (c′_{0}, …, c′_{2n−1}) respectively, then

c_{i} < c_{j} ⟺ c′_{i} < c′_{j}

for all i and j in 2n. Since 𝔅 is a dense total order without endpoints, we can chose b′_{n} so that

(a_{0}, a′_{0}, …, a_{n−1}, a′_{n−1}, a_{n}) and (b′_{0}, b_{0}, …, b′_{n−1}, b_{n−1}, b′_{n})

have the same order-type. Likewise, we can choose a′_{n} so that

(a_{0}, a′_{0}, …, a_{n}, a′_{n}), and (b′_{0}, b_{0}, …, b′_{n}, b_{n})

have the same order-type. Now let h_{n+1} = h_{n} ∪ {(a_{n}, b′_{n}), (a′_{n}, b_{n})}.

Corollary 8.3. I(T_{3}, ω) = 3.

Proof. Suppose 𝔅 is a countable model of T_{3}. The interpretation in 𝔅 of each formula

c_{n+1} < x ∧ x < c_{n}

is (when equipped with the ordering induced from 𝔅) a countable model of TO^{∗}. The same is true for the formula c_{0} < x. Finally, the set

⋂_{n∈ω}{b ∈ B : b < c_{n}}

is one of the following:

(∗) empty;

(†) a countable model of TO^{∗};

(‡) a countable dense total order with a greatest point, but no least point.

Then the previous theorem allows us to construct an isomorphism between 𝔅 and 𝔄_{0}, 𝔄_{1} or 𝔄_{2} respectively.

The following is really a corollary of Theorem 4.3:

Theorem 8.4. T_{3} admits elimination of quantifiers.

Proof. Any formula φ(x⃗) of {<, c_{0}, c_{1}, … } can be considered as

θ(x⃗ , c_{0}, …, c_{n−1})

for some formula θ of {<}. By quantifier-elimination in TO^{∗}, there is an open formula α of {<} such that

TO^{∗} ⊨ ∀x⃗ ∀y⃗ (θ(x⃗ , y⃗) ∧ ⋀_{i<n} y_{i+1} < y_{i} ↔ α(x⃗ , y⃗)).

But T_{3} ⊨ c_{i+1} < c_{i}, and T_{3} ⊨ TO^{∗}; so

T_{3} ⊨ ∀x⃗ (θ(x⃗ , c⃗) ↔ α(x⃗ , c⃗)).

Thus T_{3} admits quantifier-elimination.

Corollary 8.5. T_{3} is complete.

Proof. The three countable models 𝔄_{k} form a chain:

𝔄_{0} ⊆ 𝔄_{1} ⊆ 𝔄_{2}.

But here diag 𝔅 ⊨ Th(𝔅_{B}) for all models 𝔅 of T_{3}, so by Theorem 5.7, the chain is elementary:

𝔄_{0} ≼ 𝔄_{1} ≼ 𝔄_{2}.

In particular, the three structures are elementarily equivalent. Now, if 𝔅 is an arbitrary model of T_{3}, then it is infinite, so 𝔅 ≡ ℭ for some countably infinite structure ℭ by Theorem 6.6. But ℭ ≅ 𝔄_{k} for some k, by Corollary 8.3. Hence 𝔅 ≡ 𝔄_{0} by Theorem 5.7. Thus

T_{3} ⊨ Th(𝔄_{0});

so T_{3} is complete.

8.2 Omitting types

Since there is a sound, complete proof-system for first-order logic, we may say that a set of sentences is consistent to mean that it has a model.

An n-type of a signature L is a set of n-ary formulas of L.

An n-type Φ of L is realized by a⃗ in an L-structure 𝔄 if

𝔄 ⊨ φ(a⃗)

for all φ in Φ. A type not realized in a structure is omitted by the structure.

If a consistent theory T of L is specified, then an n-type of T is an n-type Φ that is consistent with T: This means that Φ is realized in some model of T. Equivalently, it means that, if c⃗ is an n-tuple of new constants, then the set

T ∪ {φ(c⃗) : φ ∈ Φ}

is consistent. By Compactness, for Φ to be consistent with T, it is sufficient that

T ∪ {∃x⃗ ⋀ Φ_{0}}

be consistent for all finite subsets Φ_{0} of Φ.

By Compactness also, for any collection of types consistent with T, there is a model of T in which all of the types are realized.

An n-type Φ of T is isolated in T by an n-ary formula ψ if:

(∗) T ∪ {∃x⃗ ψ} is consistent;

(†) T ⊨ ∀x⃗ (ψ → φ) for all φ in Φ.

Hence, if ψ is satisfied by a⃗ in a model of T, then a⃗ realizes Φ. Also, if T is complete, then T ⊨ ∃x⃗ ψ, so Φ is realized in every model of T.

We can call a theory countable if its signature is countable. (A more general definition is possible: T is countable if, in its signature, only countably many formulas are inequivalent in T.) It turns out that, in a countable theory, being isolated is the only barrier to being omitted by some model:

Theorem 8.6 (Omitting Types). Suppose T is a countable theory, and Φ is a non-isolated 1-type of T. Then Φ is omitted by some countable model of T.

Proof. We adjust our proof of the Compactness Theorem. As there, we introduce a set C of new constants c_{n} (where n ∈ ω). We enumerate Sn_{L∪C} as {σ_{n} : n ∈ ω}. We construct a chain

T = Σ_{0} ⊆ Σ_{1} ⊆ ⋯

as follows. Assume Σ_{3n} is consistent. Then let

Σ_{3n+1} = \begin{cases}Σ_{3n} ∪ \{σ_{n}\}, & if this is consistent; \\ Σ_{3n}, & otherwise. \end{cases}

Now let

Σ_{3n+2} = Σ_{3n+1} ∪ {φ(c_{k})},

where k is minimal such that c_{k} does not appear in Σ_{3n+1}, if σ_{n} ∈ Σ_{3n+1} and σ_{n} is ∃x φ; otherwise, Σ_{3n+2} = Σ_{3n+1}. Finally, let

Σ_{3n+3} = Σ_{3n+2} ∪ {¬ψ(c_{n})},

where ψ is an element of Φ such that Σ_{3n+2} ∪ {¬ψ(c_{n})} is consistent. But we have to check that there is such a formula ψ in Φ. If there is, then we can let

Σ^{∗} = ⋃_{n∈ω} Σ_{n}.

Then Σ^{∗} has a countable model 𝔄 (as in the proof of Compactness) such that every element of A is c^{𝔄} for some c in C. But by construction, no such element can realize Φ; so 𝔄 omits Φ.

Now, in the definition of Σ_{3n+3}, the formula ψ exists as desired because the set Σ_{3n+2} ∖ T can be assumed to be finite. In particular, the formulas in this set use only finitely many constants from C. We may assume that these constants form a tuple (c_{n}, d⃗). Then we can write ⋀ Σ_{3n+2} ∖ T as a sentence

φ(c_{n}, d⃗),

where φ is a certain formula of L. Now, if

Σ_{3n+2} ⊨ ψ(c_{n})

for some formula ψ, then

T ⊨ (φ(c_{n}, d⃗) → ψ(c_{n})),

hence

T ⊨ ∀x (∃y⃗ φ(x, y⃗) → ψ(x)).

Since Φ is not isolated in T, it is not isolated by ∃y⃗ φ. Therefore the set Σ_{3n+2} ∪ {¬ψ(c_{n})} must be consistent for some ψ in Φ.

In the proof, it is essential that Σ_{n} ∖ T is finite; the proof can’t be generalized to the case where T is uncountable. But the proof can be generalized to yield the following:

Porism 8.7. Suppose T is a countable theory, and Φ_{k} is an n-type of T for some n (depending on k), for each k in ω. Then T has a countable model omitting each Φ_{k}.

An n-type Φ of a theory T is called complete if

φ ∉ Φ ⟺ ¬φ ∈ Φ

for all n-ary formulas φ of L. Any n-tuple a⃗ of elements of a model 𝔄 of T determines a complete n-type of T, namely

{φ : 𝔄 ⊨ φ(a⃗)};

this is the complete type of a⃗ in 𝔄 and can be denoted

tp_{𝔄}(a⃗).

If Φ is an arbitrary n-type of T, then some a⃗ from some model 𝔄 of T realizes Φ, and therefore

Φ ⊆ tp_{𝔄}(a⃗).

In particular, every type of T is included in a complete type of T.

The set of complete n-types of T can be denoted

S_{n}(T);

then we can let ⋃_{n∈ω} S_{n}(T) be denoted

S(T).

So the Omitting-Types Theorem gives us that, if T is countable and |S(T)| ⩽ ω, then T has a countable model that omits all non-isolated types of T.

A structure 𝔄 that realizes only isolated types of Th(𝔄) is called atomic.

Examples 8.8.

(1) (ω,′ , 0) is atomic, since each element is named by a term. For example, a 1-type realized by 5 is isolated by the formula x = 0′′′′′.

(2) The theory of Example 5.13 has no atomic models.

The following lemma hints at the characterization of countable atomic models that we shall see in the next section.

Lemma 8.9. If 𝔄 embeds elementarily in 𝔅, then 𝔅 realizes all types that 𝔄 realizes.

Proof. Suppose h is an elementary embedding of 𝔄 in 𝔅, and a⃗ realizes the type Φ in 𝔄. Then

{φ(a⃗) : φ ∈ Φ} ⊆ Th(𝔄_{A}),

so h(a⃗) realizes Φ in 𝔅 by Theorem 5.7.

8.3 Prime structures

A structure is prime if it embeds elementarily in every model of its theory; if that theory is T, then the structure is a prime model of T. (Note then that only complete theories can have prime models, simply because the prime model is elementarily equivalent to all other models.)

Examples 8.10.

(1) If T admits quantifier-elimination, then by Corollary 5.8, all embeddings of models of T are elementary embeddings. Hence, for example, a countably infinite set is a prime model of the theory of infinite sets. Also, (ℚ, <) embeds in every model of TO^{∗}, so it is a prime model.

(2) It is possible to show that, if |L| ⩽ κ ⩽ |B|, then 𝔅 is an elementary extension of some structure 𝔄 such that |A| = κ. Hence, a model of a countable theory T is prime, provided it embeds elementarily in all countable models of T. In particular then, if T is ω-categorical, then its countable model is prime.

Theorem 8.11. Suppose T is a countable complete theory. Then the prime models of T are precisely the countable atomic models of T.

Proof. Suppose 𝔄 ⊨ T.

(⇒) If 𝔄 is not countable, then 𝔄 cannot embed in countable models of T (which must exist, by Theorem 6.6), so 𝔄 cannot be prime.

If 𝔄 is not atomic, then 𝔄 realizes some non-isolated type Φ of T. But by the Omitting-Types Theorem, T has a countable model 𝔅 that omits Φ. Then 𝔄 cannot embed elementarily in 𝔅, by Lemma 8.9.

(⇐) Suppose 𝔄 is countable and atomic, and 𝔅 ⊨ T. We construct an elementary embedding of 𝔄 in 𝔅 by the back-and-forth method, except that the construction is in only one direction. Write A as {a_{n} : n ∈ ω}. Then each tp_{𝔄}(a_{0}, …, a_{n−1}) is isolated in T by some formula φ_{n}. Then we have

(∗) T ⊨ ∃x⃗ φ_{n};
(†) T ⊨ ∀x⃗ (φ_{n} → ∃x_{n} φ_{n+1}).

Hence we can recursively find b_{k} in B so that

𝔅 ⊨ φ_{n}(b_{0}, …, b_{n−1})

for all n in ω.

Now, every sentence in Th(𝔄_{A}) is θ(a_{0}, …, a_{n−1}) for some formula θ of L. Then

T ⊨ ∀x⃗ (φ_{n} → θ),

so 𝔅 ⊨ θ(b⃗). Therefore the map a_{k} ↦ b_{k} : A → B is an elementary embedding of 𝔄 in 𝔅.

Porism 8.12. All prime models of a countable complete theory are isomorphic.

Proof. In the proof that 𝔄 embeds elementarily in 𝔅, if we assume also that 𝔅 is countable and atomic, then the full back-and-forth method gives an isomorphism between the structures.

Lemma 8.13. If I(T, ω) ⩽ ω, then |S(T)| ⩽ ω.

Proof. Exercise.

Theorem 8.14. Suppose T is a countable complete theory. Then T has a prime model if S(T) is countable.

Proof. Exercise.

8.4 Saturated structures

A saturated structure is the opposite of an atomic structure. Atomic structures realize as few types as possible. Saturated structures realize as many types as possible; moreover, these types are allowed to have parameters from the structure.

To be precise, let 𝔐 be an infinite L-structure, and let A ⊆ M. In this context, the set S_{n}(Th(𝔐_{A})) can be denoted

S_{n}(A).

Consider the special case where A is M itself. The set S_{1}(M), for example, contains types that include the type

{x ≠ a : a ∈ M}.

These types cannot be realized in 𝔐. So we say that 𝔐 is saturated, provided that, whenever A ⊆ M and |A| ⩽ |M|, each type in S(A) is realized in 𝔐. (In particular, if 𝔐 is countable here, then the sets A should be finite.)

Theorem 8.15. Suppose T is countable and complete, and |S(T)| ⩽ ω. Then T has a countable saturated model.

Proof. Suppose 𝔐 is a countable model of T. If A is a finite subset {a_{k} : k < n} of M, then each element of S_{m}(A) is

{φ(x_{0}, …, x_{m−1}, a_{0}, …, a_{n−1}) : φ ∈ p}

for some p in S_{m+n}(T). Hence |S(A)| is countable. Therefore the set

⋃{S(A) : A is a finite subset of M}

is countable. So all of the types in this set are realized in a countable elementary extension 𝔐′ of 𝔐.

Thus, if 𝔐_{0} is a countable model of T, then we can form an elementary chain

𝔐_{0} ≼ 𝔐_{1} ≼ 𝔐_{2} ≼ · · · .

It is straightforward then to define the union of this chain: this is a structure 𝔑 whose universe N is ∪_{n∈ω}M_{n}, and that is an elementary extension of each 𝔐_{n}. Every finite subset of N is a subset of some 𝔐_{n}, and so the types of S(A) are realized in 𝔐_{n+1}, hence in 𝔑. So 𝔑 is saturated.

If A is a finite subset {a_{k} : k < n} of M, and a⃗ is (a_{0}, …, a_{n−1}), we can denote 𝔐_{A} by

(𝔄, a⃗).

If 𝔐 is countable, then 𝔐 is called homogeneous if

tp_{𝔐}(a⃗) = tp_{𝔐}(b⃗) ⟹ (𝔐, a⃗) ≅ (𝔐, b⃗)

for all n-tuples a⃗ and b⃗ from M, for all n in ω.

Theorem 8.16. Countable saturated structures are homogeneous.

Proof. The back-and-forth method.

8.5 One model

For the sake of stating and proving the following theorem more easily, we can use the following notation. Suppose T is a theory of L. Then equivalence in T is an equivalence-relation on the set of n-ary formulas of L. Let the set of corresponding equivalence-classes be denoted

B_{n}(T).

Theorem 8.17. Suppose T is a countable complete theory. The following statements are equivalent:

(0) I(T, ω) = 1.

(1) All types of T are isolated.

(2) Each set B_{n}(T) is finite.

(3) Each set S_{n}(T) is finite.

Proof. (0)⇒(1): If S(T) contains a non-isolated type, then it is realized in some, but not all, countable models of T, so I(T, ω) > 1.

(1)⇒(0): If all types of T are isolated, then all models of T are atomic, so all countable models of T are prime and therefore isomorphic.

(2)⇒(3): Immediate.

(3)⇒(1)&(2): Suppose S_{n}(T) = {p_{0}, …, p_{m−1}}. For each i and j in m, if i ≠ j, then there is a formula φ_{ij} in p_{i} ∖ p_{j}. Let ψ_{i} be the formula

⋀_{j∈m∖{i}} φ_{ij}.

Then ψ_{i} is in p_{j} if and only if j = i. If 𝔄 ⊨ T, and a⃗ is an n-tuple from A, then 𝔄 realizes some unique p_{i}, and then 𝔄 ⊨ ψ_{i}(a⃗). Conversely, if 𝔄 ⊨ ψ_{i}(a⃗), then a⃗ must realize p_{i}. Therefore ψ_{i} isolates p_{i}.

If χ is an arbitrary n-ary formula, let I = {i ∈ m : χ ∈ p_{i}}. Then

T ⊨ ∀x⃗ (χ ↔ ⋁_{i∈I} ψ_{i}).

There are only finitely many possibilities for I, so B_{n}(T) is finite.

(1)⇒(3): Suppose infinitely many complete n-types are isolated in T. Since T is countable, there must be countably many such types. Say they compose the set {p_{k} : k ∈ ω}, and each p_{k} is isolated by φ_{k}. Then the type

{¬φ_{k} : k ∈ ω}

is consistent with T. It is not included in any of the p_{k}, so it must be included in a non-isolated type.

8.6 Not two models

Theorem 8.18. Suppose T is a countable complete theory. Then I(T, ω) ≠ 2.

Proof. Suppose if possible that T_{2} has just two non-isomorphic countable models. One of them, 𝔄, is prime, by Lemma 8.13 and Theorem 8.14. The other one, 𝔅, is saturated, by Theorem 8.15. Since 𝔄 embeds elementarily in 𝔅, we may assume 𝔄 ≼ 𝔅.

Since 𝔄 ≅ 𝔅̸, there is a non-isolated type Φ realized by some b⃗ in 𝔅, by Theorem 8.11 and Porism 8.12. Let T^{∗} = Th(𝔅, b⃗). Suppose (ℭ, c⃗) is a countable model of T^{∗}. Then ℭ ⊨ T_{2}, so ℭ is isomorphic to 𝔄 or 𝔅. In any case, 𝔄 embeds elementarily in ℭ. But Φ is realized by c⃗ in ℭ. Hence ℭ ≅ 𝔅 by Lemma 8.9. Let the isomorphism take c⃗ to a⃗. Then it is enough to show (𝔅, a⃗) ≅ (𝔅, b⃗). But this follows from Theorem 8.16.

Bibliography

[1] C. C. Chang and H. J. Keisler. Model theory. North-Holland Publishing Co., Amsterdam, 1973. Studies in Logic and the Foundations of Mathematics, Vol. 73.

[2] Alonzo Church. Introduction to mathematical logic. Vol. I. Princeton University Press, Princeton, N. J., 1956.

[3] Leon Henkin. The completeness of the first-order functional calculus. J. Symbolic Logic, 14:159–166, 1949.

[4] Leon Henkin. The discovery of my completeness proofs. Bull. Symbolic Logic, 2(2):127–158, 1996.

[5] Wilfrid Hodges. Model theory, volume 42 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993.

[6] David Marker. Model theory, volume 217 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. An introduction.

[7] David Pierce. Introductory notes on the foundations of mathematics, September 2004. Used in Math 111 at METU.

[8] Emil L. Post. Introduction to a general theory of elementary propositions. Amer. J. Math., 43(3):163–185, July 1921.

[9] Philipp Rothmaler. Introduction to model theory, volume 15 of Algebra, Logic and Applications. Gordon and Breach Science Publishers, Amsterdam, 2000. Prepared by Frank Reitmaier, Translated and revised from the 1995 German original by the author.

[10] Joseph R. Shoenfield. Mathematical logic. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1967.