Advanced Logic

—-
Lecture Notes

Toby Meadows
E-mail address: [Link]@[Link]
c Toby Meadows

.1 f
t
v1 ra
inDe
nl
O
 I would like to thank Aleksi Anttila, Adam George and Justine Retford for
welcome suggestions in making these notes clearer and for their patience in
spotting typos in the document.
c Toby Meadows

.1 f
t
v1 ra
inDe
nl
O
 3

READ ME:

These notes are still drafts:

• there will be typos;
• there may be errors; and
• I plan to augment them.
That said, they should be complete enough to be
useful and I hope you find them so.

I plan to update this document on my website:

c Toby Meadows

t
[Link]
.1 f
v1 ra

Unless you’ve already come from there, it could be

worth looking there for a more recent version of
D

this document.

Also, if you do spot any problems or there’s

something you don’t like or understand, I’d like to
e

hear about it. Please drop me an email at:

in
nl

[Link]@[Link].
O
 Contents

Part 1. Models & Proofs 6

Chapter 1. Languages and Induction 7

1.1. The Language of First Order Logic 7
1.2. Induction 11
Exercises Week 1 17

Chapter 2. Models 18
c Toby Meadows

2.1. What is a model? 18

2.2. Satisfaction 20
2.3. Important Semantic Properties
Exercises Week 2
.1 f
t 29
30
v1 ra
Chapter 3. Proof Systems 33
3.1. Tableau 33
3.2. Natural Deduction 38
D

3.3. Interesting Properties 40

Exercises Week 3 41

Chapter 4. Completeness 1 43
4.1. Completeness 43
4.2. Soundness 50
e

4.3. Exercises 54
in

Chapter 5. Completeness 2 55
5.1. Soundness 55
nl

5.2. Completeness 60
5.3. Exercises 66
O

Chapter 6. Model Theory 67

6.1. Isomorphism and Elementary Equivalence 67
6.2. The compactness theorem 69
6.3. Submodels & Embeddings 71
4
 CONTENTS 5

6.4. Basic Set Theory 74

6.5. Löwenheim-Skolem Theorems 78
6.6. Exercises 80

Part 2. Recursion & Incompleteness 81

Chapter 7. Recursion theory 1 82

7.1. Algorithms & Turing Machines 82
7.2. Gödel’s schema 87
7.3. Exercises. 93

Chapter 8. Recursion theory 2 94

8.1. Equivalence of Turing machines with Gödel schema 94
8.2. The Church-Turing thesis 103
8.3. Limitations in the theory of recursion 105
c Toby Meadows

8.4. Recursive and recursively enumerable sets 110

8.5. Exercises. 112

Chapter 9. Arithmetic
.1 f
9.1. Theories and axioms
t 113
113
v1 ra
9.2. A sketch of the incompleteness theorem 113
9.3. A theory of arithmetic - P E 115
9.4. Exercises. 130
D

Chapter 10. Incompleteness 131

10.1. The Diagonal Lemma 131
10.2. Incompleteness 136
10.3. Exercises. 145
e
in
nl
O
 c Toby Meadows

O
nl
in D
e Part 1

v1 ra
.1 f
Models & Proofs

t
 CHAPTER 1

Languages and Induction

Goals:

(1) Define the language of first order logic.

(2) Use recursive definitions.
(3) Familiarise ourselves with mathematical proofs.
(4) Use mathematical induction.
c Toby Meadows

1.1. The Language of First Order Logic

.1 f
• logical symbols; t
1.1.1. The pieces. The language consists of three kinds of symbols:
v1 ra
• non-logical symbols; and
• individual variables.

[Link]. Logical symbols. The logical symbols are ¬, ∧, ∨, →, ↔, ∃, ( and ).

D

[Link]. Non-logical symbols. The non-logical symbols come in three types:

• constant symbols - a, b, c, ...;

• relation symbols - P, Q, R, ...; and
• function symbols - f, g, h, ....

Each of the relation and function symbols have an arity which reflects how
e

many names or variables they take as arguments.

in

We shall often collect together the non-logical vocabulary into a set L:

L = {a, b, c, ..., P, Q, R, ..., f, g, h, ...}.

nl

[Link]. Individual variables. The individual variables are v1 , v2 , ... .

O

We shall denote an arbitrary variables by x, y, z, ....

x, y, z are sometimes known as metavariables. This is because they aren’t
strictly part of the language we are studying: the object language. They are
part of the metalanguage.
7
 1.1. THE LANGUAGE OF FIRST ORDER LOGIC 8

1.1.2. Terms and formulae

. PROBLEM: We need some way of saying when a string of these symbols is
correct or grammatical; then we shall say that it is well-formed.
The guiding idea of our definition is as follows:
• We shall take some basic strings which are obviously well-formed.
We shall call these atoms.
• Then we describe some rules which allows us to take well-formed
string and build other well formed string.
• If a string can be eventually constructed out of atoms using the
rules, then it is well-formed. Nothing else is a well formed string.
This is called a recursive definition.
[Link]. A warmup definition . Let’s use a simpler language. Let’s sup-
pose that:
c Toby Meadows

• the non-logical vocabulary consists of two propositional symbols, p

and q;

t
• the logical vocabulary consists of just the symbol ∧.
.1 f
v1 ra
We might then define a well-formed string as follows:
• Let p and q be atoms; thus they are well-formed string.
• If we have two well formed string, say ϕ and χ, then ϕ ∧ χ is a well
formed string; i.e., the string formed by placing the ∧ symbol be-
D

tween them is itself a well formed string.

• If ϕ is a string formed from atoms following the rule, then ϕ is a well
formed string; ϕ ∈ W F S. Nothing else is a well formed string.

R EMARK 1. Note the use of the symbols ϕ and χ to stand for arbitrary strings.
Are they part of language?
e
in

We can also define W F S by a kind of construction of stages:

• at the first stage, we start with p and q (the atoms) which we know
nl

are well-formed;
• then at the next stage, we form all of the strings that can be formed
O

from them using the rules - giving us p ∧ q, q ∧ p, p ∧ p, q ∧ q;

• we then keep repeating the process; and
• if ϕ gets into one of the stages, then it is in W F S.
More formally,
 1.1. THE LANGUAGE OF FIRST ORDER LOGIC 9

D EFINITION 2. ϕ ∈ W F S iff there is some stage n such that ϕ ∈ Stage(n) (the

nth stage of the construction) where:
• Stage(1) = {p, q}; and
• Stage(n + 1) is the set of ϕ such that either:
(1) ϕ ∈ Stage(n); or
(2) ϕ is of the form ψ ∧ χ where ψ, χ ∈ Stage(n).

(1.) just ensures that everything from the previous stages is included in the
next; thus, we accumulate everything we built beforehand as we go.
It turns out that these two definitions are equivalent.
[Link]. First order logic. Using the same process, we now define the
terms and well-formed formulae of first order logic.
Intuitively, a terms is something like a name. We build up the definition of
c Toby Meadows

a term using a recursive construction:

• (Base) if t is a constant symbol or an individual variable, then t is a
term.
.1 f
t
• (Rule) if t1 , ..., tn are terms and f is a function symbol with arity n,
v1 ra
then f (t1 , ..., tn ) is a term.

E XAMPLE 3. Let L have two one function symbol f with arity 2 and a constant
symbol a. Then the following are terms:
D

• a;
• v1 ;
• f (v1 a); and
• f (v1 , f (v1 , a)).

Let us call the set of terms T erm.

e

A string ϕ is an atom if:

in

• ϕ = Rt1 , ..., tn where t1 , ..., tn ∈ T erm and R is a relation symbol with

arity n.
nl

We then set out the process for constructing well formed formulae below:
O

• if ϕ is an atom then ϕ ∈ W F F ;
• if ϕ ∈ {¬ψ, ∀xψ, ∃xψ} where ψ ∈ W F F and x is a variable, then ϕ ∈
WFF;
• if ϕ ∈ {(ψ ∧ χ), (χ ∨ ψ), (ψ → χ), (ψ ↔ χ)} where ψ, χ ∈ W F F , ϕ ∈ W F F ;
 1.1. THE LANGUAGE OF FIRST ORDER LOGIC 10

• nothing else is in W F F .

R EMARK 4. The logical vocabulary and individual variables will be the same
for the remainder of this course. Thus when we speak of a language L we
shall often just mean the non-logical vocabulary. This shouldn’t cause too
much confusion. Also observe that we are including brackets around each
of the formulae before when we compose new formulae from them.

We can also define the same set using our stage based approach.

D EFINITION 5. ϕ ∈ W F F iff there is some stage n such that ϕ ∈ StageW F F (n)

(the nth stage of the construction) where:

• StageW F F (1) is the set of formulae of the form Rt1 , ..., tn where R is an
n-ary relation symbol and t1 , ..., tn are terms; and
c Toby Meadows

• StageW F F (n + 1) =is the set of ϕ such that either:

(1) ϕ ∈ StageW F F (n); or
.1 f
t
(2) ϕ ∈ {(ψ ∧ χ), (χ ∨ ψ), (ψ → χ), (ψ ↔ χ), ¬ψ, ∀xψ, ∃xψ} where ψ, χ ∈
StageW F F (n) and x is a variable.
v1 ra

1.1.3. Bound variables, free variables and sentences. Intuitively a vari-

able is free if it occurs outside the scope of all of the quantifiers in the for-
mula. A variable is bound if it is not free.
D

We’ll give some examples of this and leave it as an exercise to define the
relation x is free in ϕ using a recursive definition.

E XAMPLE 6. The variable v1 is free F v1 .

E XAMPLE 7. The variable v2 is bound in ∀v2 F v2 .

e

E XAMPLE 8. The variable v1 is bound in ∀v1 (∃v2 Rv1 v2 ∧ P v1 ).

in

E XAMPLE 9. The variable v1 is free in ∀v2 (Rv1 v2 ∧ ∀v3 (Gv1 → F v1 )).

nl

E XAMPLE 10. The variable v1 is free in ∀v1 (P v1 → Qv1 ) ∧ P v1 . Why?

O

D EFINITION 11. A sentence is a formula with no free variables. We shall

denote the sentences of some language L by SentL (omitting the L where
confusion will not arise). An atomic sentence is an atomic formula with no
free variables.
 1.2. INDUCTION 11

1.1.4. A few simplifications in the definition of W F F . Observe that

according to our definition of W F F , the following formulae are not well-
formed:
(1) F a ∧ Gb ∧ Gc (our rules say that either F a ∧ Gb or Gb ∧ Gc should have
brackets around it)
(2) F a ∨ Gb ∨ Gc (our rules say that either F a ∨ Gb or Gb ∨ Gc should have
brackets around it)
(3) ∀xP x (This sentence uses a metavariable x which is not actually part
of the language.)
Now this clearly a little annoying as we should be able to intuitively see
that none of these things would make any difference to the meaning of the
formula in question (although we haven’t really talked about meaning yet).
Moreover, it can make things very difficult to read. Consider
c Toby Meadows

as opposed to
.1 f
t
∀v1 (¬Rv1 v2 → ∃v3 (Hv3 v1 ∧ (∃v2 ¬Gv1 v2 ∧ P v3 )))
ra
∀x(¬Rxy → ∃z(Hzx ∧ ∃y¬Gxy ∧ P x)).
Thus, I’m often going to use a sloppier version of W F F , which allows us to
write formulae in the simpler form above.
D

In situations where is important to use the strict definition I will endeavour

to explicitly mention this. You should try to see that the translation back
to the strict language is very trivial and as such, the difference will rarely
v1

matter.

1.2. Induction
e

Mathematical induction is, in a sense, the other side of coin for recursive
in

constructions we’ve considered in the previous section.

nl

1.2.1. Motivation. Consider the natural numbers N = 0, 1, ... and con-

sider some subset A ⊆ N; i.e., a collection of natural numbers.
O

Now suppose that 0 ∈ A.

Moreover, suppose that for any natural number n, if n ∈ A, then n + 1 ∈ A.
So given any number, if it’s in A, then so is the next one.
If this is the case, then clearly every number n must be in A.
 1.2. INDUCTION 12

F ACT 12. (IND) Suppose A ⊆ N. If 0 ∈ A and ∀n(n ∈ A → n + 1 ∈ A), then

∀n n ∈ A.

[Link]. The least number principle. If the previous principle isn’t obvi-
ous, the perhaps this one is.

F ACT 13. (LNP) If B ⊆ N is not empty, then there is some n ∈ B such that for
all m < n, m ∈
/ B; i.e., there is some least member of B.

Of course, the least member could be 0.

Let’s prove IND, using LNP.

T HEOREM 14. LNP → IND.

R EMARK 15. We are going to produce a reductio ad absurdum. Intuitively,

the idea is that we’ll take the LNP as given and then see what happens if
c Toby Meadows

we assume that IND is not true. We’ll show that this leads us to contradict
ourselves: and absurdity. Thus, our assumption that IND is not true, is
.1 f
t
itself wrong. Thus IND is actually correct.

P ROOF. Assume LNP. Now suppose for reductio, that IND is not correct.
v1 ra
Then there is some A ⊆ N, such that:
(1) 0 ∈ A;
(2) ∀n(n ∈ A → n + 1 ∈ A); but
D

(3) there is some n, such that n ∈

/ A.
Let B = N\A; i.e., the set of natural numbers that are not in A. This not
empty by (3.) By LNP, there is some least member of B. Let’s call it b. Now b
is a natural number so either:
• b = 0; or
e

• b = n + 1 for some n.
in

In the first case, this would mean b = 0 ∈ B and thus 0 ∈ / A, contradicting

(1.). In the second case, since b = n + 1 is the least member of B, we have
nl

n ∈ A, but b = n + 1 ∈
/ A, contradicting (2.).
This tells us that there cannot be such a B; i.e., that for all n, we actually
O

have n ∈ A. Thus IND is correct. 

Indeed, we can actually go the other way too. We can prove LNP from IND.

T HEOREM 16. IND → LNP.

 1.2. INDUCTION 13

P ROOF. Suppose IND is true, but for a reductio, suppose that LNP is not.
Then there is some subset B ⊆ N such that:
(1) B is not empty; and
(2) B has no least element.
Let A = N\B. Clearly 0 ∈ / B (for then 0 would be the least element), so 0 ∈ A.
Moreover, since B has no least element, this just means that for any n ∈ N,
if n + 1 ∈ B, then n ∈ B; otherwise, such an n would be the least. But this
means that for any n if n + 1 ∈ / A, then n ∈
/ A; and by contraposition, if n ∈ A,
then n + 1 ∈ A. Thus we have both the antecedent conditions of IND and so
for all n, n ∈ A; i.e., n ∈
/ B. But this means B is empty contradicting (1.).
Thus LNP must be true after all.

c Toby Meadows

R EMARK 17. So there is a sense in which they actually both mean the same
thing. .1 f
1.2.2. Using induction.
t
v1 ra
[Link]. A simple mathematical proof. A triangular number n is such that

n = m + (m − 1) + ... + 2 + 1

for some m.
D

We can use induction to prove the following fact about natural numbers.
m(m+1)
T HEOREM 18. For all m, m + (m − 1) + ... + 2 + 1 = 2
.

R EMARK 19. This a universal statement that we want to prove by induction.

We are going to let A be the set of numbers m such that
e

m(m + 1)
in

m + (m − 1) + ... + 2 + 1 = .
2
That is, every m ∈ A is such that the equation above holds of m.
nl

To use induction, we need to show that:

(1) 0 ∈ A; and
O

(2) ∀n, if n ∈ A, then n + 1 ∈ A.

From there, we can conclude that every n is in A.
We shall call step (1.) the base case; and step (2.) the induction step.
 1.2. INDUCTION 14

P ROOF. By induction.
(Base) We need to show that 0 ∈ A. For this to be true we just need
0(0 + 1)
0 =
2
= 0/2
= 0

which is obviously correct.

(Induction Step) We take some n ∈ A and show that n + 1 ∈ A. The fact that
n ∈ A just means that
n(n + 1)
n + (n − 1) + ... + 2 + 1 = .
2
Then consider the next triangular number
c Toby Meadows

(n + 1) + n + (n − 1) + ... + 2 + 1.

t
Then with a little bit of simple maths, we get
.1 f
ra
n(n + 1)
(n + 1) + n + (n − 1) + ... + 2 + 1 = (n + 1) +
2
2
n +n
= (n + 1) +
2
D

(2n + 2) + (n2 + n)
=
2
n2 + 3n + 2
v1

=
2
(n + 1)(n + 2)
=
2
(n + 1)((n + 1) + 1)
e

=
2
in

But this just means that n + 1 ∈ A.

Thus by IND, we see that every n is in A, which is what we wanted to show.
nl


O

[Link]. Using induction on a language. Let’s go back to the toy language

from Section [Link].
It should be obvious that any ϕ ∈ W F S (i.e., a well formed string) is either
atomic or of the form χ ∧ ψ for some χ, ψ ∈ W F S.
 1.2. INDUCTION 15

But how would we prove this? We use induction.

T HEOREM 20. For every ϕ ∈ W F S either ϕ is atomic or ϕ is of the form (ψ ∧ χ)

for some χ, ψ ∈ W F S.

But how to do we use induction here? These strings are not natural num-
bers.
Consider Definition 2, which used stages construct all of the well formed
strings. Each stage of the definition was indexed by a particular natural
number n.
We shall use the stage indices to make a proof by by induction. Thus we shall
demonstrate that the proposition holds for every stage n of the construction
and thus for everything in W F S.
Thus we shall make A the set of n such that ϕ ∈ Stage(n) iff either:
c Toby Meadows

• ϕ is atomic; or
.1 f
t
• ϕ is of the form ψ ∧ χ where ψ ∧ χ ∈ Stage(m) for some m < n.

P ROOF. By induction on the stage of the construction of W F S.

v1 ra
(BASE) We need to show that 0 ∈ A, which just means that for all ϕ ∈ Stage(0)
either ϕ is atomic or ϕ is of the form ψ ∧ χ where ψ ∧ χ ∈ Stage(m) for some
m < 0. There are no stages m < 0, so we don’t have to worry about the
D

second part. Moreover, since Stage(0) = {p, q}, it is obvious that everything
in Stage(0) is atomic which is sufficient.
(INDUCTION STEP) Suppose n ∈ A. We must show that n+1 ∈ A. Since n ∈ A,
every ϕ ∈ Stage(n) is either atomic or of the form ψ ∧ χ for ψ, χ ∈ Stage(m) for
some m < n. Thus we only need to worry about those strings added at stage
n + 1. Suppose ϕ ∈ Stage(n + 1)\Stage(n); i.e., it’s one of the new things
e

added at stage n + 1. Then by the way we defined the rule of construction for
in

Stage(n + 1), ϕ must be of the form ψ ∧ χ for some ψ, χ ∈ Stage(n). So n + 1 ∈ A.

Then by induction we see that every n ∈ A. Thus for all ϕ ∈ W F S, ϕ is either
nl

atomic or ϕ is of the form ψ ∧ χ for some ψ, χ ∈ W F S. 

O

Now this is a very simple proof. In a sense, we used the definition by recur-
sion to construct a set of well formed strings and then we used induction to
show that they indeed were well formed.
We’ll usually, however, be concerned with:
 1.2. INDUCTION 16

• a more complex language (first order logic); and

• a more difficult problem.
As such, we often want a way of streamlining the kind of proof we did above.
Rather than concerning ourselves with stages in a construction, we often
define the complexity of a formula.
D EFINITION 21. Let ϕ ∈ W F F be a well formed formula of the language of first
order logic. We define the complexity of ϕ, abbreviated comp(ϕ), by recursion
as follows:
• if ϕ is atomic, then comp(ϕ) = 0;
• if ϕ ∈ {¬ψ, ∀xψ, ∃xψ} and ψ ∈ W F F , then comp(ϕ) = comp(ψ) + 1;
• if ϕ ∈ {(ψ ∧ χ), (ψ ∨ χ), (ψ → χ), (ψ ↔ χ)} and ψ, χ ∈ W F F , then

comp(ϕ) = max(comp(ψ), comp(χ)) + 1,

c Toby Meadows

where max(m, n) is the maximum of m and n.

.1 f
t
Now suppose we want to construct a proof of some fact about all the well
formed formulae. If we want to use induction, we may do this by doing the
induction on the complexity of the formulae.
v1 ra

R EMARK 22. The complexity amounts to much the same thing as the stage
in the construction.
It is conventional in proofs by induction on complexity not to explicitly men-
D

tion the complexity of the formulae. The reason for this is that now we
understand the principles underpinning the induction, we don’t really need
to think about the numbers anymore.
When we make a proof by induction on the complexity/stage of formulae,
we really just need the following steps:
e

(1) (BASE) show that the property holds for the atomic case - this just
in

the 0-level of complexity.

(2) (INDUCTION STEP) show that if the property holds for two well-
nl

formed formulae, then it holds for any well formed formula that can
be constructed by the rules from them - this is just showing that we
O

can move from any level of complexity to the next.

In the case of first order logic, verifying the induction step entails verifying
that new formulae constructed using the rules still have the desired prop-
erty.
 EXERCISES WEEK 1 17

Exercises Week 1

E XERCISE 23. What change in the rules (of the recursive definition) would
you make to W F F in order to formalise the sloppy rules of W F F in such a
way to accommodate the kind of problem illustrated in (1.) and (2.) of 1.1.4?

E XERCISE 24. In which of the following formulae is v1 bound:

(1) ∀v1 P v1 v2 ;
(2) ∀v2 (P v1 v2 ∧ ∃v3 Rv1 v2 );
(3) ∀v2 (P v2 ∧ ∃v1 Rv1 v2 );
(4) ∀v2 (P v2 ∧ (∃v1 Rv1 v2 → P v1 )).

E XERCISE 25. Are all formulae sentences? Are all sentences formulae?

E XERCISE 26. Which of the following formulae are sentences:

c Toby Meadows

(1) ∀v1 P v1 v2 ;
(2) ∀v2 (∃v1 P v1 ∧ ∀v2 Rv1 v2 );
(3)
(4)
∀v2 (P v1 → ∃v1 Rv1 v2 );
.1 f
∀v1 (P v1 → ∃v2 Rv1 v2 ). t
v1 ra
E XERCISE 27. Develop a recursive definition for the relation:
• the variable x is free in the formula ϕ.
[Try to do this in stages. Define the atomic case and then rules for getting
D

from one stage to the next. Given an atomic sentence of the form ϕ :=
P t1 , ., tk , .., tn where x = tk is a variable (and a term) we can say that x is free
in P t1 , ..., tn .]

E XERCISE 28. Prove (using induction) that every string of our toy language
W F S contains an odd number of symbols. [Clearly the atoms contain an
e

odd number of symbols. You need to construct the induction hypothesis

in

that will allows to prove the claim for every level of complexity.]
nl
O
 CHAPTER 2

Models

Goals:
(1) Define a model.
(2) Describe what it means for a sentence to be true in a model.
(3) To define some important metatheoretic properties: including valid-
ity and satisfiability.
By what of introduction, we might think of a model as something for one
c Toby Meadows

of our languages to talk about. It will consist of things which bear certain
relations to other things in the model. Moreover, we shall be able to use
.1 f
what is going on inside the model. t
sentences in the language to talk about the model: to express things about
v1 ra
2.1. What is a model?

Intuitively speaking, a model is an interpretation of a language L. By lan-

guage, we simply mean the non-logical vocabulary of constant, relation and
D

function symbols. It tells us what the language means.

Thus a model M has three ingredients:
(1) A language L = {a, b, c, ..., P, Q, R, ...., f, g, h};
(2) A domain M of objects - which we can then talk about using the
language.
e

(3) An interpretation of the language such that:

in

• Constant symbols like c are interpreted by some object from the

domain cM ∈ M - this the object which the name denotes.
nl

• Relation symbols like R where the arity of R is n are interpreted

by some set of tuples of objects hm1 , ..., mn i where m1 , ..., mn ∈ M .
O

Thus the interpretation of R in M, abbreviated RM , is a subset

of {hm1 , ..., mn i | m1 , ..., mn ∈ M }.
• Function symbols like f with arity n are interpreted by functions
taking some m1 , ...., mn from M and returning some m ∈ M .
18
 2.1. WHAT IS A MODEL? 19

To get the idea of the interpretation of a relation symbol, consider a one

place relation symbol P . The interpretation of P in M, P M , is simply the set
of objects from the domain M which are in the extension of the P according
to M.
A model M of L = {a, b, c, ..., P, Q, R, ...., f, g, h} is thus something of the form

M = hM, aM , bM , cM , ..., P M , QM , RM , ..., f M , g M , hM i.

R EMARK 29. A tuple is simply a finite list of objects. We represent a tuple of

m1 , ..., mn by hm1 , ..., mn i.

2.1.1. Examples.

E XAMPLE 30. Consider a language L = {a, P, R} consisting of: a constant

symbol a; a one place relation symbol P ; and a two place relation symbol R
c Toby Meadows

(i.e., they have arity 1 and 2 respectively). Let us define a model M for L.

t
• Let the domain M consist of two objects m1 and m2 .
• Let aM (the interpretation of a in M) be the object m1 from the domain
M.
.1 f
v1 ra
• Let P M (the interpretation of the symbol P in M) be the set {m1 }.
• Let RM be the set {hm1 , m1 i, hm1 , m2 i}.
We have given the language an domain and interpretation, so M = hM, P M , RM i.
D

Intuitively speaking, the fact that hm1 , m2 i ∈ RM tells us that m1 bears the
relation RM to m2 . In the next section we are going to show how to use
sentences of the language to express this fact.

R EMARK 31. Note that RM is a set of tuples from the domain, but R is just a
(relation) symbol from the language.
e
in

E XAMPLE 32. Imagine a room full of people: John, Mary, Peter and Dorothy.
We are going to let them from the domain of a model M. Let us have a
language consisting:
nl

• a one place relation B which we shall interpret as the set of boys;

• a one place relation G which we shall interpret as the set of girls;
O

• a two place relation D which is interpreted as all the pairs hm1 , m2 i

(tuples of length 2) such that m1 danced with m2 .
This defines a model.
 2.2. SATISFACTION 20

R EMARK 33. In the example above, I have used B because it starts with the
same letter as the word “boys”, which makes things easier to remember.
However, there is nothing stopping me from defining a different interpreta-
tion (and thus different model) in which I made B denote (be interpreted as)
the set of girls and G denote the set of boys; or let B denote all of the object
in the domain.

E XAMPLE 34. Consider the language of arithmetic

LAr = {0, 1, +, ×}.

0 and 1 are constant symbols and + and × are function symbols. The stan-
dard model of arithmetic consists of a domain N which consists of all of the
natural numbers and interprets:

• the constant symbol 0 as denoting the number zero;

c Toby Meadows

• the constant symbol 1 as denoting 1, the next number;

•
•
t
interprets the function symbol + as addition; and
interprets the function symbol × as denoting multiplication.
.1 f
v1 ra
We shall denote this model as N = hN, 0N , 1N , +N , ×N i.

R EMARK 35. We can think of a model as being something like a possible

world. The domain consists of all of the objects in that possible world and
D

then we interpret the language according to what is true in that world.

However, there are limitations to the analogy. Discussion of possible worlds
tends to be limited to an entire physical reality. Models, however, can be
based on just a few objects from this world. Moreover, the object in a model
might not be concrete: they could be abstract and they might not even need
to exist at all.
e
in

Also, while we can say things about a possible world using a language, pos-
sible worlds are supposed to be, in some sense, independent of the language
we use to describe them; a model is not. The language gives the structure
nl

to the model.
O

2.2. Satisfaction

In this section, our goal is to find a way of connecting the sentences of our
language to a model M of that language L. We want to use our language
 2.2. SATISFACTION 21

to express facts about what is going on the model. Thus we want to know
when some sentence is true in M.
If a sentence ϕ is true in M, we shall say that M satisfies ϕ, we we abbreviate
M |= ϕ.
We shall do this in stages:
(1) we show how to see when atomic sentences are true in M;
(2) we show how to use the simple connectives like ¬ and ∧;
(3) we encounter a problem with the quantifiers; and
(4) we solve that problem and give our final definition of satisfaction.

2.2.1. Atomic satisfaction. Let L = {a, b, c, ..., P, Q, R, ...., f, g, h} be our

general language consisting of constant, relation and function symbols. We
shall, however, ignore the function symbols for the moment.
c Toby Meadows

Let ϕ be an atomic sentence. Then is must be of the form P a1 ...an where P

is a n-ary relation symbol and a1 , ..., an are constant symbols from L. Since
ϕ is a sentence it cannot have any free variables.
Now let
.1 f
t
v1 ra
M = hM, aM , bM , cM , ..., P M , QM , RM , ..., f M , g M , hM i
be a model of L.
We would like to know when the atomic sentence ϕ is true in M; i.e., M |= ϕ.
D

This is quite simple. We shall say that:

• M |= P a1 ...an iff haM M
1 , ..., an i ∈ P
M
.
Intuitively speaking we are saying that P a1 ...an is true in M iff the tuple
haM M M M
1 , ..., an i consisting of the interpretations a1 , ...., an of the constant sym-
bols a1 , ..., an is in the interpretation P M of the relation symbol P .
e

E XAMPLE 36. Consider the language and model from Example 30 and the
in

sentence Raa. We then have:

nl

M |= Raa ⇔ haM , aM i ∈ RM
⇔ hm1 , m1 i ∈ {hm1 , m1 i, hm1 , m2 i}.
O

The first ⇔ is obtained by our atomic satisfaction definition and the second
⇔ is obtained by the definition of the interpretations of a and R in M. Since
the last statement is clearly correct, we see that Raa is indeed true in M.
 2.2. SATISFACTION 22

2.2.2. Simple connectives. Atomic satisfaction is pretty straightforward.

We now want to consider what to do with the connectives ¬, ∧, ∨, →, ↔. To
make things simpler, we’ll just play with ¬ and ∧.
[Link]. Negation (¬). Suppose we have some sentence ϕ ∈ SentL which
is of the form ¬ψ. Then, from last week, we know that ψ is also in SentL .
Taking an (informal) inductive approach, suppose that we already know
whether or not ψ is true in M; i.e., whether M |= ψ. Given this knowledge,
what can we then say about ϕ in M?
Suppose it is the case that M |= ψ. Then clearly ¬ψ cannot be true in M too:
this is just what negation means. Thus M 2 ¬ψ; i.e., M 2 ϕ. On the other
hand suppose we knew that M 2 ψ. Then, it must be the case that M |= ¬ψ;
i.e., M |= ϕ. Again, this is just what negation means: if it is not the case
that ψ is true, then ψ is not true (i.e., ¬ψ is true).
c Toby Meadows

With this in mind, we might then say that if ϕ is of the form ¬ψ then:
• M |= ϕ iff M 2 ψ.
.1 f
t
R EMARK 37. Note that we write M 2 ϕ to mean that it is not the case that
v1 ra
M |= ϕ.

E XAMPLE 38. Using the language and model of Example 30 again, consider
the sentences ¬P a and ¬¬Raa. For ¬P a we have the following:
D

M |= ¬P a ⇔ M 2 P a
⇔ aM ∈
/ PM
⇔ m1 ∈
/ {m1 , m2 }.

The first ⇔ is obtained the clause we just provided for negation; the second
e

⇔ is given by the atomic satisfaction clause; and the final ⇔ is given by the
in

interpretation of the symbols from L in M.

Since the final clause above is clearly false (it is the case that m1 ∈ {m1 , m2 })
we see that it is not the case that M |= ¬P a; (i.e., M 2 ¬P a).
nl

For ¬¬Raa, we have:

O

M |= ¬¬Raa ⇔ M 2 ¬Raa
⇔ M |= Raa.

We established that final clause was true in 36, so we have M |= ¬¬Raa.

 2.2. SATISFACTION 23

[Link]. Conjunction (∧). Now suppose we had a sentence ϕ ∈ SentL which

was of the form ψ ∧ χ (where, of course, ψ, χ ∈ SentL ).
Thinking in an (informally) inductive manner, suppose we already knew
whether or not it was the case that both of M |= ψ and M |= χ are cor-
rect.
Suppose we have M |= ψ and M |= χ. Then conjunction just means that
ψ ∧ χ must also be tree in M; i.e., M |= ψ ∧ χ.
On the other hand, suppose we have either M 2 ψ or M 2 χ. This just
the same as saying that it isn’t the case that both M |= ψ and M |= χ.
Then clearly (since we know what “and” means) it cannot be the case that
M |= ψ ∧ χ; thus we have M 2 ψ ∧ χ.
This suggests that we should say the following about conjunction. If ϕ ∈
SentL is of the form ψ ∧ χ then:
c Toby Meadows

• M |= ϕ iff M |= ψ and M |= χ.
.1 f
tence Raa ∧ P a. We have t
E XAMPLE 39. Returning the model and language of 30, consider the sen-
v1 ra
M |= Raa ∧ P a ⇔ M |= Raa & M |= P a
⇔ haM , aM i ∈ RM & aM ∈ P M
⇔ hm1 , m1 i ∈ {hm1 , m1 i, hm1 , m2 i} & m1 ∈ {m1 , m2 }.
D

Since the final clause is clearly correct, we see that we do have M |= Raa∧P a.

[Link]. Putting it together. Using the usual ways of defining connectives,

we can then define satisfaction using a recursive definition for the connec-
tives (and not the quantifiers).
e

To make things faster, I’m going to write ϕ := ... to mean that ϕ is of the form
in

... .
Suppose ϕ ∈ SentL and that M is a model of L. Then
nl

• if ϕ := Ra1 ...an for R an n-ary relation symbol from R and a1 , ..., an

constant symbols from r, then
O

– M |= ϕ iff haM M M
1 , ..., an i ∈ R ;
• if ϕ := ¬ψ, then
– M |= ϕ iff M 2 ψ;
• if ϕ := ψ ∧ χ, then
 2.2. SATISFACTION 24

– M |= ϕ iff M |= ψ and M |= χ;
• if ϕ := ψ ∨ χ, then
– M |= ϕ iff M |= ψ or M |= χ;
• if ϕ := ψ → χ, then
– if M |= ψ, then M |= χ;
• if ϕ := ψ ↔ χ, then
– M |= ϕ iff (M |= ψ iff M |= χ)

R EMARK 40. Note that in the last clause we needed to resort to brackets.
This is one of the drawbacks of using the natural language, English, as the
language of the metatheory.

2.2.3. A problem for quantifiers. Observe that the definition above says
nothing about what we should do when we encounter a sentence ϕ ∈ SentL
c Toby Meadows

which involves quantification.

correct?
.1 f
t
E XAMPLE 41. Using Example 30 again, consider the sentence ∃x¬P x. Is this
v1 ra
To make things clearer we might represent the interpretation of R using a
table as follows (read anti-clockwise):
PM
m1 1
D

m2 0
A 1 in the box for m1 represents the fact that m1 ∈ P M ; and a 0 in the box for
/ P M.
m2 represents the fact that m2 ∈
Now, intuitively speaking, ∃x¬P x says (of the model M) that there is some
object x such that it is not the case that x in P M . This is clearly true: m2
e

/ P M.
suffices since m2 ∈
in

[Link]. The problem. However, the rules we gave in the previous section
nl

don’t tell us how to do this. They only say what to do when we are given a
sentence composed from atomic sentences using ¬, ∧, ∨, → and ↔.
O

So clearly we need to say more about how the satisfaction relation works.
We need to say how it deals with sentences involving quantifiers.
But there is a further problem. We’ll try to extend our characterisation of
satisfaction in an obvious way and the problem will emerge.
 2.2. SATISFACTION 25

Let’s consider our sentence ∃x¬P x again. We want to be able to say some-
thing like this.

/ P M.
• M |= ∃x¬P x iff there is some object m ∈ M such that m ∈

We can see that the latter part is true and thus that ∃x¬P x is true in M.
But to do this we’ve had to make a lot of steps at once. In the case of
the connectives we were, so to speak, able to unravel one connective at a
time as we worked our way to facts about the model itself. However, here
we’ve jumped from a complex sentence involving quantification straight to
the model.
While we can see how this works with a relatively simple sentence like
∃x¬P x, it would be much more difficult with a sentence like:
c Toby Meadows

∀y(Ray → ∃x∀z(P z → (Rxz ∧ Rxy))).

.1 f
t
We want some way of unraveling a sentence one step at a time. The obvious
thing to do is to consider how the sentence was built up from formulae
v1 ra
of lower complexity. Thus, as we saw in the previous week, ∃x¬P x was
constructed in the third stage.

• P x is atomic and thus there at the beginning.

D

• ¬P x is constructed by applying ¬ to P x and thus gets into the next

stage.
• And ∃x¬P x gets is constructed by applying ∃x to ¬P x and thus gets
into the stage after that.

If we follow the pattern of construction of a sentence from the subformulae

e

which are used to construct it, then we’ll have the sort of thing we want.
in

Indeed this is how the definition works for the connectives. For example, we
figure out whether M |= ψ ∧ χ by checking whether the sentences ψ and χ
nl

are true in M.
But here’s the problem: if we take pull a quantifier off a sentence, we (may)
O

end up with a formula with a free variable. For example, if we take the ∃x
from the front of ∃x¬P x, we end up up with ¬P x. This has one free variable
(i.e., x) and thus it is not a sentence.
Our characterisation of satisfaction only works for sentences.
 2.2. SATISFACTION 26

This might help illustrate the problem. Say we try to make a rule that
unravels sentences of the form ∃xψ(x). We might say something like, if ϕ :=
∃xψ(x) then

• M |= ϕ iff if [SOME CONDITION HOLDS], then M |= ψ(x).

For the moment, don’t worry about what the condition is, the problem is the
statement M |= ψ(x). What could it mean to say that M |= ¬P x? Intuitively,
we are supposed to say something like ¬P x is true in M. But x is just a
variable, it doesn’t denote anything in the domain. It’s meaningless to say
that ¬P x is true in M.

2.2.4. Our solution and final satisfaction definition. There are a num-
ber of ways of getting around this. We’ll consider a simple technique for
solving the problem and then make some remarks about other approaches
c Toby Meadows

which are common in the literature. However, there is a sense in which they
all come down to much the same thing in the end.
.1 f
t
[Link]. Something that doesn’t work but points the way to a solution.
So our problem is that we don’t have a way of talking about the truth of
v1 ra
a formula and this makes it difficult to unravel a complex sentence into
simpler parts so that we can figure out whether or not it is true.
So let’s not try to give satisfaction conditions for formulae, let’s stick with
D

sentences. So if we have a sentence of the form ∃xϕ(x) we might consider

what would happen if we substituted constant symbols from L in for x. An
example might help here:

E XAMPLE 42. Let M for a language L = {a, b, P } be such that :

• the domain M = {m1 , m2 };

e

• aM = m1 , bM = m2 ; and
in

• P M = {m1 }.

This clearly suffices for the definition of a model.

nl

Now suppose we want to know whether or not M |= ∃xP x. To ascertain

whether or not this the case, we might ask whether there is some constant
O

symbol c from L such that M |= P c.

Clearly, we have M |= P a since

aM = m1 ∈ {m1 } = P M .
 2.2. SATISFACTION 27

Thus we can see that M |= ∃xP x.

We might then be tempted to generalise this and make the following attempt
at a rule. If ϕ is of the form ∃xψ(x) then
• M |= ϕ iff for every constant symbol c from L we have M |= ψ(c 7→ x)
where ψ(c 7→ x) means that c has been substituted for x in all of the places
where x was free in ψ.
However, it is easy to see that this approach merely gives us a sufficient
condition for M |= ∃xψ. If there is such a constant symbol, then it clearly
works. However, there may be situation where we do not have enough con-
stant symbols in the language (perhaps we even have none). An example
may illustrate this:

E XAMPLE 43. Let’s use the model and language from Example 30 and con-
c Toby Meadows

sider the sentence ∃x¬P x. Then using the proposed quantifier clause we
get:

t
M |= ∃x¬P x ⇔ there is some cons-sym c such that M |= ¬P c
.1 f
v1 ra
⇔ there is some cons-sym c such that M 2 P c
⇔ there is some cons-sym c such that cM ∈
/ P M.

However since a is the only constant symbol in L and aM ∈ P M , the last

D

clause is false; and thus, we are told that M 2 ∃x¬P x, which, as we know
from Example 41, is not correct.

So this doesn’t work, since we might not have enough constant symbols
available.
[Link]. Our solution. But this points the way to an obvious fix. We are
e

going to add more constant symbols to the language.

in

Given some model M, we need a collection of new constant symbols which

provide a name for every object from the domain M .
nl

What should we use for those constant symbols? Simple! We’ll just use the
objects m ∈ M themselves.
O

Given a language L and model M, we denote the expansion of L with the

new constant symbols by L(M ). We can then define W F FL(M ) and SentL(M )
in the same way we did last week.
Observe that W F FL ⊆ W F FL(M ) and SentL ⊆ SentL(M ) .
 2.2. SATISFACTION 28

R EMARK 44. Observe that this is a strange kind of language. Suppose we

had started with a model M for a language consisting just one predicate
P and a domain with a single object, me; i.e., M = {Toby}. Then I am a
constant symbol in the language L(M ) and P “applied to” me is a sentence
of L(M ). This may cause some philosophical concern, but we’ll leave it alone.
If it does bother you, we can add a set of new constant symbols for all of the
objects in the domain M and use them instead. The result is much the
same, but more tiresome to wield.

With this in hand we can now describe how the satisfaction predicate works
for sentences ϕ ∈ SentL(M ) of the expanded language.
To make this work, we also need to expand the model M in order that it is a
model of the expanded language L(M ). To do this we simply let mM = m for
all m ∈ M . We shall denote the resultant model by M+ .
c Toby Meadows

Thus given a model M, language L(M ) and sentence ϕ ∈ SentL(M ) we say

that if ϕ is of the form ∃xψ(x), then
.1 f
t
• M+ |= ϕ iff there is some m ∈ M such that M+ |= ψ(m 7→ x).
v1 ra
Since m is a constant symbol in L(M ) and M+ is a model of L(M ), it makes
perfect sense to say M+ |= ψ(m 7→ x).
Universal quantification can be similarly characterised.
D

So putting it all together, we now have the means of telling whether a sen-
tence ϕ ∈ SentL(M ) is true in M+ . But what we really want is a way of telling
whether or not a sentence ϕ ∈ SentL is true in our original model M.
We first observe that:

F ACT 45. if ϕ ∈ SentL , then ϕ ∈ SentL(M ) .

e

This tells us that sentence from L are also sentences in L(M ), so it makes
in

sense to say M+ |= ϕ for ϕ ∈ SentL . Moreover, we can just use M+ .

nl

D EFINITION 46. Given a language L, M a model of L and ϕ ∈ SentL

• M |= ϕ iff M+ |= ϕ.
O

This is what we wanted!

R EMARK 47. Strictly, we also need another clause which says that nothing
else is true in M.
 2.3. IMPORTANT SEMANTIC PROPERTIES 29

[Link]. = and ⊥. = is a two place relation which says that the object rep-
resented by the first constant symbol is identical to the object represented
by the second constant symbol.
⊥ is a 0-place relation symbol which is false in every model.
See Exercise 53

2.3. Important Semantic Properties

In this final section, we are going to use models and our satisfaction relation
to define some interesting properties that a sentence might have.

D EFINITION 48. ϕ is satisfiable if there is some model M in the language L

of ϕ such that M |= ϕ.

D EFINITION 49. ϕ is valid (or a logical truth), abbreviated |= ϕ, if for every

c Toby Meadows

model M in the language L of ϕ we have M |= ϕ.

.1 f
t
Intuitively speaking, ϕ is satisfiable if there is some way (i.e., a model) of
making ϕ true. Similarly ϕ is valid if there is no way of making it false.
v1 ra
R EMARK 50. Note that we use the symbol, |=, for both validity and satisfac-
tion. This practice is called overloading. Context should always settle any
confusion.
D

Let us write Γ, ∆ for sets of sentences in some language L; i.e., such that
Γ, ∆ ⊆ SentL .

D EFINITION 51. Given Γ ⊆ SentL and ϕ ∈ SentL , we say that ϕ is a conse-

quence of Γ, abbreviated Γ |= ϕ, if for every model M of L if we have M |= γ
for ever γ ∈ Γ, then M |= ϕ.
e

Intuitively, if ϕ is a consequence of Γ we are saying that every way of making

in

all of Γ true is a way which also makes ϕ true. Thus, we might say that Γ
implies ϕ.
nl
O
 EXERCISES WEEK 2 30

Exercises Week 2

E XERCISE 52. Provide the clause defining the behaviour of sentences of the
form ∀xψ(x) ∈ SentL(M ) for some model M and language L.

E XERCISE 53. Provide the |= clauses for = and ⊥.

E XERCISE 54. Write out the full definition of |=.

E XERCISE 55. Let L ={a, P, R} be the language where a is a constant symbol

and P and R are relation symbols with arity 1 and 2 respectively. Let M be
a model of L such that:
• M = {m1 , m2 };
• aM = m2 ;
• P M = {m1 }; and
c Toby Meadows

• RM = {hm1 , m1 i, hm2 , m2 i}.

Using the satisfaction definition (|=) work out whether or not the following
are correct:
(1) M |= P a;
.1 f
t
v1 ra
(2) M |= Raa ∨ ¬P a;
(3) M 2 ¬¬Ra;
(4) M |= P m2 ;
D

(5) M+ |= P m2 m1 ;
(6) M |= ∀x(P x ∨ ¬P x);
(7) M |= ∀xRxx; and
(8) M |= ∀x∃y(Rxy ∧ P y).

E XERCISE 56. Consider the language L from the exercise above and the do-
e

main M = {m1 , m2 }. We can construct a different model of L be interpreting

the nonlogical vocabulary differently. How may different models of L can
in

you make on the domain M .

Given a model M whose domain has n many objects in it, which we shall
nl

write |M| = n and say that the cardinality of M is n. Suppose the language
consists of one m-place relation symbol R, how many different interpreta-
O

tions (and thus models) are there for such a relation over M?

E XERCISE 57. In Remark 47, we note that a closing off clause is required.
What could happen if we didn’t add one of these.
 EXERCISES WEEK 2 31

E XERCISE 58. Consider the standard model of arithmetic N in the language

L = {0, P rime, 1, +, ×} from Example 34 with an expansion consisting of a
new one-place relation symbol, P rime, which is true of a number iff it is
prime. Allowing the “internal” notation for arithmetic functions, verify, if
you can, whether the following are correct:
(1) N |= ¬(1 + 0 = 1);
(2) N |= ∃x(x = 1 + 1);
(3) N |= 1 + 1 = 2;
(4) N |= ∀x(x = 0 → ¬x = 1);
(5) N |= ∀x∀y(x × y = y × x);
(6) N |= ∀x(P rime(x) → ∃y(y × (1 + 1) = x)); and
(7) N |= ∀x(∃y(y × (1 + 1) = x) → ∃y∃z(P rime(y) ∧ P rime(z) ∧ x = z + y)).
If you cannot verify it, explain why not.
c Toby Meadows

E XERCISE 59. Let M = {m1 , m2 } be a domain consisting of two objects m1 and

symbol. Now consider the following sentences:

.1 f
t
m2 . Consider the language L = {R} consisting of a single two place relation
v1 ra
(1) ∃xRxx;
(2) ∃xRxx ∧ ∃y¬Ryy; and
(3) ∀xRxx.
For each of these sentences write out the set of models over M such that
D

that sentence is true there; i.e., for each sentence (1.)-(3.), define all of the
interpretations of R such that that sentence would be true. What differences
do you note? Consider the following questions:
• Is there more than one model?
• If there is more than one model, could we add another sentence such
e

that we can pin down only one model?

in

E XERCISE 60. Verify Fact 45. [Hint: prove this by induction on the stage
construction of formulae before considering sentences.]
nl

E XERCISE 61. Define satisfiable in terms of validity; i.e., give a simple defi-
nition of what it means for a formula to be satisfiable using the concept of
O

validity.

E XERCISE 62. Consider the following properties a sentence ϕ ∈ SentL and set
of sentence Γ ⊆ SentL might have:
 EXERCISES WEEK 2 32

(1) There is no model M such that M |= γ for all γ ∈ Γ and M 2 ϕ.

(2) If for all models M, M |= γ for all γ ∈ Γ, then for all models M,
M |= ϕ.
Which of these, if any, is equivalent to saying Γ |= ϕ.

E XERCISE 63. Let M be a model of some language L. Show that for any
sentence ϕ from L that:
M |= ϕ ⇔ M 2 ¬ϕ.
This, in effect, says that every sentence is either true or false in M but not
both. [Hint: Prove this by induction on the complexity of formulae in the
expanded language.]
c Toby Meadows

.1 f
t
v1 ra
inDe
nl
O
 CHAPTER 3

Proof Systems

Goals:
(1) To review tableau proof systems.
(2) Review natural deduction proof system.
This is mainly a review week. We’ll move over this material quickly. It is
expected that you already know how to use these systems.
Our goal this week is to explore two proof systems. In each system we want
c Toby Meadows

to be able to show whether:

• some ϕ ∈ SentL is a theorem; or
.1 f
t
• ϕ may be derived from some (finite) Γ ⊆ SentL .
It turns out that the most convenient way of conduction these proofs re-
v1 ra
quires an infinite supply of constant symbols C (sometimes known as pa-
rameters). As in the previous week, we shall denote the expanded language
by L(C).
D

3.1. Tableau

3.1.1. Starting conditions. To establish whether ϕ is a theorem, we

commence a tableau by placing ¬ϕ at the top node of the tableau.
To establish whether ϕ may be derived from some (finite) Γ ⊆ SentL , we
e

commence the tableau by placing each of the sentence γ ∈ Γ followed by ¬ϕ

at the top of the tableau.
in

3.1.2. Rules. The following tableau rules should be familiar.

nl

ϕ ∧ ψ (∧) ¬(ϕ ∧ ψ) (¬∧) ¬(ϕ ∨ ψ) (∨) ϕ ∨ ψ (¬∨) ¬(ϕ → ψ) (→) ϕ → ψ (¬ →)

H
 H H
O

ϕ ¬ϕ ¬ψ ¬ϕ ϕ ψ ϕ ¬ϕ ψ
ψ ¬ψ ¬ψ

33
 3.1. TABLEAU 34

¬¬ϕ (¬¬)

¬∀xϕ(x) (∀) ∀xϕ(x) (¬∀) ∃xϕ(x) (∃) ¬∃xϕ(x) (¬∃)

¬ϕ(a) ϕ(t) ϕ(a) ¬ϕ(t)

3.1.3. Closure conditions. A branch B is a tableau is deemed to be

closed if for some sentence ϕ ∈ L(C) both ϕ and ¬ϕ occur on B. If every
c Toby Meadows

branch of a tableau closes, then the tableau is closed.

t
If the tableau for ¬ϕ closes, then we have a proof of ϕ, abbreviated `T ab ϕ.
We shall omit the T ab where no confusion can arise.
.1 f
v1 ra
If the tableau commencing with Γ, ¬ϕ closes, then we have derived ϕ from Γ,
which we abbreviate Γ `T ab ϕ.
D

3.1.4. Examples.

E XAMPLE 64. ` ∀xP x → ¬∃x¬P x

¬(∀xP x → ¬∃x¬P x)
e

∀xP x \a
in

¬¬∃x¬P x
nl

∃x¬P x × a

¬P a
O

Pa

E XAMPLE 65. ` ¬∃x¬P x → ∀xP x

 3.1. TABLEAU 35

¬(¬∃x¬P x → ∀xP x)

¬∃x¬P x \a
¬∀xP x × a

¬P a

¬¬P a
c Toby Meadows

E XAMPLE 66. ∀xP x ∨ ∀xQx ` ∀x(P x ∨ Qx)

.1 f
t
v1 ra

∀xP x ∨ ∀xQx
¬∀x(P x ∨ Qx) × a
D

¬(P a ∨ Qa)

¬P a
¬Qa
H
 HH
∀xP x \a ∀xQx \a
e
in

Pa Qa
nl
O

E XAMPLE 67. ∀x∀y∀z((Rxy ∧ Ryz) → Rxz), ∀x∃yRxy, ∀x∀y(Rxy → Ryz) ` ∀xRxx

 3.1. TABLEAU 36

∀x∀y∀z((Rxy ∧ Ryz) → Rxz) \a

∀x∃yRxy \a
∀x∀y(Rxy → Ryx) \a
¬∀xRxx × a

¬Raa

∃yRay × b

Rab

∀y(Ray → Rya) \b

Rab → Rba
HH

c Toby Meadows

H
  HH
¬Rab Rba
.1 f
t
∀y∀z((Ray ∧ Ryz) → Raz) \b
∀z((Rab ∧ Rbz) → Raz \a
v1 ra
(Rab ∧ Rba) → Raa)
HH
 H
¬(Rab ∧ Rba) Raa
D

HH
¬Rab ¬Rba
e
in
nl

3.1.5. Counterexamples.
O

E XAMPLE 68. ∀x(P x ∨ Qx) 0 ∀xP x ∨ ∀xQx

 3.1. TABLEAU 37

∀x(P x ∨ Qx){}a, b
¬(∀xP x ∨ ∀xQx)

¬∀xP x × a
¬∀xQx × b

¬P a

¬Qb

P a ∨ Qa

P b ∨ Qb
HH
Pa Qa
c Toby Meadows

H
 H
P b Qb
.1 f
t
We have applied all the rules we needed to, but there is still an open branch.
Thus there is no derivation of ∀xP x ∨ ∀xQx from ∀x(P x ∨ Qx).
v1 ra

We now use the open branch to construct a model which witnesses a coun-
terexample to the derivation; i.e., a model in which all of the premises are
D

true but the conclusion is false.

We let M = hM, P M , QM i be as follows:

• M is the set of terms occurring on the open branch (i.e., {a, b});
e

• P M is the set of terms t that occur in sentences of the form P t that

in

occur on the open branch (i.e., {b});

• QM is the set of terms t that occur in sentences of the form Qt that
occur on the open branch (i.e., {a}).
nl
O

Now it should be clear that we have M |= ∀x(P x ∨ Qx) but M 2 ∀xP x ∨ ∀xQx.

E XAMPLE 69. 0 ∀x∃yRxy

 3.2. NATURAL DEDUCTION 38

¬∃x∀yRxy{}a, b

¬∀yRay × b

¬Rab

¬∀yRby × c

Rbc
Now it should be clear that this tableau is going to go on forever. This clearly
means that the branch (there’s only one) will remain open. But how do we
describe a model which makes ∀x∃yRxy false.
In this case, we can think up a model which will do the trick without using
the branch. Let M = hM, RM i be such that:
c Toby Meadows

• M = {a}; and
• RM = {} (i.e., nothing is related by R.

Now you should be able to see that M |= ∀x∃yRxy.

.1 f
t
v1 ra
3.2. Natural Deduction

3.2.1. Rules. Again, these rules should be familiar from the course on
philosophical logic.
D

ϕ ψ ϕ∧ψ ϕ∧ψ
(∧-I) ϕ (∧-E) (∧-E)
ϕ∧ψ ψ

ϕ ψ (ϕ) (ψ)
(∨-I) (∨-I) ϕ∨ψ χ χ
ϕ∨ψ ϕ∨ψ (∨-E)
χ
e

(ϕ)
in

ϕ ϕ→ψ
ψ (→-E)
(→-I) ψ
ϕ→ψ
nl

(ϕ) ¬ϕ ϕ ¬¬ϕ
⊥ (¬-E) ϕ (DN)
⊥
¬ϕ (¬-I)
O
 3.2. NATURAL DEDUCTION 39

ϕ(a) ∀xϕ(x)
(∀-I) (∀-E)
∀xϕ(x) ϕ(t)

ϕ(a)
ϕ(t)
(∃-I) ∃xϕ(x) ψ
∃xϕ(x) (∃-E)
ψ

(∀-I) Provided a is not free in ∀xϕ(x) nor in any assumption occurring at or

above ϕ(a). (∃-E) Provided that a is not free in any assumption in the right
branch nor in ∃xϕ(x) nor ψ.

3.2.2. Derivations and theorems.

D EFINITION 70. We say that ϕ can be derived from assumptions in Γ, abbre-

c Toby Meadows

viated Γ `N at ϕ, when there is natural deduction proof with ϕ on the final line
and whose assumptions are all members of Γ. We say that ϕ is a theorem if
.1 f
t
`N at ϕ: i.e., ϕ can be derived without any assumptions.

I’m going to use a slightly slicker approach to writing up natural deduction

v1 ra
proofs. I’ll give you a simple example which I’ll write up in the style you’ve
already learned.
D

3.2.3. Examples.

E XAMPLE 71. P a → Qa ` ¬Qa → ¬P a

P a(1) P a → Qa
Qa ¬Qa(2)
⊥ (1)
e

¬P a (2)
¬Qa → ¬P a
in

We can write out the same derivation in the old notation as follows:
1 (1) P a → Qa Premise
nl

2 (2)P a Assumption
1,2 (3) Qa →-E (1, 2)
O

4 (4) ¬Qa Assumption

1,2,4 (5) ⊥ ⊥-I (3,4)
1,4 (6) ¬P a ¬-I (5,2)
1 (7) ¬Qa → ¬P a →-I (6,4)
 3.3. INTERESTING PROPERTIES 40

The only difference is that the book-keeping is a little lighter and hopefully,
you’ll see that it’s a lot easier to see what’s going on.

3.3. Interesting Properties

D EFINITION 72. (Natural deduction) A set Γ of sentences is consistent if there

is no way to derive ⊥ from Γ; i.e., Γ 0 ⊥. (Tableau) A set Γ is consistent if for
every tableau commencing with a (finite) subset of Γ remains open.

T HEOREM 73. (The deduction theorem) Γ ∪ {ϕ} ` ψ iff Γ ` ϕ → ψ.

P ROOF. For the tableau systems both proofs start with almost exactly the
same set up. We leave this as an exercise.
Let’s consider the natural deduction system. Suppose that we have a deriva-
tion of Γ ∪ {ϕ} ` ψ. Then clearly we may add another line to the derivation,
c Toby Meadows

which employs →-I and thus gives us Γ ` ϕ → ψ.

On the other hand, suppose we have a derivation of Γ ` ϕ → ψ. Then
.1 f
t
suppose we add a new line to that derivation, which employs →-E and the
added assumption ϕ. Then we clearly end up with a derivation of ψ from
v1 ra
Γ ∪ {ϕ}. 

R EMARK 74. In other proof systems, the deduction theorem can be quite
painful to prove.
D

T HEOREM 75. (Cut/Lemma - Natural deduction only) Suppose Γ ` ϕ and Γ ∪

{ϕ} ` ψ. Then Γ ` ψ.

P ROOF. Suppose we have Γ ` ϕ and Γ ∪ {ϕ} ` ψ. Then by the deduc-

tion theorem (Theorem 73) we have Γ ` ϕ → ψ. Thus we may combine the
derivations of ϕ and ϕ → ψ from Γ to get a derivation of ψ from Γ using
e

→-E. 
in

T HEOREM 76. (Monotonicity) Suppose Γ ` ϕ and ∆ ⊇ Γ, then ∆ ` ϕ.

nl
O
 EXERCISES WEEK 3 41

Exercises Week 3

E XERCISE 77. Describe tableau rules and natural deduction rules for iden-
tity =.

E XERCISE 78. Complete the following derivations, if possible, in both the

tableau system and the natural deduction system. You may want to use
the cut lemma or some derive some new rules. If it is not correct provide a
counterexample:

(1) P a → (Qa → Rc) a` (P a ∧ Qa) → Rc;

(2) P a → Qb a` ¬Qb → ¬P a;
(3) Qb ` P a → Qb;
(4) ¬P a ` P a → Qb;
(5) ¬(P a → Qb) a` P a ∧ ¬Qb;
c Toby Meadows

(6) P a → Qb a` ¬P a ∨ Qb;
(7) ` P a ∨ ¬P a;
(8)
(9)
¬P a ∧ ¬Qb a` ¬(P a ∨ Qb);
.1 f
¬P a ∨ ¬Qb a` ¬(P a ∧ Qb); t
v1 ra
(10) ∀x(P x ∧ Qx) a` ∀xQx ∧ ∀xP x;
(11) ∀x(P x → Qx), ∀x(Qx → Rx), P a ` Ra;
(12) P a ∧ (Qb ∨ Rc) a` (P a ∧ Qb) ∨ (P a ∧ Rc);
(13) P a ∨ (Qb ∧ Rc) a` (P a ∨ Qb) ∧ (P a ∨ Rc);
D

(14) ∀x(P x → Qa) a` ∃xP x → Qa;

(15) ∃x(P x → Qa) a` ∀xP x → Qa;
(16) ∀x(Qa → P x) a` Qa → ∀xP x;
(17) ∃x(Qa → P x) a` Qa → ∃xP x;
(18) ∀x∀y(Rxy → ¬Rxy) ` ∀x¬Rxx;
e

(19) ∀x∀z(∃y(Rxy ∧ Ryz) → Rxz), ∀x∀y(Rxy → Ryx) ` ∀x∀y(Rxy → Rxx);

in

(20) ∀x∀z∀y((Rxy ∧ Ryz) → Rxz), ∀x∀y(Rxy → Ryx) ` ∀xRxx.

(a` means demonstrate both directions.)

nl

E XERCISE 79. If we could derive ϕ ∧ ¬ϕ from Γ, is Γ consistent? Show that

ϕ ∧ ¬ϕ ` ψ for any sentences ϕ, ψ. Show that ⊥ ` ψ for all sentences ψ. Why
O

would this be a bad situation? [Perhaps Γ is a theory which we hold to be

true. How useful would it be?]

E XERCISE 80. Prove Theorem 73 and Theorem 76 for the tableau case.
 EXERCISES WEEK 3 42

E XERCISE 81. Consider the set Γ of sentences consisting of:

• ∀x∀y∀z(Rxy ∧ Ryz → Rxz)
• ∀x∀y(Rxy → ¬Ryx)
• ∀x∃yRxy
Is this set of sentences consistent? Describe a model for it. Can you find a
finite model? Why/Why not?

E XERCISE 82. Can you prove Theorem 75 for the tableau case? What goes
wrong?
c Toby Meadows

.1 f
t
v1 ra
in D
e
nl
O
 CHAPTER 4

Completeness 1

Goals:
• Prove the soundness of the tableau proof system.
• Prove the completeness of the tableau proof system.
Our goal is to demonstrate the following theorem.
1
T HEOREM 83. `T ab ϕ iff |= ϕ.
c Toby Meadows

The (→) direction is known as soundness; and the (←) direction is known as
completeness. .1 f
t
To keep things simple, we shall not worry (this week) about consequences
and derivations. The theorem is thus often known as weak completeness,
v1 ra
since we have not involved a set Γ of sentences.
We shall also avoid the use of function symbols.

4.1. Completeness
D

4.1.1. The Strategy. Our goal is to show that if |= ϕ, then ` ϕ. Or in

other words, if every model M (of the language of ϕ) is such that M |= ϕ,
then the tableau commencing with ¬ϕ is closed.
It’s hard to know how to start here though. How could we take the fact that
very model makes ϕ true, to showing that there is a proof of ϕ. Perhaps we
e

can re-articulate the question in a way that is more tractable.

in

For example, we already know that:

nl

F ACT 84. (Contraposition) ϕ → ψ iff ¬ψ → ¬ϕ.

Thus, we may voice the completeness problem as follows:

O

• If 0 ϕ, then 2 ϕ
or in other words,
1
For convenience, I’ll stop using the T ab for the remainder of this week’s notes.
43
 4.1. COMPLETENESS 44

• if the tableau commencing with ¬ϕ does not close (i.e., it has at least
one open branch), then there is some M such that M |= ¬ϕ.

This kind of thing should be more familiar. We have seen examples of how
to take an open branch of a tableau and define a model from it: this is how
we constructed counterexamples.
Of course, this only worked in finite cases. Our goal in this section will be
to generalise this technique to the case of infinite branches.
[Link]. Overview. At a high level, we are taking the fact that there is no
proof of ϕ and using that fact to make a set of sentences which describes a
model in which ¬ϕ is true.
Our strategy can be described as follows:

(1) Find a special set of sentences B to describe the model (this is the
c Toby Meadows

open branch);
(2) Define a model MB using the special set; and
.1 f
t
(3) Show that ¬ϕ is indeed true in MB .

This will clearly suffice to establish our completeness theorem.

v1 ra
We shall use the same strategy again next week when the proof will be more
difficult. However, this provides a good template for seeing what is going on.
D

4.1.2. The Proof. We shall proceed, first, in the language without the
identity relation =.
[Link]. The special set. We start with the fact that 0 ϕ. This means that
the tableau commencing with ¬ϕ does not close. Thus there is at least one
open branch in the tableau. Pick one and call it B.
Our special set is the collection of sentences occurring on B.
e

[Link]. Defining the model. To define a model, we are going to need need:
in

• a language;
• a domain; and
nl

• an interpretation.
O

The language L of the model will be L(C), which is the language from which
ϕ came (i.e., L) augmented with the constant symbols c required for the
construction of the tableau.
We then define our model MB as follows:
 4.1. COMPLETENESS 45

• Let the domain M B be the set of constant symbols occurring in sen-

tences on B.
B
• For each n-ary relation symbol R from L(C), let RM (the interpreta-
tion of R in MB ) be the set of n-tuples ha1 , ..., an i of constant symbols
such that the sentence Ra1 , ..., an occurs on B.
B
• For each constant symbol a from L(C), let aM be a; i.e., itself.

These are all the ingredients require for a model, so the job of defining one
is complete. The remaining job is to demonstrate that it does what we want.

R EMARK 85. Note that we have used the constant symbols themselves to
form the domain. The symbols are objects too, so there is nothing wrong
with doing this.

[Link]. Showing that MB |= ¬ϕ. Up to here, everything has been quite

c Toby Meadows

straightforward. Establishing this fact, is a little more tricky.

.1 f
t
First, we note that, intuitively speaking, we ought to think that this is
right. We’ve been constructing finite counterexamples models using this
v1 ra
technique, and this is just a simple generalisation of that approach. There
are a couple of things to say here. First, just because it worked in the fi-
nite case, doesn’t necessarily mean it will work with infinite branches. We
need to establish this. Second, when we used the counterexample construc-
D

tion technique for tableau, we noted that it worked in specific cases, but we
didn’t really prove that it worked. That is what we’re going to do now.
So our goal is to show that ¬ϕ is true in MB . It’s hard to know how we’d get
straight to such a fact. However, our construction of MB leads to a fact and
a reasonable hypothesis:
e

• FACT: If an atomic sentence or its negation is on B, then that sen-

in

tence will be true in MB . We shall check this again later, but you
should see that this is just what we’ve ensured by our definition of
nl

the model MB .
• HYPOTHESIS: Perhaps all of the sentences on B are true in MB .
O

We might suppose that the hypothesis is correct given the way that the rules
for the construction of a tableau work. Thus we might propose the following:

L EMMA 86. If ψ is on B, then MB |= ψ.

 4.1. COMPLETENESS 46

Clearly, if Lemma 86 is correct, we would have established that MB |= ¬ϕ,

since ¬ϕ is on B.

This is what we shall demonstrate.

Now this is a universal claim: we are showing that

• every ψ is a member of the set of sentences A.

where A is the set of ψ such that if ψ is on B, then MB |= ψ.

From Week 1, we know a technique that might be useful for establishing

such a claim: induction.

Moreover, the way in which the tableau is constructed might hint at a kind
of inductive flavour.
c Toby Meadows

So we might return to our recursive construction of the well-formed formu-

lae W F F . Perhaps we can show that if all the sentences constructed by
.1 f
t
stage n in the construction of W F F are in A, then all the sentences con-
structed at stage n + 1 are also in A. From here we could then employ the
v1 ra
principle of induction and establish that every ψ ∈ W F F is also in A. This
would establish the lemma.

However, there is a problem. The usual way of building up the well-formed

D

formulae in stages (as we did in Week 1) does not work. In the remainder of
this subsection, I will:

(1) show our usual construction does not work;

(2) develop a new stage-based construction of the well-formed formulae;
and
e

(3) complete the proof of the lemma on the basis of the alternative con-
in

struction.

You may prefer to skip (1.) on a first reading.

nl

So suppose we try to use the stage construction from Week 1. Here then is
how the proof might go:
O

P ROOF. (ABORTIVE) We proceed by induction on the stages of construc-

tion of well-formed formulae.
 4.1. COMPLETENESS 47

(Base) If ψ is atomic and on B, then ψ is of the form Ra1 , ..., an for some n-ary
relation symbol R and constant symbols a1 , ..., an . Then we have
B B B
Ra1 ...an is on B ⇔ haM M
1 , ..., an i ∈ R
M

⇔ MB |= Ra1 ...an

The first ⇔ follows from the definition of MB ; and the second, from the
definition of |=.

R EMARK . So clearly the atomic case works. Let’s try the induction step.

(Induction Step) Suppose that for all sentences χ of complexity ≤ n we have

established that:
• if χ is on B, then MB |= χ.
This is our induction hypothesis.
c Toby Meadows

We show that the same is true for sentences ψ of complexity n + 1. Tho do

formulae of complexity ≤ n.
.1 f
t
this we consider all of the forms of formulae that could be constructed from
v1 ra
Suppose ψ := χ ∧ δ is on B where χ and δ have complexity ≤ n. Then by the
rules for construction of tableau, both χ and δ occur on B. By our induction
hypothesis, we see that MB |= χ and MB |= δ; and thus by the definition of
|=, we get MB |= χ ∧ δ.
D

R EMARK . Thus the induction step works for conjunction. Perhaps unsur-
prisingly, the problem crops up with negation.

Suppose ψ := ¬χ is on B where χ has complexity ≤ n. Since B is an open

branch we see that χ is not on B ... 
e

But then what? We cannot make use of the induction hypothesis: it only
in

gives us facts about MB given sentences are on MB ; it doesn’t say anything

about what to do when some χ is not on B. So we are stuck.
nl

Fortunately there is a way around things. To get the idea, we might look to
how the case for conjunction worked:
O

(1) We used the tableau rules to observe that less complex sentences
where already on B; and
(2) From there we employed the induction hypothesis and the satisfac-
tion definition.
 4.1. COMPLETENESS 48

We were held up because we couldn’t get to another fact about what was
already on B.
We then observe that:

• use of the tableau always takes from facts about what is on B to less
complex things on B; and
• every sentence ψ has the form of the top sentences in one of the
tableau rules.

The first of these suggests that if we only considered sentences of the form
given in tableau rules, our induction would not get stuck. The second sug-
gests that we may be able to define all of the well-formed formulae using
just the forms given in tableau rules. It turns out that this is correct.
We now provide an alternative stage-by-stage construction of W F F and then
c Toby Meadows

show that the kind of complexity it gives, will get us through the proof of
Lemma 86. .1 f
t
Let us define our stages as follows:
ra
• StageW F F + (0) is the set of formulae of the form Rt1 , ...tn or ¬Rt1 , ..., tn
where R is an n-ary relation symbol and t1 , ..., tn are terms of the
language (these formulae are sometimes know as literals);
• StageW F F + (n + 1) is the set of formulae
D

– ψ such that ψ ∈ StageW F F + (n);

– of the form ϕ ∧ ψ, ϕ ∨ ψ, ¬¬ϕ, ∀xϕ(x) or ∃xψ(x) where ϕ, ψ ∈
v1

SentW F F + (n);
– ¬(ϕ ∧ χ), ¬(ϕ ∨ ψ), ¬∀ϕ(x) or ¬∃xϕ(x) where ¬ϕ and ¬ψ are in
SentW F F + (n); and
– ¬(ϕ → ψ), ψ → ϕ where ϕ and ¬ψ are in SentW F F + (n).
e
in

We shall then say that the +-complexity of some ϕ is the least n such that
ϕ ∈ StageW F F + (n).
nl

R EMARK 87. Observe that in the first condition in the induction step, each
formula is of the form of the top formulae in a tableau rule. This is where
O

I took them from. You should figure out which rules give rise to to which
clauses in the definition above.

It should then be relatively easy to see that:

 4.1. COMPLETENESS 49

F ACT 88. ϕ is a well formed formula (ϕ ∈ W F F ) iff there is some n such that
ϕ ∈ StageW F F + (n).

R EMARK . This itself would be a simple proof by induction.

With this in hand, we are finally ready to complete the proof of Lemma 86,
which we restate for convenience.

L EMMA . 86 If ψ is on B, then MB |= ψ.

P ROOF. We proceed by induction on the +-complexity of formulae.

(Base) If ψ is atomic and on B, then ψ is of the form Ra1 , ..., an for some n-ary
relation symbol R and constant symbols a1 , ..., an . Then we have
B B B
Ra1 ...an is on B ⇔ haM M
1 , ..., an i ∈ R
M
c Toby Meadows

⇔ MB |= Ra1 ...an

definition of |=.
.1 f
t
The first ⇔ follows from the definition of MB ; and the second, from the
v1 ra
(Induction Step) Suppose that for all sentences χ of +-complexity ≤ n we
have established that:

• if χ is on B, then MB |= χ.
D

This is our induction hypothesis.

We show that the same is true for sentences ψ of +-complexity n + 1. To do
this we consider all of the forms of formulae that could be constructed from
formulae of +-complexity ≤ n.
Suppose ψ := χ ∧ δ is on B where χ and δ have +-complexity ≤ n. Then by the
e

rules for construction of tableau, both χ and δ occur on B. By our induction

in

hypothesis, we see that MB |= χ and MB |= δ; and thus by the definition of

|=, we get MB |= χ ∧ δ.
nl

Suppose ¬(χ ∧ δ) is on B where ¬χ and ¬δ have +-complexity ≤ n. Then by

the tableau construction rules, at least one of ¬χ and ¬δ is on B. Suppose ¬χ
O

is on B. Then by induction hypothesis, MB |= ¬χ; and thus MB |= (¬χ ∧ δ).

Suppose ¬δ is on B. Then by induction hypothesis, MB |= ¬δ; and thus
MB |= ¬(χ ∧ δ).
The cases for ¬(χ ∨ δ), χ ∨ δ, ¬(χ → δ), χ → δ are similar.
 4.2. SOUNDNESS 50

Suppose ¬¬χ is on B where χ has +-complexity ≤ n. Then by the rules of

construction of tableau, χ is also on B. Then by the induction hypothesis,
we have MB |= χ; and thus, by the |= definition, MB |= ¬¬χ.
Suppose ∀xχ(x) is on B where χ(x) has +-complexity ≤ n. Then by the
tableau rules, for every constant a in L(C) we have χ(a) on B. By induction
hypothesis, we have MB |= χ(a) for each a ∈ L(C). Then since the domain,
M B , is just the set of constant symbols in L(C), we have MB |= ∀xχ(x).
Suppose ¬∀xχ(x) is on B where ¬χ(x) has +-complexity ≤ n. then by the
tableau rules, there is some constant symbol a in L(C) such that ¬χ(a) is on
B. Fix such an a. Then by induction hypothesis, we have MB |= χ(a); and
thus MB |= ∃xχ(x).
The cases for ∃xχ(x) or ¬∃xχ(x) are similar. 

[Link]. Adding the identity (=) relation.

c Toby Meadows

.1 f
t
4.2. Soundness

4.2.1. The Strategy. Our goal is to show that if ` ϕ, then |= ϕ. In other

v1 ra
words, we want to show that if the tableau commencing with ¬ϕ is closed,
then ϕ is true in every model.
We have a similar problem to the situation with completeness here. Given a
D

tableau proof of some ϕ, how should we go about showing that ϕ is true in

every model.
Again we are going to contrapose. Thus we show that:
• If 2 ϕ, then 0 ϕ.
Or, unpacking things a little, if there is a model M where M |= ¬ϕ, then
e

there is a tableau commencing with ¬ϕ which has an open branch. So all

in

we need to do is figure out how to find such a branch.

The key to doing this will be the model M. It will, so to speak, provide us
nl

with a map through the tree.

Our proof requires two parts:
O

(1) We define a process for finding of the branch; and

(2) We show that the branch cannot close.

4.2.2. The Proof.

 4.2. SOUNDNESS 51

[Link]. Constructing the branch B. Suppose we have some sentence ϕ

and a model M |= ¬ϕ. Let T be the completed tableau for ¬ϕ. Such a
tableau is one in in which every branch is either:
• closed; or
• such that every rule that can be used has been used.
Essentially, we are going to show how to find an open branch B in T by
working our way step by step down it.
We shall ensure that the branch remains open by making sure that every
sentence we add by the rules is actually true in M. Since we know there are
no sentences ϕ such that both it and its negation are true in M we are thus
guaranteed to get an open branch.
Let us let the length of a branch B in a tableau T be the number of applica-
tions of tableau rules that have occurred in its construction.
c Toby Meadows

L EMMA 89. (Branch Extension) Suppose B is an initial branch of some com-

.1 f
t
pleted tableau T and M is such that for all ψ on B

M |= ψ.
v1 ra
Then provided there are still rules left to apply, there is some extension B 0 of
branch B in T and expansion M0 of M such that for all ψ on B 0

M0 |= ψ.
D

P ROOF. To establish this, we need to go through each of the rules and

show that there is a way to extend B such that every sentence on B 0 remains
true in M.
(∧) Suppose the B continues with an application of the (∧) rule. Then χ ∧
δ occurs at some earlier point on the branch B and thus M |= χ ∧ δ (by
e

hypothesis). Thus B must be continued to B 0 be adding both χ and δ to the

in

bottom of B. We let M0 = M be the trivial expansion of M. Moreover, M |= χ

and M |= δ.
nl

(∨) Suppose B continues with an application of the (∨) rule. Then B splits
into a χ path and ψ path; and χ ∨ δ occurs at some earlier stage on B. By the
O

hypothesis, we have M |= χ ∨ δ and so either M |= χ or M |= δ. Continue B

to B 0 by picking a side of the fork on which the formula (either χ or δ) is true
in M (it could be both). Then letting M0 = M, we have our result. The cases
for (∨), (¬∨), (→), (¬ →) and (¬¬) are left as exercises.
 4.2. SOUNDNESS 52

(∃) Suppose B continues with an application of the (∃) rule. Then, by the
tableau rules, the next sentence on Bn+1 is something of the form ϕ(a 7→ m)
where a does not occur in any sentence already on B; and ∃xϕ(x) occurs on
B at some earlier stage. By the hypothesis, we have M |= ∃xϕ(x), so there is
some m ∈ M such that M+ |= ϕ(m 7→ x). Let M0 an interpretation of L ∪ {a}
such that aM = m. Then M0 |= ϕ(a 7→ n) as required.
(∀) Suppose Bn continues with an application of the (∀) rule. Then ∀xϕ(x)
occurs on Bn at some earlier stage and the next sentence on Bn is something
of the form ϕ(a) for some constant symbol

• occurring in some sentence higher up the branch Bn ; or

• an arbitrary constant symbol a from C if there are no constant sym-
bols occurring above ∀xϕ(x).

In either case, by the hypothesis, we then have that M |= ∀xϕ(x) and thus
c Toby Meadows

M |= ϕ(a 7→ x) for any constant symbol of the language. In the former case,
.1 f
t
we let M0 = M and we are done. In the latter case, we let M0 be a model of
the language L ∪ {a} such that aM = m from some arbitrary m ∈ M . Then we
have M0 |= ϕ(a 7→ x). The cases for (¬∀) and (¬∃) are left as exercises. 
v1 ra

L EMMA 90. Suppose M |= ¬ϕ. Then there is an open branch in the tableau T
for ϕ.
D

P ROOF. We prove this in two stages:

(1) we describe how to construct the open branch;

(2) we demonstrate that it is open.

To construct the open branch we commence the tableau in the usual way
by placing ¬ϕ at the top of the tableau. To find the next stage of the branch
e

we apply the Branch Extension Lemma (89). To find the stage after than we
in

apply the Branch Extension Lemma again and so on. We stop if there are
no more rules left to apply and if this never happens we keep going (thus
nl

leaving an infinite branch). Observe that this is just an informal version of

a definition by recursion. We could do this more formally by setting up a
O

system of stages.
Now we show that the branch B resulting from this process is open. Suppose
not. Then B must be closed. Thus at some (finite) stage, say Bn , in the
construction of B we must have both ψ and ¬ψ on Bn . But our use of the
 4.2. SOUNDNESS 53

Branch Extension Lemma tells us that for every sentence χ on Bn we have

Mn |= χ. Thus we have M |= ψ and M 2 ψ which is a contradiction. 

T HEOREM 91. If ` ϕ, then |= ϕ.

P ROOF. Suppose 2 ϕ. Then there is some model M such that M |= ¬ϕ.

By Lemma 90, there is an open branch in the tableau for ¬ϕ. Thus 0 ϕ. 
c Toby Meadows

.1 f
t
v1 ra
in D
e
nl
O
 4.3. EXERCISES 54

4.3. Exercises

E XERCISE 92. Suppose we are have a language L with two single place re-
lation symbols P and Q; and one constant symbol. Write out the sentences
from the first 3 stages of StageW F F + noting which label each sentence comes
from.

E XERCISE 93. In your own words:

(1) Explain what the completeness theorem says.
(2) Explain why is interesting and important.
(3) Explain how we proved it.

E XERCISE 94. Finish the rest of the cases from the proof Lemma 86.

E XERCISE 95. Complete the rest of the cases in Lemma 89.

c Toby Meadows

E XERCISE 96. Use the Completeness Theorem to prove Lemma 75.

.1 f
t
v1 ra
in D
e
nl
O
 CHAPTER 5

Completeness 2

Goals:
• Prove the soundness of the natural deduction proof system.
• Prove the completeness of the natural deduction proof system.
1
T HEOREM 97. Γ `N at ϕ iff Γ |= ϕ.

The (→) direction is known as soundness; and the (←) direction is known as
c Toby Meadows

completeness.
This theorem is know as strong completeness, since we are permitted to use
a set of sentences Γ from which to derive ϕ.
.1 f
t
v1 ra
5.1. Soundness

5.1.1. Strategy. In a nutshell, soundness says that if we can derive ϕ

from assumptions in Γ, then ϕ is true in all models where all of Γ is true. We
D

are trying to show that when we construct a proof, the rules of our natural
deduction system don’t get us into any trouble: they don’t derive things that
aren’t consequences.
Now given that we construct proofs in a stage-by-stage kind of fashion, this
suggests that we might use induction to prove this theorem. We want to
demonstrate a fact about all derivations so we might figure out a way of
e

defining the derivations in a stage-by-stage way and then use our induction
in

principle to complete the proof.

Of course, the notion of complexity/stage will not be the complexity of a for-
nl

mulae. We need something different. But the required notion is not difficult
to think up. We just need to think about how a derivation is constructed
O

using the rules of our system.

5.1.2. Proof.
1
We shall omit the N at for the remainder of this week’s notes.
55
 5.1. SOUNDNESS 56

[Link]. Building derivations in stages . Recall that we write Γ `N D ϕ to

mean that there is a (natural deduction) derivation of ϕ from (finitely many)
assumptions contained in Γ. We want to describe a way of defining all of
these derivations.
For this kind of definition to work, we need to things:

(1) a place/set from which to start (our base);

(2) a set of rules which tell use how to get from one stage to the next
(our inductive jump).

Now it’s easy to see what to use for the rules (2.). We are just going to use
the rules of the natural deduction system.
For example, suppose we had derivations of Γ ` ϕ and ∆ ` ψ. Then using
the (∧-I) rule we can clearly get a derivation of Γ, ∆ ` ϕ ∧ ψ. All we are
saying here is that we may put together the derivation dϕ of Γ ` ϕ and the
c Toby Meadows

derivation of dψ ` ψ such that one is above the other. Then the final lines

t
of each derivation can be put together using (∧-I) to get a derivation of ϕ ∧ ψ
from assumptions in Γ, ∆.2 Write this out in the Lemon style to convince
.1 f
yourself of this fact and to get more familiar with the notation.
v1 ra
Similarly, given a derivation of Γ, ϕ ` χ and a derivation of Γ, ψ ` χ, we may
use the (∨-E) rule to construct a derivation of Γ, ϕ ∨ ψ ` χ. Again, write out
the form of this derivation to convince yourself this is correct.
D

This tells us how we may move from one stage of our construction to another,
but what is our base or atomic case. Again the obvious things works. The
simplest derivation is simply the derivation of ϕ from the assumption ϕ itself.
This is the first line of any derivation. We may write this as {ϕ} ` ϕ.
Now let us formally define a derivation in stages as follows. We let StageDer (n)
e

give us the nth stage of our construction:

in

• StageDer (1) is the set of all derivations of the form {ϕ} ` ϕ for some
sentence ϕ of our language; and
nl

• StageDer (n + 1) is the set of all derivations which are either:

– in StageDer (n); or
O

– can be constructed from derivations d ∈ StageDer (n) using the

rules of the natural deduction system.
2
Strictly, since Γ and ∆ are sets of sentences, we should write Γ ∪ ∆ rather than Γ, ∆, but
we shall write it this way for convenience. No confusion should arise.
 5.1. SOUNDNESS 57

We then say that d is a derivation if there is some n such that d ∈ StageDer (n).
Alternatively and equivalently (as we saw in Week 1), we may define a deriva-
tion as follows:
• if d is of the form {ϕ} ` ϕ, then d is a derivation;
• if dϕ is a derivation of Γ ` ϕ and dψ is a derivation of ∆ ` ψ, then the
derivation d formed by combining dϕ and dψ using (∧-I) is a derivation
of Γ, ∆ ` ϕ ∧ ψ;
• ... add a case for each rule for the construction of derivations
(see Exercise 110) ...
• nothing else is a derivation.
With this method of building up derivations using rules we are ready to use
the induction principle to complete a proof about all derivations and how
they preserve truth.
c Toby Meadows

[Link]. Showing that the rules preserve truth. We first note the follow-

significant.
.1 f
t
ing simple (but important fact) which will be helpful in the proof and also
v1 ra
P ROPOSITION 98. (Monotonicity) If Γ ` ϕ and ∆ ⊇ Γ, then ∆ ` ϕ. Moreover, if d
is a derivation witnessing that Γ ` ϕ, then d also witnesses that ∆ ` ϕ.

So our goal theorem is the following:

D

T HEOREM 99. If Γ ` ϕ, then Γ |= ϕ.

But it will be useful to unpack the definition of the consequent. Thus, we

want to show that if there is a derivation such that Γ ` ϕ, then in every
model M where every γ ∈ Γ is true in M, then so is ϕ.
e

P ROOF. We proceed by induction on the complexity of derivations. Thus

in

we show that “atomic” derivations uphold our goal fact and that construc-
tions of new derivations based on the rules also uphold our goal fact.
nl

(Base) Suppose d is a derivation of the form {ϕ} ` ϕ. Then we need to show

that in every model M where every γ ∈ {ϕ} is such that M |= γ, we have
O

M |= ϕ. Let M be an arbitrary model in which every element of {ϕ} is true.

Thus M |= ϕ; and this is exactly what we want.
(Induction step) Now suppose that we have shown that for every stage m ≤ n,
that
 5.1. SOUNDNESS 58

• if some derivation witnessing that ∆ ` ψ is in StageDer (m), then ∆ |=

ψ.
This is our induction hypothesis. To complete the induction step, we need
to show that the same is true for stage n + 1. Let d which is in StageDer (n +
1)\StageDer (n) (i.e., this is the first stage of the construction in which d is
present - unlike say an atomic derivation which will be present in every
level). Then by the definition of the stages, d must have been formed from
derivation(s) in previous levels by one of the rules of the natural deduction
system. So it will suffice if we show the result holds for each of the rules.
We shall do a few of the cases here and leave the rest as exercises.
(∧-I) Suppose dϕ is a derivation of Γ ` ϕ and dψ is a derivation of ∆ ` ψ with
both dϕ and dψ being from some stage n. Then the (∧-I)-rule says that the
n + 1th stage will consist of a derivation d such that Γ, ∆ ` ϕ ∧ ψ. To complete
c Toby Meadows

this case, we must show that Γ, ∆ |= ϕ ∧ ψ.

First observe that by Proposition 98, dϕ and dψ are also derivations witness-
.1 f
t
ing that Γ, ∆ ` ϕ and Γ, ∆ ` ψ. Then by induction hypothesis, since dϕ , dψ
are less complex, we have Γ, ∆ |= ϕ and Γ, ∆ |= ψ. Let M be a model in which
v1 ra
M |= γ for all γ ∈ Γ ∪ ∆. Thus we have M |= ϕ and M |= ψ, so M |= ϕ ∧ ψ,
which is what we wanted.3
(∀-I) Suppose we have a derivation dϕ of Γ ` ϕ(a), where a does not occur
D

in Γ or ∀xϕ(x) where dϕ is a member of stage n. Then by the rules of stage

construction, there is a derivation d of Γ ` ∀xϕ(x) in stage n + 1. We must
show that Γ |= ∀xϕ(x).
By induction hypothesis, we see that Γ |= ϕ(a). Let M be a model in which
all of Γ is true. Then M |= ϕ(a). Suppose that m = aM . Now consider any
0
model M0 which is exactly like M, except that aM = m0 6= aM = m; i.e., we let
e

0
aM be some arbitrary other m0 from the domain M . Since Γ does not contain
in

any sentence with the constant symbol a in it, it is obvious that M0 is still a
model of all of Γ.4 Thus M0 |= ϕ(a).
nl

But the fact that all models M0 whose only difference from M is their inter-
pretation of the symbol a are such that M0 |= ϕ(a) just means that:
O

∀m ∈ M M+ |= ϕ(m) ⇔ M |= ∀xϕ(x).
3
Observe that I am using both interpretations of the |= symbol here. One represents the
satisfaction reading and the other is giving us the consequence reading.
4
Why is it clear? See Exercise 111.
 5.1. SOUNDNESS 59

(∨-E) This one is a little more complicated since we have more plugging-in
involved in (∨-E). Suppose:

• dϕ is a derivation of Γ, ϕ ` χ;
• dψ is a derivation of ∆, ψ ` χ; and
• dϕ∨ψ is a derivation of Ξ ` ϕ ∨ ψ.

which are all members of stage n. Then, the (∨ − E) rule tells us that the
n + 1th stage contains a derivation d of Γ, ∆, Ξ ` χ. We must show that that
Γ, ∆, Ξ |= χ.
It will actually suffice to show that Γ, ∆, ϕ ∨ ψ |= χ since if M |= γ for all
γ ∈ Γ ∪ ∆ ∪ Ξ, then M |= γ for all γ ∈ Ξ. Then since dϕ∨ψ is a derivation of
less complexity (i.e., a member of the nth stage) we see that Ξ |= ϕ ∨ ψ. Thus
M |= ϕ ∨ ψ and M |= χ, which is what we need to show.
c Toby Meadows

So let us suppose that M is such that for all γ ∈ Γ ∪ ∆ ∪ {ϕ ∨ ψ}, M |= γ. Then

by induction hypothesis , we have both:

(1) Γ, ϕ |= χ; and
.1 f
t
v1 ra
(2) ∆, ψ |= χ.

Now since M |= ϕ ∨ ψ, either M |= ϕ or M |= ψ. Suppose the former, then by

(1.), M |= χ. Suppose the latter, then by (2.), M |= χ. Thus M |= χ, which is
what we needed to prove.5
D

R EMARK 100. Note how this move relies on the assumption that a is not
free in ∀xϕ(x). If it had been, it would end up being bound by the universal
quantifier in the move we make here and we wouldn’t really have ∀xϕ(x) in
e

such a case. For example, if we’d let ϕ(x) be x = a, then we would have
in

0
|= ϕ(a); i.e., every M is such that M |= a = a. Thus every M0 where aM 6= aM
is such that M |= a = a. However, this only tells us that
nl

∀m ∈ M + M |= m = m ⇔ M |= ∀x(x = x).
O

Thus we get the universalisation of x = x, this is the wrong formula.

5
Observe that we actually employed a version of the rule (∨-E) in the metalanguage of our
proof, when took up the two suppositions: first, that ϕ is true in M; and second, that ψ is
true in M. This almost circular feature is a characteristic of soundness proofs.
 5.2. COMPLETENESS 60

5.2. Completeness

5.2.1. Strategy. At a high level, we are taking the fact that there is no
proof of ϕ from assumptions in Γ and using that fact to make a set of sen-
tences which describes a model in which Γ ∪ {¬ϕ} is true.
As in the previous week, our strategy can be described as follows:

(1) Find a special set of sentences ∆ to describe the model.

(2) Define a model M∆ using the special set; and
(3) Show that every member of Γ ∪ {¬ϕ} is indeed true in M∆ .

This will clearly suffice to establish our completeness theorem.

At this level, the proof has the same strategy as for the tableau completeness
theorem. But as we get into the details there is less similarity.
c Toby Meadows

5.2.2. The Proof.

t
[Link]. The special set. In the tableau case, we had an obvious way of
construction a special set: we used the sentences from an open branch.
.1 f
With the natural deduction system, there is no obvious counterpart. We
v1 ra
do not have a canonical means of generating counterexamples with natural
deduction: the system only gives us a means of proving things.
So what can we do? This is our position:
D

(1) We want to describe a model in which every sentence in Γ ∪ {¬ϕ};

and
(2) We know that Γ ∪ {¬ϕ} is consistent.

Now we have no reason to think that Γ ∪ {¬ϕ} contains enough information

to describe a model, but what if we added more information. Perhaps we
e

could keep on adding more sentences until we did have such a description.
in

This will be our strategy.

So which sentences should we add? Let’s make it simple and everything that
nl

we can. By “can” let us mean we add any sentence that is consistent with
Γ ∪ {¬ϕ}. If, on the other hand, we added a sentence ψ to the set which was
O

inconsistent with Γ ∪ {¬ϕ}, then we would know (by soundness) that there
was no model of Γ ∪ {¬ϕ, ψ}. So we certainly don’t want that.
We have no reason to think that adding sentence which are consistent will
stop us from being able to find a model; indeed, by adding sentences which
 5.2. COMPLETENESS 61

are consistent with Γ ∪ {¬ϕ}, we hope to be able to pin down one particular
model.
Intuitively speaking our process will be to start with the set Γ ∪ {¬ϕ} and add
as many sentences consistent with it as we can. Such a set will be called
maximal consistent.
D EFINITION 101. A set of sentences ∆ is maximal consistent if:
• ∆ is consistent; and
• if ϕ ∈
/ ∆, then ∆ ∪ {ϕ} is not consistent.

So if we added a single extra sentence to a maximal consistent ∆, then the

result would no longer be consistent.
Maximal consistent sets have a very useful property. They give us (negation)-
complete sets of sentences.6
c Toby Meadows

D EFINITION 102. A set of sentences ∆ is (negation)-complete if for every sen-

tence ϕ either ϕ ∈ ∆ or (¬ϕ) ∈
.1 f / ∆.

t
A complete set of sentences ∆ is going to be useful for describing a model,
v1 ra
just as with a model M we have M |= ϕ or M |= ¬ϕ for all sentences ϕ
we have ϕ ∈ ∆ or (¬∆). This bivalence-like property gives us, intuitively
speaking, the sufficiency of information to define the model.
T HEOREM 103. If ∆ is maximal consistent, then ∆ is complete.
D

P ROOF. Suppose ∆ is maximal consistent. Let ϕ be an arbitrary sentence.

to show that ∆ is complete, it will suffice to show that either ϕ ∈ ∆ or
(¬ϕ) ∈ ∆. We first establish a helpful claim.
C LAIM . (i) If ϕ ∈
/ ∆, then ∆ ` ¬ϕ; (ii) If (¬ϕ) ∈
/ ∆, then ∆ ` ϕ.
e

P ROOF. (i) By maximality ∆ ∪ {ϕ} is not consistent. From assumptions in

in

∆ ∪ {ϕ}, we can derive ⊥. Since ∆ is consistent, it is clear that ϕ must be

one of the assumptions in this proof. By (¬-I), we may thus get a proof of ¬ϕ
nl

from ∆; i.e., ∆ ` ¬ϕ. (ii) similar. 

Now we suppose for reductio, that both ϕ and ¬ϕ are not in ∆. By the claim
O

above, we have ∆ ` ¬ϕ and ∆ ` ϕ. Thus using (¬-E), we may construct a

proof of ⊥ from ∆: contradicting our assumption that ∆ is consistent. 
6
Note the sense of complete here is different to that meant when we speak of the complete-
ness of a proof system.
 5.2. COMPLETENESS 62

So this is a good start for our special set of sentences ∆. But there is
something else we need. In a similar fashion to the completeness proof for
tableau, we are going to use the constant symbols occurring in sentences of
the set to form our domain.
Now suppose we have the following situation. For some sentence ϕ := ∃xψ(x)
we have:

• ∃xψ(x) is in ∆; but
• for all a ∈ M ∆ (our domain of constant symbols) (¬ψ(a)) ∈ ∆.

There’s something clearly wrong with this. If it’s truth that there is a ψ, then
something from the domain had better be an a.
Now if we only restrict ourselves to consistent extensions of Γ ∪ {¬ϕ}, then
we cannot avoid this problem. To see this observe that there is no way of
c Toby Meadows

deriving ⊥ from the set consisting of:

• ∃xψ(x); and
• ¬ψ(a) for all a ∈ M ∆ .
.1 f
t
We’ll simply never get into a position where the consistency constraint could
v1 ra
(in general) block the problem.
The simple condition is to add a further condition on the set ∆. We demand
that every existential sentence gets a witness; or more formally:
D

• if ∃xψ(x) ∈ ∆, then for some constant symbol a, ψ(a) ∈ ∆.

We shall say that ∆ is existentially witnessed if it enjoys this property.

We shall see that these two requirements are sufficient for our result. We
now know what we require of our special set ∆, but how do we get such a
e

set. Again using the techniques of Week 1, we are going to build up this set
by recursion in stages.
in

We first take an enumeration (ϕn )n∈ω = ϕ1 , ϕ2 , ..., ϕn , .... of all the sentences
from L(C).
nl

We now proceed as follows:

O

• Let Stage∆ (∅) = Γ ∪ {¬ϕ}

• Let Stage∆ (n + 1) be the collection of sentences including:
– sentences from Stage∆ (n);
– ϕn+1 if ϕn+1 is consistent with Stage∆ (n); and
 5.2. COMPLETENESS 63

– ψ(a) if ϕn+1 := ∃xψ(x) where a is some constant symbol not in

Stage∆ (n) or ϕn+1 and ϕn+1 is consistent with Stage∆ (n).
We then say that ψ ∈ ∆ iff there is some n such that ψ ∈ Stage∆ (n).

R EMARK 104. Observe that we are always able to find a new constant symbol
since there are infinitely many of them and at any stage of the construction
we have only used finitely many.

∆ is then our special set. We then verify that ∆ is indeed maximal consistent
and is existentially witnessed.

L EMMA 105. ∆ is maximal consistent and existentially witnessed.

R EMARK 106. I use D to denote derivations in this proof (instead of d) in

order to avoid confusion with constant symbols.
c Toby Meadows

P ROOF. ∆ is existentially witnessed by the way we constructed the ∆.

.1 f
t
If ∆ is not consistent, then by LNP, there must have been some least stage
at which Stage∆ (n + 1) became inconsistent while Stage∆ (n) is consistent.
v1 ra
So clearly whatever was added to Stage∆ (n) caused the inconsistency. There
are two possible scenarios:
(i) Stage∆ (n + 1) = Stage∆ (n) ∪ {ϕn+1 } where ϕn+1 is not of the form ∃xψ(x);
(ii) Stage∆ (n + 1) = Stage∆ (n) ∪ {ϕn+1 , ψ(a)} where ϕn+1 is of the form ∃xψ(x).
D

In case (i), we see that by how we defined the stage construction that we
only have
Stage∆ (n + 1) = Stage∆ (n) ∪ {ϕn+1 }
when Stage∆ (n) ∪ {ϕn+1 } is consistent. This means that Stage∆ (n + 1) is con-
sistent after all.
e

In case (ii), we see that ϕn+1 must be of the form ∃xψ(x). Supposing that
in

Stage∆ (n + 1) = Stage∆ (n) ∪ {ϕn+1 , ψ(a)}

nl

is inconsistent, there must be some derivation of ⊥ from it. Consider such

a derivation D. We now show how to transform D into a derivation of ⊥
O

from Stage∆ (n) ∪ {ϕn+1 }. By the same reasoning as for the case (i), this is a
contradiction and will suffice for the Lemma.
Observe that a does not occur in Stage∆ (n + 1). Thus D cannot rely on an
assumption in which a occurs free. But this just means that we can employ
 5.2. COMPLETENESS 64

(∃-E) on ∃xψ(x) and ψ(a), thus discharging ψ(a) as an assumption in D. This

leaves us with a derivation d0 of Γ, ∃xψ(x) ` ⊥ which means that ∃xψ(x) was
inconsistent with Γ after all. By the rules of the construction, this means
that ∃xψ(x) could not be in Stage∆ (n) which contradicts our assumption. 

[Link]. Defining the model. We now use ∆ to define a model. We let the
language be L(C).
Let M∆ be such that:
• M ∆ (the domain) is the set of constant symbols a occurring in sen-
tences in ∆;
• for each constant symbol a, let aM = a (i.e., itself);
• for each n-ary relation symbol R of L(C), let RM be the set of n-tuples
ha1 , ..., an i such that Ra1 , ..., an is in ∆.
c Toby Meadows

[Link]. Showing that M∆ |= Γ ∪ {¬ϕ}. As with the tableau proof, we now

want to show that every sentence in Γ ∪ {¬ϕ} is in fact true in M∆ .
Once again we show something stronger.
.1 f
T HEOREM 107. ϕ ∈ ∆ iff M∆ |= ϕ.
t
v1 ra

R EMARK 108. Observe that we have an “iff” here, as opposed to the “if ...,
then ...” from the tableau completeness proof.
D

Again our strategy here is going to be a proof by induction. However, in

contrast to the completeness proof for tableau, this is much simpler. We
can get away with using our simple definition of the complexity of formulae
(rather that +-complexity or something even more exotic).
The following claim is very helpful.
e

C LAIM 109. Suppose ∆ is maximal consistent. Then ∆ ` ψ iff ψ ∈ ∆.

in

P ROOF. (→) Suppose ∆ ` ψ. For reductio suppose ψ ∈

/ ∆. Then by Lemma
103 we (¬ψ) ∈ ∆. Then we could make a derivation of ⊥ from sentences in
nl

∆: contradicting the consistency of ∆. Thus ψ ∈ ∆.

(←) Suppose ψ ∈ ∆. Then we may trivially derive ψ from {ψ} ⊆ ∆. 
O

P ROOF. (of Theorem 107) We proceed by induction on the complexity of

formulae.
(Base) Exercise.
 5.2. COMPLETENESS 65

(Induction Step) Suppose that for all sentence of complexity ≤ n, we have

shown that ψ ∈ ∆ iff M∆ |= ψ. We show that the same is true for formulae of
complexity n + 1.
Suppose ψ := χ ∧ δ ∈ ∆. We claim that χ ∧ δ ∈ ∆ iff both χ ∈ ∆ and δ ∈ ∆. If
χ ∧ δ ∈ ∆, then by Claim 109 and (∧-E) we have both χ and δ in ∆. If both χ
and δ are in ∆ then Claim 109 and (∧-I) tell us that χ ∧ δ ∈ ∆.
From here we have:

χ∧δ ∈∆ ⇔ χ∈∆ & δ ∈∆

⇔ M∆ |= χ & M∆ |= δ
⇔ M∆ |= χ ∧ δ.

The first ⇔ is via our claim; the second ⇔ is by induction hypothesis; and
the last ⇔ is from the |= definition.
c Toby Meadows

Suppose ψ := ¬χ. Then

.1 f (¬χ) ∈ ∆ ⇔ χ ∈
t
/∆
⇔ M∆ 2 χ
v1 ra
⇔ M∆ |= ¬χ.

The first ⇔ is via the completeness of ∆; the second ⇔ is by induction

hypothesis; and the last is via the |= definition.
D

Suppose ψ := ∃xχ(x). Then we claim that ∃xχ(x) ∈ ∆ iff there is some con-
stant symbol a in L(C) such that χ(a) ∈ ∆. Suppose ∃xχ(x) ∈ ∆. Then
by construction of ∆ (i.e., since it is existentially witnessed) there is some
a ∈ L(C) such that χ(a) ∈ ∆. On the other hand if for some a ∈ L(C), χ(a) ∈ ∆,
then by Claim 109 and (∃-I), ∃xχ(x) ∈ ∆. Then we have
e

∃xχ(x) ∈ ∆ ⇔ there is some a ∈ M ∆ such that χ(a) ∈ ∆

in

⇔ there is some a ∈ M ∆ such that M∆ |= χ(a)

⇔ M∆ |= ∃xχ(x).
nl

The first ⇔ came from our claim; the second ⇔ was via the induction hy-
pothesis; and the final ⇔ was via the |= definition.
O

The other cases are left as exercises. 

 5.3. EXERCISES 66

5.3. Exercises

E XERCISE 110. In Section [Link], our second definition has not been com-
pleted. Complete the definition by adding the appropriate clauses for each
of the other rules in the system.

E XERCISE 111. In the proof of Theorem 99, we make a claim about some-
thing being obvious (there is a footnote highlighting this). Establish the
claim.

E XERCISE 112. Complete the rest of the cases in the proof of 99.

E XERCISE 113. Complete part (ii) of the claim in Theorem 103.

E XERCISE 114. Explain why there is no derivation of ⊥ from the set consist-
ing of:
c Toby Meadows

• ∃xψ(x); and
• ¬ψ(a) for all a ∈ M ∆ .
.1 f
E XERCISE 115. In your own words: t
v1 ra
(1) Explain what the completeness theorem says.
(2) Explain why is interesting and important.
(3) Explain how we proved it.
D

E XERCISE 116. Complete the base case for Theorem 107.

E XERCISE 117. Complete the rest of the cases for the proof of Theorem 107.
e
in
nl
O
 CHAPTER 6

Model Theory

Goals:

• Look at some basic model theory.

• Prove the compactness theorem.

6.1. Isomorphism and Elementary Equivalence

c Toby Meadows

In this week, we are going to be concerned with relationships between mod-

els. .1 f
t
Consider two models M and N of some language L. All that they have in
common is the fact that they have interpretations for the same relation,
v1 ra
constant and function symbols.
We now consider two ways in which M and N may be very alike: isomor-
phism and elementary equivalence. Before we do this we’ll need a few simple
D

concepts from set theory.

A map is a function, which we may denote as say σ, which has a domain say
D and a codomain C. It takes any object in D and outputs an object from C.
We abbreviate this by writing σ : D → C.1
We say that a map σ : D → C is surjective if for every element c ∈ C, there
e

is some d ∈ D such that σ(d) = c. In other words, the map σ exhausts its
codomain. (Sometimes such maps are called onto.)
in

We say that a map σ : D → C is injective if for any two elements d1 6= d2 ∈ D,

σ(d1 ) 6= σ(d2 ). Thus different object in the domain are always output to
nl

different object in the codomain. (Sometimes such maps are called one-to-
one.)
O

We say that a map is bijective if it is both surjective and injective.

1
Note that there is no requirement that every object in C the result of σ’s application to
some object d ∈ D. Some c ∈ C may be missed, as it were.
67
 6.1. ISOMORPHISM AND ELEMENTARY EQUIVALENCE 68

D EFINITION 118. Let us say that models M and N are isomorphic, abbrevi-
ated M ∼= N , if there is a map σ between M and N (their respective domains)
such that:

• σ is bijective;
• for every constant symbol c from L, we have

σ(cM ) = cN ;

• for every n-ary relation symbol R in L and any m1 , ..., mn from M , we

have

hm1 , ..., mn i ∈ RM ⇔ hσ(m1 ), ..., σ(mn )i ∈ RN ; and

• for every n-ary function symbol f in L and any m1 , ..., mn from M , we

have
c Toby Meadows

σ(f M (m1 , ..., mn )) = f M (σ(m1 ), ..., σ(m2 )).

We shall write σ : M ∼
t
= N to indicate that σ is the map described above which
.1 f
witnesses the isomorphism.
v1 ra
R EMARK 119. There is a sense in which isomorphic models are basically
the same. The only thing that distinguishes two isomorphic models is the
material from which they are constructed. However, from the point of view
D

of the language L and what we can express in it, this kind of difference is
invisible, or perhaps better, ineffable.

Elementary equivalence is also a relation between models which expresses

the fact that they are alike in some way.
e

D EFINITION 120. Two models M and N of some language L are elementary

in

equivalent, abbreviated M ≡ N , if for every sentence ϕ ∈ SentL , we have:

M |= ϕ ⇔ N |= ϕ.
nl

Thus two models are elementary equivalent, they make exactly the same
O

sentences true.

We might wonder if elementary equivalence and isomorphism just mean the

same thing. We shall see in the next section that they do not.
 6.2. THE COMPACTNESS THEOREM 69

6.2. The compactness theorem

The compactness theorem is the foundation stone of basic model theory. It

is the engine in the background of all of the basic theorem in this research
area. However, it perhaps does not, at first glance, appear to be so signifi-
cant. To appreciate it, we’ll need to look at how it can be applied.
As usual we’ll need a few definitions to get things moving.
We already say that a sentence ϕ of some L is satisfiable if there is some M
such that M |= ϕ.
Let Γ be a set of sentences from L. We shall say that Γ is satisfiable if every
sentence γ ∈ Γ is such that M |= γ; and we’ll abbreviate this by M |= Γ
(another overloading of the |= symbol).
We shall say that Γ is finitely satisfiable if for every finite subset ∆ of Γ, ∆ is
c Toby Meadows

satisfiable; i.e., there is some M such that M |= ∆.

We may now state the compactness theorem.

t
T HEOREM 121. (Compactness) If Γ is finitely satisfiable, the Γ is satisfiable.
.1 f
v1 ra
In other words, if every finite subsets of Γ has a model, then so does Γ itself.

P ROOF. We proceed by contraposition. Suppose that Γ is not satisfiable.

This just means that Γ |= ⊥; i.e., there is no model which makes all of Γ
D

true. By completeness, we then see that Γ ` ⊥. Thus there must be some

finite set of assumptions ∆ from which we may derive ⊥ (in say the natural
deduction system); i.e. ∆ ` ⊥. But then, by soundness we get ∆ |= ⊥; or in
other works, there is no model M which makes all of ∆ true. Thus Γ is not
finitely satisfiable. 
e

6.2.1. Nonstandard models. We now show how elementary equivalence

in

and isomorphism come apart.

Let N be the standard model of arithmetic as described in Example 34 from
nl

Week 2. For convenience, let’s assume that we have a constant symbol for
every natural number. It could just be our everyday Arabic representation of
O

it. So strictly speaking we have expanded the language of arithmetic and its
standard model to accommodate all these new constant symbols. We shall
only take this approach in this section.
Another definition is helpful at this point.
 6.2. THE COMPACTNESS THEOREM 70

D EFINITION 122. Given a model M, let the theory of M, T h(M) be the set of
sentences from L which are true in M.

T HEOREM 123. There is a model M such that M |= T h(N) but M  N.

P ROOF. Our strategy here will be to employ the compactness theorem.

Let us expand L with the addition of a single new constant symbol c and call
the result Lc . Now consider Γ ⊆ SentLc which consists of:

• all of the sentences in T h(N); and

• the set of sentences of the form c 6= n̄ where n̄ is a constant symbol
denoting n.

Now we claim that Γ is finitely satisfiable. Let ∆ be some finite subset of Γ.

c Toby Meadows

To get a model N for ∆, we just expand the standard model N by giving an

interpretation of the new constant symbol c. Since ∆ is finite there must be
.1 f
t
some least n such that the sentence c 6= n is not in ∆. Let cN = n for that n.
This is all that is required, so N |= ∆ and Γ is finitely satisfiable.
v1 ra
By compactness, there must be a model M such that M |= Γ. Fix such an
M.

Now we claim that M  N. Suppose that there was an isomorphic map σ

D

between M and ω (ω is the set of natural numbers). σ will need to be such

that every constant symbol a is such that σ maps aM to aN . For the Arabic
numbers there is only one thing we can do. We have

σ(0M ) = 0N
σ(1M ) = 1N
e

..
in

.
σ(nM ) = nN
nl

..
. .
O

But since M is such that for all n, M |= c 6= n, there is no place for σ to map
cM to in N. Thus σ fails the condition on constant symbols and M ∼ = N. 

C OROLLARY 124. It is not the case that if M ≡ N , then M ∼

= N.
 6.3. SUBMODELS & EMBEDDINGS 71

6.3. Submodels & Embeddings

We now consider some relationships between models which involve less sim-
ilarity. For simplicity, we shall only consider a language with function sym-
bols.

D EFINITION 125. Let M = hM, cM , ..., RM , ...i be a model of the language L =

{c, ..., R, ...}. N = hN, cN , ..., RN , ...i is a submodel of M, abbreviated N ⊆ M if:

• N ⊆ M (i.e., the domain of N is a subset of M );

• for every constant symbol c in L, cM = cN ; and
• for every n-ary relation symbol R in L, RN is the set of n-tuples
hm1 , ..., mn i where m1 , ..., mn ∈ N and hm1 , ..., mn i ∈ RM .

Essentially, to make a submodel of M, we just take objects away from the

c Toby Meadows

domain M of M.
We now consider the embedding relationship.
.1 f
t
D EFINITION 126. Let N and M be models of some language L. We say that
f embeds N into M, if there is some M0 ⊆ M such that f : N ∼
= M0 ; i.e., N
v1 ra
is isomorphic to a submodel of M.

6.3.1. Putting these notions to work. We now ask ourselves about the
D

impact of these relations: what does it mean for M to be a submodel of N ?

Well one thing we might want to know is what sort of things are true in both
M and N .
Suppose M and N are models of the language L = {P, Q} which we describe
as follows:
e

• M = {a, b};
in

• P M = ∅ (i.e., P M = {});
• QM = {a, b};
• N = {a, b, c};
nl

• P N = {a}; and
• QN = {a, b};
O

Clearly M ⊆ N .
Consider the sentence ∃xP x. Clearly this sentence is true in N : there is
some n ∈ N (i.e., a) such that n ∈ P N . However, it is not true in M.
 6.3. SUBMODELS & EMBEDDINGS 72

Now consider the sentence ∀xQx. It is true in M since everything in M is in

QM . On the other hand, N 2 ∀xQx since c ∈/ QN .
So the sentence beginning with ∃ was made false when we went down to a
submodel; and the sentence beginning with ∀ was made false when we went
up to a supermodel.
What about the other direction? What would happen to a ∃ sentence if we
went up to a supermodel? What would happen to a ∀ sentence if we went
down to a submodel?
To explore this, we give a formal definition of the kinds of sentences we are
interested in here.

D EFINITION 127. Let us say that a sentence ϕ is Σ1 (a ∃-sentence) if ϕ is of

the form ∃xψ(x) where ψ(x) is a formula with (at most) one free variable, x,
containing no quantifiers. Let us say that a sentence ϕ is Π1 (a ∀-sentence) if
c Toby Meadows

ϕ is of the form ∀xψ(x) where ψ(x) is a formula with at most one free variable,
x, containing no quantifiers.
.1 f
T HEOREM 128. SupposeM ⊆ N . Then, t
v1 ra
(1) If ϕ is Σ1 and M |= ϕ, then N |= ϕ;
(2) If ϕ is Π1 and N |= ϕ, then M |= ϕ.
D

To get this moving we need the following lemma.

L EMMA 129. Let ψ(x) be a formula without quantifiers with one free variable
and let M ⊆ N . Then let L(M ) be the expansion of L with constant symbols
for every member of M and M+ and N † be the appropriate expansions of M
and N . Then for all m ∈ M we have
e

M+ |= ψ(m) ⇔ N † |= ψ(m).
in

2
nl

P ROOF. It should be clear that the formulae of L(M ), which do not involve
quantification can be build up inductively in stages by simply omitting the
O

rules for the quantifiers. We thus proceed by induction on the complexity of

formulae in L(M ). It should also be clear that M+ ⊆ N † .
2
I’ve written N † to distinguish it from N + which we defined in week to as the expansion of
N which accommodates L(N ).
 6.3. SUBMODELS & EMBEDDINGS 73

(Base) Suppose that ψ(x) is atomic. For example, let ψ(x) be Rxc1 ...cn . Take
an arbitrary m ∈ M . Then we have

M+ |= Rmc1 ...cn ⇔ hmM , cM M

1 , ..., cn i ∈ R
M

⇔ hmN , cN N
1 , ..., cn i ∈ R
N

⇔ N + |= Rmc1 ...cn .

The first and third ⇔ are by the satisfaction definition; and the second ⇔
follows from the fact that M+ ⊆ N † .
(Induction step) To save space, we just work through the case for ¬ and ∧.
Suppose ψ(x) is of the form ¬χ(x). Then taking arbitrary m ∈ M , we have

M+ |= ¬χ(m) ⇔ M+ 2 χ(m)
⇔ N † 2 χ(m)
c Toby Meadows

⇔ N † |= ¬χ(m).
.1 f
t
We leave the explanation of the steps as an exercise.
Suppose ψ(x) is of the form χ(x) ∧ δ(x). Then taking an arbitrary m ∈ M , we
v1 ra
have

M+ |= χ(m) ∧ δ(m) ⇔ M+ |= χ(m) & M+ |= δ(m)

⇔ N † |= χ(m) & N † |= δ(m)
D

⇔ N † |= χ(m) ∧ δ(m).

We leave the explanation of the steps as an exercise. 

With this in hand the proof of the theorem is easy.

P ROOF. (of Theorem 128) We let L(M ) be the expansion of L with con-
e

stants for every elements of M and M+ and N † be expansion of the models

in

M and N with those new constant symbols interpreted appropriately.

(1.) Suppose ϕ is of the form ∃xψ(x) and M |= ∃xψ(x). Then there is some
nl

m ∈ M such that M+ |= ψ(m) and by Lemma 129, N † |= ψ(m) and so N |=

∃xψ(x).
O

(2.) Suppose ϕ is of the form ∀xψ(x) and N |= ∀xψ(x). Then for any m ∈ M ,
we have N † |= ψ(m) (we actually know something stronger than this, but this
is sufficient). Thus by Lemma 129, we see that for all m ∈ M , M+ |= ψ(m);
or in other words, M+ |= ∀xψ(x). 
 6.4. BASIC SET THEORY 74

R EMARK 130. So the moral of this story is that for very simple formulae,
• if we find a witness then that witness will still be in the bigger model;
and
• if everything in some domain satisfies the formula then this will still
be the case in a smaller model.

6.4. Basic Set Theory

Up until now we have been considering two kinds of models: finite models
and infinite models.
The size of a model is known as its cardinality. So if the domain has five
objects in it, then its cardinality is simply five. And so on for any other finite
cardinality.
When we come to an infinite model, perhaps constructed from an open
c Toby Meadows

branch we might be tempted to just say that its cardinality is infinite.

.1 f
t
But this presupposes that there is just one infinite cardinality.
In one of the bigger surprises in this history of mathematics, this assump-
v1 ra
tion (despite how reasonable it sounds) turns out to be false. We shall
demonstrate this and then examine its effect on our theory of models.

6.4.1. Cardinality. First we need to be more precise about what it means

D

to have a certain cardinality.

D EFINITION 131. Let us say that two collections A and B have the same
cardinality, which we abbreviate A ≈ B if there is some map f : A → B which
is a bijection.

Thus if A is a collection of five sheep and B is a collection of five ducks, then

e

there is a map f which takes each sheep to a duck such that:

in

(1) every duck d is such that there is a sheep s for which f (s) = d; and
(2) if s1 6= s2 are different sheep then they are mapped to different ducks
nl

(f (s1 ) 6= f (s2 ));

i.e., f is a bijection.
O

D EFINITION 132. We shall say that collection A has less than or the same
cardinality as B, abbreviated A ≺ B, if there is an injection between A and
B.
 6.4. BASIC SET THEORY 75

Thus if in the previous example there had been six ducks, we still could have
got a map with (2.) satisfied, but one duck would have to have been left out.
So we should be able to see that these definitions are in accord with our
intuitions about finite sets, but what about infinite ones. The following fact
should be obvious, but it is instructive to prove it from our definitions.

F ACT 133. Let E be the set of even numbers and O be the set of odd numbers.
Then E ≈ O.

P ROOF. To show this, it suffices to define a bijection between E and O.

Intuitively, we let f take the first even number to the fist odd number, the
second even number to the second odd number and so on. More formally,

f (2n) = 2n + 1.
c Toby Meadows

It should be clear that this is a bijection. 

The following fact may be more surprising.

.1 f
t
v1 ra
F ACT 134. Let E be the set of even numbers and ω be the set of natural
numbers. Then N ≈ E.

P ROOF. Again we define the bijection. Let f : N → E be such that

D

f (n) = 2n.

This is clearly a surjection: every even number is output. Moreover it is an

injection. Suppose not. Then there would be some even e such that for some
m 6= n,
e

f (m) = e = f (n).
in

But then 2m = 2n and m = n: contradiction. 

nl

This might be surprising given that finite collections A and B is A is a proper

subset of B, A ( B (i.e., A ⊆ B but A 6= B), then A ≺ B. This is not always
O

the case with infinite collections.

[Link]. Enumeration. We shall say that a collection A is countable if N ≈
A; i.e., if there is a bijection f between N (the natural numbers and A). We
shall say that f enumerates A since that’s exactly what it does.
 6.4. BASIC SET THEORY 76

6.4.2. Cantor’s theorem - the are larger infinities. We are not ready
to prove that there is more than one size of infinite collection. This is known
as Cantor’s theorem.
The proof doesn’t take that long, but we’ll go through it somewhat informally
to make it as clear as possible.
Suppose we had countably many one pound coins (a pleasant thought) and
we lined them all up in a row. Each coin would either be heads-up or tails-
up. Remember that since we have countably many coins, this means we
can enumerate them with a function from N to the coins. Let us call this
function c.
We may then represent this situation in a table as follows:
c(0) c(1) c(2) c(3) c(4) c(5) c(6)
H H T H T H H ...
c Toby Meadows

Now of course there are different ways that the coins could have been laid
out. For example we might switch the third coin c(2) from tails to heads.
.1 f
t
Let us then consider the table which would result by placing each different
arrangement of the coins in new rows of the table. Thus we get something
v1 ra
like:
c(0) c(1) c(2) c(3) c(4) c(5) c(6) ...
H H T H T H H ...
T T T T T T T ...
D

H T T H T T H ...
T H T T T H H ...
.. .. .. .. .. .. .. ...
. . . . . . .
We won’t worry about the order in which the rows are filled in. We just want
to ensure that every (infinite) arrangement of heads and tails is represented
e

on exactly one row of the table.

in

Now our claim is that there are more rows than there are columns. Since
there are infinitely many columns, this will suffice to show that there is more
nl

than one size of infinite collection.

So what does it mean for there to be more rows than columns? Since we
O

know that the columns are countable, it will suffice to show that the rows
are not countable. In order to do this, we must show that there is no bijective
function r from the naturals to the rows, which provides an enumeration of
them.
 6.4. BASIC SET THEORY 77

We shall demonstrate this by reductio. Thus, suppose that there was such
an enumeration. Let us call it r. We might then represent this situation as
follows:
c(0) c(1) c(2) c(3) c(4) c(5) c(6) ...
r(0) H H T H T H H ...
r(1) T T T T T T T ...
r(2) H T T H T T H ...
r(3) T H T T T H H ...
.. .. .. .. .. .. .. ..
r(4) . . . . . . . .
To show that r cannot enumerate all of the rows, we are going to construct
a row r† that the enumeration r must miss. This is an arrangement of the
coins.
We let r† be the row constructed by flipping every coin down the diagonal of
c Toby Meadows

our table. So looking at the table above we get:

r(0) T H T
.1 f
H T H H ...t
c(0) c(1) c(2) c(3) c(4) c(5) c(6) ...
v1 ra
r(1) T H T T T T T ...
r(2) H T T H T T H ...
r(3) T H T H T H H ...
.. .. .. .. .. .. .. ...
r(4) . . . . . . .
D

Or more formally, we let r† be such that the nth column of r† is:

• heads if the nth column of the nth row is tails; and

• tails if the nth column of the nth row is heads.
e

Now if r† was in the enumeration, then there would have to be some n such
that r(n) = r† . But this is not possible. We have defined r† so that it is differ-
in

ent from every r(n) at exactly one place. Thus there can be no enumeration
of the rows and there is a infinite cardinality which is not countable. We call
nl

such sizes uncountable.

O

R EMARK 135. More informally, we observe that if there had been the same
number of rows as columns, then the table above would be an infinite
square. We have shown that there must always be an extra row beyond
this.
 6.5. LÖWENHEIM-SKOLEM THEOREMS 78

[Link]. This also tells us ... Consider each of the rows of the table. There
is a sense in which each of them represents a particular subset of the natu-
ral numbers.
For example,
c(0) c(1) c(2) c(3) c(4) c(5) c(6)
r(0) H H T H T H H ...
the 0th row could pick used to pick out the set

{0, 1, 3, 5, 6, ...}.

We simply take the set be numbers of those coins which are facing heads-
up. Moreover it should be clear that every set of natural numbers will be
represented by exactly one of these rows.
Thus we have shown:
c Toby Meadows

C OROLLARY 136. There are more sets of natural numbers than there are nat-
ural numbers.
.1 f
t
ra
Moreover, it is possible to represent any real number by an infinitely long
decimal number. We might then replace the coins in the example by a 10-
sided dice. Then each of the rows could represent a real number between 0
and 1. We can then perform much the same trick as before to show that:
D

F ACT 137. There are more real numbers than natural numbers.
v1

The sizes of sets does not stop here either. We can repeat a (slightly more
general) version of our argument above with the coins to get a collection
which is even larger than the sets of all sets of natural numbers. Indeed we
can repeat this indefinitely.
e

A full discussion of this topic would open us up in to the world of set theory
in

and the transfinite.

nl

6.5. Löwenheim-Skolem Theorems

O

But we are going to return to our discussion of models and consider what
impact cardinality has upon it. Our target question here is going to be:
• Given a theory T (i.e. a set of sentence) which has a model M will
there be other models N which have different cardinalities?
 6.5. LÖWENHEIM-SKOLEM THEOREMS 79

The answer to this question comes in two theorems which show that in
terms of cardinality, there is a massive amount of freedom here.

T HEOREM 138. (Downward Löwenheim-Skolem Theorem) Let T be a countable

theory and M be a model of T of arbitrary cardinality. Then T has a countable
model.

P ROOF. By soundness, since T has a model it is consistent. Then by the

techniques of our completeness proofs we may construct a model which has
a countable domain. 

T HEOREM 139. (Upward Löwenheim-Skolem Theorem) Let M be an infinite

model such that M |= T and let A be a set such that M ≺ A. Then there is
some N such that N ≈ A and N |= T .

In other words, given a model M of some theory and any larger set A, we
c Toby Meadows

can find another model N of T which is the same size as A.

.1 f
t
P ROOF. Let us expand the language L with a constant symbol ca for every
element a ∈ A. Then we let S be the theory consisting of those sentences in
v1 ra
T and in the set
{ca 6= cb | a, b ∈ A a 6= b}.
Clearly, every finite subset of S is satisfiable. Thus S is satisfiable in some
D

model N + . Since every one of the constant symbols denotes a different

element of N + , we have N + ≈ A. Let N be the reduct of N + back to the
language L. Clearly N |= T . 
e
in
nl
O
 6.6. EXERCISES 80

6.6. Exercises

E XERCISE 140. Show that if M ∼

= N , then M ≡ N .

E XERCISE 141. If M ≡ N , what can you say about T h(M) and T h(N )?

E XERCISE 142. In Definition 125, we avoided function symbols in our defi-

nition. What do you think would be the appropriate condition to place here?
[Note that we want the submodel to be a genuine model and so functions
must work properly. Ensuring this may involve changing other parts of the
submodel definition.]

E XERCISE 143. Explain how each of the ⇔’s are justified in Lemma 129.

E XERCISE 144. Show using counterexamples that Theorem 128 would have
failed if we had used arbitrary sentences beginning with ∃ and ∀ respectively.
c Toby Meadows

P ROBLEM 145. A theory Γ is a set of sentences which is closed under the

t
consequence relation; i.e., if Γ |= ϕ, then ϕ ∈ Γ. Suppose Γ and ∆ are both
theories. For each of the following statements, either prove it or refute it
.1 f
with a counterexample:
v1 ra
(1) {ϕ | ϕ ∈ Γ ∨ ϕ ∈ ∆} is a theory; and
(2) {ϕ | ϕ ∈
/ Γ} is a theory.
D

P ROBLEM 146. Let L be a language with a finite number of relation, function

and constant symbols. Show that the set of well-formed formulae of this
language is countable.

P ROBLEM 147. It is possible to formulate a theory of sets in first order logic.

In this theory, we can prove Cantor’s theorem and thus show that there are
uncountable collections of sets. However, since the theory is formulated in
e

first order logic we can also show that it has a countable model. What is
in

going on here?
nl
O
 Part 2

Recursion & Incompleteness

c Toby Meadows

.1 f
t
v1 ra
inDe
nl
O
 CHAPTER 7

Recursion theory 1

In the first half of the course, we almost ignored the case of functions when-
ever they were distracting. In this half of the course, functions are going to
play the starring role.
Recursion theory is the study of functions which are computable. Infor-
mally speaking, these are the functions which we compute in the sense that
given the inputs of the function there is some set of rules for the calcu-
lation/construction such that after a finite amount of time (and perhaps
c Toby Meadows

paper) we can figure out the answer.

.1 f
t
You might have thought that every function should be computable. We shall
discover next week that this is not the case. Before we get to that we need
to make very precise just what it means for a function to be computable.
v1 ra
To do this we shall introduce the concept of recursiveness and device of the
Turing machine.
D

7.1. Algorithms & Turing Machines

D EFINITION 148. An algorithm is simply a set of rules which govern the way
we perform some calculation.

Less formally, an algorithm is just a set of instructions that we follow in

e

order to perform a calculation. An algorithm is different from the function,

in

the calculation for which it provides instructions. For example, consider the
function of addition. There may be many different ways (i.e., algorithms) of
calculating that function, but the function itself (i.e., addition) remains the
nl

same.
A Turing machine give us a canonical way of recording those instructions.
O

The set up is very simple.

• Image that you have an infinitely long piece of tape that is divided
up into squares which we call cells.
82
 7.1. ALGORITHMS & TURING MACHINES 83

• Each of the squares is either blank or has the numeral 1 printed in

it.
We might represent this as follows:
1 1 1 1 1 1
The Turing machine has something called a head. This is, in a sense, where
the calculation is being done.
At any particular point in the calculation, the head is:
• sitting above a particular cell;
• in a particular state, q1 , which tells it what to do next.
We might indicate this as follows:1
1 1 1 1 1 1
qˆ1
c Toby Meadows

At a particular state it will be read what is on the cell below it and depending
on what the cell has in it, the machine must:
.1 f
• move either one cell to the left or right; or t
• place a 1 in the cell below or make it blank; and then
v1 ra
A calculation will terminate or halt when the instructions do not have any-
thing more for it to do.
An example will probably provide the easiest way to see how this might work.
D

E XAMPLE 149. Let us suppose that our tape is such that the only non-blank
cells are a finite string of 1’s, of say length 4 and that the head of the Turing
machine sits under the leftmost 1.
1 1 1 1
qˆ1
e

This gives us the initial condition of the tape. Now let us define an algorithm
in

which the Turing machine will perform. Let us say that we want to make
the tape blank. What needs to happen?
nl

Essentially, we need to move along to the right blanking out all of the ones.
After that we can stop. So let us propose the following instructions:
O

• In state q1 if the cell has a 1 in it, then

– change it to a blank;
1
Note that the square above the q0 is wider than the others for no reason other than type-
setting.
 7.1. ALGORITHMS & TURING MACHINES 84

– move to the right; and

– stay in state q1 .
• In state q1 if the cell has a 0 in it, then
– leave it as a blank (blanking a blank cell leaves a blank)
– move one cell to the left (it doesn’t really matter); and
– change to state q2 .
We can step through the instruction as follows:
1 1 1 1
qˆ1
1 1 1
qˆ1
1 1
qˆ1
c Toby Meadows

1
qˆ1
.1 f
qˆ1 t
v1 ra

qˆ2
Now at the final line, observe that head is in stage q2 . However, we do not
D

have any further instruction regarding what we should do in stage q2 , so the

calculation halts at this point.

7.1.1. A Notation System. Observe that the instructions given above

for this machine took up a lot of space to convey relatively little information.
All we needed to know was what do in each stage given a certain condition
e

of the tape. This can be summarised in a 5-tuple.

in

In state if the cell is an then change it to a move to the and go to stage

q 1/− 1/− L/R q0
nl

In this way we could re-write the instructions above by simply writing:

• q1 1 − Rq1
O

• q1 − −Lq2 .
We shall continue to adopt this system when describing Turing machines.

7.1.2. More Turing machines.

 7.1. ALGORITHMS & TURING MACHINES 85

[Link]. Do Turing machines always halt? An obvious question we might

have is whether every Turing machine must come to a halt. This is not the
case as we can easily illustrate. Let us take the machine above and make a
seemingly trivial modification.
• q1 1 − Rq1
• q1 − −Lq1 .
We stipulated that the rest of the tape was blank so the machine will simply
keep working its way to the left and since the tape is infinite the tape it will
never halt.
[Link]. Some simple arithmetic functions. The function we considered
doesn’t do anything interesting. Let us now try to represent a couple of
functions from arithmetic.
To do this we need some agreed way of representing natural numbers on
c Toby Meadows

the tape. Let us represent the number n by n + 1 many consecutive 1’s on

t
the tape. And if n is the output of the function, let us represent this fact by
having the head of the machine come to a halt over the leftmost 1. Thus if 3
.1 f
were the output of some machine, then this would be represented as:
v1 ra
1 1 1 1
qˆ1
Now say that we wanted to define a function which added two numbers
D

together. We then need to able to present more than one number to the
Turing machine. To represent some n-tuple hm1 , ..., mn i, we shall place
• m1 + 1 many 1s
• followed by a blank
• and then
• m2 + 1 many 1s
e

• followed by a blank and

in

• ...
• finally mn + 1 many 1s
nl

along the tape. Thus h3, 4i would be represented as:

1 1 1 1 1 1 1 1 1
O

qˆ1
where the calculation begins in state q0 .

E XAMPLE 150. (+1) This function takes a number and adds 1 to it.
 7.1. ALGORITHMS & TURING MACHINES 86

• q1 11Rq1
• q1 − 1Lq2
• q2 11Lq2
• q2 − −Rq3
The idea is that we go to then end of the row, add a new one and then turn
back.

E XAMPLE 151. (m + n) This function takes two values and returns their sum.

• q1 11Rq1
• q1 − 1Rq2
• q2 11Rq2 2
• q2 − −Lq3
• q3 1 − Lq4
c Toby Meadows

• q4 1 − Lq5
• q5 11Lq5
• q5 − −Rq6
.1 f
t
The idea here is that we go through the tuple changing the blank between m
v1 ra
and n into a one. Then we reach the right end, pull two 1’s off it and return
to the left.
Instead of writing qn 1 − qm , we shall now write: n 1 - m. Call this streamlined
D

notation.

E XAMPLE 152. This function takes a number n and returns the tuple hn, ni.
111R1
1--L2
211L3
e

311R4
in

41-R5
5--R6
nl

6-1L7
7--L7
O

711L8
811R9
9 1 - R 10
 7.2. GÖDEL’S SCHEMA 87

10 - - R 10
10 1 1 R 11
11 1 1 R 11
11 - 1 L 12
12 - - L 12
12 1 1 L 13
13 1 1 L 13
13 - - L 7
8 - - R 14
14 1 1 R 14
14 - 1 R 15
15 - 1 R 15
c Toby Meadows

15 1 1 L 16
16 1 - R 17
17 1 1 R 17
.1 f
t
v1 ra
17 - 1 L 19
19 1 1 L 19
19 - - L 20
D

20 1 1 L 20
20 - - R 25

3 - - R 25
The idea here is basically a lot of zig-zagging.
e
in

7.2. Gödel’s schema

We now define an alternative way of describing algorithms which can be

nl

used to calculate functions. As we have seen the Turing machine system

is extremely cumbersome for the purposes of describing often quite simple
O

functions.
The next approach was developed by Gödel. It is much easier to define
function using this technique, although the relationship with the intuitive
notion of computability is probably less obvious.
 7.2. GÖDEL’S SCHEMA 88

It will turn out that each of these methods of describing algorithms is able
to produce the same function.
This time we are going to build up algorithms using:

• basic functions; and

• rules for taking one function to another.

Any function that can be defined in this way is said to be a recursive func-
tion.
This should be familiar. This is another example of a definition by recur-
sion, although the sense of recursion is slightly different in the case of the
definition.
c Toby Meadows

7.2.1. Basic functions.

[Link]. Notation. We shall write f : ω → ω to mean that f is a function
.1 f
t
which from the natural numbers (ω) to the natural numbers. We shall write
f : ω n → ω to mean that f is a function which takes n-tuples of natural
v1 ra
numbers and returns a natural number. We shall write f : ω + ω (and
f : ω n + ω) to indicate that f is a partial function taking natural numbers
(n-tuples of natural numbers) to natural numbers. It is partial in the sense
D

that it may not be defined for every natural numbers (n-tuple of natural
numbers); i.e., its domain may be a proper subset of ω (dom(f ) ( ω).
We shall call the functions defined using the schema below, Gödel recursive
functions.

(1) The zero function, z m : ω m → ω is such that z m (hn1 , ..., nm i) = 0 for all
e

n1 , ..., nm , m ∈ ω.
in

(2) The successor function s : ω → ω is such that s(n) = n + 1.

(3) The projection function πkm : ω m → ω is such that for n1 , ..., nm with
k≤m
nl

πkm (hn1 , ..., nm i) = nk .

O

None of these function is particularly exciting. They are just the basic cases.

R EMARK . We shall also include a z 0 function which is the zero-place version

of z n . It takes no arguments (at all) and always returns the value 0.
 7.2. GÖDEL’S SCHEMA 89

7.2.2. Rules for making new functions. There are three processes for
taking recursive function and constructing more complex recursive func-
tions:
(1) Composition;
(2) Primitive recursion; and
(3) Minimisation.
[Link]. Composition. Suppose we have Gödel recursive f : ω m + and
g1 , ..., gm : ω k + ω. Then there is a Gödel recursive function h : ω k + ω such
that

h(hn1 , ..., nk i) = f (hg1 (n1 , ..., nk ), ..., gm (n1 , ..., nk )i).

R EMARK 153. The idea of this function is that it allows us to compose func-
c Toby Meadows

tion so that we may apply the result of a function the result of another
function. .1 f
t
[Link]. Primitive recursion. Suppose we have Gödel recursive f : ω m + ω
and g : ω m+2 + ω. Then there is a Gödel recursive function h : ω m+1 + ω such
v1 ra
that

h(h0, n1 , ..., nm i) = f (hn1 , ..., nm i)

D

h(hk + 1, n1 , ..., nm i) = g(hh(hk, n1 , ..., nm i), k, n1 , ..., nm i).

This one arguably looks more complicated than it really is. An example
might help.

E XAMPLE 154. Let’s define addition. First we observe the following facts
e

about addition:
in

0+n = n
nl

(k + 1) + n = (k + n) + 1.
O

Both of these should be obvious. Moreover, we see that this is quite close to
the form that we have above. The main thing we need is a function which
takes a number an adds 1 to it. And we have one of these: the successor
function. So we get something like this.
 7.2. GÖDEL’S SCHEMA 90

plus(h0, ni) = π11 (hni)

plus(hk + 1, ni) = s(π13 (hplus(k, n), k, ni)).

To emphasise that we are defining addition we write it as a function out the

front of two arguments.
Observe that we have used both composition and primitive recursion to de-
fine this function.

[Link]. Minimisation. Given a Gödel recursive function f : ω m+1 + ω,

there is a Gödel recursive g : ω m + ω such that

g(hn1 , ..., nm i) = the least k such that f (hn1 , ..., nm , ki) = 0

and for all l < k f (hn1 , ..., nm , li) is defined.
c Toby Meadows

Any function that can be described from the basic functions using these
rules is a a Gödel recursive function.
.1 f
t
R EMARK 155. Note that this kind of minimisation is not the one which takes
v1 ra
a tuple hn1 , ..., nk i and returns the least element of that tuple.

7.2.3. Some examples of functions.

E XAMPLE 156. Let’s define the function from Week 1 which took a number n
D

and returned the triangular number with side n. I.e., we want the function
f : ω → ω such that
f (n) = n + (n − 1) + ... + 1.
(We shall take it that f (0) = 0.)
Now we can think of this function as being calculated in stages as follows:
e
in

f (0) = 0
nl

f (n + 1) = (n + 1) + f (n).

This has the right kind of shape for primitive recursion. From here, we can
O

then represent it in the proper notation as follows:

tria(0) = z 0
tria(n + 1) = f (htria(n), ni)
 7.2. GÖDEL’S SCHEMA 91

where
f (n, m) = plus(hn, s(m)i).

Note that in defining this function, we have used the function plus which we
have already defined.

E XAMPLE 157. Let us define a function pre : ω → ω which takes a number

n + 1 and returns its predecessor n if there is one and 0 otherwise. Then we
want something like this:

pre(0) = z 0
pre(n + 1) = g(hpre(n), ni)

where g(m, n) = π22 (hm, ni) = n.

E XAMPLE 158. Let us define a function sub : ω 2 → ω which takes n and m and
c Toby Meadows

returns m − n if it is defined and 0 otherwise. We define this as follows:

.1 f
t
sub(h0, mi) = π11 (hmi) (= m)
sub(hk + 1, mi) = g(hsub(hk, mi), k, mi)
v1 ra
where g(hv, u, wi) = pre(Id31 (hv, u, wi) = pre(v).

E XAMPLE 159. Let’s define the function squ : ω → ω which takes a number
D

and squares it. Getting started, we note that

02 = 0

and that
(n + 1)2 = n2 + 2n + 1.
e

E XAMPLE 160. So we can put this into the notation as follows:

in

squ(0) = z 0
nl

squ(n + 1) = f (hsqu(n), ni)

where f : n2 → n is such that

O

f (hn, mi) = plus(hn, plus(hplus(hm, mi), 1i)i)

We can also represent relations using functions defined by algorithms.

 7.2. GÖDEL’S SCHEMA 92

E XAMPLE 161. We define a function gr0 : ω → ω which takes n and returns

the value 1 if n is greater than 0 and 0 otherwise. We define this as follows:

gr0(n) = sub(hpre(n), ni).

E XAMPLE 162. Let gre(m, n) be the function which returns 1 if n is greater

than m and 0 otherwise. We use the sub function and composition to get:

gre(hm, ni) = gr0(sub(hm, ni).

c Toby Meadows

.1 f
t
v1 ra
in D
e
nl
O
 7.3. EXERCISES. 93

7.3. Exercises.

E XERCISE 163. Step through the first 26 steps of the calculation of the func-
tion in Example 152 given starting condition.

1 1
qˆ1
E XERCISE 164. Write a Turing machine which doubles a number n. Use the
notation system of Example 152. Do not use state 0.

E XERCISE 165. (Harder - well ... tedious) Write a Turing machine which
takes two numbers m and n and returns their product.

E XERCISE 166. Using the Gödel notation, describe an algorithm represent-

ing a function times : ω 2 → ω which take m and n and returns m × n.
c Toby Meadows

E XERCISE 167. Using the result from Week 1, define an alternative algorithm

have already defined.)

.1 f
t
which gives triangular numbers. (You may use other functions which we
v1 ra
E XERCISE 168. Using the Gödel notation, describe an algorithm which rep-
resents a function exp : ω 2 → ω which takes m and n and returns mn .

E XERCISE 169. Using the Gödel notation, describe an algorithm which rep-
D

resents a function f ac : ω → ω which takes a number and returns n! (i.e.,

n × (n − 1) × ... × 2 × 1).

E XERCISE 170. Using Gödel notation, define a function geq : ω 2 → ω which

takes m and n as arguments and returns 1 if n is greater than m and 0
otherwise.
e

E XERCISE 171. Using Gödel notation, define a function equ : ω 2 → ω which

in

takes m and n and returns 1 if they are equal and 0 otherwise.

nl
O
 CHAPTER 8

Recursion theory 2

8.1. Equivalence of Turing machines with Gödel schema

Last week, we looked at two ways of formalising our intuitive idea of compu-
tation. On the one hand, we looked at Turing machines which were based
on extremely simple rules; and on the other, we looked at the Gödel schema
system which provided an elegant means of representing common functions
from the theory of arithmetic.
c Toby Meadows

To start this week off, we are going to provide an outline of the proof which

t
shows that these two systems are, in some salient sense, equivalent. This
is interesting since it shows us that two, seemingly quite different, means of
.1 f
formalising computation actually end up doing the same thing.
v1 ra
We only provide a sketch because the full details of the proof are quite te-
dious and lengthy.
The first thing we need is a way of comparing the two systems. At face
D

value, this isn’t going to be possible. Turing machines talk about lengths of
tape, while the Gödel schema are concerned with functions on the natural
numbers.

8.1.1. Numbers for Turing machines. Last week, we saw a way of rep-
e

resenting numbers and tuples using a tape representation. This gets us on

in

our way to representing Gödel functions using Turing machines: we have,

so to speak, the matter for our calculation.
nl

In addition to this, we need some way of coding up the functions we can

represent using Gödel schema. Suppose we had some function f : ω n → ω
O

defined using the Gödel schema. Our goal is to find a means of representing
this situation as the starting condition on the tape.
You have probably noticed that constructing Turing machines relies a lot on
counting sequences of blank squares. For example, when we get to the end
94
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 95

of a tuple representation we can tell that this has occured because we have
more than one consecutive blank square.
With this is mind, we might make a few modications to our representations
of tuples an numbers so that we can get a clearer representation of the
syntax of the Gödel schema.
So first of all, we are going to need some way of representing the primitive
symbols of the Gödel schema. Thus we need ways of representing:

• zm;
• s; and
• πkn .

Moreover, we also need to represent the operations which allow us to build

more complicated functions using:
c Toby Meadows

• composition;
• primitive recursion; and
• minimisation.
.1 f
t
v1 ra
Intuitively speaking, this kind of stuff is obviously different from numbers
and tuples. So it would be convenient if we had a simple way of discerning
the two.
[Link]. A different way of representing numbers and tuples. So our goal
D

here is to make a coding that clearly distinguishes numbers and tuples from
symbols. We are going to make use of multiple blanks for this purpose.
Let us represent a number n on the tape by writing a 1 followed by a blank
and then n + 1 many 1’s after that. So the following diagram represents the
number 2.
e

1 1 1 1
in

qˆ1
Let us represent a tuple of length m by placing a sequence of m number
nl

representations each separated by 2 blank cells. Thus the following situation

represents the tuple h2, 1i.
O

1 1 1 1 1 1 1
qˆ1
So this makes things a little more complicated for representing numbers,
but in the end it will be easier to represent the Gödel schema.
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 96

[Link]. A way of representing Gödel schema. Now for every m we know

that we have a function z m : ω m → ω which takes a tuple of length m and
always returns the value 0.
We shall represent this by 2 cells containing 1 followed by a blank followed
by n-many 1’s. Thus we would represent the function z 2 by the following:
1 1 1 1
qˆ1
Now we really want to represent the situation when this function is applied
to some tuple. To do this we shall place the code of the function to the left
of the representation of the tuple with two blank cells between them. Thus
we migh represent z 2 (h1, 1i) as follows:
1 1 1 1 1 1 1 1 1 1
qˆ1
c Toby Meadows

In a similar fashion, we represent the function s : ω → ω by placing three 1’s

consecutively on the tape. Since the s function only deals with arity 1, there

1 1 1
.1 f
t
is no need to deal for further information. Thus we represent it as follows:
v1 ra
qˆ1
And we can represent that function applied to the number 1 as follows:
1 1 1 1 1 1
D

qˆ1
Next we represent the projection function πkn : ω n → ω. We do this by placing
4 1’s on the tape followed by a blank followed by n 10 s followed by a blank
followed by k 1’s. Thus we would represent πk2 (h2, 1i) as follows:
1 1 1 1 1 1 1 1 1 1 1 1 1 1
qˆ1
e

So we now have a way of represting all of the basic function from the Gödel
in

schema. We now describe how to represent the processes for constructing

more complex recursive functions.
nl

We start with composition. So suppose we have f : ω m + ω and g1 , ..., gm :

ω k + ω. Then by the composition rule, we know there is a recursive function
O

h such that:

h(hn1 , ..., nk i) = f (hgm (hn1 , ..., nk i), ..., gm (hn1 , ..., nk i)i).

In order to represent this, it should be clear that all we need is to:

 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 97

(1) represent the arity m;

(2) represent the arity k;
(3) represent the function f ; and
(4) represent each of the functions g1 , ..., gm .
So let us represent composition by placing 5 1’s, then a blank followed by:
(1) m 10 s followed by a blank; then
(2) k 10 s followed by 2 blank cells; then
(3) the representation of the function f followed by 2 blanks; then
(4) for each 1 ≤ i ≤ m, the representation of gi each separated by 2 blank
cells.
Thus, in general a composition will look like:
1 1 1 1 1 1 -n many- 1 1 -k many- 1 f ’s rep g1 ’s rep gm ’s rep
qˆ1
c Toby Meadows

Now we represent primitive recursion in a similar fashion. Suppose we have

such that:
.1 f
t
f : ω m + ω and g : ω n+2 + ω. Then there is a recursive function h : ω m+1 + ω
v1 ra
h(h0, n1 , ..., nm i) = f (hn1 , ..., nm i)
h(hk + 1, n1 , ..., nm i) = g(hh(hk, n1 , ..., nm i), k, n1 , ..., nm i).

We represent such an h by placing 6 10 s on the tape followed by a blank

D

followed by:
• m many 1’s followed by 2 blanks; then
• the representation of the function f ; then
• the representation of the function g.
Thus in general, the tape will look like the following diagram.
e

1 1 1 1 1 1 1 -m many- 1 f ’s rep g’s rep

in

qˆ1
And finally we come to minimisation. Suppose we have a recursive function
nl

f : ω m+1 + ω. Then we know that there is a recursive function

g(hn1 , ..., nm i) = the least k such that f (hn1 , ..., nm , ki) = 0.

O

We represent such a g by placing 7 10 s on the tape followed by a blank and

then:
• m 1’s followed by 2 blanks; then
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 98

• the representation of g.

Thus, in general a representation of the minimisation function will look like

this:
1 1 1 1 1 1 1 1 -m many- 1 g’s rep
qˆ1
So we now have a way of representing any function that can be defined using
the Gödel schema and the tuple that is fed into such a function. Unfortu-
nately, this is just the beginning of the job.
[Link]. Completing the proof. With this representation, we have the scene
set for completing the proof. As you can see, just setting things up takes up
a reasonable amount of space. So we’ll satisfy ourselves here, by sketching
what needs to be done.
Now what we want to show here is that a Turing machine can calculate
c Toby Meadows

any function that can be calculated using the Gödel schema. We now have

t
a means of representing any function constructed using the Gödel schema
and in order to present an argument tuple to it, we simply place that tuple
.1 f
two blank cells after the representation of the function.
v1 ra
In order to complete the proof we need to construct a Turing machine which
takes:

• the representation of a Gödel schema algorithm; and

D

• a tuple of numbers,

and then calculates what that Gödel schema algorithm would have done.
So to do this we “simply” need to build a function that will:

• recognise which Gödel schema rules or basic function is being em-

e

ployed; and then

• run that function.
in

The recognition part is easy. We simply construct a Turing machine which

recognises how many 1’s are at the beginning of the code as this is how we
nl

tell which part of the Gödel schema has been used. For example, we might
start as follows:
O

111R2
211R3
311R4
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 99

411R5
511R6
611R7
711R8
8 1 1 R halt ; So we halt if there are more than 7 1’s as we don’t allow for
this in the code.
2 1 1 R halt ; We also halt if there is only 1 1, since then we don’t have a
function code.
3 - - R 31 ; This was the code (i.e. 2 1’s) for the z m function, so we now run
that code.
...
4 - - R 41 ; This was the code (i.e., 3 1’s) for the s function, so we now run
c Toby Meadows

that code.
...
...
.1 f
t
8 - - R 81 ; This was the code for the minimisation function, so now we run
v1 ra
that code.
We now describe how to run the successor function (basically since it’s the
easiest). So suppose we have just gone to state 4 having passed 31’s. We are
D

now in state 41. We then proceed as follows:

41 - - R 42 ; There should be two blanks in between the function and its
argument.
42 1 1 R 42 ; We go right until we reach the end of the row of 1’s.
42 - 1 L 43 ; We then place a 1 in the blank cell and move to the left.
e

43 1 1 L 43
in

43 - - R halt ; We reach the end of the 1’s and halt under the leftmost one of
them.
nl

The z m function is similarly easy to describe.

For the rest of the functions we shall content ourselves with a high-level
O

description of how to construct the machine:

• Projection (πkn ): We read across to the k-sequence of 1’s and then go
back and forth erasing an element of k and an element of the tuple
until we reach the k th element. We then use the n-sequence to erase
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 100

the rest of the tuple. Finally we zig-zag the k th element of the tuple
back to the starting point.
• Composition: We may need some space for this calculation. Thus
for each of the gi where 1 ≤ i ≤ m, we take gi ’s code and a copy of the
tuple n̄ and place them to the right of the initial setup. We then run
gi on n̄. We then leave the output to the right and repeat for each
of the inputs until we have a new tuple. We move this tuple into
position so that we can apply f to it; and we do this.
• Primitive recursion: This is definitely the ugly one. In some sense,
it’s just a more general version of the multiplication algorithm you
have already constructed. Remember that primitive recursion is de-
signed, loosely speaking, so that we can perform k many repetitions
of a certain calculation. Thus we shall keep on, so to speak, unfold-
ing the calculation to the right which will (eventually) reduce the k
c Toby Meadows

parameter to 0, at which point we may apply the f function and get

t
an output. We then work backwards to the left, putting the input
back through the g function until we get to the beginning again and
.1 f
that gives us our output.
v1 ra
• Minimisation: This time we just keep running the function f on
successively greater inputs. A tally will need to be kept somewhere
to the right on the tape. At each stage we check whether the output
D

is 0. If it is, then the tally is our output and we rearrange the tape
accordingly. If we never reach such a point, then the calculation will
not halt.

Now the full proof of this would take up a great deal more space. Moreover,
I don’t want to trivialise that activity, but (hopefully) you should be able
e

to see that the task can be completed. You should know enough about
in

Turing machines to see that this would be a challenge but one that can be
completed. I won’t set this as an exercise, although it’s certainly a good
thing to try to do at some point.
nl
O

8.1.2. Tapes for Gödel schema. Now we want to show the converse of
the above. We want to show that anything that can be done using a Turing
machine can also be done with the Gödel schema. Again, we’ll only lay the
groundwork for the proof here.
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 101

[Link]. A way of representing Turing machines. As before, our initial

problem is finding a way of comparing the two approaches. This time we
need some way of representing the tape of the Turing machine using the
natural numbers. There is a very simple way of doing this.
Suppose we hade a tape and head in the following position:
1 1 1 1 1 1
qˆ1
We could represent this situation by the number:

10111011

Thus, we take the head and then work our way t the right using a 1 to
represent a 1 on the tape and using a 0 to represent a blank.1 However,
it will actually be convenient to reverse the direction of the representation.
c Toby Meadows

Thus we shall code the tape above as:

.1 f 11011101
t
v1 ra
So that gives us a way of representing the tape. We now need to represent
the instructions for the Turing machine. The technique we use is known as
Gödel coding. We shall be using this technique again next week and the
week after that.
D

The essential idea we rely on is the following basic fact from number theory:

F ACT 172. Every natural number n is such that it has a unique prime decom-
position; i.e., there is a unique set of prime numbers p1 , ..., pm and k1 , ..., kn ≥ 1
such that:
e

n = pk11 × ... × pkmm .

in

A couple of examples might make this clearer. Consider the number 63. It
should be easy to see that:
nl

63 = 9 × 7
O

32 × 7.

1
Note that we can only represent finite sequences using this technique. To represent infinite
sequences, we’d need the real numbers and we have not designed our Gödel schema to deal
with them.
 8.1. EQUIVALENCE OF TURING MACHINES WITH GÖDEL SCHEMA 102

Consider the number 48. Clearly, we have

48 = 6 × 8
= 3 × 2 × 23
= 3 × 24

We shall represent a set of instructions for a Turing machine in two stages:

(1) we represent each of the lines; then
(2) we put all the lines together.
A typical line of Turing machine instructions will be of the form:
n??Dm
where n and m are natural numbers; ? is either 1 or −; and D is a direction
(either L or R). First we need to represent all the parts as natural numbers.
c Toby Meadows

Let us represent blank by 2; L by 1 and R by 2. Then a line like:

34 1 - R 45
would be represented as follows:
.1 f
t
v1 ra
34 1 2 2 45.
Using Gödel coding we may represent this as follows:
234 × 31 × 52 × 745 .
D

Essentially we go through use the first four prime numbers to code up the
line. It will give us a very big number, but, most importantly, it’s a number
from which we can recover the instructions.
To represent a sequence of lines of code, we simpy repeat the trick. Sup-
pose we have some lines of instructions such that their code is given in the
following table:
e

Instruction Code number

in

46 1 2 2 78 c1
67 1 1 1 98 c2
nl

...
98 1 2 1 23 cm
O

We then represent this sequence (c1 , ..., cm ) of code numbers by:

2c1 × 3c2 × ... × pcmm

where pm is the mth prime number.

 8.2. THE CHURCH-TURING THESIS 103

Thus we now have a way of representing the algorithm (instructions) for a

Turing machine as well as its tape.
[Link]. Completing the proof. Now this time, we want to define a function
using the Gödel schema which takes a code for a tape and a code number
for a Turing machine and returns the output of that machine for that input
tape.
Once again, I’m only going to describe this at a very high level. The full
details are worth working but are beyond the scope of this module.
Essentially, we want a function which:
(1) Decodes the instruction set and finds out what to do at state 1.
(2) Performs the calculation at that state and records a number for the
new position of the head on the tape and the new state of the head.
(3) It should then repeat the calculation for this new state and position
c Toby Meadows

until a halting position is reached. This will involve minimisation and

.1 f
t
we’ll want to use the tape code as k here.
Of course, this is extremely superficial. If you are interested in completing
the exercise, you are probably best off describing the process completing the
v1 ra
Turing calculation using simple “if ..., then —; otherwise _ _ _” instructions
and then figuring out how to get Gödel schema to do this.
D

8.2. The Church-Turing thesis

So now we have seen two different approaches which formalise our intuitive
(or informal notion) of (effective) computation or calculation. Moreover, we
have seen (at a high level) that these two approaches are actually equivalent.
There have also been other attempts to formalise effective computability.
e

These include:
in

• Church’s Lambda calculus;

• Kleene’s equational representation;
nl

• register machines;
• Markov algorithms; and
O

• combinatorial logics.
We won’t be looking at any of these other systems, although they are easy
enough to find. The interesting thing is that every one of these systems can
be show to be equivalent to every other.
 8.2. THE CHURCH-TURING THESIS 104

So every serious attempt to formalise the notion of effective computability

has ended up with the same class of functions. These are known as the
recursive functions. We’ve used this term before, but now we’ll make our
usage more precise.

D EFINITION 173. Let us say that function is recursive if it has an algorithm

in any one (and thus all) of the canonical formalisations.

Thus if we can make a Turing machine describing a particular function,

then that function is recursive.
But we’re going to take a step further than this now. Given that every ap-
proach to formalising effective computability has come to the same thing,
we are going to propose the following thesis:
THESIS: (Church/Turing) The set of recursive functions is the set of effec-
c Toby Meadows

tively computable functions.

Observe that this is not a theorem, it is an empirical thesis. We have not
.1 f
t
proven that it is correct from principles which are incontrovertible. Rather
we have come to think that it is true on the basis that its assmption is (very
v1 ra
convenient) and that there are no known counterexamples.
Given that effective computability is an informal notion, we perhaps shouldn’t
be too surprised or disappointed by this. Effective computability is a very
D

worldly concept and thus any attempt to approximate or describe it is lim-

ited by how much we can know about such things. Arguably, we are in
a similar situation in physics when we attempt to describe the laws which
govern the physical world.
It is also very useful. It allows us to move between the informal notion of
a function or effective calculation which we can peform using simple rules
e

to the formal notion of recursiveness. We shall make use of this in future

in

weeks.
To take an example, however, consider the strings of symbols which we can
nl

form in a finite language and consider how we verify that a such a string is
well-formed or not.
O

Can you think of a pen-and-paper algorithm which would tell you that a
string is well-formed? Hopefully, the answer is yes, but it’s worth thinking
about in detail. In this case, we may use Church’s thesis to assert that
such a function is actually recursive. The more detailed verification of this
 8.3. LIMITATIONS IN THE THEORY OF RECURSION 105

fact would involve finding a suitable coding for the strings and then showing
that there is a Gödel schema or Turing machine algorithm which can peform
such a calculation.

8.3. Limitations in the theory of recursion

8.3.1. Are all functions from ω to ω recursive? An obvious question we

might want to know is whether or not all of the functions taking arguments
in ω and returning values in ω are recursive. The answer to this question is
negative.
To see this, we observe that there are countably many recursive functions.
Obviously, there are countably many of them. To see that there are at most
countably many recursive functions, observe that any set of instructions
c Toby Meadows

(i.e., an algorithm) can be represented (as we saw above) by a natural num-

ber. Since every recursive function is determined by at least one algorithm,
.1 f
t
there are at most countably many recursive functions.
On the other hand, let us consider how many functions there are taking
v1 ra
arguments from ω and returning values from ω; i.e., what is the cardinality
of the functions f : ω → ω.
Now any of the functions f : ω → ω can be used to represent a unique subset
D

F ⊆ ω as follows. We let
n ∈ F ↔ f (n) = 0.

Thus if f (7) = 0, then 7 ∈ F ; but if f (7) = 89, then 7 ∈

/ F . But we know
from Corollary 136 that the collection of all subsets of natural numbers
is not countable. Thus, the collection of all functions from ω to ω is also
e

uncountable.
in

8.3.2. Recursive and partial recursive functions. Recall the distinc-

tion between total and partial functions. We shall say that a function f :
nl

ω 2 → ω enumerates a (countable) set of functions G = {gn | n ∈ ω} if for every

gn ∈ G there is some n ∈ ω such that
O

gn (m) = f (n, m)

for all m ∈ ω. In other words, for any imput m, gn gives the same output as
f (n, . . . ): they compute the same function.
 8.3. LIMITATIONS IN THE THEORY OF RECURSION 106

It would be convenient to have some way of enumerating the total recursive

functions. Thus we might ask whether there is a total recursive function
which enumerates all of the total recursive functions? Perhaps surprisingly,
the answer is no.

T HEOREM 174. There is no total recursive function which enumerates all of

the total recursive functions.

P ROOF. Suppose for reductio that f : ω 2 → ω is a total recursive function

which enumerates all the total recursive functions. Let g : ω → ω be such
that for all m,
g(m) = f (m, m) + 1.
Since f is total recursve, g is clearly recursive too. We just used successor
and composition.
c Toby Meadows

We claim that g cannot be in the enumeration. Suppose it were. Then there

would be some k such that for all m ∈ ω
.1 f
t
g(m) = f (k, m).
v1 ra
But then if we consider what g does with value k, we get the following:

f (k, k) = g(k) = f (k, k) + 1

D

which is a contradiction. Thus g is not in the enumeration and thus there

is no total recursive function enumerating the total recursive functions. 

R EMARK . Observe that the argument used above is basically the same as
the one used in proving Cantor’s theorem. We adjusted the values of the
enumeration function down the diagonal to get a function that could not
e

have been on the list. This technique is ubiquitous in mathematical logical.

It is often known as diagonalising out.
in

[Link]. Partial recursive functions. There is a kind of way around this

nl

problem. Rather than considering the total recursive functions, we might

consider the functions which are partial and recursive.
O

For example, in Section [Link], we saw an example of a Turing machine

that did not halt. Moreover, we saw that it was easy to think of examples of
minimisation that never halted since they never came to a value for k which
made the overall function output 0.
 8.3. LIMITATIONS IN THE THEORY OF RECURSION 107

We thus introduce a more embrasive category of partial recursive functions

which include these non-halting cases and also the total recursive functions.
We can give an enumeration the partial recursive functions. For example,
might use the code number of the Gödel schema algorithm of a function.
Suppose that n is the code of some Gödel schema. We shall denote the
function code by n as ϕn .
To take an example, suppose that the code of the multiplication function is e
for some e ∈ ω. Then we have,

ϕe (m, n) = m × n

for m, n ∈ ω.
Given that partial recursive functions are not always defined it will be helpful
c Toby Meadows

to introduce a notion of equality between them. The following is useful.

ϕs ' ϕt if
.1 f
t
D EFINITION 175. Let ϕs and ϕt be partial recursive functions. We say that
v1 ra
• for all m for which ϕs is defined, ϕs (m) = ϕt (m); and
• for all m for which ϕt is defined, ϕs (m) = ϕt (m).
D

So the basic idea here is that we identify two partial recursive function if
they produce outputs for exactly the same domain of natural numbers and
that the produce the same outputs over that domain.
Now we might ask the question: is there a partial recursive function which
enumerates all of the partial recursive functions? In this case the answer is
e

yes.
in

Appealing to Church’s thesis, we argue that we could construct a pen-and-

paper algorithm which takes the code number e of some algorithm as an
argument and then behaves like ϕe for any imput m. More formally, a partial
nl

recursive function ϕk (for some k) such that for all ϕe (i.e. partial recursive
functions):
O

ϕk (e, . . . ) ' ϕe .

Or in other words for all m for which ϕe is defined ϕk (e, m) = ϕe (m) and for
other m, ϕk (e, m) is not defined. More formally we might write:
 8.3. LIMITATIONS IN THE THEORY OF RECURSION 108


ϕ (m),
e if ϕe (m) halts.
ϕk (e, m) =
undefined, otherwise.

Such a function is known as universal (or in the specific case of a Turing

machine, a universal Turing machine).
We should wonder why the problem for total recursive function does not
recur here. Let’s step through the argument to see why.

P ROOF. (ABORTIVE) As before let us suppose for “reductio” that there

is a partial recursive function ϕk which enumerates the partial recursive
functions. Then let us consider the partial recursive function ϕj which is
defined such that for all m :

c Toby Meadows

ϕ (m, m) + 1, if ϕ (m, m) halts.

k k
ϕj (m) =
.1 f undefined,

t
otherwise.

It should be obvious that ϕj is also a partial recursive function.

v1 ra
Thus ϕj has a code number; i.e., j. Let us consider what happens when ϕj
is applied to j (its own code number),

ϕ (j, j) + 1, if ϕ (j, j) halts.
k k
ϕj (j) =
D

undefined, otherwise.

Supposing that ϕk (j, j) halts we would have

ϕk (j, j) = ϕj (j) = ϕk (j, j) + 1.

But this is obviously a contradiction, so it cannot be the case that ϕk (j, j)

e

halts. 
in

8.3.3. The halting problem. We now consider the question: is there a

nl

recursive function which can take the code of a partial recursive function
and tell us whether or not the function always halts?
O

Clearly this would be a handy thing to have. Given some set of instructions
(suitably coded) such a function could tell whether or not some programme
would eventually halt. Intuitively speaking, when a computer crashes (or
hangs) this is often because the underlying programme does not halt. It
 8.3. LIMITATIONS IN THE THEORY OF RECURSION 109

would be nice to have a special programme that could look at other pro-
grammes and tell you whether or not they hang. This is known as the
halting problem.
Let us call a function f : ω 2 → ω a halt-checker if it takes the codes of partial
recursive functions and tells us whether or not for some input m that partial
recursive function halts on m. More formally,

1 if ϕ (n) halts.
e
f (e, n) =
0 otherwise.

Unfortunately this cannot be done.

We shall, in fact, show something a little stronger than this. Let us call a
function f : ω → ω an auto-halt-checker if f is such that:
c Toby Meadows


1 if ϕ (e) halts.
e
.1 f f (e) =

t
0 otherwise.

We shall show that there is no (total) recursive auto-halt-checker from which

v1 ra
it clearly follows that there is no halt checker.

T HEOREM 176. There is no auto-halt checker.

D

P ROOF. Suppose not. Then let f : ω → ω be a (total) recursive auto-halt

checker; i.e., f is such that

1 if ϕ (e) halts.
e
f (e) =
0 if ϕe (e) does not halt.
e

Now let us define a partial function ϕk : ω + ω which is such that

in


undefined, if f (e) = 1.
ϕk (e) =
0 if f (e) = 0.
nl

To see that such partial recursive function exists, we appeal to Church’s

O

thesis by describing the algorithm required. Since f is total recursive, when

we peform that calculation it will either terminate on 1 or 0. If it outputs 1,
we give the machine instructions to loop. If it ouputs 0, we make that the
ouput.
 8.4. RECURSIVE AND RECURSIVELY ENUMERABLE SETS 110

Let us see what happens when we present k (the code for ϕk ) to the function
ϕk .
Let us first suppose that ϕk (k) is defined. Then by its definition, ϕk (k) = 0.
Thus f (k) = 0. But this means that ϕk (k) does not halt (by definition of f );
and thus ϕk (k) is not defined. This contradicts our assumption. Thus ϕk (k)
is undefined.
But this means (by definition of ϕk ) that f (k) = 1; and thus by definition of ϕk ,
we see that ϕk (k) halts and is thus defined. This contradicts our assumption
that such a ϕk exists, so there is no such ϕk .
But there was nothing wrong with our definition of the partial recursive ϕk
on the assumption that f is a total recursive function. So our assumption
is wrong; and thus, there is no such total recursive f . 

C OROLLARY 177. There is no halt-checker.

c Toby Meadows

.1 f
t
8.4. Recursive and recursively enumerable sets

In this section, we relate the concepts of recursion theory to sets.

v1 ra
D EFINITION 178. A set A ⊆ ω is recursively enumerable if A is the domain of
a partial recursive function.

So if n ∈ A, there is (by Church’s thesis) an effectively computable function

D

which will be verify this fact.

Suppose A is recursively enumerable and that n ∈ A. We verify this as
follows. Given that A is recursively enumerable, there is a partial recursive
function, say ϕe such that A is the domain of ϕe . Or in other words, for all
n ∈ ω,
e
in

n ∈ A ⇔ ϕe (n) halts.

D EFINITION 179. We say that A ⊆ ω is recursive if:

nl

• A is recursively enumerable; and

O

• ω\A is recursively enumerable.

This means that for any n we can verify whether or not it is in A. Given
A is recursive, there are partial recursive functions ϕe and ϕf which have
domains A and ω\A respectively. To check whether n ∈ A, we simply run
 8.4. RECURSIVE AND RECURSIVELY ENUMERABLE SETS 111

both ϕe (n) and ϕf (n) simultaneously (or perhaps switching back and forth).
Clearly, at most one of them can halt since we cannot have n ∈ A and n ∈ ω\A
(i.e., n ∈
/ A). Moreover, one of the functions must halt, since either n ∈ A or
n∈ / A.
Naturally enough, this might lead us to ask the question: doesn’t the same
apply to recursively enumerable sets? The answer here is no. To see this it
suffices to show the following:

T HEOREM 180. There is a K ⊆ ω which is recursively enumberable but not

recursive.

P ROOF. Let K = {e ∈ ω | ϕe (e) halts.}. We claim that K is recursively

enumberable but not recursive.
To see that K is recursively enumberable, we need partial recursive function
c Toby Meadows

ψ(e) such that

ψ(e) halts. ⇔ ϕe (e) halts.
.1 f
t
For this, we simply use the universal machine ϕk such that ϕk (e, . . . ) ' ϕe .
We let ψ(e) ' ϕk (e, e) ' ϕ(e). Then if ϕe (e) halts, then ψ(e) halts (and gives the
v1 ra
same output) and vice vera.
To see that K is not recursive, we need to show that ω\K is not recursively
enumerable. Suppose it was. Then there is a partial recursive function ϕj (m)
such that:
D

ϕj (m) halts ⇔ ϕm (m) does not halt ⇔ m ∈ ω\K

Now consider what happens if we input j into ϕj . We have:

ϕj (j) halts ⇔ j ∈ ω\K ⇔ ϕj (j) does not halt.

e

The first ⇔ follows from the definition of ϕj ; the second ⇔ follows from
the definition of K. But this is a contradiction, so there is no such partial
in

recursive function. 
nl

R EMARK 181. Note that this proof is very similar to that of Theorem 176.
O
 8.5. EXERCISES. 112

8.5. Exercises.

E XERCISE 182. Does every algorithm determine a partial recursive function?

E XERCISE 183. Can a partial recursive function be represented by more than

one code number? Why/why not?

E XERCISE 184. Give a direct Cantorian proof that there are uncountably
many functions f : ω → ω; i.e., use a diagonal argument.

E XERCISE 185. Prove Corollary 177.

E XERCISE 186. Show that set A ⊆ ω is recursively enumerable iff it is the

range of a total recursive function or the empty set. [Use Church’s thesis to
define algorithms, in an informal fashion, that will meet the requirements of
the definitions. Note that we only need perform a finite part of a calculation
c Toby Meadows

at a time.]

such that:
.1 f
t
E XERCISE 187. Take A ⊆ ω. The characteristic function χA : ω → ω of A is
v1 ra
n ∈ A ⇔ χA (n) = 0.
Show that a set A ⊆ ω is recursive iff ifs characteristic function is total
recursive.
D

E XERCISE 188. Is there a partial recursive function which takes (codes of)
sentences ϕ and returns the value 0 if |= ϕ? How would you show this?
[Please feel free to use Church’s thesis.] What does this say about the set of
valid sentences? What about the set of sentences which are merely satisfi-
able, i.e., 2 ¬ϕ.
e
in
nl
O
 CHAPTER 9

Arithmetic

9.1. Theories and axioms

We may describe a theory in first order logic by providing a set of axioms to

generate it.
For example, we can construct theories for:

• arithmetic;
• set theory; and
c Toby Meadows

• syntax.
.1 f
t
The axioms are simply sentences of first order logic which:

(1) state things which are obviously true; and

v1 ra
(2) are sufficient to capture everything about the subject of our theoris-
ing.

So we would want our theory of arithmetic to have axioms that are obviously
D

true and which capture everything about the subject matter: arithmetic.
The notion of capturing here is that of proving. We use the axioms as
premises in, say a natural deduction proof. In our informal proof about
triangular numbers in Week 1 we completed our proof on the basis of an
induction axiom and some simple facts about number theory. A good theory
e

would have been able to capture those simple facts and everything else.
in

We are going to learn in the next couple of weeks that the goal (2.) is actually
impossible to achieve in most interesting cases. This phenomena is known
as incompleteness. There are sentences which we can neither prove nor
nl

refute.
O

9.2. A sketch of the incompleteness theorem

Before we get into the full detail of this proof, which will take a while, I’ll give
you a quick and simplified sketch of the proof. This will give you an idea of
113
 9.2. A SKETCH OF THE INCOMPLETENESS THEOREM 114

the phenomena involved and also allow us to pick out the important parts
of the strategy involved in proving it.
So my goal is to show that there is a sentence γ which I can neither prove
from my axiom system Γ nor refute in it.
But first consider two properties which seem quite clearly desirable for an
axiom system:
• Consistency: we don’t want to be able to prove ⊥ from Γ. Otherwise,
as we know, we could prove anything we liked and the our theory
would not be very interesting.
• Soundness: if we can prove a sentence ϕ, the ϕ is true. Here we are
just saying that if we can prove it then it better not be false. Clearly
a theory of some subject ought to do this.
Now the axiom system Γ that we are going to be concerned with is a theory
c Toby Meadows

of arithmetic P E. This theory is quite strong. As we’ve seen above we can

t
code up Turing machines using numbers. We can use a similar trick to
code up sentences of arithmetic. Moreover, we shall see today that P E is
.1 f
actually strong enough to represent recursive functions and as we shall see
v1 ra
a predicate B(x) which says, loosely speaking, that x is the code of a provable
sentence. Showing these things is where we need to do most of the work.
However, once these things are established, we can then go on to show
D

that there is a sentence γ which says of itself (in some sense) that it is not
provable. (This is a little like the famous liar sentence: this sentence is not
true.) With this in hand we can complete the argument.

9.2.1. An informal version of the agument. We show, informally here

that there is a sentence which can neither be proven nor refuted in our
e

system P E.
in

By our assumption above, we suppose that γ says that it is not provable in

P E.
nl

Now supose for reductio that P E ` γ; i.e., γ is a provable in P E. Then since

P E is sound, γ is true. But γ just says that it is not provable in P E, which
O

is a contradiction. Thus P E 0 γ.
Now suppose for reductio that P E ` ¬γ; i.e., ¬γ is a theorem of P E. Then
since P E is consistent γ is not a theorem of P E. But then since P E is
sound, we see that ¬γ is true; and this just says that it’s not the case that
 9.3. A THEORY OF ARITHMETIC - P E 115

γ is provable in P E; i.e., γ is provable in P E. But this is a contradiction, so

P E 0 ¬γ.

9.2.2. What we need to formalise it. The argument above is very infor-
mal. Until we’ve seen how the detail works, it could be tempting to see this
as a piece of sophistry. However, it is going to turn out that each of the parts
of the argument can be described very precisely; and thus that the whole
things works.
However, what we do get from the sketch above it a clear list of things we
need to establish:

(1) We need to find a way of representing provability using P E;

(2) We need a way of capturing self-reference using P E;
(3) From here, we need to make a sentence which says of itself that it
c Toby Meadows

isn’t true.

for this problem.

.1 f
t
We are going to spend the rest of this week working on the foundation stone
v1 ra
Rather than take on provability and self-reference as separate problems we
are going to first show that we can represent the recursive functions using P E
and that from here we shall make an appeal to Church’s thesis to argue that
we can represent both provability and self-reference by recursive functions.
D

Intuitively, the idea is that if we have enough power to represent recursive

functions, then the fact that we can do proofs using a pen-and-paper al-
gorithm means that we’ll be able to represent all of this activity using our
theory.
e

9.3. A theory of arithmetic - P E

in

As we’ve seen before, a theory Γ is a set of sentences which is closed under

nl

consequence; i.e., Γ is a theory if for all ϕ, if Γ |= ϕ, then ϕ ∈ Γ.

Of course, in this form, a theory is a massive collection of sentences. It
O

would clearly be desirable to be able to capture all of this information using

something more managable. This is where an axiomatisation come in. In
this section, we are going to explore a particular axiomatisation for arith-
metic.
 9.3. A THEORY OF ARITHMETIC - P E 116

Our theory P E is formulated in the language LAr = {0, s, +, ×, ·· }. The last

symbol here is just a way of capturing the exponentiation function, whic is
not usually provided with a symbol.
We then set out the axioms for our theory of arithmetic P E as follows:
(1) 0 6= sx
(2) x 6= y → sx 6= sy
(3) x+0=x
(4) x + sy = s(x + y)
(5) x×0=0
(6) x × sy = (x × y) + x
(7) x0 = 1
(8) xsy = xy × x
(9) ϕ(0) ∧ ∀x(ϕ(x) → ϕ(sx)) → ∀xϕ(x)
c Toby Meadows

R EMARK . Each of these axioms employs implicit universal quantification. Thus

.1 f
t
the second axiom, strictly speaking, should be written

∀x∀y(x 6= y → sx 6= sy).
v1 ra
The final axiom is known as an axiom schema. It is actually a representation
of infinitely many axioms, each of which is a substitution of a formula (with
one free variable) from the language of arithmetic.
D

9.3.1. Some simple proofs. As we saw in the first weeks of this module,
numerals like 2 and 63 are not (strictly) part of the language of arithmetic.
However, they are very convenient to use. To facilitate their use we introduce
a metalinguistic function · which takes a number and returns a numeral in
the language of arithmetic. So for example, we have:
e

3 = sss0.
in

We shall also allow this to work for variable so:

nl

n = s....s0

where there is a sequence of n s’s occuring in front of 0.

O

E XAMPLE 189. P E ` 1 + 1 = 2.
Putting this properly into the language we are trying to show that:

s0 + s0 = ss0.
 9.3. A THEORY OF ARITHMETIC - P E 117

Here’s the proof as a natural deduction:

∀x∀y(x + sy = s(x + y)) ∀x(x + 0 = 0)

s0 + s0 = s(s0 + 0) s0 + 0 = s0
s0 + s0 = ss0
Using full natural deduction will quickly get very cumbersome, so we will
actually reason more informally. The effect should be the same.
By identity of terms s0 + s0 = s0 + s0. By (4.) we se that s0 + s0 = s(s0 + 0), so
by the identity rule, we may substitute s(s0 + 0) for s0 + s0 wherever we like.
Thus s0 + s0 = s(s0 + 0). Then by (3.) we have s0 + 0 = s0; thus by identity, we
have s0 + s0 = ss0.

R EMARK . Observe that in the second use of the identity rules, we substituted
for a subterm of an expression.
c Toby Meadows

We now use an example which exploits the induction axiom (8.).

E XAMPLE 190. P E ` ∀x(x + 0 = 0 + x).

.1 f
t
We exploit the induction schema by finding an appropriate ϕ to use. In this
v1 ra
case, we simply use the formula (minus the universal quantification) that
we are trying to establish. Thus

ϕ(n) ↔ n + 0 = 0 + n).
D

Schema (8.) tells us that the following axiom is an axiom of P E:

0 + 0 = 0 + 0 ∧ ∀x(x + 0 = 0 + x → sx + 0 = 0 + sx) → ∀x(x + 0 = 0 + x).

So once we have shown the first two parts of the antecedent hold, we can
take the consequent of the conditional as our conclusion: which is exactly
e

what we want.
in

Clear we have 0 + 0 = 0 + 0 from the logical rules for identity alone. Now take
an arbitrary x ∈ ω and suppose that x + 0 = 0 + x. Then
nl

sx + 0 = sx
= s(0 + x)
O

= 0 + sx.

The first = exploited axiom (3.); the second exploited our inductive hypothe-
sis; and the third = exploited axiom (4.). This suffices.
 9.3. A THEORY OF ARITHMETIC - P E 118

9.3.2. Relating recursion theory back to theories and and logic. Be-
fore we get into the hard work, let’s take a minute to tie some together the
material from this section of the course back to some of the material from
the beginning. We’ll do this with some interesting definitions for theories.

D EFINITION 191. A theory Γ is (negation) completene if for all sentences ϕ we

either:

Γ ` ϕ or Γ ` ¬ϕ.

If the goal of our theory is to say everything that we think is true about
some subject matter, then negation completeness is clear a must-have. With
it, any sentence about the subject matter will be such that either it or its
negation will be a theorem. Without it, our theory is incomplete in the sense
c Toby Meadows

that there is a sentence which the theory cannot say anything about.

R EMARK 192. Observe that since we have soundness and completeness, it

.1 f
t
doesn’t make much difference whether we use ` or |=. In first order logic,
we have discovered that they mean much the same thing.
v1 ra
D EFINITION 193. A theory Γ is decidable if the set {ϕ | Γ ` ϕ} is recursive.

So we haven’t provided a way of representing sentences using natural num-

D

bers of Turing tapes, but hopefully by now, you could think of some way of
doing this. So let’s exploit Church’s thesis at this point.
Now decidability is clearly a desirable property too. Given any particular
sentence ϕ, decidability tell us that we can tell whether or not ϕ is a theorem;
i.e., there is an algorithm which will terminate after a finite amount of time
telling us that ϕ is either a theorem of Γ or not.
e
in

D EFINITION 194. A theory Γ is finitely axiomatisable if there is a finite ∆ ⊆ Γ

such that for all γ ∈ Γ, ∆ ` γ.
nl

The value of finite axiomatisability should be clear. It allows us, so to speak,

compress a body of knowledge into a finite collection of sentences from which
O

any of the other sentences may be derived. At the very least, it’s going to be
easier to remember.
Unfortunately, in many interesting cases of theories it is not possible to
get a reasonable theory with only finitely many axioms. Such theories are
 9.3. A THEORY OF ARITHMETIC - P E 119

incomplete, not just in the Gödelian way, but in the sense that they miss
out things that are very obviously true.
Fortunately, there is another kind of axiomatisation, which gives, so to
speak, a good compression.

D EFINITION 195. A theory Γ is recursively axiomatisable if there is a recursive

∆ ⊆ Γ such that for all γ ∈ Γ, ∆ ` γ.

The idea here, is that we there is a recursive function which will tell us
whether or not some sentence is an axiom of Γ or not. So we can always fig-
ure this out in a finite period of time and then try to work out whether other
sentences are theorems of Γ. It’s not as good as finitely axiomatisability, but
it still gives us more realistic grip on Γ.

9.3.3. Representing the partial recursive functions.

c Toby Meadows

[Link]. What sort of representation? Our goal here is to show that for

t
any partial recursive function, there is an arithmetic formula which repre-
sents it in the theory P E. Given that we are working with numbers, we shall
.1 f
try to line things up with the Gödel schema approach to algorithms.
v1 ra
Now we don’t have any means of constructing new function symbols in P E,
but we can build up new formulae which represent relations and sets. For
example, the formula:
D

ϕ(x) = ∃y(y × 2 = x)
can be used to represent the even numbers.
So since we know already that functions are just special kinds of relations
we shall represent the partial recursive functions with formulae representing
their corrseponding relations. So given some recursive function f : ω m → ω,
e

we want a formula in the languge of arithemtic such that f (n̄) = k iff ϕ(m̄, k)
is true and we can actually prove that it P E.
in

The two things we want from our representation are that:

nl

(1) It is correct: so the formula doesn’t get anything wrong about the
function it represents;
(2) P E can prove those facts: thus, if it’s true then using the proof style
O

above, we can prove it using P E.

R EMARK . This actually corresponds to a different kind of soundness and

completeness. (1.) asserts that P E is sound with respect to the recursive
 9.3. A THEORY OF ARITHMETIC - P E 120

functions and (2.) asserts that P E is complete with respect to the recursive
function.

[Link]. Showing P E is strong enough. Let us first show that P E can ac-
tually prove these facts. To do this, we are actually going to prove something
a little stronger than this. We shall do the following:
(1) Define a natural class of formulae in the language or arithmetic; then
(2) Show that P E always gets facts about such formulae right.
In the next section, we shall then show that all of the recursive functions fit
into this category so P E does the job.
We now define this natural class of formulae. First of all, observe the follow-
ing facts about first order logic. First, we observe that it is possible to define
the relation < in the language of arithmetic. We have
c Toby Meadows

x < y ⇔ N |= ∃m(sx + m = y)
.1 f
t
⇔ N |= ∀m(y + m 6= sx).

In fact, as you can see, there are a couple of ways of doing it. We use the
v1 ra
semantic concept of satisfaction |= here to mean that these facts are true
in the standard model of arithmetic, which is what we want. I’ll now start
using the < symbol as if it were in the language, but on the understanding
we could always remove it. [We could also just add a new relation symbol
D

<to our language.]

The next thing we need is what is known as bounded quantification. This
can be used in any model that has an ordering relation on its domain, like
the natural numbers N. A bounded quantifer is writen in front of a formula
like this
e

∀x < yϕ(x).
in

It just means that ∀x(x < y → ϕ(x)), however, it is convenient to cordon of

this particular articulation. Similarly, we have a bounded version of exis-
nl

tential quantification written

∃x < yϕ(x)
O

which just means ∃x(x < y ∧ ϕ(x)).

We are now ready to define up our natural class of formulae. In fact, we’ll
define two of them. We call the first class the ∆0 formulae. They are defined
as follows:
 9.3. A THEORY OF ARITHMETIC - P E 121

• if ϕ is an arithmetic atomic sentence, then ϕ is ∆0 ;

• if ϕ, ψ are ∆0 , then ϕ ∧ ψ, ¬ϕ and ∀x < yϕ are also ∆0 ; and1
• nothing else is ∆0 .

We are now going to show that P E is complete for sentences which are ∆0 .

T HEOREM 196. Suppose ϕ is a ∆0 sentence of arithmetic. Then

N |= ϕ ⇒ P E ` ϕ.

R EMARK . Observe that we only have one direction ⇒ in this theorem. Thus
it’s probably going to be better to use some kind of positive complexity for
this proof.

P ROOF. We prove this by induction on the positive complexity of ∆0 sen-

tences.2
c Toby Meadows

(Base) Suppose ϕ := t = s where s and t are arithmetic terms. An induction

.1 f
t
on the complexity of terms will establish this. Similarly for ϕ := t 6= s where s
and t are arithmetic terms. The essential idea is to show that any arithmetic
v1 ra
term can be crunched back into a numeral using just P E.
(Induction Step) Suppose ϕ := ψ ∧ χ where ψ and χ are ∆0 sentences of less
positive complexity than ϕ. Then we have
D

N |= ψ ∧ χ ⇔ N |= ψ & N |= χ
⇔ PE ` ψ & PE ` χ
⇔ P E ` ψ ∧ χ.

Now suppose ϕ := ¬(ψ ∧ χ) where ¬ψ and ¬χ are ∆0 with less positive com-
e

plexity than ϕ. Then

in

N |= ¬(ψ ∧ χ) ⇔ N |= ¬ψ or N |= ¬χ
⇒ P E ` ¬ψ or P E ` ¬χ
nl

⇒ P E ` ¬(ψ ∧ χ).
O

1
I’m just going to deal with conjunction, universal quantification and negation so we can
cut down on the number of cases that we need to prove below. They can be added back
using the usual definitions.
2
The positive complexity of ∆0 sentences is the obvious generalisation of definition we used
in Week 4.
 9.3. A THEORY OF ARITHMETIC - P E 122

Now suppose ϕ := ¬¬ψ where ψ is a ∆0 sentence of less complexity than ϕ.

Then we get

N |= ¬¬ψ ⇔ N |= ψ
⇒ P E ` ψ.

Suppose ϕ := ∀x < n ψ(x) where ψ(x) is a ∆0 formula with at most one free
variable which has less positive complexity than ϕ. Then

N |= ∀x < n ψ(x) ⇔ ∀m < n N |= ψ(m)

⇔ N |= ψ(0) &...& N |= ψ(s...s0)
⇒ P E ` ψ(0) &...& N |= ψ(s...s0)
⇔ P E ` ψ(0) ∧ ... ∧ ψ(s...s0)
⇔ P E ` ∀x ≤ n ψ(x).
c Toby Meadows

The first ⇔ follows by the satisfaction definition as does the second. At the
.1 f
t
third stage, we now have sentences so we exploit the induction hypothesis.
The rest follows from facts about provability in P E.
v1 ra
Suppose ϕ := ¬∀x < n ψ(x). Then

N |= ¬∀x < n ψ(x) ⇔ ¬∀m < n N |= ψ(n)

⇔ N |= ¬ψ(0) or...or N |= ¬ψ(s...s0)
D

⇒ P E ` ¬ψ(0) or...or P E ` ¬ψ(s...s0)

⇔ P E ` ¬ψ(0) ∨ ... ∨ ¬ψ(s...s0)
⇔ P E ` ¬∀x ≤ n ψ(x)


e

R EMARK 197. Observe that not all of the arrows int he proof above point in
in

both directions. Note that the real trick behind this proof is the fact that we
only end up with finite conjunctions and disjunctions, thus there is always
a way of checking such facts.
nl

Next we define the Σ01 functions. They are simply the ∆0 formulae with
O

(possible muliple occurences of) unbounded existential quantifiers out the

front. So for example, if ϕ is ∆0 , then ∃yϕ is Σ01 and so is ∃z∃yϕ.
However, ∃yϕ ∧ ϕ is not Σ01 since it is a conjunction of a ∆01 formula and a Σ01
formula. Unfortunately, we are much more likely to come across formulae
 9.3. A THEORY OF ARITHMETIC - P E 123

of this latter kind than pure Σ01 formulae. But there is a simple way to move
between them. We now define this class of formulae and then show how to
turn them into Σ01 formulae. We shall call this class Σ formulae. We will rely
on these manipulations when we come to represent the process of defining
functions by primitive recursion.
We say that:
• if ϕ is an ∆0 3, then ϕ ∈ Σ;
• if ϕ, ψ ∈ Σ then ϕ ∧ ψ is in Σ;
• if ϕ ∈ Σ, then ¬¬ϕ, ∀x < yϕ, ∃x < yϕ, ¬∀xϕ and ∃xϕ are in Σ;
• if ¬ϕ and ¬ψ are in Σ, then ¬(ϕ ∧ ψ), ¬∀x < yϕ, ¬∃x < yϕ ∈ Σ; and
• nothing else is in Σ.

T HEOREM 198. Any Σ formulae can be converted into an equivalent Σ01 for-
mula.
c Toby Meadows

P ROOF. We proceed by induction on the complexity of Σ formulae.

(Base) If ϕ is ∆0 , then it is clearly Σ01 already.
.1 f
t
(Induction Step) Suppose ϕ := ψ ∧χ. Then by induction hypothesis, there are
v1 ra
Σ01 formulae ∃xψ2 (x) and ∃yχ2 (y) which are equivalent to ψ and χ respectively.
We then let our convervsion of ϕ be

∃x∃y(ψ2 (x) ∧ χ2 (y))

D

which is clearly equivalent to ϕ.

Suppose ϕ := ¬¬ψ. Then by the induction hypothesis, there is a Σ01 formula
∃yψ2 (y) which is equivalent (in the standard model of arithmetic) to ψ. Thus,
we let our conversion of ϕ be

∃y¬¬ψ2 (y).
e
in

Suppose ϕ := ∀x < yψ(x, y). Then by the indution hypothesis, there is a Σ01
formula ∃zψ2 (x, y, z) which is equivalent to ψ(x, y). We let the following be our
nl

conversion
∃w∀x < y∃z < w ψ2 (x, y, z)
O

and we claim that it is equivalent to ϕ. We can get ϕ from the conversion by

logic alone. For the other direction, let us take an arbitrary y, then ϕ tells
us that for each x < y there is some, z, let’s label it with an x to be clear, zx ,
3
I.e., ϕ is either atomic or the negation of an atomic.
 9.3. A THEORY OF ARITHMETIC - P E 124

such that ψ2 (x, y, zx ). Since there are only finitely many x’s there only finitely
many zx ’s; and thus, there is some w which is greater than all of them.
Thus there is some w such that for every x < y there is a z < w such that
ψ2 (x, y, z) which is exactly what our conversion says.
The rest of the cases are left as an exercise. 

T HEOREM 199. P E is Σ01 -complete.

P ROOF. Suppose ϕ := ∃xψ(x) where ψ is ∆0 . Now suppose N |= ∃xψ(x).

Then there is some n such that N |= ψ(n). Moreover since ψ is ∆0 , we have
by Theorem 196 that P E ` ψ(n). Thus by (∃-I), we also have P E ` ∃xψ(x). 

[Link]. Capturing the recursive functions . So we have now established

that our theory P E gets the Σ01 sentences right. Our goal now is to show that
c Toby Meadows

we can represent all of the recursive functions using Σ01 formulae. We shall fo-
cus on representing the Gödel schema. We want to show that any recursive
.1 f
t
function (represented by an alogorithm of the Gödel schema) can be cap-
tured using a formula in the language of arithmetic. Now the representation
v1 ra
we want works like this.

D EFINITION 200. Let f : ω n + ω be a partial function. We say that a formula

ψ(x1 , ..., xn , y) ∈ F ormLAr semantically represents f if
D

f (hm1 , ..., mn i) = k ⇔ N |= ψ(m1 , ..., mn , k).

So given any partial recursive function ϕe : ω n + ω, we want a Σ01 formula

∃zψ(z, x1 , ..., xn , y) such that:
e

ϕe (hm1 , ..., mn i) = k ⇔ N |= ∃zψ(z, m1 , ..., mn , k).

in

Observe that since ϕe is a partial function, it could well be the case that for
some m1 , ..., mn , ϕ(hm1 , ..., mn i) is not defined. The Σ01 aspect of our formula
nl

comes in handy here as this will pan out as a value of m1 , ..., mn for which
there is not z such taht ψ(z, m1 , ..., nn , k) is a truth sentence about the natural
O

numbers.
Now with such a formula in hand, we may then exploit Theorem 199 to go
from a the fact that
N |= ∃zψ(z, m1 , ..., mn , k)
 9.3. A THEORY OF ARITHMETIC - P E 125

to the fact that

P E ` ∃zψ(z, m1 , ..., mn , k).
Thus, it is in this sense that we have capturing the partial recursive function
ϕe : if ϕe is defined on some tuple and returns a value, then we there is a
sentence of arithmetic witnessing that fact which can be proven in P E.

D EFINITION 201. Let f : ω n + ω. We say that a formula ϕ ∈ F ormLAr captures

f relative to theory Γ if

f (hm1 , ..., mn i) = k ⇒ P E ` ψ(m1 , ..., mn , k).

Thus we capture the partial recursive functions in the sense that for any
partial recursive ϕe there is a Σ01 formula ∃zϕ(z, x1 , ..., xn , y ∈ F ormLAr such
that
c Toby Meadows

ϕe (hm1 , ..., mn i) = k ⇒ P E ` ∃zψ(z, m1 , ..., mn , k).

.1 f
t
So our goal now is to show that the partial recursive functions can be
captured. However, given Σ01 completeness, it will suffice to merely show
v1 ra
that we can semantically represent the partial recursive functions using Σ01
formulae of arithmetic.4
We now proceed to do that. As we did last week, we shall represent the basic
functions, and then the generators of the Gödel schema.
D

Let us attempt the z n function. This is easy. Let ψz (x1 , ..., xn , y) be defined as
follows:

ψz (x1 , ..., xn , y) ↔d y = 0.
Thus no matter what values are used for x1 , ..., xn , the formula is only true if
e

y is 0, which is what we want; i.e., we have:

in

z n (hm1 , ..., mn i) = k ⇔ N |= k = 0.
nl

I’ll leave the other two basic functions (successor and projection) as exer-
cises.
O

We not turn to the rules for generating more complex functions:

(1) composition;
4
Why does this suffice?
 9.3. A THEORY OF ARITHMETIC - P E 126

(2) primitive recursion; and

(3) minimisation.

I’m only going to do primitive recursion here. This is the most involved case.
The others are left as exercises. So by definition, we know that given recur-
sive function f : ω m → ω and g : ω m+2 → ω there is another recursive function
h : ω n+1 → ω such that

h(0, n̄) = f (n̄)

h(k + 1, n̄) = g(h(k, n̄), k, n̄).

Moreover, we suppose that we have already captured the functions f and g

with Σ01 formulae ϕ(x̄) and γ(y, z, x̄) respectively.
Now as we have seen, primitive recursion allows us to run a series of calcu-
lation by repeatedly applying the function g to previous outputs. This is why
c Toby Meadows

it is called recursive. By way of illustration, consider what happens when we

put 3 into the general formulation above.
.1 f
t
h(3, n̄) = g(h(2, n̄), 2, n̄)
v1 ra
= g(g(h(1, n̄), 1, n̄), 2, n̄)
= g(g(g(h(0, n̄), 0, n̄), 1, n̄), 2, n̄)
= g(g(g(f (n̄), 0, n̄), 1, n̄), 2, n̄)
D

Our goal here is to find a simple way of representing this kind of thing using
the language of arithmetic and P E.
To do this, it will be helpful to have a means of representing sequences.
To see how this is helpful we might express what is going on in primitive
recursion as follows. Considering h as described above we might say:
e
in

h(k, n̄) = m iff there is a sequence hb0 , ..., bk i of k + 1 numbers such that
f (m) = b0 and
nl

for all x ≤ k, g(bx , x, n̄) = bx+1 and

bk = m
O

You should see that this says the same thing as the definition of h, but we
avoid mentioning h on the right hand side. This means we have a legitimate
definition. Thus if we can represent this statement in arithmetic, then we
 9.3. A THEORY OF ARITHMETIC - P E 127

can replace any uses of primitive recursion by this instead. This is what we
want. We’ll finish this off in two stages:
• First, we’ll just suppose that we have a way of simply capturing se-
quences and show that this gives us a simple way of capturing h;
• Then we’ll show how to simply capture sequences.
So let’s suppose we have a Σ01 formula P ro(b, a, m, n) which uses both a and
b to represent the sequence number and says that the mth value of the se-
quence (represented by a and b) is n. With this and the formulas ϕ and γ
capturing f and g, we may now capture h using the following formulae ψ,
which is just a re-writing of the sentence above into the language of arith-
metic:

ψ(k, n̄, m) ≡ ∃b∃a(

c Toby Meadows

∃u < b(P ro(b, a, 0, u) ∧ ϕ(u, n̄)) ∧

∀x < sk∃w < b∃u < b(
.1 f
t
(P ro(b, a, x, w) ∧ P ro(b, a, sx, u) ∧ γ(w, x, n̄, u)) ∧
ra
P ro(a, b, k, m)

Since P ro is Σ01 , we see by Theorem 198, that ψ is also Σ01 , which is what we
require.
D

We now show how to define the P ro formula. So our goal is to represent

sequences of number using a pair of numbers a and b. One obvious situa-
tion in which we represent sequences of numbers is in our everyday arabic
v1

notation. For example, we might think of the number

334547
e

as representing the sequence 7, 4, 5, 4, 3, 3. (It’s actually much easier to go

in

backwards, which is why we do so.) This works because:

nl

334547 = 7 × 100 + 4 × 101 + 5 × 102 + 4 × 103 + 3 × 104 + 3 × 105 .

We are going to employ this trick to represent arbitrary sequences of num-
O

bers. Of course, there is an obvious problem. Using a base of 10 means

that we can only represent sequences of numbers n ≤ 9. But it’s not a big
problem. To represent sequences of larger numbers we simply need to select
a base which is larger than any number in the sequence.
 9.3. A THEORY OF ARITHMETIC - P E 128

Thus we make use of the following fact.

F ACT 202. For any sequence of numbers n0 , ..., nk and a such that a > ni for
1 ≤ i ≤ m there is a unique b such that:

b = n0 × a0 + ... + nk × ak .

Since b is unique, it seems reasonable to hope that we might be able to

recover each of the elements ni from the sequence. Indeed this is the case.
To do this we need a couple more simple functions, div and rem. div(m, n)
gives the result of dividing m by n but removes any remainder. rem(m, n)
gives the remainder that results when m is divided by n. So, for example,
div(14, 5) = 2 and rem(14, 5) = 4.
To get the ith value of the sequence n0 , ..., nk represented by b with base a we
c Toby Meadows

simply take:
rem(div(b, ai−1 ), a).
.1 f
t
This is just a simple number theoretic fact, but let’s see it in action on a
simple example. Suppose we are representing the sequence 2, 4, 1, 5 using
v1 ra
the number 5142 in base 10. Then we may recover the 3nd element using the
functions above as follows:

rem(div(5142, 103−1 ), 10) = rem(div(5142, 100), 10)

D

= rem(51, 10)
= 1

which is what we wanted.

The last thing we need to do is show how to represent this in the language
of arithmetic in a Σ01 way. We leave representing rem and div as an exercise
e

and so we suppose that we have formulae

in

• Rem(x, y, z) whic says that z is the remainder from dividing x by y;

nl

and
• Quo(x, y, z) which says that z is the result of dividing x by y.
O

We then define P ro(a, b, m, n) as follows:

∃z < b(Quo(b, am , z) ∧ Rem(z, a, n).

This is clearly Σ01 so we are now done.

 9.3. A THEORY OF ARITHMETIC - P E 129

R EMARK 203. It actually turns out that we can do this in a simpler axioma-
tisation of arithmetic. It turns out that we can get rid of exponentiation.

Now once we have found the Σ01 formulae which do this, we have basically
proven the following two theorems.

T HEOREM 204. If ϕ is a partial recursive function, then ϕ may be semantically

reprsented by a Σ01 formula.

P ROOF. By induction on the complexity of Gödel schema algorithms, we

show that they can be represented by Σ formulae. The base case and in-
ductive steps are shown above. To get a Σ01 formula, we exploit Theorem
198. 

T HEOREM 205. If ϕ is a partial recursive function, then ϕ may be captured by

P E.
c Toby Meadows

P ROOF. Let ϕe be an arbitrary partial recursive function. Then by Theo-

.1 f
t
rme 204,ϕe can be represented by a Σ01 formulae ψ. Then by Theorem 199,
we see that ψ will be proven if it is correct. I.e.,
v1 ra
ϕe (n) = k ⇔ N |= ψ(n, k) ⇒ P E ` ψ(n, k)


in D
e
nl
O
 9.4. EXERCISES. 130

9.4. Exercises.

E XERCISE 206. Is there a decidable theory which is not negation complete?

Is this correct? If so, provide a proof or explanation of this. Otherwise,
provide a counterexample. (You may want to use propositional logic rather
than first order logic here.)

E XERCISE 207. Is P E finitely axiomatisable, recursively axiomatisable or

neither of these?

E XERCISE 208. (More philosophical) If P E is recursively axiomatisable, is

there something, so to speak, still finite in the way we can represent such a
theory.

E XERCISE 209. Complete the other cases in Section [Link].

c Toby Meadows

E XERCISE 210. Represent the functions div and rem by Σ01 formula Div and
Rem in the language of arithmetic.
.1 f
t
E XERCISE 211. Describe a recursive function which lists all the sentence
of some language L(C) which has been appropriately coded. Such a listing
v1 ra
could be used to form an enumeration like the one we used to prove the
completeness of the natural deduction system.
in D
e
nl
O
 CHAPTER 10

Incompleteness

10.1. The Diagonal Lemma

We now have the means to show that there is a sentence γ which says of
itself that it is not provable.

10.1.1. Gödel coding. First we need a way of talking about sentences of

arithmetic using that material of arithmetic: the natural numbers. For this
c Toby Meadows

purpose, we use a coding system.

We have seen a number of different coding systems in this course. Let us use
.1 f
t
the prime decomposition system, which we used to code Turing machines.
Thus we might assign a number to each element of our basic vocabulary as
v1 ra
follows:
∃ ∀ ∧ ∨ → ¬ ( ) 0 s + × ·· v =
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
D

To show how the coding works, we take a simple example.

• ∃y(y = 2).

We then turn this into a proper sentence of LAr as follows:

• ∃v2 (v2 = ss0).

e

We represent this with the following string of numbers:

in

• 0, 13, 6, 9, 9, 8, 7, 6, 13, 9, 9, 8, 14, 9, 9, 8, 7

which we then code using prime decomposition as follows:

nl

• 20 × 313 × 56 × 79 × 119 × 138 × 177 × 196 × 2313 × 296 × 319 × 379 × 418 × 437 ×
4714 × 539 × 599 × 618 × 677 .
O

With a coding system in place, we are now able to express things about
sentence in the language of arithmetic.
For formulae of LAr , we write pϕq to denote the code number of ϕ.
131
 10.1. THE DIAGONAL LEMMA 132

Using similar techniques, we may also code up the proofs of P E too. We

shall not detail the process here, although it is also worth considering.
[Link]. Representation of sets. We now make more precise the concep-
tions of representation we need. The first notion is semantic and refers back
to the real interpretation of the symbols, while the second is notion is with
regard to the ability of P E to prove things.

D EFINITION 212. Let D ⊆ ω. We say that a D is semantically represented by

some ϕ(x) ∈ F ormLω1 ω if
n ∈ D ⇔ N |= ϕ(n).

R EMARK 213. Assuming our theory is consistent, we can make these arrows
go in both directions. The important thing is that we are getting the ¬ inside
the Γ ` context in the second case; i.e., we aren’t just saying that Γ 0 δ(n)
c Toby Meadows

which is much weaker.

t
T HEOREM 214. All of the recursively enumerable sets are semnatically repre-
sented by forrmulae of arithmetic in the standard model.
.1 f
v1 ra
P ROOF. Let D ⊆ ω be recursively enumerable. Then there is a partial
recursive function ϕe which is defined only on the elements of D; i.e.,

n ∈ D ⇔ ϕe (n) is defined.
D

We observe that for ϕe (n) to be defined is just to say that there is a k such
that ϕe (n) = k. Now, we know that all of the partial recursive functions can
be semantically represented by formulae of arithmetic; thus, there is some
ψ(x, y) ∈ F ormLAr such that:

ϕe (n) = k ⇔ N |= ψ(n, k).

e
in

Thus we see that

n ∈ D ⇔ N |= ∃yψ(n, y)
nl

and so D is semantically represented by ∃yψ(x, y). 

C OROLLARY 215. All of the recursive sets are semantically represented by

O

forrmulae of arithmetic.

D EFINITION 216. Let D ⊆ ω. We say that D is case-by-case captured by a

theory Γ if:
 10.1. THE DIAGONAL LEMMA 133

n ∈ D ⇒ Γ ` δ(n)
and

n∈
/ D ⇒ Γ ` ¬δ(n).

L EMMA 217. If ϕe : ω + ω is a partial recursive function, then there is a Σ01

formula ψ(x, y) ∈ F ormLAr such that

ϕe (n) = m ⇒ P E ` ∀y(ψ(n, y) ↔ y = m).

Intuitively, this just says that not only can P E capture the function, but it
can also show that the formulae which captures ϕe is a genuine function, in
the sense of giving unique outputs.
c Toby Meadows

P ROOF. (Sketch) Suppose ϕe (n) = m. We already now that there is some m

which P E can prove the existence of. We need to show that P E establishes
.1 f
t
the uniqueness of this m. We procede by induction (in the metalanguage)
on the construction of the formulae we used to represent partial recursive
v1 ra
functions which were represented by the Gödel schema. The base case is
simple. For example, supposing we had used the formula ψ(x, y) := x = x ∨
y = 0 to represent z 1 where z 1 (x) = y. Suppose z 1 (m) = n. By Theorem9.3.3.3,
we already know that P E ` ψ(m, n). To complete the claim, we must show
D

that P E ` ∀y(y 6= n → ¬ψ(m, y). To do this, we suppose that there were

some arbitrary a 6= m such that ψ(n, a) also holds. Simple application of the
identity laws show this cannot be. Then universal introduction completes
the proof. The rest of the bas case is similar.
To complete the induction step, we go through each of the generation schema
e

and use induction in P E to establish the claim. The proofs for each of these
in

cases is longer than the first case, but involves no further conceptual diffi-
culty. 
nl

T HEOREM 218. P E case-by-case captures all recursive sets.

P ROOF. Suppose D ⊆ ω is recursive. Then by Exercise187, we know there

O

is a total recursive function χD : ω → ω such that


0 if n ∈ D
χD (n) =
1 if n ∈
/ D.
 10.1. THE DIAGONAL LEMMA 134

By Lemma 217there is a Σ01 formula ϕ(x, y) such that

χD (n) = m ⇒ P E ` ∀y(ϕD (n, y) → y = k).

We now claim that the formula ϕD (x, 0) will suffice to capture D; i.e., we shall
have
n ∈ D ⇒ P E ` ϕD (n, 0)
and
n∈
/ D ⇒ P E ` ¬ϕD (n, 0).

To see the first of these suppose that n ∈ D. From here we see that χD (n) = 0
and by Σ01 completeness, we have P E ` ϕD (n, 0), which is what we want.
On the other hand, let us suppose that n ∈ / D. Then χD (n) = 1 and by
0
Σ1 completeness, we have P E ` ϕD (n, 1). But then since 0 6= 1, we may
prove from the second fact about ϕD , that P E ` ¬ϕ(n, 0), which is what we
c Toby Meadows

wanted. 
.1 f
t
[Link]. Provability and substitution. Let is-a-proof-of be the relation be-
v1 ra
tween the code of a sentence pϕq and the code of a derivation d of that
sentence. By Church’s thesis, we claim that the is-a-proof-of relation is re-
cursive. Given any pair of a code for a sentence and a code for a derivation,
we may verify in a finite amount of time whether or not it proves sentence.
D

To see this suppose, we were using a Prawitz proof system. We might de-
code, so to speak, the derivation into its diagramatic form and then verify
that every one (of the finitely many) applications of rules was correctly ap-
plied. If so, then the pair belongs in the set; otherwise not. This algorithm
defines a total recursive function which can be made to give the character-
e

istic function of the set of (codes of) sentences and derviations. Thus by
in

Exercise 187, this is a recursive set.

Now since the relation is recursive, we may case-by-case capture the sentence-
nl

derivation pairs using a formula Bw (x, y) such that

d codes a proof of ϕ ⇒ P E ` Bw (x, y)

O

and

d does not code a proof of ϕ ⇒ P E ` ¬Bw (x, y).

 10.1. THE DIAGONAL LEMMA 135

B(x, y) will be a Σ01 formula as can be seen from the proof of Theorem218
above.
Let provability be the property of being the code number of a theorem of P E.
With regard to some pϕq, it says that there is some n such that n is a proof
of ϕ. Since Bw represents a recursive set we can see that the set of codes of
provable sentences is recursively enumerable. We claim it is the domain of
a partial recursive function.
To see this, suppose again that we are using a Prawitz proof system and
that we are trying to verify whether or not ϕ is provable. We then let our
algorithm take codes n of proofs and verify whether or not they are proofs of
ϕ. If they are, then the programme is instructed to halt; otherwise, it keeps
looping.
Moreover, we can denote the provability relation by a Σ01 senten B(x) which
c Toby Meadows

is such that:
.1 f
t
B(x) ↔ ∃n Bw (x, n).

This is how we we define provability.

ra
Finally, suppose that x = pϕ(v)q is a formula of arithmetic with at most one
free variable. We let Sub(x, y, z) say that z is the code of the formula that
results when we substitute the numeral for y in the free variable places of
D

the formula coded by x. It should be clear, by Church’s thesis that this is

a recursive relation and thus we shall assume that Sub(x, y, z) stands for a
Σ01 formula of arithmetic. To see this, define an algorithm which takes the
v1

code of a formula, a number, and the putative result of a subsitution. The

algorithm should check whether the result is correct. It should be clear that
the algorithm only need a finite amount of time to verify this, moreover we
e

can make it so that it defines the characteristic function of the set of such
triples. Thus this set is recursive.
in

We summarise these results in the following table:

nl

Set type Set ω\Set Formula

SP = {hpϕq, di| d codes a proof of ϕ in rec Σ01 Σ01 Bw (x, y)
O

P E}
P {pϕq | ϕ is provable in P E} r.e. Σ01 ?? B(x)
Sub{hpϕ(v)q, y, zi| y codes the result of rec Σ01 Σ01 Sub(x, y, z)
substituting y for v in ϕ(v)
 10.2. INCOMPLETENESS 136

10.1.2. The diagonal lemma. We now show how to make a sentence

which says of itself that it is not provable. In fact, we show something
stronger.

L EMMA 219. For any arithmetic formula ϕ(x) there is a sentence γ such that

P E ` γ ↔ ϕpγq.

P ROOF. Let us define Diag(x, y) to be Sub(x, x, y).

Let χ(x) ↔d ∃y(Diag(x, y) ∧ ϕ(y)).
Let pχ(x)q = a.
Let γ be χ(a) and pγq = g.
Then it should be clear that

P E ` ∀y(Diag(a, y) ↔ y = g).
c Toby Meadows

By definition we have.1 f
t
P E ` γ ↔ ∃y(Diag(a, y) ∧ ϕ(y)).
v1 ra
But combining these, we see that

P E ` γ ↔ ∃y(y = g ∧ ϕ(y))

and so
D

P E ` γ ↔ ϕ(g)
which, by definition, just means

P E ` γ ↔ ϕpγq

which is what we wanted to show. 

e

10.2. Incompleteness
in

10.2.1. Four theorems.

nl

[Link]. Incompleteness via soundness (Gödel).

(Soundness) If ` ϕ, then N |= ϕ.
O

This actually entails consistency.

T HEOREM 220. If P E is sound, then there is some sentence γ such that P E 0 γ

and P E 0 ¬γ.
 10.2. INCOMPLETENESS 137

P ROOF. Using Lemma 219, let γ be such that:

P E ` γ ↔ ¬Bpγq.

Now suppose for reductio that P E ` γ. Then there is a proof of γ in the

system P E. Thus we have
N |= B(pγq)
and since B is Σ01 and P E is Σ01 -complete, we have

P E ` Bpγq.

But then by our definition of γ we have

P E ` ¬γ

and so by soundness we have both N |= γ and N |= ¬γ: a contradiction.

Thus, P E 0 γ.
c Toby Meadows

Now suppose for reductio that P E ` ¬γ. By definition of γ, we then get

.1 f
t
P E ` Bpγq.
v1 ra
Thus by soundness we have
N |= Bpγq
and since B semantically represents provability we then have
D

P E ` γ.

Then by soundness again, we get N |= γ and N |= ¬γ which is a contradiction.

Thus, P E 0 ¬γ. 

[Link]. Incompleteness via consistency and ω-consistency (Gödel).

e

D EFINITION 221. A theory T in the language of arithmetic is ω-inconsistent

in

if ∃xϕ(x) is in T and for all n, ¬ϕ(n) is in T too. T is ω-consistent if it is not

ω-inconsistent.
nl

R EMARK 222. This property is related to the existential witnessing property

we saw in Week 5.
O

F ACT 223. ω-consistency implies consistency.

T HEOREM 224. Suppose P E is ω-consistent. Then there is some sentence γ

such that P E 0 γ and P E 0 ¬γ.
 10.2. INCOMPLETENESS 138

The proof is much the same as the last one, so we’ll have less detail this
time.

P ROOF. Let γ be such that P E ` γ ↔ ¬Bpγq.

(P E 0 γ) Exercise.
(P E 0 ¬γ) Suppose for reductio that P E ` ¬γ. Then by definition of γ we have

P E ` Bpγq

or in other words,
P E ` ∃xBw (pγq, x).

Now suppose for reductio that there was some n ∈ ω such that

N |= Bw (pγq, n).
c Toby Meadows

Then since Bw semantically represents the proof relation in P E, we have

.1 f PE ` γ

t
which is contrary to our initial assumption. Thus there is no such n; i.e., for
v1 ra
all n we have
N |= ¬Bw (pγq, n)
and since Bw case by case captures this relation, we have
D

P E ` ¬Bw (pγq, n)

for all n ∈ ω. But this, in conjunction with our initial assumption that

P E ` ∃xBw (pγq, x)

means that P E is ω-inconsistent, which is contrary to our initial assump-

tion. Thus P E 0 ¬γ. 
e
in

[Link]. Incompleteness via consistency (Rosser).

T HEOREM 225. Suppose P E is consistent. Then there is a sentence ρ such

nl

that P E ` ρ and P E 0 ¬ρ.

O

P ROOF. By Lemma 219, let ρ be such that

ρ ↔ ∀y(Bw (pρq, y) → ∃z < y Bw (p¬ρq, z)).

The proof that P E 0 ρ is similar to the previous proof.

 10.2. INCOMPLETENESS 139

Suppose for reductio that P E ` ¬ρ. Then by definition of ρ, we also have

P E ` ¬∀y(Bw (pρq, y) → ∃z < y Bw (p¬ρq, z)).

It should be clear that for some m we have both

N |= Bw (p¬ρq, m)
N |= ∀y(y = m ∨ y < m → ¬Bw (pρq, y).

The first follows since Bw semantically represent the proof-of relation and
the second follows from the consistency of P E.
Thus we have

P E ` Bw (p¬ρq, m)
c Toby Meadows

P E ` ∀y(y = m ∨ y < m → ¬Bw (pρq, y))

.1 f
t
by Σ01 -completeness. We then see that from the first of these that

P E ` ∀y(m < y → ∃z < y Bw (p¬ρq, z)

v1 ra
and by P E alone we have1

P E ` ∀y(¬(y = m ∨ y < m) → m < y).

D

Contraposing the second or the statements above we get

P E ` ∀y(Bw (pρq, y) → ¬(y = m ∨ y < m)).

Thus
P E ` ∀y(Bw (pρq, y) → ∃z < y Bw (p¬ρq, z));
i.e.,
e

PE ` ρ
in

which contradicts the consistency of P E. Thus P E 0 ¬ρ. 

nl

[Link]. Unprovability of consistency (Gödel). We now show (less for-

mally) that P E is not capable of proving its own consistency. To do this
O

we look further at the statement of the theorem 225. It says:

• If P E is consistent, then P E 0 ρ.

1
Prove this.
 10.2. INCOMPLETENESS 140

But what does consistency mean? It just says that there is no proof from
P E of both ϕ and ¬ϕ for any sentence. However, we can actually express
this a little more simply by an equivalent statement. We claim that:

• P E’s consistency is equivalent to the statement that 0 = 1 is not

provable from P E.

To see this, let us first go from left to right, but via contraposition. Thus
we suppose that 0 = 1 is provable from P E. Well we also know that 0 6= 1
is provable from P E. Thus there is some ϕ such that both ϕ and ¬ϕ are
provable from P E. For the other direction, let us suppose that for some ϕ
both ϕ and ¬ϕ are provable from P E. But then we know that any sentence
of LAr is probable in P E; thus 0 = 1 is provable in P E.
Thus we shall let Con(P E) be the sentence ¬∃n Bw (p0 = 1q, n).
c Toby Meadows

But now this puts us in a position to state Theorem 225 in the language of
arithmetic. Thus we write:
.1 f
• Con(P E) → ¬Bpρq. t
v1 ra
Moreover, since B semantically represents provability, we must have:

• N |= Con(P E) → ¬Bpρq;
D

i.e., the corresponding sentence is true in the standard model.

Now it also turns out, although we shall not show it here that:

F ACT 226. P E ` Con(P E) → ¬Bpρq.

e

This means that we can not only express Theorem 225 in the language of
in

arithmetic, but we can actually prove it in P E. The proof of this is beyond

our present scope, but the impact of it is very interesting and worth noting.
From here, we may simply show that P E cannot prove its own consistency.
nl

T HEOREM 227. P E 0 Con(P E).

O

P ROOF. Suppose for reductio that P E ` Con(P E). Then by Fact 226, we
have P E ` ¬Bpρq. But by the definition of ρ as a diagonal sentence, we also
have P E ` γ. But this contradicts Theorem 225; thus, P E 0 Con(P E). 
 10.2. INCOMPLETENESS 141

[Link]. What about other theories? In this section, we have only con-
sidered P E, which might lead us to think that the issue of undecidability
can be confined to P E. However, it should be obvious that the arguments
that we have used here will be extendable to any theory which is:
• capable of talking about its own syntax; and
• getting the facts about recursive functions right.

10.2.2. Two more theorems. We have seen last week that a theory is
decidable if it’s theorems form a recursive set. However, we have seen that
some sets are recursively enumerable without being recursive. The following
definition links the recursion theoretic idea with a logical one.

D EFINITION 228. A theory Γ is semi-decidable if Γ is a recursively enumer-

able.
c Toby Meadows

[Link]. The set of the theorems of P E are not recursive; i.e., P E is not
decidable. .1 f
t
T HEOREM 229. Suppose P E is consistent. P E is not decidable.
v1 ra
P ROOF. Suppose for reductio, that P E is decidable. Then Γ = {pϕq | P E `
ϕ} is recursive. Since we can capture every recursive function in the lan-
guage of arithmetic, there must be some (Σ01 ) formula B(x) such that
D

pϕq ∈ Γ ⇒ P E ` Bpϕq

and

pϕq ∈
/ Γ ⇒ P E ` ¬Bpϕq.
Using the diagonal lemma, let γ be such that
e

P E ` γ ↔ ¬Bpγq.
in

But then supposing γ ∈ Γ we have

nl

γ ∈ Γ ⇒ P E ` Bpγq
O

⇔ P E ` ¬γ
⇒ PE 0 γ
⇒ γ∈
/Γ
 10.2. INCOMPLETENESS 142

which is a contradiction, so γ ∈
/ Γ. (Note that for the second ⇒ we appeal to
the consistency of P E.) But then we have

γ∈
/ Γ ⇒ P E ` ¬Bpγq
⇔ PE ` γ
⇔ γ∈Γ

which is another contradiction. Thus Γ is not recursive. 

[Link]. The set of satisfiable sentences is not recursively enumerable.

We finally return to one of the questions posed early on in the module.
• Is there a way of tweaking the tableau system for first order logic so
that we don’t need to deal with infinite branches?
In the case of propositional logic, we can certainly do this since we never
c Toby Meadows

need to get infinite branches. However, the answer in the case of first order
logic is negative. .1 f
t
P ROPOSITION 230. Let P E − Ind be P E without the induction schema. Then
P E − Ind is Σ01 -complete and can prove Lemma 217.
v1 ra

P ROOF. An inspection of the proof of the Σ01 -completeness of P E will show

that induction was not used there. More work is required to remove induc-
tion from Lemma 217. 
D

Clearly P E −Ind is incomplete like P E. However, it is also boringly complete.

For example, without induction we cannot prove simple facts like

∀x(x + 0 = 0 + x)

so it is not a very useful theory of arithmetic. Nonetheless it is useful for the

e

following reason.
in

F ACT 231. P E − Ind is finitely axiomatisable.

nl

P ROPOSITION 232. P E − Ind is not decidable. Moreover, the set

{pϕq | P E − Ind 0 ϕ}
O

is not recursively enumerable.

P ROOF. The first part is a simple adaptation of the proof of Theorem 229.
Indeed, we could have made more general proof there.
 10.2. INCOMPLETENESS 143

For the second part, we need to show that

{pϕq | P E − Ind ` ϕ}

is recursively enumerable. This is left as an exercise. Once we’ve shown that

it is clear that its complement cannot be recursively enumerable too. 

C OROLLARY 233. The set V = {pϕq | |= ϕ} is recursively enumerable but not

recursive.

P ROOF. The first part can be established by Church’s thesis and the
methods discussed at the beginning of this week.
For the second part, we shall suppose for reductio that ω\V is recursively
enumerable.
Let π be the conjunction of the sentences in P E − Ind + T ri.
c Toby Meadows

Let f : ω → ω be the total recursive function which takes codes of sentences

.1 f
t
pϕq and returns pρ → ϕq. (We appeal to Church’s thesis, but it should be
obvious that this is recursive. If not think about what you need to do to get
ra
the new code.)
Now consider the set C = {pϕq | |= f (ϕ)}.2 We claim that ω\C is recursively
enumerable. Since we are assuming that ω\V is recursively enumerable,
there is some partial recursive function ϕe whose domain is ω\V . To get a
D

function with domain is ω\C let ψ be such that

ψ(n) = m ⇔ ϕe (f (n)) = m.
v1

This is clearly partial recursive and it domain is clearly ω\V .

But then we see that
e

C = {pϕq | |= ρ → ϕ}
in

= {pϕq | ` ρ → ϕ}
= {pϕq | P E − Ind + T ri ` ϕ}.
nl

However, we know from Proposition 232, that ω\C is not recursively enu-
O

merable. This is a contradiction, thus ω\V is not recursively enumerable

and V is not recursive. 
2
My notation is a little sloppy here since we don’t put codes of sentences into the context of
|=. However, the meaning should still be clear.
 10.2. INCOMPLETENESS 144

C OROLLARY 234. The set Σ = {pϕq | ϕ is satisfiable.} (i.e., the set of satisfiable
sentences) is not recursively enumerable.
c Toby Meadows

.1 f
t
v1 ra
in D
e
nl
O
 10.3. EXERCISES. 145

10.3. Exercises.

E XERCISE 235. Show that ω-consistency implies consistency.

E XERCISE 236. Is there a negation complete theory which is not decidable.

E XERCISE 237. Complete the first half of the proof of Theorem 224.

E XERCISE 238. If P E was not consistent, would it be decidable.

c Toby Meadows

.1 f
t
v1 ra
in D
e
nl
O