Model-Theory to Compactness

David Pierce October 26, 2001

Contents

0 Introduction 1 1 The natural numbers 1 2 Cartesian powers 2 3 Structures and signatures 2 4 Homomorphisms and embeddings 3 5 Functions and terms 3 6 Algebras 4 7 Boolean algebras 7 8 Propositional logic 9 9 Relations and formulas 10 10 Elementary embeddings 11 11 Models and theories 12 12 Compactness 12

0 Introduction

These notes are an attempt to develop model theory, as economically as possible, on a foundation of some familiarity with algebraic structures. (Formal definitions of these structures are given in § 6.) References for model-theory include [1], [2] and [3].

Words in boldface are technical terms and are often being defined, implicitly or explicitly, by the sentence in which they occur.

1 The natural numbers

By one standard definition, the set ω of natural numbers is the smallest set that contains the empty set and that contains x ∪ {x} whenever it contains x. The empty set will be denoted 0 here, and x ∪ {x}, the successor of x, can be denoted x′. The triple (ω,′, 0) will turn out to be an example of a structure.

Throughout these notes, n will be a natural number, understood as the set {0, 1, 2, …, n − 1}, possibly empty; and i will range over the elements of this set. Also m will be a natural number.

2 Cartesian powers

Let M be a set. The Cartesian power M^{n} is the set of functions from n to M. Such a function will be denoted by a boldface letter, as a, but then its value a(i) at i will be denoted a_{i}. The function a can be identified with the n-tuple (a_{0}, …, a_{n−1}) of its values.

In particular, the power M^{0} has but a single member, () or 0; hence M^{0} = 1. This is so, even if M = 0; however, 0^{n} = 0 when n is positive (different from 0). The set M itself can be identified with the power M^{1}.

Any function f : m → n determines the map

a ↦ (a_{f(0)}, …, a_{f(m−1)}) : M^{n} → M^{m},

no matter what set M is. In case m = 1, we have the coordinate projections a ↦ a_{i}.

The Cartesian product A × B of sets A and B is identified with the set of (ordered) pairs (a, b) such that a ∈ A and b ∈ B. There is a map

M^{n} × M^{m} ⟶ M^{n+m}
(a, b) ⟼ (a_{0}, …, a_{n−1}, b_{0}, …, b_{m−1}),

often considered an identification.

3 Structures and signatures

A function on the set M is a map M^{n} → M; the function then is n-ary— its arity is n. A nullary (that is, 0-ary) function is a constant and can be identified with an element of M.

An n-ary relation on M is a subset of M^{n}. There are two nullary relations, namely 0 and 1. The relation of equality is binary (2-ary).

A structure is a set equipped with some distinguished constants and with some functions and relations of various positive arities. The set then is the universe of the structure. If the universe is M, then the structure might be denoted M or just M again. However, the structure (ω,′, 0) is denoted N. (This structure is often considered to contain the binary functions of addition and multiplication as well, but these are uniquely determined by the successorfunction.)

Examples. A set with no distinguished relations, functions or constants is trivially a structure. Groups, rings and partially ordered sets are structures. A vector space is a structure whose unary functions are the multiplications by the scalars. A valued field can be understood as a structure when the valuation ring is distinguished as a unary relation.

The signature of a structure contains a symbol for each function, relation and constant in the structure; the function, relation or constant is then the interpretation of the symbol. Notationally, the symbols are primary; their interpretations can be distinguished, if need be, by superscripts indicating the structure.

Examples. The complete ordered field R has the signature {+, −, ·, ⩽, 0, 1}. The ordered field Q of rational numbers has the same signature. The binary functionsymbol + is interpreted in R by addition of real numbers; the interpretation is also denoted by +, or by +^{R} if it should be distinguished from addition +^{Q} of rational numbers. To make its signature explicit, we can write R as the tuple (R, +, −, ·, ⩽, 0, 1); in the latter notation, we can understand R as the set of real numbers.

A structure in a given signature, say L′, can be understood as a structure with a smaller signature, say L: just ignore the interpretations of the symbols in L′ − L. The structure in L is then a reduct of the structure in L′, which is in turn an expansion of the structure in L.

Example. The abelian group (R, +, −, 0) is a reduct of the ordered field (R, +, −, ·, ⩽, 0, 1); the group can be expanded to the ordered field.

Throughout these notes, L will be a signature, and f, R and c will range respectively over the function-, relation- and constant-symbols in L. The structures with signature L compose the class 𝔐𝔬𝔡(L).

4 Homomorphisms and embeddings

Suppose M and N are in 𝔐𝔬𝔡(L), and h is a map M → N. (So, N must be nonempty, unless M is empty.) Then h induces maps M^{n} → N^{n} in the obvious way, even when n = 0; so, h(a)(i) = h(a_{i}), and h(0) = 0. The map h is a homomorphism from M to N if it preserves the functions, relations and constants symbolized in L, that is,

• h(f^{M}(a)) = f^{N} (h(a));

• h(a) ∈ R^{N} when a ∈ R^{M};

• h(c^{M}) = c^{N}.

Any map preserves equality. A homomorphism is an embedding if it preserves both inequality and the complements of the relations symbolized in L. In particular, the underlying map of an embedding is injective (or one-to-one); if it is also surjective (or onto), then the embedding is an isomorphism.

We may confuse a structure with its isomorphism-class.

Examples. A group-homomorphism is a homomorphism of groups; a groupmonomorphism is an embedding of groups; a group-isomorphism is an isomorphism of groups.

If M ⊆ N, and the inclusion-map of M in N is an embedding of M in N, then we write

M ⊆ N

and say that M is a substructure of N.

Example. A subgroup of a group is a substructure of a group, and in fact any substructure of a group is a subgroup. However, while Z is a substructure of R, it is not a subfield (because it is not a field).

5 Functions and terms

Suppose M is in 𝔐𝔬𝔡(L). Various functions on M can be derived, by composition, from:

• the functions f^{M},

• the constants c^{M}, and

• the coordinate projections.

These compositions can be described without reference to M; the result is the terms of L.

The interpretation t^{M} in M of an n-ary term t of L will be an n-ary function on M. Terms can be defined as strings of symbols so that the following hold:

• Each constant-symbol c is also an n-ary term whose interpretation in M is the constant map a ↦ c^{M} on M^{n}.

• There is an n-ary term x_{i} whose interpretation in M is the coordinate projection a ↦ a_{i} on M^{n}.

• If t_{0}, …, t_{n−1} are m-ary terms, and f is n-ary, then there is an m-ary term—call it f(t_{0}, …, t_{n−1})—whose interpretation is the map

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

By this account, an n-ary term is also n + 1-ary. The nullary terms are the constant terms; the terms x_{i} are the variables.

Lemma. If t is an n-ary term, and u_{0}, …, u_{n−1} are m-ary terms, then there is an m-ary term whose interpretation in M is the map

a ↦ t^{M}(u_{0}^{M}(a), …, u_{n−1}^{M}(a)).

The new term in the lemma can of course be denoted t(u_{0}, …, u_{n−1}).

We can identify terms whose interpretations are indistinguishable in every structure. In particular, if t is n-ary, but not (n − 1)-ary, then t is precisely t(x_{0}, …, x_{n−1}), which we may abbreviate as t(x). Sometimes letters like x, y and z are used for variables.

If A is a subset of M, we let L(A) be the signature L augmented with a constant-symbol for each element of A. The symbols and the elements are generally not distinguished notationally, and an L-structure M naturally determines an L(A)-structure, denoted M_{A} if there is a need to distinguish.

Lemma. Every term of L(A) is t(a, x) for some term t of L and tuple a from A.

6 Algebras

Suppose M ∈ 𝔐𝔬𝔡(L). An equation

t = u

of n-ary terms of L is an identity of M if t^{M} = u^{M}; we can then write

M ⊧ t = u

and say that M is a model of t = u or that M satisfies the identity.

Suppose L contains no relation-symbols. An element of 𝔐𝔬𝔡(L) can be called an algebra. A set of equations of terms of L determines a variety of L (namely the subclass of 𝔐𝔬𝔡(L) comprising each structure that is a model of each equation.) A substructure of an element of a variety is also in the variety.

Several standard classes of mathematical structures are varieties or subclasses of these, in signatures comprising some of:

0. the constant-symbols 0 and 1, for zero and one;

1. the unary function-symbols − and ^{−1}, for additive and multiplicative inversion;

2. the binary function-symbols + and ·, for addition and multiplication.

Specific signatures involving these symbols are sometimes named thus:

The set: … is the signature of:
{·} semi-groups
{·, 1} monoids
{·,^{−1} , 1} groups
{+, −, 0} abelian groups
{+, −, ·, 0, 1} rings

The corresponding structures will be defined presently. First, terms with these symbols are customarily written so that:

• 0, 1 and the variables x_{i} are terms;

• if t is a term, then so are (−t) and t^{−1};

• if t and u are terms, then so are (t + u) and (t · u).

Abbreviations of terms are also customary, so that, for example: outer brackets can be removed; tu means t · u; t − u means t + −u; t ∗ u ∗ v means ((t ∗ u) ∗ v), where each ∗ is the same symbol + or ·; and t + uv means t + (uv).

A semi-group is a model of the identity

x(yz) = xyz.

Examples. The empty set is the universe of a semi-group. The structure (M, ⌢) is a semi-group, where M comprises the strings

|| ⋯ |

consisting of some (positive, finite) number of strokes, and ⌢ is concatenation of strings.

A monoid is a semi-group satisfying the identities

x · 1 = x,
1 · x = x.

Examples. Let M comprise the functions from some set to itself; let ∘ be functional composition; and let id be the identity-function on M. Then (M, ∘, id) is a monoid. So is (ω, +, 0).

A group is a monoid satisfying

x · x^{−1} = 1,
x^{−1} · x = 1.

The group is abelian if it satisfies xy = yx—though, as noted, an abelian group is usually ‘written additively,’ with the signature {+, −, 0}.

Examples. The group (Z, +, −, 0) of integers is abelian; so is the group (S, ·,^{−1} , 1), where S is the circle {z ∈ C : |z| = 1}, comprising the complex numbers of modulus 1.

A ring is a structure (R, +, −, ·, 0, 1) such that:

• (R, +, −, 0) is an abelian group;

• (R, ·, 1) is a monoid;

• the identities x(y + z) = xy + xz and (x + y)z = xz + yz are satisfied.

By this definition, there is a ring, the trivial ring, satisfying 0 = 1, but its universe comprises a unique element.

A ring is commutative if it satisfies xy = yx. In a commutative ring, an element a is called:

• a zero-divisor if a ≠ 0, but ab = 0 for some non-zero b in the ring;

• a unit if ab = 1 for some b in the ring.

Then a zero-divisor cannot be a unit, and zero is a unit only in the trivial ring. The set of units of a commutative ring R is denoted

R^{×}.

Then (R^{×}, ·, 1) is a (well-defined) monoid and can be expanded to a group. A non-trivial ring is an integral domain if it is commutative and contains no zero-divisors.

Henceforth in this section, let ring mean non-trivial commutative ring, and let (R, +, −, ·, 0, 1) be such a ring. Then R is an integral domain just in case (R − {0}, ·, 1) is a well-defined monoid. If this monoid can be expanded to a group, then R is a field. Hence R is a field just in case R^{×} comprises all non-zero elements of R.

Examples. The sets Q, of rational numbers; R, of real numbers; and C, of complex numbers—each is the universe of a field. So is their subset {0, 1} (though the resulting field is not a substructure of these). Over any field K can be formed the polynomial-ring

K[x_{0}, …, x_{n−1}],

which can be defined as follows. First say that n-ary terms t and u of L(K) are equivalent if the identity t = u is satisfied in every field of which K is a substructure. (If K is infinite, it is enough that t^{K} = u^{K}.) Then K[x_{0}, …, x_{n−1}] comprises the equivalence-classes of the n-ary terms of L(K).

The signature of R-modules is the signature of abelian groups, with a unary function-symbol for each element of R. A structure with this signature is an R-module just in case the structure is an abelian group satisfying all identities

r(x + y) = rx + ry,
(r + s)x = rx + sx,
r(sx) = rsx,
1(x) = x,

where r and s are in R.

Example. Every Cartesian power of R is an R-module; in particular, R is an R-module.

A submodule of R is a substructure of R when R is considered as an Rmodule. Any subset A of R generates the submodule

(A),

which is the smallest submodule including A. A proper submodule of R is an ideal of R (although R is sometimes called an improper ideal of itself). If I is an ideal of R, then the quotient R/I is a ring, whose elements are the cosets r + I, where r ∈ R. (Here r + I = {r + a : a ∈ I}.)

Example. Any two integers a and b have a greatest common divisor, sometimes denoted (a, b), which can be found by the Euclidean algorithm; this integer generates the submodule of Z that is also denoted (a, b). Thus every ideal of Z is principal—generated by a single element. If n is a non-zero integer, then the quotient Z/(n) is finite, and its universe can be identified with n. The quotient Z/(0) is Z itself.

If h : R → S is a homomorphism of rings, then its kernel comprises a in R such that h(a) = 0; this kernel is an ideal of R. Every ideal I of R is the kernel of the quotient-map from R to R/I.

Example. Suppose a ∈ C^{m}. Then there is a ring-homomorphism from C[x_{0}, …, x_{n+m−1}] to C[x_{0}, …, x_{n−1}], namely

t(x_{0}, …, x_{n+m−1}) ⟼ t(x_{0}, …, x_{n−1}, a).

The kernel is an ideal.

An ideal I of R is prime if the complement R − I is closed under multiplication. An ideal of R is maximal if no ideal of R properly includes it.

Theorem. Suppose I is an ideal of the commutative ring R. Then:

• I is prime if and only if R/I is an integral domain;

• I is maximal if and only if R/I is a field.

A corollary of the theorem is that maximal ideals are prime.

Examples. The prime ideals of Z are the ideals (p), where p is a prime number; these ideals are maximal. Hence the quotients Z/(p) are fields, which can be denoted F_{p}. The quotient C[x]/(x^{2}) is not an integral domain, since (x^{2}) is not prime. The quotient C[x]/(x) is just C, so (x) is a maximal ideal.

7 Boolean algebras

An essential and notationally exceptional example is the Boolean algebra of subsets of a set Ω; this structure is the tuple

(P(Ω), ∩, ∪,^{c}, ∅, Ω),

but we shall consider the signature of Boolean algebras to be the set

{∧, ∨, ¬, 0, 1}.

A Boolean ring is a ring satisfying

x^{2} = x.

In particular, such a ring satisfies (x + y)^{2} = x + y, hence

xy + yx = 0;

replacing y with x, we get 2x = 0, hence

−x = x;

so the signature of Boolean rings can be considered to be {+, ·, 0, 1}. We also get xy = yx, so the ring is commutative. We have x(1 + x) = 0, so if x is a unit, then 1 + x = 0, so x = 1. Thus also every nonzero nonunit of a Boolean ring is a zero-divisor. Hence the only Boolean integral domain is the two-element ring {0, 1}, which is the field F_{2}. Therefore prime ideals of Boolean rings are maximal, since the quotient of a Boolean ring by an ideal is Boolean.

In terms in the signature of Boolean algebras, customarily negation (¬) has priority over conjunction (∧) and disjunction (∨). A structure in this signature is a Boolean algebra if it can be expanded to a signature containing + in such a way that:

• the identities

x ∨ y = x + y + (x ∧ y),
¬x = x + 1

are satisfied, and

• this expansion, reduced to the signature {+, ∧, 0, 1}, is a Boolean ring.

If such an expansion is possible, then it is obtained by defining

x + y = (x ∧ ¬y) ∨ (y ∧ ¬x).

The algebra (P(Ω), ∩, ∪,^{c}, ∅, Ω) is a Boolean algebra, since the required expansion is obtained by interpreting + as symmetric difference, △.

Any Boolean algebra has a partial order ⩽ such that

x ⩽ y ⟺ x ∧ y = x;

its interpretation in P(Ω) is inclusion (⊆).

An ideal of a Boolean algebra is just an ideal of the corresponding ring. A filter of a Boolean algebra is dual to an ideal, so F is a filter just in case {¬x : x ∈ F } is an ideal. An ultrafilter is dual to a maximal ideal. So, F is a filter just in case

1 ∈ F,
x, y ∈ F ⟹ x ∧ y ∈ F,
x ∈ F and x ⩽ y ⟹ y ∈ F,
0 ∉ F;

also, a filter F is an ultrafilter just in case

x ∨ y ∈ F ⟹ x ∈ F or y ∈ F,

equivalently, x ∉ F ⟹ ¬x ∈ F.

The set of ultrafilters of a Boolean algebra is the Stone-space of the algebra. For every element x of a Boolean algebra, the corresponding Stone-space has a subset [x] comprising the ultrafilters containing x. Then

[x] ∩ [y] = [x ∧ y]

since the elements of these sets are filters; since they are ultrafilters, we have also

[x] ∪ [y] = [x ∨ y],
[x]^{c} = [¬x].

Finally, [1] is the whole Stone-space, and [0] is empty. Therefore the map

x ⟼ [x]

is a homomorphism of Boolean algebras; it is an embedding, since [x] is nonempty when x ≠ 0.

A lower bound of a subset A of a Boolean algebra is an element a of the algebra such that

a ⩽ x

whenever x ∈ A; this lower bound is an infimum of A if b ⩽ a whenever b is a lower bound of A. Infima are unique when they exist; but they may not exist. However,

inf{x, y} = x ∧ y,

so infima of finite sets exist. Also, if A ⊆ P(Ω), then inf A is the intersection of A. Thus every Boolean algebra embeds in an algebra where infima exist. However, an embedding need not preserve infima.

Example. Let A comprise the cofinite subsets of ω. Then inf A = ∅. However, A is a filter of P(ω), so A is included in an ultrafilter F. In the Stone-space,

F ∈ [x]

whenever x ∈ A; so [∅] is not the infimum of {[x] : x ∈ A}.

A topology for a set Ω is a substructure of (P(Ω), ∩, ∪, 0, 1) that is closed under arbitrary intersection. (So the topology contains, for each of its subsets, the infimum that exists in P(Ω).) The elements of the topology are the closed sets; their complements are open. A basis for a topology is just a substructure of (P(Ω), ∪, 0, 1); the closed sets are then intersections of sets in the basis.

A topology is Hausdorff if any two distinct elements of the underlying set are contained in disjoint open sets.

A subset of P(Ω) has the finite-intersection property if it generates a (proper) filter. A topology for Ω is compact if every collection of closed sets with the finite-intersection property has non-empty intersection. It is enough that these closed sets be in the basis, if there is one.

In particular, the subsets [x] of a Stone-space compose a basis for a topology, and these basic sets are clopen. The topology is Hausdorff, since two distinct points of the space are respectively contained in some disjoint sets [x] and [¬x].

Suppose B is a subset of a Boolean algebra. Then the following are equivalent:

• the collection {[x] : x ∈ B} has the finite-intersection property;

• the set B generates a filter of the algebra;

• B included in an ultrafilter of this algebra;

• {[x] : x ∈ B} has nonempty intersection.

Thus the topology of the Stone-space is compact. Consequently, every clopen set is one of the sets [x].

Of the nonempty set Ω, we can see the Boolean ring P(Ω) of its subsets as a compact topological ring. For, we can identify any subset A of Ω with its characteristic function, the map from Ω to F_{2} taking x to 1 just in case x ∈ A. The set of such maps can be denoted F_{2}^{Ω}. With the discrete topology, in which every subset is closed, F_{2} is a compact topological ring. Therefore on F_{2}^{Ω} is induced a ring-structure and a compatible topology—the producttopology or topology of pointwise convergence, compact in this case since F_{2} is compact. The induced ring-structure makes the bijection from P(Ω) to F_{2}^{Ω} a homomorphism. In the induced topology, every finite subset of Ω determines for the zero-map on Ω an open neighborhood, comprising those maps into F_{2} that are zero on that finite subset. Translating such a neighborhood by an element of F_{2}^{Ω} gives an open neighborhood of that element, and every open subset of F_{2}^{Ω} is a union of such neighborhoods; the finite unions are precisely the clopen subsets.

8 Propositional logic

The terms in the signature of Boolean algebras—the Boolean terms—can be considered as strings of symbols generated by the following rules:

• each constant-symbol 0 or 1 is a term;

• each symbol x_{i} for a coordinate projection is a term;

• if t and u are terms, then so are (t ∧ u) and (t ∨ u) and ¬t.

A term here is n-ary just in case i < n whenever x_{i} appears in the term. Instead of (⋯ (((t_{0} ∗ t_{1}) ∗ t_{2}) ∗ ⋯ ∗ t_{n−1}) we can write

t_{0} ∗ t_{1} ∗ t_{2} ∗ ⋯ ∗ t_{n−1},

where each ∗ is (independently) ∧ or ∨.

Lemma. Every n-ary function on F_{2} is the interpretation of an n-ary Boolean term.

Proof. Suppose f be an n-ary function on F_{2}, and let a^{0}, …, a^{m−1} be the elements of F_{2}^{n} at which f is 1. If m = 0, then f is the interpretation of 0. If m > 0, then f is the interpretation of

t^{0} ∨ ⋯ ∨ t^{m−1},

where t^{j} is u_{0}^{j} ∧ ⋯ ∧ u_{n−1}^{j}, where u_{i}^{j} is x_{i}, if a_{i}^{j} = 1, and otherwise is ¬x_{i}.

The Boolean terms can be considered as the propositional formulas composing a propositional logic. The constant-symbols 0 and 1 can then be taken to stand for false and true statements, respectively; an element of F_{2}^{ω} is a truthassignment to the propositional variables x_{i}, and under such an assignment σ, a propositional formula t takes on the truth-value

t^{F_{2}}(σ(0), …, σ(n − 1))

if t is n-ary. Write ⟨σ, t⟩ for the truth-value of t under σ. A model for a set of propositional formulas is a truth-assignment σ sending the set to 1 under the map t ↦ ⟨σ, t⟩.

Theorem (Compactness for sentential logic). A set of propositional formulas has a model if each finite subset does.

Proof. If a set of sentences t satisfies the hypothesis, then the collection of closed subsets {σ : ⟨σ, t⟩ = 1} of F_{2}^{ω} has the finite-intersection property.

The sets {σ : ⟨σ, t⟩ = 1} are precisely the clopen subsets of F_{2}^{ω}.

9 Relations and formulas

From the relations R^{M} and the interpretations t^{M} of terms t, new relations on M can be derived by various techniques. These relations will be the 0-definable relations of M, and each of them will be the interpretation of a formula of L. (The definable relations of M are the interpretations of formulas of L(M).) Distinctions are made according to which techniques are needed to derive the relations.

The atomic formulas are given thus:

• If t and u are n-ary terms, then there is an n-ary atomic formula t = u whose interpretation (t = u)^{M} is {a ∈ M^{n} : t^{M}(a) = u^{M}(a)}.

• If t_{0}, …, t_{n−1} are m-ary terms, and R is n-ary, then there is an mary atomic formula—call it R(t_{0}, …, t_{n−1})—whose interpretation is {a ∈ M^{m} : (t_{0}^{M}(a), …, t_{n−1}^{M}(a)) ∈ R^{M}}.

(In particular, R(x_{0}, …, x_{n−1})^{M} = R^{M}.)

A literal is an atomic formula or its negation. The negation of an atomic formula α can be written

¬α,

but the negation of t = u is also t ≠ u. The interpretation in M of ¬α is the complement of α^{M}.

A literal is an example of a basic or quantifier-free formula. If t is an n-ary Boolean term, and ϕ_{0}, …, ϕ_{n−1} are m-ary atomic formulas, then there is an mary basic or quantifier-free formula, say t(ϕ_{0}, …, ϕ_{n−1}), whose interpretation in M is

t^{P(M^{m})}(ϕ_{0}^{M}, …, ϕ_{n−1}^{M}).

If we identify formulas that have indistinguishable interpretations in every structure, then the set of basic formulas is a Boolean algebra generated by the atomic formulas. (This assumes that the Boolean terms 0 and 1 are also n-ary formulas. If n > 0, then these are identified respectively with x_{0} ≠ 0 and x_{0} = x_{0}. If n = 0, then the formulas might be written ⊥ and ⊤; but some model-theorists don’t use such formulas.)

The set of formulas is then the smallest Boolean algebra containing the atomic formulas and closed under the operation of existential quantification; this converts an n + 1-ary formula ϕ into an n-ary formula ∃x_{n} ϕ whose interpretation is the image of ϕ^{M} under the map

(a_{0}, …, a_{n}) ↦ (a_{0}, …, a_{n−1}) : M^{n+1} → M^{n}.

The Boolean algebra of n-ary formulas of L can be denoted Fm^{n}(L). The formula ¬∃x_{n} ϕ is also denoted ∀x_{n} ¬ϕ, and ¬ϕ ∨ ψ is denoted ϕ → ψ.

Lemma. If ϕ is an n-ary formula, and t_{0}, …, t_{n−1} are m-ary terms, then there is an m-ary formula ϕ(t_{0}, …, t_{n−1}) with the obvious interpretation.

In particular, if it is not also n − 1-ary, then an n-ary formula ϕ is the same as the formula ϕ(x_{0}, …, x_{n−1}).

The A-definable relations of M are the interpretations in M of formulas of L(A). In particular, they are the sets ϕ(a_{0}, …, a_{m−1}, x_{0}, …, x_{n−1})^{M}, where ϕ is an m + n-ary formula of L, and a is a tuple from A.

Sentences are 0-ary formulas.

10 Elementary embeddings

Suppose M and N are members of 𝔐𝔬𝔡(L). We can now say that an embedding of M in N is a map h : M → N such that

h^{−1}(ϕ^{N}) = ϕ^{M}

for all basic formulas ϕ of L (or just all literals of L); if the same holds for all formulas ϕ of L, then h is an elementary embedding. If M ⊆ N, and the inclusion-map of M in N is an elementary embedding, we write

M ≼ N

and say M is an elementary substructure of N.

Lemma (Tarski–Vaught). Suppose M ⊆ N. Then M ≼ N, provided that

ϕ(a, x_{0})^{N} ∩ M

is nonempty whenever ϕ(a, x_{0})^{N} is, for all L-formulas ϕ and all tuples a from M.

Proof. Let Σ comprise the formulas ϕ such that

ϕ(x_{0}, …, x_{n−1})^{M} = ϕ(x_{0}, …, x_{n−1})^{N} ∩ M^{n}.  (∗)

Then Σ contains all the basic formulas and is closed under the Boolean operations. Suppose ϕ is in Σ and a is in M^{n}. Then

ϕ(a, x_{0})^{M} = ϕ(a, x_{0})^{N} ∩ M.

By hypothesis then, ϕ(a, x_{0})^{M} and ϕ(a, x_{0})^{N} are alike empty or not. Hence (∗) holds, mutatis mutandis, with ∃x_{n−1}ϕ in place of ϕ. Therefore Σ = Fm(L).

11 Models and theories

Suppose ϕ ∈ Fm^{n}(L), and a ∈ M^{n}, so that ϕ(a) ∈ Fm^{0}(L(M)). Then

ϕ(a)^{M} = {() ∈ M^{0} : (a_{0}^{M}(), …, a_{n−1}^{M}()) ∈ ϕ^{M}}
= {() ∈ M^{0} : a ∈ ϕ^{M}}.

So ϕ(a)^{M} = 1 if a ∈ ϕ^{M}, and in this case we write

M ⊧ ϕ(a);

if a ∈ M^{n} − ϕ^{M}, then ϕ(a)^{M} = 0, and M ⊧ ¬ϕ(a). The map h : M → N is an elementary embedding just in case

M ⊧ ϕ(a) ⟺ N ⊧ ϕ(h(a))

for all such ϕ and a.

If K is a subclass of 𝔐𝔬𝔡(L), then the theory Th(K) of K is the subset of Fm^{0}(L) comprising σ such that M ⊧ σ whenever M ∈ K; this subset is a filter, if K is nonempty; otherwise it contains every sentence. In general, a theory of L is Fm^{0}(L) or a filter of it; a consistent theory is a proper filter; a complete theory is an ultrafilter. A model of a set Σ of sentences is a structure M such that Σ ⊆ Th(M). We write

Σ ⊧ σ

if every model of Σ is a model of σ (that is, of {σ}). We write

Σ ⊢ σ

if σ is in the theory generated by Σ. If Σ ⊢ σ, then Σ ⊧ σ.

12 Compactness

It is a consequence of the following that Σ ⊢ σ if Σ ⊧ σ.

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

Proof. Let T be a consistent theory in the signature L. We shall extend L to a signature L′, and extend T to a complete theory T′ of L′. We shall do this in such a way that, for every unary formula ϕ of L′, there will be a constant-symbol c_{ϕ} not appearing in ϕ such that

T′ ⊢ ∃x_{0} ϕ → ϕ(c_{ϕ}).

Then T′ and the constant-symbols c_{ϕ} will determine a structure M in the following way. The universe of M will consist of equivalence-classes [c_{ϕ}] of the symbols c_{ϕ}, where

[c_{ϕ}] = [c_{ψ}] ⟺ T′ ⊢ c_{ϕ} = c_{ψ}.

Then we require

ϕ^{M} = {[c] : T′ ⊢ ϕ(c)}  (∗)

for all basic formulas ϕ of L′ and all tuples c of symbols c_{ϕ}. The requirements (∗) do make sense. In particular, c_{ϕ}^{M} = [c_{ϕ}]. The requirements determine a well-defined structure, since T′ is complete.

If T′ is as claimed, then (∗) holds for all formulas ϕ; we show this by induction. If ϕ is an n-ary formula, and [c] is an (n − 1)-tuple from M, let d be the constant-symbol determined by the unary formula ϕ(c, x_{0}). If (∗) holds for ϕ, then we have:

[c] ∈ (∃x_{n} ϕ)^{M} ⟹ M ⊧ ϕ(c, [e]), some [e] in M
⟹ T′ ⊢ ϕ(c, e)
⟹ T′ ⊢ ∃x_{0} ϕ(c, x_{0})
⟹ T′ ⊢ ϕ(c, d)
⟹ M ⊧ (c, [d])
⟹ [c] ∈ (∃x_{n} ϕ)^{M};

so (∗) holds with ∃x_{n} ϕ in place of ϕ.

Once (∗) holds for all formulas ϕ, then in particular it holds when ϕ is a sentence in T; so M ⊧ T.

It remains to find T′ as desired. First we construct a chain L = L_{0} ⊆ L_{1} ⊆ … of signatures, where L_{n+1} − L_{n} consists of a constant-symbol c_{ϕ} for each unary formula ϕ in L_{n}. Taking the union of the chain gives L′.

Now we work in the Stone space of Fm^{0}(L′). We claim that the collection

{[σ] : σ ∈ T } ∪ {[∀x_{0} ¬ϕ ∨ ϕ(c_{ϕ})] : ϕ ∈ Fm^{1}(L′)}

of closed sets has the finite-intersection property; from this, by compactness, we can take T′ to be an element of the intersection.

To establish the f.i.p., suppose that [ψ] is a nonempty finite intersection of sets in the collection. Then ψ ∈ Fm^{0}(L_{n}) for some n. If ϕ ∈ Fm^{1}(L′) − Fm^{1}(L_{n−1}), then c_{ϕ} does not appear in ψ. If also [ψ] ∩ [∀x_{0} ¬ϕ] is empty, then

[ψ] ∩ [ϕ(c_{ϕ})]

is nonempty; for, if M ⊧ ψ ∧ ∃x_{0} ϕ, then we may assume M ⊧ ψ ∧ ϕ(c_{ϕ}).

Theorem. Suppose N ∈ 𝔐𝔬𝔡(L), and κ is a cardinal such that

ℵ_{0} + |L| ⩽ κ ⩽ |N|.

Then there is M in 𝔐𝔬𝔡(L) such that M ≼ N and |M| = κ.

Proof. Use the proof of Compactness, with Th(N) for T. We can choose T′, and we can choose c_{ϕ}^{N} in N, so that N ⊧ T′. Then we may assume M ⊆ N, and so M ≼ N by the Tarski–Vaught test. By construction, |M| ⩽ |L′| = ℵ_{0} + |L|.

To ensure M = κ, we first add κ-many new constant-symbols to L and let their interpretations in N be distinct.

Example. In the signature {∈} of set-theory, any infinite structure has a countably infinite elementary substructure, even though the power-set of an infinite set is uncountable.

Corollary. Suppose A is an infinite L-structure and |A| + |L| ⩽ κ. Then there is M in 𝔐𝔬𝔡(L) such that A ≼ M and |M| = κ.

Proof. Let {c_{μ} : μ < κ} be a set of new constant-symbols, and let T be the theory generated by Th(A_{A}) and {c_{μ} ≠ c_{ν} : μ ≠ ν}. Use Compactness to get a model N of T; then use the last Theorem to get M as desired.

References

[1] C. C. Chang and H. J. Keisler. Model theory. North-Holland Publishing Co., Amsterdam, third edition, 1990.

[2] Wilfrid Hodges. Model Theory. Cambridge University Press, 1993.

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