Model-Theory to Compactness

David Pierce September 19, 2001

Contents

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

0 Introduction

These notes are an attempt to develop model theory, as economically as possible, on a foundation of some familiarity with algebraic structures. References include [1], [2] and [3].

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, 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 successor-function.)

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 function-symbol + 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).

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 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. Examples. A group-homomorphism is a homomorphism of groups; a groupmonomorphism is an embedding of groups. The zero-map on the ordered field R can be seen as a homomorphism, but not an embedding. (It would not even be a homomorphism if the signature of an ordered ring contained < instead of ⩽.)

5 Boolean algebras

An essential and notationally exceptional example is the Boolean algebra of subsets of a nonempty 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 (unital) ring in which every element is idempotent, that is, satisfies

x^{2} = x.

In particular, in such a ring we have (x + y)^{2} = x + y, whence

xy + yx = 0;

replacing y with x, we get 2x = 0, so every element is its additive inverse; hence also 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} or F_{2}, and this is a field. Therefore prime ideals of Boolean rings are maximal, since the quotient of a Boolean ring by an ideal is Boolean.

A structure (M, ∧, ∨, ¬, 0, 1)—call it M^{a}—in the signature of Boolean algebras determines a structure M^{r} with the same universe in the signature of rings: This structure M^{r}—that is, (M, +, ·, 0, 1)—is given by the rules

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

and the rule that 0 and 1 have the same interpretation in each structure. The structure M^{a} is a Boolean algebra just in case M^{r} is a Boolean ring. Any Boolean ring (M, +, ·, 0, 1) is determined in this way by the Boolean algebra (M, ∧, ∨, ¬, 0, 1) such that

x ∧ y = xy,
x ∨ y = x + y + xy,
¬x = 1 + x.

A Boolean algebra has a partial order ⩽ such that

x ⩽ y ⟺ x ∧ y = x.

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 Stonespace 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.

Since the collection of sets [x] contains the whole Stone-space and the empty set and is closed under finite unions, it is a basis for the closed sets of a topology for the Stone-space. By definition then, every closed subset is an intersection of some closed sets [x]. These basic closed sets are also open—they are clopen. The topology is Hausdorff, since distinct points 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, meaning any finite sub-collection has nonempty intersection;

• the set B generates a filter of the algebra;

• B included in an ultrafilter of this algebra;

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

That the first condition implies the last means that 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 product-topology 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.

6 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 in M, or t^{M}, of an n-ary term t of L will be an n-ary function on M. Terms can be defined precisely as follows:

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

• There is an n-ary term x_{i} whose interpretation 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 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.

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).

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.

7 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_{n−1}) we can write

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

where ∗ is ∧ 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—call it PL. 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 truth-assignment to the propositional variables x_{i}, and under such an assignment σ, a propositional formula t takes on the truthvalue

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}^{ω}.

8 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 0definable 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_{0} and t_{1} are n-ary terms, then there is an n-ary atomic formula t_{0} = t_{1} whose interpretation (t_{0} = t_{1})^{M} is {a ∈ M^{n} : t_{0}^{M}(a) = t_{1}^{M}(a)}.

• If t_{0}, …, t_{n−1} are m-ary terms, and R is n-ary, then there is an m-ary atomic formula R(t_{0}, …, t_{n−1}) whose interpretation R(t_{0}, …, t_{n−1})^{M} 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}.)

If t is an m-ary Boolean term, and ϕ_{0}, …, ϕ_{n−1} are n-ary atomic formulas, then there is an n-ary basic or quantifier-free formula, say t(ϕ_{0}, …, ϕ_{n−1}), whose interpretation is

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

If we identify formulas with indistinguishable interpretations in every structure, then the set of basic formulas is a Boolean algebra generated by the atomic formulas. The set of formulas is the smallest Boolean algebra containing the atomic formulas and closed under the operation converting 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 ϕ → ψ. 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 ϕ 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.

9 Substructures

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; if the same holds for all formulas ϕ of L, then h is an elementary embedding. If the universe of N includes the universe of M, and the inclusion-map is an embedding, we say M is a substructure of N and write

M ⊆ N;

if the inclusion-map 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).

10 Models and theories

Suppose ϕ is an n-ary formula of L, and a is an n-tuple of elements of M, so that ϕ(a) is a sentence of L(M). We write

M ⊧ ϕ(a)

if ϕ(a)^{M} = 1, equivalently, a ∈ ϕ^{M}. 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 Σ ⊧ σ.

11 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.