Elements of the theory of models

David Pierce

May 15, 2003

Contents

0 Preface 1

1 Conventions 1

2 Propositional model-theory 2

3 First-order logic 5

4 Types 9

0 Preface

These notes are written according to my own understanding and preferences, and they should be considered only as a rough draft. I aim to present some logic as mathematics, and I assume that the reader already has some experience with mathematics. I claim no originality, but I do not happen to know of a published treatment that is quite like mine. However, § 2 in particular is influenced by [2] and [5]; most model-theory texts seem not to deal specifically with propositional logic. For the model-theoretic development of first-order logic, see also the early parts of [4], [7] or [6]. Books on logic itself that I have found useful are [3] and [1].

Technical terms in boldface are being defined, perhaps implicitly. Mathematical propositions (theorems, lemmas) whose proofs are not supplied are to be proved by the reader.

1 Conventions

In these notes, the symbol ⟺ is just an abbreviation for the words ‘if and only if’.

Let us denote the set {0, 1, 2, … } of natural numbers by ω. It is notationally convenient to consider this as the smallest set of sets that contains ∅ and is closed under the successor-operation, namely

A ↦ A ∪ {A}.

So ω contains ∅, {∅} and {∅, {∅}}, denoted 0, 1 and 2 respectively. Thus, 2 is {0, 1}, which we shall consider as the underlying set—the universe—of the 2-element field, 𝔽_{2}. We can write any n in ω as

{0, …, n − 1}.

Suppose M is a set, and I is a finite set. We shall denote the set of functions from I to M by M^{I}. Elements of this are I-tuples; a typical I-tuple can be written

(a_{j} : j ∈ I)

or just a. If I = n for some n in ω, then we may write a as (a_{0}, …, a_{n−1}) or as the string a_{0} … a_{n−1}. As a special case, we have M^{0} = {0} = 1.

2 Propositional model-theory

We first select a set V, and we shall refer to its members as variables. Usually, V is countably infinite, but this will not be required in any definitions. If A ⊆ V, then we may refer to the ordered pair (A, V) as a (propositional) structure (for V) and denote it by

𝔄.

The structure 𝔄 determines, and is determined by, the characteristic function χ_{𝔄}: V → 2, which is given by

χ_{𝔄}(P) = \begin{cases}0, & if P ∈ V ∖ A; \\ 1, & if P ∈ A. \end{cases}

We may call such a characteristic function a truth-assignment for V, reading 0 as ‘false’, and 1 as ‘true’.

Remark 2.1. Instead of χ_{𝔄}, one may write χ_{A} if the domain of the function is clear.

Next, we introduce a set

{∧, ∨, ¬, →, ↔}

of Boolean connectives, along with a pair {(,)} of brackets. We assume that the Boolean connectives and the brackets are not variables. We define the (propositional) formulas (for V) to be the members of the smallest set Φ of strings of elements of V ∪ {∧, ∨, ¬, →, ↔} ∪ {(,)} such that

(0) V ⊆ Φ;

(1) if F ∈ Φ, then ¬F ∈ Φ;

(2) if F, G ∈ Φ, and ∗ ∈ {∧, ∨, →, ↔}, then (F ∗ G) ∈ Φ.

So, we can call ¬ a unary connective; the other connectives are binary. Let us denote the set of propositional formulas in V by PF(V). The definition of PF(V) obviously allows proof by induction. That is, if Φ ⊆ PF(V), and if Φ satisfies the three enumerated conditions in the definition of PF(V), then Φ = PF(V).

Remark 2.2. The symbols ∧, ∨, ¬, → and ↔ can be read ‘and’, ‘or’, ‘not’, ‘implies’ and ‘if and only if’, respectively. We could avoid brackets by using the so-called Polish notation, in which we would write ∗F G instead of (F ∗ G); using reverse Polish notation, we would write F G∗. Note that the formulation F G∧ in reverse Polish notation could be read as ‘F, G too,’ or in Turkish as ‘F, G de’.

Lemma 2.3 (unique readability). Any propositional formula that is not a variable is the application of exactly one connective in exactly one way, that is, if F, F′, G, G′ and H are formulas, then F ∗ G and ¬H cannot be the same formula, and if F ∗ G and F′ ∗′ G′ are the same formula, then F and F′ are the same formula.

Lemma 2.4 (definition by recursion). Functions on PF(V) can be defined recursively. To be precise, suppose S is a set, and f_{¬} is a function from S to itself, and f_{∗} is a function from S ×S to S for each binary Boolean connective ∗. Then for every function g: V → S, there is a unique extension ĝ: PF(V) → S such that

(1) ĝ(¬F) = f_{¬}(ĝ(F)) for all F in PF(V);

(2) ĝ(F ∗ G) = f_{∗}(ĝ(F), ĝ(G)) for all F and G in PF(V) and each binary Boolean connective ∗.

Proof. Let PF_{n}(V) be the set of elements of PF(V) of length at most n. Suppose h_{n} and h′_{n} have the desired properties of ĝ, but are defined only on PF_{n}(V). By induction, the set

{F ∈ PF(V): h_{n}(F) = h′_{n}(F) or F ∉ PF_{n}(V)}

is just PF(V), so h_{n} = h′_{n}.

Also, in the obvious way, by Lemma 2.3, we can extend h_{n} to a function h_{n+1} on PF_{n+1}(V) having the properties of ĝ. Finally, h_{0} = ∅; so h_{n} exists uniquely for all n in ω, and we can let ĝ = ⋃_{n∈ω} h_{n}.

For a first application of Lemma 2.4, we can define a function

F ↦ V_{F} : PF(V) → 𝒫(V)

by the requirements:

(0) V_{P} = {P } if P ∈ V;

(1) V_{¬F} = V_{F};

(2) V_{F ∗G} = V_{F} ∪ V_{G}.

Theorem 2.5. V_{F} is the set of variables that actually appear in F. In particular, if also F ∈ PF(V′), then V_{F} = V′_{F}.

For a second application of Lemma 2.4, letting S be the universe of 𝔽_{2}, we can define

f_{¬}(x) = 1 + x,
f_{∧}(x, y) = xy,
f_{∨}(x, y) = x + y + xy,
f_{→}(x, y) = 1 + x + xy,
f_{↔}(x, y) = 1 + x + y.

Letting g be a truth-assignment χ_{𝔄}, we get an extension χ̂_{𝔄}: PF(V) → 2.

Lemma 2.6. χ̂_{𝔄}(F) depends only on F and A ∩ V_{F}, that is,

χ̂_{𝔄}(F) = χ̂_{𝔄′}(F),

where 𝔄′ = (A′, V′) and F ∈ PF(V) ∩ PF(V′), provided A ∩ V_{F} = A′ ∩ V′_{F}.

If χ̂_{𝔄}(F) = 1, we say that 𝔄 is a model of F and write

𝔄 ⊧ F.

If every structure for V is a model of F, then we say F is a validity for V and write

⊧_{V} F.

The truth-table for F is the function

A ↦ χ̂_{𝔄}(F): 𝒫(V_{F}) → 2;

this is well-defined by Lemma 2.6. If this function is identically 1, then we say that F is a tautology and write

⊢ F.

Theorem 2.7 (Completeness). For all F in PF(V),

⊧_{V} F ⟺ ⊢ F.

Hence we may write the single symbol ⊧ in place of ⊧_{V} and ⊢. If Φ ⊆ PF(V), and 𝔄 is a model of every formula in Φ, then 𝔄 is a model of F, and we can write

𝔄 ⊧ Φ.

Theorem 2.8 (Compactness). A set Φ of propositional formulas for a countable set of variables has a model if and only if each finite subset of Φ has a model.

If every model of a set Φ of formulas is a model of some formula F, then F is a (logical) consequence of Φ, and we can write

Φ ⊧ F.

Also, F ⊧ G means {F } ⊧ G. In this case, if also G ⊧ F, then F and G are (logically) equivalent, and we may write

F ⊧ =| G.

Lemma 2.9. For all F and G in PF(V),

F ⊧ =| G ⟺ ⊧ F ↔ G.

Lemma 2.10. For all F and G in PF(V),

(F ∨ G) ⊧ =| ¬(¬F ∧ ¬G),
(F → G) ⊧ =| (¬F ∨ G),
(F ↔ G) ⊧ =| ((F → G) ∧ (G → F)).

Remark 2.11. By Lemma 2.10, one can show that every equivalence-class of formulas contains a formula whose only Boolean connectives are ¬ and ∧.

Theorem 2.12 (Adequacy). Let A be a finite non-empty set of variables. Every function from 𝒫(A) to 2 is the truth-table for some propositional formula.

Proof. We shall use induction on the size of A. If A = {P }, then the truthtables of P, ¬P, (P ∧ ¬P) and (P ∨ ¬P) are just the 4 possible functions from 𝒫(A) to 2.

Suppose A has size n, and P is a variable not in A, and f is a function from 𝒫(A ∪ {P }) to 2. Let f_{0} be the restriction of f to 𝒫(A), and let f_{1} be the function

B ↦ f(B ∪ {P }): 𝒫(A) → 2.

Then for all B in 𝒫(A ∪ {P }) we have

f(B) = \begin{cases}f_{0}(B ∖ \{P \}), & if P ∉ B; \\ f_{1}(B ∖ \{P \}), & if P ∈ B. \end{cases}

Now let F be a formula ((F_{0} ∧ ¬P) ∨ (F_{1} ∧ P)), where F_{0} and F_{1} are formulas whose variables are from A. If B ⊆ A ∪ {P }, then

χ̂_{B}(F) = \begin{cases}χ̂_{B∖\{P \}}(F_{0}), & if P ∉ B; \\ χ̂_{B∖\{P \}}(F_{1}), & if P ∈ B. \end{cases}

Hence, if f_{0} and f_{1} are the truth-tables for F_{0} and F_{1} respectively, then f is the truth-table for F.

Remark 2.13. We might define propositional logic as the use of formulas to represent functions from the power-sets of finite sets to 2. We may then say that our particular propositional logic uses the signature {∧, ∨, ¬, →, ↔}. The last theorem shows that this signature is adequate to the task of representing these functions; in fact, the theorem shows that {∧, ∨, ¬} is adequate. We then have, by Remark 2.11, that the signature {∧, ¬} is adequate. In fact, one could get by with a single connective, namely the binary connective | such that

F | G ⊧ =| ¬(F ∧ G);

this connective is called the Sheffer stroke, although Church in [3, n. 207, pp. 133 f.] says that Sheffer never used the stroke this way.

3 First-order logic

We now define first-order structures and their signatures. The structures are primary in interest, but in giving definitions, it is easier to start with signatures.

Remark 3.1. A standard example of a first-order structure is ℝ, considered as the 7-tuple (R, +, −, ·, 0, 1, ⩽), where R is the set of real numbers. A group is a first-order structure when considered as the ordered quadruple (G, ·,^{−1}, 1); but it is not first-order when one considers it to be equipped also with the operation S ↦ ⟨S⟩ that assigns to each subset the subgroup that it generates.

A (first-order) signature is a set, each of whose members can be uniquely recognized as a function-, relation- or constant-symbol. Each of the function- and relation-symbols has an arity: each of these symbols is n-ary for some unique positive integer n.

Let L be a signature. Let f, R and c be arbitrary function-, relation- and constant-symbols, respectively, of L, and let n stand for the arity of f or R. An L-structure is an ordered pair

(M, int),

where M is a non-empty set, and int is a function s ↦ s^{𝔐} on L such that

• f^{𝔐} is a n-ary operation on M, that is, a function from M^{n} to M;

• R^{𝔐} is an n-ary relation on M, that is, a subset of M^{n};

• c^{𝔐} ∈ M.

The structure itself can be denoted 𝔐. The set M is the universe of 𝔐, and each image s^{𝔐} is the interpretation of s in 𝔐. Remark 3.2. A structure can be considered as its universe together with the interpretations of the symbols in its signature. This is how ℝ was presented in Remark 3.1. A structure without any relations can be called an algebra. Theorem 2.4 involves an algebra, namely (S, f_{∧}, f_{∨}, f_{¬}, f_{→}, f_{↔}). The natural numbers compose the algebra (ω,′, 0), where ′ is the successor-operation. The complete set of propositional formulas in some set of variables is the universe of an algebra in an obvious way.

Subsets of M^{0} are nullary relations. There are only two of these, namely 0 and 1, which we may read as before as ‘false’ and ‘true’.

Let X be set of new symbols, called (individual-) variables. We shall develop a language, which we might denote

L^{X}.

The symbols of L^{X} will compose the disjoint union

X ∪ L ∪ {=} ∪ S ∪ {∃x : x ∈ X},

where S is an adequate signature for a propositional logic (along with brackets, if one is using them). Let us consider S to be the signature {∧, ¬}. Note that each ∃x is an indivisible symbol, in which, however, the original x can be recognized. The symbols that are not in X ∪ L are logical symbols. In every L-structure 𝔐, each symbol s of L^{X} has an interpretation (rather, a family of interpretations) s^{𝔐}. We have defined the interpretations of the elements of L. The interpretations of the rest of the symbols of L^{X} are certain operations or, in one case, a relation, associated with appropriate finite subsets I of X:

• If x ∈ I, then x^{𝔐} is a ↦ a_{x}: M^{I} → M.

• =^{𝔐} is equality, a subset of M^{2}.

• ∧^{𝔐} is (A, B) ↦ A ∩ B: 𝒫(M^{I}) × 𝒫(M^{I}) → 𝒫(M^{I}) for any I.

• ¬^{𝔐} is A ↦ A^{c} : 𝒫(M^{I}) → 𝒫(M^{I}) for any I.

• ∃x^{𝔐} is, for any I, the map from 𝒫(M^{I}) to 𝒫(M^{I∖{x}}) induced by the projection a ↦ (a_{i} : i ∈ I ∖ {x}) : M^{I} → M^{I∖{x}}.

The symbols of L^{X} compose strings of various kinds, and each of these strings has a family of interpretations. Certain strings are called terms, and their interpretations are functions. For each term t and for each finite set I of variables that contains the variables in t, there will be an interpretation t^{𝔐} : M^{I} → M. The precise definitions are thus:

• Each c is a term, and c^{𝔐}, besides being an element of M, can also be understood as the constant-function a ↦ c^{𝔐}: M^{I} → M.

• Each variable x is a term, interpreted as above.

• If t_{0}, …, t_{n−1} are terms, then ft_{0} … t_{n−1} is a term, with interpretation

a ↦ f^{𝔐}(t_{0}^{𝔐}(a), …, t_{n−1}^{𝔐}(a)): M^{I} → M.

The formulas are certain strings whose interpretations are relations. For any atomic formula α and any finite set I of variables that contains the variables appearing in α, there will be an interpretation α^{𝔐} that is a subset of M^{I}. The precise definitions are:

• If t_{0}, …, t_{n−1} are terms, then Rt_{0} … t_{n−1} is an atomic formula, with interpretation {a ∈ M^{I} : (t_{0}^{𝔐}(a), …, t_{n−1}^{𝔐}(a)) ∈ R^{𝔐}}.

• If t_{0} and t_{1} are terms, then t_{0} = t_{1} is an atomic formula, with interpretation {a ∈ M^{I} : t_{0}^{𝔐}(a) = t_{1}^{𝔐}(a)}.

The formulas in general are built up using the remaining logical symbols: The atomic formulas are formulas, and if ϕ and ψ are formulas, then so are (ϕ ∧ ψ), ¬ϕ and ∃x ϕ for any x in X. The interpretations are obvious:

• (ϕ ∧ ψ)^{𝔐} = ϕ^{𝔐} ∩ ψ^{𝔐};

• ¬ϕ^{𝔐} = (ϕ^{𝔐})^{c};

• ∃x ϕ^{𝔐} = ∃x^{𝔐}(ϕ^{𝔐}).

In particular, if ϕ^{𝔐} is a well-defined subset of M^{I}, then ∃x ϕ^{𝔐} is a welldefined subset of M^{I∖{x}}. Thus, the nullary relations 0 and 1 can arise as interpretations. To say precisely when they can arise, we recursively define the set FV(ϕ) of free variables of an arbitrary formula ϕ:

• FV(α) is the set of variables appearing in α, if α is atomic;

• FV(¬ϕ) = FV(ϕ);

• FV(ϕ ∧ ψ) = FV(ϕ) ∪ FV(ψ);

• FV(∃x ϕ) = FV(ϕ) ∖ {x}.

Then ϕ^{𝔐} is defined as a subset of M^{I}, provided FV(ϕ) ⊆ I.

Theorem 3.3 (Substitution). Suppose the following:

• ϕ is a formula of L^{X};

• I is a finite subset of X such that FV(ϕ) ⊆ I;

• u is an I-tuple of terms of L^{X};

• J is a finite subset of X that contains all variables in the entries in u.

Then there is a formula ϕ(u) of L^{X} such that FV(ϕ(u)) ⊆ J and, for every L-structure 𝔐, and for all a in M^{J},

a ∈ ϕ(u)^{𝔐} ⟺ (u_{i}^{𝔐}(a) : i ∈ I) ∈ ϕ^{𝔐}.

Example 3.4. If FV(ϕ) ⊆ I, and x is the identity on I (so x = (x : x ∈ I)), then we may assume that ϕ(x) is the same formula as x.

A sentence is a formula with no free variables. If σ is a sentence of L^{X}, and σ^{𝔐} = 1, then we say that 𝔐 is a model of σ.

Example 3.5. If FV(ϕ) ⊆ I, and a is an I-tuple of constant-symbols, then ϕ(c) is a sentence σ such that

σ^{𝔐} = 1 ⟺ c^{𝔐} ∈ ϕ^{𝔐},

where c^{𝔐} is (c_{i}^{𝔐} : i ∈ I).

We can also allow structures to be models of arbitrary formulas. Suppose ϕ is a formula of L^{X} and FV(ϕ) ⊆ I. If c is an I-tuple of constant-symbols that are not in L, and a is an I-tuple from M, then (𝔐, a) is a structure of L ∪ {c_{x} : x ∈ I} in the obvious way. Then 𝔐 is a model of ϕ, provided (𝔐, a) is a model of ϕ(c) for some tuple a.

The notations of § 2 involving ⊧ now make sense in the present context. If 𝔐 ⊧ ϕ, we say also that 𝔐 satisfies ϕ.

We may let L(M) be the disjoint union L ⊔ M, where each element of M is understood as a constant-symbol whose interpretation in 𝔐 is itself. Then we may ask whether 𝔐 is a model of a formula of L(M)^{X}.

In the following, ∃x is an abbreviation for

∃x_{0} ∃x_{1} … ∃x_{n−1} ,

where I = {x_{0}, …, x_{n−1}}.

Lemma 3.6. Suppose 𝔐 is an L-structure, and FV(ϕ) ⊆ I. The following are equivalent:

(0) 𝔐 satisfies ϕ;

(1) 𝔐 ⊧ ϕ(a) for some a in M^{I};

(2) 𝔐 ⊧ ∃x ϕ(x).

4 Types

Now suppose that the set X of individual-variables is {x_{i} : i ∈ ω}, and write L^{X} just as L. On the set of formulas of L with free variables in {x_{i} : i < n}, the relation ⊧ =| is an equivalence-relation; let us denote the set modulo the relation by

Fm^{n}(L).

Then ∧ and ¬ (and hence ∨) are well-defined operations on Fm^{n}(L), which is also partially ordered by ⊧ and, with respect to this, has a greatest element ⊤ and a least element ⊥.

An n-type of L is a subset Γ of Fm^{n}(L) such that

• ϕ, ψ ∈ Γ ⟹ ϕ ∧ ψ ∈ Γ;

• ϕ ∈ Γ & ϕ ⊧ ψ ⟹ ψ ∈ Γ;

• ⊤ ∈ Γ; the type is proper if ⊥ ∉ Γ; if proper, the type is complete if

• ϕ ∈ Fm^{n}(L) ∖ Γ ⟹ ¬ϕ ∈ Γ. The unique improper n-type is Fm^{n}(L) itself. Every subset of Fm^{n}(L) generates a type, possibly improper. The subset itself can be called consistent or finitely satisfiable if for every finite subset {ϕ_{i} : i < m} there is a structure satisfying ⋀_{i<m} ϕ_{i}. Lemma 4.1. A subset of Fm^{n}(L) is finitely satisfiable if and only if it generates a proper type.

In fact the structure (Fm^{n}(L), ∧, ∨, ¬, ⊥, ⊤, ⊧) is a Boolean algebra. A standard Boolean algebra is

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

where X is a set. One way to give a formal definition is the following. A Boolean ring is a (unital, associative) ring satisfying ∀x x · x = x. Lemma 4.2. Boolean rings are commutative and are of characteristic 2. Example 4.3. 𝔽_{2} is a Boolean ring.

Let (B, +, ·, 0, 1) be a Boolean ring, and define new operations and a relation on B by the following rules (which should be compared with the definition of χ̂_{𝔄} on p. 4):

• x ∧ y = xy;

• x ∨ y = x + y + xy;

• ¬x = 1 + x;

• x ⩽ y ⟺ x ∧ y = x;

• ⊥ = 0 and ⊤ = 1.

The structure (B, ∧, ∨, ¬, ⊥, ⊤, ⩽) arising thus is a Boolean algebra. Lemma 4.4. If (B, ∧, ∨, ¬, ⊥, ⊤, ⩽) is a Boolean algebra, then the Boolean ring from which it arises is given by

• xy = x ∧ y;

• x + y = ¬(¬x ∧ ¬y) ∧ ¬(x ∧ y);

• ⊤ = 1 and ⊥ = 0. Lemma 4.5. Fm^{n}(L) is a Boolean algebra.

A subset F of a Boolean algebra is a filter if the set {x : ¬x ∈ F } is an ideal of the corresponding ring; F is principal if I is principal; F is an ultra-filter if I is maximal. (The unique improper filter is the algebra itself; an ultra-filter must be proper.) Lemma 4.6. Types of Fm^{n}(L) are just filters; complete types are just ultrafilters.

The set of ultra-filters of a Boolean algebra 𝔅 is denoted

S(𝔅)

and called its Stone space, because of the following. If x ∈ B, let

[x]

be the subset {F : x ∈ F } of S(𝔅). Theorem 4.7 (Stone Representation). If 𝔅 be a Boolean algebra, then the map

x ↦ [x] : 𝔅 → 𝒫(S(𝔅))

is an embedding of Boolean algebras. Corollary 4.8. The subsets [x] of S(𝔅) compose a basis of open sets and of closed sets for a topology on S(𝔅), which topology is compact and Hausdorff.

For every subset X of B, let \overline{X} be the subset ⋂_{x∈X}[x] of S(𝔅). Lemma 4.9. Suppose 𝔅 is a Boolean algebra.

(0) The map

X ↦ \overline{X} : 𝒫(B) → 𝒫(S(𝔅))

is inclusion-reversing and takes unions to intersections, and its range is the set of closed subsets of S(𝔅).

(1) The map

Y ↦ ⋂ Y : 𝒫(S(𝔅)) → 𝒫(𝔅)

is inclusion-reversing and takes unions to intersections, and its range is the set of filters of 𝔅.

(2) If X ⊆ B, then ⋂ \overline{X} is the filter of 𝔅 generated by X.

(3) If Y ⊆ S(𝔅), then \overline{⋂ Y} is the topological closure of Y.

hence X ↦ \overline{X} gives a one-to-one correspondence, with inverse Y ↦ ⋂ Y, between filters of 𝔅 and closed subsets of S(𝔅).

So the complete n-types of L compose a compact Hausdorff space, denoted

S^{n}(L),

whose closed subsets are just the sets \overline{Γ} determined by arbitrary n-types Γ.

A theory of L is a 0-type The improper 0-type of L is the unique inconsistent theory of L.

Since Fm^{0}(L) embeds in Fm^{n}(L), a theory T of L determines a closed subset of S^{n}(L), denoted

S^{n}(T).

Then an arbitrary n-type Γ is consistent with T if Γ ∪ T is consistent, equivalently, \overline{Γ} ∩ S^{n}(T) ≠ 0.

Theorem 4.10 (Compactness). Every consistent theory has a model.

Proof. Let T be a theory of L. The proof that T has a model has three parts:

(0) There is a signature L′ such that L ⊆ L′, and L′ ∖ L consists of constantsymbols, and there is a bijection

ϕ ↦ c_{ϕ} : Fm^{1}(L′) → L′ ∖ L.

Now let H(T) be the set S^{0}(T) ∩ ⋂_{ϕ∈Fm^{1}(L′)}[∃x_{0} ϕ → ϕ(c_{ϕ})].

(1) Let T′ be an element of H(T). Then T′ has a canonical model, whose universe is L′ ∖ L modulo the equivalence-relation ∼ given by

c ∼ d ⟺ T′ ⊧ c = d.

(2) H(T) is non-empty.

Note that H(T) is non-empty by Corollary 4.8, in particular, compactness of S^{0}(T).

If Γ is an n-type, and c is an n-tuple of constant-symbols, then the set {ϕ(c) : ϕ ∈ Γ} can be denoted

Γ(c).

A structure 𝔐 realizes Γ if 𝔐 ⊧ Γ(a) for some tuple a from M; otherwise the structure omits the type.

An complete type p is: isolated, if {p} is open; limit, if not. These definitions can be understood absolutely, as stated, or over some theory T.

Lemma 4.11. The isolated types are precisely the principal complete types. Every type included in a principal type over a complete theory T is realized in every model of T. If Γ is a type consistent with an (arbitrary) theory T, then the following are equivalent:

(0) Γ is not included in a principal type over T; (1) \overline{Γ} has empty interior in S^{n}(T);

(2) \overline{Γ}^{c} is a dense open subset of S^{n}(T).

Example 4.12. Let L be {c_{n} : n ∈ ω} ∪ {P }, where the c_{n} are constantsymbols and P is a unary relation-symbol. Let T be the theory generated by {P c_{n} : n ∈ ω}. Then

T ⊧ ¬P x → x ≠ c_{n}

for each n, so the principal type generated by ¬P x includes the type generated by {x ≠ c_{n} : n ∈ ω}; but the latter type is not principal.

A partial converse is the Omitting-Types Theorem below, whose proof is based on [7, ch. 10]. First:

Lemma 4.13. The intersection of countably dense open subsets of a compact Hausdorff space is also dense.

Proof. Suppose X is a compact Hausdorff space. Then X is locally compact, that is, every neighborhood of every point includes a compact neighborhood. Indeed, let U be an open neighborhood of P. For each x in U^{c} there are disjoint open neighborhoods V_{x} and U_{x} of x and P respectively. Some finite union of sets V_{x} covers U^{c}; the complement is included in U and is a closed—hence compact—neighborhood of P, since it includes the corresponding intersection of sets U_{x}.

Now suppose {O_{n} : n ∈ ω} is a collection of dense open subsets of X. We can recursively define a decreasing chain U_{0} ⊇ K_{0} ⊇ U_{1} ⊇ K_{1} ⊇ U_{2} ⊇ … of sets, and at the same time a sequence (P_{n} : n ∈ ω) of points, such that:

• U_{0} = U;

• U_{n} is open;

• P_{n} ∈ U_{n} ∩ O_{n};

• K_{n} is compact, and P_{n} ∈ K_{n} ⊆ U_{n} ∩ O_{n};

• P_{n} ∈ U_{n+1} ⊆ K_{n}.

Then ⋂_{n∈ω} K_{n} is a nonempty subset of U included in each set O_{n}.

Theorem 4.14 (Omitting Types). Let T be a consistent theory of a countable signature L. For every countable collection of types Γ, none included in a principal type, T has a countable model omitting each Γ.

Proof. To the proof of the Compactness Theorem, we add a step:

(3) H(T) has an element T′ such that, for each tuple c of elements of L′ ∖ L,

and for each Γ,

T′ ∉ \overline{Γ(c)},

that is, Γ(c) ⊈ T′.

To prove this, by Lemma 4.13, it is enough to show that each closed set \overline{Γ(c)} has dense complement in H(T), since then the intersection of these complements is dense and so non-empty.

Every open subset of H(T) is a union of sets [ψ(d)] ∩ H(T), where ψ is a formula of L, and d is a tuple of elements of L′ ∖ L. Supposing

T′ ∈ [ψ(d)] ∩ H(T),

we shall derive an element T^{∗} of [ψ(d)] ∩ H(T) ∖ \overline{Γ(c)}.

Each entry of (c, d) is c_{ϕ^{0}} for some formula ϕ^{0}, which contains finitely many constant-symbols c_{ϕ^{1}}; each ϕ^{1} contains finitely many constant-symbols c_{ϕ^{2}}, and so on. The constant-symbols arising in this way form a finitely branching tree with no infinite branches; hence they are finitely numerous and compose a tuple e.

Hence if c_{ϕ} is one of the terms of (c, d, e), then the constant-symbols used in ϕ also appear in (c, d, e). Hence there is a formula θ of L such that θ(c, d, e) is the conjunction of ψ(d) and the sentences

∃x_{0}ϕ → ϕ(c_{ϕ})

such that c_{ϕ} appears in (c, d, e).

Let 𝔐 be the canonical model of T′. Then 𝔐 ⊧ θ(c, d, e). The open set [∃y ∃z θ(x, y, z)] is therefore a non-empty subset of S^{n}(T), so it is not included in \overline{Γ}. Suppose

p ∈ [∃y ∃z θ(x, y, z)] ∖ \overline{Γ}.

By the Compactness Theorem, T has a countable model 𝔑 realizing p with some tuple a. There is a bijection f between L′ ∖ L and N such that f(c) = a and

𝔑 ⊧ θ(f(c, d, e)).

This bijection determines the desired T^{∗}.

References

[1] Stanley N. Burris. Logic for Mathematics and Computer Science. Prentice Hall, Upper Saddle River, New Jersey, USA, 1998.

[2] C. C. Chang and H. J. Keisler. Model theory, volume 73 of Studies in Logic and the Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, third edition, 1990.

[3] Alonzo Church. Introduction to mathematical logic. Vol. I. Princeton University Press, Princeton, N. J., 1956.

[4] Wilfrid Hodges. Model theory, volume 42 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge, 1993.

[5] David W. Kueker. An introduction to mathematical logic. course notes, 1989.

[6] David Marker. Model theory, volume 217 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. An introduction.

[7] Bruno Poizat. A course in model theory. Universitext. Springer-Verlag, New York, 2000. An introduction to contemporary mathematical logic, Translated from the French by Moses Klein and revised by the author.

Hints

• Lemma 2.4: Prove that for each n there is a unique such function on the set of formulas of length at most n.

• Theorem 2.7: It’s a simple chain of equivalences, justified by Lemma 2.6.

• Theorem 2.8: Say V = {P_{n} : n ∈ ω}. Define V_{n} = {P_{i} : i < n}. Let T be the set of structures on the various V_{n}. Order T by the rule

(A, V_{m}) ⩽ (B, V_{n}) ⟺ m ⩽ n ∧ A = V_{m} ∩ B.

Then (T, ⩽) is a tree. Consider the set comprising those (A, V_{m}) such that, for all F in Φ, if V_{F} ⊆ V_{m}, then (A, V_{m}) ⊧ F. This set forms an infinite sub-tree of T. Hence the sub-tree includes an infinite chain.

• Lemma 2.9: Use f_{↔}.

• Lemma 2.10: Use the various f_{∗}.