Basic Model Theory

John L. Bell

1. Structures and First-Order Languages

A structure is a triple A = (A, {Ri: i I}, {ej: j J}), where A, the domain or universe of A, is a nonempty set, {Ri: i I} is an indexed family of relations on A and {ej: j J}) is an indexed set of elements the designated elements of A. For each i I there is then a natural number (i) the degree of Ri such that Ri is a (i)-place relation on A, i.e., Ri A(i). This may be regarded as a function from I to the set of natural numbers; the pair (, J) is called the type of A. Structures of the same type are said to be similar. Note that since an n-place operation f: An A can be regarded as an (n+1)-place relation on A, algebraic structures containing operations such as groups, rings, vector spaces, etc. may be construed as structures in the above sense. The cardinality A of a structure A is defined to be the cardinality |A| of its domain A. The first-order language L of type (, J) has the following categories of basic symbols: (i) individual variables: a denumerable sequence v0, v1,...; (ii) predicate symbols: for each i I, a predicate symbol Pi of degree (i); (iii) individual constants: for each j J an individual constant cj; (iv) equality symbol: the symbol =; (v) logical operators: (negation), (conjunction); (vi) existential quantifier symbol: ("there exists"); (vii) punctuation symbols: e.g. ( ) , [ ]. Predicate and constant symbols are often called extralogical symbols; variables and constants are collectively known as terms: we shall use symbols t, u, possibly with subscripts, to denote arbitrary terms. Atomic formulas of L are finite strings of basic symbols of either of the forms Pit1...t(i) or t = u, where t1 ,..., t(i), t, u are terms. Formulas of L (or L -formulas) are finite strings of basic symbols defined in the following recursive manner: (a) any atomic formula is a formula; (b) if , are formulas, so also are , , and x, where x is any variable vn; (c) a finite string of symbols is a formula exactly when it follows from finitely many applications of (a) and (b) that it is one. We write Form(L ) for the set of all formulas of L. The degree (of complexity) of a formula is

defined to be the number of occurrences of logical operators and quantifiers in it. The symbols (disjunction), (implication) and (universal quantifier) are introduced as abbreviations: for ( ) for for ( ) ( ) x for x. We also write i for 1 n.
i =1 n

It will be assumed that the notions of free and bound occurrence of a variable in a formula are understood. We write (v0, ...,vn) to indicate that the free variables of are among v0,...,vn. We also write (x/t), or simply (t), for the result of substituting t at each free occurrence of x in . More generally, we write (t0, ..., tn) for the result of substituting ti at each occurrence of vi , for i = 0, ..., n, in (v0,...,vn). An L - sentence is an L - formula without free variables. We write Sent(L ) for the set of all L-sentences. The cardinality L of L is defined to be the cardinality of its set of basic symbols. Lemma. L = |Form(L )|. Proof. Let L = . Since is infinite and each formula is a finite string of symbols, |Form(L ) . The fact that is infinite also implies that either the set of terms or the set of predicate symbols of L (or both) must have cardinality . In either case the set of atomic formulas of the form Pit...t has cardinality , so that |Form(L )| . The Lemma follows. For Sent(L) we define L to be the language whose extralogical symbols are precisely those occurring in at least one sentence of . Lemma. L = max(0, ||). Proof. If is finite, evidently L = 0. Now suppose that|| = 0. We have || Form(L )| = L by the previous lemma. For each let S() be the set of (L -) symbols occurring in : then S() is finite. Also the set K of terms of L is included in the union of the sets S () for , so that |K| |{S(): }| |S ()| ||.0 = ||.

Thus L |K| + 0 + 0 ||, and hence L = || as required.

2. Satisfaction, validity, and models.

If L is a first-order language, a structure having the same type as that of L is called an L -

structure. Let A = (A, {Ri: i I}, {ej: j J}) be an L-structure, where L has type (, J), and let a = (a0,a1,...) be a countable sequence of elements of A (such a sequence will be referred to henceforth as an A-sequence). For any predicate symbol or term of L, we define its interpretation under (A,a) as follows: Pi(A,a) = Ri cj(A,a) = ej vn(A,a) = an. (A,a) (A,a) Since Pi and cj depend only on A, we usually just write PiA and cjA for these and call them the interpretations of Pi and cj, respectively, in A. For n , b A we define [n|b]a = (a0, a1 ,..., an1, b, an+1,...). For Form(L ) we define the relation a satisfies in A, written A a , recursively on the degree of as follows: 1) for terms t, u, A a t = u t(A,a) = u(A,a); 2) for terms t1 ,..., t(i), A a Pit1...t(i) Ri(t1(A,a), ..., t (i)(A,a)); 3) A a not A a ; 4) A a A a and A a, 5) A a vn for some b A, A [n|b]a . The following facts are then easily established: (a) A a vn for all b A, A [n|b]a ; Then (b) suppose that a, b are A-sequences such that an = bn whenever vn occurs free in . A a A b , In view of fact (b), the truth of A a depends only on the interpretations under (A,a) of the free variables of , that is, if these are among v0, ...,vn, only on a0, ..., an. Accordingly, under these conditions we shall often write A a[a0, ..., an] for A a . We say that a formula is valid in A if A a for every A-sequence a and satisfiable in A if A a for some A-sequence a. It follows from (b) above that a sentence is satisfiable in a given structure iff it is valid there. If is valid in A we write A a and say that A is a model of , or that holds in A. If Sent (L ), we say that A is a model of , and write A , if A is a model of each member of . If Form(L ), we say that logically entails , and write

, if is valid in every model of . In particular, we write for ; a formula satisfying this condition is then valid in every (L -) structure and is called universally valid. Let L * be a language which is an extension of L, i.e. obtained from L by adding a set {Pi: i I*} of new predicate symbols and a set {cj: j J*} of new constant symbols. Given an L*-structure A* = (A, {Ri: i I I*}, {ej: j J J*}), the L -structure A = (A, {Ri: i I}, {ej: j J}) is called the L -reduction of A*. Analogously, A* is called an L *-expansion of A. Notice that, while an L *-structure always has a unique L-reduction, an L-structure has in general more than one L *-expansion. We write A*|L for the L-reduction of A*. It is important to keep in mind the fact that expanding or reducing has no effect on the domain of a structure; these operations merely add or subtract relations and designated elements. The following lemmas are routine. The first is proved by a straightforward induction on the degree of complexity of formulas, the second follows from the definition of . Expansion lemma. Let Sent(L ), let L* be any extension of L, let A be any L structure, and let A* be any L*-expansion of A. Then A A* . Constants lemma. Let A be an L -structure, let (v0, ...,vn) Form(L ), and let cn be constant symbols of L. Then A (c0, ..., cn) A [c0A, ..., cnA]. c0, ...,

3. Review of first-order predicate logic.

Let L be a first-order language of type (, J). We specify axioms and rules of inference for L as follows. As axioms we take 1) all instances of propositional tautologies; 2) equality axioms: t=t t=uu=t t=u u=vt=v (t1 = u1 t(i) = u(i)) [Pit1 t(i) Piu1...u(i) ] 3) all formulas of the form x (x ) (t ) (t ) x (x ) where, if t is a variable, it does not occur bound in . The rules of inference of L are:

1) modus ponens: 2) quantifier rules: if x is not free in , (x) x(x) (x) x(x)

A proof in L of from a set Sent(L ) is a finite sequence 1, ..., n of L-formulas, with n = , each member of which is either an axiom, a member of , or else follows from previous i by one of the rules of inference. We say that is provable from , and write , if there is a proof of from . is said to be consistent (in L ) if for no L -formula do we have . If , we write and say that is a theorem of L. We now list a number of basic results concerning these notions. Throughout, denotes an arbitrary set of L -sentences. Quantifier lemma. If x does not occur free in , then x( ) ( x) x( ) ( x). Deduction theorem. If Sent(L ), then for any formula , {} . Finiteness theorem. If , then 0 for some finite subset 0 of . Soundness theorem. If , then . Consistency lemma. (i) is consistent iff not for some L-formula . (ii) is consistent iff every finite subset of is so. (iii) If Sent(L), {} is consistent iff . Generalization lemma. If (v0, ...,vn) Form(L ), then v0vn.

4. The completeness and model existence theorems and some of their consequences.
Let L be a first-order language of type (, J). We make the following definitions. 1. An extension L * of L is called a simple extension of L if it is obtained by adding just new constant symbols.

2. Let Sent(L ) and let L * be a simple extension of L. A set * Sent(L *) is called an L-saturated extension of in L * if * and, for any L -formula with at most one free variable x, there is a constant symbol c of L * such that * x(x) (c). 3. A set Sent(L ) is saturated if for any L -formula with at most one free variable x, there is a constant c of L for which x(x) (c). If is saturated, then clearly: x(x) (c) for some constant c of L. Notice also that if some set of L -sentences is saturated, then L contains at least one constant symbol. Lemma 1. Suppose that Sent(L ) is consistent. Then there is a consistent L -saturated extension * in a simple extension L * of L for which L * = L . Proof. Let F be the set of L-formulas with at most one free variable (which we shall denote by x). For each F introduce a new constant symbol c in such a way that, if and are distinct formulas, then c and c are distinct constants. In this way we obtain a simple extension L * of L: clearly L * = L . Now define * = {x(x) (c): F}. Clearly * is an L -saturated extension of in L*. It remains to show that * is consistent. Suppose, on the contrary, that * is inconsistent. Then by the consistency lemma there is a finite subset {1,..., n}of F such that, writing ci for ci , {xi i(ci): i = 1,.., n} is inconsistent. It follows from the consistency lemma that (*) [xi i (ci )]
i =1 n

Now choose n distinct variables x1,...,xn which do not occur in the proof from of the sentence on the right hand side of the turnstile in (*). If in this proof we change ci at each of its occurrences to xi for i = 1,...,n, we obtain a proof of the formula [xi i ( xi )] from ,
i =1 n

whence [xi i ( xi )] .
i =1 n

By the generalization lemma, v1vn [xi i ( xi )]

i =1 n

so that (**) v1vn [xi i ( xi )] .

i =1 n

Now the xi have been chosen in such a way that, if i j, then xi does not occur in j(xi). So it follows from the quantifier lemma that the existential quantifiers on the right hand side of the turnstile in (**) may be moved across the conjunctions and implications to yield

[xi xi i ( xi )] .
i =1

But since, clearly, xi xi i ( xi ) for each i, it follows that is inconsistent, contradicting assumption. Accordingly * is consistent and the lemma is proved. A set Sent(L ) is said to be complete if, for any Sent(L ), we have or .
Lemma 2. Suppose that Sent(L ) is consistent. Then there is a complete consistent set Sent(L ) such that . Proof. The family of consistent sets of sentences of L containing , ordered by inclusion, is easily seen to be closed under unions of chains, and so by Zorn's lemma has a maximal member . If Sent(L ) and , then {} is consistent by the consistency lemma.

Since is maximal consistent, we must have {} = , so a fortiori . Thus is complete and meets the requirements of the lemma.
Theorem 1. Suppose that Sent(L ) is consistent. Then there is a simple extension L + of L such that L + = L and a complete saturated consistent set + Sent(L +) such that

+.
Proof. We construct a sequence L0, L1,... of simple extensions of L and a sequence 0, 1,... of consistent sets of sentences as follows. We begin by putting L0 = L and 0 = . Suppose now that the consistent set n Sent(Ln) has been defined. By Lemma 1 there is a simple extension Ln* such that L n* = Ln and a consistent Ln-saturated extension n* of n in Ln*

And by Lemma 2, there is a complete consistent extension n* of n in Ln*: clearly n* is Lnsaturated also. We set Ln+1 = Ln*, n+1 = n* . Then n+1 is a complete, consistent Ln-saturated extension of n in Ln+1. Now we define L + to be the union of all the languages Ln and + to be the union of all the sets n. Since L n = L 0 = L for all n, it follows that L + = L . Also, + Sent(L +), + and +, as the union of the chain 0 1 ... of consistent sets, is itself consistent. For if + is inconsistent, let be the finite set of formulas of L+ in a proof P of a formula of the form from +. Then Form(Lm) for some m, and + n for some n. Writing q for the larger of m, n, P is then a proof of from q in Lq, contradicting the consistency of q. Moreover, + is complete. for, if Sent(L +), then Sent(L n), for some n, and so, since n is complete, either n or n Since n +, it follows that + or + , proving the claim. Finally, + is saturated. For let (x) be a formula of L + with one free variable x. Then (x) Form(L n) for some n. Since n+1 is an Ln-saturated extension of n in Ln+1, there is a

constant symbol c of L n+1 for which the sentence x(x) (c) is provable from n+1, and hence also, since n+1 +, from +. Therefore the latter is saturated as claimed. Now let be a fixed consistent set of sentences of L. Let C be the set of constant symbols of L: we shall assume that this set is nonempty. We define the relation on C by c d c = d. It is easy to verify, using the equality axioms in L , that is an equivalence relation. For each c C write c for the equivalence class of c with respect to ; thus
c = {d C: c = d}.

Let
C = { c : c C} be the set of all such equivalence classes. Corresponding to each predicate symbol Pi of L define the (i)- ary relation Ri on C by Ri( c1 ,..., c (i ) ) Pic1...c(i).

We can now frame the

Definition. The canonical structure determined by is the L -structure A = ( C , {Ri: i I}, { c j : j J}).

Observe that A |C|. . (*)

Theorem 2. Suppose that is complete, consistent and saturated. Then A is a model of Proof. We show that, for any L-sentence , A .

That this holds for atomic sentences is an immediate consequence of the definition of A . We now argue by induction on the degree of complexity of the sentence . Suppose then that n > 0 and that (*) holds for all sentences of degree < n. Let have degree n; then is either a conjunction or a negation of sentences of degree < n, or an existentialization of a formula of degree < n. Verifying (*) in the first two cases is routine (using the completeness of in the negation case) and we omit the details. In the last case, is of the form x(x), where has degree < n. We then have A A x(x) A [ c ] for some c C (by constants lemma) (by (*)) (since is saturated) A (c) for some c C (c) for some c C x(x) . Therefore satisfies (*) and the proof is complete.

These results have the following important corollaries.

Model Existence Theorem (Gdel-Henkin). Any consistent set of first-order sentences has a model of cardinality at most max(0, ||). Proof. Let = max(0, ||); then = L by the lemma on p. 3. By Theorem 1 we can

extend to a complete consistent saturated set of sentences in a simple extension L of L such that L = L

= . By Theorem 2, the canonical structure A is a model of and

hence also of . The expansion theorem implies that the L -reduction A of A is a model of , and that any L-expansion A of A is likewise. Moreover, if C is the set of constant symbols of
L , then A

= A |C| L = . The proof is complete.

Completeness Theorem. If Sent(L ) and Sent(L ), then . Proof. If , then, by the consistency theorem, {} is consistent and so, by the

model existence theorem, has a model A. Since A is a model of but not of , it follows that .
Compactness Theorem. A set of first-order sentences has a model iff every finite subset of has a model. Proof. One way round is trivial. If, conversely, every finite subset of has a model, then every finite subset of is consistent and so itself is consistent by the consistency lemma. Therefore has a model by the model existence theorem. Invariance Theorem. Provability and consistency are invariant with respect to language. That is, if Sent(L ) and Sent(L ), and L * is an extension of L, then (a) in L in L *

(b) is consistent in L is consistent in L *. Proof. We prove (a); (b) is an immediate consequence. Clearly in L in
L *.Conversely, if in L *, then by the completeness theorem, that is, every L *-structure which is a model of is also a model of . If A is any L -structure which is a model of , it can be expanded to an L *-structure A* which, by the expansion lemma, is also a model of L. Then A* is a model of , and so, applying the expansion lemma again, A, as the Lreduction of A*, is a model of . Therefore, by the completeness theorem, in L. Lwenheim-Skolem Theorem. If a set of first-order sentences has an infinite model, it has a model of any cardinality max(0, ||). Proof. For simplicity write L for L. Let L * be the simple extension of L obtained by adding a set {dj: j J} of new constant symbols, where |J| = . Let

10

* = {(dj = dk): j, k J & j k}. If 0 is any finite subset of *, only finitely many sentences of the form (dj = dk) occur in 0; let dj1, ..., djn be a list of all constant symbols occurring in such sentences in 0. If now A is an infinite model of (which we may take to be an L-structure), choose n distinct elements a1,,..., an of its domain A. Let A* be the L*-expansion of A in which the interpretation of djp is ap for p = 1,..., n and that of dj is an arbitrary element of A for j {j1, ..., jn}. Clearly A* is then a model of 0. It follows that every finite subset of * has a model. Thus every finite subset of * is consistent and so * is itself consistent. Clearly |*| = , so the model existence theorem implies that * has a model of cardinality . Since the interpretations of the dj in any model of * must be distinct, any such model must have cardinality . So * has a model of cardinality ; its L -reduction is a model of of cardinality .
Overspill Theorem. If a set of first-order sentences has arbitrarily large finite models, it has an infinite model. Proof. For each n let n be a sentence (formulable in any first-order language with equality) asserting that there at least n individuals. Given a set of first-order sentences, let * = {n: n }. If has arbitrarily large finite models, then each finite subset of * has a model, so by the compactness theorem * has a model, which must evidently be an infinite model of .

5. Relations between structures.

Let A = (A, {Ri: i I}, {ej: j J}) and B = (B, {Si: i I}, {dj: j J}) be structures of the same type (,J). We say that A is a substructure of B, written A B, if A B, ej = dj for all j J, and Ri = Si A(i) for all i I. If C is a nonempty subset of B containing all the designated elements of B, we define the substructure B|C of B by B|C = (C, {Si C(i): i I}, {dj: j J}). An embedding of a structure A into a structure B is an injective map f: A B such that f(ej) = dj for all j J, and for all i I and a1, ..., a(i) A, we have Ri(a1, ..., a(i)) Si(fa1 , ..., fa(i)). If there exists an embedding of A into B, we say that A is embeddable into B and write A B. If f is an embedding of A into B, we write f[A] for the structure B|f[A]. A surjective embedding is called an isomorphism. If there exists an isomorphism between A and B, they are said to be isomorphic and we write A B. Let L be the first-order language of type (,J). We say that the L-structures A and B are elementarily equivalent, and write A B, if A B for any L sentence . It is easily shown that isomorphic structures are elementarily equivalent, but the Lwenheim-Skolem theorem implies that the converse fails. The L -structure A is said to be an elementary substructure of the L -structure B, and B an elementary extension of A, if A B and, for any L formula (v0,...,vn) and any a0,..., an A,

11

we have
A [a0, ..., an] B [a0, ..., an].

In this situation we write A B. Evidently A B A B, but the converse is easily seen to be false. An embedding f of A into B is called an elementary embedding if for any L -formula (v0, ...,vn) and any a0, ..., an A we have A [a0, ..., an] B [fa0, ... ,fan]. In this situation we write f: A B. If such an f exists, we write A B. Clearly A B
A B. It is also easily shown that any isomorphism is an elementary embedding. Tarski-Vaught Lemma. If A and B are L -structures, then A B iff A B and, for any L-formula (v0, ...,vn) and any a0, ..., an1 A,

(*)

if B vn [a0, ..., an1], then, for some a A, A [a0, ..., an1, a].

Proof. One direction is trivial. Conversely, suppose that (*) holds. We prove by induction on the degree of that, for any n, any L formula (v0, ...,vn) and any a0, ..., an A, A [a0, ..., an] B [a0, ..., an]. (**)

That (**) holds for atomic formulas is obvious, as are the induction steps for and . It remains to show that, if it holds for , it also holds for vk . Without loss of generality we may assume that n is greater than the index of every variable (free or bound) occurring in , and then, by making a suitable change of variable in (i.e., by substituting vn for vk), that k = n. If A vn[a0, ..., an1], then A [a0, ..., an-1, a] for some a A, and it follows from (**) for that
B [a0, ..., an-1, a], whence B vn[a0, ..., an1]. Conversely, if B vn[a0, ..., an1], then, by (*), B [a0, ..., an-1, a] for some a A, whence A [a0, ..., an-1, a] by (**), so that A vn[a0, ..., an1]. This completes the induction step and the proof. Corollary. Write Q and

for the sets of rational and real numbers. Then

(Q, ) ( , ). Proof. We show that the Tarski-Vaught lemma applies. Suppose that, for a formula (v0, ...,vn) of the appropriate language, and a0 < ... < an-1 Q, we have ( , ) vn[a0, ..., an-1]. Then there is b such that ( , ) [a0, ..., an-1, b]. Say ai < b < ai+1 (the cases b < or > all ai being similar). Choose a to be any rational such that ai < a < ai+1. It is easy to construct an isomorphism f: such that f(aj) = aj for 0 j n 1 and f(b) = a. This f is also an elementary embedding. Hence ( , ) [fa0, ...,fan-1, b], i.e. ( , ) [a0, ..., an-1, a]. Since a Q, the Tarski-Vaught lemma applies to yield the required conclusion.

12

Given a set X, let LX be the simple extension of L obtained by adding a set {cx: x X} of distinct new constant symbols indexed by X. If A is an L -structure and X is a subset of its domain A, we write (A, X) for the LX -expansion of A in which the interpretation of each cx is x. If f is a mapping of X into the domain B of an L -structure B, we write (B, f[X]) for the LXexpansion of B in which the interpretation of each cx is f(x). The diagram of A, (A), is the set of atomic and negated atomic sentences that hold in (A, A). The complete diagram of A, (A), is the set of all sentences of LA that hold in (A, A). The proof of the following lemma is then straightforward.
Diagram lemma. Let A and B be L -structures. Then:

(i) A B iff B can be expanded to a model of (A); (ii) A B iff B can be expanded to a model of (A); (iii) if A B, then A B iff (B, A) (A); (iv) an embedding f of A into B is an elementary embedding iff (A, A) (B, f[A]). We now show that infinite structures have elementary substructures and extensions of most cardinalities.
Theorem. Let A be an infinite L -structure. (i) If X A, then for any cardinal satisfying max(|X|, L ) |A|, there is an

elementary substructure B of A such that |B| = and X B. (ii) A has an elementary extension of any cardinality max(|X|, L ). Proof. (i) Let < be some fixed well-ordering of A. We define a sequence B0, B1,... of subsets of A recursively as follows. Choose B0 to be any subset of A such that |B0| = and X B0. If Bn has been defined, put Bn+1 = {b: for some L -formula (v0, ..., vm) and some b0, ..., bm-1 Bn, b is the <-least element of A such that A [b0,...,bm-1, b]}. It is easy to check that Bn Bn+1 and that |Bn+1| = . Now define B to be the union of the Bn and B = A|B. Then B is a substructure of A of cardinality and it is easy to apply the TarskiVaught lemma to conclude that B A.
(ii) Let be the complete diagram of A. Then || = max(|X|, L ). Since is evidently

consistent, the model existence theorem implies that it has a model of any cardinality || = max(|A|, L ). The result now follows from the diagram lemma.

13

6. Ultraproducts
A filter over a set I is a family F of subsets of I such that (i) X, Y F X Y F, (ii) F. It follows immediately from (i) that any filter F over I satisfies; X F and X Y F Y F. An ultrafilter over I is a filter U over I satisfying the condition: for any X U, either X U or I X U . In particular, for any i I, Ui = {X I : i X} is an ultrafilter over I called the principal ultrafilter generated by i. It is easily shown that an ultrafilter is precisely a filter that is maximal in the sense that it is included in no filter apart from itself. A straightforward application of Zorns Lemma shows that a family A of subsets of I is included in an ultrafilter over I if and only if it has the finite intersection property: that is, for any finite subfamily B of A we have B . For ease of exposition we confine our attention throughout this section to structures consisting of a nonempty set and a single binary relation on that set. The appropriate language L for such structures thus has a single predicate symbol of degree 2, say P0. The type of these structures,a nd of L, is then ((0, 2), ). It should be clear that everything we do can be extended to arbitrary structures merely by complicating the notation. Now let I be some arbitrary fixed index set, and for each i I let Ai = (Ai, Ri) be an L structure. Let Ai be the Cartesian product of the sets Ai: we use letters f, g, h, f, g, h to denote elements of Ai . Given a family F of subsets of I, we define the relation F on Ai by f F g {i I : f(i) = g(i)} F. It is easily shown that, if F is a filter over I, then F is an equivalence relation on Ai . From here on we shall suppose that F is a filter over I. For each f Ai we write f /F for the F -equivalence class of f , and we define Ai /F = {f /F : f Ai}. We define the relation R on Ai by: (f, g) R {i I : (f(i), g(i)) Ri} F. It is not difficult to show that R is compatible with F in the sense that, if f F f and gF g, then fRg fRg. That being the case, the relation R on Ai induces the relation RF on Ai /F given by (f /F, g/F) RF fRg. The L -structure Ai /F = (Ai /F , RF) is called the reduced product of the family {Ai: i I} over the filter F: if F is an ultrafilter, the reduced product over F is called an ultraproduct. If, for each i I, Ai is a fixed structure A, the reduced product is denoted by AI /F and is called the reduced power of A over F. When F is an ultrafilter the reduced power is called an ultrapower. Observe that if F is the filter {I}, the reduced power Ai /F is isomorphic to (Ai, R), and that, for k I, the ultraproduct Ai /Uk is isomorphic to Ak. If f = (f0, f1,) is a sequence of elements of Ai, that is, if f (Ai), we write f(i) for the sequence (f0(i), f1(i),) Ai and, if U is an ultrafilter over I, f /U for the sequence

14

(f0/U, f1/U,) (Ai/U). We now prove the fundamental theorem on ultraproducts, viz.,
os Theorem. If U is an ultrafilter over I, a formula of L and f a sequence of elements of Ai, then (*) Ai /U f/U {i I: Ai f(i) } U. Proof. The proof goes by induction on the complexity of . That (*) holds for atomic is a straightforward consequence of the definitions of F and RF. The induction steps for and follow easily from the defining properties of ultrafilters. Now suppose that (*) holds for (and arbitrary f); we show that it holds for vn. Define D = {i I: Ai f(i) vn}. We have to show that Ai /U f/U vn D U.

Suppose that Ai /U f/U vn. Then there is some b Ai for which Ai /U [n|b]f/U . Let E = {i I: Ai ([n|b]f)(i) }. Then by the induction hypothesis E F. And since ([n|b]f)(i) = [n|b(i)]f(i), it follows that E D, and so because U is a filter, D U. Conversely suppose that D U. If i D, then there is some bi Ai such that A i [ n / bi ] f (i ) . By the axiom of choice there is c Ai for which c(i) = bi for every i D, and is an arbitrary element of Ai otherwise. Defining C = {i I: A i ([ n|c ] f )(i ) }, we have D C so that C U. It now follows from the induction hypothesis that Ai /U ([n|c]f)/U , i.e., since ([n|c]f)/U = [n|c/U] f/U , Ai /U [n|c/U] f/U . Therefore Ai /U f/U vn, completing the proof of the theorem. As an immediate consequence we have the
Corollary. For any L sentence we have Ai /U {i I: Ai } U.

Let A be a structure and let U be an ultrafilter on the set I. For each a A let a AI be the function given by a (i ) = a for all i I. The canonical embedding of A into AI /U is the map d: A AI/U defined by d(a) = a /U . It is a straightforward consequence of os theorem that d is an elementary embedding. os theorem may also be used to provide a simple direct proof of the compactness

15

theorem, avoiding the use of the completeness theorem. To wit, suppose that each finite subset of a given set of sentences has a model A; for simplicity write I for the family of all finite subsets of . For each I let = { I: }. For any members 1, , n of I, we have 1 ... n 1 ... n , and so the collection { : I} has the finite intersection property. It can therefore be extended to an ultrafilter U over I. The ultraproduct A /U is then a model of . For if
I

, then {} , and A{} ; moreover, A whenever . Hence

{} = { I : } { I : A } .

Since {} U, { I : A } U and therefore, by os theorem,

A
I

/U . The proof

is complete.

7. Completeness and categoricity

For simplicity, throughout this section we let L be a countable first-order language. By a theory in L we shall mean a set of L -sentences which is closed under provability, i.e such that, for each L sentence , if , then . A subset of a theory is called a set of
postulates for if for every . Clearly each set of L -sentences is a set of postulates

for a unique theory , namely = { Sent(L ): }. For each L -structure A let (A), the
theory of A, be the set of all L -sentences holding in A. Clearly (A) is a complete theory. The following lemma is a straightforward consequence of the completeness theorem.
Lemma. The following conditions on a consistent theory in L are equivalent: (i) is complete; (ii) any pair of models of are elementarily equivalent; (iii) = (A) for some L -structure A.

Let be an infinite cardinal. A theory is said to be -categorical if any pair of models of of cardinality are isomorphic. Examples. (i) Let L have no extralogical symbols and let be the set of all L -sentences which hold in every L -structure. Then is -categorical for every infinite . (ii) Let L have just one unary predicate symbol P and let be the set of L -sentences which hold in every L -structure. Then is not -categorical for any infinite . (iii) Let L be as in (ii) and for each matural number m let m be the first-order sentence which asserts that there are at least m individuals having the property P and at least m individuals not having P. Let be the theory with the set of all m as postulates. Then is 0-categorical

16

but not -categorical for any > 0. (iv) Let L be the language whose sole extralogical symbols are countably many constants c0, c1,... and let be the theory with postulates {(cm = cn): m n}. Then is -categorical for every > 0 but not 0 -categorical.

One of the deepest results in model theory is Morley's theorem (whose proof is too difficult to be included here) which asserts that the four possibilities above are exhaustive, that is, if a theory in a countable language is -categorical for some > 0, it is -categorical for all > 0. The next result provides a simple, but useful, sufficient condition for completeness.
Theorem. (Vaught's test.) Let be a consistent theory with no finite models and which is -categorical for some infinite . Then is complete. Proof. If is not complete, then there is a sentence such that neither nor are provable from . So both {} and {} are consistent and hence have models, which must be infinite since was assumed to have no finite models. Therefore, by LwenheimSkolem, both {} and {} have models of cardinality . Since holds in one of these models but not in the other, is not -categorical.

This theorem may be applied to establish the completeness of various theories.

UDO the theory of unbounded dense linear orderings is formulated in a language with just one binary predicate symbol R and has the following postulates (where we write x y for (x = y)): (i) xRxx xy[Rxy Ryx x = y] xyz[Rxy Ryz Rxz] xy[Rxy Ryx] (ii) xy[Rxy x y x[x z y z Rxz Rzy]] (iii) xyz[x y x z Ryx Rxz] Postulate (i) asserts that R is a linear ordering, (ii) that it is dense, and (iii) that it is unbounded below and above. Natural examples of models of UDO are (Q, ) and ( , ). Theorem. UDO is 0-categorical and so, by Vaught's test, complete. Proof. Let (A, ) and (B, ) be denumerable models of UDO. Thus each is an

unbounded dense linearly ordered set. Let A = {an: n } and B = {bn: n }. We define two new sequences {an*: n } and {bn*: n } as follows. First, put a0* = a0 and b0* = b0. Now suppose k > 0; we consider two cases. (i) k = 2m is even. In this case we put ak* = am. If, for some j < k, ak* = aj*, we put bk* = bj*. Otherwise we let bk* be some element of B bearing the same order relations to b0*, ...,bk-1* as does ak* to a0*, ..., ak-1*; that is, for each j < k, if ak* > or < aj*, then bk* > or < bj*. Since (B, ) is a dense unbounded linearly ordered set, it is clear that such an element can always be found. (ii) k = 2m + 1 is odd. In this case we put bk* = bm. If bk* = bj for some j < k, put ak* = aj*. Otherwise we choose ak* to be some element of A bearing the same order relations to a0*, ..., ak-1* as does bk* to b0*, ..., bk-1*. Again such an element can always be found.

17

This completes our recursive definition. We now define h: A B by putting h(an*) = bn* for each n . Clearly h is an isomorphism between (A, ) and (B, ). The theory we consider next is most naturally formulated in a language with operation symbols: all our previous results extend naturally to theories in such languages. The language F for fields is a first-order language with constant symbols 0, 1 and binary operation symbols +, . The theory FT of fields has the following postulates (where we write xy for x y): xy[(x + y) + z = x + (y + z)] x [x + 0 = x] xy[x + y = y + x] xy[x + y = 0] xyz[(xy)z = x(yz)] x[1x = x] xy[xy = yx] xyx[(y + z) = xy + xz] (0 = 1). For p , write p1 for 1 + 1 + ... + 1 with p summands. If to the postulates of FT we add the infinite set of sentences {(p1 = 0): p }, we get the theory FT0 of fields of characteristic 0. (Natural examples are the fields of rationals and reals.) We now write xn for the expression x ( x (... ( x x)...) with n factors. The infinite list of sentences, for n 1, x0...xn[(xn = 0) y(xnyn + xn-1yn-1 + ... + x1y + x0 = 0)] when added to the postulates of FT0, yields the theory ACF0 of algebraically closed fields of characteristic 0. Each new postulate asserts that all polynomials of a given degree n has a zero. We observe that ACF0 is not 0-categorical. For the field F of algebraic numbers and the algebraic closure of the field F[] obtained by adjoining the transcendental to F are countable nonisomorphic models of ACF0. On the other hand, a classical theorem of Steinitz asserts that ACF0 is -categorical for any uncountable , so we conclude from Vaught's test that ACF0 is complete Since the field of complex numbers is a model of ACF0, it follows that ACF0 is a set of postulates for the theory of .

8. The elementary chain theorem and some of its consequences.

Let A0 A1 ... be a chain of L -structures: in particular the Ai all have the same designated elements. The union of the chain is the structure A = A n defined as follows. The
n

18

domain of A is the set A = An . For i I, the ith relation Ri of A is the union of the
n

corresponding ith relations of the An. The designated elements of A are the designated elements of the An. Clearly each An is a substructure of A. A chain of structures A0 A1 ... in which each An is an elementary substructure of An+1 is called an elementary chain. In this case we write A0 A1 ... .
Elementary Chain Theorem. Each member of an elementary chain of structures is an elementary substructure of the union of the chain. Proof. Let A0 A1 ... be an elementary chain, and let A be its union. We prove the following assertion by induction on the degree of a formula: for any L formula (v0, ..., vn), any n and any a0, ..., am An, An [a0, ..., am] A [a0, ..., am]. (*)

The proof is routine for atomic formulas, and the induction steps for and are easy. Now suppose that is existential; without loss of generality we may assume that is vn, and that satisfies (*). If a0, ..., am-1 An and An [a0, ..., am1], then for some a An we have
An [a0, ..., am1, a]. So by (*) A [a0, ..., am-1, a] whence A [a0, ..., am1].

Conversely, suppose that A [a0, ..., am1]. Then A [a0, ..., am-1, a] for some

A. For some k, a Ak. Let l be the larger of k and n. Then a0, ..., am-1, a Al and so, by (*), Al

[a0, ..., am-1, a], whence Al [a0, ..., am1]. But n l and so, since An Al, we conclude that
An [a0, ..., am1].

We use this in the proof of the

Joint Consistency Theorem. Let and be theories in L, and let E be the language whose extralogical symbols are those common to L and L. Then the following are equivalent: (i) is consistent.; (ii) for no E sentence do we have and ;

(iii) for some complete (consistent) theory in E, both and are consistent; (iv) there is an E -structure which can be expanded both to a model of and to a model of
Proof. (i) (ii) is obvious. (ii) (iii). Assume (ii) and let * = { Sent(E): }. It follows easily from (ii)

that * is consistent and so has a model A. Let be the theory of the E -structure A|E. Since A , is consistent. If is inconsistent, there is such that , i.e. *. But then A , whence , a contradiction. Hence is consistent. (iii) (iv). Assume (iii), and let A0 and B0 be models of and , respectively. Then since A0|E and B0|E are both models of the complete theory , they are elementarily equivalent. It follows easily from this that the union of the complete diagram * of A0|E with

19

the complete diagram ** of B0 is consistent. (Observe that each finite subset of * is interpretable in B0.) Let B* be a model of and let B1 be its L -reduction. Then since B* is a model of both * and ** it follows from the diagram lemma that A0|E B1|E and B0 B1. Identifying B0 with its image in B1 makes the former an elementary substructure of the latter. Let f1 be an elementary embedding of A0|E into B1|E . Passing to the extended language EA0 , the diagram lemma implies that the structures (A0|E, A0) = (A0, A0)| EA0 and (B1|E, f1[A0]) = (B1, f1[A0]) are elementarily equivalent. Repeating the above construction in the other direction, this time with the L A0 -structures (A0, A0) and (B1, f1[A0]) in place of A0, B0, respectively, we obtain an elementary extension A1 of A0 and an elementary embedding g1 of (B1, f1[A0])| EA0 into (A1, A0)| EA0 Then g f1 is the identity on A0, so that f1 g1-1. Iterating this construction yields a diagram
A0 A1 A2 ... f1 g1 f2 g2 B0 B1 B2 ...

such that, for each m, fm is an elementary embedding of Am1|E into Bm|E , gm is an elementary embedding of Bm|E into Am|E , and fm gm-1 fm+1. Let A and B be the unions of the elementary chains A0 A1 ... and B0 B1 ... respectively. Then, by the elementary chain theorem, A is a model of and B is a model of . Moreover, f m is an isomorphism of A|E
m

and B|E (since, by construction, it has inverse

gm . It follows that B is isomorphic to a

structure B such that A|E = B|E . Accordingly the E -structure A|E can be expanded both to the model A of and to the model B of . (iv) (i). Let A be an E-structure expandable both to a model B of and to a model C of . Define the L -structure D as follows: the domain of D is that of A; if s is any extralogical symbol of L , then sA if s E sD= sB if s L L sC if s L Clearly D|L = B, so D . Also, D|L = C, so D . Therefore D is a model of , so the latter is consistent. From this we deduce
Craig's Interpolation Theorem. Suppose , are L -sentences and . Then there

is a sentence such that , , and every extralogical symbol occurring in occurs in both and .

20

Proof. Let E be the language whose extralogical symbols are exactly those occurring in both and . If , then {, } is inconsistent, so by (ii) of the joint consistency theorem

there is an E sentence such that and . The result now follows immediately. Suppose that Sent(L ) contains the n-ary predicate symbol P. P is said to be explicitly definable from if there is an L -formula (x1, ..., xn), in which P does not occur, such that x1...xn[Px1...xn ]. Now let P* be an n-ary predicate symbol not belonging to L , and let * be the set of sentences obtained from by replacing all occurrences of P by P*. Then P is said to be implicitly definable from if * x1...xn[Px1...xn P*x1...xn]. Semantically speaking, this means that any pair of L -structures which are both models of , have the same domain and agree on the interpretation of all extralogical symbols apart possibly from P, must also agree on the interpretation of P. Clearly, if P is explicitly definable from , it is implicitly definable from . Conversely, we have
Beth's Definability Theorem. If P is implicitly definable from , it is explicitly definable from . Proof. Suppose P is implicitly definable from . Without loss of generality we may assume to be finite, and we can then replace by the conjunction of all its sentences. So we may assume that consists of a single sentence . Let * be the result of replacing each occurrence of P in by P*. Then we have (1) {, *} x1...xn[Px1...xn P*x1...xn]. Now add new constant symbols c1,...,cn to L. Then, by (1), {, *} Pc1...cn P*c1...cn. So Pc1...cn (* P*c1...cn). By Craig's theorem, there is a sentence whose extralogical symbols are common to both Pc1...cn and * P*c1...cn, hence, in particular, not containing P or P* such that Pc1...cn and (* P*c1...cn). Therefore (2) Pc1...cn and (3) * P*c1...cn. If we replace P* by P in (3), * becomes and is unchanged. So (4) Pc1...cn. (2) and (4) now give Pc1...cn. (5)

But is (c1,...cn) for some L formula (x1, ..., xn) in which P does not occur. Since c1, ..., cn

21

are not in L , the result of replacing ci by xi (i = 1, ..., n) in the proof from of Pc1...cn yields a proof from of Px1...xn. Applying the generalization lemma gives x1xn[ Px1...xn] and so P is explicitly definable from .