OXFORD LOGIC GUIDES
GENERAL EDITOR : DANA SCOTT

BEGINNING
MODEL THEORY
THE COMPLETENESS THEOREM
AND SOME CONSEQUENCES
BY
JANE BRIDGE
CLARENDON PRESS • OXFORD

Oxford University Press, Walton Street, Oxford ox2 6dp
OXFORD LONDON GLASGOW
NEW YORK TORONTO MELBOURNE WELLINGTON
KUALA LUMPUR SINGAPORE JAKARTA HONG KONG TOKYO
DELHI BOMBAY CALCUTTA MADRAS KARACHI
IBADAN NAIROBI DAR ES SALAAM CAPE TOWN
ISBN 0 19 853157 5
© Oxford University Press 1977
First published 1977
Reprinted 1978
All rights reserved. No part of this publication may be reproduced,
stored in a retrieval system, or transmitted, in any form or by any means,
electronic, mechanical, photocopying, recording or otherwise, without
the prior permission of Oxford University Press
Printed in Great Britain
by Morrison & Gibb Limited, Edinburgh

PREFACE
An essential feature of mathematical logic distinguishing it
from other branches of mathematics, is the explicit study of
the language in which mathematics may be described. This
book is intended as an introduction to that aspect of logic
which concerns the relationship between, on the one hand,
mathematical theories , described in a formal language, and
on thepther, mathematical structures realizing those
theories.
The text is based on a series of lectures given in
Oxford each year from 1970 to 1973. The course was intended
for second^year undergraduates reading Mathematics and
Philosophy who had already had an introductory logic course.
As a consequence, we assume here familiarity with some
elementary concepts and results. For instance, the reader
should ideally have studied the propositional (sentential)
calculus, including the notions of a propositional language,
a tautology, and a formal system of axioms and rules for
+
generating all tautologies as theorems. Acquaintance with
the formalization of statements involving quantifiers is
desirable though not strictly essential. Mathematical
examples are given for which some familiarity with elementary
abstract algebra is necessary. A summary of some set-
theoretic concepts used in the text is given in the
introduction.
At this point a brief summary outlining the contents of
the book may be helpful. In Chapter 1 we consider the
objects with which the mathematician is primarily concerned:
'Mendelson (1964), Chapter 1, or Lemmon (1965), Chapters
1 and 2, contain the relevant material. Scott*s book in
this series will cover the Oxford introductory course.

VI
mathematical structures. A formal (first-order) language is
developed in which some of the properties of a particular
structure or class of structures may be expressed. The
formalizable properties include many of the attributes of
mathematical interest, (Such attributes are normally
expressed in English, by English-speaking mathematicians,
together with some standard abbreviations.) The grammar of
the language is described and a definition given of what it
is for a statement of the language to be true or false in
a given structure.
Following the discussion of mathematical structures and
the (first order) languages in which their properties can be
formulated we turn, in Chapter 2, to the Syntactic* notions.
We define a formal system comprising axioms, rules of proof,
and derivations and develop some elementary theory of the
system.
Chapter 3 is the core of the book; the semantics of
Chapter 1 (which concern the * real1 mathematical world and
meaning in that world) are related to the syntactic (purely
formal) ideas of Chapter 2. The formal system codes an
intuitive idea of fprovable from certain axioms*; moreover the
system is strong enough tc generate all intuitively
acceptable theorems* (expressible in the system). This important
result, Godel's completeness theorem is the first substantial
theorem of the book and, together with its corollaries, is
the essential foundation for nearly all further work in model
theory.
The final chapter is a selective introduction to topics
in what might be termed fproper model theory*. The directions
taken are by no means the only ones which properly follow the
completeness theorem. The aim is to convey the flavour of
the subiect and to interest the reader sufficiently so that he
will be encouraged to study further with the help of one of
the more advanced standard texts on model theory.
I would like to thank several people for their help during
the preparation of this book. Robin Gandy, Anne Troelstra,
Derek Goldrei, and Michael Katz each read an early version of

vii
the text and provided much constructive criticism and advice.
At a later stage a duplicated version of the text was used in
Oxford and several students pointed out to me errors and
inaccuracies. I am grateful to them and to Alan Slomson who
suggested further corrections and improvements. Finally I
am indebted to Dana Scott whose idea it was originally that I
should write this book. His help during the preparation has
been invaluable.
October 1975
J.B.

CONTENTS
INTRODUCTION: BACKGROUND SET THEORY 1
1. RELATIONAL STRUCTURES 6
1.1 Definitions and examples 6
1.2 The first order language associated with a 16
relational structure
1.3 Interpretations 23
2. A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 40
2.1 Axioms and rules for the predicate calculus 40
2.2 Consistency 48
2.3 Language and metalanguage 52
2.4 Further metatheory 54
2.5 First order theories with equality 58
3. THE COMPLETENESS THEOREM AND ITS COROLLARIES 67
3.1 Definitions and outlines of the proof 68
3.2 Completeness for countable languages 71
3.3 Countable languages LE with equality 77
3.4 Completeness for uncountable languages 80
3.5 Applications of the compactness theorem 86
3.6 Completeness for the propositional calculus 93
4. BEGINNING MODEL THEORY 9 7
4.1 The Lowenheim-Skolem theorems 97
4.2 Completeness and categoricity 100
4.3 Elementary embeddings and model completeness 113
4.4 Completeness and decidability 135
FURTHER READING 137
REFERENCES 138
INDEX 141

INTRODUCTION
BACKGROUND SET THEORY
The fundamental mathematical concepts to be considered in
this book can only be defined relative to more basic, and it
is hoped simpler, more intuitive concepts. The concepts we
accept as our starting point are those of (naive) set theory.
The student having only minimal acquaintance with text books
of pure mathematics will be familiar with the introductory
chapter on set theory such books invariably contain. We will
assume knowledge of the contents of such a chapter. In order
to comprehend the most general form of the completeness
theorem in Chapter 3 and some of its corollaries in Chapter
4 the axiom of choice and some simple cardinal arithmetic
are needed. The following remarks highlight the aspects of
set theory which are most important for our purposes.
A set is a collection of elements. When the element &
is a member of the set S we write s e S and, conversely,
s I S denotes that s is not a member of S. Two sets S and T
are the same just in case they have precisely the same
elements (the axiom of extensionality). Hence S may be
described (uniquely) by exhibiting those elements which are
members of s. S = {x ,...,x } denotes that S has as members
precisely x ,...,x . More generally, S = {x : P(x)} denotes
that S consists of those elements x which satisfy the
proposition P(x). The set 5 is a subset of the set T, S Q T, if
every element of S is also an element of T. The empty set,
the set with no members, is denoted by 0. With any two
elements a,b we associate the ordered pair <a ,b) which has
the following property: < a ,b) = <a' ,b') just in case a = a'
and b = b'. (Any set-theoretic definition which has this
property is sufficient for our purposes. One example in
common use is <a,b) = f {{a}, {a,M}.) Now by induction on
n for n > 2 the ordered n-tuple < a±9...a ) of elements
a a 9 is defined to be the ordered pair «a„,... a „> ,a >.
1' ' n 1 n-1 n

2
BACKGROUND SET THEORY
Given any two sets S and T the union,
S u T, is {r: r e S or r e t); the intersection, S n T, is
{i»: r e S and 2» e T); and the cartesian product, S * T, is
{<s,£> : s e £,£ e 21} . More generally, if S ,. . . 9S are sets
and n > 2 then we define
S. u •... u 5 ={s:seS'. for some isl,...,«},
1 n *z,
5 n .... n 5 = {s: s e S'. for all £=l,...,n), and
5 x .... x s = {<s ,...,s > : s e 5. for £=l,...,n}.
5 x .... x S (n times) is sometimes abbreviated by Sn.
An n-ary relation R (n > 2) on £ne set 5 is a subset of 5 .
A unary relation on S is simply a subset of S. An n-ary
function or map f on S (n £ 1) is an (n+l)-ary relation on 5 with
the property that for each n-tuple <s1,...,s > e Sn there is
a unique s e S (usually written f(s±9.. . >s )) such that
< s ,... ,s ,s) e /. More generally, a function f from S to T
written / : S -»- T9 is a subset of 5 * 21 such that for each
s e 5 there is a unique t e T with <s,t> e f. When < s yt) e f
we write f(s) = t. If / is a function from 5 to T £ne
domain of f is S and the range of f is {t e T: for some
s e 5, <s,t) e /}. f is onto when the range of f is the
whole of T and one-one when for each t in the range of / there
is a unique s e S with <s,t) e /. / is a bije&tion when it
is one-one and onto.
Suppose {S.: i e 1} is a collection of sets indexed by
elements of the set J. The union of {S.: i e I}, U £.,
lei
is {s: s e 5. for some i e J} and the intersection of
{S^: £ e 1} is {s: s e 5. for all i e I}. The product
X S. is defined to be {/: f is a function, f: I + (J 5.
and /(<£) e 5. for all £ e I}. (When I is {l, ,n} then we
associate f: I + |J s^ with </(1),.. . ,/(n)> to accord
i-1,... ,n
with our earlier definition of £ * .... * 5 .) The axiom
of choice states that if for each i e I the set 5. is a non-
v
empty set then the product X 5. is also non-empty. The
iel v

BACKGROUND SET THEORY
3
axiom implies that there is at least one function, a choice
function which picks out from each of a family of non-empty
sets an element of that set. There are several important
consequences of this axiom and essential use of one of them,
the well ordering theorem, will be made in Chapter 3. First,
a few more definitions are necessary. A binary relationR on
S is a partial order on S if
(i) for every s e S, < s ,s> e' R (R is reflexive),
(ii) for every s ,s2,s e S if (s19sj e R and
(s2,sJ e R then ( s ,s ) e R (.R is transitive),
and (Hi) for every s 9s e S if <s19sJ e # and
^^sj e # then s = s (# is anti-symmetric).
When R is a partial order on S then we write s± < s7 for
<s1,s2> e #. The ordered pair <£,<> denotes the partially
ordered set. The partially ordered set <5,<> is totally
ordered if for every s1,s2 € ^ either s < s or s2 ^ s. (^ is
connected). A well order < on S is a total order such that
for every non-empty S Q S there is an sQ e S0 such that
s < s for all s e 5 (every non-empty subset of S has a
minimal element).
The well ordering theorem , which both implies and is a
consequence of the axiom of choice, states that every
nonempty set can be well ordered. An alternative equivalent
of the axiom of choice which will not be used in the text
but is referred to in the exercises is Zorn's lemma: suppose
<X9<) is a non-empty partially ordered set such that every
totally ordered subset Y Q X has an upper bound in X (i.e.
there is an element xy e X such that for all y e Y9y < Xy)\
then X has a maximal element (i.e. an element m e X such that
for all x e X,777 < x implies m - x) .
A binary relation < is a strict partial [total] order
on S if
(i) for every s e S9 not s < s (irreflexive)
(ii) for every s1>s2,s3 € S if sl < s2 and s2 < s3
then s1 < s3(transitive),

4
BACKGROUND SET THEORY
[(Hi) for every s 1,s2 e S either s± < s2 or s± = s2
or s2 < s (connected)].
A strict well order on S is a strict total order < on S such
that for each non-empty S Q S there is an s e S such that
for each s e S either s = sQ or s < s. Any partial [total,
well] order on 5, say £, induces a strict partial [total,well]
order of S, <, given by
s± < s2 iff s1 < s2 and s1 ^ s2*
Similarly given a strict partial order < the relation <
defined by
s1 < s2 iff s± < s2 or s1 = s2
is a partial order.
A transitive set S is a set such that for all s ,s if
s± e s e S then s e 5 (or, equivalently, s e S implies
s7 Q S). A transitive set on which e is a strict well order
is an ordinal. According to this definition the empty set
is an ordinal (in this context usually written as o) and if
a is an ordinal then a u {a} is an ordinal, the successor of
a, sometimes written as a + 1. An ordinal 3 which is not
the successor of an ordinal and is not 0 is a limit ordinal
and has the property 6 = U3 = {a: a e y for some y e 6).
The least limit ordinal, {0,{0},{0,{0}},...}, is denoted by w.
Since e is a strict well order on any set of ordinals we
sometimes write a < $ for a,6 ordinals and a e 6. Every well
ordered set (X9<) is order-isomorphic to a unique ordinal;
that is, there is an ordinal a and a one-one onto function
/: X ■* a such that if x± < x2 then f(x±) e /(a?2> or
/(#.) = f(x). So the well ordered set < X,<) can be written
{x~: $ e a} where x„ is the unique inverse image of 6 under
/. The principle of mathematical induction for the natural
numbers can be extended to the principle of trans finite-
induction for the ordinals (or, indeed, any well ordered set):
Throughout !iff! will be used as an abbreviation for
'if and only if!.

BACKGROUND SET THEORY
5
suppose P(a) is a property of ordinals such that for any
ordinal $, when P(y) holds for all ordinals y < 3 then P(B)
holds; then P(a) holds for all ordinals a.
The cardinal of a set X is denoted by J and is a
measure of the size of X. If X and Y are sets then we define
Y < Y (Y is at least as large as X) if there is a one-one
function /: X + 7; I = F if 7 £ F and F < J or, equivalently,f
if there is some one-one and onto function f: X + Y. A
corollary of the axiom of choice is that for any two sets
X,Y either X < Y or F < J; moreover cardinals may be
identified with certain initial ordinals (defined as those
which cannot be put in one-one correspondence with strictly
lesser ordinals). Let N denote the set of all natural numbers
(with 0) and X = F. A set X is finite iff for some natural
number n,X is in one-one correspondence with {o,...,n-l}.
X is infinite if it is not finite. X is countable if I < X
Suppose Y = k and F = X; the cardinal sum k + X is defined
to be X* u Y* where X*,Y* are disjoint sets with the same
cardinal as X,Y respectively (e.g. X* = X x {o},
Y* = Y x {{0}}); the cardinal product kX is X x Y;
X Y
and cardinal exponentiation k is defined to be X' where
X* - {f: f is a function from Y into X]. Some simple laws of
cardinal arithmetic, which follow from the assumption of the
axiom of choice, are stated in Chapter 3 (lemma 3.17). Full
details of all these set-theoretic concepts may be found in
any standard text book of set theory, e.g. Halmos (1960).
By the Schroder-Bernstein theorem; see Halmos (1960)
page 88.

1
RELATIONAL STRUCTURES
1.1. DEFINITIONS AND EXAMPLES
Mathematics is rich in structures. Euclid's notion of
three-dimensional space with points, lines, and planes and
the more recent notion of a group may be construed as typical
examples of a concept of 'abstract structure' that is
fundamental to the mathematician. Loosely speaking, such a
structure consists of a collection of objects, (first order)
relations between the objects, (second-order) relations
between those relations, and so on. The structure is
'abstract' in the sense that the nature of the objects and of
the relations is, mathematically speaking, irrelevant; the
importance of the structure from this point of view lies in
the underlying pattern of the objects together with the
relations. Euclidean space is a structure whose objects are
points, lines, and planes; relations are those such as
incidence, collinearity, and parallelism. A group is a
structure in which the key relation is that determined by the
group operation. Our first definition makes explicit a
particular form of this abstract concept, namely that of a first
order structure. This set-theoretic foundation Will underlie
our study of model theory.
Definition 1.1. A relational structure is an ordered
quadruple
% = <A, {R.} , {/.} , {ov} > with
v ieT 3 jeJ K keK
associated functions \:I + N,\i:J + N
such that
See Gandy (1973) for a lucid essay on 'structure' as
it occurs in mathematics.

RELATIONAL STRUCTURES
7
(i) A, the domain of SI, is a non-empty set,
(ii) I is a (possibly empty) set such that for
each i e I \{i) is a positive integer and
R^ is a A(£)-ary relation on A,
(iii) J is a (possibly empty) set such that for
each j e J y(j) is a positive integer and
f. is a y(j)-ary function on A,
V
(iv) K is a (possibly empty) set such that for
each k e K c«, a distinguished element
(or eotts£att£l, is an element of 4.
As indicated in the definition we use a Gothic letter
for a relational structure and adopt the convention that the
corresponding Roman letter denotes the domain of the
structure. If we allow A to be empty then certain technical
problems arise from subsequent definitions depending on the
notion of a relational structure. These can be overcome by
considering separately the case where A is empty. However
we prefer to eliminate this case at the outset. I, J, K are
indexing sets for the relations, functions, and distinguished
elements respectively. X,u are functions from I, J
respectively to N , the set of positive integers, coding the arity
of the relations and functions. We recall that unary
relations on A are identified with subsets of the domain A.
This unwieldy definition covers a very wide family of
mathematical structures. (Note however that we have excluded
structures with proper classes as domain.) For many of the
familiar mathematical structures a more restricted but
simpler definition would have sufficed. In some instances,
for example, the sets J and K are empty. When this occurs
Most set-theoretic definitions of 'function' identify
it with a certain type of relation, a so-called functional
relation (see page 2). Here we wish to distinguish between
some such relations, indexed by elements of J, and arbitrary
relations, indexed by elements of I.

8
RELATIONAL STRUCTURES
the relational structure is effectively an ordered pair
consisting of a non-empty domain A and a set of relations on A;
it is then said to be purely relational. Other simple forms
of structure are exemplified below.
Example 1.2. A non-empty set S can be considered as a purely
relational structure with a single binary relation, =, the
equality relation, <£,{ = }> .
When, as in this example, the set I is finite we omit the
brackets { } and instead list the relations. Thus the example
<£,{ = }> is written <£,=> and, in general, if J has n elements
{R.} is replaced by i?. i? . A similar replacement is
iel
made if J or K is finite.
To include the equality relation in the presentation
of a structure is, in a sense, superfluous. It does not
imply any 'structure' on the underlying domain. However, in
section 1.2 we introduce a language associated with a given
structure and this depends intrinsically on the relations,
functions, and constants explicitly displayed in the
presentation. Two different languages arise depending on whether or
not the equality relation is included. Most mathematical
languages do include a symbol for equality. At this stage
though we do not assume that the equality relation is given
in the presentation of a relational structure.
Example 1.3. The ordered set of natural numbers N with least
element o is a structure <#,<,0> with one binary relation, <,
such that the pair <n9m) e < just in case n < m in the usual
ordering.
Some familiar mathematical examples have a number of different
characterizations as relational structures.
Example 1.4.1. A group may be presented as a relational
structure of the form <G,=,*,e> , where G is the set of
elements of the group, = is the equality relation on G, *, a

RELATIONAL STRUCTURES
9
binary function, is the group operation, and e is the identity
element. We could also include a unary function, ,
representing the inverse operation.
Example 1.4.2. A group may also be presented as a structure
with the following form: (9 = < G,M,e) where M is a ternary
relation representing the group operation '•' in the following
way:
<91,g2>93) e M iff g± . g2 = g ^.
The group axioms then ensure that
(i) if <g1,g2>g3) »<^,2,^4,^5> € M then there is a
unique ^ e (? such that <g1,gs,g6> ,
<^3>^,4,^6> e # (associativity of the group
operation);
(ii) for each g e G, < g ,e ,g) e M and < e ,g ,g) e M
(e is the identity element);
and (Hi) for each g e G there is a unique # e G such
-1 -1
that < g yg ,e) ,< g ,#,£> e M (every element
has an inverse).
Alternative presentations may be given either by omitting the
constant e or by adding the equality relation. The structure
<G,M,e) of example 1.4.2 is, from a purely formal point of
view, simpler than the structure <£,=,•,e) of example 1.4.1.
The function • is replaced by the relation M. This kind of
replacement is always possible when the set of functions
{/.} in the relational structure % is non-empty. We sub-
stitute for the U(J)-ary function /. the (u(J)+l)-ary relation
3
R„ given by
7 A
If a function is defined as a certain kind of relation
(as on page 2) then M is just • ! However the presentation
differs from that in 1.4.1 because j is now empty and there
is a single ternary relation in place of a binary function.

10
RELATIONAL STRUCTURES
<a0,...,au(i)> €R iff /J-<«0.---.flW>-l) = %(J)-
J
We can go one stage further and replace each distinguished
constant e by the unary relation R = {c} so that the
resulting structure %R = < A , {R.} u {/?- } u {R } > is
* iel 'j je«7" Cfe keK
purely relational. Although purely relational structures are
technically simpler than the most general kind of relational
structure we prefer, in most cases, to consider structures
with the added complexity due to functions and constants. In
the transition from a function / to the associated relation
Rjf the functional character is obscured. Although functions
are sometimes introduced as special kinds of relations they
themselves are so fundamental in mathematics that it is
natural to exhibit them explicitly as functions in the
structure. It is for instance more natural to think of a
group as a set G together with an operation • : G * G + G and
a distinguished element, e, the identity, rather than as a set
G with a ternary relation R and a unary relation R . From a
mathematical viewpoint the two structures $1 and the associated
purely relational structure are identical. However as
relational structures they are distinct. For the remainder of
this book a relational structure is assumed to have a unique
presentation of the form
<A9 {R.} , {/.} , {oA > .
% iel ° jeJ K keK
Exercise 1.1. Give at least two distinct presentations of a
field as a relational structure.
The final example of a relational structure demonstrates that
the definition allows the inclusion of structures with more
than one kind of basic element.
Example 1.5. A vector space over a field F is a structure
58 = <V, U, F, +, • , 0^, 0F, ip

RELATIONAL STRUCTURES
11
where V is the set of vectors and scalars (elements Q£ ^ ^ ^
F are unary relations such that
v e U iff v is a vector,
and a e F iff a is a scalar,
0,. is the zero vector, 0 is the zero scalar, 1„ is the unit
element of F> + is a binary function representing both scalar
and vector addition, and • is a binary function representing
scalar multiplication and multiplication of a vector by a
scalar. In the definition of a relational structure functions
are assumed to be defined on the whole domain. However in an
arbitrary vector space multiplication of two vectors is not
defined. Likewise there is no operation of addition on a vector
and a scalar. In order to construe a vector space as a
structure in the sense of definition 1.1 we suppose that
multiplication is defined on a pair of vectors in some purely
arbitrary way; for example v • i>2 = 0U for any vectors v ,v2.
Similarly if a e F and v is a vector then a+v is given some
arbitrary value (in V). Thus in a sense we have imposed extra
structure on the vector space so as to bring it in line with
the general definition. If the corresponding ternary relations
R and R are used in place of the functions * and + then no
+
such problem occurs.
The example given of a vector space is just one instance
of a common phenomenon in mathematics, that of a structure
with several different sorts of basic objects. Another
familiar example is Euclidean space with points, lines, and
planes. Although such examples can be construed as relational
structures of the type defined in 1.1 (as is done above for
vector spaces) an alternative method is to consider many-
sorted structures (i.e. structures with an indexed set of
domains each containing objects of a different sort) from the
start. For further details of this approach see e.g. Kreisel-
Krivine (1967) Chapter 5, or Wang (1952).

12
RELATIONAL STRUCTURES
Because the class of relational structures is so wide
it is convenient to be able to consider those structures in
some well-defined subclass. The following definition provides
a useful classification.
Definition 1.6. Given a relational structure
« = <A,{R } , {/.} , {o } >
v iel d jeJ K keX
the type of%* $9t, is the ordered triple
<K, X, u>
where X: I + N , \i: J + N are functions coding the arity of
the relations and functions respectively. The type of a
structure is simply a measure of the relations, functions
(together with their arities) and constants in the structure.
Notice that is does not code the cardinality of the domain.
Two structures % and 33 are of the same type just in case 6~
is the same .as 6~>. Two structures may be of the same type
even when the domains are of different cardinalities but their
relations, functions-, and constants will be in one-one
correspondence. Two groups presented as <G,=,*,e> and <G',=,+,0>
are of the same type according to definition 1.6 but the
groups <G, =, *, e) and < G' , A, o> (where A is the ternary
relation representing +) are not. We say the structures %
and 33 are of similar type if 6^ = < K,\ ,y> and 6«x = < K' ,X ' ,u'>
and there are bisections ft • J->-J' ft* J + J' ft : K + Kf
J 1 '2 3
(J', J' are the domains of X',u' respectively) such that
X(i) = X'(ft (i)) for each i e I and u(j) = u'(ft2(j)) for each
j e J. Thus structures of similar type can readily be re-
indexed so as to become structures of the same type.
It is usual to single out from an arbitrary algebraic
structure certain distinguished subsets. We consider
subgroups of groups, ideals and subrings of rings, subspaces of
vector spaces, and so on. Such subsets are characterized
as those non-empty subsets which are closed under the alge-

RELATIONAL STRUCTURES
13
braic operations defined on the structure. These are
themselves structures under the induced relations and restricted
functions. Consideration of this construction motivates the
following definition.
Definition 1.7. Suppose 31 = < A, {/?„.} , {/.} , {o,} >.
% id ° jeJ K keK
A substructure of 31 is a relational structure of the same
type as 31, say 33= <B, {£.} , {g .} , {<*-} > satisfying
% iel ° jeJ keK
the following conditions:
(i) B c a (the domain of a substructure of 31 is
a subset of the domain of 31) ;
(ii) for each i e I, R. n BX(t,) = S. (5. is the
restriction of if. to the domain of 33 ) ;
(Hi) for each &,..,& .. e B, each j e J,
^(ii"-'iu(j)) = 0(ii'--'2'y(j)) (?j is
the restriction of the function f. to the
3
domain of 33 which must therefore by definition
1.1 be closed under the function /.)»
3
(iv) for each keK, o, = <L (each distinguished
element of 31 is in the domain of a
substructure of 31) .
If 33 is a substructure of 31 then 31 is an extension of 33. We
write 33 <= 31 or 31 3 33.
Exercise 1.2. Show that c is a partial ordering on the class
of realizations of type 6.
We now reconsider some of the earlier examples in the light
of this definition. A substructure of the set <£,=> (example
1.2) is trivially a subset and conversely a subset is a
substructure. A subgroup < H, = ,• 9e) of the group <£, = ,• ,e)
(example 1.4.1) contains the distinguished element e and is
closed under the operation • ; it is therefore a substructure.
However a substructure < G' , = ,• ,e) of the group <G, = ,*,e> is
not necessarily a subgroup. There is no reason to suppose

14
RELATIONAL STRUCTURES
that Gr is closed under inverses. For example the non-zero
integers form a substructure <Z - {o},=,*,l> but not a
subgroup of the non-zero reals under multiplication
(R - {o}, = ,*,i> . Furthermore substructures of the group
<G,M9e) (example 1.4.2), say <G'9M',e) , are not necessarily
closed under the group operation, let alone under the inverse
operation. Despite this it is possible to present a group in
such a way that the substructures are precisely the subgroups.
For consider a substructure <#,=,*, 9e) of the group
_ i
<<?, = ,*, ,e> . By definition 1.7 (iv) e e H and by (Hi) H
is closed under •,
Exercise 1.3. Is a substructure of the ring
<#, =, +, •, o> necessarily a subring?
What happens if the unary additive inverse operation is added
to the presentation of the ring?
Exercise 1.4. Give a presentation of a field so that the
substructures are precisely the subfields.
Just as a subset S of a group 0 generates a subgroup G„, the
smallest subgroup of G containing S, so a subset S of the
domain of a relational structure 21 generates a Substructure
21 , the smallest substructure of 21 having a domain with S as
s
subset. The domain of SIC is the closure of 5 u {c-h} under
the set of functions ifj} . ,. Note that any non-empty
subset of the domain of a purely relational structure 21 is
the domain of a substructure of 21.
Mappings between two algebraic structures of the same
kind that preserve structure are called homomorphisms. We
adopt precisely the same terminology.
Definition 1.8. Suppose 21 = < A, {R.} , {/.} , {e,} >
: V iel 3 jeJ K kcK
and 33= < B, {S.} , {g .} , {d,} > are two structures
V iel 3 jeJ K keK
of the same type. A map h: A -* B is a homomorphism from 21 to

RELATIONAL STRUCTURES
15
SB iff for each id, jeJ, keK, a. , . . . ,a, , . >. , a.9...9a ,..9aeA9
1 A\V ) 1 \1\ J )
<al--->a\U)} £ Ri " <*<«1>'-"-'fc(aA(i))> e V
/.(a1,. . . »«jl(J-)) = a "* gjihia^ ,. . . >7z(au(J-))) = Ma),
and ft(efe) = a^.
ft is a mapping that preserves structure.
A homomorphism from <G,=,*,e> to <Gr,=,+,0> when the two
relational structures are groups is a group homomorphism in
the usual group-theoretic sense.
Exercise 1.5. Is a homomorphism (of relational structures)
from the group <G9M9e) to the group < G' 9Mf 9e') a group
homomorphism?
Exejcise 1.6. Suppose h: (£ -*■ S) is a homomorphism. Is the
image of (S under h9 h((&), a substructure of D?
Definition 1.9. The homomorphism h: 21 + 33 is an isomorphism
if there is a homomorphism h': SB ■* 21 such that ftftr is the
identity map on SB and hfh the identity on 21. In this case
we write 21= SB. h is an embedding if h is an isomorphism
between 21 and ft(2l) •
Exercise 1.7. With the notation of definition 1.8 show that
h: 21 + SB is an isomorphism if and only if
(i) h is a bisection;
(ii) for each i e J, a ,...,aw. x e A
1 A ^ ^ )
<ai'"-aX(i)> £ *i i££
< h(a±) , . . . >fr(aA(£) ^ € ^V*
(£££J for each j e J9 a^ ,...,a , .. £ 4
Mft7.(a1,...,au(t.))) = j^Uj),...,^.,));
and (iv) h(-°k^ = dk for each k e K'

16
RELATIONAL STRUCTURES
Exercise 1.8. Give an example of non-isomorphic structures
51, 33 of the same type such that there exists a homomorphism
h: % + 93 with In a one-one map from A onto B.
1.2. THE FIRST ORDER LANGUAGE ASSOCIATED WITH A RELATIONAL
STRUCTURE.
In the first section we formalized a general notion of
'relational (algebraic) structure' which was sufficient to
embrace many types of structure studied by mathematicians.
Propositions about particular structures, such as for example
theorems concerning groups, are formulated by mathematicians
in English (with some standard abbreviations). In order that
such propositions may be formulated in a more precise and
unambiguous way, a formalized language associated with a given
structure is introduced.
Definition 1.10. The first order language L(%) for the
structure 3l(= <A, {R.} , {/.} , {c,} >) consists of
v iel ° jeJ K keK
(i) individual variables v.,v.,...9v ,... (for neN);
0 1 7*
(ii) individual constants c, for each k e K;
(Hi) a A(£)-ary predicate letter R. for each i e J;
(iv) a y(j)-ary function symbol f . for each j e J;
3
(v) logical connectives -('not1) and & ('and');
(vi) the universal quantifier V ('for all');
and (vii) brackets (,).
We adopt the convention that a boldface symbol in the language
corresponds to the light face symbol for the relation, function,
or constant in the structure % (e.g. the predicate R .
corresponds to the relation R^). Notice that the language L(2D
depends effectively only on the type of the structure $L. The
languages for two structures of the same (or similar) type
are, up to alphabetic variants, identical. Thus we will
sometimes write L(<5) for the language associated with all
structures of type 6. L will denote an arbitrary first order

RELATIONAL STRUCTURES
17
language. We say that % is a realization of the language L(%)
(or L(6) if a is a structure of type 6).
Finite strings of symbols of L with particular well
defined forms constitute the vocabulary of L. Terms, atomic
formulae, and well formed formulae are inductively defined
subsets of the set of all ordered finite subsets of symbols
in L.
Definition 1.11. The set of terms of L, Term (L), is the
smallest set X such that
(i) all individual variables v ,v ,... and
individual constants, c, for k e K are members of X
and (ii) if *!»••• »*y(j-) * * then f j(*i»• • •> *U(j )) e *
(for each j e J") .
Exercise 1.9. Verify that each term of L is a finite string
of symbols of L.
Definition 1.12. The set of atomic formulae of L, Atom (L),
consists of all finite strings of elements of L with the form
R .(£„ ,. . . ,£w .. ) where i e I and t ,. . . ,£, , . * e Term (L).
Definition 1.13. The set of well formed formulae of L,
Form (L), is the smallest set I such that
(i) all atomic formulae are members of Y
and (ii) if $, * e 7 then (<(> & i|0, -<f>, Vv .$ e 7.
Exercise 1.10. Verify that each well formed formula of L is
a finite string of symbols of L.
As indicated in the definitions we use t (with or without
subscripts) as a variable for a term of L and <(>, ty, x>-»- as
variables for well formed formulae. We sometimes use x as a
variable ranging over the set of variables {v^ : i = 0 ,l ,2 ,'.. } .
A 'well formed formula1 is sometimes abbreviated to a
1 formula'.

18
RELATIONAL STRUCTURES
Definition 1.14. The set of subformulae of a formula <(>,
Subform (<\>), is defined recursively:
Subform (W---.*x(i)>> = <W... *AU)};
Subform (-.<[>) = {-.<[>} u Subform (<(>);
Subform ((<() & #)) = {(<j> & i|;)} u Subform (<(>)
u Subform (\p);
and Subform (Vy.<(>) = {vv.<(>} u Subform (<j>).
It is immediately apparent from the definition and exercise
1.10 that for any $ e Form(L), Subform ($) is a finite subset
of Form(L) and that $ is atomic if and only if Subform ($)
contains the single element $.
The logical connectives v (!or'), + ('implies1), •**
(!if and only if1) and the quantifier 3 ('there exists') are
defined in terms of the primitives as follows:
*))
Note that v, -►, <*9 3 are not elements of the language L but
are simply used as convenient abbreviations in certain well-
formed formulae.
Alternative formulations of a first order language L can
be given using other sets of primitive connectives in place
of {-», &, V}. Each of the pairs {-•,-»■}, {--,v} is a possible
set of primitive propositional connectives; the remaining
propositional connectives can be defined in terms of truth-
functionally equivalent forms involving only the primitive
connectives. Similarly, the existential quantifier 3 may be
taken as the primitive quantifier and the universal quantifier
is then defined in terms of 3 and -1. The use of a minimal
set of connectives is simply a convenient technical device
which shortens some definitions and proofs, and the particular
set chosen here is just one such minimal set.
(*
(*
3v
+ ♦)
«► i|0
,.*
= Df
= Df
= Df
-i(4>
((*
-»vi^
& -.*)
+ ♦)
r-«+

RELATIONAL STRUCTURES
19
A few more definitions related to the notion of a well
formed formula <\> are necessary.
Definition 1.15, The scope of (the exhibited occurrence of)
the quantifier Vv. in .... Vv .(j> .... is <\>.
Definition 1.16. An occurrence of a variable x in <(> e Form(L)
is bound if and only if either it is immediately after the
sign V in <(> or it is in the scope of a quantifier occurrence
Vx in <(>.
An occurrence of x which is not bound is free.
In the case where the occurrence of x is in the scope \p of
a quantifier Vx in <(>, x is said to be bound by that quantifier
occurrence provided x does not lie in the scope of a
quantifier Vx in \\) (i.e. x is bound by the innermost quantifier
occurrence within whose scope x lies). Thus for instance in
the formula Vx3z/ VxR(x,i/) the occurrence of x in R(x9y) is
bound by the quantifier Vx immediately preceding R and not
by the leftmost quantifier Vx. We illustrate the two
preceding definitions with some examples.
Consider the formula: Vv± R± (f (v± ), c) & R^i^ ,i>2 ,d)).
The scope of the quantifier Vy„ is R ±(f(v ) ,c). Hence the
first two occurrences of the variable v„ are bound whereas
l
the third occurrence (in R 9(v ,v7,d)) is free. The single
occurrence of v is free.
In the following formula: 3y2(Ri(y2,C) "*" R2(yi,f (yl ,y2)))
each occurrence of v9 is bound whereas v is free at each
occurrence.
Bound occurrences of variables (in a first order formula)
may be compared with 'dummy' variables that occur in other
familiar mathematical expressions. For example, suppose
/: R -*■ R is a real-valued integrable function on the reals.
Occurrences of x in the expression fix) are free whereas in
A
the expression J f(x)dx the occurrences of x in f(x) become
,i °
bound by J ...dx. The effect of the integral sign is similar
0

20
RELATIONAL STRUCTURES
to that of the quantifier; it binds the free occurrences of
x occurring within its scope. Similarly in the expression
00
£ a for an infinite convergent series the occurrences of n
n=i °°
are bound, or dummy variables. In this case £ binds the
variable n (which occurs free) in a .
The use of brackets (), in the definition of a formula
(1.13) and of the defined connectives v, + , •»■ ensures that
given any formula <(> its subformulae are unique and can
readily be extracted from <(>. Consider the formula
( -. (<j> & -♦)& x).
Without brackets this- becomes -*<\> & -»^ & x which is- not a
formula. We can insert brackets to give a formula but there
is no unique way of doing this: besides the original
formula (-»(((> &-\|0 & x) we can have ((-»<(> & -ii|0 & x)>
(^4> & (-4 & X)),(-i* &-»(♦ & X))» -»((* &-»♦) & X)
etc.. Sometimes it is possible to omit certain brackets in a
formula without losing unique readability. We shall often
leave off the outermost brackets of $ when the outermost
connective is binary (i.e. &, v, +, «►) . If we adopt a
standard convention other brackets may also be omitted. The
propositional connectives fall into three groups: -. , & and
v, -+ and •»-, each of which is considered more binding than the
one succeeding it. This means that, for example,
((-.<(> & i|/) -»■ (x v <(>)) can be written
-,((> & \\) ■+ X v ^
unambiguously, according to the convention. We cannot
however drop any brackets in the formula
-.(-.* &((♦ + x) v *))•
Another standard convention is to write
♦ & ... & *fc or & ^i for (<|> &(<f>2 &...(...(& *fc)...)
and *1 v ... v if; or Y *i £or (^l V(*2 •••(•••(v ♦fc)---).
l<£<fc

RELATIONAL STRUCTURES
21
It is sometimes convenient to display for a particular
(j> £ Form (L) the variables which have free occurrences in <\>.
We will use the notation <t>(x ,. .. ,x ) to denote that
(j> £ Forw (L) and that the free variables in <\> (necessarily
a finite number since <t> is of finite length) are included
in the set {x ,...,# }. Similarly, if t e Term(L) we use
t(x ,... 9x ) to denote that the variables occurring in t are
in {x„, 9x }. We will sometimes abbreviate this using
In
vector notation: (|> (5) stands for (|> (x± , . . . 9x ) and £(£) for
t(x ,...,# ). Similarly a finite sequence of like
quantifiers Vtf„ . . . Vx (or 3 a:, ... 3a; ) will sometimes be written
+ i n I 1 nJ ^
Var (or 3ar) . If <t)(ar) £ Form(L) then $(£) in Form(.L) will
denote the formula obtained from $(x) when each free
occurrence of x. is replaced by £ ..
If Is
Consider the following formula: Vv^Cy v ) (where
v has a free occurrence in (J>) . y is an individual variable
and indeed is meant to represent a variable in the sense that
the substitution of another arbitrary variable for each free
occurrence of the variable v does not change the formula
essentially. But suppose we substitute v for y . Then the
formula becomes Vy <j)(y ,v ) which no longer has a free
variable. A similar situation arises if the term f(i> ) is
l
substituted for v . The following definition is designed to
prevent precisely this kind of 'clash' occurring when an
arbitrary term t is substituted for a free variable a; in a
formula (j>.
Definition 1.17. t e Term(L) is free for x in <$ e Form(L)
iff the variable x has no free occurrences in (j> which lie
within the scope of a quantifier Vz/ where y is a variable
occurring in t.
The definition ensures that if t is substituted for x in <t>
then no variable in t becomes bound, as it were, accidentally.
In the example preceding the definition neither the term v
nor the term f(v±) is free for v2 in Vi? (p(y ,y2). We
remark that for any formula (j> the variable x is free for

22
RELATIONAL STRUCTURES
x in cf).
Exercise 1,11, In which, if any, of the following formulae
is the term f(v 9v ,c) free for v2*.
d) (R(y1,y2) & s(y2,c)) -► vi^Rd^.c)
(££; R(g(wl9y2)) v vy1s(g(y1,c)9y1)
(Hi) Vy1R(y1,y2,y3) & SC^^)
(£i>; Vy± Vy2R(y1,h(y1,y2))?
Definition 1.18. If <(> e Form(L) and <() has no free variables
then (J> is a sentence. We use the abbreviation Sent(L) for
the subset of Form(L) consisting of all sentences and a as a
variable for sentences.
Definition 1.19. If $(x , ,x ) e Form(L) then the
closure of <(> is Va; ... Va; $(x ,...,# ) e Sent(L).
We showed at the beginning of this section how to associate
with a given relational structure 21 (up to isomorphism) a
unique language L($). More precisely, there is a one-one
correspondence between types of relational structures and
first order languages. It is sometimes convenient to consider
an extension L* of a given first order language L formed by
adding new non-logical symbols, predicate letters, function
symbols, and individual constants. A realization 21 for L
will not in general be a realization for L*. However 21 can
be expanded to a structure 21* which will be a realization
for L*. The way this is accomplished is by the imposition
of extra structure on the domain A of 21. The structure 21*
will have the same domain as that of 21. Wew relations and
functions are then defined on A in one-one correspondence
with the new predicate and function symbols in the language
and similarly certain members of A are singled oat as
distinguished elements in correspondence with the new individual
constants in the language. For example, consider the language

RELATIONAL STRUCTURES
23
£(<§» for a group ®= <G, = , + ,0> . Any ring <#, = , + ,0> presented
as an additive group, is a realization for L($). If a new
function is added to £(©) to give L*, the language for a
ring, then the full structure of the ring <#,=,+,o,-> is a
realization for L*. A structure H* obtained from the
structure fc by the addition of new relations and functions
on A and an enlargement of the set of distinguished elements
is an expansion of 21 and % is a reduct of 31*.
1.3. INTERPRETATIONS.
A first order language L, even though associated with a
given (type of) structure, is technically a syntactic object
with no semantic significance. However the intention is to
be able to express propositions concerning a given structure.
It remains to be shown how this is to be achieved.
The variables are to be interpreted as ranging over the
domain A. The constant symbols and function symbols are
interpreted as the constants and functions with which they
are in one-one correspondence. So the terms, relative to an
assignment of elements of A to the variables, are interpreted
as elements of A. The predicates are interpreted as the
corresponding relations and the connectives have their
intended meaning: '-i1 is 'not1, !&! is 'and1, and War1 is
'for every element of 4! . A given formula <(> is interpreted,
relative to an interpretation of the free variables, as an
assertion about 8. For example consider the cyclic group
with six elements, G = {g,g ,...,# = e). Let ©= <G, = ,-,e>
and <(> e Form(L(©)) be the formula: (v - v )- v = e. (We
write x>y instead of • (x,y) for the binary function
representing the group operation and t =t for =(t 9t ).) If v is
interpreted as e, g , or g then <(> makes a correct assertion
3 2 3 4 3
about © since e , (g ) 9(g ) are all equal to e. However
3 5
if v is interpreted as g9 g , or g then the assertion made
by <(> is no longer valid. The formula Vy ((y -y )-y = e)
has no free variables and so makes an absolute assertion
about ©:

24
RELATIONAL STRUCTURES
'for all g e G9 g3 = e'
which is false.
Alternatively lv A(v* v )• v = e) makes a correct assertion
because it is an abbreviation for
- W± - ((v1-v1)-v1 = e),
3
i.e. !not for all g e G is it not the case that g = ey
Q
or 'there is some g e G such that g - e'.
These informal ideas illustrated above on the intended
meaning of the language L(5l) are now incorporated in a formal
definition. First let a = <a ,a ,...> be an infinite
sequence of elements of the domain of the structure %. We do
not insist that the elements a., as elements of A, be
distinct and indeed each a. may be the same element of A. The
assignment determined by a is that in which the variable v.
is interpreted as the element a. e A. A further piece of
notation we shall use is the following: a(&/ ) is an
abbreviation for the sequence obtained from a with b replacing a ,
i.e. *(2>/n) = <a0,a1,...,an_1,Z?,an+1,... > .
First we show how to interpret terms of the language
L(%) in the structure 91 relative to the assignment a.
•Definition 1«20« The denotation of a term t in 21 with respect
Of
to a, £ [-a], (where a is the sequence < a ,a ,. . . >), is
defined recursively as follows:.
(i) if t is y. then £ [a] = a.;
i v
(ii) if t is c, then £^[a] = o,;
(Hi) if £ is f.(£„,...,£ /-x) then
This definition is very natural; each variable v. is replaced
by the element a. e A and each constant and function symbol is
replaced by the distinguished element or function to which
it corresponds. Relative to a given assignment there is a
or
unique element t [a] e 4 associated with t e Term(L(2I)).

RELATIONAL STRUCTURES
25
Definition 1,21. a satisfies $ in 2l,2lK <(>, where
(J) e Form(L(yi)), is defined recursively:
U) * ha V*i""'*X(i)) i« <*12lta],...,*X(.*[a]> e a.;
(ii) % |= -(J) iff it is not the case that
aha ♦;
(Hi) «|=a (l>1 & <f>2 iff Sl[=a ^ and 2l|=a <f>2;
riy; a |-a Vv^cf) iff for any b e A * Ha(2,/. )*- +
Definitions 1.20 and 1.21 may be thought of as providing a
dictionary which, in a given context, 'translates1 the formal
language L(2l) into English. The logical connectives, which
are independent of the context, -», & are given their intended
meanings, !not!, !and!. As a corollary to the definition
the defined connectives +, v, •»■ also have their intended
interpretation under this definition. Likewise the
existential quantifier 3 is interpreted as 'there exists an element
of A such that....1 just as (1.21 (iv)) V is interpreted as
1for every element of 4....1.
Lemma 1.22. For every <(>, \p e Form(L(%)) and every sequence
a in A
(a)
(b)
(o)
(d)
Proof:
*h
*Ha
*h
*h
(a)
by 1
<j) V \\)
<f> + ♦
<(>•»■ \p
3M
(f) V lp
..21
iff ^Ha * or flf=a #;
iff w/zem a |= (p tTzerc 21 f=a ^
iff not ttf=a (() or 5l|=a *;
£// 21 H=» <(> Just in case % 1=
1 a a
iff for some Z? e i4 31 f= a (2?/ )
is by definition -.(-<() & -«^). S
*;
The definition of satisfaction using an infinite
sequence a of the domain is due to Tarski (1935).
Alternative forms of definitions 1.20 and 1.21 can be given using
only a finite sequence of elements of the domain as in e.g.
Chang and Keisler (1973).

26
RELATIONAL STRUCTURES
3l|= 4>v\\) iff it is not the case that 21 (=a — $ & -»if>
iff it is not the case that 51 |=a -i<(> and a |=a-i^.
By 1.21 di) it is not the case that 3l|=a -.<(> just when H (=a <J>.
So 31 |=a <()V^ iff either 31 |=a <(> or 31 |=a #.
(b) and (ej are left as exercises.
To prove (d) we first remark that 3y.<(> is by
definition -iVv . -»<(>. Then definition 1.21 implies that
$|= 3i>^<t> iff it is not the case that 21 |=a V^-.<|)
iff it is not the case that for all b e A
«l"a(»/.)^
iff for some 2? e 4 it is not the case that
aN(2,/-)-*
iff for some b e A 31 (= a(£/.) *• D
To illustrate the formal definition of satisfaction consider
the structure <£,<> with domain Q9 the rationals, ordered by
the relation <. Then L(Q) contains a single binary predicate
< corresponding to the relation <.
Suppose <f> is 3v1(vQ<v1 & v1<v2 & Vy3^yi<y3 "*" yo<y3^"
We write O for <Q9< > and q for a sequence of rationals. By
definition 1.21 and lemma 1.22
Ok <J> iff there is a rational x such that
Q'*q(a:/ ) y0<yl & yl<y2 & Vy3(yl<y3 * Vy3}
iff there is a rational a; such that
(i) Q l=qf i>0<yi>
and (iii) for every rational z/ if
Q,= q'(2//3)I'l<y3 thenCh,'(y/,) Vy3
(where qr is q(x/1))
iff there is a rational a; such that
(i) yQQi:qr3 < y^Eq'] < i>f*Cq'3
and (ii) for every rational y if

RELATIONAL STRUCTURES
27
then y0°[qr(z//3)] < v3°[q ' (j//3) ] .
Now we use definition 1.20:
yP[qr] = ql = |^0 if £ = o; z^Pnq' (y/ 3) ] = |<?0 if j = 0
if i = 1 la? if j = 1
\q2 if i = 2 \ 2/ i f j = 3
Combining these results we have:
Qk <b iff there is a rational x such that
' q
(i) qQ < x < q2
and fiij for every rational y if x < y then q < y
Now if q < x then necessarily for every rational y,x < y
implies q < y. So the condition on the right above will be
satisfied just in case there is a rational x with q < x < q„
So finally, O (=q * iff qQ < q2-
Exercise 1.12, For which sequences of rationals q does
<<?><> l=n * where <J) is (a) vQ<v± & 3v2(v±<v2)
(b) V*>0(yo<yl & v±<v2 + vQ<v2)?
Exercise 1.13. For how many groups < G,=,«,e> (up to
isomorphism) does
4
<y4 = y0Vy4 = yiVy4 = y2Vy4 = V
9
for all sequences g?
It can be seen from the example <£,<> (= <J) where <J) is
3v (vQ<v & v^<v2 & Vy3(yi<y3 "*" yo<y3) that the onl>r e!ements
of the sequence q that affect the truth value of <£,<> |= <(>
are q and q , the elements corresponding to the free variables
v and v in <J). An inspection of definitions 1.20 and 1.21
shows immediately that the only elements of the sequence a that
affect the truth value of % 1= d> are those a. such that v.
1 a T v i>
occurs in <(>. The following theorem shows that in fact the
only elements a. which affect the truth value are those such
that y. is free in A.

28
RELATIONAL STRUCTURES
Theorem 1.23. Suppose v. , ...,t>. are the free variables
" " vo %k
of <j>.
Then for any a, SI ^ $ ^// /or a^ sequences b
a
>
b(a. /. ,...,a. /. )
Proof: We first remark that a consequence of definition
1.20 is that **[a] = **[b ] if a.*b. for all i such that v.
occurs in the term t. We prove the theorem by induction
on the length of <J) (which may be measured by the number of
connectives and quantifiers in $). Note that a subformula
<J> r of the formula <j> may have free variables which are not
free in <(>.
First we consider the case where <(> is atomic (i.e. has
length zero). Then <(> is of the form R . (t ... . ,£, , . N). The
free variables of $ are those variables occurring in
t , ...,£w.*. Suppose these are v. ,...,v. . Then by the
i a^v) iq ik
preliminary remark, for any sequences a ,b
*Aa] - * *Cb(a. /. .....a. /. )] for r-1,. . . ,X U).
r r *<? %o %k %k
Definition 1.21^^^ then implies that for any sequences
a'b *l=a Ri(*i *X(i)> iff
a^b(a. /, ,...,a. /. ) Ri(*l'---'*X(i)K
00 fc k
Now suppose that <() is —»ip - The free variables of <(> are
those of i|; and by the induction hypothesis, since \\> has fewer
connectives and quantifiers than <(>, for any a
SI (= 4* iff for all sequences b
a
th ■><*«„" W ''
0 0 AC K
For any formula X either SI k X or SI k -» x and so
a d
SI k 4> iff for all sequences b, SI |= . , , <(>.
a , u^ /^ , ...,a. /. ;
o o k k
The case where <fr is $ & <t>2 is equally straightforward,
using the induction hypothesis for the formulae <(> , <J> , and
will be omitted.
Lastly suppose that $ is Vv .if>. Then y. is not a free

RELATIONAL STRUCTURES
29
variable of <(> but may be a free variable of ty. By
definition % 1= 6 iff 91 h ^x/.x ^ for all b £ 4. The induction
1 a &\ dIq )
hypothesis applied to \\> yields
$lf= .,, . ty iff for all sequences b
V
*tb<b/ a. / ,..., / ,*■
So $11= <(> iff for all b e A and all sequences b
+ btb/j9a. Ii ,...,a /^ )
and hence 91 |=a <(> iff for all sequences b
*H(a./ a. I. ) ♦• D
O O k K
The method of proof used in theorem 1.23, induction on the
length of a formula, illustrates a fundamental principle
that is frequently used to establish properties of all
formulae of L. There are four cases to consider
corresponding to the clauses of definition 1.13. First the property
is established for atomic formulae and then, assuming the
property to hold for all proper subformulae of <J), it is
established for <(> first of the form -.ij;, then of the form
<(> & <(> , and finally of the form Vv.iJj. The complexity of
a formula <(> can be measured by the number of connectives and
quantifiers in <t> and induction on this natural number is used
to establish properties of <(>.
Corollary 1.24. For all o e Sent(L( ))
either $1 k o for all sequences a
or % k -.a for all sequences a. .
Proof: A sentence a by definition has no free variables and
so this corollary follows immediately from theorem 1.23. D
Following the definition of free and bound variables (1.16)
certain analogies were noted between occurrences of bound
variables in first order formulae and dummy variables used
elsewhere in mathematics. The first example cited there was
the expression for the definite integral f f(x)dx. This
o
integral may equally well be represented by the expression

30
RELATIONAL STRUCTURES
1
f f(y)dy (provided y does not occur in the expression fix)).
J o
The switch of dummy variable from x to the new variable y
does not alter the gleaning of the expression. Similarly the
two infinite sums \ a and \ a (where m does not occur
rc=l w=i
in the expression a ) represent the same real number. A
precisely similar situation occurs when bound occurrences of a
variable v . in a formula <(> are replaced by another variable
v. not occurring in <(>. The meaning of <(> in any given inter-
3
pretation is unchanged.
This is established in the following lemma.
Lemma 1.25. Suppose v . does not occur in <(> and that $\ is
the formula resulting when each bound occurrence in <b of v .
is replaced by v .. Then for any structure 21 and sequence a
3
a l=a * iff a ha +j
Proof: Again we use induction on the length of <(>. In the
case where <(> is atomic there is nothing to prove for then <(>
does not contain bound occurrences of any variable and so
$\ is the same formula as <(>. When <(> is ->ty then $\ is -i^.
3 3 3
In this case the result follows immediately from the induction
hypothesis and the satisfaction definition. The case where (j) is a
conjunction <(> & <(> is equally straightforward. Now $\ is
i i ^
($-)• & (<f>0) • and the induction hypothesis gives us
l 3 ^3
2l|=a <t>fe iff 21 (=a (<t>fe)^ for k=1>2- Then we aPP1/
definition 1.21 to infer the result 2lk <(> iff 21 k <t>^.
a a q
Finally we consider the tricky case when cj> is Vv i|/(u ). We
must distinguish between the cases when p is i and when p is
not i. The second case is simpler for then cj>^ is Vv ^(y ).
F 3 P 3 P
The induction hypothesis implies that
% •" a(*/ ) *<V iff * I" a(a/ ) *J<V <where a(ZV is an
arbitrary sequence of elements in the domain of 21) . Kence
^ H =>• i, / x i|>(i> ) for all & e 4 just in case
a(£/ ) P
2l(= a/t/ ) ^(p) f°r a11 ^ e i4. But then by 1.21 we have

RELATIONAL STRUCTURES
31
SI |=^ <J) iff SI |=^ $\. Lastly we consider the case where <J)
V
is Vy.ipCv.). Now $\ is Vi?.^(v.). By the induction
hypothesis SI k <Mv.) iff &h **(*>•) - Since v. does
not occur in <J> it also has no occurrences in if>(i;.). Now a
simple inductive proof shows that
»l=a *<V iff a^a(a./.,a./.) *<V ' Hence for all
'Z' €/ c7 ^
sequences a
Now again using the satisfaction definition
Sl|=a $ iff 21 |= $\m This completes the proof. D
Exercise 1.14. Construct a formula <f> with free occurrences
of v . such that for some structure SI and sequence a
0
SI k <(> and not SI k ♦ *.
a a Q
Lemma 1.26. Suppose t e Term(L) and t is free for v. in <f>.
Then SI |=ft <(>(£) iff SI |= ^ , <t>(^) y^re t*[a] = b.
Proof: Suppose the variables occurring in t are v. ,...,v. .
Since t is free for y . in <J) there are no free occurrences of
v. in <J) lying within the scope of a quantifier
Vv. (j=l,...,fe). However there may be bound occurrences of
the variables v. in <J>. If a straightforward induction
%i
on the length of <f> is used to establish the lemma such
bound occurrences are tiresome. The proof can be simplified
by eliminating those occurrences at the outset. Accordingly
we define <(>*(v.) to be the formula which results when each
bound occurrence of y. in <J)(v.) is replaced by a new
%i %
variable v not already occurring in <b(v .) or t. A con-
sequence of the hypothesis that t be free for v . in <J> is that
<J)*(£) is the formula obtained when each bound occurrence of
v. in <i>(t;) is replaced by v for no occurrences of v.
J J J
become bound as it were accidentally when t is put in place
of free occurrences of v.. A corollary of the preceding

32
RELATIONAL STRUCTURES
lemma is that
««■ .(*/.) *(V iff *N(v.) **(V
and
*t=a *<*> i££ *^a **<*>•
Hence it will suffice to show that
a ba **(*> i££ ^^acb/.) **(i;i) where *aca3 = h-
We use induction on the length of \p to show that for all sub-
formulae i|> of 6*(y.)
v
*ba *(*) i££ aHa(2>/.) ^(yi} where **Ca:i = *•
v
In the case where i|/ is atomic the result is an immediate
consequence of definition 1.21(i). If \p is of the form
-ty' or \p & i|> the property follows directly using the
induction hypothesis and the satisfaction definition. When \p
is of the form w i|/„(i> ) we know that v is not one of the
pyl p p
variables of t (since v will be bound in (j>*(v.)). The in-
P i
duction hypothesis implies that
«|=a V^v ,t) iff S|=a(2,/.) W1^ where *a[a] =b
for all sequences a.
Since v does not occur in t we have
P
*a[a] = **[a(e/ )] for all o e A.
r
(Intuitively, the interpretation of t is independent of that
of v .) So for all o e A
^aU/ ) *i(V'} iff *l=a(*/ ,*/.) WV
9| P P
where £ [a] = fr.
So by the satisfaction definition
ak #(*> i££ *l= arfc/ ^ *(tf*> for b = **Ca3-
This completes the proof.
Theorem 1.23 justifies the following abbreviations in
notation:
(I) I f £(i> . ,... ,v . ) £ TermL{%) wc write
% o vk

RELATIONAL STRUCTURES
33
t\at ,. . yai ] for t*lal.
v o ^n
(ii) If a e Sent (L(Sl)) and 2lj= a for some sequence
a
a then, since SI [= a for all sequences a, we
a
write % |= a.
(£££J If <J)(v. ,...,y. ) e Form(^(2l)) and
SI k <J)(y . ,. . ,y . ) then we write
a %o vk
Notice that (J)[a. ,..,a. ] is not a formula of the language.
%o vk
It is shorthand for 'interpret the variable v- as a.'. The
square brackets are not part of the language L(2D so even if
a. ,...,a. happen to be constants of the language it is not
%o %k
the case that (j)Ca. ,...,a. ] e Form L(Sl).
ok
Using vector notation we shall sometimes write a e A
and SI |= (j)[a] to denote that <t>(x) is satisfied in SI with
the element a- e A assigned to the variable x..
Exercise 1.15. Suppose SI,33 are structures of the same type
and h : SI -»■ S& is an isomorphism. If <|>(a? ,. . . 9x, ) e Form £(21)
and a ,...,afe e A show that
Sl|= *[a1,...,afc] iff 33 |= *Cfc(a1),. . . ,n(afc) ] .
Exercise 1.16. fa,) Suppose ((>(#) e Form MQ) where £ is the
set of rationals and Q= <£,<> . Show that if Q |= <j>[<?] for
some q e Q then O (= <H<7'3 for any q' e Q.
(b) Suppose (j)(# 1, . . . ,xh) e Form L(Q) with Q
as in (a). Show that if Q j= $lq1,. . . 9qh2 and for i,
j=l,...,ft, q ! < q'. just in case q^ < q- then
The following definitions, which depend on definitions
1.20 and 1.21,characterize some formulae of L according to
their semantic properties. We suppose that 21,33 are
realizations for L.
Definition 1.27.
(a) (J> e Form(L) is valid (or true) in 21 just in case

34
RELATIONAL STRUCTURES
21 K <f> for all sequences a. When <(> is valid in 21
a
we say 21 is a model for <(>.
Note that if a € Sent(L) then either a or -,a (but not
both) is valid in 21.
(b) <(> € Formal) is universally (or logically) valid if it
is valid in all realizations for Lm
(o) <(> € F02»m(£) is satisfiable if for some realization 39
for L and some sequence b in B 33 k <J>.
(dj <() € Form(L) is refutable if -kJ) is satisfiable.
Exercise 1.17. Suppose <(> € Form(L).
(a) Show that <J) is universally valid if and only if -><\> is
not satisfiable.
(2>j Show that <\>(x±,.. . ,a?n) is valid in 39 if and only if
Vx± Vx 4>(*1,. . . ,* ) is valid in 59 and that
<\>(x ,...,# ) is satisfiable in 39 if and only if
3x± 3xn<t>(x±,. >. yxn) is satisfiable in 39.
The rigorous definition of a true proposition in a
structure 21 is intended to capture the informal notion of
truth as used by mathematicians. Further, a universally
valid formula is one that is true on account of its logical
form alone irrespective of the meaning of the predicates,
functions, and constants in <(>. It is the counterpart, in a
first order language, of a tautology in a propositional
language. There are many similarities between the two notions,
tautologies and universally valid formulae, but there is one
very important difference. Given a formula ♦ in a
propositional language L (without quantifiers) there is a simple
procedure to determine whether (j> is a tautology. It is
sufficient to examine the truth table of <J>; <J> is a tautology
if and only if every assignment of truth values makes <\> true.
In general however there is no finite procedure to determine
of a given first order formula whether or not it is
universally valid. There are infinitely many non-isomorphic
realizations of a given first order language because the
domain may be of arbitrary cardinality. This contrasts with

RELATIONAL STRUCTURES
35
the finite number of distinct assignments of truth values
to the variables in a formula in a propositional language.
Although it is sometimes possible to establish that a given
formula is not valid in some interpretation (and hence that
it is not universally valid) it is not in general possible to
ascertain in a finite way that a given formula is valid in
every interpretation. Although the most obvious approach for
determining the validity of a given formula in every
situation (by considering every realization of the language of the
formula) clearly fails there could, in principle, be other
methods for establishing universal validity. However, a
theorem due to Church (1936) proves that the problem is
essentially undecidable, in the sense that no such general
method exists. It is immediate from the definitions that a
formula <|> is not satisfiable just in case the formula -.(j> is
universally valid and so in general the question of the
satisfiability of a given formula is also undecidable.
The following lemmas illustrate some cases where the
validity of a given formula is decidable.
Lemma 1.28. Given a formula $ there are only finitely many
non-isomorphic realizations of the language of <\> with a
domain of (finite) cardinality N.
Proof: Suppose R ,...,R are the distinct predicates
occurring in (j>, f ,...,f the function symbols, and
c ,...,c the constants. Suppose R. is a X(£)-ary predicate.
P \(i) v
There are N K J X(£)-tuples from an N-element domain and
(NX(i))
hence 2 distinct subsets of X(£)-tuples from an N-
(NX(i))
element domain; so there are 2 possible
interpretations for R.. Similarly the domain of the interpretation
of the u(j)-ary function symbol f . has N^^J' elements, the
totality of distinct y(j)-tuples over an tf-element domain.
There are N possible values for each argument and hence
N possible interpretations of the function symbol f ..
3
There are N possible interpretations for each constant
symbol c^.. Thus there are at most

36
RELATIONAL STRUCTURES
n 2^X(i)) x n *<*ua)> « mp
i=l Jsl possible
interpretations for the language of <J). D
The validity of a formula <\> with a particular form can
sometimes be determined by its validity in all domains of bounded
finite cardinality. By lemma 1.28 there are only finitely
many such (non-isomorphic) realizations for the language of
(J). Further, for any such realization, SI say, with finite
domain {s ,...,s,} there is a decision procedure to
determine whether or not 31 K <\>. In this case definition 1.21
a
(iv) becomes:
»Ha v*^ iff *|-a(e /)# and....and «ha( ,♦
1 Is K 1*
from which it is clear that % k <\> may be determined in a
finite number of steps. Thus the problem of whether such a
formula (j> is universally valid is decidable.
Lemrna 1.29. Suppose (j> e Form(L) contains only unary
predicate letters R,.,...,^ and no functions or constants. Then
(J) is universally valid if and only if (j> is valid in all
fa
domains with < 2 elements.
Proof: Suppose SI = <A9 #,...,#,> is a realization for the
language of (J) such that for some a ,...,a e A
H h -i<l>[a.,. . . ,a ]. We show that there is a realization
SI* with domain of at most 2 elements in which (j> is not
valid. First we define an equivalence relation on A:
a ~ a' iff for each i = l,...,fe a e R. just in case a' e i?..
It is clear that ~ is an equivalence relation on A. Let 4*
be the set of equivalence classes {fa]} of A induced by ~.

RELATIONAL STRUCTURES
37
There are at most 2 possible equivalence classes since for
each i=l,...,fe and any a either a e R. or a £ R -. For
i=l9...9k define #* = {[a] : a e R.}. This is well defined
since [a] = lb] implies that a and b belong to precisely
the same subsets R. of A. (We call such a relation ~ a con-
gruence relation with respect to R ,...,#,). Then
21* = < A*,/?*... ,#*> is a realization for the language of <t>.
A straightforward induction on the length of a formula
ty(x.,...,x) then shows that for any aA9...9a e A
51 |= *Ca1,...,a;7iJ iff 21* h *[ [a^ ,. . . ,[affl] ] .
So then 21* (= i*[[a1],...,[a ]]. Since the domain of 2I*
k n
has at most 2 elements we have established that if $ is
not valid in some structure then it is not valid in some
structure with at most 2 elements. The converse implication
is trivial. D
We now state a very simple lemma which will be used in
establishing the decidability of another class of formulae.
Lemma 1.30. Suppose that <\>(x ,. . . ,x ) e Form(LC$[)) where
(J>(:c ,. . . ,x ) is quantifier-free and that %*Q 21. Then for
any a±9...,an e A*
% H Ha± an] iff $* h Ha± anl.
Proof: By hypothesis 21* is a substructure of 81 and hence
a*9...9a e A n 4*. An induction on the length of
1 ■ n 91 91*
t e Term(LC&)) shows that tula± ,. . . yan~\ = t* la± ,. . . yan~\
(when the variables in t are among x ,...,x ). A second in- .
duction on the length of the (quantifier-free) formula (j> is
used to prove the lemma. The atomic case is an immediate
consequence of our preliminary result on terms. For <\> of
the form -»i|/ or (J) & (J) the result is a simple consequence of
definition 1.21 and the induction hypothesis. D

38
RELATIONAL STRUCTURES
Theorem 1.31. Suppose o e Sent(L) is of the form
3x 3x Vyij) where ty contains no quantifierst function
symbols or constants. If o is satisfiable then o is satis-
fiable in a domain with at most n elements.
Proof: Suppose R1,...,R,, are the predicate letters occurring
in ty and that 31 = < A, # ,... 9RJ is a realization such that
& |= a. Then for some a 9. . . 9a e A SI (= Vz/^Ea. ,. . . ,a ] .
But then
(*) for all t e A 31 h ^La±,.. . ,a ,?].
Let 4* = {a ,...,a } and for i=l,...,fe define
#* ='#. n (.4*) ( (R . is assumed to be a X(£)-ary predicate).
Let SI* = < A*,R*. . . 9Rp , the substructure of SI generated by
{a ,...,a }. Now by lemma 1.30 and (*) it follows that
for all t e A* SI* |= \pla±,. . . ,an ,tl.
So by definition 1.21 SI* h Vytyla±,. . . ,a ] whence by lemma
1.22 SI* [= a. This completes the proof that the <n element
structure SI* is a model for a. D
Corollary 1.32. If the sentence o is of the form
Vx .. . . Vx 3 y\p where \p contains no quantifiers., function
symbols or constants then a is universally valid iff o is
valid in all domains with at most n elements•
Proof: Apply theorem 1.31 to -iC □
The final definition in connection with the semantics of a
first order language is a generalization of definition 1.27(b),
Definition 1.33. If T u {$} c Form(L(S)) then T logically
implies (j> (alternatively <t> is a logical consequence of T)
r (= (j>, if whenever 31 is a realization of type 6 and a a
sequence in A such that SI |= ty for every \p e r then

RELATIONAL STRUCTURES
39
A logical consequence of a set of formulae r is a necessary
semantic consequence of r on account of its logical form
alone (and the formalization of truth in a given structure).
A logical consequence of the empty set, 0, is a universally
valid formula and in this case we write |= (J) (instead of
0 [= 4>). We write Si k T if SI k ♦ for all ty e r ^Form(L).
a a
Exercise 1.18, (a) Show that theorem 1.31 can be generalized
if we omit the restriction that a contains no constants;
i.e. show if a e Sent(L) is of the form 3x 3x V y.ty
where \p contains no quantifiers, no function symbols, but m
distinct constants, then a is satisfiable only if a is
satisfiable in a domain with at most rc+m elements.
(b) Show by an example that theorem 1.31 is no longer
true if we omit the restriction that a contain no function
symbols.
Exercise 1.19. Show that {(J)} |= \p if and only if h <\> + ^.
Exercise 1.20. Are the following formulae universally valid?
(a) Vy(Va?(F(a?) ■+ (F(j/) - G(a?))) + (H(a) + (VxFUh G(j/))))
(b) 3a: 3j/(((F(a?) * G(j/)) vVs H(a)) + (H(a?)& (F(aO + G(j/))))
Exercise 1.21. Suppose that for i=l,...,m+l $ .eSent(L)
is of the form Va;^. where iJj. is quantifier-free and
contains no function symbols or constants. Describe a procedure
to determine if (j> is a logical consequence of {(j> ,... ,$ }.
Exercise 1.22. (a) Suppose (J) £ Serc£ L(U) is universal
(that is, <f> is of the form Vxty where ty is quantifier free)
and that U*c U. Show that if U |= <|> then U* |= 4>.
(b) Suppose $ e Sent L(U) is existential (of the
form Ixty where ty is quantifier-free) and that U c ft*. Show
that if U (= <|> then U* [= 4>.

2
A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
In the previous chapter mathematical structures, the objects
of mathematical investigation, were considered. From a
rigorous unambiguous definition of a relational structure it
is possible to interpret familiar mathematical objects as
examples of this type of structure. We can express in a
formal first order language certain propositions that may or
may not be true in a given structure. To continue the
analysis of the mathematical study of structures we consider the
notion of a 'mathematical proof1. From a basic set of
axioms (defining a class of structures) the mathematician
makes logical deductions to produce theorems. In this
chapter a formal deduction system is defined which embraces
certain types of logical reasoning whereby some first order
formula is inferred from a given set of formulae as
hypotheses. The formalization is deceptively simple and even
apparently restrictive in the kinds of logical deduction
permitted in the system. The system is consistent in the strong
sense that a formula (j> derivable from a set r of hypotheses
is necessarily a logical consequence of r (theorem 2.6). The
converse result, that all logical consequences of r are also
derivable from r, is proved in Chapter 3. That the formal
system is complete in this sense is perhaps surprising; it
establishes that all intuitively 'logical1 arguments can be
derived from very few basic principles.
2.1. AXIOMS AND RULES FOR THE PREDICATE CALCULUS
There are finitely many axiom schemata and rules of
inference for the predicate calculus which fall naturally
into two groups. The first group, of propositional axioms
and rules, contains six different schemata and one rule. We
take as axioms:

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
41
Al. (J> + (♦"►*);
A2. (*-►(♦-* X)) + ((* + ♦) + (* + X));
A3. (-I* "►♦)-► ((-»♦ + -.1/0 + *);
A4a. <p & i|> ■* (J>; A4b. <|> & i|; ■* i|r,
AS. 4> -*•(♦-► 4> & ♦);
for all (J), i|/, x € Form(L). The propositional rule of
inference is :
Rl. Modus ponens: i|/ is an immediate consequence of
(J>, <|> + i|/ (for any (J), ^ e Fo2»m(L)).
The second group of schemata and second rule explicitly
involve the universal quantifier. For all <|>, \p e Form(L)
A6. Va?<|>(a?) -»■ <(>(£) where t is a term free for x in <|>;
A7. Vx(<\> + i|0 + (<|> -»■ va?i|0 where <j> contains no free
occurrences of x
are axioms. (In A6 <J> may or may not contain free occurrences
of x and may contain other free variables.) The quantifier
rule is
R2. Generalization: Vx<\> is an immediate consequence
of <|> (where <j> e Form(L) and x is any variable).
Deductions are made from the axioms using the rules of
inference. More formally, we have
Definition 2.1. Suppose Z u {<£} Q Form(L). A derivation
of (J) from the (possibly empty) set Z is a finite sequence
<!>„,...,<j> of formulae such that <J> = <J> and for each i ^ n
either (i) <j>. is an axiom
or (ii) (jk e Z
or (iii) for some j 9k < i <j). is an immediate consequence
of <|>.,(|>7, according to Rl
or (iv) for some j < i ^• is an immediate consequence
of <f> . according to R2 and the quantified
variable x does not occur free in Z.

42 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
When there is a derivation of (j> from Z and Z* c Form(L) is
any set such that Z Q Z* then we say (j> is derivable from Z*
and write Z* f* (j>. (J) is a theorem of the predicate calculus
when there is a derivation of <\> from the empty set, and in
this case we write h (j> (instead of 0 h $). If Z* |- (j> then (j>
is a theorem of Z*.
Axioms are the starting point for derivations (2.1(i)) and,
as such, we require amongst other things that they be
universally valid. The restrictions on the term t in A6
and on the variable x in A7 are designed to preclude
precisely those instances of the schemata that are not always
valid. They are perhaps most easily understood with specific
examples in mind. The term y is not free for x in the formula
3y P(a;»z/) since the free occurrence of x lies within the scope of
the quantifier Vz/ (cf. definition 1.17). Now we consider the
formula:
V* *y?(x9y) + 3yP(y9y).
In the structure ft = < N9<5 with the set of natural numbers
as domain and < as the binary relation corresponding to P
the sentence VxlyP(x,y) is valid since it states: 'For every
natural number n there is a larger natural number m»;
however 3yP(y9y)is manifestly false since it asserts that there
is a natural number larger than itself.
Suppose now we consider the following unrestricted
instance of A7:
Va?(P(a?) + Q(aO) + (PU) + VarQU)).
and the interpretation ft= < N,P9Q> where N is the set of
natural numbers, P is the unary relation !- is divisible by
4' and Q »- is even1. Then certainly ft (= va;( P(#) + Q(aO).
However the formula P(#) + VxQ(x) has a free variable x and
ft (= (P(a?)->Va:Q(a:))[n] will hold only when ft (= P[n] does not
hold since we do not have ft (= V#Q(a;). Hence if rc is divisible
by 4 then ft (= P[rc] and so not ft (= (P(a?)-»-Va?Q(a?) )[n]; we can
conclude that Vx(P(x)+Q(x) ) + (P (:c)+V;cQ(:c)) is not universally

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
43
valid.
The restriction on the use of R2 in derivations
(2.1(iv)) is also motivated by semantic considerations. The
aim here is that a formula (J) which is derivable from Z should
be a logical consequence of Z. If we suppose that the set Z
contains the single formula x « 0 and consider the
'derivation1 of Vxx = 0 from Z : x = 0, Vxx = 0, not
satisfying the restriction of 2.1(iv), then in the interpretation
<tf,=,o> x = 0 is satisfied with x interpreted as o but
Vxx = 0 is false.
By inspecting definition 2.1 it can be seen that if
Z |- (j> then there is some minimal, finite Z c z such that
((> ,...,((> , say, is a derivation of (j> from Z ; namely,
Z„ consists of those formulae <\>. in the derivation which do
not occur as axioms ((i)) or as consequences of the rules
((iii),(iv)). The restriction of the use of R2 need only
apply to that minimal Z . Hence, for instance, if x does
not occur free in <\> then
(*(j/), ♦(*)} h V*(i|Ka?) + 4>(j/)) is valid;
the following is a derivation of Vx(ty(x) + 4>(z/)) from {$(y)}:
4>(2/)) (instance of Al) ,
1
2
3 :
4
<\>(y) ■* (*(a?) ^
*(J/)
: *(-a?) -»■ <|>(2/)
: Va:(i|;(a:) + 4>(j/))
(from 4>1,4>2 by Rl) ,
(from <|> by R2) .
So the free occurrence of x in i|;( a?) in {<\>(y) ,i|;(a?)} is not
relevant in the particular derivation we have above.
Since the set Form(L) is infinite there are infinitely
many instances of each axiom schema. However the infinite
set of axioms is recursive; that is, there is a decision
A definition of 'recursive1 may be found in any text
book of recursive function theory, e.g. Rogers(1967).

44 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
procedure to determine whether or not a given (j> e Form(L) is
an instance of Al-7. Similarly, there is a finite procedure
to determine of a given finite sequence of formulae
<t> ,...,((> whether it constitutes a derivation of (j> from a
recursive set I Q Form(L). For each i=l,...,n we simply
determine whether or not <\>. is an axiom, (j>. is a member of
'Z' 'Z'
Z, (j). follows from (j>.., (j>, by Rl for some j,fe in the finite
set {l,. . . ,i-'l} , or (J), follows from <\>. by R2 for some j <i
and the quantified variable does not occur free in those
fprmulae of Z occurring in {$,... ,4>.}.
If §> ty9 X are well formed formulae in a propositional
language, built up from statement letters (propositional
variables) using the propositional connectives &, -• then
the formulae corresponding to the forms Al - A5 are
tautologies. It is useful to classify the formulae of a first
order language L which have the form of a propositional
tautology.
Definition 2.2. $ e Form(L) is an instance of a tautology
if there is a tautology <\>r with distinct statement letters
?.,...,?„ and (J).,...,(J) e Form(L) such that <t> results from
1 n 1 Yl
(J)r when for each i = l,...,n each occurrence of P. is replaced
by 4k.
Exercise 2.1. Which of the following formulae are instances
of tautologies?
(a) Vx<i>(x) + ( 3y\\)(y) + Va?<KaO),
(b) (<t>(x,y) & '4>(x,y)) + (<J>(*,#) v x(*)),
(c) <t>(x) ■* 3a?<|>(a?).
Lemma 2.3. tfaefr instance of a tautology is universally
valid.
Proof: Suppose <\> is an instance of a tautology.
If 51 is a realization for L and a a sequence in A

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
45
then 21 |=a #! & ^2 i££ * l=a *i and * h* ^2
and 51 |=a -♦ iff not 51 |=a ♦ (definition 1.21).
A comparison with the truth tables for & and -i
p
T
T
F
F
Q
T
F
T
F
P&Q
T
F 1
F
F 1
p IP
T 1 F
F\ T
shows that the definition of (= for the propositional
connectives mimics the definition of truth value. More
precisely, suppose P ,...9P are the statement letters occurring
in the tautology <J>' from which <|> results by the substitution
of <|>. for P.; if v is the assignment of truth values to
propositional formulae generated by the definition:
v(P.) = T if and only if 21 K 4> •» then for all subformulae
ty of (j) built up from {((>.,... ,(() } using &, ~" 21 K ^ if and
only if v(\\)')
Since <J>f is a tautology (i.e. v(<t>')
for all assignments of truth values v) then 21 k <1> for all
a
realizations 21 and all sequences a. D
Alternative sets of schemata yielding as axioms
instances of tautologies could be used in place of Al - 5. One
aim in the formalization is to generate as theorems all
universally valid formulae. So, as a corollary to lemma 2.3
we wish all instances of tautologies to be provable. A way
to ensure that this is the case is to take as axioms in place
of those generated by the schemata Al - 5, all instances of
tautologies. The set of all tautologies is, like the set of
instances of Al - 5, a recursive set since the truth table
method can be used to determine whether a given formula is
an instance of a tautology. However, as a corollary to the
completeness theorem for the propositional calculus'with, as
axioms, all instances of Al - 5 and modus ponens as the only
rule we have the following lemma:

46 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
Lemma 2,4. Each instance of a tautology <t> is a theorem of
the predicate calculus. Moreover there is a derivation
$*$••• 9$ of (j> (from the empty set) such that for i < n
either (i) (J), is an axiom of the form Al - 5
or (ii) (J), is an immediate consequence of (J>.,(1>7, for
some j,fc < i by Rl.
Proof: Suppose (J) is an instance of a tautology resulting
from the propositional tautology (j)f when i|/ ,.. . , ty e Form(L)
are substituted for the distinct statement letters
P ,...,? in (J)f. The completeness theorem for the
propositional calculus implies that there is a derivation
(j>',.. . , (J>f of (j>' in the propositional calculus; i.e.
(j>' = (j>' and for each i < k either (j> C is a propositional
instance of Al - 5 or for some j*,fc < -£, (j> C follows from
<f>'-><l>k by modus ponens. Let ^ e Form(L) be the result of
replacing for s = l,...,m each occurrence of P in (J) C by \\)
s is s
and each statement letter Q f P ,...,P by an arbitrary
(J), e Form(L) (for £ = l, ,rc). Then <!>„,... ,<!> will be a
iqi ± n
derivation of (j> in the required form. □
Exercise 2.2. Suppose that <\> e Form(L) is derivable and
that there is a derivation <|>1,...,<|> of (J) of the form given
in Lemma 2.4. Show that <t> is an instance of a tautology.
In a system with -»,+ as primitive connectives, Al-3
alone, together with modus ponens, are sufficient to generate
all tautologies (see e.g. Mendelson (1964),page 36). However
with -i,& as primitive and P ■*• Q defined by -*(P & -*Q) the
additional axioms A4,5 are necessary. (The independence of
A4,5 from Al-3 can be demonstrated using a 3-valued
interpretation). The completeness of our system can be proved
using the Kalmar method (as in Mendelson(1964),page 36 with &
replacing + in the induction step of lemma 1.12). An
alternative proof will be given at the end of Chapter 3.

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 47
It is precisely the complete character of the schemata
Al - 5 together with Rl for generating all instances of
tautologies that is important. Any (recursive) set of
schemata which together with the rule Rl is sufficient to
generate as theorems all instances of tautologies could be
used in place of Al - 5. Throughout the remainder of this
book we will assume the completeness of the set Al - 5 (in
the sense described above). However it will be clear when
a given proof rests on this assumption. The completeness
proof for the predicate calculus given in the following
chapter can be adapted to provide a proof of the
completeness of the schemata Al - 5 for the propositional calculus
(without, of course, assuming that all tautologies are
derivable). This method is outlined in theorem 3.28.
It might at first sight seem possible that all
universally valid formulae are instances of tautologies. That this
is not the case is an immediate corollary of the following
lemma.
Lemma 2.5. Each instance of A6 and A7 is universally valid.
Proof: (i) Let (J) e Form(L) be of the form Vxty(x) -*■ ty(t)
where t is a term free for x in ty. Suppose 21 is a realization
for L and a a sequence of elements of the domain of 21.
By lemma 1.22(b) 31 |= 4> iff when 21 |=a Vxty(x) then
21 |= ty(t). So suppose % k Vxty(x). Then for all elements
a a
b e A 21 K/w \ i|Ka?) where a; is y.. In particular
SI ra/w ) ty(x) when b = t [a]. Then by lemma 1.26
i
& (= i|>(£). This implies the universal validity of 4>.
(ii) Suppose <|> e Form(L) is of the form
Vx(\\) + x) "*" (* "*" Va;X) where there are no free occurrences
of x in i|/. Suppose 21 |= V#(^ + x) where 21 is some
realization for L. Then for all b e A 21 K,w n *l> ■* X (assuming
a(£/^)
x is v.). Hence if 21 j= -, , N ^ then 21 K/w NX • Bv theorem
v ' a(&/ .) T ' aCZ?/^)^
1.23 since x is not free in i|/ either 21 K/w \ ^ f°r all
2? e A or it is not the case that 21 K ^. Hence

48 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
21 f=a ty implies that 21 |=a(w ) X for all b e A.
Then
21 Ya ^ "*" VXX- So for any realization 21 of L and any
sequence a, 21 |= <\>. D
It is clear that an instance of A6 or A7 is not an
instance of a tautology and yet by lemma 2.5 is universally
valid. Thus in order to construct a formal system in which
all universally valid formulae may be derivable it is
necessary to have as axioms formulae which are not instances of
tautologies or rules other than modus ponens (or both). What
is perhaps surprising is that the addition of only two
schemata A6 and A7 together with the rule of generalization
is sufficient to generate all universally valid formulae.
2.2. CONSISTENCY.
The following theorem demonstrates that the system is
consistent with the semantic concept of logical consequence.
It is sometimes known as the soundness theorem.
Theorem 2.6. Suppose {(J)} u Z Q Form(L). If I \- (j> then
Proof: We suppose Z f- <|> for some minimal Z c Z and use
induction on the length of the derivation <j>„,... ,<\> of <\>
from E to show that for each i < n Z |= <\>.. From lemmas
2.3 and 2.5 it follows that when <\>. is an instance of Al - 7
then [= (j>.. So in this case clearly Z \- §.. Trivially if
(J>. e Z0 then Z |= (J).. Now suppose that for all g < i
Z. |= (J), and that <j>. follows from <\> . and $ . = $ . + $. by
OJ i* 3 ^ ^2^1^
Rl where j ,j < •£. Suppose further that 21 is a realization
for L such that 21 k 2 . By the induction hypothesis
21 k 4>. and 21 k (f>. . Then by lemma 1.22 21 k 4>..
,aj1 'a tj2 ' ' a -z.
So by definition 1.33 Z. 1= (j>.. Finally suppose (j>. is Vi?,(|>.
0 1' I* K Q
and that it follows from (J>. by R2 where j < i. By definition
3
2.1 (iv) and the minimality of Z , v, does not occur free in
Z . Then for any realization 21 for L and any sequence a in A

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
49
31 |=a ZQ implies 31 l=a(£/ ) z0 for a11 h e A. Hence by the
induction hypothesis (since j < •£) if 21 |= Z then
51 K/t,/ n <1> for all b e A. Hence 21 k £n implies
21 k Vy,(j>. and so Z (= $.. To complete the proof note
that since ZA c z, if 21 k Z then 31 k EA. Hence Z |= <fr. □
0 d a 0
The method of proof used in theorem 2.6, induction on the
length of a derivation, is, like the type of induction first
used in theorem 1.23, characteristic of many proofs of
theorems about the formal system. A derivation is necessarily
of finite length and furthermore each formula in the
derivation arises in one of only four ways, as an axiom, as a member
of Z, or as a consequence of Rl or R2. Thus for the
induction step all that is necessary is to check that the
hypothesis still holds for a formula occurring in the derivation
which has arisen by one of these four methods. This method
of proof can be used to yield theorems concerning derivable
formulae or derivations in any formal system in which the
number of axiom schemata and rules of inference is finite.
(If there are infinitely many schemata given in a uniform
manner then again the induction method is applicable.)
Definition 2.7. A (possibly empty) Z c Form(L) is
consistent if for no (J) e Form(L) is it the case that Z |- $
and Z |- -i (J). Z is inconsistent if Z is not consistent.
Corollary 2.8. The empty set is consistent.
Proof: Suppose there is some <J> e Form(L) such that |- <\> and
|- -i (J>. Then by theorem 2.6 f (J) and [= -i <\> which is clearly
impossible because it contradicts definition 1.21. □
Definition 2.9. A theory T in L is a set of sentences of L
which is deductively closed, i.e. for each a e Sent(L)
T y a if and only if a e T.

50
A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
Lemma 2.10. Z ^ Form(L) is inconsistent if and only if for
each <f> e Form(L) Z |- (J).
Proof: One way round the implication is obvious because of
definition 2.7. Conversely suppose that Z is inconsistent.
Then for some (J) e Form(L) Z |- (f) and Z |—.((>. For any
\\> e Form(L) the formula (j> -»-(-i(|> ■*■ ^) is an instance of a
tautology and hence by lemma 2.4 Z f- (j> + (-i(|> + ^) . Two uses
of the rule Rl yield Z |- i|/ as required. O
Corollary 2.11. A theory T in L is consistent iff
T f Sent(L).
The following theorem demonstrates that there is a
derived rule of the formal system which acts as a kind of
converse to modus ponens. Use of this derived rule often
shortens considerably formal derivations in the system
(although, of course, it does not add to the power of the system).
Theorem 2.12. The Deduction Theorem.
If Z u {<fr,i|;} QForm(L) and Z u U} f- ♦ then
Z \- 4> + \\).
Proof: If Z u {(J)} \- i|/ then either Z [ \\) or whenever Z |- i|/
for some Z c Z u {<\>} then <\> e Z . In the first case, since
Z |- ty + ((|> + i|0 (by Al) it follows by modus ponens that
Z f- <\> + ty. In the second case by induction on the length of
the derivation i^,...,^ of \\> from a minimal
Z u {(j>} c z u {(j>} we show that for each i < rc Z \- 4> + ty..
If ty. is an axiom or in Z. then since \\>. + (<f) + i|/.) is an
Is U Is Is
instance of Al and Z. |- ty. then Z_ |- (j> + \|;.. If i|/. is itself
0 Is U Is Is
(j) then § -*■ ty. is an instance of a tautology and hence
provable by lemma 2.4. Now suppose i|/. follows from \j;. and
Is J
\K = i);. •* \j;. by Rl when j9k < i. By the induction hypothesis
^ J 'Z'
£n I" $ "*" * • and zn h 4> ■*■(*•■»■ *•). The formula
U Q U 3 ^
((J) + (\|;. + i|/.)) ■* ((<!> + ^.) ■* ($ + ^.)) is an instance of A2
3 Is J ^
and so two applications of Rl yield Z_ \ § + ty.. Finally
U Is
suppose ty. is Varip. where j < i and a; is not free in
i" 3

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
51
Z u {(j>} (from definition 2.1). By the induction hypothesis
EQ h <t> -»■ *?-; then R2 (x not free in ZQ) yields
Z \- Va;((j> ■* i|/.). Then using A7 we obtain Z |- <|> ■* VariJ;.
u j u j
which is Z |- <\> + ty.. This completes the proof. □
Because of the restrictions on the use of the rule R2
in a derivation of i|; from Z u {(j)} it is possible to 'carry
over1 (J) from left to right across the symbol (- (as proved
in theorem 2.12). Some systems allow unrestricted use of
the generalization rule in derivations. Then the statement
of both the deduction theorem and theorem 2.6 must be
modified. These modifications are cumbersome in comparison
with the restriction on R2 in derivations. Another reason
for preferring the restricted rule of generalization has been
given on page 43.
Exercise 2.3. (a) Show that {<t>(x ,. . . 9x )} is consistent
iff {3x 3x (J)(:c ,. . . >x )} is consistent.
(b) Show that Z Q Form(L) is consistent
iff every finite subset of Z is consistent.
Exercise 2.4. Show that if <\> is built up from the formulae
<t>± ,. . . ,((>. using only the propositional connectives and
for £ = i,...,k |- <t>. <* \\>. then |- <t> ■» i|/ where \\> results when ty-
is substituted for (j>. in <t>.
Exercise 2.5. The independence of axioms A6,7.
Let *, 'be the functions from Form(L)to itself generated by:
(i) (J)* = (J)r = (J) if (j> is atomic;
(ii) (-4>)* = -*<!>* ),(-.*)' = -i((J>');
(iii) (^ & <|>2)* = <|>* & **9{<b1 & *2)r = *J & *£;
(iv) (v:c<|>)* = Vz/(j)*(z/) where z/ consists of those variables
occurring free in <\>*,
( vx<J)) ' = <t>'(c) where c is a (fixed) new constant
substituted for the free

52 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
occurrences of x in <\>'.
Prove that
(a) if <j> is derivable using Al-6, Rl, R2 then \-$*;
(b) if 4> is derivable using Al-5, A7, Rl, R2 then |-<f>'.
By considering instances $ 9\\> such that [-(J), \-\\> and (f)*,^' are
not universally valid show that
(c) A7 is independent of Al-6, Rl, R2
(d) A6 is independent of Al-5, A7, Rl, R2.
2.3. LANGUAGE AND METALANGUAGE.
In this chapter two essentially different types of
theorem occur in the text. For one type, theorems in the
formal system, there is a very precise definition (2.1) and
a symbolic notation ! f-! so that ! |- (J>! means ! <t> is derivable
from a precisely defined set of axioms and two rules of
inference, modus ponens and generalization1. On the other
hand some theorems are prefaced by 'Theorem1 (followed by a
number), stated in English and proved using the kind of
reasoning ordinarily accepted by the mathematician. Such
theorems are sometimes called metatheorems in order to
distinguish them from the formal theorems. For example,
consider the deduction theorem, 2.12. The statement of the
theorem involves quantification over sets of formulae;
formulae and derivations in the system become objects of
discourse. The proof of theorem 2.12 is accomplished using the
principle of induction. This kind of reasoning is applicable
because a derivation in the system is of finite length and
the dependence of some stage in the proof on previous stages
is clearly defined. The principle is justified on the basis
of our intuitive understanding of the natural numbers, the
working mathematician in general accepts the method of
induction as a valid form of reasoning. Although the principle
of induction has no immediate analogue in the formal system
other kinds of argument have direct counterparts in the
system and yet are justified for distinctly different reasons.
For example, in corollary 2.8 reductio ad absurdum is used.

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 53
From the assumption that the corollary does not hold a
contradiction results. So the corollary must hold. The formal
analogue may be stated as follows: if -i(J> |- \\> and
-i(J> |--ii|/ then [- <\>. This is a derived rule of the formal
system. By the deduction theorem if -kj> |- i|/ and -i(J> ]—1\\> then
[--i<j> + \\> and f- -i(j> + -ii|/ . Then by A3 and modus ponens |- <|>.
The justification of this derived rule in the system depends
on the axioms and rules of the system and not upon their
intended interpretation.
It is important to distinguish between the two distinct
languages, the formal first order language L and the
metalanguage in which the formal system can be analysed. We have
chosen English as the metalanguage although in principle we
could equally well have adopted a formalized metalanguage.
Similarly although we have not analysed the valid forms of
reasoning in the metatheory it would have been possible to
formalize the permitted forms of inference (such as induction
and reductio ad absurdum). However such a formalization on
the metalevel provides no justification for the metatheory.
Indeed a meta-meta language is necessary to 'translate1 such
a metalanguage into one understood by the reader. The use of
English as a metalanguage accentuates the distinction between
the two levels, the formal system itself and the informal
system in which the formal system is analysed, and does not
require translation. The most important differences are
emphasized in the following table:
Informal level Formal level
(for analysis of the formal (for analysis within the
system.) formal system.)
English First order language
Theorem |-
Proof Derivation
Rules of proof accepted by Axioms Al-7
mathematicians Rules Rl, R2

54 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
2.4. FURTHER METATHEORY
Some proper subsets of Form(L) play significant roles
in both proof-theoretic and. model-theoretic analysis. We
shall be concerned with sets S with the following property:
(*) There is a map *: Form(L) ■* S such that |- <j> iff \.$*
or with the stronger property
(**) There is a map **: Form(L) + S such that
Proper subsets with the property (**) are particularly
useful; for any <|> e Form(L) there is a (j>** e S which is proof-
theoretically and (by theorem 2.6) semantically equivalent
to <|>. Hence a property of Form(L) relating to the proof
theory of the formal system or to the model theory has only
to be established for S in order for it to hold for all
Form(L). Sets with the property (*) are less important in
the metatheory but nevertheless are sometimes useful in
considerations of the theorems of the system.
Lemma 2.13. Sent(L) has the property (*). For any
$(x 9...9xn) e Form(L)
h 4>(a?1,...,a?n) iff |- Va?1 V*n 4>(x± ,. . . ,a?n)
Proof: If |- (J) then by n applications of R2 it 'follows that
Conversely if [■ Vx Vx <j> then, since x. is free for x.
in any \|; e Form(L) , by A6 and Rl |- <J>. D
Exercise 2.4. Show that there exists <\> e Form(L) such that
it is not the case that I- <t> ^ Va; Vx ((>.
Definition 2.14. (j) e Form(L) is said to be in prenex normal
form if it is of the form QAxA Q x ty where for £=l,...,rc
J Minn '
Q. is a quantifier V or 3 and ij; contains no quantifiers.
PNF(L) is the subset of Form(L) consisting of all formulae in
prenex normal form.

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 55
PNF(L) has the strong property (**) and moreover given any
(j> e Form(L) there is an effective method to determine a
(J)** e PNF(L) provably equivalent to (j>.
Theorem 2.15. For each (j> e Form(L) there is a (j>** e PNF(L)
such that f- <(> <* <(>**.
Proof: The following formulae are all derivable;
(i) ->Vx\\) «► 3a? ii|/
(ii) -»3a?\|; *> Va? -. i|/
(iii) Va;*^ & <|>2 ** Va?((j> & (j> ) where x is not free in
(iv) (J> & Va:(J)2 ** Va?((j> & <(> ) where x is not free in
(v) Sa?^ & (j> <* 3a?((j> & (J> ) where a? is not free in
(vi) (J> & 3x<t>7 <* SarCcf). & 4>2) where a? is not free in
♦i'
By definition 3x-*\\) is -,Va?-,-,\J;. i|i.#-i-ti|i is an instance of a
tautology. Hence Vxty |—• —• \|^ using A6, Al and Rl. Then by R2
Vxty |- Vx-,-)p. A similar argument shows that Va;-,-,^ |- Vx\\>.
Then by the deduction theorem and the definition of <* and A5
we have |- -» Vxty +► 3a? -ii|/. Similarly |- -i3a?i|/ ^ Va?-ii|/.
Va?<|> & (J>2 f- (J>1 using A4 and A6. Also Va?<|> & <j> |- <j>
So using A5 and R2 to generalize over a: (by hypothesis not
free in Va?<|> & (j> ) we obtain Va?4> & <j> |- Va?((j> & (j>2) .
Conversely, Va?((j> & (j> ) |- <(> & <J) and hence
Var(<[)1 & 4>2) |- (1>1 and Va?(4> & 4> ) |- 4> . Using R2 to
generalize over a? and again A5 Va?((j> & (j> ) f- Va?(j> & (J) . The
deduction theorem and the tautology (4+B) + ((B+A) + (4<*B))
imply that [- Va?(<fr & <fr2) <* Va?<fr & <fr2. Since U&B) <* (B&X)
is a tautology we can readily show that
|- (f> & VaT(j> <* Va?((j> & <f> ) if x is not free in <J) . To prove
(v) we show that, assuming a; is not free in (j>2, both
-i3*(<|> & *2) |- -. ( 3*<|> & ^ ) and

'56 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
-»( 3a;(j)1 & (j> ) |—i 3x(<\> & (J>2). Then we use the deduction
theorem and the tautology (-i4 <*-iB) + (A**B) to deduce
h 3x$1 & (f>2 «*• 3a;((l)1 & (f>2) . By (ii)
-i3a;(<(> & (j> ) |- Va?-i(<|>1 & (J>9). Using the tautologies
->(4&B) <* (-»i4 v-,B) and (-1,4 v-,B) <* (B +-i4) we get
-liarC^ & <|>2) |- Va?(<|>2 -►-i^). Then by A7, (ii) above and
the second tautology -.3 x((j> & <|> ) |- -,3a;(j> v -,<|> . So
-^(^ & *2) (- -,( 3a:(J)l & <|>2). -,3*(|>1 & *2 h -»3x((l)1 & *2)
is proved in a similar way. (vi) is an almost immediate
corollary of (v) just as (iv) follows from (iii).
Now suppose (j> is written in its unabbreviated form with
only the connectives and quantifier, -1, &, and V. Using (i),
(ii), (iii), or (iv) in 2.15 quantifiers can be 'pulled out1
from right to left. When the universal quantifier is pulled
across -1 it is replaced by an existential quantifier. For
this reason we include (ii) , (v), and (vi) to show how to
deal with the existential as well as the universal quantifier.
We illustrate the procedure by an example thus showing how
to obtain (j>** e PNF(L) given (j> e Form(L). Suppose $ is
(-»Vx?(x9y) & Q(a?)) & -1 ( VsR(s) & S(w))
where P, Q, R, and S are predicates of L. By (i)
\- -iVx?(x,y) «► lx^P(x9y).
We cannot apply (v) directly to the formula 3x -*P (x9y) & Q(x)
because x is free in Q. However it is straightforward to
show that f- 3x\\)(x) ** 3ui|/(iO where u is a variable not
occurring in i|/ (cf. the semantic parallel in lemma 1.25). So
now by (v) we have |- 3 a: -,P (x9y) & Q(aO <* 3u(-iP(u,z/) & Q(ar)).
By (iii) and (i) |- -1 ( VsR(s) & S(w)) <* 3s-t(R(s) & S(w)).
So by (v) \- 4> <* 3M3a(-iP(u,y) & QU) &-i(R(s) & S (w))) . D
Exercise 2.6. Show that
(a) \- ( Va;(j)(a;) + \|0 <* 3#((|>(tf) ^ ^) if a; is not free in i|/,

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 57
(b) \- ( 3x<i>(x) + \\)) ** Vx(<\>(x) + i|/) if x is not free in i|/,
(c) \- (ty + Va?<|>(aO) <* Va?(i|; + <|>(a?)) if a? is not free in i|/,
(d) |- (i|/ + 3a?<|>(a?)) <* 3a?(i|/ + <!>(*)) if a? is not free in i|/,
(e) |- ( Vx<t>(x) v i|/) -b. Va:((j>(a;) v i|/) if a? is not free in i|/,
(f) |- ( 3x<t>(x) v \|;) <* 3ar((()(a;) v \|/) if a; is not free in i|/.
Exercise 2.7. Find prenex normal forms equivalent to the
following formulae:
(a) ( Vx?(x9y) + Q(a)) v 3s(R(s) + Vz/S (^ ,s))
(b) -,( 3x?(x) & Vy(P(y) v Q(z/,s)) + 3wR(i/,3 ,w) ) .
Exercise 2.8. Show that theorem 2.15 may be strengthened by
replacing PNF(L) with PNF*(L) where PNF*(L) contains
precisely those formulae of the form Q.x ®nxn^ wliere * is t*ie
disjunction of conjunctions of the form p &....& p- where
for each i=l,...,fe p. is either an atomic formula or the
negation of an atomic formula.
Exercise 2.9. Show that f- <|>(£) -*■ 3a?4>(a?:) if t is free for
x in (f)(a?).
Exercise 2.10. Show that the following are derived rules
of the system:
(a) If r, (J>(c) h ^ where the constant c does not
occur in r, i|/ or <|>(ay)
then r, 3a?<|>(a?) [• i|/ ;
(b) If r |- c()(c) where the constant c does not
occur in T, <|>(a?)
then r |- Va?<fr(aO.
Exercise 2.11. Show that |- 3xVy<t>(x9y) + Vz/ 3x$(x9y)
but that in general it is not the case that
|- Vz/ 3x$(x9y) ■* 3a: Vz/(J)(a;,z/).
Exercise 2.12. The Principle of Duality. Suppose
(j> e Form(L) contains no function symbols and only the
connectives v, &,-», V, 3 . Let <j> be the formula which results

58 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
from (J> when v is replaced by &, & by v, v by 3 and 3 by V .
Suppose 21 - <A,#,...,R^9c.,... 9o^ is a realization for the
language of <f>. Let 21 = < A9R ,...,#, 9c 1,... 9qi) where for
i«lf...,*,*? = AX(i) - Ri.
Show that (a) 21 (= (f>[a] iff 2iD |= -. 4>Dlal
and (b) I- (() iff |- -, ^
2.5. FIRST ORDER THEORIES WITH EQUALITY.
The examples of relational structures given in Chapter
1 show that the appropriate first order language for a
mathematical structure frequently contains a binary predicate
corresponding to the equality relation. The most natural
first order languages used by working mathematicians for
groups, rings, fields, arithmetic, and so on have the
predicate = and functions instead of predicates representing
functions. The intention is that = should be interpreted
as identity in all realizations of the languages. For the
remainder of this section we consider a first order language
with a distinguished binary predicate =. The language will
be denoted by L„ and we write t. - t. instead of = (t-9t.)
in order to follow standard mathematical notation more
closely. When the language L„ is used the set of axioms of the
corresponding formal system is extended to include the
following:
A8. Vx(x = x);
A9. x = y -+(<$>(x9x) + <J)(:c,2/)) for every atomic formula <j>
such that $(x9y) is obtained from <\>(x9x) by replacing x with
y in some (not necessarily all) free occurrences of x in
<j) (x9x).
Note that we assume neither that $ has any free
occurrences of x nor that x is the only free variable of <\>. A8 is
a single new axiom but the schema A9 generates an infinite set
of axioms if the language L„ contains infinitely many non-
logical symbols.. It is immediately obvious that in any
realization 21 for L„ in which = is interpreted by equality the new
axioms are valid and hence consistent. Unfortunately the
converse, that the interpretation of = in any model of axioms

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
59
Al - 9 is equality, is false. However, as a corollary to the
following lemma, it is the case that in a model of Al - 9 the
interpretation of = is an equivalence relation on the domain
of the structure.
If <J> is derivable from Z in a language L£ with equality
(i.e. definition 2.1 with (i) meaning !4 is an axiom of the
kind Al-91) then we write Z \~E <|>. If 31 is a realization for
L„ we assume that the binary relation E representing *■■ is
such that A8 and each instance of A9 are valid in 21.
Lemma 2.16. (a) \- x = y -*■ y = x
(b) [Ex=y^{y-z^x-z).
Proof: (a) Take <b(x9x) to be x = x and <t>(x9y) to be y = x
in A9. Then |-■ x = y +(x = x -*■ y = x) Now use the
tautology A +((B +(A + C)) + (B+C)) and \~E x = x to obtain
\-E x = y + y = x.
(b) Take <b(y 9y) to be y = z and $(y yx) to be x = z
and use A9 with x and y interchanged to get
\-„ y = x +(y = z + x = z). By (i) and the tautology
U+B) + ((B+£) + U+£)) we obtain V- x = y + (z/ = s ■* a? = s) &
Corollary 2.17. Suppose % is a realization for L„. Then E,
ti
the relation representing =, is an equivalence relation on
A.
Proof: E is reflexive since % |= x = x. The symmetry and
transitivity of E are immediate consequences of lemma 2.16
(a) and (b) respectively. D
Although the number of instances of A9 may be finite
(when the number of nonlogical symbols is finite and we
identify formulae of the same form differing only in the free
variables) there are infinitely many theorems with the same
form as A9.
Theorem 2.18. For all $ e Form(L„)
YE x = y -+(<t>(x9x) -*■ <\>(x9y)) (in the notation of A9) where in
$(x,y) each substituted occurrence of y is free.

60 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
Proof: (by induction on the length of <k) . I £ <(> is atomic
then x = y + (<\>(x9x) + <t>(x9y)) is an axiom. Now suppose ((> is
of the form -nty. Then by the induction hypothesis (with x9y
interchanged) \- y = x + (ty(x9y) + \\)(x,x)). The result
\- x - y -+(-*\l)(x9x) ■+ ->ty(x 9y)) follows from lemma 2.16(a) and
the propositional tautologies (A+B) + (-tB^-iA) and
U+B) + ((B-K7) + (A+C)). When <\> is of the form 4> & 4> the
result comes immediately from the induction hypothesis and
the tautology
U+iB^C^) + tU+(B2+C2)) + (A+(B±&B2 + C±&C2))). If
$(x9x) is of the form Vz\\)(x9x 9z) then by the induction
hypothesis f-^, x = y -+(\\)(x 9x 9z) -*■ ty(x9y 9z)). If z is x or 2/ then
by assumption Vai|; (a?,a?,s) is Vzty(x9y 9z) . Using R2 to generalize
over s and then A7 (if z not free in x-y) we obtain
\- x = y + Vz(\\)(x9x9z) + *(a:,y,3)).
|- Vs(u^v) ■* ( Vsu+ vav) is a simple consequence from A6, Rl
and the deduction theorem. So combining this with the
previous statement we have
1 x = y +( y/z\\)(x9x9z) + Vz\\>(x9y9z)). This completes the
E r □
proof.
A consequence of theorem 2.18 is that any model for a theory
in LE can be contracted to one in which = is interpreted by
equality and the sets of sentences valid in the twc models
are precisely the same.
Definition 2.19. Suppose 31 is a realization for L .
The normal contraction 31 is defined as follows:
(i) 31 is a structure of the same type as 31.
(ii) A , the domain of 31 , is the set of equivalence classes
of the domain of A induced by the equivalence relation
E representing = in 31. We write [a] for the
equivalence class containing a e A.
(iii) If R. is a relation in 31 then R. is defined by
<Ca1].....Cax(i)3> * *J iff < a± ,. . . .aX(i)> e R^
(iv) If f. is a function in 31 then f. is defined by

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 61
(v) If c, is a distinguished element in 21 then c, - lo^].
N
21 is well defined (i.e. clauses (iii), (iv), and (v) are
unambiguous) because
*Fa x = y +(Ri(t1,.. . ,x9. ..tx(i)) + Ri(*1,...»^,-..*X(i)))
and
21 |=a x = y -►(fJ.(*1,... ,*,...t^.j) = (fJ.(*1,...,j/,...*u( .j)).
Definition 2.20. A realization 2t for L„ is normal iff = is
interpreted by equality.
Theorem 2.21. If 21 is a realization for L £fterc £fte normal
contraction 21 is normal and for any $(x) e Form(L„)
a e A
21't= 4>[2] iff 2^ 1= *CCS]]
But
Proof: By definition 2.19 (iii) <[a1],[a2]> e EN iff
< a1 ,a > e tf where E is the interpretation of = in 21.
(a 9a > e £ iff la ] = [<z9]. So tf is the equality relation
in 21, which is therefore normal.
To show that 21 |= 4>[S] iff 21^ |= 4>[[2]] we show firstly
by induction on the length of a term that for all
t e Term(L„) [*a[a]] = t^ [[a]]. If t is v. then
C*a[a]] = [a.] = t21 [[a]]. If t is e- then
% N
Ct^La]] = [e-] = t21 [[a]]. If t is f .(*„ ,... ,t,.J then
by the induction hypothesis [£.[a]] .= £7 [[a]] for all
£=l,. .. ,\i(j )• Then by definition 2.19 (iv)
Ct*[a]] - ta" [[a]].
Now we use induction on the length of <\> to show that
2l(= 4>[S] iff 21^ (= ♦CCa]]
If <|> is Ri(*1,. • • ytx(i)) then
:2l(=(()[S] iff < t*[S],...,t*(i)[S]> e f^

62 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
iff < [Aa]],... ,[£w .*[a]]> e RN. by definition
1 A { % ) %
iff %N h *CCa]] by the above.
If <\> is -,ty or (J) & (j> then it follows immediately from the
induction hypothesis that 21 f= 4>[a] iff 21^ |= 4>[[a]].
Lastly suppose $ is Vx^. Then by definition 1.21 and the
induction hypothesis
21 |= <|>[a] iff for all b e A 21 [= tyla9bl
iff for all [2>] e AN %N |* ♦CCa],[Z>]]
iff 21^ (= c()[[a]]. This completes the proof.D
Corollary 2.22. If Z c Form(LE) then Z Tzas a msdeZ. iff Z
feas a normal model.
Proof: If Z has a model 9fl then the normal contraction^
of 3Wis a normal model for Z. D
From now on we will suppose that a realization for L„
is normal. Each realization 21 for L^ is essentially the
same as its normal contraction 21 since precisely the same
formulae are satisfiable in the two structures. Some authors
do not consider non-normal realizations for languages with
equality. One method to ensure that all realizations will be
normal is to add the following clause to definition 1.21
|=a t± = t2 iff *J[a] = tjca].
It is important to remember though that = is, in the context
of the language L , a purely formal symbol and without this
additional clause (which ensures that axioms A8 and A9 are
universally valid) need not be interpreted as equality.
Familiar mathematical theories can be axiomatized in
a language with equality. For example, let I>E(G) be the
language with one binary function + and one constant 0. The
theory of groups is then the set of theorems derivable from:
(i) Vx Vy V2( (x+y) + z = x +(y + z) )
(ii) Vx(x + 0 » x)

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 63
(iii) Vx 3 y(x + y = 0).
If we add a new unary function - to the language LE(G) then
(iii) can be replaced by the purely universal sentence (iii)!
Vx(x +(-x) = 0). All (normal) models for (i), (ii) , and
(iii) will be groups as will those of (i), (ii) , (iii)1.
Models of (i), (ii) , and (iii)1 have the property that all
substructures are subgroups by exercise 1.22(a). (The group
axioms may also be formalized in a language L with + and
no constants.)
Exercise 2.13. Show how to extend the axioms (i), (ii) and
(iii)! for groups given above (in a suitably extended
language) so that all models are
(a) rings and (b) fields
and that substructures are respectively rings and fields.
In the language L it is possible to formalize
'There is exactly one x such that P(tf)1
where P(x) is some proposition expressible in L_. More
precisely, suppose <\>(x) e Form(L ). Let ty e FormiLg) be
3x(^(x) & Vj/(4>(j/) + x = y)).
Then if 31 is a (normal) realization for L_
SI |= y\> iff there is precisely one a e A such that % |= <f>[a].
So we have
Definition 2.23. V.x$(x) =Df lx(4>(x) & Vz/(<j>(z/) + x = y)).
Exercise 2.14. Show that for any realization 3W for LE
2tt h 3* Vy(x=y <* <\>(y)) ~ 3\x <j>U).
Exercise 2.15. Suppose
£\x<$(x) =D 3x(<t>(x) & 3\y((\>(y) & -i* = y)).
Show that 21 (= 3 \x$(x) iff there are precisely two
distinct a 9a e A such that Slf=(J>[a.] for i = 1^2.

64 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
Exercise 2.16. By considering a suitable generalization of
3 lx<b(x) define a formula 3 lx<t>(x) by induction on n such
that 21 (= 3 lx<t>(x) iff there are precisely n distinct
a ,. . . ,a e 4 such that 31 h <l>[a •] for £=l,2,...,rc.
Hence define a a e Sent(L„) such that
w hi
21 f= a iff the domain of 21 has exactly n elements.
In a language with equality associated with a (normal)
structure SI it is possible to express properties of 21
concerning the cardinality of some subsets of A. The preceding
exercises show that 'There are precisely n elements of 21
with the (first order) property (j>! can be expressed in the
language for 21. The following lemma illustrates that the
notions of a normal model and a language with equality are
necessary for this kind of expressive power in a first order
language.
Lemma 2.24. Suppose 21 is a realization of cardinality X
for the first order language L. For each cardinal k ^ X
there is a realization 53 of cardinality k such that 21 Q 53
and for any (j) e Form(L)9 a , ...,a e A
SI |= 4>[a1,...,an] iff 53 \° *la1,. . . ,an]
Proof: First we extend A, the domain of 21, to a set B with
cardinality k. Let a be some fixed element of A. We define
a map * : B + A as follows; b* = b if b e A, b* = a if
2? ^ 4. We shall now arrange that each element b e B has
exactly those properties of its image under * in A. More
precisely, suppose that for i e I9 R* is the interpretation
of R. in 53 and b.,. .. ,&, , . ^ e B. Then we define
<bi *xu)> « n iff <Z;i---'z'*(i)> e v
Similarly the function f*. is defined on B as follows:
3
tybi bVXo)) ■ fo(b*i KuJ for bi-'-'\(j) e B>i'J-

A FORMAL SYSTEM FOR THE PREDICATE CALCULUS 65
(#. and f. are respectively a relation and function in -4.)
Since we want Sic 93 the constants c, for k e K must
necessarily have the same interpietation in the two structures.
It is now straightforward to show by induction on the length
of (J) e Form(L) that for b ,...,& e B
(*) 93|=<KV---'V i££ 59 h <!>[*>*,...,*>*]
iff SI (= ♦[&*,... ,&*].
For atomic formulae (*) is an immediate consequence of the
definitions of R$ and f*.. For ((> of the form -4 or ((> & <\>
I* J 1 z
the result follows at once from the induction hypothesis.
When <\> is Vxty(x9y ,.. . 9y ) then by the induction hypothesis
for all b9b ,... ,b e B
59 (= Hb,b1,...9bnl iff SB [= nb*b*l9...,b*l
iff SI h Ub*,b*l9... 9bp.
As & ranges over B, &* ranges over A. Hence
<B I" ♦C2>1>...>2>n] i££ 53 |- *CibJf... ,**]
iff SI h ♦[*£,...,**]. D
Corollary 2.25. If % is a realization for L and SI |= <j>[a ]
/or some a e A then for any cardinal X there is a
realization 33 such that
% G $ and {& : 53 f8 c()[Z?]} Tzas cardinal > X.
Proof: Define the domain of 53 to be A v X where X is some
set disjoint from A of cardinality X. Define the map
* : B + A as in the proof of lemma 2.24 and then define the
relations, functions and constants of 53 as before. We have
then for all b e B
<8 (= tlbl iff SI h *[2>*]
So for all b e X » |= $lbl (because SI \= Qta ] and b* = a ). D

66 A FORMAL SYSTEM FOR THE PREDICATE CALCULUS
A consequence of lemma 2.24 is that a structure for L
(without equality) can trivially be expanded to one of
arbitrarily large cardinality in which precisely the same formulae
are valid. Since there is no upper bound on the size of a
model of a satisfiable formula there is no syntactic way of
limiting the size of a (class of) structures of a certain
kind.
Exercise 2.17. Show that any model of (J) where (j> is
Vx -,P(x9x) & Va;Vz/V2(P(a;}z/) & P(j/,s) + ?(x9z)) & V* ly? (x9y).
is necessarily infinite. Give examples of such models and
show that the prenex normal form of (j> cannot be of the form
BwVyifi where \\> is quantifier free.
Although it is possible in a language with equality to define
sentences whose models are of bounded finite cardinality, in
the following chapter we shall show that even in such a
language some concepts related to cardinality are not character-
izable by a first order set of sentences.

3
THE COMPLETENESS THEOREM AND ITS COROLLARIES
In the previous chapter it was shown that the notion of
formal derivability (in our system) is consistent with, and
no stronger than, the notion of logical consequence. Our
aim now is to show that the converse is also true and hence
to deduce that the two concepts, (semantic) logical
consequence and (syntactic) derivability, coincide. This was
first proved by Godel (1930). The proof given here is
essentially that due to Henkin (1949). The method is not
only applicable to the particular system for the predicate
calculus of Chapter 2 but can be generalized to establish the
completeness (i.e. the equivalence of derivability and logical
consequence) of other formal systems. Other important meta-
theorems follow as corollaries to the completeness theorem and
the particular form of the proof. One form of the completeness
theorem relating the syntactic and semantic properties of a set
of sentences is as follows:
Theorem. A set Z c Sent(L) is consistent if and only if
Z has a model.
(Other forms of the completeness theorem will be proved as
corollaries.)
One implication, that a set of sentences with a model
is necessarily consistent is an immediate consequence of
theorem 2.6 since no realization can be a model both for some
sentence a and its negation ->a. Now we consider the converse
implication. We suppose that Z c Sent(L) is a set known to
have the (syntactic) property of being consistent. A model
for Z has somehow to be constructed. The tools we use are
the actual symbols of the language of Z (suitably extended if
necessary to a richer language) which themselves determine a
model for Z.

68 THE COMPLETENESS THEOREM AND ITS COROLLARIES
3.1. DEFINITIONS AND OUTLINE OF THE PROOF.
Definition 3.1. Z Q Sent(L) is complete if for each
a e Sent(L) either Z |- a or Z |- -*a.
It is important to realize that the notion of completeness
of a set of sentences (or theory) is distinct from the notion
of completeness of a formal system, which pertains to the
equivalence between certain semantic and syntactic concepts.
The completeness of Z is, as stated here, entirely a
syntactic property. However the completeness theorem for the
predicate calculus implies that the property may equally well
be defined in terms of semantic concepts.
Definition 3.2. A first order language Lf is an alphabetic
extension of the language L if L' is obtained from L by the
addition of a set of new constant symbols alone. We write
L c: l ' when L' is an alphabetic extension of L.
Definition 3.3. Suppose Z c Sent(L) and L Q^L'.
Z' c Sent(L') is a I-full extension of 1 in L' if Z c z ' and
for any formula <i>(x) e Form(L) with precisely one free
variable x such that Z |- 3x<\>(x) there is a constant c e L'
such that <fr(C) e Z'.
Definition 3.4. Z c Sent(L) is full if Z is a Z-full
extension of Z in L.
If Z' is a Z-full extension of Z in Lr then an instantiating
constant c corresponding to the derivable existential
sentence 3a;(j)(:c) (i.e. Z' \-3x<t>(x) + (j>(C)) is sometimes called
a Henkin constant.
We now outline the steps by which we show that a
consistent set of sentences has a model.
A. Any consistent Z c Sent(L) can be embedded in a
consistent Z-full extension Zr c Sent(L') for some Lr

THE COMPLETENESS THEOREM AND ITS COROLLARIES 69
such that L QA Lr.
A
B. Any consistent Z Q Sent(L) can be embedded in a
complete consistent Z*c Sent(L).
C. (Using A and B alternately) any consistent Z c Sent(L)
can be embedded in a complete consistent full
Z+c. Sent(L+) where L c l+.
D. A complete consistent full Z Q Sent(L ) has a model.
E. (Using C and D) if Z c Sent(L) is consistent then
has a model.
The method of proof involves the construction of a
model (step D) which depends only on the sentences in Z .
An analysis of the construction of the model yields stronger
theorems than that stated at the beginning of this chapter
for we can ascertain bounds on the size of a canonical model
associated with a consistent set of sentences. For languages
L with equality the associated canonical model (D) is
normal.
The first two lemmas in the proof, of which one is
stated in A above, are valid for sets of sentences in
arbitrary first order languages L. To continue the steps
outlined above we consider separate cases according to the
cardinality of the language L. The steps of the proof are the
same in each case but the assumptions under which B can be
carried out depend intrinsically on the cardinality of L.
Lemma 3.5. Suppose Z c Sent(L) and Z is consistent. Then
there is an L' such that L Q. L' and a consistent 1-full
extension of!> Zr Q Sent(L').
Proof: There is an obvious way in which to extend Z to a
Z-full set Z' in a language with fenough* constants. The
problem is to show that the natural construction does yield
a consistent Zr. First we consider those existential
sentences of L for which we require instantiating constants.
Let

70 THE COMPLETENESS THEOREM AND ITS COROLLARIES
Z = {(j> e Form(L): 4> has exactly one free variable x. and
Z |- Ix^ix^)}.
Now we simply add to L new constants not already occurring
in L in one-one correspondence with the elements of Z1#
That is, Lr = L u {c : <(> e Z1> where c ^ l and
c. = c. only if <t> = ty. It is trivial that
Z' = Z u H(c.) : <t> e Z } is a Z-full extension of Z in L'.
Now we must show that Z' is consistent. We argue by
contradiction. Suppose that Z' is inconsistent. Then for some
\\> e Form(Lr) we have both Z' \- \\> and Zr |- -n|/. The
derivations of i|/ and -»i|/ from Z r are of finite length and hence
there is a finite subset H-Cc. ) ,.. . ,<|>n( c )} of
n
{<f>(c.) : <J) e S1> such that Z u U^Cc, )}^ = 1 |- ty and
Z u {(,)i( cd).)}i = i I""1*- So the set
Z u (<l>1(c. )&...& (J) (c. )} is inconsistent and, writing
(P1 <Pn
<£> for (f>1( c, ) & . .. & 4> (c, ), we have Z u {<£>} |—• $ by
lemma 2.10. Then using thendeduction theorem and the
tautology (<£> +-i$) +-i$, Z |- -i$. The constants c ,...,c do
not occur in Z since by construction they are not in L, the
language of Z. So in the derivation of -i<£> from Z each
occurrence of c. may be replaced by a distinct new variable
* i
y.eL not already occurring in the derivation to yield a
derivation o£ -i (4>1(t/1) & ... & 4>n(*/n)) from t. Using R2
to generalize over #.,...,# we obtain
^ V^y1 *yn -.(*1(j/1) & ... & *n(j/n))- Then, using the
proof of theorem 2.15, Z |—» 31/ 3*/„ (*, (j/, )& ... &<!> (#„)).
Since the z/.!s are distinct w. does not occur in
<t> Ay .) if i f j and it is easily shown that
Z |--,( 3^^^) & ... & lyn4>n(yn)). But since
£ h 3 2/-^^ (2/•) f°r i = l,---,n (4>.e Z ) this contradicts the
consistency of Z. Hence Z' is consistent. □
Lemma 3.6. Suppose Z u {(J)} Q Sent(L) and it is not the case
that Z |—i(j). Then Z u {(J)} is consistent.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 71
Proof: Notice that since -><t> is not provable from Z then by
lemma 2.10 Z is consistent. Suppose Z u {<\>} is inconsistent.
Then Z u {(J)} |— —><t>• Using the deduction theorem and the
tautology (cj> ■+ -»(j>) ■+ -i(J> we have Z |—i(J> which contradicts the
hypothesis of the lemma. Hence Z u {<\>} is consistent. □
3.2. COMPLETENESS FOR COUNTABLE LANGUAGES
For this section we restrict our attention to sets of
sentences in a countable language L. The proof of B (of the
outline scheme in section 3.1) which we give for sets of
sentences in a countable language does not generalize for the
case where L is uncountable without a further set-theoretic
axiom that is unnecessary in the countable case. The crucial
property of a countable language L is that the set of
sentences of L is itself countable and can be enumerated
$1*$2'm m m ' ^e Preci-se order in which the sentences occur
in the list is unimportant; it is sufficient for our purposes
that for each (j> e Sent(L) there is some finite n such that
<J> = (j>. A listing of the sentences of L with this property
can be obtained in the following way: list the symbols of
the language (assumed countable) s ,s7,... ; at the nth
stage consider the strings of symbols from {s±9... ,s } of
length £ n (this is a finite set); eliminate those strings
which are not sentences and those sentences already occurring
in the list of sentences; then order the remaining (finite)
set of sentences and add them to the list obtained up to the
(rc-l)th stage; then proceed to the (rc+l)th stage. Each
sentence in the language will automatically occur in this
listing.
Lemma 3.7. Suppose Z Q Sent(L) where L is countable and Z
is consistent. Then there is a complete consistent
Z*Q Sent(L) extending Z.
Proof: Suppose $ ,(j> ,... is an enumeration of all the
sentences of £. We define a countable sequence of sets of
sentences ZQ,Z1,. . . such that Z = Zqc: vc -Zn~ Sent(L)

72 THE COMPLETENESS THEOREM AND ITS COROLLARIES
and Z is consistent. Let Z = Z. For n > 0
Zrc+1 = Zrc U {(^+l} i£ iZ is not the case that ln l""l*n+l and
Z = Z^ otherwise. Let Z* = (J Z . The claim now is that
neN
each Z is consistent and that Z* is complete and consistent.
That Z is consistent is proved by induction on n using lemma
3.6. If Z* is inconsistent then there is a finite A Q Z*
such that A is inconsistent (exercise 2.3(b)). But for any
finite A c £* there is an n such that A c £ since if
n
A = {cr1,...,a } we may take n = max {n. : i=l9... 9m} where
a. e Z . But this means Z is inconsistent contradicting an
i ni
earlier result in the proof. Consequently Z* is consistent.
It remains to show Z* is complete. Suppose a e Sent(L)
Then a = <\> . for some n > 0. So either Z I- —ta or a e Z
Hence E* is complete. □
The particular complete consistent extension Z* of the
consistent set Z defined in lemma 3.7 is in no sense unique
if Z itself is not complete. From different orderings of the
set of sentences different complete sets will result from
the construction given in the proof. Indeed, for each
a e Sent(L) such that not I \- o and not Z |—ia, both Z u {a}
and Z u {-ia} are consistent and each can be extended to a
complete consistent set including Z.
In the following theorem we combine lemmas 3.5 and 3.7
in a suitable way to carry out step C in the outline scheme.
When Z Q Sent(L) is consistent and L is countable an analysis
of the proof of lemma 3.5 shows that the lemma may be
strengthened as follows: there is a countable alphabetic extension
L' of L and a countable Z-full extension Z' c Sent(L'). L'
is countable since E, is countable and the union of two coun-
l
table sets is countable. Since Z' is a set of sentences in
a countable language L', Z' is countable. We note that
trivially a set of sentences in a countable language has a
countable complete extension (since both sets are subsets of
the countable set of sentences of the language).

THE COMPLETENESS THEOREM AND ITS COROLLARIES 7 3
Theorem 3.8. Suppose Z Q Sent(L) is consistent. Then
there is an L*9 L C L* and a complete consistent full
Z* c: Sent(L*) extending Z.
Proof: We use lemmas 3.5 and 3.7 alternately countably
often to construct (countable) languages L ,L2,... and
(countable) sets of sentences Z , T2, Z , T3,... such that
for each i
r . „ u z ,
.,.=„-. „,Z.cr.cz.„ and
-z, 4 ^ +1' ^ v + 1 v + l
c SentiL. „). Let L„ = L and Z. = Z. When L
and Z have been defined then (by lemma 3.5) L 1 and r 1
are chosen' so that L ^„ L and r , is a consistent Z -
n A rc + 1 rc+1 n
full extension of Z in L „. Z . is a complete consistent
n rc+1 rc + 1 ^
extension of r in L (lemma 3.7). Finally let
oo oo
L* = (J L and Z* = (J Z . Z* is clearly an extension of
rc=l rc=l
Z and L Q L*. By construction each Z is consistent and so,
as in the proof of lemma 3.7 it follows that Z* is consistent.
If a e Sent(L*) then for some n > 1 a e Sent(L ) and hence
either Z |- a or Z \-->o; so Z* is complete. To show Z* is
full we suppose that Z* |- 3x<t>(x) where <t> e Form(L*) and <{>
has the single free variable x. Then for some m9
Z 1-3 xd>(x) and so there is a constant c e L A such that
m ' m+1
^c) e rm+1 - z*- This completes the proof that Z* has the
desired properties. Q
We have now completed A, B, and C of the proof for
countable languages L. Before we continue to D we need one
further definition.
Definition 3.9. If Z Q Sent(L) is consistent and L contains
at least one constant the canonical structure determined by Z
is Zz = <?, {^}i£j> lfj}d€j. i°k}k€l?
where T = {t: t is a closed term (i.e. without variables) of L}
and < tl9...9tXii)> e R^ iff Z [^i(t± ,... ,*x(i) ) for i e I
and c, = c, for k e K.

74 THE COMPLETENESS THEOREM AND ITS COROLLARIES
We here use a new notation t for the term t to emphasize that
the term assumes a new (semantic) role as an element in the
domain of a relational structure and to distinguish this
role from the original (syntactic) usage of t. So the set
? is simply a set of elements in one-one correspondence with
the set of closed terms of L (non-empty since L is assumed
to contain at least one constant).
The properties of completeness, fullness, and consistency
are precisely those required to show that the canonical
structure determined by Z is indeed a model for Z.
Theorem 3.10. Suppose Z c Sent(L) and that Z is consistent,
complete and full. For each a e Sent(L)
(*) Xz [= a iff Z [- a
Proof: We remark that if Z is full and non-empty then L has at
least one constant (e.g. Z |- a^R^ (x,x9. . . ,*) v- R . (x,x, . . . 9x))) .
We use induction on the length of a e Sent(L) to prove (*).
Note that we are using induction to establish a property of
all sentences of L instead of the more familiar case of a
property of all formulae of L. The induction steps must
be modified accordingly: the atomic sentence a is a formula
of the form R . (£ ,.. . ,£ . ) where £,...,£w.. are closed
t'l A {1* ) 1 A {is )
(variable-free) terms of L; -ia, a & a are sentences just
in case a, a and a respectively are sentences; Vx<t>(x) is
a sentence if and only if for some (or, equivalently, all)
closed term t of L <t>(t) is a sentence and so at this stage
of the induction the hypothesis can only be assumed for <\>(t)
where t is any closed term and not, as is usually the case,
for the subformula <$>(x). When a is atomic then (*) is simply
part of the definition of 2^(since the denotation of t is t).
Now suppose (*) holds for af when a' has length less than
that of a. There are three cases to consider according to
the outermost connective in a.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 75
1. a is -ta!
Z |= a iff not 31 |= a' by definition 1.21
iff not Z |- a' by the induction hypothesis
iff Z |—ia' because Z is consistent and
complete.
2. a is a & a .
Iz |= a iff £z |= o and Z^ |= a2 by definition 1.21
iff Z |- a and Z |- a by the induction
hypothesis
iff Z [- a & a because a + (a +(o &a ))
and (a &a0) -*■ a. for i = i,2
are instances of A4 and A5.
3. a is Va? <|>(a?).
3^, (= a iff for all t e T Z^, |= ((>[?] by definition
1.21
iff for all t e T° {T° is the set of closed
terms)
Zy (= (j>(£) since the interpretation of
the closed term t is t
iff for all t e T° Z |- (j>(£) by the induction
hypothesis since (j>(£) e Sent(L\
Suppose that it is not the case that Z \- a. Then by the
completeness of Z , Z |—ia. But Z |—<j iff Z |- 3x -*$(x) (by
theorem 2.15). Z is full so for some c e L Z |—■ <(>(c ).
Then by the equivalence above it is not the case that
Z^ |= a. Conversely if Z |- a then by A6 for all closed terms
t Z |- (j>(£) and so L )= a. This completes the induction and
hence the theorem is established. □
A combination of theorems 3.8 and 3.10 will now complete the
proof of the theorem for countable languages stated at the
beginning of the chapter.

76 THE COMPLETENESS THEOREM AND ITS COROLLARIES
Theorem 3.11. (Godel-Henkin) Any consistent Z Q Sent(L)
for countable L has a model.
Proof: By theorem 3.8 there is an alphabetic extension L*
of L and a complete consistent full Z* c Sent(L*) extending
Z. The reduct of 3_,* to the language L is a model for Z. D
Several important theorems are corollaries of theorem 3.11.
The first asserts the completeness of the formal system in
the form in which the notion of completeness was first
formulated on p. 68.
Theorem 3.12. If Z u {a} c Sent(L) then Z |= a iff Z |- a.
Proof: That Z j- a implies Z |= a was proved in theorem 2.6.
Conversely suppose that it is not the case that Z |- a. Then
it is also not the case that Z |—i —icr. So by lemma 3.6
Z u {-ia} is consistent and by theorem 3.11 has a model £.
This implies that not Z ^ a. So Z (= a iff Z |- a
demonstrating that formal derivability is as strong a concept as
logical consequence. □
Corollary 3.13. The theorems of the predicate calculus are
precisely the universally valid formulae.
Proof: Let Z be empty and a be the universal closure of
some formula (J). Theorem 3.12 then implies that |= a iff |- a.
However <j> is universally valid iff a is universally valid
(exercise 1.17(b)) and (J) is derivable iff a is derivable.
Hence the result. □
Theorem 3.14. Compactness theorem. If Z Q Sent(L) then Z
has a model if and only if every finite subset of Z has a
mode I.
Proof: If Z has a model then trivially every finite subset
of Z has a model.
Conversely suppose Z has no model. Then by theorem
3.11 Z is inconsistent. So for some finite subsets
E , Z2 c £ and some (J) e Form(L) Z |- (J) and Z [--.(J)

THE COMPLETENESS THEOREM AND ITS COROLLARIES 11
Consequently the finite subset of Z, Z u Z0 is inconsistent
and hence has no model. □
The compactness theorem is formulated entirely in terms of
semantic concepts. The theorem is meaningful without the
apparatus of a formal system for first order logic. Indeed
the theorem can be proved without reference to formal
systems but here it is an almost trivial consequence of the
completeness theorem, which relates the .syntactic and
semantic ideas. The proof is totally non-constructive in the
sense that there is no method for constructing a model for
Z given models for each finite subset of Z. The
compactness theorem is probably the most important and fundamental
theorem in model theory and some applications will be given
when we have established the completeness theorem for a
larger class of first order languages L .
3.3. COUNTABLE LANGUAGES L WITH EQUALITY.
The construction of X- for complete consistent full
sets of sentences Z does not in general yield a normal model
for Z. However using the construction of theorem 2.21 it is
immediately clear that a consistent set Z c Sent(LE) has a
normal model. In the case where L„ is a language.with
equality we will collapse the canonical structure associated with
Z c SentiL„) so that it is automatically a normal model for
Z when Z is complete, consistent and full.
Definition 3.15. If Z c SentiL^) and L„ contains at least
hi a
one constant then the canonical structure determined by Z is
*Z = <?' {Ri}Ul {^W {a*W
where T is the set of equivalence classes [£] of closed
terms t of L determined by the equivalence relation
See e.g. Bell and Slomson (1969), page 102.

78 THE COMPLETENESS THEOREM AND ITS COROLLARIES
t± ~ t2 iff t Y *x = *2
and (as before)
<[t1],...,C*X(i)]> € Ri iff £ I- Ri(*1.---.*X(i)) for i e J
^(CV C*u(^)]) " CV'l 'u(j))] f0r J' € '
The proof of theorem 3.10 can now be carried out as before
to obtain a normal canonical model for complete consistent
full sets of sentences in a countable L_. Consequently
Theorem 3.16A. If Z £ Sent(L„) and L„ is countable then Z
is consistent if and only if Z has a (normal) model.
As before, from this theorem may be deduced the analogues
of corollary 3.13 and theorem 3.14 (the compactness theorem).
One further important result may be proved at this stage.
The proofs of theorems 3.8 and 3.10 are sufficiently
constructive to consider the cardinality of a canonical model
associated with a given countable consistent set of
sentences. In theorem 3.8 a countable sequence of countable
languages < L > is constructed by adjoining at each stage a
ne a)
countable set of new constants. To ensure that the
resulting language L* = \J L is countable also (without the axiom
new
of choice) we may first define the language
L - L u {c. : iew}. Then let f : w + w x wbe some one-one
onto function. At the nth stage in the construction
instantiating constants for sentences of the form
3x$(x) e Sent(L ) such that Z |- 3x<\>(x) are taken from the
countably infinite set {c: 3m f(i) = <n,m>}. Then the
countable language L is an alphabetic extension of each L
and hence of I*. Consequently the set of equivalence classes
of closed terms of L* is at most countable. Theorem 3.16A
can be strengthened as follows:

THE COMPLETENESS THEOREM AND ITS COROLLARIES 79
Theorem 3.16B. If LE is countable and Z Q Sent(L„) then
Z is consistent if and only if Z has a countable model.
Of course theorem 3.16B is also valid for sets of sentences
in a countable language without equality. But cardinality
concepts are of considerably more significance for languages
with equality (cf. pages 64,65).
The remainder of this section is concerned with some
refinements of the completeness theorem and its proof for
which familiarity with certain concepts of recursion theory
and first order arithmetic is desirable. The reader may
omit these paragraphs (which are not referred to elsewhere)
and resume again at the beginning of Section 3.4.
A countable structure is isomorphic to a structure
whose domain is a subset of N9 the set of natural numbers.
So, without loss of generality, the completeness theorem as
proved in theorems 3.11 and 3.16 may be stated:
A countable consistent set of sentences is satisfiable
in a subset of the natural numbers (with suitable relations,
functions and individual constants).
Certain subsets of N (or subsets of Nn) admitting a
definition of a particularly simple form are arithmetic;
they can be classified further in the hierarchy of
arithmetic sets of which those at the lowest level are the
recursive sets. When a sentence is satisfied in a domain
included in the natural numbers the interpretations for the
predicate letters in the sentence are simply subsets of N
and as such may be arithmetic. Kleene and Hasenjaeger have shown
that it is always possible to find a model (with domain c n) for
a satisfiable sentence in which the relations are A (relatively
low in the arithmetic hierarchy); i.e. each ?z-ary relation R
has the form
«a?1,. .. ,xn> Vj/ 3zS±(y >z9x±9. . . ,a?n)>
and the dual form

80 THE COMPLETENESS THEOREM AND ITS COROLLARIES
{<x±9... yxn) : 3yVzS2(y 9z9xl9... 9xn ) }
where S ,S are recursive. Although some refinements of
this result have been obtained it is not always possible to
improve this result significantly; for example in general
we cannot ensure that the relations are recursively
enumerable, let alone recursive.
One of the corollaries of the completeness theorem
is that each universally valid formula can be derived in the
formal system of Chapter 2. A particular mathematical
theory is obtained by considering the logical consequences
of the axiom schemata Al - 7 and additional non-logical
axioms determined by the theory. Suppose now that instead
of considering the addition of single instances of non-
logical axioms we consider PC , the system resulting
from the adjunction of a new axiom schema A(J> with the form
of an unprovable formula (j>. Using the Godel technique of
arithmetization Hilbert-Bernays showed that first-order
arithmetic (the formal system based on Peano's axioms) is
a)-inconsistent when PC is the underlying logic; i.e. there
is some formula ty(x) such that ^(0), ^(l), i|K2),... and
-tVxtyix) are all provable. This is clearly an undesirable
consequence of the underlying system for the predicate
calculus; the schemata Al - 7 (and their consequences using Rl
and R2) are indeed sufficient.
3.4. COMPLETENESS FOR UNCOUNTABLE LANGUAGES
Suppose that L is a first order language of cardinality
k (i.e. the set of symbols of L has cardinality k). If k < Kn
(i.e. is countable) then there is an enumeration of the
countable set of sentences of L and, as a corollary, every
consistent set of sentences of L can be extended to a
complete consistent set. An analysis of the proof of lemma
+See Kleene (19 52), page 394, Theorem 35.
++See Kleene (1952), page 395.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 81
3.7 shows that the well-ordered enumeration of the sentences
plays an integral part in the construction of the complete
set extending the given consistent set. If k is uncountable
then in a standard formulation of set theory (e.g. Zermelo-
Fraenkel or Godel-Bernays) it is consistent to assume there
is no such well ordering of the set of sentences. Hence in
order to extend lemma 3.7 to uncountable languages it is
necessary to add a new set theoretic axiom, the axiom of
choice, to the metatheory. For the remainder of this
section we will assume the axiom of choice and write (AC)
beside theorems with proofs dependent upon this assumption.
The specific form of the axiom of choice to be used is given
in the following:
Well ordering theorem (AC). Any set can be well ordered.
A proof that the axiom of choice is actually equivalent to
the proposition that any set can be well ordered can be
found in any standard text book on set theory.
A further corollary of the axiom of choice which will be
used is stated in the following
Lemma 3.17 (AC). Suppose k is an infinite cardinal. Then
K = K . N = K . K .
A proof of this lemma can again be found in a standard set
theory text.
Corollary 3.18 (AC). If L is a first order language with
cardinality k then the set of sentences of L has cardinality
K.
Proof: There are < <n sentences of L of length n since
there are < k possible choices for each symbol. Hence there
See e.g. Halmos (1960) , pages 68, 97.

82 THE COMPLETENESS THEOREM AND ITS COROLLARIES
are < £ <n - £ k=N0.k=k sentences of L. That
new new
there are at least k sentences follows from the observation
that either there are k distinct predicates or there are k
distinct terms of L. D
Lemma 3.7 can now be extended for an arbitrary first order
language L.
Lemma 3.19 fAC). Suppose Z Q Sent(L) and Z is consistent.
Then there is a complete consistent Zf Q Sent(L) such that
Z c £'.
Proof: The set of sentences of L can be well-ordered
{(j> : a < 3) where 3 is some ordinal with the same
cardinality as L. By analogy with the proof of lemma 3.7 we define
a sequence of sets of sentences of L as follows:
ln = l> E^i = l„ u {$„} if it is not the case that
U Oli 1 Ob 01
2~ h -•♦«, and E . = Z otherwise; and for limit ordinals
a ' Ta a+l a '
X < 3 Z, = (J Z . It follows from lemma 3.6 that if
a<X
E is consistent then so also is Z^ „ . For limit X,if Z,
a a+l 'X
is inconsistent then for some an < X Zrt is inconsistent.
o ao
So by transfinite induction Z is consistent for each a < 3.
Let Zf = Zg. Zg is complete because for any a c Sent(L)
there is an a < 3 such that a = <b . So either Z I- -.((> or
a a ' a
ra a+l 3
Exercise 3.1. Show that lemma 3.19 can be proved by
applying Zorn's Lemma to the partially ordered set 'of consistent
extensions of Z in L.
The remainder of the proof of the completeness theorem
is carried out as in the countable case. The countability
of L is explicitly used only in the proof of step B which
in the general case is lemma 3.19. The proof of theorem
3.8 is again accomplished by the application of lemmas 3.5
and 3.19 alternately countably often. Increasing sequences
of sets < Z > , < r > are defined and then the. union
n * n

THE COMPLETENESS THEOREM AND ITS COROLLARIES 83
Z* = (J Z is a complete consistent full extension of the
new
consistent set Z. The canonical structure is a model for
Z* and hence its reduct to the language of Z is a model for
Z. The generalized completeness theorem can be formulated
as follows:
Theorem 3.20 TACl. If Z c Sent(L) LSent(LE)l9 Z is
consistent and L has cardinality k then Z has a [normal] model
of cardinality < k.
Proof: The cardinal bound on the canonical structure
associated with a complete consistent full extension of Z is
obtained as follows:
(i) If L has cardinality < k then by corollary 3.18
Z = {(j> e Form(L): Z |- 3a?<|>(a?)} has cardinality < k. Hence
there is an alphabetic extension L' of L with cardinality
< k + k = k and a Z-full Zr c Sent(L') extending Z.
(ii) If L has cardinality < k and Z Q Sent(L) then there
is a complete extension Z* of Z with cardinality < k.
(iii) The sets Z , T for n e N (cf. proof of theorem 3.8)
v J ny n v r j
have cardinality £ k and hence Z*, a complete consistent
full extension of Z, can be constructed in a language
L* with cardinality < k . K = k. The set of equivalence
classes of closed terms of L* has cardinality < k
establishing the required bound on the canonical structure. □
We have shown how to construct a model for a consistent set
of sentences. What, if any, is the corresponding result for
a consistent set of formulae , $? For simplicity, we will
consider here only the case where $ is a countable consistent
set of quantifier-free formulae. Notice that the addition
of Henkin constants when dealing with sets of sentences was
necessary only for the quantifier case of the induction in
theorem 3.10, so we would hope to be able to omit that step
when considering quantifier-free formulae. The following
theorem demonstrates how the result and the construction

84 THE COMPLETENESS THEOREM AND ITS COROLLARIES
*0 = *;
w + 1
$ u f it
n n
<£> otherwise
involved in the proof may be modified in this case.
Theorem 3.21. If $ is a countable consistent set of
quantifier-free formulae of L then <S> is satisfiable in a
countable structure.
Proof: There are essentially two steps in the proof
(corresponding to steps B and D of the outline of section
3.1). First we extend $ to a consistent set <£>' complete
with respect to quantifier-free formulae. A straightforward
modification of the construction in lemma 3.7 accomplishes
this:
namely, we enumerate the quantifier-free formulae of L, say
^/m^-i »• • • an<i define
$' = U $
We leave it to the reader to verify that <£>' is consistent
and that for any quantifier-free i|/ e Form(L) either
<£>' \- ip or <£>' |- -up.
Now construct a countable structure 53 (depending on
<£>r) as follows:
(i) as domain, 5, we take the set of all terms of L,
(ii) for i e I < t. ,.. . ,£w . .> e #.
iff •' f-w....*X(i)>.
(iii) for o e J /.(£,...,£,..) is to be the term
(iv) for k e K the interpretation of c, is just c, .
It is simple to verify that for any t(x ,... 9x ) e Term(L)
t \_x. 9. . . 9x J = t(x 9,., 9x )
(i.e. the denotation of t with respect to the assignment of
the element x. in B to the variable x. is just t itself).

THE COMPLETENESS THEOREM AND ITS COROLLARIES 85
Now we show by induction on the length of a quantifier-free
formula (J> that
(t) <B 1= 4>lx± xnl iff $' |- <(>(*! a?w).
(Notice that, as for the terms above, the x ,...,# occurring
on the left-hand side are to be thought of as elements in the
domain of the structure 53 whereas on the right-hand side
they are terms in the language L.)
When <\>(x±9. . . 9xn) is R^( t±,. . . ,*w£ x) (so that a?1,...,a?
are the variables occurring in the terms £.,... ,£, , . v) then
/ 1 A (. *Z* J
by definition 1.21
53 f8 *Ca?1 a:^] iff < t± *X(i)> e/?£
iff $ r f- R. (£ ,. . . , t. , .. ) by definition.
The two induction steps corresponding to the propositionai
connectives -.and & are almost exactly as in theorem 3.10.
Then since we are considering only quantifier-free formulae
this completes the proof. Q
Exercise 3.2. Suppose <j> is a quantifier-free formula such
that h terms and sub-terms occur in (J). Show that if <t> is
satisfiable then (J) is satisfiable in a structure with < h elements.
We have seen how the Henkin method for proving the
completeness theorem in the countable case readily extends
to the uncountable case. (This case was first proved by
Malcev (1936).) This is not true of Godel's original proof
and is one reason for preferring the Henkin method of proof
here. The completeness of certain systems other than first
order predicate logic can also be established with a Henkin-
style proof. Henkin (1950) himself used the method to
prove a suitable formulation of the completeness theorem
for a system of order u). Another application can be made
in the case of infinitary logic as introduced by Barwise
where the language -£? is based on a countable admissible

86 THE COMPLETENESS THEOREM AND ITS COROLLARIES
set A. Other methods for proving completeness include that
of Rasiowa and Sikorski (1950), which uses Boolean algebras,
and of Beth (1955) using semantic tableaux.
Although we have used the well ordering theorem, a set-
theoretic principle equivalent to the axiom of choice, to
establish the completeness theorem for arbitrary first order
languages, a weaker principle, the Boolean prime ideal
theorem, implied by, but not implying, the axiom of choice,
is sufficient to show completeness in the following sense:
a consistent first order theory has a model.
3.5. APPLICATIONS OF THE COMPACTNESS THEOREM
In this section we begin with a general model-theoretic
result before considering applications of the compactness
theorem to particular mathematical theories.
Theorem 3.22. Suppose Z c Sent(L„) has arbitrarily large
finite models. Then Z has an infinite model.
Proof: We define an alphabetic extension L* of L„ by
adjoining a countably infinite set of distinct new constants
{bi: i e a)} to LE. Let Z* c Sent(L*) be the union of Z with
the set of all sentences of the form ->b . = b . where i < j < ta
* 3 d
Now suppose Z is a finite subset of Z*. Then
Zn = Z. u {-ib. = b . }P for some finite p and some finite
01 vk 3k fc = l
Z £ Z. By hypothesis Z has a model % with more than 2p
elements. We expand % to a realization 2l* for L* by
adjoining distinct new constants d. e A for the < 2p new constant
symbols b. occurring in Z and arbitrary interpretations d.
for those b. which do not occur in Z„. Then
3 0
+See e.g. Aczel (1973)
++See e.g. Mendelson (1964), page 100.
In this section the axiom of choice is assumed whenever
necessary to yield the completeness theorem for uncountable
languages.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 87
SI* = <2l, {d. : i e o)}> h ZA.
' *z* '0
Now we can apply the compactness theorem to the set
E* c Sent(L*). Since an arbitrary finite subset Z of Z*
has a model so also does Z*, say 33*. 59* has an infinite
domain since there are infinitely many distinct elements
that are the interpretations for the set {b .} . . The re-
duct of 33* to the language L„ is an infinite model for Z. Q
Corollary 3.23. There is no set of sentences Z such that
2ft |= Z if and only if 2ft is finite.
Corollary 3.23 can be contrasted with the result (exercise
2.16) that it is possible to characterize in a single
sentence (in a language with equality) all (normal) structures
with a given fixed finite cardinality, or indeed those
structures with domains of less than some fixed finite cardinality.
Finiteness itself cannot be characterized in the same way
even when infinite sets of sentences are considered.
The compactness theorem can be used in more specific
circumstances to obtain results in other branches of
mathematics. This is illustrated with examples from algebra,
arithmetic, and graph theory.
Theorem 3.24. Suppose L„ is a first order language for the
theory of fields with two binary functions +, • and two
constants 0,1 . The theory of fields of characteristic zero
cannot be finitely axiomatized (i.e. there is no finite
I QSent(LE) such that g ^Z iff % is a field of
characteristic zero).
Proof: The theory of fields can be axiomatized by the
following set of sentences in L„.
i Va;Vz/ V2((i + y) + z = x + (y + z))
\ VxVy(x + y=y + x)
j Vx(a; + 0 = x)
\ V* Vj/(a? + y = 0)

88 THE COMPLETENESS THEOREM AND ITS COROLLARIES
IV x Vz/ V z( (x • y) • z - x • (y • s ) )
ViVz/(x • i/ =1/ • #)
Vx(a; * 1 = x)
Vx(-ix - 0 ->- 3 i/ (a; • y = 1 ))
III VarVz/V s(x • (z/ + z) - (x • z/) + (x • 2))
IV nO = 1
Any model for group I will be an additive abelian group. A
model for group II will, without the interpretation for 0,
be a multiplicative group. Ill asserts that multiplication,
• , is distributive over addition, +. Let
F = I u II u III u IV.
An axiomatization for fields of characteristic zero
is obtained by adding to F an infinite set of sentences
{S } where S is
n new n
-i(l + 1 + . . . + 1) = 0
n times
(A field is of characteristic zero if and only if it is not
of non-zero finite characteristic.)
Let Fn = F u {S }
0 n new
Just because there is an axiomatization for fields of
characteristic zero with an infinite set of axioms there is no a
priori reason why a finite set I Q Sent(LJ) should not vield
F as theorems. The following lemma however eliminates this
possibility.
Lemma: Suppose o e Sent(L„) and F ^ 0; then there is an n
such that o is valid in all fields with characteristic £ n.
Proof: Suppose F |= a. Suppose there is no n such that o
is valid in all fields with characteristic > n. Then -na is
satisfiable in a field with arbitrarily large finite
characteristic. So any finite subset of F u {-»<?} has a model.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 89
So by compactness F u {—a} has a model which contradicts
the initial hypothesis that F f= o. Hence there is some n
such that a is valid in all fields with characteristic > n.
N.B. The proof of the lemma given above does not give us
any particular n satisfying the lemma. The proof merely
shows that the hypothesis that, no such n exists leads to a
contradiction. However if we use the completeness theorem
(to replace |= by |-) then from a derivation of a from F it
is possible to compute an n: the derivation of a will use
only a finite number of instances of {S} say, Sm >...ySm •
then (by completeness again) we conclude that for
n > maxim ,...9m.) o is valid in all fields of
characteristic > n.
Now we return to the theorem. If ij^,...,^, is a finite
axiomatization for F then consider a = ^1 & ... & i|/fe . By
the lemma a is valid in all fields with characteristic ^ n
for some finite n. Since there are fields with arbitrarily
large finite characteristic (e.g. J , the field of integers
modulo p where p is prime) we have the required
contradiction. D
Exercise 3.3. Assume that for any non-constant polynomial
p(x) with coefficients in some field 8 there is an extension
field 3* of 8 in which p(x) has a root. Show, by using the
compactness theorem, that for any field $ there is an
extension field 8* of g in which every non-constant polynomial
of \^Lxl has a root.
The next example is an application of compactness to
arithmetic.
Theorem 3.25. Suppose L„ is a first order language with one
unary function ' (successor)9 two binary functions +, •, and
one constant 0. Let W = <#»'?+, •, 0> be the realization
of L„ with domain N, the natural numbers, successor, addition
and multiplication the interpretations for ', +, »
respectively, and 0 the interpretation for 0. Let

90 THE COMPLETENESS THEOREM AND ITS COROLLARIES
ThiW) = {o : o e Sent(L„) & 31ha}. Then there is an 2H_
a u
such that%fl |= Th{Jt) andffll is not isomorphic to 9t.
Proof: Let Lp, be an alphabetic extension of L„ obtained by
the addition of a single new constant c.
Let Z+ = Th(W) u {a >weaj where a is -ic = n and
n is 0".,. f. Suppose I is any finite subset of I .
n times
Then there is, some n such that for all m > n -yc = m / I .
Then <9t,w > |= E . Hence by the compactness theorem I has
a model, 2ft say. Suppose 9#Q, the reduct of 2R to the language
L„, is isomorphic to W. Then there is an isomorphism
f : % "^^o* So for some integer n fin) = c where c is the
interpretation of c in9W. But
2H0 |=-ia: = n[c] and 5tt (= x = n[n]
which gives the required contradiction. Q
Exercise 3.4. Suppose 9JL is the (countable) model for
Th(W) u {a } occurring in the proof of theorem 3.24.
n new
Define $(xyy) to be 3z(-nz = 0 & x + z - y)
Then Vx V y {${x9y) v 4>(j/,a?) v * = y) e Thffl).
Hence there is a linear ordering <~> of 9ft defined by a <w« b
iff 93^ h <Ha,2>]. *> fe
What is the order type of this ordering of the domain of 3tt ?
The final illustration of the compactness theorem is
taken from graph theory.
Definition 3.26. (i) The structure <M,B) where i? is a
binary relation on M is a graph if R is irreflexive and
symmetric on M. If a,b e M and (a9b) e R then a is connected
to b.
(ii) The graph <M,#> is k-colourable if
there is a partition of M into < k subsets such that no two
connected elements are in the same subset.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 91
Theorem 3.27. Suppose (M9R) is a graph, <M9R) is
k-colourable if and only if every finite substructure of < M9R) is
k-colourable.
Proof: Clearly if < M9R) is k-colourable then any finite
substructure of <M9R) is k-colourable.
To prove the converse, that if every finite
substructure of <M9R) is k-colourable then so also is < M9R) ,
we introduce a first order language for < M9R) and add to it
k unary predicates P , ...,P, and constants c for each a e M.
Let A be the following set of sentences of L:
R(c »ci.) for each pair <a9b) such that <a9b> e R
a' d r J
-R(c ,c, ) for each pair < a9b) such that <a9b) I R
Va:(P1(a:) v v Pfe(*))
Va;((P.(a;) -»--iP.(a?)) for each pair (i9j) with 1 < i?j < k
VxVy(P.(x) & P.(j/) + ->RU,z/)) for £=l,...,fc.
A has the same cardinality as M if M is infinite.
Now suppose every finite subgraph of <M9R) is k-colourable.
Let AQ Q A be a finite subset of A and suppose
M = {a , ...,a } is the finite subset of M consisting of
those elements a such that c occurs in A . By assumption
<M 9R n (Af x m )> is k-colourable. So there is a partition
of M into k disjoint subsets, S ,...,£, say, such that for
£=l,...,fc if a9b e S. then <a9b) i R. Take some a e M .
If a is the interpretation c for a I M then
<V* n (W'5l V{a>a£M0 u ^aW^ I" V ^
compactness we obtain a model 53= < B 9R* 9P ,. .. ,P, , {c } ^
for A in which P. is the interpretation for P. and c the
•z, r i> a
interpretation for c . The substructure of $, say 53 ,
with domain {c } ,. is also a model for A because each sen-
aaeM
tence in A is universal and hence valid in all substructures
of models of A (exercise 1.22(a)). The structure <BQ9R*> is
isomorphic to < M9R) since 53Q f= R(c ,e, ) if and only if

92 THE COMPLETENESS THEOREM AND ITS COROLLARIES
<a,b) e R. We define k disjoint subsets of M, Q ,...9Q, as
follows: a e Q. iff o e P. n Bn. Since
*i a v 0
350 |=Vi(P (a) v ... v P^(x)) then each a e M is put into at
least one set Q.. This set is unique because
$ ^Vx(?.(x) +-iP.(:c)) if i ^ j. Two connected elements
\i U J
are in different sets of the partition because
VxV y(P^(x) & P^iy) + -»RU,z/)) is valid in$Q. Hence < M 9R)
is k-colourable. □
This is the final example we shall give of the use of
the compactness theorem in this section. However it is
such a fundamental tool for model theory that it will be
used explicitly or implicitly in much of what follows.
Exercise 3.5. Show that there is no finite set Z of
sentences in a first order language L„ such that SI |= Z if and
only if A is infinite.
Exercise 3.6. Suppose T yT are theories in a language L
such that for any realization 9fl of L, 2fl |= T1 if and only if
2tt^ T . Show that TA and T are both finitely
axiomatizable. (We recall, from theorem 3.24 that T is finitely
axiomatizable iff there is some finite Z Q Form(L) such that
Z f- o for each a e T.)
Exercise 3.7. (Herbrand!s theorem) Suppose 3x<b(x) is a
universally valid existential sentence in a language L with
at least one constant. Show that there is a universally
valid sentence of the form (f)(?1) v ... v $(£ ) where for
£=l,...,w t. is a sequence of closed terms of L.
Exercise 3.8. Show that if S is a finite set and P a
partial ordering on S then there is a total ordering P* on S
extending P. Hence show, using the compactness theorem that
any partially ordered set <J,<> can be totally ordered by some
<* extending <.

THE COMPLETENESS THEOREM AND ITS COROLLARIES 93
Exercise 3.9. Show that there is no set of sentences Z of
a first order language L_ with, besides equality, one binary
predicate letter P such that for any realization 31 of L
SI |= Z if and only if P, the interpretation of P well orders
A.
Exercise 3.10. Show that the theory of torsion-free Abelian
groups is not finitely axiomatizable.
(The group <G, +, 0> is torsion free if for each non-zero new
and each x e G such that x f 0 x + x + ... + x f 0
n times
i.e. no element other than 0 has finite order).
Exercise 3.11. Suppose F is the theory of fields in a
language L with 0,1 , +, -, •. Let L* = L u {P} where P is a
unary predicate. OF is the theory generated by F together with
1. Vx(x = 0 v ?(x) v P(-x))
2. VxVy(P(x) & P(j/) + ?(x+y))
3. Va?(P(a?) +->P(-;c)).
If a; < y is defined to be P(y-x) then prove in OF that < is
a strict total ordering.
Show that there exist non-Archimedian models of OF i.e.
models in which there are elements a,b such that a9b e P and
for no natural number n does a + a + ... + a > b hold.
i t
n times
Exercise 3.12. Let X be the class of all realizations for
the first order language L. For each a e Sent(L) let
U = Wl: 9fte X & 9W Y 0} and let * be the topology on J
generated by the basis {Z7 :a e Sent(L)}. Show that the
compactness theorem for L is equivalent to the assertion: <Xf%> is
a compact space.
3.6. COMPLETENESS FOR THE PROPOSITIONAL CALCULUS
The Henkin-style proof of the completeness theorem
given in sections 3.2 and 3.4. can be adapted to establish
the completeness of an axiomatization of the propositional

94 THE COMPLETENESS THEOREM AND ITS COROLLARIES
calculus. The proof in section 3.2 assumes that each
instance of a tautology is provable. The full generality of
this property of our particular axiom system for the
predicate calculus is not used. Very few provable tautological
forms are quoted in the proof. It is sufficient to assume
that these particular tautologies are provable in the system.
Likewise, in order to prove the completeness of a system for
the propositional calculus using the Henkin method it is
sufficient to establish that a few selected tautologies are
theorems.
For the remainder of this section L will denote a pro-
positional language with propositional variables {P.:i e 1}
and connectives -., &. Formulae and the remaining
propositional connectives v, +, <* are defined as before (with a
few simplifications) (cf. page 18 ). A truth assignment
for L is a map v:Form(L ) + {T9F} such that
v(<t> & i|/) = T if and only if v($) = T and v(ty) = T
and v(-.((>) = !P if and only if v(<\>) = F
(j) e Form(L ) is a tautology if and only if v(<\>) = T for
all truth assignments v.
A is an axiomatization for the classical propositional
calculus with the following properties:
1) all axioms are tautologies;
2) if (J> is inferred from <|>1,...,<|> by one of the
rules of 4 and v is some truth assignment such
that v(4>) . = T for i = l,...,w then v((J>) = T;
3) modus ponens is a (derived) rule of 4 and the
deduction theorem is a metatheorem;
4) the following tautologies are provable in A :
(a) (-,((> + ♦ ) -► ((i(l) + -»♦) + (f>)
(b) <|> -► (♦ -► (<|> & ♦ ))
(c) ((> & i|/ ■* 4>, 4> & i|/ ■* i|;
for any <|>9i|/ e i?0r77?(L ).
(The system we have given clearly has these properties.)

THE COMPLETENESS THEOREM AND ITS COROLLARIES 95
Z c Form(L ) is consistent (relative to A ) if there is no
(J> e Form(L ) such that Z |- (j> and Z f- -»(J) where |-. denotes
A0 A0 Ao
a derivation from the axioms and rules of A . Z Q Form(L )
is complete if for each (j> e Form(L ) either E k (J) or
0
Z Q Form(LQ) has a model if there is some truth assignment
v such that t>((J>) = T for all (J> e Z.
Theorem 3.28. Suppose Z c Form(L ). Z is consistent if
and only if Z feas a model.
Proof: If Z |- (j> then it is straightforward to show by
Al
» 1 pnatVi n-F ^"h^ ^pri vatinn n-F <+* -F-rn-m T" -in z^
0
induction on the length of the derivation of <\> from Z in A
that a model for Z is also a model for ((>. This is an
immediate consequence of properties 1) and 2) of AQ. A
corollary of this analogue of theorem 2.6 is that a set of
sentences with a model is consistent.
To show that a consistent set of sentences has a model
we modify the construction in section 2. The steps A and C
of the proof are not necessary. The construction of a
complete consistent set Z* extending the consistent set Z is
almost exactly as in theorems 3.7 (in the countable case)
and 3.19 (in the uncountable case). A sequence of sets of
formulae {Z : a < 8) is defined such that for each a, Z is
consistent. Z = Z, Z is Z unless it is not the case
that Z I- 6 in which case Z^ . is Z u {-i(j> }, and Z. for
O 01 01+1 Ot 01 ■ A
limit X is (J Z . Then using the deduction theorem (pro-
a<X a
perty 3) and 4a we obtain a contradiction from assuming Z
consistent and Z . inconsistent. As before Z0 is N Z„
a+1 0 a^6 a
and is complete and consistent. For a complete consistent
set Z c Form(L ) a canonical truth assignment v is defined
as follows:
(i) y(P.) = 7 if and only if Z |- . P.,
(ii) v is extended to Form(L ) in the usual way, i.e.
i?((J> & i|/) = T if and only if v(<l>) = T and

96 THE COMPLETENESS THEOREM AND ITS COROLLARIES
i;(i|0 = T.
v(-i(JO = T if and only if v($) = F.
Then by induction on the length of (j> e Form(LQ) we show
v(<\>) = T if and only if Z |- . <\>.
For propositional variables this is merely a restatement ofthe
definition of y. If (J) is -i\\> then the induction hypothesis
implies that,i;(\|0 = 7 if and only if Z \- i|/. By consistency
if Z |- i|/ then not Z |- <j> and by completeness if not Z |- (j>
then Z |- -.(j). Hence v(\|0 = F iff Z \- 4 and so i; (<fr) - 21 iff
Z |- (J). If (J) is (J) & (J) then by the induction hypothesis
v(4>1> = T iff Z |- 4>1 and v{$ ) = T iff Z |- 4> . By the
assumptions 4) (b) and (c) on 4 we have Z |- <J> and Z |- <J>
just in case Z |- (J) & <\> . So tf ($) = T iff Z |- (J) which
completes the proof. D
Corollary 3.29.
(a) A is complete i.e. the theorems of An are precisely
the tautologies.
(b) If Z Q Form(L ) then Z has a model if and only if
every finite subset of Z has a model.
Proof: (a) Properties 1 and 2 are sufficient to ensure that
all theorems are tautologies. Conversely if not |- (j> then
as in the proof above {-i(j>} is consistent and hence has a
model. So all tautologies are theorems.
(b) is proved exactly as in 3.14. D

4
BEGINNING MODEL THEORY
4.1. THE LOWENHEIM-SKOLEM THEOREMS
The Lowenheim-Skolem theorems are, like the
compactness theorem, model-theoretic results which can be deduced
as straightforward consequences of the completeness theorem.
Both the Lowenheim-Skolem theorems concern the possible size
of models of satisfiable sets of sentences. So for this
section it is assumed that the language L„ has equality and
that all models are normal. The first theorem concerns the
possible lower bounds on the cardinality of models for
satisfiable sets of sentences.
Theorem 4.1. (AC) Downward Lowenheim-Skolem Theorem
If Z Q Sent(L„)j Z has cardinality k and Z has a model then
Z has a model of cardinality < k. (It is assumed that k is
infinite.)
Proof: If Z has a model then Z is consistent. Z has infinite
cardinality k just in case the language of Z has cardinality
k. Hence by theorem 3.20 Z has a model of cardinality < k.D
Lowenheim (1915) first proved a particular instance of
theorem 4.1. He showed that when Z is a finite set of
sentences (and hence the language of Z is countable) and Z is
satisfiable then Z is satisfiable in a countable domain. The
result was generalized by Skolem in 1920 to the case where Z
is a countably infinite set of formulae. The first Skolem
proof assumed the axiom of choice (as indeed does the proof
of the more general form of the theorem given in 4.1 above).
However the completeness theorem for countable sets of
sentences (and, more especially, theorem 3.16B) does not
require the axiom of choice. Hence the following special case
of theorem 4.1 may be proved without reference to the axiom
of choice.

98
BEGINNING. MODEL THEORY
Theorem 4.2. If Z is a countable satisfiable set of
sentences then Z has a countable model.
In 1922 Skolem published a new proof of theorem 4.2 which
did not depend on the axiom of choice.
One of the paradoxes of logic, the so-called Skolem
paradox, is a consequence of theorem 4.2. Using a
countable language it is possible to formalize a strong-enough
theory T for a system including the real numbers, in which
the proposition that the reals are uncountable is derivable.
The language of T contains the two predicates = and e, and
sets and functions are represented in the theory as elements
with special defining properties. Assuming that T has a
model (or, equivalently, is consistent) then theorem 4.2
implies that T has a countable model ©. There is no
inconsistency here for the following reason: the proposition
that the reals are uncountable is formalized by 'There is
no function f:R+N which is one-one1. In the model <S
there are elements of the domain representing the real
numbers, the natural numbers, and functions. The statement
that the reals are uncountable will be true in the model;
but that simply means that no element in the model satisfies
the formula: %x is a one-one function from R to N!. The
element R^ in the domain representing the reals may indeed
be countable; no contradiction occurs because the one-one
function from Br* onto the natural numbers will be outside
the model.
The compactness theorem and the downward Lowenheim-
Skolem theorem are both used to prove the so called upward
Lowenheim-Skolem theorem which is a non-trivial analogue
of lemma 2.24 for languages with equality. It establishes
that sets of sentences with an infinite model have models of
arbitrarily high cardinality.
Theorem 4.3 fACl Upward Lowenheim-Skolem Theorem.
Suppose Z Q Sent(L„) where L„ has cardinality k. If Z has
an infinite model then Z has a model of cardinality \ for

BEGINNING MODEL THEORY
99
each infinite X > k.
Proof: The argument is similar to that used in theorem 3.2 2.
Suppose X is a some cardinal > k. We extend L_ to a lan-
guage L* with cardinality X by adjoining a set of new
constants {b.:i e J} where I is some set with cardinal X.
Z* c Sent(L*) is defined to be the union of Z with the set
of all sentences of the form -»b. = b. where i ,j e I and
i f j. Consider a finite subset Z of Z*. Only finitely
many of the new constants b. ,...,b. occur in Z . By hypo-
thesis Z has an infinite model %. 31 can be expanded to a
realization for the language of Z*, by adjoining as
distinguished elements distinct a. ,...,a. e A for b. ,...,b.
and an arbitrary a e A, say a., for the other b.'s. Then
If Is
<$ » ^a-^i t* Is 2o" ^ compactness Z* has a model
$= ^n> tZ?.}- r> where 33n is a realization for L„. Since
b. f b. if i,j e I and i i- q then SB has cardinality > X. By
the downward Lowenheim-Skolem theorem Z* (with cardinality
X) has a model of cardinality < X, say < (5, {o^} . J . But
the form of Z* implies that any model has cardinality at least
X and hence (5 has cardinality exactly X. (5 |= Z and so the
proof is complete. □
Theorem 4.3 was proved in the countable case by Skolem
(1920) and by Tarski in the uncountable case. Just as we
may infer from theorem 3.22 that no set of sentences of a
first order language is valid in precisely the finite
realizations of L_ so we may infer from the upward Lowenheim-
Skolem theorem that there is no set of sentences
characterizing the realizations of a given infinite cardinality.
The generalized Lowenheim-Skolem theorems (4.1 and
4.3) are proved by appealing to the generalized
completeness theorem and its corollary, the compactness theorem, the
proofs of which depend upon the axiom of choice. This
dependence is intrinsic; either of the Lowenheim-Skolem

100
BEGINNING MODEL THEORY
theorems is sufficiently strong to imply the axiom of choice;
4.2. COMPLETENESS AND CATEGORICITY.
The completeness theorem shows that the relations h
and j- are interchangeable. So syntactic properties of
theories (or sets of sentences) can be expressed also in terms
of semantic notions and vice versa. As has already been
demonstrated in the compactness theorem and the Lowenheim-
Skolem theorems, model-theoretic properties are sometimes
most easily proved by considering their proof-theoretic
analogues. A further illustration of the kind of flexibility
in the metatheory implied by the completeness theorem is
given by an alternative model-theoretic characterization of
a complete theory. A preliminary definition is needed.
Definition 4.4. Suppose 31 and 33 are two realizations for
a first order language L. 31 is elementarily equivalent
to 33 (written 31 = 33) if and only if for each sentence
a e Sent(L) % |= a implies 33 |= a.
Elementary equivalence is an equivalence relation on the
class of structures for L since for any a e sent(L) and any
realization 3i for L either 31 |= a or 3i (= -a. So .31 = 33 iff
for each a e Sent(L) 31 (= o just in case 33 |= a. An example
of two elementarily equivalent structures was demonstrated
in theorem 3.25. The two structures 91 (the natural numbers)
and the non-isomorphic 9fl are both models for all the true
sentences in first order arithmetic. More trivial examples
are provided by any pair 31 ,33 of isomorphic structures.
Exercise 4.1. Suppose L is a countable first order
language, arid (5 some realization of L of cardinality k > w.
Show that for each infinite X there is a realization D of
L of cardinality > X which is elementarily equivalent to .<£.
See e.g. Bell and Slomson (1969), pages 83-4.

BEGINNING MODEL THEORY
101
Lemma 4.5. Z Q Sent(L) is complete if and only if all models
of Z are elementarily equivalent.
Proof: If Z is complete then (definition 3.1) for every
a e Sent(L) either Z |- a or Z |--»a. So by the completeness
theorem either Z |= a or Z ^-•a and hence for all models ®
of Z ® |= a or for all models ®, ® ^-»a. So any two models
of Z are elementarily equivalent.
Conversely suppose all models of Z are elementarily
equivalent. Then for all a e Sent(L) either Z |=o or I |= - a
which by the completeness theorem implies that either Z f- a
or Z |- -a. D
Complete theories are of interest for several reasons.
Mathematical applications can be made using the
characterization given in lemma 4.5. Suppose ® and X are two models
for a complete theory T. If a is a sentence in the language
of T which is true in ® then a is true in %m As a result of
this observation known properties of a familiar structure,
®say, may be inferred about a less familiar structure X
which is a model for the same complete theory T. Another
important application of the concept is concerned with the
decidability of a theory. This aspect is considered in more
detail in section 4.4.
Some theories T are, by definition, trivially complete.
For example, if 2ft is a realization for L then
Th(W = io:o e Sent(L) and 9fl \* o}
is complete because each sentence of L is either true or
false in 9fl. However in the more usual mathematical situation
a finite or recursive set of axioms Z is given for a theory
T (i.«e- T - {o e Sent(L) : Z j- a}) and the question is then
posed: is T complete? For example, P, Peano's axioms for
arithmetic written in a first order language, are true in
the intended interpretation, the natural numbers. Can all
sentences in the first order language for arithmetic be
decided in P? or, equivalently, does P generate the theory

102
BEGINNING MODEL THEORY
ThiW)? The answer to these questions is no (Godel 1931).
But now we consider how we might establish for a given
theory T that T is complete. A direct attempt to show that,
given any sentence a (in the language of T) , either a or -»a
is a theorem of T is unlikely to be successful for it is not
possible to consider all conceivable theorems of T in a
finite time. An alternative model-theoretic approach,
directly using the concept of elementary equivalence, is
again unsatisfactory because the infinite set of all
sentences of the language must be considered. The example
in theorem 3.25 illustrates that elementarily equivalent
structures are not necessarily 'alike1 in the algebraic
sense; that is, they are not necessarily isomorphic (although,
trivially, isomorphic structures are elementarily equivalent).
For the remainder of this chapter we will consider
alternative methods by which we may decide for a given theory T
if T is complete. Lemma 4.5 will be used to establish
tests for completeness and mathematical consequences of a
known complete theory T, rather than as a tool with which
to tackle directly the problem of the completeness of a
particular theory. Examples of elementarily equivalent
structures will follow immediately once we have established that
certain theories are complete.
Since isomorphic structures are elementarily
equivalent one way to establish that a given theory T is
complete is to show that all models of T are isomorphic.
However a corollary of the upward Lowenheim-Skolem theorem
is that any theory T (in a language with equality) with
infinite models has non-isomorphic models because models of
different cardinality are necessarily non-isomorphic. For
languages without equality a consistent theory always has
non-isomorphic models by lemma 2.24. Nearly all the
familiar mathematical theories and in particular all examples
to be considered here, are expressed in languages with
equality. So for the remainder of this chapter the first
order language L will have equality. Prompted by these
considerations we introduce two further definitions related

BEGINNING MODEL THEORY
103
to the algebraic structure of models of a particular theory.
Definition 4.6. Suppose T is a consistent theory in a
language L.
(a) T is categorical if all models are isomorphic.
(b) T is \z- categorical (where k is a cardinal) if
(i) T has a model of cardinal k
and (ii) any two models of T of cardinal k are isomorphic.
From the remarks preceding the definition it is clear that
any categorical theory can have only finite models. Such
theories do indeed exist.
Example 4.7. The theory T axiomatized by the sentence
asserting the existence of precisely n elements (exercise 2.16)
is trivially categorical because any two sets with n elements
are isomorphic as sets.
Example 4.8. A less trivial example is the theory of a
group of order 4 in which each non-identity element has order
2. This theory is axiomatized by the following:
Va?Vj/ V3((U.j/)-3) = (x,(y-z)))
V x(x *1 = x)
Vx 3 y(x*y = 1 )
V x(x'X = 1)
3x3y3z3w(->x = y & -• a? = z & -• a? = w &-»# = z
Vw(w -x^u-y^u-zyu- w)).
We have already noted that isomorphic structures are
necessarily elementarily equivalent, and hence it is trivial that
categorical theories are complete. The following lemma
provides a partial converse.
Lemma 4.9. A complete theory T Q Sent(L) with a finite
model is categorical.

104
BEGINNING MODEL THEORY
Proof: Suppose 21 is the given finite model of T. If 4 has
n elements then 21 |= a , where a is the sentence of L
asserting that there are precisely n elements (cf. exercise 2.16).
Since T is complete a e T. So if 99 is any other model of
T then SSwill also contain n elements. By lemma 4.5 51 = 53,
Now we must show that % is actually isomorphic to 99. This
we achieve by considering a finite sequence of alphabetic
extensions of1 L, say <L^ - L u {c ,...,c } : r=l,...,rc>
(where the c. are new constant symbols not occurring in L)
and then, supposing A - {a ,...,a } we show by induction on
r < n that, for some (suitably chosen) numbering {b ,...,& }
of B, we have
(*) <?l,a1,.. . ,a > = < 39,Z?1,. . . ,Z?r> (as structures for Lp).
Finally we construct an isomorphism h which sends a. to b..
First we consider the induction on r to establish (*).
When 2» = o there is nothing to prove since we already know
that 21 = 99. So now we assume
(%9a ,. . . ,a^> = <^&9b ,. . . ,Z?r> for some r < n
and Lr+1 = L u {ci'---»Cr»Cr+lK
Suppose it is not the case that
<«,a1,...,ar+1> = <33,Z?1,... ,br,b) for any b e B-{b± ,. . . 9bp}.
Then for each b e B-{b ,... ,b } there is some sentence
4>, ( c. ,. . . , c ,c J of I . with
<2l,a1,...,ar+1> t= *z,(c1,...,cr,c2i+1) and
<»,Z?1,... 9b) h"'^(c1,...,cr+1).
Now we consider the formula in L that is the (finite) con-
junction of
{<M c. ,. . . ,c ,#) :b e B-{b.9...9b}} u {-c. = x: i = l,. . . 9r}
DIP 1 P 1
which we denote by 6(c ,...,c 9x).
Now <a,a1,... ,ar> (= 6( c1,. . . , Cp ,*) [ar+1]
an "
d <»,ib1>...>ib > h 6(c ,...,<:,*) [2>]

BEGINNING MODEL THEORY
105
for any b e B-{b± fr^K
So <2I ,a ,...,a > |= 3aj6(c ,...,c ,#). But then by our
induction hypothesis < 53, Z? ,. . . 9b > (= 3a;6(c ,...,c 9x). This
is a contradiction since if
<$"»&«»•••yb) ^6(c ,...,c ,x) Ibl then necessarily
b f b. for i = l,...,r and so b e B-{b.,... ,b}. So there is
some b e 5- {£ ,. , . 9b } , which we will call b , such that
Now we can conclude that
and consider the map h: A -+ B defined by n(a.) - b. for
i-1,...,n.
If R is a k-ary predicate letter of L then for any
a . ,. ..,a . e 4
V **
21 ^ R[a. ,...,a. ] iff <«,a1,...,a> M(c, ••.••C. ).
By the elementary equivalence of <2l >a. ,. . . ,a > and
<»,ib1>...>ibn>
OI,^,..^) M(c. ....c. ) iff <58,&1 ... ,b > hR(c ,..,c. ).
in %\ %k in ^l ^fe
So SI l= R[a. ,...,a. ] iff <8 |= R[2>. ,...,£. ] or, equi-
valently, <a. ,...,a. > e # iff <n(a. ,...,n(a. )> e i? .
Similarly by considering the sentences of L
f(c. ,...,c. ) = c , c = c. (f, c are respectively
1 J function and constant
symbols of L)
we can show that
f\a. ,...,a. ) = a iff J*(fc(a. ),...,n(a. )) = fc(a )
^ I* . V ^1 ^-f P

106
BEGINNING MODEL THEORY
and Hoh = e$.+
So by exercise 1.7. 21 -$. D
Remark: At first sight it seems plausible that the use of
a well-ordering of the domain of 21 and transfinite induction
might enable us to extend the proof of lemma 4.9 to the
case where A is infinite. However we know that the Lowenheim-
Skolem theorems exclude this possibility. It is instructive
to observe just where the proof breaks down. Certainly if
21,53 |= T and T is complete, 21 infinite then 53 is also
infinite (21 is a model for: 'there are at least n elements1).
But consider the definition of the formula 6(c ,...,c ,x).
For this to be a formula it must be of finite length and so
the set B-{b 1,...,Z? } must be finite for our construction
to work. The essentially finite character of the expressions
of a first order language is what prevents us from
generalizing lemma 4.9.
The technique introduced in lemma 4.9 of adjoining to
the language L for the structure 21, constants for the
elements of A does have applications, however, in the case
where A is infinite. Some of these will be considered in
the next section.
Exercise 4.2. Show that if Z is categorical and the
language of Z contains only finitely many non-logical symbols
then there is a finite Z Q Z such that Z |- a for all
a e Z.
It is clear that a theory with both finite and infinite
models is not complete for the sentence 'there are exactly
n elements1 is undecided for s.ome finite rc. We now turn our
When we consider several realizations U,$B,2Betc. for
the language L we use the notation R 9R 9R etc. for the
interpretation of the predicate R in U,SB,2Betc. Similar
notations are used for function and constant symbols.

BEGINNING MODEL THEORY
107
attention to theories all of whose models are infinite.
Many mathematical structures of interest are infinite and
hence any (partial) axiomatization of the theory of such a
structure will not be categorical by the Lowenheim-Skolem
theorem. However there are examples of such axiomatizations
that are k-categorical for some cardinals k.
Example 4.10. The sentence which asserts that there are at
least n elements: 3 a; *xn^ & ^x '~xn ^ ^ axiomatizes
a K-categorical theory for each k > n.
Example 4.11. Suppose L is language with a single binary
predicate < (besides equality). We write x < y for <(x9y).
DLO (dense linear (or total) ordering without end points)
is the theory with the following axioms:
(i) V:c(-,:c < x)
(ii) VxVy(x < y v y < x v x = y)
(iii) V:c V y V z(x < y & z/ < z + x < z)
(iv) Va;Vj/(a; < y -*■ 3z(x < z & z < y ))
(v) Va: 3 y(y < x)
(vi) Vx 1 y(x < y) .
(i)-(iii) are the axioms for a strict linear ordering. (iv)
asserts that the ordering is dense, i.e. between any two
distinct elements lies a third. (v), (vi) assert that there
are no least or greatest elements in the ordering. Any
model of DLO is necessarily infinite since a linear ordering
of a finite set cannot be dense, and moreover always has a
least element. Two non-isomorphic models of DLO are <#,<> ,
the ordered set of rationals, and < i?,<> , the ordered set of
reals. A theorem of Cantor establishes that DLO is K -
categorical.
Theorem 4.12. (Cantor 1895). If <A,<A> and <5,<5> are two
countable models of DLO then < A,< > ^ <B,<„> .

108
BEGINNING MODEL THEORY
Proof: We assume that
A = {aQ9a±9 } and B = {bQ9b19 }
We do not assume that the order of enumeration of the domain
*
of either model bears any relation to the interpretation of
< in that model. To show that %= < A, < > and <8 = <5,< > are
isomorphic we exhibit a one-one function h from A onto B
which is order-preserving i.e. h(a) <„ h(a') iff a <. a'
for all a9a' e A. We begin by setting h(a ) = b . At the
2rcth stage in the construction of h we ensure that
h(a ),...9h(a ) have been defined and at the (2n+l)th stage
that bQ9. . . 9b are in the range. Suppose that at the mth.
* • • • i
iff
stage h has been defined on {a. ,...,a. } and for j = l,...,fe
3 3 3 3'
b <D b
r3 B r3>
Case 1. If m - 2n then there are two possibilities.
1.1. If a e {a. ,...,a. } then do nothing.
n fc^ ^-
1.2. If a /£ {a. ,...,a. } then consider the order
n ^1, ^,
relations holding between a and a. for j=l,...,fe. Since 5
is densely ordered by <„ and has no first or last element
there is a uniquely defined minimal p such that for
j=l,...,fc b <„ fr iff a„ <A a. . There are in fact in-
* 3 3
finitely many elements of B which are in the same order
relation to b ,...,Z? as a to a. ,...,a. but there is a
V rk n V **
first such b in the particular (well ordered) listing we
have adopted for elements of 5. Let h(a ) - b .
n p
Case 2. If m - 2n+l then again there are two cases.
2.1. If b e {b ,...,Z? } then do nothing.
2.2. If b I {b ,...,& } then there is a minimal q
n r^ * r« ^
su.ch that a < a. iff 2? <„ 2? for j = l,...,fe. Let
^ A ^ • W D V .
Because <.,<„ are strict orderings on 4,B respectively it
is immediate from the definition that h is one-one. h is

BEGINNING MODEL THEORY
109
defined on the whole of A and is onto B since by the
(2k+l)!th stage h(a,) has been defined and b-, is in the
range. By construction h is order-preserving and
consequently h is an isomorphism with the requisite properties. □
Categoricity in a countable power does not imply k-
categoricity for uncountable k as is demonstrated in the
following lemma.
Lemma 4.13. Suppose < R, <> is the ordered set of reals and
<#*,<> is the substructure of (R,<) obtained by deleting 0
from the domain. Then <R,<) is not isomorphic to <#*,<>.
Proof: Suppose (R,<) = <#*,<> and h: ffi + ffi* is an
isomorphism. For each non zero rc, — e R*. Let p be the inverse
r 7 n c n
1 1
image under h of —, i.e. hip ) = —. Then since h is order-
preserving p < p _ < ... < p . The strictly decreasing
sequence {p } is bounded below (by, for example, q where
h(q) = -1). So, since R is complete, {p } converges to
some p e R. h(p) < Mp ) for each n. Hence h(p) < 0. But
then there is some r e R* such that h(p) < r < 0 and
r < hip ) = — for each n. So since p is the greatest lower
_ -i
bound of {p } h (r) < p. This is a contradiction since
w new
^ is order preserving. Consequently such an isomorphism h
cannot exist. D
Corollary 4.14. DLO is not 2 -categorical.
Proof: <#,<> and <R*,<> are both models of DLO of cardinal
*\
Exercise 4.3. Let L be the language for DLO, $) a realization
of L, Th(<&) = {a:a £ Sent(L) & $)|=a}. Give finite axioma-
tizations for the following theories and show that they are
N -categorical:

110
BEGINNING MODEL THEORY
(i) Th« [0,1], <> )
(ii) Th(< [0,1),<> )
(iii) Th« (0,1] ,<> ).
Exercise 4.4. (i) Suppose <X9<) is a countable linearly
ordered set. Show that < X9 <> can be embedded in <#,<> .
When is <Xy<) elementarily equivalent to <#,<>?
(ii) Use the compactness theorem to show that any
linearly ordered set can be embedded in a dense linear
ordering without end points.
The following example demonstrates that precisely the
opposite situation to that for DLO can occur. There is a con-
*o
sistent theory which is 2 -categorical but is not K -
categorical.
Example 4.15. A recursive set of axioms for fields of
characteristic zero, F > was given in theorem 3.24. Suppose
ACFn is Fn u {P } where P is the sentence asserting
0 0 n n °
new
that every non-constant polynomial of degree n has a root;
i.e. pn is
V*nV *n-l ••• VV^rc = ° " 3*<*n*n + ^w-i^"1+ •• + ^o = 0))
where xm is an abbreviation for (... (x-x)>x)... x).
m times
ACF is a set of axioms for algebraically closed fields of
characteristic zero. The field of algebraic numbers, A, is
a countable model for ACF and the field of complex numbers
an uncountable model. A theorem of Steinitz (1910) asserts
that ACF is X-categorical for uncountable X. However ACF
is not N -categorical. Both A and the algebraic closure of
the field extension of A obtained by adjoining one
transcendental element are countable models for ACFn.

BEGINNING MODEL THEORY
111
Exercise 4.5. Suppose T„ is the theory (in the language L
with a unary function S and a constant 0) generated by the
following axioms:
(i) Vx(-n0 = Sx) ;
(ii) Va: Vz/(Sa; = Sy ■* x = y);
(iii) V^ha; = 0 -► 3z/(* = Sy));
(iv) Va;M = Sx), Vx(-,x = S(S*)), Va(-,a; = S(S(SU))),
..., Vx(-ix = S(S ... (Sx)...)),.. .
(a) Show that all models of T~ are infinite and that
< N, S, 0) is a model for 21-.
(b) Find another non-isomorphic countable model for T~.
(c) Show that if © |= T^ and ©has uncountable cardinality
k then ©is isomorphic to the disjoint union of
<N9 Sy 0) with k copies of <Z,£> (the integers together
with the successor function); deduce that T„ is k-
b
categorical.
We have exhibited examples of the following- types of theory
T:
(i) T is K-categorical for each k (example 4.10);
(ii). T is K -categorical but not 2 °-categorical
(theorem 4.12 and exercise 4.3);
(iii) T is X-categorical for uncountable X but not
K -categorical (example 4.15 and exercise 4.5).
The following important theorem is due to Morley and Shelah
(but will not be proved here).
Result 4.16. (Morley 1965, Shelah 1970) If T is a theory and
T is X-categorical fo.r some uncountable X then T is
X-categorical for each uncountable X.
Having established that k-categoricity is a meaningful
concept we return to the starting point for the discussion of
categoricity to consider how it relates to completeness.
Theorem 4.17. (Vaught 1954) Suppose T is a theory of car-

112
BEGINNING MODEL THEORY
dinality k with no finite models. If T is X-oategorioal for
some (infinite) X > k then T is complete.
Proof: Suppose T is not complete but is X-categorical for
some X > k. Then there is some sentence a in the language
of T such that neither T \- o nor T [-> o. So by lemma 3.6
T = T u {no} and T = T u {a} are both consistent. By the
completeness theorem, for £ = 1,2 T. has a model SW. which by
hypothesis is not finite. Then by the upward Lowenheim-
Skolem theor.em (4.3) T. has a model 9h of cardinal X. W
is a model for -.a and 9L for a. However we are assuming
that T is X-categorical so 9i and 9L are isomorphic
structures. Since isomorphic structures satisfy precisely the
same sentences this is a contradiction. Hence if T is
X-categorical then T is complete. □
Corollary 4.18 (a) DLC9 ACFand T~ (exercise 4.5) are
complete .
(b) < Q, <> = <#,<> and the field of algebraic numbers
is elementarily equivalent to the field of complex numbers.
Proof: (a) Theorem 4.17 is immediately applicable: DLO,
ACF and Ts are countable theories with no finite models;
DLO is K -categorical by Cantor's theorem (4.12) and ACF ,
T~ are k-categorical for each uncountable k.
(b) <£,<> and <#,<> are both models for DLO. The
field of algebraic numbers and the field of complex numbers
are models for ACF . The result now follows from lemma 4.5.D
This corollary demonstrates that Vaught's test (4.17)
is a useful technique with which to tackle the problem of
completeness. However there are complete theories which are
not K-categorical for any infinite k and for such theories
we must develop alternative methods for establishing
completeness. We mention here just one example of such a
theory, the theory of discretely ordered sets with first
but no last element. We denote this theory by f.... It has
the following axioms:

BEGINNING MODEL THEORY
113
(i) Va;(-ia; < x) \
(ii) Va;Vi/V'3(i < y & y < z + x < z) [ (< is a total
(iii) ViVj/(jj <yvy<xvy=x) ) ordering)
(iv) Vx(3y(y < x) + 3z(z < x $ Vw(w < x +
(w < z v w = z))))
(This says: every element with predecessors has an immediate
predecessor.)
(v) Vx(3y(x<y) -*■ 3z(x<z & Vw(x<w +(z < v v z = w))))
(Every element with successors has an immediate successor.)
(vi) 3xVy(x < y v x = y) (There is a first element.)
(vii) Vxly(x < y) (There is no last element.)
TDIS is not w0"categ°rical because, for example, linearly
ordered sets of type w and of type w + w* + w are countable
non-isomorphic models of the theory. Tr>rs is not 2
categorical either: if X denotes the (natural) order type
of the reals then ordered sets with order types
a) + (go* + u))X and w + (u)* + u))(X+l) provide non isomorphic
models of cardinality 2 . By Morley's result we infer
that TDIS is not k-categorical for any cardinal k. We
cannot, therefore, use Vaught's test here. In the following
section an alternative test for completeness will be used
to show that TDTq is nevertheless complete.
4.3. ELEMENTARY EMBEDDINGS AND MODEL COMPLETENESS
It follows from the results of the previous section
that complete theories exist having non-isomorphic models.
Elementary equivalence is therefore a coarser relation than
isomorphism on the class of structures for a given language
(that is, there are fewer equivalence classes). The
following definition introduces a new binary relation on the class
of L-structures which is strong enough to imply elementary
equivalence and yet does not imply isomorphism.
see e.g. Cantor (1895) for the definitions of
addition and multiplication of order types.

114
BEGINNING MODEL THEORY
Definition 4.19. If 21 £ $ then 21 is an elementary
substructure of $ if for all $(x) e Form(L) and a e A, 21 |= (j>[a]
implies 35 h <|>Ca]. We write 31 -< 33 and say $ is an
elementary extension of
We recall that for 21 and 33 to be elementarily equivalent
(definition 4.4) we stipulated that the same sentences be
true in both structures. The relation we are considering
here refers to all formulae. If 21 Q 33 then for % to be an
elementary substructure of 33 not only must the same sentences
be true in 21, and 33 but also a formula satisfiable in 21 must
be satisfied in 53 by the same elements of A.
Exercise 4.6. Show that !... 21 |= <fr[ a] implies 33 [= <fr[a]. . . !
in definition 4.19 may be replaced by ! .. 31 (= 4>[a] iff
33 |= ♦[2]...'.
Exercise 4.7. Show that •< is a partial ordering on the class
of L-structures.
Exercise 4.8. Suppose £, 3) ,(5 are structures of the same
type such that (5 -< (S ,$) < <g and gc^, Show that (5 ■< ©.
Definition 4.20. The embedding f:2l-»-33 is an elementary
embedding if /(2l)-< $6 . We write f:2l:^33. When such an
embedding exists 21 is said to be elementarily embeddable
in 33 .
An embedding from 21 to 33 preserves the algebraic structure
of 21 so that the image of 21 is an isomorphic copy of 21
inside 33. An elementary embedding preserves much more as is
demonstrated in the following lemma.
Lemma 4.21. Suppose 21, 33are (structures of the same type
and f: A+B is any map.
(a) / is an embedding iff for every atomic or negated
atomic formula <b(x) in L and ~a e A> 21 (= (f>[a] implies 33 |= <J>C/a];

BEGINNING MODEL THEORY
115
(b) / is an elementary embedding iff for every
formula <t>(x) in L and a e A, % [= (j>[a] implies $ |= <|>[/a].
Proof: The proof of (a) is left a4 an exercise. To prove
(b) we suppose firstly that / is an elementary embedding
according to definition 4.20. Suppose $(x) e Form(L) and
a e A: then since 21, f(%) are isomorphic &|=(l>[a] iff
/(2l) h *C/2] (exercise 1.15). So if 21 |= <fr[a] then, since
/(«)< $ and /a 6 /U) 39 |= *[/a].
Conversely suppose /:4 + B is a map such that for
every formula <t>(x) or L and a e 4, 21 ^ 4>[a] implies
33 f= <K/a]. We must show firstly that / is an isomorphism
between 21 and its image, /(2l) (definition 1.9). Suppose
t(x ,. . . 9x ) e Term(L) and (J>(z/ ,# ,. . . ,# ) is the formula
t(x±9.. . 9xn) = j/.
(We are assuming in this chapter that L is a language with
equality.) Then if t la ,...,a ] is 2? we have
* f= ♦C2>,a1,. . . ,an]
and hence 33 ^= <\>lfb9fa 9...9fa ] or, equivalently
Hence if g is a function symbol in L with interpretations
g^ and g® in 21 and 39 respectively then
/(^(a1,...,an)) = ^(/a^...,^)
(take t(x 9. .. 9x ) to be g(x 9. ., 9x )), and if c is a con-
ft? «\ Qf en
stant symbol with interpretations &> , <rO then f(c ) = <f°
(take £ to be c). Furthermore / is one-one (take the formula
-*x = y) .
21
Now suppose < a ,. . . ,a. , . *> e #.. Then if <j>(:c ,. . . 9x. . . * )
is the formula R (x. ,. . . 9x. , . . ) we have f= (j>[a ,. . . ,a^ , .. ]
and hence 39 |= Qlfa ,. . . ,/a, . .. ] , or, equivalently,
<^ai»---»^aX(i)> e *?' Conversely if < «!»••• >a\(i)) i Ri

116
BEGINNING MODEL THEORY
then consideration of the formula -iR. (a... ,a? ..) leads us
to conclude that <fa9...9fa^,..) £ Rr. So by exercise 1.7
we conclude that / is an isomorphism between $1 and /(9l).
Now let <b(x ,. .. ,x ) be any formula of L9
a1,...,an e A: If /(«) h *lfa±9...,fanl then
^H ^ta1,..t,a ] whence by our hypothesis,
*H ♦C/«1» - - - ,/a ]- So /<2D<<8 which completes the proof. D
It is a trivial consequence of the definitions that
if U is an elementary substructure of SB, or more generally,
if U is elementarily embeddable in SB then U=SB. If U = SB
then it is certainly not the case in general that U < SBor
even that U is elementarily embeddable in 58. Even if Uc$
and U = SB still no converse to the above result holds; each
of the following three possibilities can be realized:
(i) U < SB;
(ii) there is an / such that /:U ^ SB although U ^ $;
(iii) there is no / such that f :U 3 $.
Illustrations of these situations are given below.
Example 4.22. <£,<> < <#,<>. By corollary 4.18 (b) we
already know that <£,<> = </?,<> . Trivially <£,<> Q (R9<) .
Suppose that <i>(x9y) e Form(L) and for some q e Q 9 r e R
* t= *C?,r]. We show that then
(*) there is some q e Q such that ft |= <t>lq 9q Q].
The rationals in the sequence q form a finite linearly
ordered set which without loss of generality we may take as
q < q < ... < q . Then either r e Q (when there is
nothing to prove) or r < q or r > q or for some -£ = 1,. . . ,rc-l
a. < r < q. „ . In each of the last three cases it is pos-
sible to define an order isomorphism h:ft + ft such that
h(q .) = q. for j=l,...,rc and h(r) e Q. The last case is
3 V
illustrated diagrammatically:

BEGINNING MODEL THEORY
117
H + l
ql qi qO qUl qn
More precisely: h(x) = x for x < q . or x z q . -, let a be
^% n^ + l ' ^ 0
some rational such that q. < qn < q. „ and then define
ft(tf) = q^ + (x-q^^o-Qj) for q. < a? < r;
(r - qi)
hix) = *£ + l " (<7-:il-*ft*+l - <70) for r < a: < <^ + 1.
(*) follows immediately when h(r) is taken for q . Now it
is straightforward to show by induction on the length of
<\> that for q e Q
<G,<> MC?] implies </?,<> Mc?].
(*) is used for the induction step when (j> is of the form
Vxty(x).
Example 4.23. Suppose 7? = # n [0,«) and R = R n [1,«).
Then <R±94 Q <RQ9<> but it is not the case that
<R±9<> < ^q,^ , for suppose $(x) is ly(y < x), then
</?1,<> h-i«l] and <RQ,4 M^.
Moreover <#0,<> = < R±, <> since both are models for the theory
of dense linear orderings with first but no last element
which is complete by exercise 4.3 (ii) and Vaught's test.
If /: R + R is defined by fix) = x-l then / is an
elementary embedding from < R, <> to < R , <) (it is actually an
isomorphism) .
Example 4.24. Suppose A is the disjoint union of N -copies
of the positive rationals and K copies of the non-negative

118
BEGINNING MODEL THEORY
rationals; B is the disjoint union of K copies of the non-
negative rationals and K copies of the rationals.
Specifically:
A = {(a,4) : (0 < a < w & q > 0 & q e $) v (w < a < w &
q > 0 & q e #)}
5 = {(a,4) : (0<a<u)&q£0&<7€£)v
(a) < a < a) & qr e £) } . *
For both 4 and B a relation < is defined:
(*!><!!*> K (a2^2} i£f ai = a2 and *1 ^ ^2
Now take 21= < A, <> and 39= <5,<> and certainly 21 Q 33.
To show that 21 and 33 are elementarily equivalent we construct
an axiomatizable theory T9 say, for which both 21 and 33 are
models and then prove that the theory T is complete. T has
the following axioms:
(i) Vihi < x) y | ' < is a strict
(ii) Vx Vy Vz(x < y & y < z + x < z), ' partial order1
(iii) VxVyix < y + 3z(x < z & z < y))> !< is dense1
(iv) Vxlyix < y) 'there are no maximal elements1
(v) 3x. Ix ( & (-,*. = a:.) &
1 n 1<£<jsw * J
& Vi/C-ii/ < a;.)) for each n
l<i<n ^
'there are (at least) n distinct minimal elements1.
(vi) 3x 3x ( & (->#. = x .) & & (-.#. < ar.)
1 n l<i<o<n % ° l<i9j<n % °
& & Vy(y < x. v y = a: + 32(2 < 2/)))
l<i<n v v
for each n,
'there are (at least) n incomparable elements
x 9. . . 9x with no minimal element y < x. for i = l,...,n.!
(vii) VxVy(3z((x <zvx=zvz<x)l iy<zvy = zvz< y))
+ (x < y v y < x v x = y)) .
'a) is the second infinite initial ordinal and has
cardinal **.

BEGINNING MODEL THEORY
119
It is clear that 31 and 39 are models for this theory. We
leave it as an exercise to show that T is complete. (Hint:
show that T is N -categorical and apply Vaught!s test.)
Now we show, by contradiction, that there is no elementary
embedding from 31 into 39; for suppose /; 31 + 39 is an elementary
embedding. From considerations of cardinality for some
a > a) /(a,o) = ($,<?) for some 3 ^ w. Suppose <J> is the
formula 3x(x < y ). Then
31 h-.*[(a,0)] but 33h *[/(a,0)].
Hence / cannot be elementary.
The concept of elementary embedding can be reduced to
that of elementary equivalence by considering appropriate
expansions of the original structures. In Chapter 3
alphabetic extensions of a given first order language L were
constructed to provide instantiating constants for certain
derivable sentences of the form Ixfyix). Model-theoretic
considerations lead to the following general construction of
an alphabetic extension of a given language. (This
construction generalizes that of L in lemma 4.9.)
Definition 4.25. If 31 is a realization for L, L (31) is the
alphabetic extension of L obtained by adjoining to L a new
individual constant a for each a in A.
Even when the language L already contains a constant c that
is interpreted as a in 31 an additional constant a is
included in L (31), The expanded structure for L (31) in which
each new constant has its intended interpretation (as the
element to which it corresponds) is denoted by <3l 9A >.
Lemma 4.26. If f:A + B then f\% + 39 iff (%9A) e <33,/U)>
Proof: With each $ e Form L (31) we associate a <J> e Form(L)
as follows: suppose a ,...,a are the constants of L (51)
(and not in L) occurring in (j>; 4>0(y1> • • • >2/M) is tne formula

120
BEGINNING MODEL THEORY
obtained when each constant a. is replaced by a distinct new
variable y. not already occuring in (j>. Now suppose that
<(5,4> is some realization for the language L (51). We show by
induction on the length of <t>(x) e Form L (51) that
(*) <<M> I- +(a1,...,an)[S] iff C |= ♦0Ca1,...,an,S].
(*) is trivial to verify when <j> is atomic (using lemma 1.26) or
is of the form -ii|/, (f>1 & <|>2. So we turn immediately to the case
where <j> is VariKar). By tne induction hypothesis for each o e C
<<M> 1= *(a1>...fan)Co()fS ] iff « h *0Calf...fanfoofS].
So <<5,4> |= V^(a1,... ,an,*)[S] iff S |= v*i|;()[a1,. . . ,an,3]
or since 4>Q is V^Q(2/1,. . . ,z/n ,*),
<<5,4> |= *(a1,... ,an)[2] iff ff h *0Ca1>. . . ,an,2].
Now suppose /:5l^$. Then for <j> e Sen£ L+(5l) (and so
(j)Q e Form(L))
51 (= +0[alf...fan] iff 39 |= ^C^,. . . ,/an]
and then by (*)
<5M> (= « iff <8./U)> t= <J>
which implies that <51 ,^4> = <93,/(4)>. The converse follows
in a similar manner. D
Corollary 4.27. J/ 51 c 59 £ftew 51 is an elementary
substructure ofSQ iff <51,4> = <<B,4> .
We have already introduced existential and universal
formulae (exercise 1.22). A further classification of
formulae is helpful at this stage.
Definition 4.2 8. Suppose <J> e Form(L) and n z 0.
(j) e Vrc Form(L) iff there is a prenex normal form (j>f for ((>
such that <t>' has the form

BEGINNING MODEL THEORY
121
where Q is V if n is odd, 3 if n
n '
is even and ty is quantifier-free.
(j) e 3n Form(L) iff -i(J) e Vrc Form (I)
Vn Sent(L) = Vn Form(L) n Sent(L) and 3n Sent(L) is defined
analogously.
The important characteristic in this classification of
(prenex) formulae is not the number of quantifiers in the
formula but rather the number of alternations of quantifiers.
Some examples will help to clarify this idea. We suppose
that \\> is a quantifier-free formula:
Vx±V x2 3 y \fr € V2 Form(L)
V^V^Vi^ e Vl Form(L)
Vx±l y1V x2\\) e V3 Form(L)
For an arbitrary formula (J) the associated prenex normal
form (j> is not unique and so, according to our definition,
(j> may belong to more than one of the sets Vn Form(L) and
3rc Form(L). For example, suppose (j> is
lyty^y) -*■ 3a?i|>2(aO
where \K and \J; are quantifier-free. Then both
and 3w Vs(i|/ (a) + i|/ (w))
(where 2 does not occur in i|/ ,w does not occur in i|/ )
are prenex normal forms for <j>. So $ e V2 Form(L) n 32 Form(L).
As trivial corollaries to the definition we remark that the
set of quantifier-free formulae is a subset of Vo Form{L) (whicl
is the same as 30 Formal)); the set of universal formulae is
contained in Vl Form{L)\ the set of existential formulae is

122
BEGINNING MODEL THEORY
contained in 3l Form(L); and finally,
Form(L) = UVrc Form(L) (since trivially 3n Form(L)cVn+l Form(L)\
ne(° |- 3x${x) <* Vy3x<\>(x)
if y does not occur in 3x<t>(x)).
A weakening of the conditions for an elementary substructure
leads to the following definition.
Definition 4.29. If 21 Q 33 then 21 is an n-et'ementary
substructure of 33 if for all $(x) e Vrc Form(L) and a e A
21 f= 4>[a] implies »(=<k2]. We write 21 <n%
Exercise 4.9. Show that 21^: 33 iff 21 c 33 and for all
(j)(a;) £ 3n Form(L) and a e A
33 h *Ca] implies 2l|= *Ca].
Exercise 4.10. (a) Show that 21 £ 33 iff 2l<0$
(b) Show that 21 < 33 iff 21 <n 33 for all n.
Further characterizations of the relations £, < are obtained
when diagrams, a notion first introduced by Robinson, are
considered.
Definition 4.30. 21 is a realization for L.
(a) The open diagram of 21, A(2l) c Sent L+(2l) is
{(j>: <2l,4> ^ (J) and ((> is an atomic sentence or the
negation of an atomic sentence in L (21)}.
(b) The complete diagram of 21, Ac(2l) is
ThC&9A) = {a:<2l,4> f= a and a e Sent L+(2l)L
The open diagram is an encoding in the expanded language
L (21) of the structure of 21: for every (a ,. . . >ay,; ^ e R^
the sentence R . ( a. ,. .. ,a, , .. ) e A(20 and conversely if
< a1,... ,aX(i)> 4 Si then-Ri(a1 aX(i)) e A<21>; similarly,
fd(al au(j)) " a iff fJ-(ai'---'ay(j)) = a e A(SI)-
For example, when 21 is the field of integers modulo p,

BEGINNING MODEL THEORY
123
3 = < J" , + ,• ,0,1) then A(31) essentially gives the
multiplication tables for + and •. Trivially A(31) c Ac(3l) and Ac(31),
being the set of all true sentences in a structure, is
complete. The following exercise demonstrates the close
connection between the notions we have introduced in this
section.
Exercise 4.11. Show that:(a) there is an elementary embedding
f:3l ^53 iff there is an X c b such that <53,*> (= Ac (3D.
(b) there is an n-elementary embedding
f: 31 +n53 (i.e. f(3l) <n% ) iff there is an X c B such that
<53,X> |= Ac(3l) n.Vrc Sent L+(3l).
(c) there is an embedding /: 31 + 53 iff there
is an X c b such that <53,X> |= A(3l).
In lemma 4.5 we established a model-theoretic condition (in
terms of elementary equivalence) for a given theory to be
complete. An alternative condition in terms of elementary
embeddings is given in the following lemma.
Lemma 4.31. T is complete iff given any two models of T
31 .,53 there is a structure (S and elementary embeddings
f: 31 ^ G, g: 53 * <S
Proof: Suppose firstly that T is complete and that 31,53 are
any two models of Tv. By exercise 4.11(a) above for S to be
an elementary extension of 31 it is necessary and sufficient
that for some X c c <§,*> (= Ac(3l). So we must show that
for some £, X Q C9 Y c c we have
<G,J,Y> f= Ac(3l) u Ac(53)
where X is the set of interpretations for {a:a e 4} and Y
is the set of interpretations for {b :b e 5}. By the
completeness theorem it will be sufficient to show that
Ac(3l) u Ac(53) is consistent. We will work by contradiction.
If Ac(3l) u Ac(53) is inconsistent then some finite subset is
inconsistent; so there exist sentences (j>(a) e. Sent L (31),

124
BEGINNING MODEL THEORY
♦ (b) € Sent L (39) such that <% 9A> (=(|>(a), <39,S> (=^(S), and
(<Ma), *Mb)} is inconsistent. Hence 4>(a) F-»♦(?). The
constants b are distinct from a and so we may replace b by
distinct new variables y not occurring in <l>(a) or i|Kb) to
obtain <J>(a) \--^ty(y). Then by generalization <(>(a) f Vy^ty(y) .
Since <% 9A> \= 4>(a) it follows that <% ,A> \=Vy^(y) and hence,
since V#-ii|/(i/) e Sent(L) and 21 is complete, vi/-.i|/(2/) e 2\ We
infer that 39 |= Vy-tty(y). This is a contradiction since
39 (= ♦[£]. So our assumption, that Ac(9l) u Ac(39) is
inconsistent, is false. Now by completeness there is a model
<<S,J,7> |= Ac(5l) u Ac(39). If 1= {*a:a e ^} and we de£ine
/: 51 -*(£by /(a) = # then / is an elementary embedding (by
exercise 4.11(a)). Similarly we define an elementary
embedding g:Sd +£by gib) = yb where Y = -Cz/ ^: i> e 5}.
Conversely if 21,39 |= T and there exist f:5l ^$, #:39 ^ $
then 51 = (5 = 39 and hence by lemma 4.5 T is complete. D
As with lemma 4.5 the above lemma is not in general a
practical tool with which to try to establish the
completeness of a given theory. However we are still concerned to
establish sufficient model-theoretic conditions under which
a given theory T is complete and such that the conditions
are in practice sometimes verifiable. Given an arbitrary
structure ©which is a model for T then, in general, a
substructure <Sr is unlikely to be an elementary substructure
of <S. But suppose we focus our attention on those
substructures which are also models for T. We saw in example
4.22 that the structure <#,<> and its substructure <Q,<>
are both models for DLO and that in this case <£,<> < <#,<> .
Is it possible that given any substructure S of a structure
S) such that S), @ are both models for DLO then@<D? The
answer turns out to be yes. The situation is sufficiently
general to merit the introduction of a new definition.
Definition 4.32 (Robinson). T is mo del-complete if for
every pair of models of T9 <S,Xsuch that © Q X, <§ < X.

BEGINNING MODEL THEORY
125
An additional test for completeness follows.
Theorem 4.33. (Robinson's Prime Model Test 1956). If T is
model complete and there is a. X (= T such that X can be
embedded in every model for T then T is complete.
Proof: We aim to show that, under the hypotheses of this
theorem, any two models of T are elementarily equivalent so
that we can apply lemma 4.5.
Suppose U, 55 (= T. By hypothesis X is embeddable in U and 55
and so there are substructures U*,55* of U,55 respectively such
that X = U* = 55*. So, since X |= T then U*,35* h T. Hence by
model completeness it follows that U* < U and 55* ■< 55. So
U e U* e 55* = 55 which completes the proof. D
Although Vaught's test was used to prove the
completeness of DLO (corollary 4.18) the prime model test is also
applicable in this case. Here the 'prime model1 ($), embeddable
in every model of DLO) is <Q,<> . To prove that DLO is model-
complete requires a new technique. In example 4.22 we showed
that < Q, <> < <#,<> by constructing an isomorphism from < R ,<>
to itself which fixed a finite number of given rationals and
sent a given real to a rational. The isomprphism was defined
using the properties of R as an ordered field (i.e. the
operations of addition, subtraction, and division). In an
arbitrary model of DLO there is no analogue. A method which can be
used to establish that DLO is model-complete will be given
below (corollary 4.38).
An example of the application of Robinson's prime model
test to a theory for which Vaught's test cannot be used will
be given after we have established some useful equivalent
formulations of model-completeness. One such characterization
is a seemingly weaker condition on the models of a theory T.
It is an abstraction to the general case of a property of
algebraically closed fields.
Definition 4.34. If 21 j= T, 21 is existentially closed over
the theory T if for all <j>(5) e 3l Form(L) and a e A and any
53 j= T such that 21 c 55 if 59 |= 4>[a] then 3lf=*c2].

126
BEGINNING MODEL THEORY
Equivalently, 21 is existentially closed over T if for every
53 such that 21 £33 |= T, 21-^ $ .+
In the case where T is the theory of fields consider the
existential formula ly(x yn + x yn~ + ... + x - 0)
(where n > o). If J is some field, then in the usual
algebraic sense 5 is said to be algebraically closed if any non-
constant polynomial a yn + ... + a with coefficients in F
has a root in F. For any field 8 the polynomial
Yl
ay + ... + a always has a root in some extension field
of 5 (e.g. the extension obtained by adjoining the root!)
and hence we may say that 8 is algebraically closed if for
any a ,. . . ,a e F and any g* \= T such that 5 Q g*
if S*h ly(xnyn + ... + xQ = 0) [an,...,aQ] then
$ h 3y(xnyn + ••• + *0 = 0) Carc>- ••>ao]-
We now prove a general lemma which we shall use to show the
connection between model completeness and"existentially
closed structures over a theory T.
Lemma 4.35. If 21 Q 33 then for n > 0 the following are
equivalent:
(i) a <n+1s
(ii) there is some (S with 21 < (£., 33< (5
(iii) there is some Gt wi£7z 21 ■< (§, 33 < (§•
Proof: That (ii) =» (iii) is an immediate corollary of
exercise 4.10. (iii) =* (i) is left as an exercise (c.f.
exercise 4.8).
The hardest part of the lemma is to show (i) =» (ii). So
suppose 21 < .33 . By exercise 4.11 we must show that
Ac(2l) u [Ac(33) n Vn Sent L+(33)] (where the new constant for
a e A Q B is the same in both L+(2l) and L+(33)) has a model.
Suppose it does not. Then by compactness there exist
see Simmons (1972) for discussion of existentially closed
structures.

BEGINNING MODEL THEORY
127
^(S.a),..., * (S,a) e Vrc S\2rc£(L+(93))
such that <$,B> (= c|>.($,a) for £=l,... ,p
and Ac(2l) u {<\>1( b ,a) ,.. . ,(j> (S,a)} has no model.
(Here, 6 is a list of the constants corresponding to b e B-A
and a is a list of the constants corresponding to a e A).
The sentence 3~x & (j>.(J,a) e 3rc+l 5ewt L+(2D
\<i<p v
and Ac(2l) u {3a; & <|>.(a?,a)} is inconsistent.
l<i<p v
So<2i,4> f=v"S-, & <|>.(£,a) and
l<i<p ^
Va- & 4. (a,"a) e Vn+1 Sett£(L+(2i)).
l<i<p
By hypothesis 21 -< $ and hence
<S8 ,i4> (= Va?-, & <|>.(a?,a) which contradicts
l<i<p ^
591= 4>.C?,a] for each i.
So Ac(2i) u [Ac(39) n Vn 5ent L+($)] has a model <<5 ,BQ) say.
By a suitable renaming of the elements of B corresponding
to the constants {b:b e B} we may suppose
21 ■< S and 93 -< & as required. D
n
Now we return to the discussion of model-completeness and
prove the theorem relating it to the concept of Texisten-
tially closed1.
Theorem 4.36. The following are equivalent conditions on a
theory T:
(i) T is model-complete;
(ii) for every 21 h T, T u A(21) is complete;
(iii) all models for T are existentially closed over T.
Proof: (i) =» (ii) . • Suppose T is model-complete, 21 f= T but
T u A(2l) is not complete. Then there is some a e Sent L (21)
such that T u A(21) u {a} and T u A(21) u {-»a} are both con-

128
BEGINNING MODEL THEORY
sistent. We suppose without loss of generality that 21 |= a.
Because T u A(2l) u {-ia} is consistent it has a model <58,AT>
say. By exercise 4.11 there is an embedding f: S + 33 and,
by identifying 21 and jT20 we may assume $£$, % is model-
complete and so 21 < 33 and, in particular, for the sentence
-•a, since 33 |=->a then 21 ^-»a. This is a contradiction. So
T u A(9l) is complete.
(ii) =» (iii). Suppose that for every model 21 for T9
T u A($l) is complete. Let 21, $ |= T such that 21 Q 33 and
suppose (f)(5) e 3l Form(L) , a e 4 such that 53 |= <|>Ca]. Then
(J)(a) e Serc£ L (21) and hence is decided in T u A(31).
<33,4> Is 21 u A(51) by exercise 4.11 and hence T u A(2l) ^ 4>(a).
So <2i,4> (= <|>(a) and hence 211= 4>[a].
(iii) =* (i). Suppose all models for T are existentially
closed over T. We show by induction on n > 1 that for all
21,33 such that 21, 33 (= T and 2lc 33 , 2i <n 33. For rc=l this is
simply a result of 21 being existentially closed over T.
Now suppose the result holds for n-k^l and all 21Q 33,21 ,<& h Tm
By the induction hypothesis 21 < 33 . By lemma 4.35 (i) => (ii)
there is some (5 with 21 < (S and <®<k_1& • Since 21 < Sit
follows that (£ (= 2\ So, again by the induction hypothesis
since 58 £ § and 33, (5 h ^ $3 "<£ $ • So appealing to the lemma
again ((ii) =* (i)) we have 21 <« 1 33 • Now by exercise 4.10
we conclude that if 21Q33 and 21, 33 |= T then 21 < 33 i.e. T
is model-complete. D
Definition 4.37. A primitive formula is one of the form
3x & 4>.(a?,2/) where each $.(x9y) is either an atomic
l<i<?z v %
formula or the negation of an atomic formula.
Corollary 4.38. (Robinson's model-completeness test)
T is model-complete iff for all 21,33 (= T such that 21 Q 33
and all primitive <\>(y), a e A9 if 33 |= 4>[a] £7zerc 21 |= <|>[a].
Proof: First we assume the condition on the right. By

BEGINNING MODEL THEORY
129
theorem 4.36 to show T model-complete it is sufficient to
show that if 21 G 93 , 8 ,8 M then 21 *< 33. So suppose
ty(x) e 3l Form(L) and "^ |= \j;[a] for some a e A.
Since a quantifier free formula is equivalent to one in dis-
junctive normal form
formula of the form:
junctive normal form ty(x) is logically equivalent to a
3 2/ V $Ax9y)
l<i<n
where for i=l,...,n (J), is a conjunction of atomic formulae
and negations of atomic formulae.
So 5|=32/ V <!>.(£,i/) [a]. So for some i where
l<i.<n v
l<i<n ,93 h ly<kAx9y) [a] . ly$Ax9y) is primitive. So by
our hypothesis 2lf= 3y$ . (x9y ) la] and hence 51 |= i|/[a].
The converse implication is trivial. □
At the end of section 4.2 we showed that ?DIS (the
theory of discrete linear orderings with first but no last
element) did not satisfy the conditions for Vaught's test.
We cannot apply Robinson's prime model test directly either;
TDiq is not model-complete, as is readily verified by
considering the structures <#,<> and (N - {o},<> both of which
are models for TDI„y the second is a substructure of the
first but <N - {o},<> ■< <#,<> since they have different
first elements. Instead, we extend the language of TDlq by
adjoining a new constant 0 (for the minimal element) and a
binary predicate S (for the successor relation). Now we
consider the theory T* where T* is the theory generated by
tdis u ^Wx(x = ° ~ v# "• y < x)
VxVy(S(x>y) <*• x < y & -i 3 s (a; < z & s < y))}
We are going to prove that T* is complete by applying
Robinson's prime model test. It is clear that <N, <9S 90)
See e.g. Mendelson (1964) page 27 and exercise 2.8.

130
BEGINNING MODEL THEORY
will be embeddable in every model of T*. So we must now
show that T* is model-complete. We shall use Robinson's
model-completeness test. We suppose that 21, 53 |= T* 9 21 Q $
and 3xty(x9y) is a primitive formula, a e A such that
So there exist elements t e B such that $|=\|;[£,a].
The formula \K#,#) e Form(L) is the conjunction of formulae
of the form:
where £. e {£,#,0} for £=1,2.
We construct a new formula \\>*(x9y 9z) e Form(L) which is the
conjunction of atomic formulae of the form
t± < t2, S(t±9t2)
(we eliminate those of the remaining four forms listed above)
such that
Sb |= 3s\j;*(i,J,s)[?,a] and for a* e A
21 |= l~z\\)*(x9y ,s)[a*,a] just in case 21 (= \j;[a*,a].
->■->■ 7?
With each term £ in {tf,z/,0} we associate an element t of 5
as follows: (i) if t is i. then t = &.,
(ii) if £ is w. then t = a.,
9 3 3
(iii) if t is 0 then £5 = 0® (= 031).
We are now ready to construct ty*.
A) Firstly we replace each conjunct of the form
-i S(t1 ,£2) in i|/ .
Since SB |= ♦C?,2] it follows that 59 |=-i S[£* ,£*].
Replace-.S(*1,*2) by (i) 12 < ^ if *2 < *f;
(ii) *2 = * if t\ = *J;

BEGINNING MODEL THEORY
131
(iii) t1 < z^ & z^ < t2 if there
is a b* e B with
tB± < b* < t\ and
-*S{t19t2) is the i'th
conjunct of i|/.
B) Now we replace each conjunct ->t1 < t7 by
(i) t2 < tx if t\ < tj;
(ii) *2 - tx if tj = t\ (»H-.tJ < **).
C) Thirdly we replace each conjunct -tt± = £2 by
(i) t± < t2 if tj < tB2;
(ii) *2 < tx if ** < *J.
D) The transformed formula is now the conjunction of
formulae of the form: t < t , S(£ >t ), t - t .
(a) If each conjunct is of the form t± - t7 then we
define ty* to be 0 < z .
(b) Otherwise for each conjunct of the form £ = t2
replace each occurrence of t„ in the other con-
juncts by t± and drop t± - t2.
By construction it is apparent that ty*(x9y,z) has the
following properties:
(i) 33(= 3^*(J,£,?)[£,2];
(ii) for each a* e A
«|=iH«*»2] iff 21 (= 3si|;*(S,J,3)Ca*,a].
Since we are trying to show that 911= \^[a*,a] for some
a* e A it will be sufficient to prove that
911= \\)*[.a* >a,c~\ for some a* 9c e A.
In the case where ty* is 0 < z± the result is immediate,
we consider case D) (b) above. We know that for some d
we have 53 f* ^*[£,a,2].
Firstly we show that if 2? e 5, a,ar e .4 and:
Now

132
BEGINNING MODEL THEORY
(i) b <B a (or a <B b) and there are finitely many
elements in B between b and a
or (ii) a <B b <B a' and there are finitely many elements
in A between a and a'
then b € A.
In the first case 93 (= S[fr,e ] & ... & S[e ,a] for some
&^,..•,e^ £ 5 •
Since T* (- V^3!z/ S(x,y) & Vs(-.3 = 0 -> 3! w S(w,s))
and S& = S® n (A x 4) it then follows that 2>,e ,...,e ,a e A.
(ii) is proved in a similar way.
We must find a*,c e .4 to correspond to ?,2 e B such that
the same order relations hold between corresponding elements
and a and, further, when SB (= S[fr ,2? ] then 31 (= S[a*a*]
(a* corresponds to &.)•
If b € $ (or 2) and b e A then there is no problem. (Take
b to correspond to b). Suppose a - a±9...,a where
a. < .... < a .
For those elements b e £,2 not in 4 one of the following
holds:
(i) 0 < b < a and there are infinitely many
1 a
elements in A between 0 and a •
(ii) a. < fr < a. . and there are infinitely many
elements in 4 between a^ and a^+1;
(iii) a < & and there are infinitely many elements
in B between an and b .
In each case it is clear that we can find a* e A to
correspond to b e B such that the order and successor relations
are preserved. (In case (iii) it may happen that there are
finitely many elements between a* and a . We are only
concerned that if ^\=Slai9bl then a(=S[a^,a*] and not that if
$ 1= -«S[a. ,2>] then 21 (= iS[c.,c*].)
This completes the proof that 21 (= Ha*,a] and hence by

BEGINNING MODEL THEORY
133
corollary 4.38, that T* is complete.
We now wish to show that TDIS is complete.
Suppose a e Sent(L) where L is the language of TDIS. Since
T* is complete (and a is a sentence in the language of T*)
either T* [■ a or T* |—i a. Without loss of generality suppose
<t> 1,.. . ,4>n = a is a derivation of a in T*. The constant 0 and
the predicate symbol S may occur in the derivation (although
not in a). However we replace an atomic subformula A(t90)
in (j>. by 3y(A(t9y) & Vs(-is < y)) and each atomic subformula
S(t±9t2) by t1 < t2 &-.3s(*1 < z & z < t2).
Let "$". denote this new formula of L. If <J> - is an axiom of
T* then ^ is in TDIS- Hence o" (= a) is in TDIS* So, finally,
we have shown that TDIS is complete.
Exercise 4.12.(a) Show that the theory of discrete linear
orderings with last but no first element is complete.
(b) Show that the theory of discrete linear
orderings with first and last elements is not complete.
Exercise 4.13. T± is the theory of dense linear orderings
with a first but no last element in the language with =, <.
Show that T is not model-complete but that if T is the
same theory in an extended language with =, < and 0 then T
is model-complete.
A theory T has the joint embedding property (JEP) if given
any two models of T9 U, SB there is a model 2B of T and embed-
dings f: U+2B, g:<& +2B.
Exercise 4.14. Show that the following are equivalent:
(i) T has the JEP;
A similar (but simpler) argument is used to show DLO
is model complete. In this case the language does not have
to be extended and ty* is a conjunction of formulae of the
form t < tr.

134
BEGINNING MODEL THEORY
(ii) for every (J>, i|/ eVl Sent(L) if T |- <|> v i|; then
T |- <|> or T [ i|/
(iii) for every <b, i|/ e 3i Sent(L) if T u {(J)}, 21 u {i|/}
are consistent then T u {<\> & i|/} is consistent.
Exercise 4.15. , Show that the theory of groups (in a
language with •, 1) has the JEP but that the theory of fields
does not.
Exercise 4.16. Show that if T is model-complete and has
the JEP then T is complete.
Exercise 4.17. Show that T is model complete iff given
31,53 h 2\ 31Q58 , $(x9y) e Form(L) , a e A, b e B if
$3 (= (J>[a,fr] then for some a e A 53 f= <l>[a,a].
Exercise 4.18. Show that if T is model-complete then 21 is
axiomatizable by V2 Sentences.
Exercise 4.19. Suppose 31 |= T. Show that the following are
equivalent:
(i) 31 is existentially closed over T;
(ii) if 31 |= fylal for some <t>(x) e Vl Form(L), a e 4 then
S7 u A(3l) I- 4>[a];
(iii) if 311= <()[a] for some ((>(#) e Vl Form(L) , a e 4 then
ttfiere is 6(:c) e 3l Form(L) such that
31 h ec2] and r f=v*(e<£) "* *(*))-
Exercise 4.20. Suppose 93,2Bf= T such that 53 <± 2B and SB
is existentially closed over T. JShow that SB is existentially
closed over T.
A chain is a sequence of structures <3I :a < 3> of the same
type such that for a < a < 3 31 Q 31 . The union of
the chain is the unique structure 31 (of the same type) with
domain A = \J A a such that for a < 3 3laQ 31 .

BEGINNING MODEL THEORY
135
Exercise 4.21. Suppose <<& :a < 3> is a chain of structures
such that for a < a9 < 3 <§ < <5 . Show that the union
of the chain is an elementary extension of each <& .
Deduce that if T is model-complete then the union of any
chain of models of T is a model of T.
Exercise 4.22. (Lindstrom's theorem 1964).
Suppose T is a theory in a countable language such that
(i) all models of T are infinite;
(ii) the union of any chain of models of T is a model of T.
Prove that T has an existentially closed model of each
infinite cardinality k.
If, further, T is K-categorical for some infinite k show
that T is model-complete.
4.4. COMPLETENESS AND DECIDABILITY.
We close with some elementary observations on the
consequences of completeness concerned with decidability. A
comprehensive study requires knowledge of recursive function
theory and so outline proofs only are given.
At the end of the first chapter examples were given of
formulae $ for which the question: !Is <\> logically valid?1
could be answered using a well defined method, a decision
procedure. By the completeness theorem, for such a formula
(j> the question: !is (j> derivable (from the empty set)?1 is
also decidable. A mathematician is in general concerned not
with logically valid formulae (j> but with formulae (J> valid
in all models of some theory T, such as groups, fields, etc.
Again appealing to the completeness theorem, the question
is essentially: 'given (j> in the language of T is it the
case that T |- $ ?! The completeness of certain (countable)
T has an important consequence bearing on this problem.
Definition 4.39. T is a consistent countable theory. T is
finitely (recursively) axiomatizable if there is a finite

136
BEGINNING MODEL THEORY
(recursive) subset T Q T such that for all (j> e T, T \- <\>.
Theorem 4.40. If T is a complete recursively axiomatizdble
theory then T is recursive (decidable).
Proof: We must show that there in a recursive procedure to
determine of any sentence a in the language of T whether
or not o e T. Since T is complete we know that given a
either a e T or-10 e t. We let $. ,4>2,.. . be a recursive
enumeration of the recursive set of axioms for T. At the
nth stage we consider all those theorems derivable from
(J> ,...,6 in at most n steps. This is a finite set. At
some (finite) stage in this procedure either a or-ia will
occur as a theorem. So, since T is consistent, we can
determine if a e T. □
Exercise 4.23. Suppose J is a consistent theory with no
infinite normal models and the language of T has only finitely
many predicate, function, and constant symbols. Show that T has
only finitely many non-isomorphic models and that T is decidable.
Exercise 4.24. Suppose T is a recursively axiomatizable
theory with only finitely many distinct theories T .(l<i<m)
such that T Q T.. Show that all the T. and T are decidable.

FURTHER READING
We finish with a few suggestions for further reading
on model theory for the interested reader.
Chang and Keisler (1973) is a very comprehensive text
on model theory that must now count as essential reading
for a serious student of the subject.
Robinson, whose work on model theory during the
fifties and sixties %is fundamental in the subject, wrote several
texts. The most recent edition (1965) includes most of the
material of our Chapter 4 in greater detail together with
other important topics.
Bell and Slomson (1969) approaches the subject via
Boolean algebras and the ultraproduct construction. (It
includes a proof of the completeness theorem using Boolean
algebras.)
Sacks1 (1972) elegant and concise book includes a
proof of Morley's result (4.16) and other related theorems.
The selection we have given is in no way comprehensive.
Each of the above texts contains a lengthy bibliography
with still more suggestions of books and papers on model
theory that should provide sufficient stimulus for the
keenest student.

REFERENCES
Aczel, P. (1973). Infinitary logic and the Barwise
compactness theorem, in: The Proceedings of the Bertrand
Russell Memorial Logic Conference, Denmark 1971,
J. L. Bell, J. Cole, G. Priest and A. B. Slomson,
Eds. 234-277 (B. Russell Logic Conference, Leeds).
Bell, J.L. and Slomson, A.B. (1969). Models and ultra-
products, (North-Holland, Amsterdam).
Beth, E.W. (1955). Semantic entailment and formal deriva-
bility , Mededelingen der Koninklijke Nederlandse
Akademie van wetenschappen, afd. letterkunde, n.s.,
JL£ 309-342,
Cantor, G. (1895). Beitrage zur Begrundung der trans-
finiten Mengenlehre , Math. Ann. £6, 481-512 (English
translation in: Contributions to the Founding of the
Theory of Transfinite Numbers (Dover, New York 1915)).
Chang, C.C. and Keisler, H.J. (1973). Model theory,
(North-Holland, Amsterdam).
Church, A. (1936). A note on the Entscheidungsproblem,
J. Symb. Logic ^L 40-41, correction ibid. 101-102.
Enderton, H.B. (1972). A mathematical introduction to logic,
Academic Press, New York).
Gandy, R.O. (1973). 'Structure* in mathematics, in
Structuralism: an Introduction, D. Robey, Ed.
(Clarendon Press, Oxford).
Godel, K. (1930). die Vollstandigkeit der Axiome des
logischen Funktionenkalkuls, Monatsh. Math. Phys. 37,
349-360 (English translation in: From Frege to GodeT,
J. van Heijenoort, Ed. 582-591 (Harvard 1967)).
(1931). fiber formal unentscheidbare Satze der Prin-
cipia Mathematica und verwandter Systeme I, Monatsh.
Math.Phys.38, 173-198 (English translation in: From
Frege to GocTel. J. van Heijenoort, Ed. 596-616 (Harvard
1967)).
Halmos, P.R. (1960). Naive set theory,(Van Nostrand,Princeton).
(N.B. Latest edition published by Springer-Verlag,Berlin).
Henkin, L.A. (1949). The completeness of the first order
functional calculus, J. Symb. Logic L4, 159-166.

REFERENCES
139
Henkin, L.A. (1950). Completeness in the theory of types,
J. Symb. Logic !L!5, 81-91.
Herbrand, J. (1930). Reoherohes sur la theorie de la
demonstration, Trav. Soc. Sci. Lett. Varsovie, .Classe III 3j5
(English translation of Ch.5 in: From Frege to Godel,
J. van Heijenoort, Ed., 525-581 (Harvard 1967).)
Kleene, S.C. (1952). Introduction to metamathematies9
(Van Nostrand, Princeton).
Kreisel, G. and Krivine, J.L. (1967). Elements of
mathematical logic: model theory, (North-Holland, Amsterdam).
Lemmon, E.J. (1965). Beginning logic, (Nelson).
Lindstrom, P. (1964). On model completeness , Theoria (Lund)
3£, 183-196.
Lowenheim, L. (1915). Uber Mogliohkeiten inx Relativkalkul,
Math.Ann. 76, 447-470 (English translation in: From
Frege to Goclel, J. van Heijenoort, Ed., 228-251
(Harvard 1967)).
Malcev, A. (1936). Untersuchungen aus dem Gebiete der mathe-
matischen Logik, Rec. Math. N.S.3^, 323-336.
Mendelson, E. (1964). Introduction to mathematical logic,
(Van Nostrand, Princeton).
Morley, M. (1965). Categoricity in power, Trans. Am. Math.
Soc. 114, 514-538.
Rasiowa, H. and Sikorski, R. (1950). A proof of the
completeness theorem of Godel, Fund. Math. _32, 193-200.
Robinson, A. (1956). Complete theories, (North-Holland,
Amsterdam).
(1965). Introduction to model theory and to the
metamathematics of algebra, (North-Holland, Amsterdam).
Rogers, H. (1967). Theory of recursive functions and
effective computability9 (McGraw-Hill, New York).
Sacks, G. (1972). Saturated model theory, (Benjamin).
Shelah, S. (1970). Solution of Zos's conjecture for
uncountable languages, Not. Am. Math. Soc. 11_, 1968.
Shoenfield, J.R. (1967). Mathematical Logic, (Addison-
Wesley, Reading, Mass.).
Simmons, H. (1972). Existentially closed structures , J.Symb.
Logic ll_, 293-310.

140
REFERENCES
Skolem, T. (1920). Logisch-kombinatorische Untersuchungen
uber die Erfullbarkeit oder Beweisbarkeit mathema-
tischer Satze nebst einem Theorem uber diolnte Mengen,
Skrifter utgitt av Videnskapsselskapet i Kristiania,
I. Mat. Naturv. Kl.£. (English translation in:
From Frege to Godel, J. van Heijenoort, Ed., 252-263
(Harvard 1967)) .
(1922). Einige Bemerkungen zur axiomatisohen
Begrundung der Mengenlehre, Mathematikakongressen i
Helsingfors den 4-7 Juli 1922, Den femte skandanaviska
matematikakongressen, Redogorelse (Akademiska
Bokhandeln, Helsinki 1923) (English translation in:
From Frege to Godel, J. van Heijenoort, Ed., 290-301
(Harvard 1967)).
Steinitz, E. (1910). Algebraisohe Theorie der Korper,
J. Reine Angew. Math. 137, 167-309.
Tarski, A. (1935). Der Wahrheitsbegriff in den formali-
sierten Sprachen, Studia Philos. (Warsaw) 1L, 261-405
(English translation in: Logic, Semantics and
Meta-mathematics 152-278 (Clarendon Press, Oxford 1956)).
Tarski, A. and Vaught, R. (1957). Arithmet ioal extensions
of relational systems, Compositio Math. L3, 81-102.
Vaught, R. (1954). Applications of the Lowenheim-Skolem-
Tarski theorem to problems of completeness and
decidability , Koninkl. Ned. Akad. Wetensch. Proc.
Ser. A _57 (Indag. Math 16 467-472).
Wang, H. (1952). Logic of many sorted theories* J. Symb.
Logic 1_7, 105-116.

INDEX
algebraically closed fields 11
alphabetic extension 68
antisymmetric relation 3
atomic formula 17
axioms of
choice 2
extensionality 1
axioms
for equality 48
logical 41
prepositional 41
for quantifier 41
Beth 85
bijection 2
bound variable 19
bracket conventions 20
canonical structure 73, 77
Cantor 107, 113
cardinal 5
exponentiation 5
product 5
sum 5
Cartesian product 2
categorical 103
chain of structures 134
choice
axiom of 2
function 3
Church 35
closed term 73
closure 22
compactness theorem 76
complete
diagram 122
formal system 67
completeness
of the prepositional calculus
theorem 67, 76
connected relation 3
consequence, logical 38
consistent 49
constant
Henkin 68
in a structure 7
contravalid formula 34
countable set 5
deduction theorem 50
denotation of a term 24
dense linear order 10 7^25
derivation 4
diagram
complete 122
open 122
discrete linear order
112, 129-133
distinguished element 7
domain of a
function 2
structure 7
downward Lowenheim-Skolem
theorem 97
duality, principle of 57
elementarily equivalent
100
elementary
embedding 114
extension 114
substructure 114
embedding 15
elementary 114
n-elementary 12 3
empty set 1
equality 58
axioms 58
equivalence, elementary
100
existential
sentence 39
quantifier 18
existentially closed 125
expansion 2 3
extension 13
alphabetic 68
elementary 114
95 extensionality, axiom of 1
fields
algebraically closed 110
of characteristic zero
88
theory of 87
finite set 5

142
INDEX
finitely axiomatizable 87, 135
first-order language 16
formula
atomic 17
contravalid 34
primitive 128
refutable 34
satisfaction of 25
satisfiable 34
well-formed 17
free
for a variable 21
variable 19
full 68
function 2
generalization 41
GSdel 67, 76, 102
graph 90
groups
axioms for 62
torsion-free 93
Henkin 67, 76, 85
constant 68
Herbrand 92
homomorphism 14
implication, logical 38
inconsistent 49
independence of axioms 51
individual
constant 16
variable 16
induction on the length
of a formula 29
infinite set 5
initial ordinal 5
instance of a tautology 44
intersection 2
isomorphism 15
joint embedding property 133
K-categorical
k-colourable graph 90
language
with equality 58
first order 16
limit ordinal 4
linear order
dense 107, 125
discrete 112, 129-33
logical
axioms 41
connectives 16, 18
consequence 38
implication 38
logically valid formula 34
Lowenheim 9 7
-Skolem theorem, downward
97
-Skolem theorem, upward
98
Malcev 85
metalanguage 52
metatheorem 52
model 34
model-complete 124
model-completeness test 128
modus ponens 41
Morley 111
n-ary relation 2
n-elementary
embedding 123
substructure 122
normal
contraction 60
realization 61
one-one function 2
onto function 2
open diagram 122
order
partial 3
total 3
well 3
ordered
n-tuple 1
pair 1
ordinal 4
initial 5
limit 4
successor 4
partial
order 3
ordering 3
predicate letter 16
prenex normal form 54

INDEX
143
prime model test 125
primitive formula 128
principle
of duality 57
of transfinite induction
product 2
propositional
axioms 41
rule of inference 41
purely relational structure
quantifier
axioms 41
existential 18
rule 41
universal 16
range of a function 2
Rasiowa 86
realization 17
normal 61
recursively axiomatizable 135
reduct 2 3
reflexive relation 3
refutable formula 34
relation, n-ary 2
relational structure 6
Robinson 122, 124, 125, 128
rule of inference, propositional
satisfaction 25
satisfiable formula 34
scope 19
sentence 22
existential 39
universal 39
Sikorski 86
similar type 12
Skolem 97, 98
paradox 98
soundness theorem 48^
Steinitz 110
strict order 3
structure
canonical 73, 77
relational 6
subformula 18
subset 1
substructure 13
elementary 114
n-elementary 122
successor ordinal 4
Tarski 99
tautological instance 44
tautology 94
term 17
closed 73
denotation of 24
free for a variable 21
theorem of the predicate
calculus 42
theory 49
of fields 87
of groups 62
torsion-free groups 93
total order 3
transfinite induction,
principle of 4
transitive
relation 3
set 4
true in a structure 33
truth assignment 94
type
similar 12
of- a structure 12
union 2
of a chain 134
universal
closure 22
41 quantifier 16
sentence 39
universally valid
formula 34
upward Lowenheim-Skolem
theorem 98
valid in a structure 33
validity
logical 34
universal 34
variable
bound 19
free 19
Vaught 111
well-formed formula 17
well order 3
well-ordering theorem
3, 81
Zorn's Lemma 3