ELEMENTS OF DEDUCTIVE LOGIC

AC PASEAU
Faculty of Philosophy
Oxford University

Lecture Notes
Hilary 2019

Corrections to: paseau@[Link]

 The notes below are a write-up of the EDL lectures in Hilary 2019. They
contain most of the results stated in those lectures. I’ve omitted some of the
‘chat’—motivating remarks, informal discussion, and sometimes illustrating
examples. You will also notice one or two improvements on the lectures
and some additions. As this is the first year of these notes’ existence, there
are bound to be at least some typos, notational inconsistencies and the like.
Comments and corrections should be sent to me at: paseau@[Link].1

Lecture 1
In an ideal world, we would devote the first couple of lectures to a review of
mathematical notation and basic proof techniques (e.g. argument by contra-
position, argument by contradiction). There’s no time for that, so I refer you
to Stephen Blamey’s notes. That said, it’s worth mentioning notation we’ll
use fairly often: A „ B means that A is a (proper or improper) subset of B,
in other words that every element of A is an element of B; A Y B  tx : x P A
or x P B u is the set of elements in A or B (or both); A X B  tx : x P A
and x P B u is the set of elements in both A and B ; and AzB  tx : x P A
and x R B u is the set of elements of A not in B. For simplicity, I’ll be casual
about use and mention, as I was in the last sentence by omitting quotation
marks, and I’ll certainly dispense with Quine quotes (if you don’t know what
that means, don’t worry). We’ll also assume knowlege of The Logic Manual,
covered in the Introduction to Logic course.
The main mathematical tool we’ll need is proof by induction. I expect
most of you have seen this before, so I’ll be relatively brief. One stan-
dard form of the PMI (Principle of Mathematical Induction), in premise–
conclusion form, is:

Φp0q 
@n Φpnq Ñ Φpn 1q

@nΦpnq
The quantifiers here range over the natural numbers (0, 1, 2, 3, . . .), and Φ is
any numerical property. Observe that this statement of the PMI is informal,
i.e. formulated in the language of informal mathematics. If/when you take a
more advanced course in logic, you’ll come across a formal statement of the
1
I’m grateful to past and present EDL students, especially Joe Deakin, Emma Baldas-
sari, Paolo Marimon and Raymond Douglas, for comments. Thanks also to Beau Madison
Mount and Joel David Hamkins.

1
PMI in an extension of L that contains function symbols. Here’s another
version of the PMI, sometimes called the strong form:

Φp0q 
@n @k ¤ nΦpkq Ñ Φpn 1q

@nΦpnq
It’s an easy exercise to show that these two versions of the PMI are equivalent
(and in particular that they are no different in strength). As you’ll see, we’ll
tend to use the latter more than the former. In lectures, I also mentioned the
Least Number Principle, another equivalent of the PMI, which states that
if at least one natural number has property Φ then there is a least natural
number with property Φ.
Let’s now have two examples of the PMI’s use, the first from arithmetic,
the second from logic.

Proposition 1 The sum of the natural numbers from 0 to N is N N 1p q.

2

You may have come across non-inductive proofs of this proposition. Our
proof will be by induction.

Proof. First, let’s check that 0 has the property. Yes, it does, since the
sum of the natural numbers from 0 to 0, namely 0, is indeed 0p02 1q  0. So
we’ve checked the base case.
Next, suppose that the sum of the natural numbers from 0 to N is N pN2 1q .
This is the assumption in the induction step. On that assumption, we need
to prove that the sum of the numbers from 0 to N 1 is pN 1qppN 1q 1q

pN 1qppN 2q . Now
2

2
 p q
Σ i Σ i N 1 N N 1
N 1  pN 1qp2 N 2q
¤¤
0 i N 1 ¤¤
0 i N 2

The middle one of the three equations follows from the induction hypothesis
and the last one summarises a short algebraic manipulation. Since we’ve
proved the base case and the induction step, we can conclude by the PMI
that all numbers have the stated property. 

The next example of a proof by induction is much more typical of the kind of
reasoning used in this course. Before that, though, we need some definitions.

Definition 1 Let φ be an L1 -formula. Connpφq is the set of connectives in

φ. N Connpφq is the number of occurrences of connectives in φ. Atompφq is
the set of atoms in φ and SenLettpφq is the set of sentence letters in φ.

2
 
Suppose for example that φ is ppP ^ Qq ^ Rq _ P1 . Then Connpφq 
t^, _u, N Connpφq  3, and Atompφq  SenLettpφq  tP, Q, R, P1u. In
fact, Atompφq  SenLettpφq more generally for all L1 -sentences φ. Note
that Connpφq is a set of connective types, whereas N Connpφq counts the
number of connective tokens in φ. Many of the proofs in this course show
that all formulas have some property Φ ‘by induction on the complexity of φ’.
This means that the induction is on N Connpφq: we prove that a formula with
no connectives has the property, and that if a formula with n connectives has
the property Ψ then a formula with n 1 connectives also has the property Ψ;
we then conclude that all formulas have the property. That gives us a handy
way of proving facts about all formulas, by associating them with natural
numbers in this fashion. In other words, what we’re doing is proving that 0 is
such that every formula with that many connectives has the property Ψ, and
that every number n is such that every formula with that many connectives
has the property Ψ, then n 1 is also such that every formula with that
many connectives has the property Ψ. So every number n is such that every
formula with that many connectives has the property Ψ; so all formulas have
the property.
Here’s an example of this approach at work.

Proposition 2 Suppose Connpφq „ tØu Then φ is not a contradiction, i.e.

there’s an L1 -structure in which φ is true.

Proof. We’ll use induction on a stronger claim, for reasons that will
become apparent. Let Φpnq be the claim:

Suppose N Connpφq  n and Connpφq „ tØu. Let A be an

L1 -structure such that |α|A  T for all α P Atompφq. Then
|φ|A  T .
Clearly, the proposition we’ve set out to prove follows from @nΦpnq. So it
will be sufficient to prove @nΦpnq, which we’ll do using the second version of
the PMI mentioned above.
The base case: suppose N Connpφq  0. Then φ is an atom. So if
|α|A  T for all α P Atompφq, it follows that |φ|A  T since φ is an atom of
φ (indeed the only atom of φ).
Now for the induction step. We assume that @k ¤ nΦpk q. Suppose then
that N Connpφq  n 1 and Connpφq „ tØu. Then φ  φ1 Ø φ2 for some
φ1 , φ2 such that Connpφi q „ tØu and N Connpφi q ¤ n, for i  1, 2. (In fact,
we know that N Connpφ1 q N Connpφ2 q  n.)
Suppose that A is an L1 -structure such that |α|A  T for all α P Atompφq.
Since Atompφ1 q, Atompφ2 q „ Atompφq, it follows that |α|A  T for all α P

3
Atompφi q, for i  1, 2. Hence by the induction hypothesis we know that
|φ1|A  T and |φ2|A  T . The truth-table for Ø then yields, for this same
structure A :

|φ|A  |φ1 Ø φ2|A  T

By the Principle of Mathematical Induction, @nΦpnq, which proves our propo-

sition. 

Notice two facts about this proof. We had to use the second rather
than the first version of the PMI because the inductive step involves two
formulas φ1 and φ2 whose complexity is unknown. All we know about the
formulas’ complexity is that N Connpφ1 q N Connpφ2 q  n, so our inductive
hypothesis must perforce be that the required property holds for formulas of
any complexity ¤ n. The second point is that we proved the proposition from
a stronger assumption: whereas the proposition states that a formula whose
only connective if any is Ø is true in some L1 -structure, our proof showed
that such a formula is true in the structure that maps all the formula’s atoms
to T . If in the inductive step all we could draw on were the hypotheses that
φ1 is true in some structure A1 and that φ2 is true in some structure A2
then we would have been stuck. For without knowing that A1 and A2 agree
on the atoms of φ, we couldn’t use them to define an L1 -structure in which
φ  φ1 Ø φ2 is true. Hence the moral: choose your inductive hypotheses
wisely!
At the end of the first lecture, we covered some of the material to follow
in the next section. But I’ll end the section here since it’s a natural break.

4
Lecture 2
Wherein we make a start on metalogic proper and prove the Interpolation
Theorem for propositional logic. Henceforth we’ll use 1 and 0 as truth-values
rather than T and F , as we can algebraically manipulate the former more
easily.
It’s useful to consider a slight extension of L1 which I’ll (unimaginatively)
call L1 . This logic expands the language of L1 with two atomic sentences
J and K such that |J|A  1 and |K|A  0 for all structures A. Note that
J and K are atoms but not sentence letters. So whereas in L1 , SenLettpφq
is always identical to Atompφq, these notions can come apart in L1 ; e.g.
SenLettpP Ñ Jq  tP u whereas AtompP Ñ Jq  tP, Ju. We’ll assume
that L1 -consequence respects L1 -consequence, i.e. that a subset Γ of L1 -
sentences entails an L1 -sentence φ in L1 iff Γ entails φ in L1 .
There now follows a sequence of lemmas and definitions, of great use for
the rest of the course. Intuitively, the next lemma tells us that the truth-
value of a sentence in a structure is fixed by the truth-value of its sentence
letters in that structure. Although that should seem obvious enough, it does
require proof. The lemma, note, applies to both L1 and L1 .

Lemma 3 (Relevance Lemma) Suppose |α|A  |α|B for all α P SenLettpφq.

Then |φ|A  |φ|B .

Proof We prove the result by induction on the complexity of φ, that is,

by induction on N Connpφq. From now on, it’s understood that that is what
we mean by saying ‘by induction on the complexity of φ’.
For the base case, we consider φ of complexity 0, i.e. sentences with no
connectives. So φ is either a sentence letter or, in the case of L1 , it could
also be one of J or K. If A and B agree on the sentence letters of φ and φ is
a sentence letter, then A and B must agree on φ. And if φ is J or K, then A
and B agree on φ since all valuations agree on J or K (|J|A  |J|B  1 for
all A and B, and |K|A  |K|B  0 for all A and B).
For the inductive step, we use the ‘strong’ form of induction once more.
So suppose the relevance property holds for all formulas of complexity ¤ n.
A formula φ of complexity n 1 is of the form ψ or φ1 ^ φ2 or φ1 _ φ2 or
φ1 Ñ φ2 or φ1 Ø φ2 , where ψ, φ1 and φ2 are all of complexity ¤ n. If A and
B agree on the atoms of φ then they must agree on the atoms of ψ, φ1 and φ2
in each of these five cases. By the inductive hypothesis, that means that the
truth-value of ψ in A is the same as its truth-value in B (in the first case),
and the truth-values of φ1 and φ2 in A are the same as their truth-values in
B (in the other four cases). Since the truth-value of ψ is determined by

5
that of ψ, and the truth-value of each of φ1 ^ φ2 and φ1 _ φ2 and φ1 Ñ φ2
and φ1 Ø φ2 is likewise determined by those of φ1 and φ2 , A and B agree on
φ. In other words, |φ|A  |φ|B . 

One way to understand the Relevance Lemma is that it underwrites the

use of the usual, finite, truth-tables. For consider a truth-table such as:

P Q P ^Q
1 1 1
1 0 0
0 1 0
0 0 0

The usual way of doing things—including ours—has each of the rows

representing not a structure or valuation but a class of stuctures, all of which
agree on the truth-values of P and Q (but which may differ on the truth-
values of other sentence letters not represented in the table). Yet how do we
know that all structures that agree on the truth-values of P and Q agree on
the truth-value of P ^ Q? The answer: by the Relevance Lemma! So if you
thought that the Relevance Lemma didn’t require proof, it’s perhaps because
you hadn’t fully appreciated that propositional structures are specified by
their assignment of truth-values to all sentence letters.2
We now offer a sequence of definitions, in which Γ is a set of sentences
and A is a structure. The definitions, which apply to both L1 and L1 , set
out some widely-used notational variants for concepts you’ve already come
across.

Definition 2 A ( φ means that |φ|A  1; we say ‘A satisfies φ’. And we

write A ( Γ to abbreviate: for all γ P Γ, A ( γ.
Γ is satisfiable iff it’s semantically consistent, i.e. just when there’s a
structure A such that A ( Γ. Γ is unsatisfiable otherwise, i.e. just when for
all A, A * Γ.
2
(A non-examinable note for students who know about countable and uncountable
sets.) Each row in fact represents uncountably many structures. To see that there are
uncountably many L1 -structures, observe that there is an onto (surjective) map from
the class of structures to the numbers in the closed interval r0, 1s, which is well known
to be uncountable. Simply enumerate the sentence letters in a list α1 ,    , αn ,    and
map structure A to the real number Σ |αi |A 2
i , which you can think of as the number’s
¤
1 i
binary representation. Observe that the map is onto but not one-one since for example
1  2
1 0  2
2 0  2
3 . . .  0  2
1 1  2
2 1  2
3 . . .. (In other words, the real number
corresponding to the binary decimal 0.1000000 . . . is the same as that corresponding to
the binary decimal 0.0111111 . . ., just as 0.5  0.4999999 . . ..) A similar argument shows
that uncountably many structures agree on any finite subset of the set of sentence letters.

6
 φ is a tautology just when, for all A, A ( φ. And φ is a contradiction
just when, for all A, A * φ.
Γ ( φ means: for all A if A ( Γ then A ( φ.
φ and ψ are logically equivalent just when: for all A, A ( φ iff A ( ψ.
We note that the symbol ‘(’ is ambiguous in logic. ‘A ( φ’ means that
the structure A satisfies the sentence φ, whereas ‘Γ ( φ’ means that all
structures that satisfy Γ also satisfy φ. In practice, it would be hard to
confuse the two, as both notation and context should make it clear whether
the symbol to the left of ‘(’ denotes a set of sentences or a structure. In
lectures, I also used φ )( ψ to mean that φ and ψ are logically equivalent,
but I won’t do so here.
Let’s now move on to substitution. We’d like to capture the idea that we
can replace all occurrences of a sentence letter, or more generally sequence
of letters, with some formula(s). This motivates the following definition.
Definition 3 Let Sen(L) be the set of logic L’s sentences. Let π : SenLettpL1 q Ñ
SenpL1 q, i.e. π is a function which maps the sentence letters of L1 to sen-
tences of L1 . Then we extend π to a map defined on all the sentences of
L1 which by abuse of notation we also label π and which we represent by a
superscript, as follows:
απ  πpαq if α P SenLettpL1 q
Jπ  J
Kπ  K
p φqπ  pφπ q
pφ ^ ψqπ  φπ ^ ψπ
pφ _ ψqπ  φπ _ ψπ
pφ Ñ ψqπ  φπ Ñ ψπ
pφ Ø ψqπ  φπ Ø ψπ
We also extend π to sets of sentences in the obvious way: Γπ  tγ π : γ P
Γu.
Given such a map π : SenLettpL1 q Ñ SenpL1 q, we define a correspond-
ing map on structures. Given any structure A, let Aπ be the structure defined
by the following stipulation:
|α|A  |πpαq|A for all α P SenLettpL1 q
π

The value |φ|A for a complex sentence φ is then fixed by the values of |α|A
π π

for φ’s sentence letters (by the Relevance Lemma). The following lemma
shows that we can ‘move the superscript down from the sentence to the
structure’.

7
Lemma 4 (Substitution Lemma) |φπ |A  |φ|A π , for all φ and A.

Proof By induction on the complexity of φ, as usual. For the base

case, suppose that φ is a sentence letter α. Then by the definition of απ ,
|απ |A  |πpαq|A. And by the definiton of Aπ , |α|Aπ  |πpαq|A also. The case
of J is straightforward: Jπ  J and J is true in all structures; similarly,
Kπ  K and K is false in all structures.
For the inductive step, we’ll need to consider five cases. I’ll do two of
these cases and leave the remaining three to you. The first case is when
φ  ψ. Using the inductive hypothesis and the fact that | χ|A  1
|χ|A
for any sentence χ and structure A:

|φπ |A  |p ψqπ |A
 | ψ π |A
 1
| ψ π |A
 1
| ψ |A π

 | ψ |A π

 |φ|A π

The second case, in which φ  φ1 ^ φ2 , is very similar. We use the

inductive hypothesis and the fact that |χ1 ^ χ2 |A  |χ1 |A |χ2 |A :

|φπ |A  |pφ1 ^ φ2qπ |A

 |φπ1 ^ φπ2 |A
 |φπ1 |A|φπ2 |A
 |φ1|A |φ2|A π π

 |φ1 ^ φ2|A π

 |φ|A π

The other cases are entirely analogous. 

We draw a couple of corollaries from the lemma. Their proof is left as an

exercise.

Corollary 5 If Γ ( φ then Γπ ( φπ .
Corollary 6 Suppose ( φi Ø ψi (i.e. φi and ψi are logical equivalents) for
1 ¤ i ¤ N . Let χpφ1 {α1 ,    , φN {αN q be the formula obtained by replacing all

8
occurrences (if any) of the sentence letter αi in χ by φi , for 1 ¤ i ¤ N ; and
let χpψ1 {α1 ,    , ψN {αN q be the formula obtained by replacing all occurrences
(if any) of the sentence letter αi in χ by ψi , for 1 ¤ i ¤ N . Note that
this is simultaneous, not sequential, substitution in the sense of π. Then
( χpφ1{α1,    , φN {αN q Ø χpψ1{α1,    , ψN {αN q.
We now come to the highlight of this lecture.
Theorem 7 (Interpolation Theorem for L1 ) Suppose φ ( ψ. Then there
is a sentence λ such that: (i) Senlettpλq „ Senlettpφq X Senlettpψ q; (ii)
φ ( λ; and (iii) λ ( ψ. λ is known as an interpolant for the sequent φ ( ψ.
Proof We may assume that SenlettpφqzSenlettpψ q is non-empty; for if
it’s empty then Senlettpφq „ Senlettpψ q, in which case we may take φ as
our interpolant. Let’s now define a set Π of substitutions as follows:
Π  tπ : π pαq P tJ, Ku for all α P SenlettpφqzSenlettpψ q and π pαq 
α if α is a sentence letter not in SenlettpφqzSenlettpψ qu
Intuitively, a substitution π gets rid of the sentence letters in φ but not ψ by
replacing each of them by either J or K. Π then consists of all the possible
ways of doing so: it’s the set of all substitutions of this kind.
Given Π, we define λ as follows:
š
λ φπ
P
π Π

Thus if SenlettpφqzSenlettpψ q is a set of size n, λ will be a disjunction of 2n

sentences. It remains to prove three things: (i) Senlettpλq „ Senlettpφq X
Senlettpψ q; (ii) φ ( λ; and (iii) λ ( ψ.
(i) That Senlettpλq „ Senlettpφq X Senlettpψ q is immediate from the def-
inition of λ, since SenLettpφπ q „ Senlettpφq X Senlettpψ q for each
disjunct φπ in λ.
(ii) Suppose A ( φ. Consider the substitution function π defined as follows
on sentence letters α:
$
'
& J if α P SenlettpφqzSenlettpψ q and |α|A  1
π pαq  K if α P SenlettpφqzSenlettpψ q and |α|A  0
'
otherwise, i.e. if α R SenlettpφqzSenlettpψ q
%
α
Clearly, A  Aπ since they agree on all sentence letters (formally, an
inductive argument would be required here). Now by the Substitution
Lemma, |φπ |A  |φ|Aπ . So since A  Aπ , |φπ |A  |φ|A  1. Since φπ
is a disjunct in λ, λ is true in A. We conclude that φ ( λ.

9
 š
(iii) Suppose A ( λ. Since λ  φπ , A ( φπ for some π
P Π, i.e. |φπ |A  1
P
for this π. By the Substitution Lemma, it follows that |φ|A  1 for
π Π
π

this π. As φ ( ψ, we deduce that |ψ |A  1. Now since Aπ and A

π

agree on all the sentence letters in ψ, we deduce from the Relevance

Lemma that |ψ |A  1. Thus λ ( ψ. 

It’s worth thinking about the relative strength of interpolants for a given
sequent. How does λ as defined in the theorem’s proof compare to other
interpolants for the sequent φ ( ψ?
The interpolation theorem for L1 is a relatively straightforward corollary
of the interpolation theorem for L1 . To prove it, we require a couple of
further lemmas.

Lemma 8 Suppose φ P SenpL1 q s.t. Atompφq „ tJ, Ku. Then φ is logically

equivalent (in L1 ) to J or to K.

Proof. By induction on the complexity of φ; left as an exercise. Or prove

this more directly from the Relevance Lemma, since any two structures must
agree on the truth-value of φ. 

Lemma 9 Suppose φ P SenpL1 q s.t. SenLettpφq is non-empty. Then φ is

logically equivalent (in L1 ) to a formula ψ such that Atompψ q  SenLettpφq.

Proof. By induction on the complexity of φ; left as an exercise. 

Theorem 10 (Interpolation Theorem for L1 ) Suppose φ ( ψ, with φ

not a contradiction and ψ not a tautology. Then there is a λ such that: (i)
φ ( λ ( ψ; and (ii) Senlettpλq „ Senlettpφq X Senlettpψ q.

Proof. Suppose φ ( ψ, with φ, ψ P SenpL1 q. Consider this as a claim

about L1 -sentences (since every L1 -sentence is also an L1 -sentence). By the
Interpolation Theorem for L1 , there is an L1 -interpolant λ for the sequent
φ ( ψ whose set of sentence letters SenLettpλq is a subset of the intersection
of SenLettpφq and SenLettpψ q. There are two possibilies, depending on
whether SenLettpλq is empty or not.
Suppose SenLettpλq is empty. By Lemma 8, λ is then logically equivalent
to J or K. But if φ entails K then φ is a contradiction; and if J entails ψ
then ψ is a tautology; hence this case is excluded.
It follows then that SenLettpλq must be non-empty. So by Lemma 9, λ
is equivalent to a sentence whose atom set is SenLettpλq; the latter sentence
is the required L1 -interpolant. 

10
 The theorem is ‘best possible’ because we can’t remove the restriction to
φ not being a contradiction or ψ not being a tautology. To see this, consider
for example the sequents P ( Q _ Q and P ^ P ( Q.

11
Lecture 3
Last time we proved the Interpolation Theorem for L1 , and, as a corollary,
the Interpolation Theorem for L1 . The topic of today’s lecture is duality.
It’s a fairly self-contained topic, popular with EDL examiners, so well worth
getting under your belt. To introduce it, it will be useful to know something
about truth-functions.

Definition 4 A truth-function is a function from an n-tuple of 1s and 0s to

1 or 0. A bit more formally, it is a function from t0, 1un to t0, 1u; here t0, 1un
is the n-fold Cartesian product of t0, 1u with itself: tlooooooooooomooooooooooon
0, 1u      t0, 1u.
ntimes
If c is an n-place propositional connective, the n-ary truth-function fc
associated with c is defined by:

for all structures A and formulas φ1 ,    φn , fc p|φ1 |A ,    , |φn |A q 

|cpφ1,    , φnq|A.
1 and 0 can be considered as the constantly true and constantly false 0-ary
truth-functions respectively.
Every formula φ is also associated with a unique truth-function fφ defined
by:

Let SenLettpφq  tα1 ,    , αn u. Then for all structures A,

fφ p|α1 |A ,    , |αn |A q  |φ|A

In the case of L1 : if SenLettpφq is empty, we associate it with the 0-ary

truth-function 1 or the 0-ary truth-function 0, as the case may be. (Lemma 8
justifies this definition.)

For example, f^ pt1 , t2 q  t1 t2 , f_ pt1 , t2 q  maxtt1 , t2 u  t1 t2
t1 t2 and

f ptq  1
t. If φ  P ^ Q then fφ  f^ , and so on.
In lectures, we then motivated the definition of the dual of a connective
by playing around with truth-tables. We’ll dispense with the pictures here,
but state the key idea. To find the dual of a connective c, take its truth-table
and turn all the 1s into 0s and 0s into 1s (in all the ‘input’ columns as well
as the ‘output’ column); this defines a new connective, c’s dual, which we
call c . Applying this procedure to ^, _ and we discover that ^  _,
_  ^, and  ; the last equation shows that is self-dual. We also
 
observe that P Ñ Q is logically equivalent to pQ Ñ P q and that P Ø Q
is logically equivalent to pQ Ø P q. Flipping a single 1 turns it into a 0 and
a single 0 into a 1, which also justifies: J  K and K  J.

12
 The most natural setting for duality is a propositional logic in which there
is a unique way to represent each connective’s dual. In the propositional
logics L1 or L1 , defining a connective’s dual involves some arbitrary choices.
For example, we can define P Ñ Q as pQ Ñ P q, or as P ^ Q, or in
countless other ways. There is no such thing as the ‘right’ definition, only
a choice to be made on pragmatic grounds. To avoid this, and to introduce
you to a third propositional logic, we work in L1 . We’ll define this logic
informally, as we did L1 .

Definition 5 L1 is a propositional logic with the same set of atoms as L1 ,

i.e. the sentence letters of L1 as well as J and K. For each n-place truth-
function f , L1 has a single n-place connective c s.t. f  fc , i.e. f is the
truth-function associated with c, for n ¥ 1. The syntax and semantics of
L1 is that of L1 with the obvious changes.

As with L1 , I encourage you to come up with L1 ’s full syntactic and se-

mantic specification. You’ll notice that in this case, the recursive syntactic
and semantic clauses can’t be individually specified, one per connective, since
there are infinitely many such connectives. So the clauses must be schematic.
No problem with this, of course, since even the specification of L1 ’s syntax
and semantics is schematic when it comes to the base cases, seeing as there
are infinitely many sentence letters.
In the definition of L1 , we’ve taken J and K as atoms; we could equally
have taken them to be 0-place connectives, and occasionally we’ll regard
them as such. We’ll also continue to use the symbols ^, _, , Ñ and Ø for
the five connectives L1 has in common with L1 (and L1 ).
We now define three dual maps on L1 . We begin with the dual of a
connective; then that of a sentence; and we end with the dual of an L1 -
structure. The highlight of the lecture and its culmination will be the Duality
Theorem, which links the last two notions.

Definition 6 (Dual of a connective) Let c be an n-place connective in

L1 with associated truth-function fc . Then its dual c is the L1 -connective
whose associated truth-function fc is defined by:

fc pt1 ,    , tn q  1
fc p1
t1 ,    , 1
tn q

for all truth-values t1 ,    tn .

We note that c exists and that it’s unique. In languages such as L1 which
lack a primitive symbol for some connectives’ duals, we’d have to define c

13
in some arbitrary fashion, as mentioned, and of course the dual map would
only be defined on the connectives the language happens to contain.
Let’s have some examples, starting with negation. (In these examples,
construe A as a variable ranging over L1 -structures.) From our definitions:
| φ|A  1
pf p1
|φ|Aqq  1
p1
p1
|φ|Aqqq  1
|φ|A  | φ|A. This
calculation shows that   , or in other words that is self-dual.
For our second example, let’s check that ^  _. Here’s the calculation:
f^ p|φ1 |A , |φ2 |A q  1
f^ p1
|φ1 |A , 1
|φ2 |A q  1
p1
|φ1 |A qp1
|φ2 |A q 
|φ1|A |φ2|A
|φ1|A|φ2|A  f_p|φ1|A, |φ2|Aq. Thus ^  _. We may similarly
check that _  ^. In fact, we can deduce that _  ^ from ^  _ and
the lemma to follow.

Lemma 11 For any connective c of L1 , c  c.

Proof

fc pt1 ,    , tn q  1
fc p1
t1 ,    , 1
tn q


 1
1
fcp1
p1
t1q,    , 1
p1
tnqq
 fcpt1,    , tnq 
We’ve defined the dual of a connective, so now let’s have the dual of a
sentence and of a structure.

Definition 7 Given an L1 -structure A, we define its dual A by stipulating

that |α|A  1
|α|A for all sentence letters α.
We also define the dual φ of an L1 -sentence φ recursively. For any
sentence letterα, α  α; also, J  K, K  J. If φ  cpφ1 ,    , φn q then

cpφ1 ,    , φn q  c pφ1 ,    , φn q.

We note that the definition of a sentence’s dual depends on that of a

connective’s dual. Note also that in the first definition we need only define
the truth-value of sentence letters in A , since the truth-values of all other
sentences are determined by these. (We also know that |J|A  1 since this
holds for all structures, and similarly |K|A  0.)
We saw earlier that the double dual of any connective is itself. The double
dual of any sentence is also itself.

Proposition 12 For all L1 -sentences φ, φ  φ.

Proof. We prove this by induction on the complexity of φ. Base case: a
sentence letter’s dual is itself, so its double dual is also itself. J  K  J
and similarly K  J  K.

14
 As for the induction step:
 
cpφ1 ,    , φn q  cpφ1 ,    , φnq 
 cpφ 
1 ,    , φn q
 cpφ1,    , φnq
 cpφ1,    , φnq
The first two equations are definitional, the third uses the inductive hypoth-
esis and the fourth the fact that c  c. 

We note a trivial corollary: φ is logically equivalent to φ. In proposi-

tional languages other than L1 , the double dual of a sentence may not be
the sentence itself; but it should at least be equivalent to it. Time now for
the most important result about duality.

Theorem 13 (Duality Theorem) For all L1 -structures A and L1 -sentences

φ,

|φ|A |φ|A  1
Proof By induction on the complexity of φ. For the base case, we note
from definitions that if α is a sentence letter then |α |A  |α|A  1
|α|A .
Also |J |A  |K|A  0 and |K |A  |J|A  1, so each of J and K also has
the noted property.
For the induction step, let φ be cpφ1 ,    , φn q. Then:


|φ|A  | cpφ1,    , φnq |A
 |cpφ1 ,    , φnq|A
 fc p|φ1 |A,    , |φn|Aq
 1
fcp1
|φ1 |A,    , 1
|φn|Aq
 1
fcp|φ1|A ,    , |φn|A q
 1
|cpφ1,    , φnq|A
 1
|φ|A
The main step, from the fourth to the fifth line, uses the induction hypothesis.
This proves the result. 

We note a corollary of the theorem.

Corollary 14 If φ ( ψ then ψ  ( φ.

15
 Proof Assume φ ( ψ. If |ψ  |A  1 then by the Duality Theorem,
|ψ|A  0. If |ψ|A  0 then by the assumption, |φ|A  0. It follows from
the Duality Theorem that |φ |A  1. Since A is any L1 -structure, we have
proved that ψ  ( φ . 

16
Lecture 4
Last time was all about duality. Today, we’ll look at Expressive Adequacy
and the Compactness Theorem. Recall from the first lecture that we can’t
build a contradiction making use of the connective Ø. Thus the set tØu is
not expressively adequate. So which sets of connectives are? First, let’s get
clear on what the question is.

Definition 8 (L1 , L1 , L1 ) φ defines the truth-function f just when

for all structures A, |φpα1 , . . . , αn q|A  f p|α1|A, . . . , |αn|Aq

where α1 , . . . , αn are the sentence letters in φ.

The following definition is for L1 , but is easily adapted to L1 or L1 .

Definition 9 (Expressive Adequacy) A set C of connectives is expres-

sively adequate just when, for every truth-function f , there is a φ P SenpL1 q
with Connpφq „ C that expresses f .

We’re now in position to prove a key theorem about expressive adequacy.

Theorem 15 (L1 , L1 , L1 ) The set t , ^, _u is expressively adequate.

Proof. The proof is for L1 but is easily adapted to L1 or L1 . First, let’s
get 0-place truth-functions out of the way: they’re respectively expressed by
J and K in L1 or L1 , and by e.g. P _ P and P ^ P in L1.
Suppose then that f is an N -place truth-function, with N ¥ 1. If
f pt1 ,    , tN q  0 for all n-tuples of truth-values xt1 ,    , tN y, we can take
φ as P ^ P .
In all other cases, we use f ’s truth table to define a formula φ that is a
disjunction of formulas χj each of which is a conjunction of literals (sentence
letters or their negations). To do so, first define αjk for each j : t1,    , N u Ñ
t0, 1u (i.e. j is a function from the set t1,    , N u to t0, 1u) and 1 ¤ k ¤ N
as follows:
#
if j pk q  1
αjk  Pk
Pk if j pk q  0
Intuitively, j is a row of f ’s truth-table, and αjk ‘corresponds’ to the k th
element of this row, sentence letters corresponding to 1s and negations of
sentence letters to 0s. We define χj to be the conjunction of these αjk , i.e.

17
 ™
χj  αjk
¤¤
1 k N

Next, let T pf q be the set

tj : j is a function from t1,    , N u to t0, 1u s.t. f pj p1q,    , j pN qq 

1u

By our previous assumption, T pf q is non-empty. Putting everything to-

gether, we can define the formula expressing f :
š
φ χj
P pq
j T f

φ is thus a disjunction of conjunctions of sentence letters or their negations

(or in the case in which T pf q is of size 1, just a conjunction of literals). Notice
that SenLettpφq  tP1 ,    , PN u.
We claim that the L1 -formula φ expresses the truth-function f . Suppose
A is an L1 -structure and that jA is the particular function from t1,    , N u
for which jA pk q  |Pk |A for 1 ¤ k ¤ N . A determines jA , so we we need
only focus on the row of the the truth-table that corresponds to jA .
Then:

f p|P1 |A ,    , |Pn |A q  1
õ
jA P T pf q
õ
χjA is a disjunct in φ and |χjA |A 1
õ
|φpP1,    , Pnq|A  1
First biconditional: by the definition of jA and T pf q. Second biconditional:
by the definition of φ in terms of the χj and the properties of conjunctions.
Third biconditional, top to bottom: if χjA is a disjunct in φ and is true in
A then clearly so is φ. Third biconditional, bottom to top: if |φ|A  1 then
some disjunct χj in φ must be true in A; by the properties of conjunctions
|χj |A  1 only if j  jA. 
The proofs of the next three corollaries and proposition are left as exercises.

Corollary 16 The sets t^, u, t_, u and tÑ, u are all expressively ade-
quate.

18
Definition 10 A literal is a sentence letter or its negation. Any disjunction
of conjunctions of literals is in disjunctive normal form and any conjunction
of disjunctions of literals is in conjunctive normal form.

Corollary 17 By Theorem 15, every L1 , L1 and L1 formula is equivalent

to one in disjunctive normal form, and also equivalent to one in conjunctive
normal form.

Proposition 18 In L1 there are exactly 2 expressively adequate binary

connectives.

We now move on to a key theorem, one of the most important theorems in

logic. It’s almost certainly the most important theorem mentioned in this
course, even if it’s not apparent why yet.

Definition 11 Consider a logic L with entailment relation (L . L is compact

just when: for any set of formulas Γ and formula φ, if Γ ( φ then Γfin ( φ
for some finite Γfin „ Γ.

It is easy to show—you should check this—that, for any logic L containing

negation, L is compact just when: if Γ is unsatisfiable then some finite subset
Γfin of Γ is unsatisfiable. Another alternative characterisation of compactness:
if every finite subset of Γ is satisfiable then so is Γ itself. This notion crops
up sufficiently often that it deserves its own definition.

Definition 12 Γ is finitely satisfiable just when all of its finite subsets are
satisfiable.

Theorem 19 L1 , L1 , L1 , L2 and L are all compact logics.

Proof. We’ll prove the theorem for L1 , L2 and L . In fact, our argument
proves a much more general result: any logic with a sound and complete
procedure is compact. Here’s the deceptively simple argument:

(1) Γ(φ Assumption

(2) Γ$φ From (1) by Completeness
(3) Γfin $ φ From (2) by the finiteness of proofs
(4) Γfin ( φ From (3) by Soundness

Here Γfin is some finite subset of Γ. Anything deserving of the name of ‘proof
procedure’ usually satisfies a host of syntactic requirements. Given soundness
and completeness the only such requirement needed for the validity of the

19
inference above is that the step from (2) to (3) be valid, i.e. that proofs draw
only on finitely many premisses. The argument just given therefore applies
to any logic which has a sound and complete proof procedure in this sense.
In particular, it includes L1 , L2 and L , which we know from Introduction
to Logic all satisfy this condition, with $ interpreted as ‘provable in ND’. 

This proof, magnificent though it is, is something of a cheat since we

haven’t yet proved the soundness and completeness of any of the logics we’re
interested in. Actually, we’ll prove the soundness and completeness of L1 in
the second half of this course, and thereby the compactness of L1 . The proof
of soundness and completeness of predicate logics such as L2 or L is more
advanced (though not much more), and will have to await a later course. As
I mentioned in lectures, some logicians take exception to the proof just given,
because they think that proofs of semantic facts such as the Compactness
Theorem need not, and should not, invoke any syntactic notions. In lecture
8, we’ll sketch an entirely semantic proof of the compactness of L1 .
To give you a glimpse of the Compactness Theorem’s importance, I’ll
mention a more advanced and non-examinable result. It shows that L ,
powerful though it is, cannot define the notion ‘there are infinitely many
things’. First, a definitional aside:

Definition 13 An infinite L -structure (or L2 -structure) is one with an

infinite domain; similarly for a finite L -structure (or L2 -structure).

Proposition 20 (Expressive Limitation of L ) There is no L -sentence

that is true in all and only infinite L -structures.

Sketch Proof. Suppose for reductio that φ were a sentence with this
property. Then φ would be true™in all and only finite structures. For each
n ¥ 1, let D¥n be Dx1    Dxn p xi  xj q. Clearly, D¥n is true in an
¤ ¤
1 i j n
L -structure iff the structure has at least n elements in its domain.
Now consider Γ  t φu Y tD¥n : n ¥ 1u.
Our first subclaim is that Γ is unsatisfiable, because φ is satisfiable in
all and only finite structures, and the set tD¥n : n ¥ 1u is satisfiable in all
and only infinite structures.
The second subclaim is that any finite subset of Γ is satisfiable. You
should convince yourself of this by thinking about what a finite subset of
tD¥n : n ¥ 1u looks like.
Putting the two subclaims together shows that Γ contradicts the com-
pactness of L . Thus there is no such formula φ. 

20
Lecture 5
The first half of the course consisted of semantic metatheory, principally that
of L1 . We were concerned with the semantic consequence relation (, and
with proving general results about the logic, of the form say ‘If Γ ( φ then...’,
rather than with proving specific results such as say tP, P Ñ Qu ( Q. In the
second half, we’ll focus more on deductive metatheory. In this lecture, we’ll
think about deductive systems in a more abstract way than you’ve hitherto
been used to. In later lectures the focus will be on the specific proof system
you studied in Introduction to Logic, especially its propositional fragment.
A logic L may be characterised in general terms as consisting of a language
and a consequence relation (L . SenpLq is the set of sentences of the logic,
and the consequence relation (L is almost always taken to relate subsets
of SenpLq to elements of SenpLq; that is, if Γ (L φ then Γ „ SenpLq
and φ P SenpLq. (Formally speaking, then, the relation (L is a subset of
PpSenpLqq  SenpLq; don’t worry if this way of putting things doesn’t make
sense.) The relation (L is not usually taken as primitive but rather defined
using the notion of an L-structure, as in the Introduction to Logic course,:
Γ (L φ just when, for all L-structures A, if A satisfies all the elements of Γ
then A satisfies φ.
A deductive system D for a logic gives rise to a consequence relation $D ,
where Γ $D φ is usually taken to mean: there’s a proof in D of φ from
premises all of which are elements of Γ. It’s tricky to say exactly what we
require of a deductive system and what it means to be a proof. Part of the
job description of a deductive system is that it be syntactic, i.e. concerned
only with symbols and not their meanings; but spelling this out is not as
straightforward as you might think. Proofs are also required to be decidable:
there should be an algorithm (a computer programme if you like) that returns
the answer YES when faced with a string of symbols that is a D-proof and
NO when it isn’t. A string of symbols may not be a D-proof either because
it’s not a sequence of L-formulas, or because it is but the formulas are not
combined together in the right way to make up a D-proof. We’ll set to one
side all these difficult questions about what a proof system is and just assume
that it satisfies three conditions.

Definition 14 (Minimal assumptions on a proof system) If $D is a

deductive consequence relation, we assume that
i. For all Γ „ SenpLq and all φ P SenpLq, if Γ $D φ then there is a finite
Γfin „ Γ such that Γfin $D φ.

ii. For all Γ „ SenpLq and all φ P SenpLq, Γ $D φ if φ P Γ.

21
 iii. For all Γ, ∆ „ SenpLq and all φ P SenpLq, if Γ $D φ then Γ Y ∆ $D φ.

We used the first condition at the end of lecture 4 to prove the compact-
ness theorem. The condition states that proofs can only have finitely many
premises. The second condition expresses the intuitive thought that one can
prove anything one assumes. And the third condition expresses the idea that
provability is monotonic: unlike inductive reasoning, in deductive reasoning
the set of conclusions you can prove can’t shrink by adding more premises.
These three requirements are fairly weak conditions to put on a proof sys-
tem. I certainly wouldn’t want to claim that satisfying them is sufficient for
being a proof system. In fact, the conditions may not even be necessary: per-
haps something deserves to be called a deductive system even whilst failing
one or more of the conditions.
Moving on, let’s consider how (L and $D may be related.

Definition 15 D is strongly sound with respect to (L just when for all

Γ „ SenpLq and all φ P SenpLq, if Γ $D φ then Γ (L φ.
D is strongly complete with respect to (L just when for all Γ „ SenpLq
and all φ P SenpLq, if Γ (L φ then Γ $D φ.
D is weakly sound with respect to (L just when for all φ P SenpLq, if
$D φ then (L φ.
D is weakly complete with respect to (L just when for all φ P SenpLq, if
(L φ then $D φ.
(L is strongly completable just when there is a deductive system D that
is strongly (sound and) complete with respect to (L .
(L is weakly completable just when there is a deductive system D that
is weakly (sound and) complete with respect to (L .

I’ve put the soundness condition in brackets in the definitions of strong and
weak completability because it’s usually assumed that any proof system we
might be interested in is sound. Note that $D φ means that φ is provable in
D from the empty set, so could be alternatively written as H $D φ; similarly
(L φ means that φ is semantically entailed from the empty set and could
be written as H (L φ. It’s immediate, then, that the strong versions of the
theses imply the weak versions. Logicians often omit the adjectives ‘weak’
and ‘strong’, it being clear from context which they mean.
In Introduction to Logic, you saw that the ND system is sound and com-
plete with respect to L -consequence. It will be useful to have labels for the
three systems you encountered there.

Definition 16 Let N Di be the system of rules in The Logic Manual for the
Li -connectives, for i  1, 2, .

22
Thus N D1 consists of all and only the propositional rules, N D2 extends N D1
with the rules for @ and D, and N D in turn extends N D2 with the rules
for . As was mentioned in that course, N Di is sound and complete with
respect to Li -consequence, for i  1, 2 and . Caveat: it does not in general
follow from the fact that logic L with deductive system D is a sublogic of L
with deductive system D that if Γ $D φ for Γ „ SenpLq and φ P SenpLq
then Γ $D φ. When no more L-sequents are proved by D than by D, we
say that the former system is conservative over the latter. In more advanced
proof theory, the notion of conservativeness will turn out to be of central
importance.
Let’s now do some elementary ‘abstract proof theory’. In what follows,
we assume that SenpLq is non-empty and that it is closed under negation,
i.e. if φ P SenpLq then φ P SenpLq. We use Γ &D φ to mean that it’s not
the case that Γ $D φ.

Definition 17 Γ is consistentD (or D-consistent) just when there is a φ P

SenpLq such that Γ &D φ.
Γ is negation-consistentD just when there is no φ P SenpLq such that
Γ $D φ and Γ $D φ.

How are these two notions related? ConsistencyD is more general than
negation-consistencyD , because it does not assume the existence of negation
in the language. It’s also weaker, even granted that assumption. To spell all
this out, let’s see first why negation-consistencyD implies consistencyD . It’s
understood throughout that Γ „ SenpLq and φ P SenpLq.

Lemma 21 If Γ is negation-consistentD then Γ is consistentD .

Proof Suppose Γ is negation-consistentD , i.e. there is no φ such that

Γ $D φ and Γ $D φ. Given any φ P SenpLq (a set we’ve assumed is
non-empty), either Γ &D φ or Γ &D φ. So Γ is consistentD . 

Negation-consistencyD is in fact equivalent to consistencyD plus the fol-

lowing property.

Definition 18 Deductive system D underwrites EFQ (Ex Falso Quodlibet)

from Γ just when: if Γ $D φ and Γ $D φ for some φ then Γ $D ψ for all
ψ.
Deductive system D underwrites EFQ (Ex Falso Quodlibet) just when it
underwrites EFQ from all Γ.

Proposition 22 Γ is negation-consistentD iff Γ is consistentD and D un-

derwrites EFQ from Γ.

23
 Proof Suppose Γ is negation-consistentD . We saw in the previous lemma
that Γ is consistentD . Γ also vacuously satisfies the condition for underwriting
EFQ since there is no φ such that Γ $D φ and Γ $D φ (if the antecedent
of a conditional begins ‘there exists an F such that ...’ then the conditional
is true when there is no such F ).
Suppose conversely that Γ is consistentD and that D underwrites EFQ
from Γ. If Γ were negation-inconsistentD , there would be a φ such that
Γ $D φ and Γ $D φ. Because D underwrites EFQ from Γ, it would follow
that Γ $ ψ for all ψ. Hence Γ would be inconsistentD , a contradiction. 

I leave it as an exercise for you to prove that N D1 underwrites EFQ from

Γ for all Γ „ SenpL1 q. Let’s now have three more properties of a deductive
system, which this time I’ll phrase in terms of all premise sets Γ.

Definition 19 D underwrites Double Negation Introduction (DNI) just when,

for all Γ and φ, if Γ $ φ then Γ $ φ.
D underwrites Double Negation Elimination (DNE) just when, for all Γ and
φ, if Γ $ φ then Γ $ φ.
D underwrites Redundancy (RED) just when, for all Γ and φ, if ΓYtφu $ φ
then Γ $ φ.

Proposition 23 Suppose D underwrites EFQ and RED. Then Γ Y tφu is

consistentD iff Γ &D φ.

Proof. We’ll prove the contrapositives. Suppose Γ $D φ. Then by

the third of the conditions on D (Definition 14), Γ Y tφu $D φ. But also,
by the second of the conditions on D (Definition 14), Γ Y tφu $D φ. Thus
Γ Y tφu is negation-inconsistentD , so it’s inconsistentD , by Proposition 22.
For the other direction, suppose Γ Y tφu is inconsistentD . As it proves
everything, it proves φ in particular: Γ Y tφu $D φ. Since D underwrites
RED, it follows that Γ $D φ. 

Corollary 24 Suppose D underwrites EFQ, RED, DNI and DNE. Then

Γ Y t φu is consistentD iff Γ &D φ.

By the previous proposition, Γ Y t φu is consistentD iff Γ &D φ. By

the fact that D underwrites DNI and DNE, Γ &D φ iff Γ &D φ. Hence
Γ Y t φu is consistentD iff Γ &D φ. 

The global conditions DNI, DNE and RED are, as you may have guessed,
overkill for these results.

24
 You should check that N D1 underwrites DNI, DNE and RED, as well
as EFQ. Going forward, we’ll assume all these facts about N D1 , e.g. we’ll
assume that Γ Ytφu is consistentN D1 iff Γ &N D1 φ, for all Γ „ SenpL1 q and
φ P SenpL1 q.

25
Lecture 6
Let’s continue to think about deductive systems abstractly before focusing
on a concrete proof sytem, that of N D1 (the propositional fragment of the
proof system in The Logic Manual ). As usual, we assume that Γ is a set of
sentences and φ a sentence, and in the following definitions we also assume
that our logic L is closed under negation (if φ is in SenpLq then so is φ).

Definition 20 Γ is semantically complete just when: for all φ, Γ ( φ or

Γ ( φ (or both).
Γ is deductively complete with respect to D (or D-complete) just when:
for all φ, Γ $D φ or Γ $D φ (or both).
Γ is maximally consistentD (or maximally D-consistent) just when Γ is
consistentD (see Definition 17) and if Γ Y tφu is consistentD then φ P Γ.

So when Γ is semantically complete it acts like an L-structure by seman-

tically deciding every claim, and when Γ is deductively complete, it does so
deductively. Finally to say that Γ is maximally consistentD is, informally,
to say that it is full to the brim, almost bursting, as far as consistencyD is
concerned: add an extra sentence to it and it will no longer be consistentD .
For the rest of this lecture, we take D  N D1 . We’ll also assume that
N D1 underwrites the conditions EFQ, RED, DNI and DNE, something I
asked you to prove earlier, and thus that all the results proved in lecture 5
apply to N D1 .

Lemma 25 Suppose Γ „ SenpL1 q is maximally N D1 -consistent. Then Γ is

N D1 -consistent and N D1 -complete.

Proof Assume that Γ is maximally N D1 -consistent. Γ is N D1 -consistent

by the definition of maximal N D1 -consistency.
Suppose Γ were N D1 -incomplete, i.e. Γ &N D1 φ and Γ &N D1 φ for
some φ. Using Corollary 24 applied to N D1 , we deduce from Γ &N D1 φ that
Γ Yt φu is N D1 -consistent. By Γ’s maximal N D1 -consistency, it follow that
φ P Γ.
Similarly, by Proposition 23 applied to N D1 , we deduce from Γ &N D1 φ
that Γ Y tφu is N D1 -consistent. By Γ’s maximal N D1 -consistency, it follows
that φ P Γ.
Since both φ, φ are in Γ, Γ proves them both, and so is negation-
inconsistentN D1 and hence inconsistentN D1 . This contradicts our assumption,
thereby proving that Γ is N D1 -complete. 

26
 We note that the lemma’s converse fails. Consider for example Γ  tα : α
is a sentence letteru. You should check that Γ is N D1 -consistent and N D1 -
complete. Yet Γ is patently not maximally N D1 -consistent; e.g. Γ $N D1
P ^ Q, so Γ Y tP ^ Qu is N D1 -consistent yet P ^ Q R Γ.
The next lemma tell us that for maximally N D1 -consistent sets, mem-
bership coincides with derivability.

Lemma 26 Suppose Γ is maximally N D1 -consistent. Then for any φ, Γ $N D1

φ iff φ P Γ.

Proof If φ P Γ then clearly Γ $N D1 φ.

For the other direction, we invoke Proposition 23, applied to N D1 , which
states that Γ Y tφu is N D1 -consistent iff Γ &N D1 φ. From Γ $N D1 φ
and Γ’s N D1 -consistency (more precisely: its negation-consistencyN D1 ), it
follows that Γ &N D1 φ. So by Proposition 23 applied to N D1 , Γ Y tφu is
N D1 -consistent. So by Γ’s maximal N D1 -consistency, φ P Γ. 

Next, we show that consistency and completeness are sufficient for deriv-
ability to behave just like truth in a structure.

Lemma 27 (Consistency + Completeness Lemma) Suppose Γ is both

N D1 -consistent and N D1 -complete. Then for all φ and ψ,

(i) Γ $N D1 φ iff Γ &N D1 φ

(ii) Γ $N D1 φ ^ ψ iff Γ $N D1 φ and Γ $N D1 ψ

(iii) Γ $N D1 φ _ ψ iff Γ $N D1 φ or Γ $N D1 ψ (or both)

(iv) Γ $N D1 φ Ñ ψ iff Γ &N D1 φ or Γ $N D1 ψ (or both)

(v) Γ $N D1 φ Ø ψ iff (Γ $N D φ and Γ $N D ψ) or (Γ &N D φ and

Γ &N D1 ψ)
1 1 1

Proof I’ll prove the first two parts and leave the rest to you. We assume
thoughout that Γ is N D1 -consistent and N D1 -complete. We’ll also assume
the equivalence of consistencyN D1 and negation-inconsistencyN D1 , previously
proved.
For the left-to-right direction in (i), suppose Γ $N D1 φ . Since Γ is
N D1 -consistent, it follows that Γ & φ.
For the right-to-left-direction in (i), suppose Γ & φ. Then by Γ’s N D1 -
completeness, Γ $ φ.

27
 For the right-to-left direction in (ii), suppose Γ $N D1 φ and Γ $N D1 ψ.
Let Π1 be an N D1 -proof whose set of undischarged assumptions is a subset of
Γ and whose conclusion is φ, and similarly let Π2 be an N D1 -proof whose set
of undischarged assumptions is a subset of Γ and whose conclusion is ψ. We
let Π3 be the proof obtained by putting Π1 and Π2 side by side and applying
the ^-introduction rule to their respective conclusions φ and ψ to obtain
φ ^ ψ. Π3 is thus an N D1 -proof whose set of undischarged assumptions is
a subset of Γ (since the sets of undischarged assumptions of Π1 and Π2 are
subsets of Γ) and whose conclusion is φ ^ ψ. Pictorially:

Π1 Π2
.. ..
. .
φ
φ^ψ
ψ
^intro
For the left-to-right direction in (ii), suppose Γ $N D1 φ ^ ψ. A similar
argument to the one just given shows that a proof of φ ^ ψ from premises that
are all elements of Γ can be extended by a single application of the first ^-
elimination rule to a proof of φ from these same premises, and that this same
proof can be extended by a single application of the other ^-elimination rule
to a proof of ψ from these same premises. Hence Γ $N D1 φ and Γ $N D1 ψ.
Cases (iii), (iv) and (v) are entirely analogous. 

Corollary 28 Suppose Γ is maximally N D1 -consistent. Then for all φ and

ψ,

(i) φ P Γ iff φ R Γ

(ii) φ ^ ψ P Γ iff φ P Γ and ψ P Γ

(iii) φ _ ψ P Γ iff φ P Γ or ψ P Γ (or both)

(iv) φ Ñ ψ P Γ iff φ R Γ or ψ P Γ (or both)

(v) φ Ø ψ P Γ iff (φ P Γ and ψ P Γ) or (φ R Γ and ψ R Γ) (or both)

Proof A consequence of the previous two lemmas. We’ll do cases (i) and
(ii). We assume that Γ is maximally N D1 -consistent throughout.
As for (i): by Lemma 26, φ P Γ iff Γ $N D1 φ. By Lemma 27, Γ $N D1
φ iff Γ &N D1 φ. And by Lemma 26 again, Γ &N D1 φ iff φ R Γ. So φ P Γ
iff φ R Γ.

28
 As for (ii): by Lemma 26, φ ^ ψ P Γ iff Γ $N D1 φ ^ ψ. By Lemma 27,
Γ $N D1 φ ^ ψ iff Γ $ ψ and Γ $ φ. And by Lemma 26 again, Γ $ φ and
Γ $ ψ iff φ P Γ and ψ P Γ . So φ ^ ψ P Γ iff φ P Γ and ψ P Γ.
Cases (iii), (iv) and (v) are entirely analogous. 

29
Lecture 7
Last time, we familiarised ourselves with maximally consistent sets and their
properties, as well as the properties of complete and consistent sets, of which
maximally consistent sets are an example. Today, we’ll prove the soundess
of N D1 with respect to L1 -consequence, and make a start on proving its
completeness. Without further ado, then, let’s prove soundness.

Theorem 29 (Soundness of N D1 ) For all Γ „ SenpL1q, φ P SenpL1q, if

Γ $N D1 φ then Γ ( φ.

Proof We assign a natural number to each N D1 -proof given by the num-

ber of rule applications in the proof. Let’s call this number the size of the
proof. (‘Length’ is more usual when discussing proofs; but natural deduc-
tion proofs are trees rather than linear sequences.) For the avoidance of
misunderstanding, rule applications are tokens not types, so that e.g. the
proof

_ Q _ intro
P
1
P
pP _ Qq _ R _ intro 1

has size 2 since it applies the (first) _-introduction rule twice. We then
prove the result by induction on the size of proofs, taking as our inductive
hypothesis that if Π is an N D1 -proof of φ from Γ of size N then Γ ( φ.
For the induction basis, suppose Π is a proof of size 0, i.e. containing no
rule applications. Then Π must take the form: φ. Since this one-line proof
is a proof from Γ of φ, φ must be an element of Γ. Clearly, then, Γ ( φ as
φ P Γ.
For the inductive step, assume the inductive hypothesis for proofs of size
¤ N . So let Π be a proof of size N 1 of φ from a set of undischarged
assumptions all of which are elements of Γ. Let’s call the last rule used
in this proof ρ (notice that every proof has a last rule). The argument
now proceeds by considering all the possibilities for ρ. This involves a large
number of cases, so I’ll do one here and leave the rest to you.
Suppose ρ is the ^-introduction rule. So Π takes the following form:

Π1 Π2
.. ..
. .
ρ  ^intro
φ1 φ2
φ1 ^ φ2

30
where φ  φ1 ^ φ2 . Let’s call P rempΠi q the set of undischarged assumptions
in subproof Πi of φi , for i  1, 2. Since P rempΠ1 q and P rempΠ2 q are both
subsets of the set of undischarged assumptions in Π, which itself is a subset
of Γ, it follows that P rempΠ1 q, P rempΠ2 q „ Γ. And since Π1 and Π2 are of
size ¤ N , it follows from the inductive hypothesis that

P rempΠ1 q ( φ1 and P rempΠ2 q ( φ2

By the semantic rule for conjunction, we deduce that P rempΠ1 qYP rempΠ2 q (
φ1 ^ φ2 . And since P rempΠ1 q Y P rempΠ2 q „ Γ, we futher deduce

Γ ( φ1 ^ φ2

This proves the inductive step for the case ρ  ^-introduction. I leave the
cases in which ρ is some other rule as exercises for you, which you should
endeavour to do. They are very similar to the above. (A detail that’s un-
likely to trip you up yet that’s nevertheless worth mentioning: for rules that
discharge assumptions you must be careful not to assume that Π’s set of
undischarged assumptions is the union of the set of undischarged assump-
tions of its subproofs.) 

Having dealt with soundness, we now move on to completeness. To prove

completeness, we’ll need two important auxiliary lemmas. The first lemma
states that any consistent set can be extended to a maximally consistent
set; the second says that given any maximally consistent set we can define
an L1 -structure by equating truth in that structure with membership of the
maximally consistent set.

Lemma 30 (First Auxiliary Lemma/Lindenbaum’s Lemma) If Γ is

N D1 -consistent then there’s a maximally N D1 -consistent set Γ such that
Äà .

Proof Assume Γ is N D1 -consistent. Though I won’t do it here, it’s not

hard to show that SenpL1 q is a countably infinite set, which we may enu-
merate (without repetition) as φ1 ,    , φn ,    . Informally, the idea behind
the proof is that we run though these sentences, adding a sentence to Γ if we
can do so whilst preserving consistency; what we end up with must then be
not just consistent, but maximally so.
More formally, we define Γn , for n a natural number, recursively. We set
Γ0  Γ and
#
Γn Y tφn u if Γn Y tφn u is N D1 -consistent
Γn 1 
Γn otherwise

31
It’s immediate from this definition that Γn is N D1 -consistent for all n. We
can prove this by induction: Γ0  Γ is N D1 -consistent by assumption, and
Γn 1 is clearly N D1 -consistent if Γn is.
Let’s now
”
define Γ as the set of sentences that appear in any of the
Γn : Γ  Γn . Clearly, Γn „ Γ for all n, including the case n  0, i.e.
¤
0 n
Γ  Γ0 „ Γ . We first prove that Γ is N D1 -consistent before proving that
it’s maximally N D1 -consistent.
Suppose for reductio, then, that Γ were N D1 -inconsistent, so that Γ $N D1
φ and Γ $N D1 φ. (As ever, we’re taking negation-consistencyN D1 and
consistencyN D1 as equivalent.) Thus, since proofs are finite:

tγ1,    , γmu $N D φ for some tγ1 ,    , γm u „ Γ

tγ1,    , γnu $N D φ for some tγ1 ,    , γn u „ Γ
1

where m and n are natural numbers. The finitely many (¤ m n) elements

of tγ1 ,    , γm u Y tγ1 ,    , γn u have all appeared at some finite stage of the
enumeration of SenpL1 q, so define

k = the maximum i such that φi P tγ1,    , γmu Y tγ1,    , γnu

It follows from this definition that tγ1 ,    , γm u Y tγ1 ,    , γn u „ Γk 1 , so
that Γk 1 $N D φ and Γk 1 $N D
1 φ. This, however, contradicts Γk 1 ’s
1
N D1 -consistency. Hence we may conclude that Γ is N D1 -consistent.
It now remains to show that Γ is maximally N D1 -consistent. So suppose
Γ Y tφu is N D1 -consistent, where φ  φk in our enumeration of SenpL1 q.
Since Γ Y tφk u is N D1 -consistent and Γk „ Γ , it follows that Γk Y tφk u is
N D1 -consistent. (The third property in Definition 14 implies that a subset of
a consistent set is also consistent.) Thus by the definition of Γk 1 , φk P Γk 1
so that φk P Γ since Γk 1 „ Γ . We conclude that Γ is maximally N D1 -
consistent.
To recap: we’ve shown how, given an N D1 -consistent set Γ, we may
define a sequence of consistent extensions of Γ, Γ  Γ0 „ Γ1    „ Γn „    .
Letting Γ be the union of these Γn , so that Γ „ Γ , we then checked that
Γ is not just N D1 -consistent but maximally N D1 -consistent. This proves
the lemma. .

The First Auxiliary Lemma (Lemma 30) is the first staging post on the
way to proving N D1 -completeness. We now state and prove the second.

Lemma 31 (Second Auxiliary Lemma) If Γ is maximally N D1 -consistent

then there is an L1 -structure AΓ such that, for all φ P SenpL1 q, φ P Γ iff
AΓ ( φ.

32
 Proof Assume Γ is maximally N D1 -consistent. We define AΓ so that for
atomic formulas α (i.e. sentence letters),

AΓ ( α iff α P Γ
We must now prove that this applies to all formulas φ, i.e. that φ P Γ iff
AΓ ( φ whatever φ may be. The proof is by induction on the complexity of
φ.
Base case: φ is of complexity 0, i.e. φ is a sentence letter. There is
nothing to prove, since φ P Γ iff AΓ ( φ holds by the definition of AΓ .
For the induction step, suppose φ is of complexity N 1. There are, as
you would expect, five cases to consider.
The first case is φ  ψ, where ψ has complexity N . Since Γ is maximally
N D1 -consistent, then by Corollary 28, ψ P Γ iff ψ R Γ. By the induction
hypothesis, ψ P Γ iff AΓ ( ψ, or equivalently, ψ R Γ iff AΓ * ψ. And
clearly, by the semantic rule for , AΓ * ψ iff AΓ ( ψ. From these three
biconditionals, we deduce that ψ P Γ iff AΓ ( ψ.
The second case is φ  φ1 ^ φ2 , where φ1 and φ2 each has complexity
¤ N . Since Γ is maximally N D1-consistent, then by Corollary 28, φ1 ^ φ2 P Γ
iff φ1 P Γ and φ2 P Γ. By the induction hypothesis, φi P Γ iff AΓ ( φi , for
i  1, 2. And clearly, by the semantic rule for ^, AΓ ( φ1 ^ φ2 iff AΓ ( φ1
and AΓ ( φ2 . From these three biconditionals, we deduce that φ1 ^ φ2 P Γ
iff AΓ ( φ1 ^ φ2 .
The third, fourth and fifth cases, dealing with _, Ñ and Ø are entirely
analogous and are left as exercises. 

We now have all the ingredients for proving N D1 -completeness. But

we’ve run out of time, so we’ll prove it in the next and final lecture.

33
Lecture 8
Last time, we proved the soundness of N D1 with respect to L1 ’s consequence
relation. We also proved that any N D1 -consistent set can be extended to a
maximally consistent set (First Auxiliary Lemma, i.e. Lemma 30) and that
a maximally consistent set corresponds to a unique L1 -structure (Second
Auxiliary Lemma, i.e. Lemma 34). It now remains to put these pieces
together to prove N D1 ’s completeness with respect to L1 -consequence.

Theorem 32 (Completeness of N D1 ) For all Γ „ SenpL1 q and φ P SenpL1 q,

if Γ (L1 φ then Γ $N D1 φ.

Proof We prove the contrapositive: if Γ &N D1 φ then Γ *L1 φ. So

suppose Γ &N D1 φ. By Corollary 24 applied to N D1 , viz. Γ Y t φu is N D1 -
consistent iff Γ &N D1 φ, it follows that Γ Y t φu is N D1 -consistent. So by
the First Auxiliary Lemma, there is a maximal N D1 -consistent set Γ such
that Γ Y t φu „ Γ . And by the Second Auxiliary Lemma, there is an
L1 -structure A such that for all δ P SenpL1 q, A ( δ iff δ P Γ . In particular,
since Γ Y t φu „ Γ , A ( Γ and A ( φ. Hence Γ *L1 φ, which was to be
proved. 

The proof is deceptively simple, because most of the work has been packed
into the First Auxiliary Lemma and the Second Auxiliary Lemma. Moreover,
the Second Auxiliary Lemma itself depended on a host of lemmas about the
properties of maximally N D1 -consistent sets.
The proof we gave at the end of Lecture 4 of the Compactness Theorem
made use of Soundness and Completeness. Since we’ve now proved these for
N D1 , we’ve discharged our obligations as far as L1 is concerned: we’ve proved
that (L1 is compact. But as I mentioned in lectures, it would be better if
possible to give a purely semantic proof of that semantic result than have to
give a deductive argument. In the last part of today’s lecture, we’ll sketch
a strictly semantic proof of L1 ’s compactness. The proof will effectively be
a semantic version of the argument for N D1 ’s completeness. So it will also
serve the purpose of highlighting the proof’s more abstract features.
Recall Definition 12, which stated that a set of sentences is finitely sat-
isfiable just when all its finite subsets are satisfiable. L1 ’s compactness is
equivalent to the statement that if a set of sentences Γ is finitely satisfiable
then it’s satisfiable – this was left as an exercise back in lecture 4, which I
urge you to do. As we’re going to try to mimic the proof of N D1 ’s complete-
ness as much as possible in proving the compactness of L1 , we’ll need the
following definition.

34
Definition 21 Γ is maximally finitely satisfiable just when Γ is finitely sat-
isfiable and if Γ Y tφu is finitely satisfiable then φ P Γ.

Mimicking N D1 ’s completeness proof, we lay down two auxiliary propo-

sitions.

Lemma 33 (First Auxiliary Lemma*) If Γ is finitely satifisable then there’s

a maximal finitely satisfiable set Γ such that Γ „ Γ .

Lemma 34 (Second Auxiliary Lemma*) If Γ is maximally finitely sat-

isfiable then there is an L1 -structure AΓ such that, for all φ P SenpL1 q, φ P Γ
iff AΓ ( φ.

I’ll give abbreviated proofs of each of these lemmas, since their proofs are
so similar to that of their deductive counterparts.

Sketch proof of the First Auxiliary Lemma* We assume Γ is finitely

satisfiable and enumerate the sentences of SenpL1 q as φ1 ,    , φn ,    . Define
Γ0  Γ and
#
Γn Y tφn u if Γn Y tφn u is finitely satisfiable
Γn 1 
Γn otherwise
It’s immediate from the definition”that Γn is finitely satisfiable for all n. Γ
is then defined as before by Γ  Γn . Clearly, Γn „ Γ for all n, including
¤
0 n
the case n  0, i.e. Γ  Γ0 „ Γ .
If Γ were not finitely satisfiable then one of its finite subsets would
be unsatisfiable, and this finite subset must be entirely drawn from some
Γn , which would contradict Γn ’s finite satisfiability. Hence Γ is finitely
satisfiable. And if φk in our enumeration is such that Γ Y tφk u is finitely
satisfiable then Γk 1  Γ Y tφk u must be finitely satisfiable, so that φk P
Γk 1 „ Γ . In other words, Γ is maximally finitely satisfiable. 

Sketch Proof of the Second Auxiliary Lemma* Assume Γ is max-

imally finitely satisfiable. Diverging a little from the proof of the Second
Auxiliary Lemma, we first prove that Γ contains exactly one of φ, φ, for
every φ P SenpL1 q. Clearly, Γ cannot contain both φ and φ since tφ, φu
is finite and unsatisfiable. And if it contains neither, then some finite subset
F1 of Γ is such that that F1 Y tφu is unsatisfiable, and some finite subset F2
of Γ is such that that F2 Y t φu is unsatisfiable. But then F1 Y F2 is a finite
and unsatisfiable subset of Γ (since F1 ( φ and F2 ( φ), contradicting Γ’s
finite satisfiability.

35
 Given the fact that φ P Γ iff φ R Γ, it’s now easy to prove that (i)
φ1 ^ φ2 P Γ iff φ1 P Γ and φ2 P Γ; (ii) φ1 _ φ2 P Γ iff φ1 P Γ or φ2 P Γ (or
both); (iii) φ1 Ñ φ2 P Γ iff φ1 R Γ or φ2 P Γ (or both); and (iv) φ1 Ø φ2 P Γ
iff (φ1 P Γ and φ2 P Γ) or (φ1 R Γ and φ2 R Γ). For example, if φ1 ^ φ2 P Γ and
φ1 R Γ then tφ1 ^ φ2 , φ1 u would be a finite but unsatisfiable subset of Γ. We
conclude that membership in Γ behaves just like truth in an L1 -structure.
Using the above, we define AΓ as in the proof of the Second Auxiliary
Lemma, so that for atomic formulas α (i.e. sentence letters),

AΓ ( α iff α P Γ
It’s now easy to prove that φ P Γ iff AΓ ( φ for all all formulas φ (not just
atomic ones). The proof is once more by induction on the complexity of φ,
using the facts established in the previous paragraph. 

Combining the First Auxiliary Lemma* and the Second Auxiliary Lemma*
yields an alternative proof of the compactness of L1 (an instance of theo-
rem 19).

Alternative proof of Theorem 19 for L1 . As noted, we prove an

equivalent of the compactness theorem of L1 : if Γ is finitely satisfiable then
Γ is satisfiable. So suppose Γ is finitely satisfiable. By the First Auxiliary
Lemma*, there’s a maximal finitely satisfiable Γ such that Γ „ Γ . By the
Second Auxiliary Lemma*, there’s an L1 -structure A such that A ( φ iff
φ P Γ for all φ P SenpL1 q. In particular, A ( Γ, since Γ „ Γ . Hence Γ is
satisfiable. 

You may have been wondering about how our proofs of N D1 -completeness
and L1 ’s compactness would go if the set of sentence letters were not count-
ably infinite. Clearly, if there were only finitely many sentence letters the
proofs would be easier if anything; an alternative proof of compactness could
be given from the observation that there’s a finite subset of sentences such
that every sentence is logically equivalent to one of its members. So the
question is what happens in the case in which the set of sentence letters is
uncountable. In fact, one can give a more abstract version and (once one
has got used to its initally dizzying level of abstraction) easier version of the
arguments for the First Auxiliary Lemma and the First Auxiliary Lemma*.
Here we’ll give the argument for the latter lemma, easily amended to yield
the argument for the former lemma. (The next paragraph is non-examinable,
and uses some terminology about orders that I won’t define but invite you
to look up.)

36
 Suppose Γ is finitely satisfiable. Order by inclusion the set FΓ of finitely-
satisfiable sets of sentences of the language containing Γ. FΓ is non-empty,
since it contains at least Γ. Any chain in FΓ has an upper bound, obtained
by taking the union of the elements in the chain: this union contains Γ as a
subset since all the members of the chain do, and it is finitely satisfiable since
any of its finite subsets must come from some element of the chain, which by
hypothesis is finitely satisfiable. Zorn’s Lemma states precisely that every
partial order with the property that every chain has an upper bound has a
maximal element. Since the conditions of Zorn’s Lemma are satisfied, we
deduce that FΓ has a maximal element; that is, FΓ is a maximal finitely
satisfiable set extending Γ. Note that nowhere did we rely on the fact that
the sentence letters are denumerably many, or on any assumption about the
set of connectives. So this more general argument establishes the analogue
of the First Auxiliary Lemma* for a propositional logic with atom set of any
size.3
Finally, I leave you with a teaser. As we’ve seen, the three logics studied
in Intro Logic are compact. A natural question is whether English itself is
compact. To tackle this question, one must first clarify what compactness
means for a non-formal language such as English. A reasonable definition
might be that if an English argument Γ 6 δ is valid, where Γ is a set of
English sentences and δ is an English sentence, then Γf in 6 δ is valid, where
Γf in is a finite subset of Γ. What validity in English comes to is of course
a vexed issue. But put sceptical doubts aside for a minute and assume that
this notion is in good order. Consider now the following argument:

There is at least one thing.

There are at least two things.
..
.
There are at least n things.
..
.

There are infinitely many things.

This argument appears to be valid; for if there are at least n things for
every finite n then there must be infinitely many things. It also seems that
3
The abstract argument just given invoked Zorn’s Lemma, well known to be equivalent
to the Axiom of Choice in standard set theory. In fact, a slightly weaker principle than
Zorn’s Lemma, the Ultrafilter Lemma, suffices.

37
no finite subset of the premiss set entails the conclusion; that there are at
least n1 ,    nk things for some finite n1 ,    nk does not entail that there are
infinitely many things.
If this is right—and I certainly haven’t proved it—then English conse-
quence is incompact, and none of L1 , L2 and L is capable of capturing it,
since these three logics are all compact. Indeed, as we saw in lecture 4, the
strongest of the three, L , isn’t even capable of formulating the argument’s
conclusion. So which logic captures English validity?

38