Mathlogicp1 PDF
Mathlogicp1 PDF
Mathlogicp1 PDF
Joseph R. Mileti
1 Introduction 7
1.1 The Nature of Mathematical Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 The Language of Mathematics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3 Syntax and Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.4 The Point of It All . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.5 Some Basic Terminology and Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3 Propositional Logic 29
3.1 The Syntax of Propositional Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.1 Standard Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.1.2 Polish Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.3 Official Syntax and Our Abuses of It . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.1.4 Recursive Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2 Truth Assignments and Semantic Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3 Boolean Functions and Connectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Syntactic Implication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.2 Official Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.3 Examples Of Deductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.4 Theorems about ` . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Soundness and Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.1 The Soundness Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.2 The Completeness Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Compactness and Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3
4 CONTENTS
Introduction
One successful result of such a program is that we can study mathematical language and reasoning using
mathematics. For example, we will eventually give a precise mathematical definition of a formal proof, and to
avoid confusion with your current intuitive understand of what a proof is, we’ll call these objects deductions.
You should think of this as analogous to giving a precise mathematical definition of continuity to replace the
fuzzy “a graph that can be drawn without lifting your pencil”. Once we’ve codified the notion in this way,
we’ll have turned deductions into mathematical objects and this allows use to prove mathematical theorems
about deductions using normal mathematical reasoning. Thus, we’ve opened up the possibility of proving
that there is no deduction of a certain statement.
Some newcomers to the subject find the whole enterprise perplexing. For instance, if you come to the
subject with the belief that the role of mathematical logic is to serve as a foundation to make mathematics
more precise and secure, then the above description probably seems a little circular and this will almost
certainly lead to a great deal of confusion. You may ask yourself:
Okay, we’ve just given a decent definition of a deduction. However, instead of proving things
about deductions following this formal definition, we’re proving things about deductions using
the usual informal proof style that I’ve grown accustomed to in other math courses. Why should
I trust these informal proofs about deductions? How can we formally prove things (using deduc-
tions) about deductions? Isn’t that circular? Is that why we’re only giving informal proofs? I
thought that I’d come away from this subject feeling better about the philosophical foundations
of mathematics, but we’ve just added a new layer to mathematics and we have both informal
proofs and deductions, making the whole thing even more dubious.
To others who begin a study of the subject, there is no problem. After all, mathematics is the most
reliable method we have to establish truth, and there was never any serious question as to its validity. Such
a person may react to the above thoughts as follows:
7
8 CHAPTER 1. INTRODUCTION
Should we be so dismissive of the first philosophically inclined student? The answer, or course, depends
on your own philosophical views, but I’ll try to give my own views as a mathematician specializing in logic
with a definite interest in foundational questions. It is my firm belief that you should put all philosophical
questions out of your mind during a first reading of the material (and perhaps forever, if you’re so inclined),
and come to the subject with a point of view which accepts an independent mathematical reality susceptible
to the mathematical analysis you’ve grown accustomed to. In your mind, you should keep a careful distinction
between normal “real” mathematical reasoning and the formal precise model of mathematical reasoning we
are developing. Some people like to give this distinction a name by calling the normal mathematical realm
we’re working in the metatheory.
To those who are interested, we’ll eventually be able to give reasonable answers to the first student and
provide other respectable philosophical accounts of the nature of mathematics, but this should wait until
we’ve developed the necessary framework. Once we’ve done so, we can give examples of formal theories,
such as first-order set theory, which are able to support the entire enterprise of mathematics including
mathematical logic. This is of great philosophical interest, because this makes it possible to carry out
(nearly) all of mathematics inside this formal theory.
The ideas and techniques that were developed with philosophical goals in mind have now found application
in other branches of mathematics and in computer science. The subject, like all mature areas of mathematics,
has also developed its own very interesting internal questions which are often (for better or worse) divorced
from its roots. Most of the subject developed after the 1930’s has been concerned with these internal and
tangential questions, along with applications to other areas, and now foundational work is just one small
(but still important) part of mathematical logic. Thus, if you have no interest in the more philosophical
aspects of the subject, there remains an impressive, beautiful, and mathematically applicable theory which
is worth your attention.
In order to ignore the nagging question of what constitutes a primitive statement, our first attempt will be to
simply take an arbitrary set whose elements we think of as the primitive statements and put them together
in all possible ways using the connectives.
For example, suppose we start with the set P = {A, B, C}. We think of A, B, and C as our primitive
statements, and we may or may not care what they might express. We now want to put together the elements
of P using the connectives, perhaps repeatedly, but to avoid ambiguity we should be careful. Should the
“meaning” of A ∧ B ∨ C be “A holds, and either B holds or C holds”, corresponding to A ∧ (B ∨ C), or should
it be “Either both A and B holds, or C holds”, corresponding to (A ∧ B) ∨ C? We need some way to avoid
this ambiguity. Probably the most natural way to achieve this is to insert parentheses to make it clear how to
group terms (although we’ll see another natural way later). We now describe the formulas of our language,
denoted by F ormP . First, we put every element of P in F ormP , and then we generate other formulas using
the following rules.
This simple setup, called propositional logic, is a drastic simplification of the language of mathematics,
but there are already many interesting questions and theorems that arise from a careful study. We’ll spend
some time on it in Chapter 3.
Of course, mathematical language is much more rich and varied than what we can get using propositional
logic. One important way to make more complicated and interesting mathematical statements is to make
use of the quantifiers for all and there exists which we’ll denote using the symbols ∀ and ∃. In order to do
so, we will need variables to act as something to quantify over. We’ll denote variables by letters like x, y, z,
etc. Once we’ve come this far, however, we’ll have have to refine our naive notion of primitive statements
above because it’s unclear how to interpret a statement like ∀xB without knowledge of the role of x “inside”
B.
Let’s think a little about our primitive statements. As we mentioned above, it seems daunting to come
up with primitive statements for all areas of mathematics at once, so let’s think of the areas in isolation.
For instance, take group theory. A group is a set G equipped with a binary operation · (that is, · takes in
two elements x, y ∈ G and produces a new element of G denoted by x · y) and an element e such satisfying
Although it is customary and certainly easier on the eyes to put · between two elements of the group, let’s
instead use the standard function notation in order to make the mathematical notation uniform across fields.
In this setting, a group is a set G equipped with a function f : G × G → G and an element e satisfying
1. For all x, y, z ∈ G, we have f (f (x, y), z) = f (x, f (y, z)).
2. For all x ∈ G, we have f (x, e) = x = f (e, x).
3. For all x ∈ G, there exists y ∈ G such that f (x, y) = e = f (y, x).
In order to allow our language to make statement about groups, we introduce a function symbol which we
denote by f to represent the group operation, and a constant symbol which we denote by e to represent the
group identity. Now the group operation is supposed to take in two elements of the group, so if x and y are
variables, then we should allow the formation of f(x, y) which should denote an element of the group (once
we’ve assigned elements of the group to x and y). Also, we should allow the constant symbol to be used
in this way, allowing us to form things like f(x, e). Once we’ve formed these, we should be allowed to use
them like variables in more complicated expressions such as f(f(x, e), y). Each of these expressions formed
by putting together, perhaps repeatedly, variables and the constant symbol e using the function symbol f is
called a term. Intuitively, a term will name a certain element of the group once we’ve assigned elements to
the variables.
With a way to name group elements in hand, we’re now in position to say what out primitive statements
are. The most basic thing that we can say about two group elements is whether or not they are equal, so
we introduce a new equality symbol, which we will denote by the customary =. Given two terms t1 and t2 ,
we call the expression (t1 = t2 ) an atomic formula. These are our primitive statements.
With atomic formulas in hand, we can use the old connectives and the new quantifiers to make new
statements. This puts us in a position to define formulas. First off, all atomic formulas are formulas. Given
formulas we already know, we can put them together using the above connectives. Also, if ϕ is a formula
and x is a variable then each of the following are formulas:
1. ∀xϕ
2. ∃xϕ
Perhaps without realizing it, we’ve described quite a powerful language which can make many nontrivial
statements. For instance, we can write formulas in this language which express the axioms for a group:
1. ∀x∀y∀z(f(f(x, y), z) = f(x, f(y, z)))
2. ∀x((f(x, e) = x) ∧ (f(e, x) = x))
3. ∀x∃y((f(x, y) = e) ∧ (f(y, x) = e))
We can also write a statement saying that the group is abelian:
We can simply have two function symbols a and m which take two arguments (a to represent addition and
m to represent multiplication) and two constant symbols 0 and 1 (0 to represent the additive identity and 1
to represent the multiplicative identity). Writing the axioms for commutative rings in this language is fairly
straightforward.
To take something fairly different, what about the theory of partially ordered sets? Recall that a partially
ordered set is a set P equipped with a subset ≤ of P × P , where we write x ≤ y to mean than (x, y) is an
element of this subset, satisfying
Similar to how we handled the group operation, we’ll use notation which puts the ordering in front of the
two arguments. This may seem odd at this point, given how we’re putting equality in the middle, but we’ll
see that this provides a unifying notation for other similar objects. We thus introduce a relation symbol R,
and we keep the equality symbol =, but we no longer have a need for constant symbols or function symbols.
In this setting without constant or function symbols, the only terms that we have (i.e. the only names for
elements of the partially ordered set) are the variables. However, our atomic formulas are more interesting
because now there are two basic things we can say about elements of the partial ordering: whether they are
equal and whether they are related by the ordering. Thus, our atomic formulas are things of the form t1 = t2
and R(t1 , t2 ) where t1 and t2 are terms. From these atomic formulas, we build up all our formulas as above.
Similar to the situation for groups, we can know write formulas expressing the axioms of partial orderings:
1. ∀xR(x, x)
We can also write a statement saying that the partial ordering is a linear ordering:
∀x∃n(xn = e)
but this poses a problem for two reasons. The first is that our variables are supposed to quantify over
elements of the group in question, not the natural numbers. The second is that we put no construction in
our language to allow us to write something like xn . For each fixed n, we can express it (for example, for
12 CHAPTER 1. INTRODUCTION
n = 3, we can write f(f(x, x), x) and for n = 4, we can write f(f(f(x, x), x), x)), but it’s not clear how to write
it in a general way that would even allow quantification over the natural numbers.
Another example is trying to express that a group is simple (i.e. has no nontrivial normal subgroups).
The natural instinct is to quantify over all subsets of the group H, and say that if it so happens that H
is a normal subgroup, then H is either trivial or everything. However, we have no way to quantify over
subsets. It’s certainly possible to allow such constructions, and this gives second-order logic. If you allow
quantifications over sets of subsets (for example one way of expressing that a ring is Noetherian is to say
that every nonempty set of ideals has a minimal element), you get third-order logic, etc.
Newcomers to the field often find it strange that we focus primarily on first-order logic. There are many
reasons to give special attention to first-order logic that will be developed throughout our study, but for
now you should think of it as providing a simple example of a language which is capable of expressing many
important aspects of various branches of mathematics.
assign true/false values to A, B, and C that make the formulas in Γ true, it happens that ϕ will also be true.
Another approach that we’ll develop is syntactic. We’ll define deductions which are “formal proofs” built
from certain permissible syntactic manipulations, and Γ will imply ϕ in this sense if there is a witnessing
deduction. The Soundness Theorem and the Completeness Theorem for first-order logic (and propositional
logic) says that the semantic version and syntactic version are the same. This result amazingly allows one
to mimic mathematical reasoning with syntactic manipulations.
∃y(m(x, y) = 1)
has a free variable x and “defines” the set of units in the ring. With this point of view, we’ve opened up
the possibility of proving lower bounds on the complexity of any definition of a certain object, or even of
proving that no such definition exists in the language.
Another, closely related, way to take our definitions of precise languages and run with it is the subject
of model theory. In group theory, you state some axioms and work from there in order to study all possible
realizations of the axioms, i.e. groups. However, as we saw above, the group axioms arise in one possible
language with one possible set of axioms. Instead, we can study all possible languages and all possible sets
of axioms and see what we can prove in general and how the realizations compare to each other. In this
sense, model theory is a kind of abstract abstract algebra.
Finally, although it’s probably far from clear how it fits in at this point, computability theory is intimately
related to the above subjects. To see the first glimmer of a connection, notice that computer programming
languages are also formal languages with a precise grammar and a clear distinction between syntax and
semantics. As we’ll see in time, however, the connection is much deeper.
We will often find a need to work with finite sequences, so we establish notation here.
Definition 1.5.3. Let X be a set. Given n ∈ N, we call a function σ : [n] → X a finite sequence from X
of length n. We denote the set of all finite sequences from X of length n by X n . We use λ to denote the
unique sequence of length 0, so X 0 = {λ}.
Definition 1.5.4. Let X be a set. We let X ∗ = n∈N X n , i.e. X ∗ is the set of all finite sequences from X.
S
We denote finite sequences by simply listing the elements in order. For instance, if X = {a, b}, the
sequence aababbba is an element of X ∗ . Sometimes for clarity, we’ll insert commas and instead write
a, a, b, a, b, b, b, a.
Definition 1.5.5. If σ, τ ∈ X ∗ , we say that σ is an initial segment of τ , and write σ ⊆ τ , if σ = τ [n] for
some n. We say that σ is a proper initial segment of τ , and write σ ⊂ τ , if σ ⊆ τ and σ 6= τ .
Definition 1.5.6. If σ, τ ∈ X ∗ , we denote the concatenation of σ and τ by στ or σ ∗ τ .
Definition 1.5.7. If σ, τ ∈ X ∗ , we say that σ is a substring of τ if there exists θ, ρ ∈ X ∗ such that σ = θτ ρ.
Definition 1.5.8. A set A is countably infinite if there exists a bijection g : N → A. A set A is countable
if it is either finite or countably infinite.
Definition 1.5.9. Given a set A, we let P(A) be the set of all subsets of A, and we call P(A) the power set
of A.
Chapter 2
The natural numbers are perhaps the only structure that you’ve had the pleasure of working with when doing
proofs by induction or definitions by recursion, but there are many more arenas in which variants of induction
and recursion apply. In fact, more delicate and exotic proofs by induction and definitions by recursion are
two central tools in mathematical logic. Once we get to set theory, we’ll see how to do transfinite induction
and recursion, and this tool is invaluable in set theory and model theory. In this section, we develop the
more modest tools of induction and recursion along structures which are generated by one-step processes,
like the natural numbers.
15
16 CHAPTER 2. INDUCTION AND RECURSION
Suppose that X is a set and we’re trying to define f : N → X recursively. What do you need? Well, you
need to know f (0), and you need to have a method telling you how to define f (S(n)) from knowledge of n
and the value of f (n). If we want to avoid the self-referential reference to f in invoking the value of f (n),
what we need is a method which tells us what to do next regardless of the actual particular value of f (n).
That is, it needs to tell you what to do on any possible value, not just the one the ends up happening to be
f (n). Formally, this “method” can be given by a function g : N × X → X which tells you what to do at the
next step. Intuitively, this function acts as an iterator. That is, it says if the the last thing you were working
on was input n and it so happened that you set f (n) to equal x ∈ A, then you should define f (S(n)) to be
the value g(n, x).
With all this setup, we now state the theorem which says that no matter what value you want to assign
to f (0), and no matter what iterating function g : N × X → X you give, there exists a unique function
f : N → X obeying the rules.
Theorem 2.1.3 (Recursion on N - Step Form). Let X be a set, let y ∈ X, and let g : N × X → X. There
exists a unique function f : N → X such that
1. f (0) = y.
In the case of the factorial function, we have X = N, y = 1, and g : N×N → N defined by g(n, x) = S(n)·x.
The above theorem implies that there is a unique function f : N → N such that
1. f (0) = y = 1.
Notice how we’ve avoiding a self-reference in the definition. Our definition of g is given nonrecursively, and
then the theorem states the existence and uniqueness of a function which behaves properly.
There is another version of induction on N, sometimes called “strong induction”, which appeals to the
ordering of the natural numbers rather than the stepping of the successor function.
Theorem 2.1.4 (Induction on N - Order Form). Suppose that X ⊆ N is such that n ∈ X whenever m ∈ X
for all m < n. We then have X = N.
Notice that there is no need to deal with the “base case” of n = 0, because this is handled vacuously due
to the fact that there is no m < 0.
Theorem 2.1.5 (Recursion on N - Order Form). Let X be a set and let g : X ∗ → X. There exists a unique
function f : N → X such that
f (n) = g(f [n])
for all n ∈ N.
2.2 Generation
There are many situations throughout mathematics when we want to look at what a certain subset “gen-
erates”. For instance, you have a subset of a group (vector space, ring), and you want to consider the
subgroup (subspace, ideal) that they generate. Another example is you have a subset of a graph, and you
want to consider the set of vertices in the graph reachable from the subset. In the introduction, we talked
about generating all formulas from primitive formulas using certain connections. This situation will arise so
frequently in what follows that it’s a good idea to unify them all in a common framework.
2.2. GENERATION 17
Definition 2.2.1. Let A be a set and let k ∈ N+ . A function h : Ak → A is called a k-ary function on A.
We call k the arity of h. A 1-ary function is sometimes called unary and a 2-ary function is sometimes
called binary.
Definition 2.2.2. Suppose that A is a set, B ⊆ A and H is a collection of functions such that each h ∈ H is
a k-ary function on A for some k ∈ N+ . We call (A, B, H) a simple generating system. In such a situation,
for each k ∈ N+ , we denote the set of k-ary functions in H by Hk .
Examples.
1. Let G be a group and let B ⊆ G. We want the subgroup of G that B generates. The operations in
question here are the group operation and inversion, so we let H = {h1 , h2 } where
2. Let V be a vector space over R and let B ⊆ V . We want the subspace of V that B generates. The
operations in question consist of vector addition and scalar multiplication, so we let H = {g} ∪ {hα :
α ∈ R} where
There are certain cases when the natural functions to put into H are not total or are “multi-valued”. For
instance, in the first example below, we’ll talk about the subfield generated by a certain subset of a field,
and we’ll want to include multiplicative inverses for all nonzero elements. When putting a corresponding
function in H, there is no obvious way to define it on 0. Also, if generating the vertices reachable from a
subset of a graph, we may want to throw many vertices in because a vertex can be linked to many others.
Definition 2.2.3. Let A be a set and let k ∈ N+ . A function h : Ak → P(A) is called a set-valued k-ary
function on A. We call k the arity of h. A 1-ary set-valued function is sometimes called unary and a 2-ary
set-valued function is sometimes called binary.
Definition 2.2.4. Suppose that A is a set, B ⊆ A and H is a collection of functions such that each h ∈ H
is a set-valued k-ary function on A for some k ∈ N+ . We call (A, B, H) a generating system. In such a
situation, for each k ∈ N+ , we denote the set of multi-valued k-ary functions in H by Hk .
Examples.
1. Let K be a field and let B ⊆ K. We want the subfield of K that B generates. The operations in
question here are addition, multiplication, and both additive and multiplicative inverses. We thus let
H = {h1 , h2 , h3 , h4 } where
Notice that if we have a simple generating system (A, B, H), then we can associate to it the generating
system (A, B, H0 ) where H0 = {h0 : h ∈ H} where if h : Ak → A is an element of Hk , then h0 : Ak → P(A) is
defined by letting h0 (a1 , a2 , . . . , ak ) = {h(a1 , a2 , . . . , ak )}.
Given a generating system (A, B, H), we want to define the set of elements of A generated from B using
the functions in H. There are many natural ways of doing this. We discuss three different ways which divide
into approaches “from above” and approaches “from below”. Each of these descriptions can be slightly
simplified for simple generating systems, but it’s not much harder to handle the more general case.
Definition 2.2.16. Let (A, B, H) be a generating system. We denote the common value of I, V, W by
G(A, B, H) or simply G.
The nice thing about having multiple equivalent definitions for the same concept is that we can use the
most convenient one when proving a theorem. For example, using (2) of Remark 2.2.9, we get the following
corollary.
Corollary 2.2.17. Let (A, B, H) be a generating system. For all c ∈ G, either c ∈ B or there exists k ∈ N+ ,
h ∈ Hk , and a1 , a2 , . . . , ak ∈ G with c ∈ h(a1 , a2 , . . . , ak ).
Proposition 2.3.1 (Step Induction). Let (A, B, H) be a generating system. Suppose that X ⊆ A satisfies
1. B ⊆ X.
The next example illustrates how we can sometimes identify G explicitly. Notice that we use 2 different
types of induction in the argument. One direction uses induction on N and the other uses induction on G
as just described.
2.4. STEP RECURSION 21
Example 2.3.2. Consider the following simple generating system. Let A = R, B = {7}, and H = {h}
where h : R → R is the function h(x) = 2x. Determine G explicitly.
Proof. Intuitively, we want the set {7, 14, 28, 56, . . . }, which we can write more formally as {7 · 2n : n ∈ N}.
Let X = {7 · 2n : n ∈ N}
We first show that X ⊆ G by showing that 7 · 2n ∈ G for all n ∈ N by induction (on N). We have
7 · 20 = 7 · 1 = 7 ∈ G because B ⊆ G as G is inductive. Suppose that n ∈ N is such that 7 · 2n ∈ G. Since
G is inductive, it follows that h(7 · 2n ) = 2 · 7 · 2n = 7 · 2n+1 ∈ G. Therefore, 7 · 2n ∈ G for all n ∈ N by
induction, hence X ⊆ G.
We now show that G ⊆ X by induction (on G). Notice that B ⊆ X because 7 = 7 · 1 = 7 · 20 ∈ X.
Suppose now that x ∈ X and fix n ∈ N with x = 7 · 2n . We then have h(x) = 2 · x = 7 · 2n+1 ∈ X. Therefore
G ⊆ X by induction.
It follows that X = G.
In many cases, it’s very hard to give a simple explicit description of the set G. This is where induction
really shines, because it allows us to prove something about all elements of G despite the fact that we have
a hard time getting a handle on what exactly the elements of G look like. Here’s an example.
Example 2.3.3. Consider the following simple generating system. Let A = Z, B = {6, 183}, and H = {h}
where h : A3 → A is given by h(k, m, n) = k · m + n. Every element of G is divisible by 3.
Proof. Let X = {n ∈ Z : n is divisible by 3}. We prove by induction that G ⊆ X. We first handle the bases
case. Notice that 6 = 3 · 2 and 183 = 3 · 61, so B ⊆ X.
We now do the inductive step. Suppose that k, m, n ∈ X, and fix `1 , `2 , `3 ∈ Z with k = 3`1 , m = 3`2 ,
and n = 3`3 . We then have
h(k, m, n) = k · m + n
= (3`1 ) · (3`2 ) + 3`3
= 9`1 `2 + 3`3
= 3(3`1 `2 + `3 )
hence h(k, m, n) ∈ X.
It follows by induction that G ⊆ X, i.e. that every element of G is divisible by 3.
Example 2.4.2. Consider the following simple generating system. Let A = {1, 2}, B = {1}, and H = {h}
where h : A → A is given by h(1) = 2 and h(2) = 1. Let X = N. Define ι : B → N by letting ι(1) = 1 and
define gh : A × N → N by letting gh (a, n) = n + 1. There is no function f : G → N such that
Proof. Notice first that G = {1, 2}. Suppose that f : G → N satisfies (1) and (2) above. Since f satisfies (1),
we must have f (1) = ι(1) = 1. By (2), we then have that
To get around this problem, we want a definition of a “nice” simple generating system. Intuitively, we
want to say something like “every element of G is generated in a unique way”. The following definition is a
relatively straightforward way to formulate this.
1. ran(h Gk ) ∩ B = ∅ whenever h ∈ Hk .
Here’s a simple example which will play a role for us in Section 2.5. We’ll see more subtle and important
examples when we come to Propositional Logic and First-Order Logic.
Example 2.4.4. Let X be a set. Consider the following simple generating system. Let A = X ∗ , let B = X,
and let H = {hx : x ∈ X} where hx : X ∗ → X ∗ is the function hx (σ) = xσ. We then have that G = X ∗ \{λ}
and that (A, B, H) is free.
We now show that (A, B, H) is free. First notice that for any x ∈ X, we have that ran(hx G) ∩ X = ∅
because every elemnts of ran(hx G) has length at least 2 (because λ ∈
/ G).
Now for any x ∈ X, we have that hx G is injective because if hx (σ) = hx (τ ), then xσ = xτ , and hence
σ = τ.
Finally, notice that if x, y ∈ X with x 6= y, we have that ran(hx G) ∩ ran(hy G) = ∅ because every
elements of ran(hx G) begins with x while every element of ran(hy G) begins with y.
On to the theorem which says that if a simple generating system is free, then we can perform recursive
definitions on it.
Theorem 2.4.5. Suppose that the simple generating system (A, B, H) is free and X is a set. Suppose also
that ι : B → X and that for every h ∈ Hk , we have a function gh : (A × X)k → X. There exists a unique
function f : G → X such that
Since a1 , a2 , . . . , ak ∈ G, this contradicts the fact that ran(h Gk ) ∩ B = ∅. Therefore, for every b ∈ B,
there exists a unique x ∈ X, namely ι(b), such that (b, x) ∈ G0 . Thus, B ⊆ Z.
Inductive Step: Fix h ∈ Hk , and suppose that a1 , a2 , . . . , ak ∈ Z. For each i, let xi be the unique element
of X with (ai , xi ) ∈ G0 . Notice that
(h(a1 , a2 , . . . , ak ), gh (a1 , x1 , a2 , x2 , . . . , ak , xk )) = gh0 (a1 , x1 , a2 , x2 , . . . , ak , xk ) ∈ G0
hence there exists x ∈ X such that (h(a1 , a2 , . . . , ak ), x) ∈ G0 . Suppose now that y ∈ X is such that
(h(a1 , a2 , . . . , ak ), y) ∈ G0 . We have (h(a1 , a2 , . . . , ak ), y) ∈
/ B 0 because ran(h Gk ) ∩ B = ∅, so there exists
0
ĥ ∈ H` together with (c1 , z1 ), (c2 , z2 ), . . . , (c` , z` ) ∈ G such that
hence b ∈ Y . It follows that B ⊆ Y . Suppose now that h ∈ Hk and a1 , a2 , . . . , ak ∈ Y . Since ai ∈ Y for each
i, we have f1 (ai ) = f2 (ai ) for each i, and hence
Thus, h(a1 , a2 , . . . , ak ) ∈ Y . It follows by induction that Y = G, i.e. f1 (a) = f2 (a) for all a ∈ G.
Definition 2.5.1. Define a binary function h : (Sym∗A )2 → Sym∗A by letting h(σ, τ ) be the sequence [σ ? τ ].
Let V alidExpA = G(Sym∗A , A, {h}) (viewed as a simple generating system).
For example, suppose that A = {a, b, c}. Typical elements of G(Sym∗A , A, {h}) are c, [b ? [a ? c]] and
[c ? [[c ? b] ? a]. The idea now is that if we have a particular function f : A2 → A, we can intrepret ? as
application of the function, and then this should give us a way to “make sense of”, that is evaluate, any
element of V alidExpA .
Definition 2.5.3. Define K : Sym∗A → Z as follows. We first define w : SymA → Z by letting w(a) = 0 for
∗
Pw([) = −1, and letting w(]) =∗ 1. We then define K : SymA → Z by letting K(λ) = 0 and
all a ∈ A, letting
letting K(σ) = i<|σ| w(σ(i)) for all σ ∈ SymA \{λ}.
Proof. The proof is by induction on ϕ. In other words, we let X = {ϕ ∈ V alidExpA : K(ϕ) = 0}, and we
prove by induction that X = V alidExpA . Notice that for every a ∈ A, we have that K(a) = 0. Suppose
that ϕ, ψ ∈ V alidExpA are such that K(ϕ) = 0 = K(ψ). We then have that
Proof. In other words, we let X = {ϕ ∈ V alidExpA : whenever σ ⊂ ϕ and σ 6= λ, we have that K(σ) ≤ −1},
and we prove by induction that X = V alidExpA .
For every a ∈ A, this is trivial because there is no σ 6= λ with σ ⊂ a.
Suppose that ϕ, ψ ∈ V alidExpA and the result holds for ϕ and ψ. We prove the result for [ϕ ? ψ].
Suppose that σ ⊂ [ϕ ? ψ] and σ 6= λ. If σ is [, then K(σ) = −1. If σ is [τ where τ 6= λ and τ ⊂ ϕ, then
K(σ) = −1 + K(τ )
≤ −1 − 1 (by induction)
≤ −1.
If σ is [ϕ or [ϕ?, then
K(σ) = −1 + K(ϕ)
= −1 + 0 (by Proposition 2.5.5)
= −1.
Otherwise, σ is [ϕ ? ψ, and
Proof. This follows by combining Proposition 2.5.5 and Proposition 2.5.6, along with noting that λ ∈
/
V alidExpA (which follows by a trivial induction).
Proof. First notice that ran(h (V alidExpA )2 ) ∩ A = ∅ because all elements of ran(h) begin with [.
Suppose that ϕ1 , ϕ2 , ψ1 , ψ2 ∈ V alidExpA and h(ϕ1 , ψ1 ) = h(ϕ2 , ψ2 ). We then have [ϕ1 ? ψ1 ] = [ϕ2 ? ψ2 ],
hence ϕ1 ? ψ1 = ϕ2 ? ψ2 . Since ϕ1 ⊂ ϕ2 and ϕ2 ⊂ ϕ1 are both impossible by Corollary 2.5.7, it follows that
ϕ1 = ϕ2 . Therefore, ?ψ1 = ?ψ2 , and so ψ1 = ψ2 . It follows that h (V alidExpA )2 is injective.
• Evf ([ϕ ? ψ]) = f (Evf (ϕ), Evf (ψ)) for all ϕ, ψ ∈ V alidExpA .
Formally, we use freeness to justify this definition as follows. Let ι : A → A be the identity map, and let
gh : (Sym∗A × A)2 → A be the function defined by letting gh ((ϕ, a), (ψ, b)) = f (a, b). By freeness, there is a
unique function Evf : V alidExpA → A such that
1. Evf (a) = ι(a) for all a ∈ A.
2. Evf (h(ϕ, ψ)) = gh ((ϕ, Evf (ϕ)), (ψ, Evf (ψ))) for all ϕ, ψ ∈ V alidExpA .
which, unravelling definitions, is exactly what we wrote above.
We now define the function which elimanates all mention of parentheses and ?. Thus, it produces the
sequence of elements of A occuring in the given sequence in order.
Definition 2.5.10. Define a function D : V alidExpA → A∗ recursively by letting
• D(a) = a for all a ∈ A.
• D([ϕ ? ψ]) = D(ϕ) ∗ D(ψ) for all ϕ, ψ ∈ V alidExpA .
With these definitions in hand, we can now precisely state our theorem.
Theorem 2.5.11. Suppose that f : A2 → A is associative, i.e. f (a, f (b, c)) = f (f (a, b), c) for all a, b, c ∈ A.
For all ϕ, ψ ∈ V alidExpA with D(ϕ) = D(ψ), we have Evf (ϕ) = Evf (ψ).
In order to prove our theorem, we’ll make use of the following function. Intuitively, it takes a sequence
such as cabc and “associates to the right” to produce [c ? [a ? [b ? c]]]. Thus, it provides a canonical way to
put together the elements of the sequence into something we can evaluate.
To make the recursive definition precise, consider the simple generating system (A∗ , A, {ha : a ∈ A})
where ha : A∗ → A∗ is defined by ha (σ) = aσ. As shown in Example 2.4.4, we know that (A∗ , A, {ha : a ∈ A})
is free and we have that G = A∗ \{λ}.
Definition 2.5.12. We define R : A∗ \{λ} → Sym∗A recursively by letting R(a) = a for all a ∈ A, and letting
R(aσ) = [a ? R(σ)] for all a ∈ A and all σ ∈ A∗ \{λ}.
In order to prove our theorem, we will show that Evf (ϕ) = Evf (R(D(ϕ))) for all ϕ ∈ V alidExpA ,
i.e. that we can take any ϕ ∈ V alidExpA , rip it apart so that we see the elements of A in order, and then
associate to the right, without affecting the result of the evaluation. We first need the following lemma.
Lemma 2.5.13. Evf ([R(σ) ? R(τ )]) = Evf (R(στ )) for all σ, τ ∈ A∗ \{λ}.
Proof. Fix τ ∈ A∗ \{λ}. We prove the result for this fixed τ by induction on A∗ \{λ}. That is, we let
X = {σ ∈ A∗ \{λ} : Evf ([R(σ) ? R(τ )]) = Evf (R(στ ))} and prove by induction on (A∗ , A, {ha : a ∈ A})
that X = A∗ \{λ}. Suppose first that a ∈ A. We then have
Evf ([R(a) ? R(τ )]) = Evf ([a ? R(τ )]) (by definition of R)
= Evf (R(aτ )) (by definition of R)
so a ∈ X. Suppose now that σ ∈ X and that a ∈ A. We show that aσ ∈ X. We have
Evf ([R(aσ) ? R(τ )]) = Evf ([[a ? R(σ)] ? R(τ )]) (by definition of R)
= f (Evf ([a ? R(σ)]), Evf (R(τ ))) (by definition of Evf )
= f (f (a, Evf (R(σ))), Evf (R(τ ))) (by definition of Evf using Evf (a) = a)
= f (a, f (Evf (R(σ)), Evf (R(τ )))) (since f is associative)
= f (a, Evf ([R(σ) ? R(τ )])) (by definition of Evf )
= f (a, Evf (R(στ ))) (since σ ∈ X)
= Evf ([a ? R(στ )]) (by definition of Evf using Evf (a) = a)
= Evf (R(aστ )) (by definition of R)
2.5. AN ILLUSTRATIVE EXAMPLE 27
Proof. By induction on V alidExpA . If a ∈ A, this is trivial because R(D(a)) = R(a) = a. Suppose that
ϕ, ψ ∈ V alidExpA and the result holds for ϕ and ψ.
Evf ([ϕ ? ψ]) = f (Evf (ϕ), Evf (ψ)) (by definition of Evf )
= f (Evf (R(D(ϕ))), Evf (R(D(ψ)))) (by induction)
= Evf ([R(D(ϕ)) ? R(D(ψ))]) (by definition of Evf )
= Evf (R(D(ϕ) ∗ D(ψ))) (by Lemma 2.5.13)
= Evf (R(D([ϕ ? ψ]))) (by definition of D)
Proof of Theorem 2.5.11. Suppose that ϕ, ψ ∈ V alidExpA are such that D(ϕ) = D(ψ). We then have that
Definition 2.5.15. Define a binary function h : (Sym∗A )2 → Sym∗A by letting h(σ, τ ) be the sequence ?στ .
Let P olishExpA = G(Sym∗A , A, {h}) (viewed as a simple generating system).
Definition 2.5.17. Define K : Sym∗A → Z as follows. We first define w : SymA → Z by letting w(a) = 1
for all aP∈ A and letting w(?) = −1. We then define K : Sym∗A → Z by letting K(λ) = 0 and letting
K(σ) = i<|σ| w(σ(i)) for all σ ∈ Sym∗A \{λ}.
Proof. The proof is by induction on ϕ. Notice that for every a ∈ A, we have that K(a) = 1. Suppose that
ϕ, ψ ∈ P olishExpA are such that K(ϕ) = 1 = K(ψ). We then have that
Proof. The proof is by induction on ϕ. For every a ∈ A, this is trivial because the only σ ⊂ A is σ = λ, and
we have K(λ) = 0.
Suppose that ϕ, ψ ∈ P olishExpA and the result holds for ϕ and ψ. We prove the result for ?ϕψ. Suppose
that σ ⊂ ?ϕψ. If σ = λ, then K(σ) = 0. If σ is ?τ for some τ ⊂ ϕ, then
Propositional Logic
h¬ (σ) = (¬σ)
h∧ (σ, τ ) = (σ ∧ τ )
h∨ (σ, τ ) = (σ ∨ τ )
h→ (σ, τ ) = (σ → τ )
Definition 3.1.3. Define K : Sym∗P → Z as follows. We first define w : SymP → Z by letting w(A) = 0
for all A ∈ P , letting w(3) = 0 for all 3 ∈ {¬, ∧, ∨, →}, letting
Pw(() = −1, and letting w()) = 1. We then
define K : Sym∗P → Z by letting K(λ) = 0 and letting K(σ) = i<|σ| w(σ(i)) for all σ ∈ Sym∗P \{λ}.
Proof. This follows by combining Proposition 3.1.5 and Proposition 3.1.6, along with noting that λ ∈
/ F ormP
(which follows by a simple induction).
29
30 CHAPTER 3. PROPOSITIONAL LOGIC
Proof. First notice that ran(h¬ F ormP ) ∩ P = ∅ because all elements of ran(h¬ ) begin with (. Similarly,
for any 3 ∈ {∧, ∨, →}, we have ran(h3 F orm2P ) ∩ P = ∅ since all elements of ran(h3 ) begin with (.
Suppose that ϕ, ψ ∈ F ormP and h¬ (ϕ) = h¬ (ψ). We then have (¬ϕ) = (¬ψ), hence ϕ = ψ. Therefore,
h¬ F ormP is injective. Fix 3 ∈ {∧, ∨, →}. Suppose that ϕ1 , ϕ2 , ψ1 , ψ2 ∈ F ormP and that h3 (ϕ1 , ψ1 ) =
h3 (ϕ2 , ψ2 ). We then have (ϕ1 3ψ1 ) = (ϕ2 3ψ2 ), hence ϕ1 3ψ1 = ϕ2 3ψ2 . Since ϕ1 ⊂ ϕ2 and ϕ2 ⊂ ϕ1 are
both impossible by Corollary 3.1.7, it follows that ϕ1 = ϕ2 . Therefore, 3ψ1 = 3ψ2 , and so ψ1 = ψ2 . It
follows that h3 F orm2P is injective.
Let 3 ∈ {∧, ∨, →}. Suppose that ϕ, ψ1 , ψ2 ∈ F ormP and h¬ (ϕ) = h3 (ψ1 , ψ2 ). We then have (¬ϕ) =
(ψ1 3ψ2 ), hence ¬ϕ = ψ1 3ψ2 , contradicting the fact that no element of F ormP begins with ¬ (by a simple
induction). Therefore, ran(h¬ F ormP ) ∩ ran(h3 F orm2P ) = ∅.
Suppose now that 31 , 32 ∈ {∧, ∨, →} with 31 6= 32 . Suppose that ϕ1 , ϕ2 , ψ1 , ψ2 ∈ F ormP and
h31 (ϕ1 , ψ1 ) = h32 (ϕ2 , ψ2 ). We then have (ϕ1 31 ψ1 ) = (ϕ2 32 ψ2 ), hence ϕ1 31 ψ1 = ϕ2 32 ψ2 . Since ϕ1 ⊂ ϕ2
and ϕ2 ⊂ ϕ1 are both impossible by Corollary 3.1.7, it follows that ϕ1 = ϕ2 . Therefore, 31 = 32 , a
contradiction. It follows that ran(h31 F orm2P ) ∩ ran(h32 F orm2P ) = ∅.
h¬ (σ) = ¬σ
h∧ (σ, τ ) = ∧στ
h∨ (σ, τ ) = ∨στ
h→ (σ, τ ) = → στ
K(¬ϕ) = 0 + K(ϕ)
= K(ϕ)
= 1.
Suppose now that ϕ, ψ ∈ F ormP are such that K(ϕ) = 1 = K(ψ), and 3 ∈ {∧, ∨, →}. We then have that
Proof. The proof is by induction on ϕ. For every A ∈ P , this is trivial because the only σ ⊂ A is σ = λ, and
we have K(λ) = 0.
Suppose that ϕ ∈ F ormP and the result holds for ϕ. We prove the result for ¬ϕ. Suppose that σ ⊂ ¬ϕ.
If σ = λ, then K(σ) = 0. Otherwise, σ is ¬τ for some τ ⊂ ϕ, in which case
K(σ) = 0 + K(τ )
≤0+0 (by induction)
≤ 0.
K(σ) = −1 + K(τ )
≤ −1 + 0 (by induction)
≤ −1.
Proof. First notice that ran(h¬ F ormP ) ∩ P = ∅ because all elements of ran(h¬ ) begin with ¬. Similarly,
for any 3 ∈ {∧, ∨, →}, we have ran(h3 F orm2P ) ∩ P = ∅ since all elements of ran(h3 ) begin with 3.
Suppose that ϕ, ψ ∈ F ormP and h¬ (ϕ) = h¬ (ψ). We then have ¬ϕ = ¬ψ, hence ϕ = ψ. Therefore,
h¬ F ormP is injective. Fix 3 ∈ {∧, ∨, →}. Suppose that ϕ1 , ϕ2 , ψ1 , ψ2 ∈ F ormP and that h3 (ϕ1 , ψ1 ) =
h3 (ϕ2 , ψ2 ). We then have 3ϕ1 ψ1 = 3ϕ2 ψ2 , hence ϕ1 ψ1 = ϕ2 ψ2 . Since ϕ1 ⊂ ϕ2 and ϕ2 ⊂ ϕ1 are both
impossible by Corollary 3.1.15, it follows that ϕ1 = ϕ2 . Therefore, ψ1 = ψ2 . It follows that h3 F orm2P is
injective.
For any 3 ∈ {∧, ∨, →}, we have ran(h¬ F ormP )∩ran(h3 F orm2P ) = ∅ because all elements of ran(h¬ )
begin with ¬ and all elements of ran(h3 ) begin with 3. Similarly, if 31 , 32 ∈ {∧, ∨, →} with 31 6= 32 , we
have ran(h31 F orm2P ) ∩ ran(h32 F orm2P ) = ∅ because all elements of ran(h31 ) begin with 31 and all
elements of ran(h32 ) begin with 32 .
standard syntax or in more abbreviated forms. For example, we’ll write A ∧ B instead of ∧AB (or (A ∧ B)
in the original syntax) . We’ll also write something like
A1 ∧ A2 ∧ · · · ∧ An−1 ∧ An
or
n
^
Ai
i=1
instead of (A1 ∧ (A2 ∧ (· · · (An−1 ∧ An ) · · · ))) in standard syntax or ∧A1 ∧ A2 · · · ∧ An−1 An in Polish notation
(which can be precisely defined in a similar manner as R in Section 2.5). In general, when we string together
multiple applications of an operation (such as ∧) occur in order, we always associate to the right.
When it comes to mixing symbols, let’s agree to the following conventions about “binding” in a similar
fashion to how we think of · as more binding than + (so that 3·5+2 is read as (3·5)+2). We think of ¬ as the
most binding, so we read ¬A ∧ B as ((¬A) ∧ B). After that, we consider ∧ and ∨ as the next most binding,
and → has the least binding. We’ll insert parentheses when we wish to override this binding. For example,
A ∧ ¬B → C ∨ D is really ((A ∧ (¬B)) → (C ∨ D)) while A ∧ (¬B → C ∨ D) is really (A ∧ ((¬B) → (C ∨ D))).
Proof. The proof is by induction on ϕ ∈ F ormP . Suppose first that A ∈ P . Since OccurP rop(A) = {A} and
A ∈ F ormA , we have A ∈ F ormOccurP rop(A) .
Suppose that ϕ ∈ F ormP and that the result holds for ϕ, i.e. we have ϕ ∈ F ormOccurP rop(ϕ) . Since
OccurP rop(¬ϕ) = OccurP rop(ϕ), it follows that ϕ ∈ F ormOccurP rop(¬ϕ) . Hence, ¬ϕ ∈ F ormOccurP rop(¬ϕ) .
Suppose that ϕ, ψ ∈ F ormP , that 3 ∈ {∧, ∨, →}, and that the result holds for ϕ and ψ, i.e. we have
ϕ ∈ F ormOccurP rop(ϕ) and ψ ∈ F ormOccurP rop(ψ) . Since
it follows from Proposition 3.1.19 that ϕ, ψ ∈ F ormOccurP rop(3ϕψ) . Therefore, 3ϕψ ∈ F ormOccurP rop(3ϕψ) .
• Depth(¬ϕ) = Depth(ϕ) + 1.
Definition 3.1.23. We define a function Subf orm : F ormP → P(F ormP ) recursively as follows.
• Subf orm(3ϕψ) = {3ϕψ} ∪ Subf orm(ϕ) ∪ Subf orm(ψ) for each 3 ∈ {∧, ∨, →}.
Definition 3.1.25. Let θ, γ ∈ F ormP . We define a function Substθγ : F ormP → F ormP recursively as
follows.
(
θ θ if γ = A
• Substγ (A) =
A otherwise
(
θ if γ = ¬ϕ
• Substθγ (¬ϕ) =
¬Substθγ (ϕ) otherwise
(
θ if γ = 3ϕψ
• Substθγ (3ϕψ) =
3Substθγ (ϕ)Substθγ (ψ) otherwise
for each 3 ∈ {∧, ∨, →}.
0 if v(ϕ) = 0 and v(ψ) = 0
1 if v(ϕ) = 0 and v(ψ) = 1
• v(∨ϕψ) =
1 if v(ϕ) = 1 and v(ψ) = 0
1 if v(ϕ) = 1 and v(ψ) = 1
1 if v(ϕ) = 0 and v(ψ) = 0
1 if v(ϕ) = 0 and v(ψ) = 1
• v(→ ϕψ) =
0
if v(ϕ) = 1 and v(ψ) = 0
1 if v(ϕ) = 1 and v(ψ) = 1
Before moving on, we should a couple of things about what happens when we shrink/enlarge the set P .
Intuitively, if ϕ ∈ F ormQ and Q ⊆ P , then we can extend the truth assigment from Q to P arbitrarily
without affecting the value of v(ϕ). Here is the precise statement.
Proposition 3.2.3. Suppose that Q ⊆ P and that v : P → {0, 1} is a truth assignment on P . We then have
that v(ϕ) = (v Q)(ϕ) for all ϕ ∈ F ormQ .
Proof. A trivial induction on ϕ ∈ F ormQ .
Proposition 3.2.4. Suppose ϕ ∈ F ormP . Whenever v1 and v2 are truth assignments on P such that
v1 (A) = v2 (A) for all A ∈ OccurP rop(ϕ), we have v 1 (ϕ) = v 2 (ϕ).
Proof. Let Q = OccurP rop(ϕ). We then have that ϕ ∈ F ormQ by Proposition 3.1.20. Since v1 Q = v2 Q,
we have
v 1 (ϕ) = (v1 Q)(ϕ) = (v2 Q)(ϕ) = v 2 (ϕ)
With a method of assigning true/false values to formulas in hand (once we’ve assigned them to P ), we’re
now in position to use our semantic definitions to given a precise meaning to “The set of formulas Γ implies
the formula ϕ”.
Definition 3.2.5. Let P be given Let Γ ⊆ F ormP and let ϕ ∈ F ormP . We write Γ P ϕ, or simply Γ ϕ
if P is clear, to mean that whenever v is a truth assignment on P such that v(γ) = 1 for all γ ∈ Γ, we have
v(ϕ) = 1. We pronounce Γ ϕ as “Γ semantically implies ϕ”.
3.2. TRUTH ASSIGNMENTS AND SEMANTIC IMPLICATION 35
We also have a semantic way to say that a set of formulas is not contradictory.
Definition 3.2.6. Γ is satisfiable if there exists a truth assignment v : P → {0, 1} such that v(γ) = 1 for all
γ ∈ Γ. Otherwise, we say that Γ is unsatisfiable.
Example 3.2.7. Let P = {A, B, C}. We have {A ∨ B, ¬(A ∧ (¬C))} B ∨ C.
Proof. Let v : P → {0, 1} be a truth assignment such that v(A ∨ B) = 1 and v(¬(A ∧ (¬C))) = 1. We need to
show that v(B ∨ C) = 1. Suppose not. We would then have that v(B) = 0 and v(C) = 0. Since v(A ∨ B) = 1,
this implies that v(A) = 1. Therefore, v(A ∧ (¬C)) = 1, so v(¬(A ∧ (¬C))) = 0, a contradiction.
Example 3.2.8. Let P be given. For any ϕ, ψ ∈ F ormP , we have {ϕ → ψ, ϕ} ψ
Proof. Let v : P → {0, 1} be a truth assignment and suppose that v(ϕ → ψ) = 1 and v(ϕ) = 1. If v(ψ) = 0,
it would follows that v(ϕ → ψ) = 0, a contradiction. Thus, v(ψ) = 1.
Notation 3.2.9.
1. If Γ = ∅, we write ϕ instead of ∅ ϕ.
2. If Γ = {γ}, we write γ ϕ instead of {γ} ϕ.
Definition 3.2.10.
1. Let ϕ ∈ F ormP . We say that ϕ is a tautology if ϕ.
2. If ϕ ψ and ψ ϕ, we say that ϕ and ψ are semantically equivalent.
Remark 3.2.11. Notice that ϕ and ψ are semantically equivalent if and only if for all truth assigments
v : P → {0, 1}, we have v(ϕ) = v(ψ).
Example 3.2.12. ϕ ∨ ¬ϕ is a tautology for any ϕ ∈ F ormP .
Proof. Fix ϕ ∈ F ormP . Let v : P → {0, 1} be a truth assignment. If v(ϕ) = 1, then v(ϕ ∨ ¬ϕ) = 1.
Otherwise, we have v(ϕ) = 0, in which case v(¬ϕ) = 1, and hence v(ϕ ∨ ¬ϕ) = 1. Therefore, v(ϕ ∨ ¬ϕ) = 1
for all truth assignments v : P → {0, 1}, hence ϕ ∨ ¬ϕ is a tautology.
Example 3.2.13. ϕ is semantically equivalent to ¬¬ϕ for any ϕ ∈ F ormP .
Proof. Fix ϕ ∈ F ormP . We need to show that for any truth assignment v : P → {0, 1}, we have v(ϕ) = 1 if
and only if v(¬¬ϕ) = 1. We have
v(ϕ) = 1 ⇐⇒ v(¬ϕ) = 0
⇐⇒ v(¬¬ϕ) = 1
Proposition 3.2.16. Suppose that Q ⊆ P , that Γ ⊆ F ormQ , and that ϕ ∈ F ormQ . We then have that
Γ P ϕ if and only if Γ Q ϕ.
Proof. First notice that Γ ⊆ F ormP and ϕ ∈ F ormP by Proposition 3.1.19 and Proposition 3.1.20.
Suppose first that Γ Q ϕ. Let v : P → {0, 1} be a truth assignment such that v(γ) = 1 for all γ ∈ Γ.
We then have that (v Q)(γ) = 1 for all γ ∈ Γ, hence (v Q)(ϕ) = 1 because Γ Q ϕ. Therefore, v(ϕ) = 1.
It follows that Γ P ϕ.
Suppose then that Γ P ϕ. Let v : Q → {0, 1} be a truth assignment such that v(γ) = 1 for all γ ∈ Γ.
Define a truth assignment w : P → {0, 1} by letting w(A) = v(A) for all A ∈ Q and letting w(A) = 0 for all
A ∈ P \Q. Since w Q = v, we have w(γ) = v(γ) = 1 for all γ ∈ Γ. Since Γ P ϕ, it follows that w(ϕ) = 1,
hence v(ϕ) = 1. Therefore, Γ Q ϕ.
Suppose that Γ is finite, and we want to determine whether or not Γ ϕ. By the previous proposition,
instead of examining all truth assignments v : P → {0, 1} on P , we need only consider truth assignments
v : OccurP rop(Γ ∪ {ϕ}) → {0, 1}. Now OccurP rop(Γ ∪ {ϕ}) is a finite set, so there are only finitely many
possibilities. Thus, one way of determining whether Γ ϕ is simply to check all of them. If |OccurP rop(Γ ∪
{ϕ})| = n, then there are 2n different truth assignments. We can systematically arrange them in a table
like below, where we ensure we put the the elements of OccurP rop(Γ ∪ {ϕ}) in the first columns, and put
all elements of Γ ∪ {ϕ} in later columns. We also ensure that if ψ is in a column, then all subformulas of ψ
appear in an earlier column. This allows us to fill in the table one column at a time. This simple-minded
exhaustive technique is called the method of truth tables.
Example 3.2.17. Show that {(A ∨ B) ∧ C, A → (¬C)} (¬C) → B.
Proof.
A B C A∨B (A ∨ B) ∧ C ¬C A → (¬C) (¬C) → B
0 0 0 0 0 1 1 0
0 0 1 0 0 0 1 1
0 1 0 1 0 1 1 1
0 1 1 1 1 0 1 1
1 0 0 1 0 1 1 0
1 0 1 1 1 0 0 1
1 1 0 1 0 1 1 1
1 1 1 1 1 0 0 1
Notice that every row in which both of the (A ∨ B) ∧ C column and the A → (¬C) column have a 1, namely
just the row beginning with 011, we have that the entry under the (¬C) → B column is a 1. Therefore,
{(A ∨ B) ∧ C, A → (¬C)} (¬C) → B.
Example 3.2.18. Show that ¬(A ∧ B) is semantically equivalent to ¬A ∨ ¬B.
Proof.
A B A∧B ¬(A ∧ B) ¬A ¬B ¬A ∨ ¬B
0 0 0 1 1 1 1
0 1 0 1 1 0 1
1 0 0 1 0 1 1
1 1 1 0 0 0 0
3.3. BOOLEAN FUNCTIONS AND CONNECTIVES 37
Notice that the rows in which the ¬(A ∧ B) column has a 1 are exactly the same as the rows in which the
¬A ∨ ¬B column has a 1. Therefore, ¬(A ∧ B) is semantically equivalent to ¬A ∨ ¬B.
The idea is that there’s no real need to introduce this connective because for any ϕ, ψ ∈ F ormP we would
have that ϕ ↔ ψ is semantically equivalent to (ϕ → ψ) ∧ (ψ → ϕ).
Perhaps we could be more exotic and introduce a new connective with takes three formulas allowing
us to form the formulas ϕψθ (here’s an instance when Polish notation becomes important), and extend
our definition of v so that
(
1 if at least two of v(ϕ) = 1, v(ψ) = 1, v(θ) = 1
v(ϕψθ) =
0 otherwise
It’s not hard (and a good exercise) to show that for any ϕ, ψ, θ ∈ F ormP , there exists α ∈ F ormP such that
ϕψθ is semantically equivalent to α. We want a general theorem which says that no matter how exotic a
connective one invents, it’s always possible to find an element of F ormP which is semantically equivalent,
and thus our choice of connectives is sufficient to express everything we’d ever want.
Rather than deal with arbitrary connectives, the real issue here is whether we can express any possible
function taking k true/false values to true/false values.
Definition 3.3.1. Let k ∈ N+ . A function f : {0, 1}k → {0, 1} is called a boolean function of arity k.
Definition 3.3.2. Suppose that P = {A0 , A1 , . . . , Ak−1 }. Given ϕ ∈ F ormP , we define a boolean function
Bϕ : {0, 1}k → {0, 1} as follows. Given σ ∈ {0, 1}k , define a truth assignment v : P → {0, 1} by letting
v(Ai ) = σ(i) for all i, and set Bϕ (σ) = v(ϕ).
Theorem 3.3.3. Fix k ∈ N+ , and let P = {A0 , A1 , . . . , Ak−1 }. For any boolean function f : {0, 1}k → {0, 1}
of arity k, there exists ϕ ∈ F ormP such that f = Bϕ .
In fact, we’ll prove a stronger theorem below which says that we may assume that our formula ϕ is in a
particularly simple form.
Let’s look at an example before we do the proof. Suppose that f : {0, 1}3 → {0, 1} is given by
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1
38 CHAPTER 3. PROPOSITIONAL LOGIC
Suppose we wanted to come up with a formula ϕ such that f = Bϕ . One option is to use a lot of thought
to come up with an elegant solution. Another is simply to think as follows. Since f (000) = 1, perhaps we
should put
¬A0 ∧ ¬A1 ∧ ¬A2
into the formula somewhere. Similarly, since f (010) = 1, perhaps we should put
¬A0 ∧ A1 ∧ ¬A2
into the formula somewhere. If we do the same to the other lines which have value 1, we can put all of these
pieces together in a manner which makes them all play nice by connecting them with ∨. Thus, our formula
is
(¬A0 ∧ ¬A1 ∧ ¬A2 ) ∨ (¬A0 ∧ A1 ∧ ¬A2 ) ∨ (A0 ∧ A1 ∧ ¬A2 ) ∨ (A0 ∧ A1 ∧ A2 )
We now give the general proof.
Definition 3.3.4. A literal is a element of P ∪ {¬A : A ∈ P }. We denote the set of literals by LitP .
Definition 3.3.5.
• Let ConjP = G(Sym∗P , LitP , {h∧ }). We call the elements of ConjP conjunctive formulas.
• Let DisjP = G(Sym∗P , LitP , {h∨ }). We call the elements of DisjP disjunctive formulas.
Definition 3.3.6.
• Let DN FP = G(Sym∗P , ConjP , {h∨ }). We say that an element of DN FP is in disjunctive normal
form.
• Let CN FP = G(Sym∗P , DisjP , {h∧ }). We say that an element of CN FP is in conjunctive normal
form.
Theorem 3.3.7. Fix k ∈ N+ , and let P = {A0 , A1 , . . . , Ak−1 }. For any boolean function f : {0, 1}k → {0, 1}
of arity k, there exists ϕ ∈ DN FP such that f = Bϕ .
Proof. Let T = {σ ∈ {0, 1}k : f (σ) = 1}. If T = ∅, we may let ϕ be A0 ∧ (¬A0 ). Suppose then that T 6= ∅.
For each σ ∈ T , let
k−1
^
ψσ = θi
i=0
where (
Ai if σ(i) = 1
θi =
¬Ai if σ(i) = 0
For each σ ∈ T , notice that ψσ ∈ ConjP because θi ∈ LitP for all i. Finally, let
_
ϕ= ψσ
σ∈T
Since DN FP formulas suffice, we don’t even need → if all we want to do is have the ability to express
all boolean functions. In fact we can also get rid of one of ∧ or ∨ as well (think about why).
3.4. SYNTACTIC IMPLICATION 39
Basic Proofs: Γ ` ϕ if ϕ ∈ Γ.
Rules for ∧: We have two rules for ∧-elimination and one for ∧-introduction.
Γ`ϕ∧ψ Γ`ϕ∧ψ Γ`ϕ Γ`ψ
(∧EL) (∧ER) (∧I)
Γ`ϕ Γ`ψ Γ`ϕ∧ψ
Rules for ∨: We have two rules for introducing ∨.
Γ`ϕ Γ`ψ
(∨IL) (∨IR)
Γ`ϕ∨ψ Γ`ϕ∨ψ
Rules for →:
Γ`ϕ→ψ Γ ∪ {ϕ} ` ψ
(→ E) (→ I)
Γ ∪ {ϕ} ` ψ Γ`ϕ→ψ
Rules for proofs by cases:
Γ ∪ {¬ϕ} ` ψ Γ ∪ {¬ϕ} ` ¬ψ
(Contr)
Γ`ϕ
For the ∨IL rule, we have the function h∨IL : LineP → P(LineP ) by
Definition 3.4.4. Let Γ ⊆ F ormP and let ϕ ∈ F ormP . We write Γ `P ϕ, or simply Γ ` ϕ if P is clear, to
mean that
(Γ, ϕ) ∈ G(LineP , AssumeP , H).
We pronounce Γ ` ϕ as “Γ syntactically implies ϕ”.
Notation 3.4.5.
1. If Γ = ∅, we write ` ϕ instead of ∅ ` ϕ.
Definition 3.4.6. Γ is inconsistent if there exists θ ∈ F ormP such that Γ ` θ and Γ ` ¬θ. Otherwise, we
say that Γ is consistent.
Proof.
{A ∧ B} ` A ∧ B (AssumeP ) (1)
{A ∧ B} ` A (∧EL on 1) (2)
{A ∧ B} ` A ∨ B (∨I on 2) (3)
Proof.
Proof.
Proof.
Proof. The proof is by induction. We let X = {(Γ, ϕ) ∈ G : Γ0 ` ϕ for all Γ0 ⊇ Γ} and we show by induction
on G that X = G. We begin by noting that if ϕ ∈ Γ, then for every Γ0 ⊇ Γ, we have ϕ ∈ Γ0 and hence
Γ0 ` ϕ. Therefore, (Γ, ϕ) ∈ X for all (Γ, ϕ) ∈ AssumeP .
We first handle the ∧EL rule. Suppose that (Γ, ϕ ∧ ψ) ∈ X. We need to show that (Γ, ϕ) ∈ X. Suppose
that Γ0 ⊇ Γ. We then have that Γ0 ` ϕ ∧ ψ by induction (i.e. since (Γ, ϕ ∧ ψ) ∈ X), hence Γ0 ` ϕ by the
∧EL rule. Therefore, (Γ, ϕ) ∈ X. The other ∧ rules and the ∨ rules are similar.
We now handle → E rule. Suppose that (Γ, ϕ → ψ) ∈ X. We need to show that (Γ ∪ {ϕ}, ψ). Suppose
that Γ0 ⊇ Γ ∪ {ϕ}. We then have that Γ0 ⊇ Γ, hence Γ0 ` ϕ → ψ by induction, and so Γ0 ∪ {ϕ} ` ψ by the
→ E rule. However, Γ0 ∪ {ϕ} = Γ0 because ϕ ∈ Γ0 , so Γ0 ` ψ. Therefore, (Γ ∪ {ϕ}, ψ) ∈ X.
We now handle → I rule. Suppose that (Γ ∪ {ϕ}, ψ) ∈ X. We need to show that (Γ, ϕ → ψ). Suppose
that Γ0 ⊇ Γ. We then have that Γ0 ∪ {ϕ} ⊇ Γ ∪ {ϕ}, hence Γ0 ∪ {ϕ} ` ψ by induction, and so Γ0 ` ϕ → ψ
by the → I rule. Therefore, (Γ, ϕ → ψ) ∈ X.
Let’s go for the ∨P C rule. Suppose that (Γ ∪ {ϕ}, θ) ∈ X and (Γ ∪ {ψ}, θ) ∈ X. We need to show
that (Γ ∪ {ϕ ∨ ψ}, θ) ∈ X. Suppose that Γ0 ⊇ Γ ∪ {ϕ ∨ ψ}. We then have that Γ0 ∪ {ϕ} ⊇ Γ ∪ {ϕ} and
Γ0 ∪ {ψ} ⊇ Γ ∪ {ψ}, hence Γ0 ∪ {ϕ} ` θ and Γ0 ∪ {ψ} ` θ by induction, and so Γ0 ∪ {ϕ ∨ ψ} ` θ by the ¬P C
rule. However, Γ0 ∪ {ϕ ∨ ψ} = Γ0 because ϕ ∨ ψ ∈ Γ0 , so Γ0 ` θ. Therefore, (Γ ∪ {ϕ ∨ ψ}, θ) ∈ X.
Let’s next attack the ¬P C rule. Suppose that (Γ ∪ {ψ}, ϕ) ∈ X and (Γ ∪ {¬ψ}, ϕ) ∈ X. We need to show
that (Γ, ϕ) ∈ X. Suppose that Γ0 ⊇ Γ. We then have that Γ0 ∪ {ψ} ⊇ Γ ∪ {ψ} and Γ0 ∪ {¬ψ} ⊇ Γ ∪ {¬ψ},
hence Γ0 ∪ {ψ} ` ϕ and Γ0 ∪ {¬ψ} ` ϕ by induction, and so Γ0 ` ϕ by the ¬P C rule. Therefore, (Γ, ϕ) ∈ X.
We finish off with the Contr rule. Suppose that (Γ ∪ {¬ϕ}, ψ) ∈ X and (Γ ∪ {¬ϕ}, ¬ψ) ∈ X. We need to
show that (Γ, ϕ) ∈ X. Suppose that Γ0 ⊇ Γ. We then have that Γ0 ∪ {¬ϕ} ⊇ Γ ∪ {¬ϕ}, hence Γ0 ∪ {¬ϕ} ` ψ
and Γ0 ∪ {¬ϕ} ` ¬ψ by induction, and so Γ0 ` ϕ by the Contr rule. Therefore, (Γ, ϕ) ∈ X.
The result follows by induction.
42 CHAPTER 3. PROPOSITIONAL LOGIC
Proof. Fix θ such that Γ ` θ and Γ ` ¬θ, and fix ϕ ∈ F ormP . We have that Γ ∪ {¬ϕ} ` θ and Γ ∪ {¬ϕ} ` ¬θ
by Proposition 3.4.11. Therefore, Γ ` ϕ by using the Contr rule.
Proposition 3.4.13.
Proof.
1. Since Γ ∪ {ϕ} is inconsistent, we know that Γ ∪ {ϕ} ` ¬ϕ by Proposition 3.4.12. Since we also have
that Γ ∪ {¬ϕ} ` ¬ϕ by AssumeP , it follows that Γ ` ¬ϕ by the ¬P C rule.
2. Since Γ ∪ {¬ϕ} is inconsistent, we know that Γ ∪ {¬ϕ} ` ϕ by Proposition 3.4.12. Since we also have
that Γ ∪ {ϕ} ` ϕ by AssumeP , it follows that Γ ` ϕ by the ¬P C rule.
Corollary 3.4.14. If Γ ⊆ F ormP is consistent and ϕ ∈ F ormP , then either Γ ∪ {ϕ} is consistent or
Γ ∪ {¬ϕ} is consistent.
Proof. If both Γ ∪ {ϕ} and Γ ∪ {¬ϕ} are inconsistent, then both Γ ` ¬ϕ and Γ ` ϕ by Proposition 3.4.13,
so Γ is inconsistent.
Proposition 3.4.15.
2. If Γ ` ϕ and Γ ` ϕ → ψ, then Γ ` ψ.
Proof.
1. Since Γ ` ϕ, it follows from Proposition 3.4.11 that Γ ∪ {¬ϕ} ` ϕ. Since we also have Γ ∪ {¬ϕ} ` ¬ϕ
by AssumeP , we may conclude that Γ ∪ {¬ϕ} is inconsistent. Therefore, by Proposition 3.4.12, we
have that Γ ∪ {¬ϕ} ` ψ. Now we also have Γ ∪ {ϕ} ` ψ by assumption, so the ¬P C rule gives that
Γ ` ψ.
2. Since Γ ` ϕ → ψ, we can conclude that Γ ∪ {ϕ} ` ψ by rule → E. The result follows from part 1.
Proof. The proof is by induction. We let X = {(Γ, ϕ) ∈ G : there exists a finite Γ0 ⊆ Γ such that Γ0 ` ϕ}
and we show by induction on G that X = G. We begin by noting that if ϕ ∈ Γ, then we have {ϕ} is a finite
subset of Γ and {ϕ} ` ϕ. Therefore, (Γ, ϕ) ∈ X for all (Γ, ϕ) ∈ AssumeP .
We first handle the ∧EL rule. Suppose that (Γ, ϕ ∧ ψ) ∈ X. We need to show that (Γ, ϕ) ∈ X. By
induction (i.e. since (Γ, ϕ ∧ ψ) ∈ X), we may fix a finite Γ0 ⊆ Γ such that Γ0 ` ϕ ∧ ψ. We then have that
Γ0 ` ϕ by the ∧EL rule. Therefore, (Γ, ϕ) ∈ X. The other ∧ER rule and the ∨ rules are similar.
We now handle the ∧I rule. Suppose that (Γ, ϕ) ∈ X and (Γ, ψ) ∈ X. We need to show that (Γ, ϕ ∧ ψ) ∈
X. By induction, we may fix a finite Γ0 ⊆ Γ such that Γ0 ` ϕ and we may fix a finite Γ1 ⊆ Γ such that
Γ1 ` ψ. We then have that Γ0 ∪ Γ1 ` ϕ and Γ0 ∪ Γ1 ` ψ by Proposition 3.4.11, hence Γ0 ∪ Γ1 ` ϕ ∧ ψ by the
∧I rule. Therefore, (Γ, ϕ ∧ ψ) ∈ X because Γ0 ∪ Γ1 is a finite subset of Γ.
3.5. SOUNDNESS AND COMPLETENESS 43
We now handle → E rule. Suppose that (Γ, ϕ → ψ) ∈ X. We need to show that (Γ ∪ {ϕ}, ψ) ∈ X. By
induction, we may fix a finite Γ0 ⊆ Γ such that Γ0 ` ϕ → ψ. We then have that Γ0 ∪ {ϕ} ` ψ by the → E
rule. Therefore, (Γ ∪ {ϕ}, ψ) ∈ X because Γ0 ∪ {ϕ} is a finite subset of Γ ∪ {ϕ}.
We now handle → I rule. Suppose that (Γ ∪ {ϕ}, ψ) ∈ X. We need to show that (Γ, ϕ → ψ) ∈ X. By
induction, we may fix a finite Γ0 ⊆ Γ ∪ {ϕ} such that Γ0 ` ψ. Let Γ00 = Γ0 − {ϕ}. We then have that
Γ0 ⊆ Γ00 ∪ {ϕ}, hence Γ00 ∪ {ϕ} ` ψ by Proposition 3.4.11, and so Γ00 ` ϕ → ψ by the → I rule. Therefore,
(Γ, ϕ → ψ) ∈ X because Γ00 is a finite subset of Γ.
The other rules are exercises. The result follows by induction.
Corollary 3.4.17. If every finite subset of Γ is consistent, then Γ is consistent.
Proof. Suppose that Γ is inconsistent, and fix θ ∈ F ormP such that Γ ` θ and Γ ` ¬θ. By Proposition
3.4.16, there exists finite sets Γ0 ⊆ Γ and Γ1 ⊆ Γ such that Γ0 ` θ and Γ1 ` ¬θ. Using Proposition 3.4.11,
it follows that Γ0 ∪ Γ1 ` θ and Γ0 ∪ Γ1 ` ¬θ, so Γ0 ∪ Γ1 is a finite inconsistent subset of Γ.
Proposition 3.5.3. Suppose that P is countable. If Γ is consistent, then there exists a set ∆ ⊇ Γ which is
consistent and complete.
Proof. Since P is countable, it follows that F ormP is countable. List F ormP as ψ1 , ψ2 , ψ3 , . . . . We define a
sequence of sets Γ0 , Γ1 , Γ2 , . . . recursively as follows. Let Γ0 = Γ. Suppose that n ∈ N and we have defined
Γn . Let (
Γn ∪ {ψn } if Γn ∪ {ψn } is consistent
Γn+1 =
Γn ∪ {¬ψn } otherwise
S
Using induction and Corollary 3.4.14, it follows that Γn is consistent for all n ∈ N. Let ∆ = n∈N Γn .
We first argue that ∆ is consistent. For any finite subset ∆0 of ∆, there exists an n ∈ N such that
∆0 ⊆ Γn , and so ∆0 is consistent because every Γn is consistent. Therefore, ∆ is consistent by Proposition
3.4.17. We end by arguing that ∆ is complete. Fix ϕ ∈ F ormP , and fix n ∈ N+ such that ϕ = ψn . By
construction, we either have ϕ ∈ Γn ⊆ ∆ or ¬ϕ ∈ Γn ⊆ ∆. Therefore, ∆ is complete.
Proof. Suppose that ∆ is maximal consistent. We certainly have that ∆ is consistent. Fix ϕ ∈ F ormP . By
Corollary 3.4.14, either ∆ ∪ {ϕ} is consistent or ∆ ∪ {¬ϕ} is consistent. If ∆ ∪ {ϕ} is consistent, then ϕ ∈ ∆
because ∆ is maximal consistent. Similarly, If ∆ ∪ {¬ϕ} is consistent, then ¬ϕ ∈ ∆ because ∆ is maximal
consistent. Therefore, either ϕ ∈ ∆ or ¬ϕ ∈ ∆.
Suppose that ∆ is consistent and complete. Suppose that ∆0 ⊃ ∆ and fix ϕ ∈ ∆0 − ∆. Since ∆ is
complete and ϕ ∈ / ∆, we have ¬ϕ ∈ ∆. Therefore, ∆0 ` ϕ and ∆0 ` ¬ϕ, so ∆0 is inconsistent. It follows that
∆ is maximal consistent.
Proposition 3.5.6. If Γ is consistent, then there exists a set ∆ ⊇ Γ which is consistent and complete.
Proof. Let S = {Φ ⊆ F ormP : Γ ⊆ Φ and Φ is consistent}, and S order S be ⊆. Notice that S is nonempty
because Γ ∈ S. Suppose that C ⊆ S is a chain in S. Let Ψ = C = {ψ ∈ F ormP : ψ ∈ Φ for some Φ ∈ C}.
We need to argue that Ψ is consistent. Suppose that Ψ0 is a finite subset of Ψ, say Ψ0 = {ψ1 , ψ2 , . . . , ψn }.
For each ψi , fix Φi ∈ C with ψi ∈ Φi . Since C is a chain, there exists j such that Φj ⊇ Φi for all i. Now
Φj ∈ C ⊆ S, so Φj is consistent, and hence Ψ0 is consistent. Therefore, Ψ is consistent by Proposition 3.4.17.
It follows that Ψ ∈ S and using the fact that Φ ⊆ Ψ for all Φ ∈ C, we may conclude that C has an upper
bound.
Therefore, by Zorn’s Lemma, S has a maximal element ∆. Notice that ∆ is maximal consistent, hence
∆ is complete and consistent by Proposition 3.5.5.
1. ¬ϕ ∈ ∆ if and only if ϕ ∈
/ ∆.
3.5. SOUNDNESS AND COMPLETENESS 45
Proof.
1. If ¬ϕ ∈ ∆, then ϕ ∈
/ ∆ because otherwise ∆ ` ϕ and so ∆ would be inconsistent.
Conversely, if ϕ ∈
/ ∆, then ¬ϕ ∈ ∆ because ∆ is complete.
2. Suppose first that ϕ ∧ ψ ∈ ∆. We then have that ∆ ` ϕ ∧ ψ, hence ∆ ` ϕ by the ∧EL rule and ∆ ` ψ
by the ∧ER rule. Therefore, ϕ ∈ ∆ and ψ ∈ ∆ by Lemma 3.5.7.
Conversely, suppose that ϕ ∈ ∆ and ψ ∈ ∆. We then have ∆ ` ϕ and ∆ ` ψ, hence ∆ ` ϕ ∧ ψ by the
∧I rule. Therefore, ϕ ∧ ψ ∈ ∆ by Lemma 3.5.7.
A ∈ ∆ ⇔ v(A) = 1 ⇔ v(A) = 1
by our definition of v.
46 CHAPTER 3. PROPOSITIONAL LOGIC
¬ϕ ∈ ∆ ⇔ ϕ ∈
/∆ (by Lemma 3.5.8)
⇔ v(ϕ) = 0 (by induction)
⇔ v(¬ϕ) = 1
and
and finally
ϕ→ψ∈∆⇔ϕ∈
/ ∆ or ψ ∈ ∆ (by Lemma 3.5.8)
⇔ v(ϕ) = 0 or v(ψ) = 1 (by induction)
⇔ v(ϕ → ψ) = 1
Therefore, by induction, we have ϕ ∈ ∆ if and only if v(ϕ) = 1. In particular, we have v(ϕ) = 1 for all
ϕ ∈ ∆, hence ∆ is satisfiable.
2. If Γ ϕ, then Γ ` ϕ.
Proof.
1. Suppose that Γ is consistent. By Proposition 3.5.6, we may fix ∆ ⊇ Γ which is consistent and complete.
Now ∆ is satisfiable by Proposition 3.5.9, so we may fix v : P → {0, 1} such that v(δ) = 1 for all δ ∈ ∆.
Since Γ ⊆ ∆, it follows that v(γ) = 1 for all γ ∈ Γ, hence Γ is satisfiable.
2. Suppose that Γ ϕ. We then have that Γ ∪ {¬ϕ} is unsatisfiable, hence Γ ∪ {¬ϕ} is inconsistent by
part 1. It follows from Proposition 3.4.13 that Γ ` ϕ.
We use the Compactness Theorem to show that Γ is satisfiable. Suppose that Γ0 ⊆ Γ is finite. Let
{u1 , u2 , . . . , un } be all of the elements u ∈ V such that Au,i occurs in some element of Γ0 for some i. Since
every finite subgraph of G is k-colorable, we may fix a k-coloring f : {u1 , u2 , . . . , un } → [k] such that whenever
u` and um are linked by an edge of E, we have f (u` ) 6= f (um ). If we define a truth assignment v : P → {0, 1}
by (
1 if w = u` and f (u` ) = i
v(Aw,i ) =
0 otherwise
we see that v(ϕ) = 1 for all ϕ ∈ Γ0 . Thus, Γ0 is satisfiable. Therefore, Γ is satisfiable by the Compactness
Theorem.
Fix a truth assignment v : P → {0, 1} such that v(ϕ) = 1 for all ϕ ∈ Γ. Notice that for each u ∈ V ,
there exists a unique i such that v(Au,i ) = 1 because of the first two sets in the definition of Γ. If we define
f : V → {1, 2, . . . , k} by letting f (u) be the unique i such that v(Au,i ) = 1, then for all u, w ∈ V linked by
an edge in E we have that f (u) 6= f (w) (because of the third set in the definition of Γ). Therefore, G is
k-colorable.
Corollary 3.6.4. Every (possibly infinite) planar graph is 4-colorable.
Definition 3.6.5. A set T ⊆ {0, 1}∗ is called a tree if whenever σ ∈ T and τ ⊆ σ, we have τ ∈ T .
Theorem 3.6.6 (Weak König’s Lemma). Suppose that T ⊆ {0, 1}∗ is a tree which is infinite. There exists
an f : N → {0, 1} such that f [n] ∈ T for all n ∈ N.
Proof. Let P = {Aσ : σ ∈ T }. For each n ∈ N, let Tn = {σ ∈ T : |σ| = n} and notice that Tn 6= ∅ for all
n ∈ N because T is infinite. Let
_
Γ={ Aσ : n ∈ N} ∪ {¬(Aσ ∧ Aτ ) : σ, τ ∈ Tn and σ 6= τ }
σ∈Tn
∪ {(Aσ → Aτ ) : σ, τ ∈ T, τ ⊆ σ}
48 CHAPTER 3. PROPOSITIONAL LOGIC
We use the Compactness Theorem to show that Γ is satisfiable. Suppose that Γ0 ⊆ Γ is finite. Let
Σ = {σ1 , σ2 , . . . , σk } be all of the elements σ ∈ {0, 1}∗ such that Aσ occurs in some element of Γ0 . Let
n = max{|σ1 |, |σ2 |, . . . , |σk |}. Since Tn 6= ∅, we may fix τ ∈ Tn . If we define a truth assignment v : P → {0, 1}
by (
1 if σ ⊆ τ
v(Aσ ) =
0 otherwise
we see that v(ϕ) = 1 for all ϕ ∈ Γ0 . Thus, Γ0 is satisfiable. Therefore, Γ is satisfiable by the Compactness
Theorem.
Fix a truth assignment v : P → {0, 1} such that v(ϕ) = 1 for all ϕ ∈ Γ. Notice that for each n ∈ N+ ,
there exists a unique σ ∈ Tn such that v(Aσ ) = 1 because of the first two sets in the definition of Γ. For
each n, denote the unique such σ by ρn and notice that ρm ⊆ ρn whenver m ≤ n. Define f : N → {0, 1} by
letting f (n) = ρn+1 (n). We then have that f [n] = ρn ∈ T for all n ∈ N.
Proof.
3. We have a 6= 0, hence −a 6= 0. Suppose that −a > 0. We would then have a + (−a) > 0, hence 0 > 0,
a contradiction.
4. Similar to 3.
Definition 3.6.12. An abelian group (A, +, 0) is torsion-free if every nonzero element of A has infinite
order.
Proof. Let (A, +, 0) be an ordered abelian group. Let a ∈ A. If a > 0, then we have n · a > 0 for every
n ∈ N+ by induction. If a < 0, then we have n · a < 0 for every n ∈ N+ by induction.
Proof. First notice that every finitely generated torsion-free abelian group is isomorphic to Zn for some n,
which we can order lexicographically from above. We can transer this ordering across the isomorphism to
order our finitely generated abelian group.
Suppose now that A is an arbitrary torsion-free abelian group. Let P be the set {La,b : a, b ∈ A} and let
Γ be the union of the sets
• {La,a : a ∈ A}.
• {¬(La,b ∧ Lb,a ) : a, b ∈ A, a 6= b}
We show that Γ is satisfiable. By Compactness, it suffices to show that any finite subset of Γ is satisfiable.
Suppose that Γ0 ⊆ Γ is finite, and let S the finite subset of A consisting of all elements of A which appear
as a subscript of a symbol occuring in Γ0 . Let B be the subgroup of A generated by S. We then have that
B is a finitely generated torsion-free abelian group, so from above we may fix an order ≤ on it. If we define
a truth assignment v : P → {0, 1} by
(
1 if a ≤ b
v(La,b ) =
0 otherwise
we see that v(ϕ) = 1 for all ϕ ∈ Γ0 . Thus, Γ0 is satisfiable. Therefore, Γ is satisfiable by the Compactness
Theorem.
Fix a truth assignment v : P → {0, 1} such that v(γ) = 1 for all γ ∈ Γ. Define ≤ on A2 by letting a ≤ b
if and only if v(La,b ) = 1. We then have that ≤ orders A. Therefore, A can be ordered.
Chapter 4
Now that we’ve succeeded in giving a decent analysis of propositional logic, together with proving a few
nontrivial theorems, it’s time to move on to a much more substantial and important logic: first-order logic.
As summarized in the introduction, the general idea is as follows. Many areas of mathematics deal with
mathematical structures consisting of special constants, relations, and functions, together with certain axioms
that these objects obey. We want our logic to be able to handle many different types of situations, so we
allow ourselves to vary the number and types of these symbols. Any such choice gives rise to a language,
and once we’ve fixed such a language, we can build up formulas which will express something meaningful
once we’ve decided on an interpretation of the symbols.
51
52 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
Definition 4.1.4. Let L be a language. For each f ∈ Fk , define hf : (Sym∗L )k → Sym∗L by letting
hf (σ1 , σ2 , . . . , σk ) = fσ1 σ2 · · · σk
Let
T ermL = G(Sym∗L , C ∪ V ar, {hf : f ∈ F})
Now that we have terms which intuitively name elements once we’ve fixed an interpretation, we need to
say what our atomic formulas are. The idea is that the most basic things we can say are whether or not two
objects are equal or whether or not a k-tuple is in the interpretation of some relation symbol R ∈ Rk .
Definition 4.1.5. Let L be a language. We let
AtomicF ormL = {Rt1 t2 · · · tk : k ∈ N+ , R ∈ Rk , and t1 , t2 , . . . , tk ∈ T ermL } ∪ {= t1 t2 : t1 , t2 ∈ T ermL }
From here, we can build up all formulas.
Definition 4.1.6. Let L be a language. Define a unary function h¬ and binary functions h∧ , h∨ , and h→
on Sym∗L as follows.
h¬ (σ) = ¬σ
h∧ (σ, τ ) = ∧στ
h∨ (σ, τ ) = ∨στ
h→ (σ, τ ) =→ στ
Also, for each x ∈ V ar, define two unary functions h∀,x and h∃,x on Sym∗L as follows
h∀,x (σ) = ∀xσ
h∃,x (σ) = ∃xσ
Let
F ormL = G(Sym∗L , AtomicF ormL , {h¬ , h∧ , h∨ , h→ } ∪ {h∀,x , h∃,x : x ∈ V ar})
As with propositional logic, we’d like to be able to define things recursively, so we need to check that our
generating systems are free. Notice that in the construction of formulas, we have two generating systems
around. We first generate all terms. With terms taken care of, we next describe the atomic formulas, and
from them we generate all formulas. Thus, we’ll need to prove that two generating systems are free. The
general idea is to make use of the insights gained by proving the corresponding result for Polish notation in
propositional logic.
Definition 4.1.7. Let L be a language. Define K : Sym∗L → Z as follows. We first define w : SymL → Z
as follows.
w(c) = 1 for all c ∈ C
w(f) = 1 − k for all f ∈ Fk
w(R) = 1 − k for all R ∈ Rk
w(x) = 1 for all x ∈ V ar
w(=) = −1
w(Q) = −1 for all Q ∈ {∀, ∃}
w(¬) = 0
w(3) = −1 for all 3 ∈ {∧, ∨, →}
Sym∗L
P
We then define K on all of by letting K(λ) = 0 and letting K(σ) = i<|σ| w(σ(i)) for all σ ∈
Sym∗L \{λ}.
4.1. THE SYNTAX OF FIRST-ORDER LOGIC 53
Proof. The proof is by induction on t. Notice first that K(c) = 1 for all c ∈ C and K(x) = 1 for all x ∈ V ar.
Suppose that k ∈ N+ , f ∈ Fk , and t1 , t2 , . . . , tk ∈ T ermL are such that K(ti ) = 1 for all i. We then have
that
Proof. The proof is by induction on t. For every c ∈ C, this is trivial because the only σ ⊂ c is σ = λ and
we have K(λ) = 0. Similarly, for every x ∈ V ar, the only σ ⊂ x is σ = λ and we have K(λ) = 0.
Suppose that k ∈ N+ , f ∈ Fk , and t1 , t2 , . . . , tk ∈ T ermL are such that the result holds for each ti . We
prove the result for ft1 t2 · · · tk . Suppose that σ ⊂ ft1 t2 · · · tk . If σ = λ, then K(σ) = 0. Otherwise, there
exists i < k and τ ⊂ ti such that σ = ft1 t2 · · · ti−1 τ , in which case
Theorem 4.1.12. The generating system (Sym∗L , C ∪ V ar, {hf : f ∈ F}) is free.
Proof. First notice that for all f ∈ F, we have that ran(hf (T ermL )k ) ∩ (C ∪ V ar) = ∅ because all elements
of ran(hf ) begin with f and we know that f ∈ / C ∪ V ar.
Fix f ∈ Fk . Suppose that t1 , t2 , . . . , tk , u1 , u2 , . . . , uk ∈ T ermL and hf (t1 , t2 , . . . , tk ) = hf (u1 , u2 , . . . , uk ).
We then have ft1 t2 · · · tk = fu1 u2 · · · uk , hence t1 t2 · · · tk = u1 u2 · · · uk . Since t1 ⊂ u1 and u1 ⊂ t1 are both
impossible by Corollary 4.1.11, it follows that t1 = u1 . Thus, t2 · · · tk = u2 · · · uk , and so t2 = u2 for the
same reason. Continuing in this fashion, we conclude that ti = ui for all i. It follows that hf (T ermL )k is
injective.
Finally notice that for any f ∈ Fk and any g ∈ F` with f 6= g, we have that ran(hf (T ermL )k ) ∩
ran(hg (T ermL )` ) = ∅ because all elements of ran(hf (T ermL )k ) begin with f while all elements of
ran(hg (T ermL )` ) begin with g.
Proof. The proof is by induction on ϕ. We first show that K(ϕ) = 1 for all ϕ ∈ AtomicF ormL . Suppose
that ϕ is Rt1 t2 · · · tk where R ∈ Rk and t1 , t2 , . . . , tk ∈ T ermL . We then have
Suppose now that ϕ, ψ ∈ F ormL are such that K(ϕ) = 1 = K(ψ), and 3 ∈ {∧, ∨, →}. We then have that
Thus, the result holds for Rt1 t2 · · · tk . The same argument works for = t1 t2 where t1 , t2 ∈ T ermL , so the
result holds for all ϕ ∈ AtomicF ormL .
4.1. THE SYNTAX OF FIRST-ORDER LOGIC 55
Suppose that the result holds for ϕ ∈ F ormL . Suppose that σ ⊂ ¬ϕ. If σ = λ, then K(σ) = 0.
Otherwise, σ = ¬τ for some τ ⊂ ϕ, in which case
Suppose now that Q ∈ {∀, ∃}, that x ∈ V ar, and that σ ⊂ Qxϕ. If σ = λ, then K(σ) = 0, and if σ = Q,
then K(σ) = −1. Otherwise, σ = Qxτ for some τ ⊂ ϕ, in which case
Suppose now that the result holds for ϕ, ψ ∈ F ormL , and 3 ∈ {∧, ∨, →}. Suppose that σ ⊂ 3ϕψ. If σ = λ,
then K(σ) = 0. If σ is 3τ for some τ ⊂ ϕ, then
Theorem 4.1.16. The generating system (Sym∗L , AtomicF ormL , {h¬ , h∧ , h∨ , h→ } ∪ {h∀,x , h∃,x : x ∈ V }) is
free.
With these freeness results, we are now able to define functions recursively on T ermL and F ormL . Since
we use terms in our definition of atomic formulas, which are the basic formulas, we will often need to make
two recursive definitions (on terms first, then on formulas) in order to define a function on formulas. Here’s
an example.
Example 4.2.2. Let L = {R} where R is a binary relation symbol. Here are some examples of L-structures.
4. M = {0, 1, 2, 3, 4} and RM = {(0, 2), (3, 3), (4, 1), (4, 2), (4, 3)}.
Example 4.2.3. Let L = {c, f} where c is a constant symbol and f is a binary function symbol. Here are
some examples of L-structures.
3. For any group (G, e, ·), we get an L-structure by letting M = G, cM = e, and letting f M be the group
operation.
At first, it may appear than an L-structure provides a means to make sense out of any formula. However,
this is not the case, as you can see by looking at the formula x = y where x, y ∈ V ar. Until we provide a way
to interpret the elements of V ar, this formula is meaningless. This motivates the following definition.
Recall in propositional logic that every truth assignment v : P → {0, 1} gave rise to an extension
v : F ormP → {0, 1} telling us how to interpret every formula. In our case, every variable assignment
s : V ar → M gives rise to an extension s : T ermL → M telling us which element of M to assign to each
term.
We’re now in position to define the intuitive statement “ϕ holds in the L-structure M with variable
assignment s” recursively. We need the following definition.
58 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
3. For every s, we have (M, s) ∀x(Rx → (fx = x)). To see this, fix s : V ar → M . We have
(M, s) ∀x(Rx → (f(x) = x)) ⇔ For all a ∈ M, we have (M, s[x ⇒ a]) (Rx → (fx = x))
⇔ For all a ∈ M, we have either
(M, s[x ⇒ a]) 6 Rx or (M, s[x ⇒ a]) (fx = x)
⇔ For all a ∈ M, we have either
/ RM or s[x ⇒ a](fx) = s[x ⇒ a](x)
s[x ⇒ a](x) ∈
⇔ For all a ∈ M, we have either
/ RM or f M (s[x ⇒ a](x)) = s[x ⇒ a](x)
s[x ⇒ a](x) ∈
⇔ For all a ∈ M, we have either
/ RM or f M (s[x ⇒ a](x)) = s[x ⇒ a](x)
s[x ⇒ a](x) ∈
/ RM or f M (a) = a
⇔ For all a ∈ M, we have either a ∈
/ RM , f M (1) = 1, 2 ∈
which is true because 0 ∈ / RM , and f M (3) = 3.
In the above examples, it’s clear that only the value of s on the free variables in ϕ affect whether or not
(M, s) ϕ. The following precise statement of this fact follows by a straightforward induction.
Proposition 4.2.8. Let M be an L-structure. Suppose that t ∈ T ermL and s1 , s2 : V ar → M are two
variable assignments such that s1 (x) = s2 (x) for all x ∈ OccurV ar(t). We then have s1 (t) = s2 (t).
Proposition 4.2.9. Let M be an L-structure. Suppose that ϕ ∈ F ormL and s1 , s2 : V ar → M are two
variable assignments such that s1 (x) = s2 (x) for all x ∈ F reeV ar(ϕ). We then have
3. As a special case of 2, we have the following. Suppose that M is an L-structure and σ ∈ SentL . We
write M σ to mean that (M, s) σ for some (any) s : V ar → M .
Definition 4.2.11. Let L be a language, and let Σ ⊆ SentL . We let M od(Σ) be the class of all L-structures
M such that M σ for all σ ∈ Σ. If σ ∈ SentL , we write M od(σ) instead of M od(Σ).
Example. Let L be any language whatsoever, and let n ∈ N+ . The class of L-structures of cardinality at
least n is an elementary class as witnessed by the formula:
^
∃x1 ∃x2 · · · ∃xn ( 6 xj ))
(xi =
1≤i<j≤n
Furthermore, the class of L-structures of cardinality equal to n is an elementary class. Letting σn be the
above formula for n, we can see this by considering σn ∧ (¬σn+1 ).
Examples. Let L = {0, 1, +, ·} where 0, 1 are constant symbols and +, · are binary function symbols.
1. The class of fields is an elementary class. We may let Σ be the following collection of sentences:
(a) ∀x∀y∀z(x + (y + z) = (x + y) + z)
(b) ∀x((x + 0 = x) ∧ (0 + x = x))
(c) ∀x∃y((x + y = 0) ∧ (y + x = 0))
(d) ∀x∀y(x + y = y + x)
(e) ∀x∀y∀z(x · (y · z) = (x · y) · z)
(f) ∀x((x · 1 = x) ∧ (1 · x = x))
(g) ∀x(x 6= 0 → ∃y((x · y = 1) ∧ (y · x = 0)))
4.2. STRUCTURES: THE SEMANTICS OF FIRST-ORDER LOGIC 61
(h) ∀x∀y(x · y = y · x)
(i) ∀x∀y∀z(x · (y + z) = (x · y) + (x · z))
2. For each prime p > 0, the class of fields of characteristic p is an elementary class. Fix a prime p > 0,
and let Σp be the above sentences togheter with the sentence 1 + 1 + · · · + 1 = 0 (where there are p
1’s in the sum).
3. The class of fields of characteristic 0 is a weak elementary class. Let Σ be the above sentences together
with {τn : n ∈ N+ } where for each n ∈ N+ , we have τn = ¬(1 + 1 + · · · + 1 = 0) (where there are n 1’s
in the sum).
Example. Let F be a field, and let LF = {0, +} ∪ {hα : α ∈ F } where 0 is a constant symbol, + is binary
function symbol, and each hα is a unary function symbol. The class of vector spaces over F is a weak
elementary class. We may let Σ be the following collection of sentences:
1. ∀x∀y∀z(x + (y + z) = (x + y) + z)
2. ∀x((x + 0 = x) ∧ (0 + x = x))
3. ∀x∃y((x + y = 0) ∧ (y + x = 0))
4. ∀x∀y(x + y = y + x)
8. ∀x(h1 (x) = x)
At this point, it’s often clear how to show that a certain class of structures is a (weak) elementary class:
simply exhibit the correct sentences. However, it may seem very difficult to show that a class is not a (weak)
elementary class. For example, is the class of fields of characteristic 0 an elementary class? Is the class of
finite groups a weak elementary class? There are no obvious ways to answer these questions affirmatively.
We’ll develop some tools later which will allow us to resolve these questions.
Another interesting case is that of Dedekind-complete ordered fields. Now the ordered field axioms are
easily written down in the first-order language L = {0, 1, <, +, ·}. In contrast, the Dedekind-completeness
axiom, which says that every nonempty subset which is bounded above has a least upper bound, can not
be directly translated in the language L because it involves quantifying over subsets instead of elements.
However, we are unable to immediately conclude that this isn’t due to a lack of cleverness on our part.
Perhaps there is an alternative approach which captures Dedekind-complete ordered fields in a first-order
way (by finding a clever equivalent first-order expression of Dedekind-completeness). More formally, the
precise question is whether the complete ordered fields are a (weak) elementary class in the language L.
We’ll be able to answer this question later.
62 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
X = {(a1 , a2 , . . . , ak ) ∈ M k : (M, a1 , a2 , . . . , ak ) ϕ}
Examples. Let L = {0, 1, +, ·} where 0 and 1 are constant symbols and + and · are binary function symbols.
∃z(z 6= 0 ∧ (x + z = y))
∃y(y · y = x)
Example.
1. Let L = {<} where < is a binary relation symbol. For every n ∈ N, the set {n} is definable in (N, <).
To see this, first define ϕn (x) to be the formula
^ n
^
∃y1 ∃y2 · · · ∃yn ( (yi 6= yj ) ∧ (yi < x))
1≤i<j≤n i=1
¬∃y(y < x)
and for each n ∈ N+ , the set {n} is definable as witnessed by the formula
2. Let L = {e, f} where e is a constant symbol and f is a binary function symbol. Let (G, e, ·) be a group
interpreted as an L-stucture. The center of G is definable in (G, e, ·) as witnessed by the formula
Sometimes, there isn’t an obvious way to show that a set is definable, but some cleverness really pays off.
Examples. Let L = {0, 1, +, ·} where 0 and 1 are constant symbols and + and · are binary function symbols.
4.2. STRUCTURES: THE SEMANTICS OF FIRST-ORDER LOGIC 63
because by Lagrange’s Theorem, every natural number is the sum of four squares.
3. The set Z is definable in (Q, 0, 1, +, ·). This is a deep result of Julia Robinson.
As for elementary classes, it’s clear how to attempt to show that something is definable (although as
we’ve seen this may require a great deal of cleverness). However, it’s not at all obvious how one could show
that a set is not definable. We’ll develop a few tools to do this in time.
4.2.4 Substitution
In time, we will see the need to “substitute” terms for variables. Roughly, you would think that if ∀xϕ was
true in some structure, then when you take any term and substitute it in for x in the formula ϕ, the resulting
formula would be true. We need a way to relate truth before substituting with truth after substituting. The
hope would be the following, where we use the notation ϕtx to intuitively mean that you substitute t for x:
Hope 4.2.15. Let M be an L-structure, let s : V ar → M , let t ∈ T ermL , and let x ∈ V ar. For all
ϕ ∈ F ormL , we have
(M, s) ϕtx if and only if (M, s[x ⇒ s(t)]) ϕ
In order to make this precise, we first need to define substitition. Even with the “correct” definition of
substitution, however, the above statement is not true. Let’s first define substitution for terms and show
that it behaves well.
Definition 4.2.16. Let x ∈ V ar and let t ∈ T ermL . We define a function Substtx : T ermL → T ermL
denoted by utx as follows.
3. (fu1 u2 . . . uk )tx = f(u1 )tx (u2 )tx · · · (uk )tx for all f ∈ Fk and all u1 , u2 , . . . , uk ∈ T ermL .
Here’s the key lemma that relates how to interpret a term before and after substitition.
Lemma 4.2.17. Let M be an L-structure, let s : V ar → M , let t ∈ T ermL , and let x ∈ V ar. For all
u ∈ T ermL , we have
s(utx ) = s[x ⇒ s(t)](u)
64 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
s(ctx ) = s(c)
= cM
= s[x ⇒ s(t)](c)
= s[x ⇒ s(t)](c)
s(xtx ) = s(t)
= s[x ⇒ s(t)](x)
= s[x ⇒ s(t)](x)
s(yxt ) = y
= s[x ⇒ s(t)](y)
= s[x ⇒ s(t)](y)
Finally, suppose that f ∈ Fk and that the result holds for u1 , u2 , . . . , uk ∈ T ermL . We then have
With subsitution in terms defined, we now move to define substitution in formals. The key fact about
this definition is that we only replace x by the term t for the free occurances of x because we certainly don’t
want to change ∀xϕ into ∀tϕ, nor do we want to mess with an x inside the scope of such a quantifier. We
thus make the following recursive definition.
Definition 4.2.18. We now define F reeSubstt,x : F ormL → F ormL , again denoted ϕtx , as follows.
1. (Ru1 u2 · · · uk )tx = R(u1 )tx (u2 )tx · · · (uk )tx for all R ∈ Rk and all u1 , u2 , . . . , uk ∈ T ermL .
4. (3ϕψ)tx = 3ϕtx ψxt for all ϕ, ψ ∈ F ormL and all 3 ∈ {∧, ∨, →}.
(
t Qyϕ if x = y
5. (Qyϕ)x =
Qy(ϕtx ) otherwise
for all ϕ ∈ F ormL , y ∈ V ar, and Q ∈ {∃, ∀}.
4.2. STRUCTURES: THE SEMANTICS OF FIRST-ORDER LOGIC 65
With the definition in hand, let’s analyze the above hope. Suppose that L = ∅, and consider the formula
ϕ(y) ∈ F ormL given by
∃x¬(x = y)
For any L-structure M and any s : V ar → M , we have (M, s) ϕ if and only if |M | ≥ 2. Now notice that
the formula ϕxy is
∃x¬(x = x)
so for any L-structure M and any s : V ar → M , we have (M, s) 6 ϕxy . Therefore, the above hope fails
whenever M is an L-stucture with |M | ≥ 2. The problem is that the term we substituted (in this case x)
had a variable which became “captured” by a quantifier, and thus the “meaning” of the formula became
transformed. We thus defined a function which indicates with this does not happen.
Definition 4.2.19. Let t ∈ T ermL and let x ∈ V ar. We define a function V alidSubsttx : F ormL → {0, 1}
as follows.
Theorem 4.2.20 (Substitution Theorem). Let M be an L-structure, let s : V ar → M , let t ∈ T ermL , and
let x ∈ V ar. For all ϕ ∈ F ormL with V alidSubsttx (ϕ) = 1, we have
Proof. The proof is by induction on ϕ. We first handle the case when ϕ ∈ AtomicF ormL . Suppose that
R ∈ Rk and that u1 , u2 , . . . , uk ∈ T ermL . We then have
(M, s) (Ru1 u2 · · · uk )tx ⇔ (M, s) R(u1 )tx (u2 )tx · · · (uk )tx
⇔ (s((u1 )tx ), s((u2 )tx ), · · · , s((uk )tx )) ∈ RM
⇔ (s[x ⇒ s(t)](u1 ), s[x ⇒ s(t)](u2 ), · · · , s[x ⇒ s(t)](uk )) ∈ RM
⇔ (M, s[x ⇒ s(t)]) Ru1 u2 · · · uk
If u1 , u2 ∈ T ermL , we have
Suppose that the results holds for ϕ and that V alidSubsttx (¬ϕ) = 1. We then have that V alidSubsttx (ϕ) = 1,
and hence
Suppose then that x ∈ F reeV ar(∃yϕ), so in particular x 6= y. Since V alidSubsttx (∃yϕ) = 1, we have that
y∈/ OccurV ar(t), and also that V alidSubsttx (ϕ) = 1. Now using the fact that y ∈
/ OccurV ar(t), it follows
that s[y ⇒ a](t) = s(t) for every a ∈ M . Therefore,
Suppose that the result holds for ϕ and that V alidSubsttx (∀yϕ) = 1. First, if x ∈
/ F reeV ar(∃yϕ), we have
Suppose then that x ∈ F reeV ar(∀yϕ), so in particular x 6= y. Since V alidSubsttx (∀yϕ) = 1, we have that
y∈/ OccurV ar(t) and also that V alidSubsttx (ϕ) = 1. Now using the fact that y ∈/ OccurV ar(t), it follows
that s[y ⇒ a](t) = s(t) for every a ∈ M . Therefore,
Notation 4.3.2. Let M and N be L-structures. If M and N are isomorphic, i.e. if there exists an
isomorphism h : M → N , then we write M ∼
= N.
Theorem 4.3.4. Let L be a language, and let M and N be L-structures. Suppose that h : M → N is a
homomorphism, and suppose that s : V ar → M is a variable assignment.
2. For every quantifier-free ϕ ∈ F ormL not containing the equality symbol, we have
Proof.
h(s(c)) = h(cM )
= cN (since h is a homomorphism)
= h ◦ s(c).
h(s(x)) = h(s(x)))
= (h ◦ s)(x)
= h ◦ s(x)
68 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
Suppose now that f ∈ Fk , that t1 , t2 , . . . , tk ∈ T ermL , and the result holds for each ti . We then have
2. Suppose that h is an embedding. We prove the result by induction on ϕ. Suppose first that R ∈ Rk
and that t1 , t2 , . . . , tk ∈ T ermL . We then have
Suppose that the result holds for ϕ. We prove it for ¬ϕ. We have
(M, s) ¬ϕ ⇔ (M, s) 6 ϕ
⇔ (N , h ◦ s) 6 ϕ (by induction)
⇔ (N , h ◦ s) ¬ϕ
3. In light of the proof of 2, we need only show that if ϕ is = t1 t2 where t1 , t2 ∈ T ermL , then (M, s) ϕ
if and only if (N , h ◦ s) ϕ. For any t1 , t2 ∈ T ermL , we have
and also
Definition 4.3.5. Let L be a language, and let M and N be L-structures. We write M ≡ N , and say that
M and N are elementarily equivalent, if for all σ ∈ SentL , we have M σ if and only if N σ.
X = {(a1 , a2 , . . . , ak ) ∈ M k : (M, a1 , a2 , . . . , ak ) ϕ}
Corollary 4.3.8. Suppose that M is an L-structure and k ∈ N+ . Suppose also that X ⊆ M k is and that
h : M → M is an automorphism. If there exists a1 , a2 , . . . , ak ∈ M such that exactly one of the following
holds:
• (a1 , a2 , . . . , ak ) ∈ X
Example. Let L = {R} where R is a binary relation symbol, and let M be the L-structure where M = Z
and RM = {(a, b) ∈ Z2 : a < b}. We show that a set X ⊆ M is definable in M if and only if either X = ∅ or
X = Z. First notice that ∅ is definable as witnessed by ¬(x = x) and Z as witnessed by x = x. Suppose now
that X ⊆ Z is such that X 6= ∅ and X 6= Z. Fix a, b ∈ Z such that a ∈ X and b ∈ / X. Define h : M → M
70 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
by letting h(c) = c + (b − a) for all c ∈ M . Notice that h is automorphism of M because it is bijective (the
map g(c) = c − (b − a) is clearly an inverse) and a homomorphism because if c1 , c2 ∈ Z, then have have
(c1 , c2 ) ∈ RM ⇔ c1 < c2
⇔ c1 + (b − a) < c2 + (b − a)
⇔ h(c1 ) < h(c2 )
⇔ (h(c1 ), h(c2 )) ∈ RM
4.3.3 Substructures
Definition 4.3.9. Let L be a language and let M and A be L-structures. We say that A is a substructure
of M, and we write A ⊆ M if
1. A ⊆ M .
2. cA = cM for all c ∈ C.
3. RA = RM ∩ Ak for all R ∈ Rk .
4. f A = f M Ak for all f ∈ Fk .
Remark 4.3.10. Let L be a language and let M and A be L-structures with A ⊆ M . We then have that
A ⊆ M if and only if the identity map ι : A → M is a homomorphism.
Remark 4.3.11. Suppose that M is an L-structure and that A ⊆ M . A is the universe of a substructure
of M if and only if {cM : c ∈ C} ⊆ A and f M (a1 , a2 , . . . , ak ) ∈ A for all f ∈ Fk and all a1 , a2 , . . . , ak ∈ A.
Proof.
1. This follows from Remark 4.3.10 and Theorem 4.3.4.
2. We prove this by induction. If ϕ is quantifier-free, this follows from part 1. Suppose that we know the
result for ϕ, and suppose that (A, s) ∃xϕ. Fix a ∈ A such that (A, s[x ⇒ a]) ϕ. By induction, we
know that (M, s[x ⇒ a]) ϕ, hence (M, s) ∃xϕ.
3. We prove this by induction. If ϕ is quantifier-free, this follows from part 1. Suppose that we know the
result for ϕ, and suppose that (M, s) ∀xϕ. For every a ∈ A, we then have (M, s[x ⇒ a]) ϕ, and
hence (A, s[x ⇒ a]) ϕ by induction. It follows that (A, s) ∀xϕ.
A σ if and only if M σ
However, notice that A 6 M because if ϕ(x) is the formula ¬∃y(fy = x), we then have that (A, 1) ϕ but
(M, 1) 6 ϕ.
Theorem 4.3.16 (Tarski-Vaught Test). Suppose that A ⊆ M. The following are equivalent.
1. A M.
2. Whenever ϕ ∈ F ormL , x ∈ V ar, and s : V ar → A satisfy (M, s) ∃xϕ, there exists a ∈ A such that
Proof. We first prove that 1 implies 2. Suppose then that A M. Let ϕ ∈ F ormL and s : V ar → A be
such that (M, s) ∃xϕ. Using the fact that A M, it follows that (A, s) ∃xϕ. Fix a ∈ A such that
(A, s[x ⇒ a]) ϕ. Using again the fact that A M, we have (M, s[x ⇒ a]) ϕ.
We now prove that 2 implies 1. We prove by induction on ϕ ∈ F ormL that for all s : V ar → A, we have
(A, s) ϕ if and only if (M, s) ϕ. That is, we let
and prove that X = F ormL by induction. First notice that ϕ ∈ X for all quantifier-free ϕ because A ⊆ M.
Suppose now that ϕ ∈ X. For any s : V ar → A, we have
(A, s) ¬ϕ ⇔ (A, s) 6 ϕ
⇔ (M, s) 6 ϕ (since ϕ ∈ X)
⇔ (M, s) ¬ϕ
72 CHAPTER 4. FIRST-ORDER LOGIC : SYNTAX AND SEMANTICS
Therefore, ¬ϕ ∈ X.
Suppose now that ϕ, ψ ∈ X. For any s : V ar → A, we have
(A, s) ϕ ∧ ψ ⇔ (A, s) ϕ and (A, s) ψ
⇔ (M, s) ϕ and (M, s) ψ (since ϕ, ψ ∈ X)
⇔ (M, s) ϕ ∧ ψ
Therefore, ϕ ∧ ψ ∈ X. Similarly, we have ϕ ∨ ψ ∈ X and ϕ → ψ ∈ X.
Suppose now that ϕ ∈ X and x ∈ V ar. For any s : V ar → A, we have
(A, s) ∃xϕ ⇔ There exists a ∈ A such that (A, s[x ⇒ a]) ϕ
⇔ There exists a ∈ A such that (M, s[x ⇒ a]) ϕ (since ϕ ∈ X)
⇔ (M, s) ∃xϕ (by our assumption 2)
Therefore, ∃xϕ ∈ X.
Suppose now that ϕ ∈ X and x ∈ V ar. We then have that ¬ϕ ∈ X from above, hence ∃x¬ϕ ∈ X from
above, hence ¬∃x¬ϕ ∈ X again from above. Thus, for any s : V ar → A, we have
(A, s) ∀xϕ ⇔ (A, s) ¬∃x¬ϕ
⇔ (M, s) ¬∃x¬ϕ (since ¬∃x¬ϕ ∈ X)
⇔ (M, s) ∀xϕ
Therefore, ∀xϕ ∈ X.
Theorem 4.3.17 (Countable Lowenheim-Skolem-Tarski Theorem). Suppose that L is countable, that M is
an L-structure, and that X ⊆ M is countable. There exists a countable A M such that X ⊆ A.
Proof. Fix an element d ∈ M (this will be used as a “dummy” element of M to ensure that we always have
something to go to when all else fails).
For each ϕ ∈ F ormL and x ∈ V ar such that F reeV ar(ϕ) = {x}, we define an element nϕ,x ∈ M as
follows. If M ∃xϕ, fix an arbitrary m ∈ M such that (M, m) ϕ, and let nϕ,x = m. Otherwise, let
nϕ,x = d.
Now for each ϕ ∈ F ormL and x ∈ V ar such that {x} ( F reeV ar(ϕ), we define a function. Suppose that
F reeV ar(ϕ) = {y1 , y2 , . . . , yk , x}. We define a function hϕ,x : M k → M as follows. Let b1 , b2 , . . . , bk ∈
M . If (M, b1 , b2 , . . . , bk ) ∃xϕ, fix an arbitrary a ∈ M such that (M, b1 , b2 , . . . , bk , a) ϕ, and let
hϕ,x (b1 , b2 , . . . , bk ) = a. Otherwise, let hϕ,x (b1 , b2 , . . . , bk ) = d.
We now let
B = X ∪ {d} ∪ {cM : c ∈ C} ∪ {nϕ,x : x ∈ V ar, ϕ ∈ F ormL , and F reeV ar(ϕ) = {x}}
and we let
A = G(M, B, {f M : f ∈ Fk } ∪ {hϕ,x : ϕ ∈ F ormP , x ∈ V ar})
We then have that A is the universe of a substructure A of M. Notice that X ⊆ A and that by a problem
on Homework 1, we have that A is countable. Thus, we need only show that A M, which we do by the
Tarski-Vaught test. Suppose that ϕ ∈ F ormL , x ∈ V ar, and s : V ar → A are such that (M, s) ∃xϕ.
Suppose first that x ∈ / F reeV ar(ϕ). Since (M, s) ∃xϕ, we may fix m ∈ M such that (M, s[x ⇒ m]) ϕ.
Now using the fact that x ∈ / F reeV ar(ϕ), it follows that (M, s[x ⇒ d]) ϕ.
Suppose now that F reeV ar(ϕ) = {x}, and let a = nϕ,x ∈ A. Since M ∃xϕ, hence (M, a) ϕ by
definition of nϕ,x . It follows that there exists a ∈ A such that (M, s[x ⇒ a]) ϕ.
Finally, suppose that F reeV ar(ϕ) = {y1 , y2 , . . . , yk , x}. For each i with 1 ≤ i ≤ k, let bi = s(yi ), and let
a = hϕ,x (b1 , b2 , . . . , bk ) ∈ A. Since (M, b1 , b2 , . . . , bk ) ∃xϕ, hence (M, b1 , b2 , . . . , bk , a) ϕ by definition of
hϕ,x . It follows that there exists a ∈ A such that (M, s[x ⇒ a]) ϕ.
4.4. CHANGING THE LANGUAGE 73
Corollary 4.3.18. Suppose that L is countable and that M is an L-structure. There exists a countable
L-structure N such that N ≡ M.
Proof. Let N be a countable elementary substructure of M. For any σ ∈ SentL , we then have that N σ
if and only if M σ, so N ≡ M.
This is our first indication that first-order logic is not powerful enough to distinguish certain aspects of
cardinality, and we’ll see more examples of this phenomenon after the Compactness Theorem (for first-order
logic) and once we talk about infinite cardinalities and extend the Lowenheim-Skolem-Tarski result.
This restriction already has some interesting consequences. For example, you may be familiar with the
result that (R, 0, 1, <, +, ·) is the unique (up to isomorphism) Dedekind-complete ordered field.
Corollary 4.3.19. The Dedekind-complete ordered fields are not a weak elementary class in the language
L = {0, 1, <, +, ·}.
Proof. Let K be the class of all Dedekind-complete ordered fields. Suppose that Σ ⊆ SentL is such that
K = M od(Σ). By the Countable Lowenheim-Skolem-Tarski Theorem, there exists a countable N such that
N ≡ (R, 0, 1, <, +, ·). Since (R, 0, 1, <, +, ·) ∈ K, we have (R, 0, 1, <, +, ·) σ for all σ ∈ Σ, so N σ for all
σ ∈ Σ, and hence N ∈ K. However, this is a contradiction because all Dedekind-complete ordered fields are
isomorphic to (R, 0, 1, <, +, ·), hence are uncountable.
Definition 4.3.20. Let L be a language and let M and N be L-structures. Suppose that h : N → M . We
say that h is an elementary embedding if h is an embedding and for all ϕ ∈ F ormL and all s : V ar → N ,
we have
(N , s) ϕ if and only if (M, h ◦ s) ϕ
• M = M 0.
0
• cM = cM for all c ∈ C.
0
• RM = RM for all R ∈ R.
0
• f M = f M for all f ∈ F.
Proposition 4.4.2. Let L ⊆ L0 be languages, let M0 be an L0 -structure, and let M be the restriction of M0
to L. For all ϕ ∈ F ormL and all s : V ar → M , we have (M, s) ϕ if and only if (M0 , s) ϕ.
Proof. By induction.
Proposition 4.4.7. Let L be a language and let M and N be the L-structures. The following are equivalent:
• There exists an embedding h from M to N .
• There exists an expansion of N to an LM -structure which is a model of AtomicDiag(M).
Proposition 4.4.8. Let L be a language and let M and N be the L-structures. The following are equivalent:
• There exists an elementary embedding h from M to N .
• There exists an expansion of N to an LM -structure which is a model of Diag(M).
Chapter 5
• M is an L-structure.
• s : V ar → M is a variable assignment.
Definition 5.1.2. Let L be a language. Let Γ ⊆ F ormL and let ϕ ∈ F ormL . We write Γ ϕ to mean that
whenever (M, s) is a model of Γ, we have that (M, s) ϕ. We pronounce Γ ϕ as Γ semantically implies
ϕ.
Definition 5.1.3. Let L be a language and let Γ ⊆ F ormL . We say that Γ is satisfiable if there exists a
model of Γ.
• Σ is a satisfiable.
There are two standard ways to get theories. One is to take a stucture, and consider all of the sentences
that are true in that structure.
Definition 5.1.5. Let M be an L-structure. We let T h(M) = {σ ∈ SentL : M σ}. We call T h(M) the
theory of M.
Proof. First notice that T h(M) is satisfiable because M is a model of T h(M) (since M σ for all σ ∈
T h(M) by definition. Suppose now that τ ∈ SentL is such that T h(M) τ . Since M is a model of T h(M),
it follows that M τ , and hence τ ∈ T h(M).
Another standard way to get a theory is to take an arbitrary satisfiable set of sentences, and close it off
under semantic implication.
75
76 CHAPTER 5. SEMANTIC AND SYNTACTIC IMPLICATION
Definition 5.1.7. Let L be a language and let Σ ⊆ SentL . We let Cn(Σ) = {τ ∈ SentL : Σ τ }. We call
Cn(Σ) the set of consequences of Σ.
Proposition 5.1.8. Let L be a language and let Σ ⊆ SentL be satisfiable. We then have that Cn(Σ) is an
L-theory.
Proof. We first show that Cn(Σ) is satisfiable. Since Σ is satsfiable, we may fix a model M of Σ. Let
τ ∈ Cn(Σ). We then have that Σ τ , so using the fact that M is a model of Σ we conclude that M τ .
Therefore, M is a model of Cn(Σ), hence Cn(Σ) is satisfiable.
Suppose now that τ ∈ SentL and that Cn(Σ) τ . We need to show that τ ∈ Cn(Σ), i.e. that Σ τ .
Let M be a model of Σ. Since Σ σ for all σ ∈ Cn(Σ), it follows that M σ for all σ ∈ Cn(Σ). Thus, M
is a model of Cn(Σ). Since Cn(Σ) τ , it follows that M τ . Thus, Σ τ , and so τ ∈ Cn(Σ).
Definition 5.1.9. An L-theory Σ is complete if for all τ ∈ SentL , either τ ∈ Σ or ¬τ ∈ Σ.
Proposition 5.1.10. Let L be a language and let M be an L-theory. T h(M) is a complete L-theory.
Proof. We’ve already seen that T h(M) is a theory. Suppose now that σ ∈ SentL . If M σ, we then have
that σ ∈ T h(M). Otherwise, we have M 6 σ, so by definition M ¬σ, and hence ¬σ ∈ T h(M).
Example. Let L = {f, e} where f is a binary function symbol and e is a constant symbol. Consider the
following sentences.
ϕ1 = ∀x∀y∀z(f(f(x, y), z) = f(x, f(x, y)))
ϕ2 = ∀x(f(x, e) = x ∧ f(e, x) = x)
ϕ3 = ∀x∃y(f(x, y) = e ∧ f(y, x) = e)
The theory T = Cn({ϕ1 , ϕ2 , ϕ3 }) is the theory of groups. T is not complete because it neither contains
∀x∀y(f(x, y) = f(y, x)) nor its negation because there are both abelian groups and nonabelian groups.
Definition 5.1.11. Let L = {R} where R is a binary relation symbol. Consider the following sentences
ϕ1 = ∀x¬Rxx
ϕ2 = ∀x∀y∀z((Rxy ∧ Ryz) → Rxz)
ϕ3 = ∀x∀y¬(Rxy ∧ Ryx)
ϕ4 = ∀x∀y(x = y ∨ Rxy ∨ Ryx)
and let LO = Cn({ϕ1 , ϕ2 , ϕ3 , ϕ4 }). LO is called the theory of (strict) linear orderings. LO is not complete
because it neither contains ∃y∀x(x = y ∨ x < y) nor its negation because there are linear ordering with greatest
elements and linear orderings without greatest elements.
Definition 5.1.12. Let L = {R} where R is a binary relation symbol. Consider the following sentences
ϕ1 = ∀x¬Rxx
ϕ2 = ∀x∀y∀z((Rxy ∧ Ryz) → Rxz)
ϕ3 = ∀x∀y¬(Rxy ∧ Ryx)
ϕ4 = ∀x∀y(x = y ∨ Rxy ∨ Ryx)
ϕ5 = ∀x∀y(Rxy → ∃z(Rxz ∧ Rzy))
ϕ6 = ∀x∃yRxy
ϕ7 = ∀x∃yRyx
and let DLO = Cn({ϕ1 , ϕ2 , ϕ3 , ϕ4 , ϕ5 , ϕ6 , ϕ7 }). DLO is called the theory of dense (strict) linear orderings
without endpoints. DLO is complete as we’ll see below.
5.1. SEMANTIC IMPLICATION AND THEORIES 77
Theorem 5.1.13 (Countable Lowenheim-Skolem Theorem). Suppose that L is countable and that Γ ⊆
F ormL is satisfiable. There exists a countable model (M, s) of Γ.
Proof. Since Γ is satisfiable, we may fix a model (N , s) of Γ. Let X = ran(s) ⊆ N and notice that X
is countable. By the Countable Lowenheim-Skolem-Tarski Theorem, there exists a countable elementary
substructure M N such that X ⊆ M . Notice that s is also a variable assigment on M . Now for any
γ ∈ Γ, we have that (N , s) γ because (N , s) is a model of Γ, hence (M, s) γ because M N . It follows
that (M, s) is a model of Γ.
Example 5.1.20. Let L = {f} where f is a unary function symbol, and let T = Cn({∀x(ffx = x)}). We have
I(T, n) = b n2 c + 1 for all n ∈ N+ .
Proof. Let’s first analyze the finite models of T . Suppose that M is a model of T of cardinality n. For every
a ∈ M , we then have f M (f M (a)) = a. There are now two cases. Either f M (a) = a, or f M (a) = b 6= a in
which case f M (b) = a. Let
From above, we then have that |M oveM | is even and that |F ixM | + |M oveM | = n. Now the idea is that
two models M and N of T of cardinality n are isomorphic if and only if they have the same number of fixed
points, because then we can match up the fixed points and then match up the “pairings” left over to get an
isomorphism. Here’s a more formal argument.
We know show that if M and N are models of T of cardinality n, then M ∼ = N if and only if |F ixM | =
|F ixN |. Clearly, if M ∼= N , then |F ixM | = |F ixN |. Suppose conversely that |F ixM | = |F ixN |. We then
must have |M oveM | = |M oveN |. Let XM ⊆ M oveM be a set of cardinality |M ove 2
M|
such that f M (x) 6= y
M
for all x, y ∈ X (that is, we pick out one member from each pairing given by f ), and let XN be such
a set for N . Define a function h : M → N . Fix a bijection from α : F ixM → F ixN and a bijection
β : XM → XN . Define h by letting h(a) = α(a) for all a ∈ F ixM , letting h(x) = β(x) for all x ∈ XM , and
letting h(y) = f N (β(f M (y))) for all y ∈ M oveM \X. We then have that h is an isomophism from M to N .
Now we need only count how many possible values there are for |F ixM |. Let n ∈ N+ . Suppose first that n
is even. Since |M oveM | must be even, it follows that |F ixM | must be even. Thus, |F ixM | ∈ {0, 2, 4, . . . , n},
so there are n2 + 1 many possibilities, and it’s easy to construct models in which each of these possibilities
occurs. Suppose now that n is odd. Since |M oveM | must be even, it follows that |F ixM | must be odd.
Thus, |F ixM | ∈ {1, 3, 5, . . . , n}, so there are n−1
2 + 1 many possibilities, and it’s easy to construct models in
which each of these possibilities occurs. Thus, in either case, we have I(T, n) = b n2 c + 1.
Proof. As mentioned in the LO example, every finite linear ordering has a least element.
Proposition 5.1.23. There exists a finite language L and a σ ∈ SentL such that Spec(σ) = {2n : n ∈ N+ }.
Proof. We’ll give two separate arguments. First, let L = {e, f} be the language of group theory. Let σ be
the conjunction of the group axioms with the sentence ∃x(¬(x = e) ∧ fxx = e) expressing that there is an
element of order 2. Now for every n ∈ N+ , the group Z/(2n)Z is a model of σ of cardinality 2n because n is
an element of order 2. Thus, {2n : n ∈ N+ } ⊆ Spec(σ). Suppose now that k ∈ Spec(σ), and fix a model M
of σ of order k. We then have that M is a group with an element of order 2, so by Lagrange’s Theorem it
follows that 2 | k, so k ∈ {2n : n ∈ N+ }. It follows that Spec(σ) = {2n : n ∈ N+ }.
For a second example, let L = {R} where R is a binary relation symbol. Let σ be the conjunction of the
following sentences:
• ∀xRxx.
• ∀x∀y(Rxy → Ryx).
Proof Rules:
Γ`ϕ∧ψ Γ`ϕ∧ψ Γ`ϕ Γ`ψ
(∧EL) (∧ER) (∧I)
Γ`ϕ Γ`ψ Γ`ϕ∧ψ
Γ`ϕ Γ`ψ
(∨IL) (∨IR)
Γ`ϕ∨ψ Γ`ϕ∨ψ
Γ`ϕ→ψ Γ ∪ {ϕ} ` ψ
(→ E) (→ I)
Γ ∪ {ϕ} ` ψ Γ`ϕ→ψ
Γ ∪ {ϕ} ` θ Γ ∪ {ψ} ` θ Γ ∪ {ψ} ` ϕ Γ ∪ {¬ψ} ` ϕ
(∨P C) (¬P C)
Γ ∪ {ϕ ∨ ψ} ` θ Γ`ϕ
Γ ∪ {¬ϕ} ` ψ Γ ∪ {¬ϕ} ` ¬ψ
(Contr)
Γ`ϕ
Equality Rules:
Γ ` ϕtx Γ ` t = u
if V alidSubsttx (ϕ) = 1 = V alidSubstux (ϕ) (= Sub)
Γ ` ϕux
Existential Rules:
Γ ` ϕtx
if V alidSubsttx (ϕ) = 1 (∃I)
Γ ` ∃xϕ
Γ ∪ {ϕyx } ` ψ
/ F reeV ar(Γ ∪ {∃xϕ, ψ}) and V alidSubstyx (ϕ) = 1 (∃P )
if y ∈
Γ ∪ {∃xϕ} ` ψ
Universal Rules:
Γ ` ∀xϕ
if V alidSubsttx (ϕ) = 1 (∀E)
Γ ` ϕtx
Γ ` ϕyx
/ F reeV ar(Γ ∪ {∀xϕ}) and V alidSubstyx (ϕ) = 1 (∀I)
if y ∈
Γ ` ∀xϕ
Superset Rule:
Γ`ϕ
if Γ0 ⊇ Γ (Super)
Γ0 ` ϕ
Definition 5.2.1. A deduction is a witnessing sequence in (P(F ormL ) × F ormL , AssumeL ∪ EqRef l, H).
Definition 5.2.2. Let Γ ⊆ F ormP and let ϕ ∈ F ormP . We write Γ ` ϕ to mean that
Notation 5.2.3.
1. If Γ = ∅, we write ` ϕ instead of ∅ ` ϕ.
Definition 5.2.4. Γ is inconsistent if there exists θ ∈ F ormP such that Γ ` θ and Γ ` ¬θ. Otherwise, we
say that Γ is consistent.
5.2. SYNTACTIC IMPLICATION 81
{t = u} ` t = t (EqRef l) (1)
{t = u} ` t = u (AssumeL ) (2)
{t = u} ` u = t (= Sub on 1 and 2 with x = t) (3)
{t = u, u = w} ` t = u (AssumeL ) (1)
{t = u, u = w} ` u = w (AssumeL ) (2)
{t = u, u = w} ` t = w (= Sub on 1 and 2 with t = x) (3)
{Rt1 t2 · · · tk , t1 = u1 , t2 = u2 , . . . , tk = uk } ` Ru1 u2 · · · uk
Sk
Proof. Fix R ∈ Rk and t1 , t2 , . . . , tk ∈ T ermL . Fix x ∈ / i=1 (OccurV ar(ti ) ∪ OccurV ar(ui )). Let Γ =
{Rt1 t2 · · · tk , t1 = u1 , t2 = u2 , . . . , tk = uk }. We have
u1 , t2 = u2 , . . . , tk = uk }. We have
Similar to the previous proposition, but start with the line ∅ ` ft1 t2 · · · tk = ft1 t2 · · · tk using the EqRef l
rule.
Proposition 5.2.9. ∃xϕ ` ¬∀x¬ϕ.
Proof. Fix y 6= x with y ∈
/ OccurV ar(ϕ).
Corollary 5.2.13. If Γ ⊆ F ormL is consistent and ϕ ∈ F ormL , then either Γ ∪ {ϕ} is consistent or
Γ ∪ {¬ϕ} is consistent.
Proof. If both Γ ∪ {ϕ} and Γ ∪ {¬ϕ} are inconsistent, then both Γ ` ¬ϕ and Γ ` ϕ by Proposition 5.2.12,
so Γ is inconsistent.
Proposition 5.2.14.
1. If Γ ` ϕ and Γ ∪ {ϕ} ` ψ, then Γ ` ψ.
2. If Γ ` ϕ and Γ ` ϕ → ψ, then Γ ` ψ.
Proof.
1. Since Γ ` ϕ, it follows from the Super rule that Γ ∪ {¬ϕ} ` ϕ. Since we also have Γ ∪ {¬ϕ} ` ¬ϕ by
Assume, we may conclude that Γ ∪ {¬ϕ} is inconsistent. Therefore, by Proposition 5.2.11, we have
that Γ ∪ {¬ϕ} ` ψ. Now we also have Γ ∪ {ϕ} ` ψ by assumption, so the ¬P C rule gives that Γ ` ψ.
2. Since Γ ` ϕ → ψ, we can conclude that Γ ∪ {ϕ} ` ψ by rule → E. The result follows from part 1.
Proposition 5.2.15. Let Gf in = G(Pf in (F ormL ) × F ormL , AssumeL ∪ EqRef l, H), i.e. we insist that the
set Γ is finite but otherwise have exactly the same proof rules. Let Γ `f in ϕ denote that (Γ, ϕ) ∈ Gf in
1. If Γ `f in ϕ, then Γ ` ϕ.
6.1 Soundness
Theorem 6.1.1 (Soundness Theorem).
1. If Γ ` ϕ, then Γ ϕ.
2. Every satisfiable set of formulas is consistent.
Proof.
1. The proof is by induction. We let X = {(Γ, ϕ) ∈ G : Γ ϕ} and we show by induction on G that
X = G. We begin by noting that if ϕ ∈ Γ, then Γ ϕ because if (M, s) is a model of Γ, then (M, s)
is a model of γ simply because ϕ ∈ Γ. Therefore, (Γ, ϕ) ∈ X for all (Γ, ϕ) ∈ AssumeL . Also, for any
Γ ⊆ F ormL and any t ∈ T ermL , we have Γ t = t because for any any model (M, s) of Γ we have
s(t) = s(t), hence (M, s) t = t.
We now handle the inductive steps. All of the old rules go through in a similar manner as before, and
the Super rule is trivial.
• We first handle the = Sub rule. Suppose that Γ ϕtx , that Γ t = u, and that V alidSubsttx (ϕ) =
1 = V alidSubstux (ϕ). We need to show that Γ ϕux . Fix a model (M, s) of Γ. Since Γ ϕtx , we
have that (M, s) ϕtx . Also, since Γ t = u, we htave that (M, s) t = u, and hence s(t) = s(u).
Now using the fact that V alidSubsttx (ϕ) = 1 = V alidSubstux (ϕ) = 1, we have
(M, s) ϕtx ⇒ (M, s[x ⇒ s(t)]) ϕ (by the Substitution Theorem)
⇒ (M, s[x ⇒ s(u)]) ϕ
⇒ (M, s) ϕux (by the Substitution Theorem)
• We now handle the ∃I rule. Suppose that Γ ϕtx where V alidSubstt,x (ϕ) = 1. We need to
show that Γ ∃xϕ. Fix a model (M, s) of Γ. Since Γ ϕtx , it follows that (M, s) ϕtx . Since
V alidSubsttx (ϕ) = 1, we have
(M, s) ϕtx ⇒ (M, s[x ⇒ s(t)]) ϕ (by the Substitution Theorem)
⇒ There exists a ∈ M such that (M, s[x ⇒ a]) ϕ
⇒ (M, s) ∃xϕ
85
86 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
Thus, (M, s[y ⇒ a]) ϕyx in either case. Now since (M, s) γ for all γ ∈ Γ and y ∈
/ F reeV ar(Γ),
we have (M, s[y ⇒ a]) γ for all γ ∈ Γ. Thus, (M, s[y ⇒ a]) ψ because Γ ∪ {ϕyx } ψ. Finally,
since y ∈
/ F reeV ar(ψ), it follows that (M, s) ψ.
• We next do the ∀E rule. Suppose that Γ ∀xϕ and that t ∈ T ermL is such that V alidSubsttx (ϕ) =
1. We need to show that Γ ϕtx . Fix a model (M, s) of Γ. Since Γ ∀xϕ, it follows that that
(M, s) ∀xϕ. Since V alidSubsttx (ϕ) = 1, we have
(M, s[y ⇒ a]) ϕyx ⇒ (M, (s[y ⇒ a])[x ⇒ s[y ⇒ a](y)]) ϕ (by the Substitution Theorem)
⇒ (M, (s[y ⇒ a])[x ⇒ a]) ϕ
⇒ (M, s[x ⇒ a]) ϕ (since y ∈
/ F reeV ar(ϕ) and y 6= x)
Now a ∈ M was arbitrary, so (M, s[x ⇒ a]) ϕ for every a ∈ M , hence (M, s) ∀xϕ.
2. Let Γ be a satisfiable set of formulas. Fix a model (M, s) of Γ. Suppose that Γ is inconsistent, and fix
θ ∈ F ormL such that Γ ` θ and Γ ` ¬θ. We then have Γ θ and Γ ¬θ by part 1, hence (M, s) θ
and (M, s) (¬θ), a contradiction. It follows that Γ is consistent.
6.2. PRIME FORMULAS 87
Corollary 6.2.5. Let L be a language, let Γ ⊆ F ormL , and let ϕ ∈ F ormL . If Γ# P (L) ϕ# (in the
propositional language P (L)), then Γ `L ϕ (in the first-order language L).
88 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
Proof. Suppose that Γ# P (L) ϕ# . By Proposition 6.2.4, it follows that (Γ# )? P (L) (ϕ# )? , hence Γ `L ϕ
by Proposition 6.2.3
Example 6.2.6. Let L be a languague and let ϕ, ψ ∈ F ormL We have ¬(ϕ → ψ) `L ϕ ∧ (¬ψ)
2. (ϕ ∧ (¬ψ))# = ϕ# ∧ ¬(ψ # ).
Suppose that v : P (L) → {0, 1} is a truth assignment such that v(¬(ϕ# → ψ # )) = 1. We then have v(ϕ# →
ψ # ) = 0, hence v(ϕ# ) = 1 and v(ψ # ) = 0. We therefore have v(¬(ψ # )) = 1 and hence v(ϕ# ∧ ¬(ψ # )) = 1.
It follows that (¬(ϕ → ψ))# P (L) (ϕ ∧ (¬ψ))# .
Corollary 6.2.7. Let L be a language, let Γ ⊆ F ormL , and let ϕ, ψ ∈ F ormL . If Γ `L ϕ and ϕ# P (L) ψ # ,
then Γ `L ψ.
Proof. Since ϕ# P (L) ψ # , we have that ϕ `L ψ by Corollary 6.2.5. It follows from the Super rule that
Γ ∪ {ϕ} `L ψ. Using Proposition 5.2.14 (since Γ `L ϕ and Γ ∪ {ϕ} `L ψ), we may conclude that Γ `L ψ.
6.3 Completeness
6.3.1 Motivating the Proof
We first give an overview of the key ideas in our proof of completeness. Let L be a language, and suppose
that Γ ⊆ L is consistent.
Definition 6.3.1. Suppose that L is a language and that ∆ ⊆ F ormL . We say that ∆ is complete if for all
ϕ ∈ F ormL , either ϕ ∈ ∆ or ¬ϕ ∈ ∆.
As we saw in propositional logic, it will aid use greatly to extend Γ to a set ∆ ⊇ Γ which is both consistent
and complete, so let’s assume that we can do that (we will prove it exactly the same way below). We need
to construct an L-structure M and a variable assignment s : V ar → M such that (M, s) δ for all δ ∈ ∆.
Now all that we have is the syntactic information that ∆ provides, so it seems that the only way to proceed
is to define our M from these syntactic objects. Since terms intuitively name elements, it is natural to try
to define the universe M to simply be T ermL . We would then define the structure as follows
1. cM = c for all c ∈ C.
and let s : V ar → M be the variable assignment defined by s(x) = x for all x ∈ V ar.
However, there are two problems with this approach, one of which is minor and the other is quite serious.
First, let’s think about the minor problem. Suppose that L = {f, e} where f is a binary function symbol
and e is a constant symbol, and that Γ is the set of group axioms. Suppose that ∆ ⊇ Γ is consistent and
complete. We then have fee = e ∈ ∆ because Γ ` fee = e. However, the two terms fee and e are syntactically
different objects, so if we were to let M be T ermL this would cause a problem because fee and e are distinct
despite the fact that ∆ says they must be equal. Of course, when you have distinct objects which you want
to consider equivalent, you should define an equivalence relation. Thus, we should define ∼ on T ermL by
letting t ∼ u if t = u ∈ ∆. We would then need to check that ∼ is an equivalence relation and that the
6.3. COMPLETENESS 89
definition of the structure above is independent of our choice of representatives for the classes. This is all
fairly straightfoward, and will be carried out below.
On to the more serious obstactle. Suppose that L = {P} where P is a unary relation symbol. Let
Γ = {¬Px : x ∈ V ar} ∪ {¬(x = y) : x, y ∈ V ar with x 6= y} ∪ {∃xPx} and notice that Γ is consistent because
it is satisfiable. Suppose that ∆ ⊇ Γ is consistent and complete. In the model M constructed, we have
M = T ermL = V ar (notice that the equivalence relation defined above will be trivial in this case). Thus,
since (M, s) ¬Px for all x ∈ V ar, it follows that (M, s) 6 ∃xPx. Hence, M is not a model of ∆.
The problem in the above example is that there was an existential statement in ∆, but whenever you
plugged a term in for the quantied variable, the resulting formula was not in ∆. Since we are building our
model from the terms, this is a serious problem. However, if ∆ had the following, then this problem would
not arise.
Definition 6.3.2. Let L be a language and let Γ ⊆ F ormL . We say that Γ contains witnesses if for all
ϕ ∈ F ormL and all x ∈ V ar, there exists c ∈ C such that (∃xϕ) → ϕcx ∈ Γ.
Our goal then is to show that if Γ is consistent, then there exists a ∆ ⊇ Γ which is consistent, complete,
and contains witnesses. On the face of it, this is not true, as the above example shows (because there are
no constant symbols). However, if we allow ourselves to expand our language with new constant symbols,
we can repeatedly add witnessing statements by using these fresh constant symbols as our witnesses.
Lemma 6.3.3. Let ϕ ∈ F ormL , let t ∈ T ermL , let c ∈ C, and let x, z ∈ V ar. Suppose that z ∈
/ OccurV ar(ϕ).
tz
• (ϕtx )zc equals (ϕzc )xc .
tz
• If V alidSubsttx (ϕ) = 1, then V alidSubstxc (ϕzc ) = 1.
Lemma 6.3.4. Let L be a language, and let L0 be L together with a new constant symbol c. Suppose that
Γ0 `L0 ϕ0
Γ1 `L0 ϕ1
Γ2 `L0 ϕ2
..
.
Γn `L0 ϕn
Sn
is an L0 -deduction. For any z ∈ V ar with z ∈
/ OccurV ar( i=0 (Γi ∪ {ϕi })), we have that
is an L-deduction.
90 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
is an L-deduction.
If ϕ ∈ Γ, then ϕzc ∈ Γzc .
Suppose that line i is Γ ` t = t where t ∈ T ermL0 . Since (t = t)zc equals tzc = tzc , we can place Γzc ` tzc = tzc
on line i by the EqRef l rule.
Suppose that Γ `L0 ϕ∧ψ was a previous line and we inferred Γ `L0 ϕ. Inductively, we have Γzc `L (ϕ ∧ ψ)zc
on the corresponding line. Since (ϕ ∧ ψ)zc = ϕzc ∧ ψcz , we may use the ∧EL rule to put Γzc `L ϕzc on the
corresponding line. The other propositional rules are similarly uninteresting.
Suppose that Γ `L0 ϕtx and Γ `L0 t = u were previous lines, that V alidSubsttx (ϕ) = 1 = V alidSubstux (ϕ),
and we inferred Γ `L0 ϕux . Inductively, we have Γzc `L (ϕtx )zc and Γzc `L (t = u)zc on the corresponding lines.
tz tz
Now (ϕtx )zc equals (ϕzc )xc by the previous lemma, and (t = u)zc equals tzc = uzc . Thus, we have Γzc `L (ϕzc )xc
and Γzc `L tzc = uzc on the corresponding lines. Using the fact that V alidSubsttx (ϕ) = 1 = V alidSubstux (ϕ),
tz uz
we can use the previous lemma to conclude that that V alidSubstxc (ϕzc ) = 1 = V alidSubstx c (ϕzc ). Hence, we
z
u uz
may use that = Sub rule to put Γzc `L (ϕzc )x c on the corresponding line. We now need only note that (ϕzc )x c
equals (ϕux )zc by the previous lemma.
Suppose that Γ `L0 ϕtx where V alidSubsttx (ϕ) = 1 was a previous line and we inferred Γ `L0 ∃xϕ.
tz tz
Inductively, we have Γzc `L (ϕtx )zc on the corresponding line. Now (ϕtx )zc equals (ϕzc )xc and V alidSubstxc (ϕzc ) = 1
by the previous lemma. Hence, we may use the ∃I rule to put Γzc `L ∃x(ϕzc ) on the corresponding line. We
now need only note that ∃x(ϕzc ) equals (∃xϕ)zc .
The other rules are similarly awful.
Corollary 6.3.5 (Generalization on Constants). Let L be a language, and let L0 be L together with a new
constant symbol c. Suppose that Γ ⊆ F ormL and ϕ ∈ F ormL . If Γ `L0 ϕcx , then Γ `L ∀xϕ.
Γ0 `L0 ϕ0
Γ1 `L0 ϕ1
Γ2 `L0 ϕ2
..
.
Γn `L0 ϕn
n
[
y∈
/ OccurV ar( (Γi ∪ {ϕi }))
i=0
6.3. COMPLETENESS 91
is an L-deduction. Since Γn ⊆ Γ ⊆ F ormL , we have (Γn )yc = Γn . Now (ϕn )yc = (ϕcx )yc = ϕyx . We therefore
have Γn `L ϕyx . We may then use the ∀I rule to conclude that Γn `L ∀xϕ. Finally, Γ `L ∀xϕ by the Super
rule.
2. Let L0 be L together with finitely many new constant symbols. If Γ `L0 ϕ, then Γ `L ϕ.
3. Let L0 be L together with (perhaps infinitely many) new constant symbols. If Γ `L0 ϕ, then Γ `L ϕ.
Proof.
Γ0 `L0 ϕ0
Γ1 `L0 ϕ1
Γ2 `L0 ϕ2
..
.
Γn `L0 ϕn
is an L-deduction. Since Γn ⊆ Γ ⊆ F ormL and ϕ ∈ F ormL , it follows that (Γn )yc = Γn and (ϕn )yc = ϕ.
Thus, Γn `L ϕ and so Γ `L ϕ by the Super rule.
2. This is proved by induction on the number of new constant symbols, using part 1 for the base case
and the inductive step.
92 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
Γ0 `L0 ϕ0
Γ1 `L0 ϕ1
Γ2 `L0 ϕ2
..
.
Γn `L0 ϕn
Γ0 `L0 ϕ0
Γ1 `L0 ϕ1
Γ2 `L0 ϕ2
..
.
Γn `L0 ϕn
is an L0 -deduction, so Γn `L0 ϕ. Using the Super rule, we conclude that Γ `L0 ϕ. Therefore, Γ `L ϕ
by part 2.
Corollary 6.3.7. Let L be a language and let L0 be L together with (perhaps infinitely many) new constant
symbols. Let Γ ⊆ F ormL . Γ is L-consistent if and only if Γ is L0 -consistent.
Proof. Since any L-deduction is also a L0 -deduction, if Γ is L-inconsistent then it is L0 -inconsistent . Suppose
that Γ is L0 -inconsistent. We then have that Γ `L0 ϕ for all ϕ ∈ F ormL by Proposition 5.2.11, hence Γ `L ϕ
for all ϕ ∈ F ormL by Corollary 6.3.6. Therefore, Γ is L-inconsistent.
Lemma 6.3.8. Let L be a language, and let L0 be L together with a new constant symbol c. Suppose that
Γ ⊆ F ormL is L-consistent and that ϕ ∈ F ormL . We then have that Γ ∪ {(∃xϕ) → ϕcx } is L0 -consistent.
Proof. Suppose that Γ ∪ {(∃xϕ) → ϕcx } is L0 -inconsistent. We then have that Γ `L0 ¬((∃xϕ) → ϕcx ), hence
# #
Γ `L0 (∃xϕ) ∧ ¬(ϕcx ) by Corollary 6.2.7 (because (¬((∃xϕ) → ϕcx )) P (L0 ) ((∃xϕ) ∧ ¬(ϕcx )) ). Thus, Γ `L0
∃xϕ by the ∧EL rule, so Γ `L0 ¬∀x¬ϕ (by Proposition 5.2.9 and Proposition 5.2.14), and hence Γ `L ¬∀x¬ϕ
by Corollary 6.3.6. We also have Γ `L0 (¬ϕ)cx by the ∧ER rule, so Γ `L ∀x¬ϕ by Generalization on
Constants. This contradicts the fact that Γ is L-consistent.
Lemma 6.3.9. Let L be a language and let Γ ⊆ F ormL be L-consistent. There exists a language L0 ⊇ L
and Γ0 ⊆ F ormL0 such that
1. Γ ⊆ Γ0 .
2. Γ0 is L0 -consistent.
3. For all ϕ ∈ F ormL and all x ∈ V ar, there exists c ∈ C such that (∃xϕ) → ϕcx ∈ Γ0 .
Proof. For each ϕ ∈ F ormL and each x ∈ V ar, let cϕ,x be a new constant symbol (distinct from all symbols
in L). Let L0 = L ∪ {cϕ,x : ϕ ∈ F ormL and x ∈ V ar}. Let
c
Γ0 = Γ ∪ {(∃xϕ) → ϕxϕ,x : ϕ ∈ F ormL and x ∈ V ar}}
6.3. COMPLETENESS 93
Conditions 1 and 3 are clear, so we need only check that Γ0 is L0 -consistent. By Corollary 5.2.16, it suffices
to check that all finite subsets of Γ0 are L0 -consistent, and for this it suffices to show that
cϕ ,x cϕ ,x c
Γ ∪ {(∃x1 ϕ1 ) → (ϕ1 )x1 1 1 , (∃x2 ϕ2 ) → (ϕ2 )x2 2 2 , . . . , (∃xn ϕn ) → (ϕn )xϕn n ,xn }
is L0 -consistent whenever ϕ1 , ϕ2 , . . . , ϕn ∈ F ormL and x1 , x2 , . . . , xn ∈ V ar. Formally, one can prove this by
induction on n. A slightly informal argument is as as follows. Fix ϕ1 , ϕ2 , . . . , ϕn ∈ F ormL and x1 , x2 , . . . , xn ∈
V ar. We have
• Γ is L-consistent, so
cϕ ,x
• Γ ∪ {(∃x1 ϕ1 ) → (ϕ1 )x1 1 1 } is (L ∪ {cϕ1 ,x1 })-consistent by Lemma 6.3.8, so
cϕ ,x cϕ ,x
• Γ ∪ {(∃x1 ϕ1 ) → (ϕ1 )x1 1 1 , (∃x2 ϕ2 ) → (ϕ2 )x2 2 2 } is (L ∪ {cϕ1 ,x1 , cϕ2 ,x2 })-consistent by Lemma 6.3.8, so
• ...
cϕ ,x cϕ ,x c
• Γ ∪ {(∃x1 ϕ1 ) → (ϕ1 )x1 1 1 , (∃x2 ϕ2 ) → (ϕ2 )x2 2 2 , . . . , (∃xn ϕn ) → (ϕn )xϕn n ,xn } is
(L ∪ {cϕ1 ,x1 , cϕ2 ,x2 , . . . , cϕn ,xn })-consistent
Therefore,
cϕ ,x cϕ ,x c
Γ ∪ {(∃x1 ϕ1 ) → (ϕ1 )x1 1 1 , (∃x2 ϕ2 ) → (ϕ2 )x2 2 2 , . . . , (∃xn ϕn ) → (ϕn )xϕn n ,xn }
is L0 -consistent by Corollary 6.3.7.
Proposition 6.3.10. Let L be a language and let Γ ⊆ F ormL be consistent. There exists a language L0 ⊇ L
and Γ0 ⊆ F ormL0 such that
1. Γ ⊆ Γ0 .
2. Γ0 is L0 -consistent.
3. Γ0 contains witnesses.
Proof. Let L0S= L and Γ0 = Γ. ForSeach n ∈ N, use the previous lemma to get Ln+1 and Γn+1 from Ln and
Γn . Set L0 = n∈N L and set Γ0 = n∈N Γn .
Proposition 6.3.11. (Suppose that L is countable.) If Γ is consistent, then there exists a set ∆ ⊇ Γ which
is consistent and complete.
Proof. Exactly the same proof as the propositional logic case, using Zorn’s Lemma in the uncountable
case.
Proposition 6.3.12. Let L be a language. If Γ ⊆ L is consistent, then there a language L0 ⊇ L (which is
L together with new constant symbols) and ∆ ⊆ F ormL0 such that
• Γ ⊆ ∆.
• ∆ is consistent.
• ∆ is complete.
• ∆ contains witnesses.
Proof.
Lemma 6.3.13. Suppose that ∆ is consistent and complete. If ∆ ` ϕ, then ϕ ∈ ∆.
94 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
5. Suppose first that ∃xϕ ∈ ∆. Since ∆ contains witnesses, we may fix c ∈ C such that (∃xϕ) → ϕcx ∈ ∆.
We therefore have ∆ ` ∃xϕ and ∆ ` (∃xϕ) → ϕcx , hence ∆ ` ϕcx by Proposition 5.2.14. Using Lemma
6.3.13, we conclude that ϕcx ∈ ∆.
Conversely, suppose that there exists c ∈ C such that ϕcx ∈ ∆. We then have ∆ ` ϕcx , hence ∆ ` ∃xϕ
using the ∃I rule (notice that V alidSubstcx (ϕ) = 1). Using Lemma 6.3.13, we conclude that ∃xϕ ∈ ∆.
6. Suppose first that ∀xϕ ∈ ∆. We then have ∆ ` ∀xϕ, hence ∆ ` ϕcx for all c ∈ C using the ∀E rule
(notice that V alidSubstcx (ϕ) = 1 for all c ∈ C). Using Lemma 6.3.13, we conclude that ϕcx ∈ ∆ for all
c ∈ C.
Conversely, suppose that ϕcx ∈ ∆ for all c ∈ C. Since ∆ is consistent, this implies that there does not
exist c ∈ C with ¬(ϕcx ) = (¬ϕ)cx ∈ ∆. Therefore, ∃x¬ϕ ∈ / ∆ by part 5, so ¬∃x¬ϕ ∈ ∆ by part 1. It
follows from Proposition 5.2.10 that ∆ ` ∀xϕ. Using Lemma 6.3.13, we conclude that ∀xϕ ∈ ∆.
Notice that our definitions of RM do not depend on our choice of representatives for the equivalence classes
by Proposition 5.2.7. Similarly, our definitions of f M do not depend on our choice of representatives for the
equivalences classes by Proposition 5.2.8. Finally, define s : V ar → M by letting s(x) = [x] for all x ∈ V ar.
We first show that s(t) = [t] for all t ∈ T ermL by induction. We have s(c) = cM = [c] for all c ∈ C and
s(x) = s(x) = [x] for all x ∈ V ar. Suppose that f ∈ Fk and t1 , t2 , . . . , tk ∈ T ermL are such that s(ti ) = [ti ]
for all i. We then have
2. If Γ ϕ, then Γ ` ϕ.
Proof.
1. Suppose that Γ is consistent. By Proposition 6.3.12, we may fix a language L0 ⊇ L and ∆ ⊆ F ormL0
such that ∆ ⊇ Γ is consistent, complete, and contains witnesses. Now ∆ is satisfiable by Proposition
6.3.16, so we may fix an L0 -structure M0 together with s : V ar → M 0 such that (M0 , s) ϕ for all
ϕ ∈ ∆. We then have (M0 , s) γ for all γ ∈ Γ. Letting M be the restiction of M0 to L, we then have
(M, s) γ for all γ ∈ Γ. Therefore, Γ is satisfiable.
2. Suppose that Γ ϕ. We then have that Γ ∪ {¬ϕ} is unsatisfiable, hence Γ ∪ {¬ϕ} is inconsistent by
part 1. It follows from Proposition 5.2.12 that Γ ` ϕ.
We now give another proof of the Countable Lowenheim-Skolem Theorem which does not go through the
concept of elementary substructures.
Corollary 6.3.18 (Countable Lowenheim-Skolem Theorem). Suppose that L is countable and Γ ⊆ F ormL
is consistent. There exists a countable model of Γ.
Proof. Notice that if L is consistent, then the L0 formed in Lemma 6.3.9 is countable because F ormL × V ar
is countable. Thus, each Ln in the proof of Proposition 6.3.10 is countable, so the L0 formed in Proposition
6.3.10 is countable. It follows that T ermL0 is countable, and since the L0 -structure M we construct in the
proof of Proposition 6.3.16 is formed by taking the quotient from an equivalence relation on the countable
T ermL0 , we can conclude that M is countable. Therefore, the L-structure which is the restriction of M to
L from the proof of the Completeness Theorem is countable.
6.4 Compactness
Corollary 6.4.1 (Compactness Theorem).
Proof.
1. Suppose that Γ ϕ. By the Completeness Theorem, we have Γ ` ϕ. Using Proposition 5.2.15, we may
fix a finite Γ0 ⊆ Γ such that Γ0 ` ϕ. By the Soundness Theorem, we have Γ0 ϕ.
2. If every finite subset of Γ is satisfiable, then every finite subset of Γ is consistent by the Soundness
Theorem, hence Γ is consistent by Corollary 5.2.16, and so Γ is satisfiable by the Soundness Theorem.
98 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
Proposition 6.5.1. Let L be a language. Suppose that Γ ⊆ F ormL is such that for all n ∈ N, there exists
a model (M, s) of Γ such that |M | > n. We then have that there exists a model (M, s) of Γ such that M is
infinite.
Proof. Let L0 = L ∪ {ck : k ∈ N} where the ck are new distinct constant symbols. Let
Γ0 = Γ ∪ {ck 6= c` : k, ` ∈ N and k 6= `}
We claim that every finite subset of Γ0 is satisfiable. Fix a finite Γ00 ⊆ Γ0 . Fix N ∈ N such that
By assumption, we may fix a model (M, s) of Γ such that |M | > N . Let M0 be the L0 structure M together
with interpreting the constants c0 , c1 , . . . , cN as distinct elements of M and interpreting each ci for i > N
arbitrarily. We then have (M0 , s) is a model of Γ0 . Hence, every finite subset of Γ0 is satisfiable.
By the Compactness Theorem we may conclude that Γ0 is satisfiable. Fix a model (M0 , s) of Γ0 . If we
let M be the restriction of M0 to L, then (M, s) is a model of Γ which is infinite.
Corollary 6.5.2. The class of all finite groups is not a weak elementary class in the language L = {F, e}.
Proof. If Σ ⊆ SentL is such that M od(Σ) includes all finite groups, then we may use the trivial fact that there
are arbitrarily large finite groups and Proposition 6.5.1 to conclude that it contains an infinite structure.
Proposition 6.5.3. Let L be a language. Suppose that Γ ⊆ F ormL is such there exists a model (M, s) of
Γ with M infinite. We then have that there exists a model (M, s) of Γ such that M is uncountable.
Proof. Let L0 = L ∪ {cr : r ∈ R} where the cr are new distinct constant symbols. Let
Γ0 = Γ ∪ {cr 6= ct : r, t ∈ R and r 6= t}
We claim that every finite subset of Γ0 is satisfiable. Fix a finite Γ00 ⊆ Γ0 . Fix a finite Z ⊆ R such that
Γ00 ⊆ Γ ∪ {cr 6= ct : r, t ∈ Z}
By assumption, we may fix a model (M, s) of Γ such that M is infinite. Let M0 be the L0 structure M
together with interpreting the constants cr for r ∈ Z as distinct elements of M and interpreting each ct for
t∈/ Z arbitrarily. We then have (M0 , s) is a model of Γ0 . Hence, every finite subset of Γ0 is satisfiable.
By the Compactness Theorem we may conclude that Γ0 is satisfiable. Fix a model (M0 , s) of Γ0 . If we
let M be the restriction of M0 to L, then (M, s) is a model of Γ which is uncountable.
Proposition 6.5.4. The class K of all torsion groups is not a weak elementary class in the language
L = {f, e}.
Proof. Suppose that Σ ⊆ SentL is such that K ⊆ M od(Σ). Let L0 = L ∪ {c} where c is new constant symbol.
For each n ∈ N+ , let τn ∈ SentL0 be cn 6= e (more formally, fcfc · · · fcc where there are n − 1 f’s). Let
Σ0 = Σ ∪ {τn : n ∈ N}
6.5. APPLICATIONS OF COMPACTNESS 99
We claim that every finite subset of Σ0 has a model. Suppose that Σ0 ⊆ Σ0 is finite. Fix N ∈ N such that
Σ0 ⊆ Σ ∪ {τn : n < N }
0
Notice that if we let M0 be the group Z/N Z and let cM = 1, then M0 is a model of Σ0 . Thus, every finite
subset of Σ0 has a model, so Σ0 has a model by Compactness. If we restrict this model to L, we get an
element of M od(Σ) which is not int K because it has an element of infinite order.
Proposition 6.5.5. The class K of all equivalence relations in which all equivalence classes are finite is not
a weak elementary class in the language L = {R}.
Proof. Suppose that Σ ⊆ SentL is such that K ⊆ M od(Σ). Let L0 = L ∪ {c} where c is new constant symbol.
For each n ∈ N+ , let τn ∈ SentL0 be
^ n
^
∃x1 ∃x2 · · · ∃xn ( (xi 6= xj ) ∧ Rcxi )
1≤i<j≤n i=1
and let
Σ0 = Σ ∪ {τn : n ∈ N}
We claim that every finite subset of Σ0 has a model. Suppose that Σ0 ⊆ Σ0 is finite. Fix N ∈ N such that
Σ0 ⊆ Σ ∪ {τn : n ≤ N }
0 0
Notice that if we let M 0 = {0, 1, 2, . . . , N }, RM = (M 0 )2 , and cM = 0, then M0 is a model of Σ0 . Thus,
every finite subset of Σ0 has a model, so Σ0 has a model by Compactness. If we restrict this model to L, we
get an element of M od(Σ) which is not int K because it has an infinite equivalence class.
Proposition 6.5.6. Suppose that K is an elementary class, that Σ ⊆ SentL , and that K = M od(Σ). There
exists a finite Σ0 ⊆ Σ such that K = M od(Σ0 ).
Proof. Since K is an elementary class, we may fix τ ∈ SentL with K = M od(τ ). We then have Σ τ , so by
the Compactness Theorem we may fix a finite Σ0 ⊆ Σ such that Σ0 τ . Notice that K = M od(Σ0 ).
Corollary 6.5.7. The class K of all fields of characteristic 0 is a weak elementary class, but not an ele-
mentary class, in the language L = {0, 1, +, ·}.
Proof. We already know that K is a weak elementary class because if we let σ be the conjunction of the
fields axioms and let τn be 1 + 1 + · · · + 1 6= 0 (where there are n 1’s) for each n ∈ N+ , then K = M od(Σ)
where
Σ = {σ} ∪ {τn : n ∈ N+ }
Suppose that K is an elementary class. By the previous proposition, we may fix a finite Σ0 ⊆ Σ such that
K = M od(Σ0 ). Fix N ∈ N such that
Σ0 ⊆ {σ} ∪ {τn : n ≤ N }
Now if fix a prime p > N we see that (Fp , 0, 1, +, ·) (the field with p elements) is a model of Σ0 which is not
an element of K. This is a contradiction, so K is not an elementary class.
100 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
Proposition 6.6.5. For all r, s ∈ N with max{r, s} > 0, we have lim P rn (σr,s ) = 1.
n→∞
Proof. Fix r, s ∈ N. Suppose that n ∈ N with n > r, s. Fix distinct a1 , a2 , . . . , ar , b1 , b2 , . . . , bs ∈ {1, 2, . . . , n}.
For each c distinct from the ai and bj , let
Ac = {M ∈ Gn : c is linked to each ai and to no bj }
1 1
For each such c, we have P rn (Ac ) = 2r+s , so P rn (Ac ) = 1 − 2r+s and hence the probability that no c works
is
1
(1 − )n−r−s
2r+s
Therefore,
n n−r 1
P rn (¬σr,s ) ≤ (1 − r+s )n−r−s
r s 2
1
≤ nr+s (1 − r+s )n−r−s
2
1 −r−s r+s 1
= (1 − r+s ) · n (1 − r+s )n
2 2
1 2r+s − 1
= (1 − r+s )−r−s · nr+s ( r+s )n
2 2
1 −r−s nr+s
= (1 − r+s ) · 2r+s
2 ( 2r+s −1 )n
6.6. AN EXAMPLE: THE RANDOM GRAPH 101
Proposition 6.6.6. Let Σ = {∀x¬Rxx, ∀x∀y(Rxy → Ryx)} ∪ {σr,s : r, s ∈ N+ and max{r, s} > 0} and let
RG = Cn(Σ).
Proposition 6.6.7. RG is satisfiable.
Proof. We build a countable model M of RG with M = N. Notice first that since Pf in (N) (the set of all
finite subsets of N) is countable, so is the set Pf in (N)2 , Hence the set
{(A, B) ∈ Pf in (N)2 : A ∩ B = ∅ and A ∪ B 6= ∅}
is countable. Therefore, we may list it as
(A1 , B1 ), (A2 , B2 ), (A3 , B3 ), . . .
and furthermore we may assume that max(An ∪ Bn ) < n for all n ∈ N. Let M be the L-structure where
M = N and RM = {(k, n) : k ∈ An } ∪ {(n, k) : k ∈ An }. Suppose now that A, B ⊆ N are finite with
A ∩ B = ∅ and A ∪ B 6= ∅. Fix n ∈ N with A = An . We then have that (k, n) ∈ RM for all k ∈ A and
/ RM for all ` ∈ B. Fix n ∈ N with A = An and B = Bn . We then have that (k, n) ∈ RM for all
(`, n) ∈
k ∈ A (because k ∈ An ) and (`, n) ∈/ RM for all ` ∈ B (because ` ∈
/ An and n ∈
/ A` since ` < n). Therefore,
M σr,s for all r, s ∈ N with max r, s > 0. Thus, M is a model of RG.
Theorem 6.6.8. All models of RG are infinite, and any two countable models of RG are isomorphic.
Proof. Suppose that M is model of RG which is finite. Let n = |M |. Since M σn,0 , there exists b ∈ M
such that (b, a) ∈ RM for all a ∈ M . However, this is a contradiction because (a, a) ∈ / RM for all a ∈ M . It
follows that all models of RG are infinite.
Suppose now that M and N are two countable models of RG. From above, we know that M and N are
both countably infinite. List M as m0 , m1 , m2 , . . . and list N as n0 , n1 , n2 , . . . . We build an isomorphism
via a back-and-forth construction as in the proof of the corresponding result for DLO. That is, we define
σk ∈ Pf in (M × N ) for k ∈ N recursively such that
1. σk ⊆ σk+1 .
2. If (m, n) ∈ σk and (m0 , n) ∈ σk , then m = m0 .
3. If (m, n) ∈ σk and (m, n0 ) ∈ σk , then n = n0 .
4. mi ∈ dom(σ2i ).
5. nj ∈ ran(σ2j+1 ).
6. If (m, n) ∈ σ and (m0 , n0 ) ∈ σ, then (m, m0 ) ∈ RM if and only if (n, n0 ) ∈ RN
Suppose
S that we are successful. Define h : M → N be letting h(m) be the unique n such that (m, n) ∈
k∈N σk , and notice that h is isomorphism.
We now define the σk . Let σ0 = (m0 , n0 ). Suppose that k ∈ N and we’ve defined σk . Suppose first
that k is odd, say k = 2i + 1. If mi ∈ dom(σk ), let σk+1 = σk . Suppose then that mi ∈ / dom(σk ). Let
A = {m ∈ dom(σk ) : (m, mi ) ∈ RM } and let B = {m ∈ dom(σk ) : (m, mi ) ∈ / RM }. Since N is a model of RG
and A ∩ B = ∅, we may fix n ∈ N \ran(σk ) such that (σk (m), n) ∈ RM for all m ∈ A and (σk (m), n) ∈ / RM
for all m ∈ B. Let σk+1 = σk ∪ {(mi , n)}.
Suppose now that k is even, say k = 2j. If nj ∈ ran(σk ), let σk+1 = σk . Suppose then that nj ∈/ ran(σk ).
Let A = {n ∈ ran(σk ) : (n, nj ) ∈ RN } and let B = {n ∈ ran(σk ) : (n, nj ) ∈
/ RN }. Since M is a model of RG
and A∩B = ∅, we may fix m ∈ M \dom(σk ) such that (σk−1 (n), m) ∈ RM for all n ∈ A and (σk−1 (n), m) ∈ / RM
for all n ∈ B. Let σk+1 = σk ∪ {(m, nj )}.
102 CHAPTER 6. SOUNDNESS, COMPLETENESS, AND COMPACTNESS
2. If τ ∈
/ RG, then lim P rn (τ ) = 0.
n→∞
Proof.
1. Suppose that τ ∈ RG. We then have Σ τ , so by Compactness we may fix N ∈ N such that
2. Suppose that τ ∈
/ RG. Since RG is complete, it follows that ¬τ ∈ RG. Thus, lim P rn (¬τ ) = 1 by
n→∞
part 1, and hence lim P rn (τ ) = 0.
n→∞
Chapter 7
Quantifier Elimination
The above examples focused on one structure rather than a theory (which could have many models).
The next example uses a theory.
Example. Let L = {0, 1, +, ·} and let T be the theory of fields, i.e. T = Cn(Σ) where Σ is the set of field
axioms. Let ϕ(a, b, c, d) (where a, b, c, d ∈ V ar) be the formula
∃w∃x∃y∃z(wa + xc = 1 ∧ wb + xd = 0 ∧ ya + zc = 0 ∧ yb + zd = 1)
Using determinants, we have
T ϕ ↔ ad 6= bc
103
104 CHAPTER 7. QUANTIFIER ELIMINATION
Definition 7.1.1. Let T be a theory. We say that T has quantifier elimination, or has QE, if for every
k ≥ 1 and every ϕ(x1 , x2 , . . . , xk ) ∈ F ormL , there exists a quantifier-free ψ(x1 , x2 , . . . , xk ) such that
T ϕ↔ψ
M1 σ ⇔ (M1 , h1 (n)) ϕ
⇔ (M1 , h1 (n)) ψ
⇔ (A1 , h1 (n)) ψ (since ψ is quantifier-free)
⇔ (N , n) ψ (since h1 is an isomorphism from N to A1 )
⇔ (A2 , h2 (n)) ψ (since h2 is an isomorphism from N to A2 )
⇔ (M2 , h2 (n)) ψ (since ψ is quantifier-free)
⇔ (M2 , h2 (n)) ϕ
⇔ M2 σ
Proposition 7.2.2. Let T be a theory that has QE. Suppose that A and M are models of T and that
A ⊆ M. We then have that A M.
Proof. Let ϕ ∈ F ormL and let s : V ar → A be a variable assignment. Suppose first that ϕ ∈
/ SentL . Since
T has QE, we may fix a quantifier-free ψ(x) ∈ F ormL such that T ϕ ↔ ψ. We then have
(M, s) ϕ ⇔ (M, s) ψ
⇔ (A, s) ψ (since ψ is quantifier-free)
⇔ (A, s) ϕ
We now list a bunch of simple rules for manipulating formulas while maintaing.
and also that if ϕ1 are ϕ2 s.e., and ψ1 and ψ2 are s.e., then
Definition 7.3.2. A quantifier-free formula ϕ is in disjunctive normal form if there exists ψi for 1 ≤ i ≤ n
such that
ϕ = ψ1 ∨ ψ2 ∨ · · · ∨ ψn
where for each i, there exists αi,j which is either an atomic formula or the negation of an atomic formula
for 1 ≤ j ≤ mi such that
ψi = αi,1 ∧ αi,2 ∧ · · · ∧ αi,mi
Proposition 7.3.3. Suppose that ϕ(x1 , x2 , . . . , xk ) ∈ F ormL is quantifier-free. There exists a quantifier-free
formula θ(x1 , x2 , . . . , xk ) in disjunctive normal form such that ϕ and θ are s.e.
Proof.
106 CHAPTER 7. QUANTIFIER ELIMINATION
Proposition 7.3.5. For every ϕ ∈ F ormL , there exists a prenex formula ψ such that ϕ and ψ are seman-
tically equivalent.
1. T has QE.
Proof.
We need to show that there exists a quantifier-free ψ(x1 , x2 , . . . , xk ) ∈ F ormL such that
m
^ n
^
T ∃y( αi ∧ ¬βj ) ↔ ψ
i=1 j=1
Now each αi and βj is s.e. with, and hence we may assume is, one of the following:
1. x` = y
2. y = y
7.4. EXAMPLES OF THEORIES WITH QE 107
If some αi is x` = y, then
m
^ n
^ m
^ n
^
T ∃y( αi ∧ ¬βj ) ↔ ( αi ∧ ¬βj )xy`
i=1 j=1 i=1 j=1
If some βj is y = y, then
m
^ n
^
T ∃y( αi ∧ ¬βj ) ↔ ¬(x1 = x1 )
i=1 j=1
We need to show that there exists a quantifier-free ψ(x1 , x2 , . . . , xk ) ∈ F ormL such that
m
^ n
^
RG ∃y( αi ∧ ¬βj ) ↔ ψ
i=1 j=1
Now each αi and βj is RG-equivalent with, and hence we may assume is, one of the following:
1. x` = y
2. Rx` y
3. y = y
4. Ryy
If some αi is x` = y, then
m
^ n
^ m
^ n
^
RG ∃y( αi ∧ ¬βj ) ↔ ( αi ∧ ¬βj )xy`
i=1 j=1 i=1 j=1
and let
B = {` ∈ {1, 2, . . . , k} : there exists j such that βj is Rx` y}
We then have that
m
^ n
^ ^ ^
RG ∃y( αi ∧ ¬βj ) ↔ ¬(xa = xb )
i=1 j=1 a∈A b∈B
because in models of RG, given disjoint finite sets A and B of vertices, there are infinitely many vertices
linked to everything in A and not linked to everything in B. Therefore, RG has QE.
Notice that RG is complete because the structure M given by M = {0} and RM = ∅ trivially embeds
into all models of RG.
Suppose now that R is a ring and p1 , p2 , . . . , pm , q ∈ R[y] listed in decreasing order of degrees. Let the
leading term of p1 be ay n and let the leading term of pm be by k . We then have that there is a simlutaneous
root of polynomials p1 , p2 , . . . , pm which is not a root of q if and only if one of the following happens:
1. b = 0 and there is simlutaneous root of polynomials p1 , p2 , . . . , pm−1 , pm − by k which is not a root of q.
2. b 6= 0 and there is a simultaneous root of the polynomials bp1 − ay n−k pm , p2 , . . . , pm which is not a
root of q.
Repeating this, we may assume that we have a forumla of the form
∃y[p(~x, y) = 0 ∧ q(~x, y) 6= 0]
If q is not present, then we may use the fact that in an algebraically closed field, the polynomial an y n +
· · · + a1 y + a0 has a root if and only if some ai 6= 0 for i > 0, or a0 = 0. If p is not present, then we use
7.5. ALGEBRAICALLY CLOSED FIELDS 109
the fact that every algebraically closed field is infinite and also that every nonzero has finitely many roots to
conclude that the there is an element which is not a root of the polynomial an y n + · · · a1 y + a0 if and only
if some ai 6= 0.
Suppose then that both p and q are present. The key fact is to use here is that if p and q are polynomials
over an algebraically closed field and the degree of p is at most n, then every root of p is a root of q if and
only if p | q n .
Thus, we have two polynomials p and q, and we want to find a quantifier formula equivlent to p | q. We
may now use the Euclidean algorithm to repeatedly reduce the problem.
Corollary 7.5.3. ACF0 is complete and ACFp is complete for all primes p.
Corollary 7.5.4. If F and K are algebraically closed fields such that F is a subfield of K, then (F, 0, 1, +, ·)
(K, 0, 1, +, ·).
Proof. 1 imples 2 is Compactness. 2 implies 3 is trivial. 3 implies 1 using completeness of ACF0 and the
ACFp for each prime p, together with 1 implies 2.
Proposition 7.5.8. Let p be prime. Every finitely generated subfield of Fp is finite.
n
Proof. Let p be prime. For every n, let Kn be the set of roots of xp − x in Fp . By standard results
in algebra, we have that Kn is a field of order pn , and furthermore is the unique subfield of Fp of order
d 2·d d d d
pn . If d | n, we then have that Kd ⊆ Kn because if ap = a, then ap = (ap )p = ap = a, so
3·d 2·d d d
ap = (ap )p = ap = a, etc. Let K = n∈N Kn . Notice that K is a subfield of Fp because if a ∈ Kn
S
and b ∈ Km , then a + b, a · b ∈ Km·n . Furthermore, notice that K is algebraically closed because a finite
extension of a finite field is finite. Therefore, K = Fp .
Theorem 7.5.9. Every injective polynomial map from Cn to Cn is surjective.
Proof. Let σn,d ∈ SentL be the sentence expressing that every injective polynomial map from F n to F n
where each polynomial has degree at most d is surjective. We want to show that C σn,d for all n, d. To do
this, it suffices to show that Fp σn,d for all primes p and all n, d ∈ N. Thus, it suffices to show that for all
n n
primes p, every injective polynomial map from Fp to Fp is surjective.
n n
Fix a prime p and an n ∈ N. Suppose that f : Fp → Fp is an injective polynomial map. Let
n n
(b1 , b2 , . . . , bn ) ∈ Fp . We need to show that there exists (a1 , a2 , . . . , an ) ∈ Fp with f (a1 , a2 , . . . , an ) =
(b1 , b2 , . . . , bn ). Let f1 , f2 , . . . , fn ∈ Fp [x1 , x2 , . . . , xn ] be such that f = (f1 , f2 , . . . , fn ), and let C be the fi-
nite set of coefficients appearing in f1 , f2 , . . . , fn . Let K be the subfield of Fp generated by C ∪{b1 , b2 , . . . , bn }
and notice that K is a finite field. Now f K n maps K n into K n and is injective, so it’s surjective because
n
K n is finite. Thus, there exists (a1 , a2 , . . . , an ) ∈ K n ⊆ Fp such that f (a1 , a2 , . . . , an ) = (b1 , b2 , . . . , bn ).
110 CHAPTER 7. QUANTIFIER ELIMINATION
Chapter 8
Using Proposition 6.5.3, we can immediately give a negative answer to this question because there is an
uncountable model of T h(N), and an uncountable model can’t be isomorphic to N. What would such a
model look like? In order to answer this, let’s think a little about the kinds of sentences that are in T h(N).
Definition 8.1.2. For each n ∈ N, we define a term n ∈ T ermL as follows. Let 0 = 0 and let 1 = 1. Now
define the n recursively by letting n + 1 = n + 1 for each n ≥ 1. Notice here that the 1 and the + in n + 1
mean the actual number 1 and the actual addition function, whereas the 1 and + in n + 1 mean the symbols
1 and + in our language L. Thus, for example, 2 is the term 1 + 1 and 3 is the term (1 + 1) + 1.
Definition 8.1.3. Let M be an L-structure. We know that given any t ∈ T ermL containing no variables, t
corresponds to an element of M given by s(t) for some (any) variable assignment s : V ar → M . We denote
this value by tM .
Notice that nN = n for all n ∈ N be a simple induction. Here are some important examples of the kinds
of things in T h(N).
2. ∀x∀y(x + y = y + x)
111
112 CHAPTER 8. NONSTANDARD MODELS OF ARITHMETIC AND ANALYSIS
Now any model M of T h(N) must satisfy all of these sentences. The basic sentences in 1 above roughly
tell us that M has a piece which looks just like N. We make this precise as follows.
Proposition 8.1.4. For any model M of T h(N), the function h : N → M given by h(n) = nM is an
embedding of N into M.
Proof. Notice that
h(0N ) = h(0) = 0M = 0M
and
h(1N ) = h(1) = 1M = 1M
Now let m, n ∈ N. We have
m<n⇔Nm<n
⇔ m < n ∈ T h(N)
⇔Mm<n
⇔ mM <M nM
⇔ h(m) <M h(n)
h(m + n) = (m + n)M
= m M +M n M
= h(m) +M h(n)
h(m · n) = (m · n)M
= mM ·M nM
= h(m) ·M h(n)
Finally, for any m, n ∈ N with m 6= n, we have m 6= n ∈ T h(N), so M m 6= n, and hence h(m) 6= h(n).
Proposition 8.1.5. Let M be a model of T h(N). The following are equivalent.
1. M ∼
= N.
2. M = {nM : n ∈ N}.
Proof. If 2 holds, then the h of the Proposition 8.1.4 is surjective and hence an isomorphism. Suppose then
that 1 holds and fix an isomorphism h : N → M from N to M. We show that h(n) = nM for all n ∈ N by
induction. We have
h(0) = h(0N ) = 0M
and
h(1) = h(1N ) = 1M
8.2. THE STRUCTURE OF NONSTANDARD MODELS OF ARITHMETIC 113
We’ve already seen that there are nonstandard models of arithmetic by cardinality considerations, but
we can also build countable nonstandard models of arithmetic using the Compactness Theorem and the
Countable Lowenheim-Skolem Theorem.
Proof. Let L0 = L ∪ {c} where c is a new constant symbol. Consider the following set of L0 -sentences.
Σ0 = T h(N) ∪ {c 6= n : n ∈ N}
Notice that every finite subset of Σ0 has a model (by taking N and interpreting c large enough), so Σ0
has a countable model M (notice that L0 is countable) by the Compactness Theorem and the Countable
Lowenheim-Skolem Theorem. Restricting this model to the original language L, we may use the Proposition
8.1.5 to conclude that M is a countable nonstandard model of arithmetic.
Proposition 8.2.1.
• +M is associative on M .
• +M is commutative on M .
• ∀x∀y∀z(x + (y + z) = (x + y) + x)
• ∀x∀y(x + y = y + x)
are in T h(N).
114 CHAPTER 8. NONSTANDARD MODELS OF ARITHMETIC AND ANALYSIS
Since we already know that N is naturally embedded in M, and it gets tiresome to write +M , ·M , and
<M , we’ll abuse notation by using just +, ·, and < to denote these. Thus, these symbols now have three
different meanings. They are used as formal symbols in our language, as the normal functions and relations
in N, and as their interpretations in M. Make sure you know how each appearance of these symbols is being
used.
Definition 8.2.2. We let Mf in = {nM : n ∈ N} and we call Mf in the set of finite elements of M. We also
let Minf = M \Mf in and we call Minf the set of infinite elements of M.
The following definition justifies our choice of name.
Proposition 8.2.3. Let a ∈ Minf . For any n ∈ N, we have nM < a.
Proof. For each n ∈ N, the sentence
n−1
_
∀x(x < n → (x = i))
i=0
is in T h(N). Since a 6= nM for all n ∈ N, it follows that it’s not the case that a < nM for all n ∈ N. Since
< is a linear ordering on M , we may conclude that nM < a for all n ∈ N.
Definition 8.2.4. Define a relation ∼ on M by letting a ∼ b if either
• a = b.
• a < b and there exists n ∈ N such that a + nM = b.
• b < a and there exists n ∈ N such that b + nM = a.
In other words, a ∼ b if a and b are “finitely” far apart.
Proposition 8.2.5. ∼ is an equivalence relation on M .
Proof. ∼ is clearly relexive and symmetric. Suppose that a, b, c ∈ M , that a ∼ b, and that b ∼ c. We handle
one case. Suppose that a < b and b < c. Fix m, n ∈ N with a + mM = b and b + nM = c. We then have
a + (m + n)M = a + (mM + nM )
= (a + mM ) + nM
= b + nM
=c
so a ∼ c. The other cases are similar.
Definition 8.2.6. Let a, b ∈ M . We write a b to mean that a < b and a 6∼ b.
We’d like to know that that relation is well-defined on the equivalence classes of ∼. The following
lemma is useful.
Lemma 8.2.7. Let a, b, c ∈ M be such that a ≤ b ≤ c and suppose that a ∼ c. We then have a ∼ b and
b ∼ c.
Proof. If either a = b or b = c, this is trivial, so assume that a < b < c. Since a < c and a ∼ c, there exists
n ∈ N+ with a + nM = c. Now the sentence
∀x∀z∀w(x + w = z → ∀y((x < y ∧ y < z) → ∃u(u < w ∧ x + u = y)))
is in T h(N), so there exists d ∈ M such that d < nM and a + d = b. Since d < nM , there exists i ∈ N with
d = iM . We then have a + iM = b, hence a ∼ b. The proof that b ∼ c is similar.
8.2. THE STRUCTURE OF NONSTANDARD MODELS OF ARITHMETIC 115
Proposition 8.2.8. Suppose that a0 , b0 ∈ M are such that a0 b0 . For any a, b ∈ M with a ∼ a0 and
b ∼ b0 , we have a b.
Proof. We first show that a 6∼ b. If a ∼ b, then using a0 ∼ a and b0 ∼ b, together with the fact that ∼ is an
equivalence relation, we can conclude that a0 ∼ b0 , a contradiction. Therefore, a 6∼ b.
Thus, we need only show that a < b. Notice that a0 < b because otherwise a0 ∼ b0 by Lemma 8.2.7.
Similarly, a < b0 because otherwise a0 ∼ b0 by Lemma 8.2.7. Thus, if b ≤ a, we have
a0 < b ≤ a < b0 .
The next proposition implies that there is no largest equivalence class under the ordering ≺.
is in T h(N). Using this when n = 0, we see that a = a + 0M < a + a. Since a ∈ Minf , we have nM < a and
hence a + nM < a + a for all n ∈ N. Therefore, a + nM 6= a + a for all n ∈ N, and so a 6∼ a + a.
Proof. Suppose first that we have a b ∈ M such that a = 2M · b. We then have a = b + b (because
∀x(2 · x = x + x) is in T h(N)). Notice that b ∈
/ Mf in because otherwise we would have a ∈ Mf in . Therefore,
b b + b = a using Proposition 8.2.10. Suppose instead that we have a b ∈ M such that a = 2M · b + 1M .
We then have a = (b + b) + 1M because ∀x(2 · x + 1 = (x + x) + 1) is in T h(N). Notice that b ∈
/ Mf in because
otherwise we would have a ∈ Mf in . Therefore, b b + b using Proposition 8.2.10, so b (b + b) + 1 = a
since b + b ∼ (b + b) + 1.
Proposition 8.2.13. For any a, b ∈ Minf with a b, there exists c ∈ Minf with a c b.
Proof. Suppose first that we have a c ∈ M such that a + b = 2M · c. We then have a + b = c + c. Since
a + (2n)M + b = c + c + (2n)M
= (c + nM ) + (c + nM )
=b+b
This last proposition shows how nonstandard models can simplify quantifiers. It says that asking whether
a first-order statement holds for infinitely many n ∈ N is equivalent to asking whether it holds for at least
one infinite element of a nonstandard model.
Proof. Suppose first that there are infinitely many n ∈ N such that (N, n) ϕ. In this case, the sentence
∀y∃x(y < x ∧ ϕ)
is in T h(N), so it holds in M. Fixing any b ∈ Minf , we may conclude that there exists a ∈ M with b < a
such that (M, a) ϕ. Since b < a and b ∈ Minf , we may conclude that a ∈ Minf .
Conversely, suppose that there are only finitely many n ∈ N such that (N, a) ϕ. Fix N ∈ N such that
n < N for all n with (N, n) ϕ. We then have that the sentence
∀x(ϕ → x < N )
is in T h(N), so it holds in M. Since there is no a ∈ Minf with a < N M , it follows that there is no a ∈ Minf
such that M ϕ(a).
Proposition 8.3.1. For any model M of T h(R), the function h : R → M given by h(n) = rM is an
embedding of R into M.
8.3. NONSTANDARD MODELS OF ANALYSIS 117
(r1 , r2 , . . . , rn ) ∈ P R ⇔ R P r1 r2 · · · rk
⇔ P r1 r2 · · · rk ∈ T h(R)
⇔ M P r1 r2 · · · rk
⇔ (r1 M , r2 M , . . . , rk M ) ∈ P M
⇔ (h(r1 ), h(r2 ), . . . , h(rk )) ∈ P M
1. M ∼
= R.
2. M = {rM : r ∈ R}.
Proof. If 2 holds, then the h of the Proposition 8.3.1 is surjective and hence an isomorphism. Suppose
then that 1 holds and fix an isomorphism h : R → M from R to M. For any r ∈ R, we must have
h(r) = h(rR ) = rM . Therefore, M = {rM : r ∈ R} because h is surjective.
Proof. Let L0 = L ∪ {c} where c is a new constant symbol. Consider the following set of L0 -sentences.
Σ0 = T h(R) ∪ {c 6= r : r ∈ R}
Notice that every finite subset of Σ0 has a model (by taking R and interpreting c distinct from each r
such that r appears in Σ0 ), so Σ0 has a model M by the Compactness Theorem. Restricting this model to
the original language L, we may use the Proposition 8.3.2 to conclude that M is a nonstandard model of
analysis.
Definition 8.3.5. ∗For the rest of this section, fix a nonstandard model of analysis and denote it by ∗ R.
Instead of wrting f R for each f : Rk → R, we simply write ∗ f . We use similar notation for each P ⊆ Rk .
Also, since there is a natural embedding (the h above) from R into ∗ R, we will identify R with it’s image
and hence think of R as a subset of ∗ R. Finally, for operations like + and ·, we will abuse notation and omit
the ∗’s.
Proposition 8.3.6. There exists z ∈ ∗ R such that z > 0 and z < ε for all ε ∈ R with ε > 0.
118 CHAPTER 8. NONSTANDARD MODELS OF ARITHMETIC AND ANALYSIS
Let z = ∗ f (b). We then have have that z > 0 using the sentence
Also, for any ε ∈ R with ε > 0, we have that b > 1ε , hence z < ε using the sentence
Case 2: Suppose that b < r for all r ∈ R. We then have that b < −r for all r ∈ R and hence r < −b for
all r ∈ R. Thus, we may tak z = ∗ f (−b) by the argument in Case 1.
Case 3: Suppose then that there exists r ∈ R with r < b and there exists r ∈ R with b < r. Let
X = {r ∈ R : r < b}
Notice that X is downward closed (if r1 , r2 ∈ R with r2 ∈ X and r1 < r2 , then r1 ∈ X), nonempty, bounded
above, Let s = sup X ∈ R. Now b = s is impossible, so either s < b or b < s.
Subcase 1: Suppose that s < b. We claim that we may take z = b − s. Since s < b, we have z = b − s > 0.
Suppose that ε ∈ R and ε > 0. We then have that s + ε > s = sup X, so s + ε ∈ / X and hence s + ε ≥ b.
Now s + ε 6= b because s + ε ∈ R, so s + ε > b. It follows that z = b − s < ε.
Subcase 2: Suppose that b < s. We claim that we may take z = s − b. Since b < s, we have z = s − b > 0.
Suppose that ε ∈ R and ε > 0. We then that s − ε < s = sup X, so we may fix r ∈ X with s − ε < r. Since
X is downward closed, we have that s − ε ∈ X, so s − ε < b. It follows that z = s − b < ε.
Definition 8.3.7.
1. Z = {a ∈ ∗ R : |a| < ε for all ε ∈ R with ε > 0}. We call Z the set of infinitesimals.
2. F = {a ∈ ∗ R : |a| < r for some r ∈ R with r > 0}. We call F the set of finite or limited elements.
Proposition 8.3.8.
1. Z is a subring of ∗ R.
2. F is a subring of ∗ R.
3. Z is a prime ideal of F.
Proof.
|a − b| ≤ |a + (−b)|
≤ |a| + | − b|
≤ |a| + |b|
ε ε
< +
2 2
=ε
Therefore, a − b ∈ Z. We also have that |a| < 1 and |b| < ε, hence
|a · b| = |a| · |b|
<1·ε
=ε
Therefore, a · b ∈ Z.
2. Clearly, F 6= ∅. Suppose that a, b ∈ F, and fix r1 , r2 ∈ R with r1 , r2 > 0 such that |a| < r1 and |b| < r2 .
We have
|a − b| ≤ |a + (−b)|
≤ |a| + | − b|
≤ |a| + |b|
< r1 + r2
so a − b ∈ F. We also have
|a · b| = |a| · |b|
< r1 · r2
so a · b ∈ F.
3. We first show that Z is an ideal of F. Suppose that a ∈ F and b ∈ Z. Fix r ∈ R with r > 0 and
|a| < r. Let ε ∈ R with ε > 0. We then have that rε ∈ R and rε > 0, hence |a| < rε . It follows that
|a · b| = |a| · |b|
ε
< ·r
r
=ε
Therefore, a · b ∈ Z.
We now show that Z is a prime ideal of F. Suppose that a, b ∈ F\Z. We have a · b ∈ F by part 2.
Fix ε, δ ∈ R with ε, δ > 0 such that |a| > ε and |b| > δ. We then have |a · b| = |a| · |b| > ε · δ, hence
a·b∈ / Z.
Proof.
1. We have a1 − b1 ∈ Z and a2 − b2 ∈ Z, hence
is in Z by Proposition 8.3.8.
2. We have a1 − b1 ∈ Z and a2 − b2 ∈ Z, hence
is in Z by Proposition 8.3.8.
3. We have a1 − b1 ∈ Z and a2 − b2 ∈ Z. Now
a1 · a2 − b1 · b2 = a1 · a2 − a1 · b2 + a1 · b2 − b1 · b2 = a1 · (a2 − b2 ) + b2 · (a1 − b1 )
so a1 · a2 − b1 · b2 ∈ Z by Proposition 8.3.8.
4. We have a1 − b1 ∈ Z and a2 − b2 ∈ Z. Now
a1 b1 a1 · b2 − a2 · b1 1
− = = · (a1 · b2 − a2 · b1 )
a2 b2 a2 · b2 a2 · b2
and we know by part 3 that a1 · b2 − a2 · b1 ∈ Z. Since a2 , b2 ∈ F\Z, it follows that a2 · b2 ∈ F\Z
by Proposition 8.3.8. Therefore, a21·b2 ∈ F (if ε > 0 is such that |a2 · b2 | > ε, then | a21·b2 | < 1ε ), so
a1 b1
a2 − b2 ∈ Z by Proposition 8.3.8.
X = {r ∈ R : r < a}
and notice that X is downward closed, nonempty, and bounded above because a ∈ F. Now let s = sup X
and argue as in Case 3 of Proposition 8.3.6 that a ≈ s.
Suppose now that r1 , r2 ∈ R are such that a ≈ r1 and a ≈ r2 . We then have that r1 ≈ r2 because ≈ is
an equivalence relation. However, this is a contradiction because |r1 − r2 | > |r1 −r
2
2|
∈ R.
8.3. NONSTANDARD MODELS OF ANALYSIS 121
Definition 8.3.14. We define a map st : F → R by letting st(a) be the unique r ∈ R such that a ≈ r. We
call st(a) the standard part or shadow of a.
Corollary 8.3.15. The function st : F → R is a ring homomorphism and ker(st) = Z.
Proposition 8.3.16. Suppose that A ⊆ R, that f : A → R, and that r, ` ∈ R. Suppose also that there exists
δ > 0 such that (r − δ, r + δ)\{r} ⊆ A. The following are equivalent.
1. lim f (x) = `.
x→r
is in T h(∗ R) = T h(R). By fixing a witnessing δ, we see that the limit condition holds for ε.
Proposition 8.3.17. Suppose that A ⊆ R, that f, g : A → R, and that r, `, m ∈ R. Suppose also that there
exists δ > 0 such that (r − δ, r + δ)\{r} ⊆ A, that lim f (x) = ` and lim g(x) = m. We then have
x→r x→r
1. lim (f + g)(x) = ` + m.
x→r
2. lim (f − g)(x) = ` + m.
x→r
3. lim (f · g)(x) = ` · m.
x→r
Corollary 8.3.18. Suppose that A ⊆ R, that f : A → R, and that r ∈ R. Suppose also that there exists
δ > 0 such that (r − δ, r + δ) ⊆ A. The following are equivalent.
1. f is continuous at r.
2. For all a ≈ r, we have ∗ f (a) ≈ f (r).
122 CHAPTER 8. NONSTANDARD MODELS OF ARITHMETIC AND ANALYSIS
Taking the standard definition of the derivative, we immediately get the following.
Corollary 8.3.19. Suppose that A ⊆ R, that f : A → R, and that r, ` ∈ R. Suppose also that there exists
δ > 0 such that (r − δ, r + δ) ⊆ A. The following are equivalent.
1. f is differentiable at r with f 0 (r) = `.
∗
f (a)−f (r)
2. For all a ≈ r with a 6= r, we have a−r ≈ `.
Now fix a ≈ r with a 6= r. Since g is continuous at r, we have ∗ g(a) ≈ g(r). If ∗ g(a) 6= g(r), then
∗ ∗ ∗
(f ◦ g)(a) − (f ◦ g)(r) f ( g(a)) − f (g(r))
=
a−r a−r
∗ ∗
f ( g(a)) − f (g(r)) ∗ g(a) − g(r)
= ∗ g(a) − g(r)
·
a−r
0 0
≈ f (g(r)) · g (r)
Suppose then that ∗ g(a) = g(r). Since the first line above holds for every a ≈ r with a 6= r, we must have
g 0 (r) ≈ 0 and hence g 0 (r) = 0 because g 0 (r) ∈ R. Therefore,
∗ ∗ ∗
(f ◦ g)(a) − (f ◦ g)(r) f ( g(a)) − f (g(r))
=
a−r a−r
=0
= f 0 (g(r)) · g 0 (r)