Basic Logic, Lecture 6

Luca Incurvati

[email protected]

Luca Incurvati ([email protected]) Basic Logic 6 1 / 35

 Outline

1 Proving strong soundness for FOL

2 Proving strong completeness for FOL

Luca Incurvati ([email protected]) Basic Logic 6 2 / 35

 Proving strong soundness for FOL

The proof for FOL

We prove that the deductive system for first-order logic we are using
is sound with respect to the corresponding semantics.
We use the same strategy we used in the propositional case.

Theorem 2.1 (Strong soundness of FOL)

Let ϕ be a sentence and Γ be a set of sentences of LFOL . If Γ ` ϕ, then

Γ |= ϕ.

Luca Incurvati ([email protected]) Basic Logic 6 3 / 35

 Proving strong soundness for FOL

The proof for FOL

We’ll first prove a lemma:

Lemma 2.2
Suppose a sentence ϕ of LFOL is like ϕ0 except that for having the
individual constants γ1 , γ2 . . . , γn where ϕ0 has, respectively, the distinct
individual constants δ1 , δ2 , . . . , δn . And suppose, further, that I 0 differs
from I only in that it assigns to δ1 , . . . , δn what I assigns to γ1 , . . . , γn .
Then ϕ is true under I iff ϕ0 is true under I 0 .

Luca Incurvati ([email protected]) Basic Logic 6 4 / 35

 Proving strong soundness for FOL

The proof for FOL

Proof.
By induction on the complexity of ϕ.
(i) ϕ is θn γ1 , γ2 , . . . γn . Let I = hD, Vi and I 0 = hD, V 0 i. θn γ1 , γ2 , . . . γn
is true in I iff hV(γ1 ), V(γ2 ), . . . , V(γn )i ∈ V(θn ) (by the definition of
truth in an interpretation) iff hV 0 (δ1 ), V 0 (δ2 ), . . . , V 0 (δn )i ∈ V 0 (θn ) (by
the supposition of the lemma) iff θn δ1 , δ2 , . . . δn is true in I 0 (by the
definition of truth in an interpretation).
(ii) ϕ is ¬ψ. ¬ψ is true in I iff ψ is not true in I (by the definition of
truth in an interpretation) iff ψ 0 is not true in I 0 (by the induction
hypothesis) iff ¬ψ 0 is true in I 0 (by the definition of truth in an
interpretation).
(iii-v) Similar to (ii).

Luca Incurvati ([email protected]) Basic Logic 6 5 / 35

 Proving strong soundness for FOL

The proof for FOL

Proof.
(vi) ϕ is ∃αψ. ∃αψ is true in I iff ψ[β/α] is true in some β-variant I ? of
I (by the definition of truth in an interpretation) iff ψ[β/α]0 is true in
I ?? , which assigns to individual constants in ψ[β/α]0 what I ? assigns
to individual constants in ψ[β/α] (by the induction hypothesis) iff
∃αψ 0 is true in I 0 (by the definition of truth in an interpretation).
(vii) ϕ is ∀αψ. Similar to (vi).

Luca Incurvati ([email protected]) Basic Logic 6 6 / 35

 Proving strong soundness for FOL

The proof for FOL

Proof.
The proof proceeds by induction on the length of deductions.
Base clause. As in the propositional case.
Inductive clause. Suppose that for any deduction D of ≤ n lines, if D is
a deduction of ϕ from Γ, then Γ |= ϕ. For each inference rule R, we
consider the result of extending a deduction D of n lines to a deduction D0
of n + 1 lines by using R. Assuming the induction hypothesis, we show
that if D0 is a deduction of ϕ from Γ, then Γ |= ϕ.
We have already covered the clauses concerning the propositional rules in
the proof of strong soundness of PL. There remain to prove the clauses
concerning ∀I , ∀E , ∃I and ∃E .

Luca Incurvati ([email protected]) Basic Logic 6 7 / 35

 Proving strong soundness for FOL

The proof for FOL

Proof continued.
(∀E ) Induction hypothesis: For any Γ containing the hypotheses of
D
we have that Γ |= ∀αϕ(α). Let Γ0 contain the hypotheses
∀αϕ(α)
D
of ∀αϕ(α) and let I be an interpretation in which Γ0 is true. This is
ϕ(γ)
an interpretation in which ∀αϕ(α) is true (by the induction
hypothesis). By the definition of truth in an interpretation, this means
that ϕ[β/α] is true in every β-variant of I. Let I ? be the β-variant in
which β is assigned the object assigned to γ in I. Since I ? makes
ϕ[β/α] true, it follows by Lemma 2.2 that I makes ϕ(γ) true.

Luca Incurvati ([email protected]) Basic Logic 6 8 / 35

 Proving strong soundness for FOL

The proof for FOL

Proof continued.
D
(∀I ) Induction hypothesis: For any Γ containing the hypotheses of
ϕ(γ)
D
we have that Γ |= ϕ(γ). Let Γ0 contain the hypotheses of ϕ(γ)
∀αϕ(α)
and let I be an interpretation in which Γ0 is true. We want to show
that ∀αϕ(α) is true in I. That is, we want to show that ϕ[γ/α] is true
in every γ-variant of I. Let I ? be such a γ-variant. Since γ does not
occur in Γ0 , we have that I ? makes Γ0 true. By the induction
hypothesis, we then have that I ? makes ϕ[γ/α] true. But I ? was
chosen arbitrarily. Thus, ∀αϕ(α) is true in I.

Luca Incurvati ([email protected]) Basic Logic 6 9 / 35

 Proving strong soundness for FOL

The proof for FOL

Proof continued.
The remaining cases are left as an exercise.

Luca Incurvati ([email protected]) Basic Logic 6 10 / 35

 Proving strong completeness for FOL

1 Proving strong soundness for FOL

2 Proving strong completeness for FOL

Luca Incurvati ([email protected]) Basic Logic 6 11 / 35

 Proving strong completeness for FOL

Outline of proof of strong completeness

The proof of strong completeness of PL proceeded as follows:

Luca Incurvati ([email protected]) Basic Logic 6 12 / 35

 Proving strong completeness for FOL

Outline of proof of strong completeness

The proof of strong completeness of PL proceeded as follows:

1 We observe that a deductive system is strongly complete iff if a set Φ

of sentences is consistent, then Φ is satisfiable (has a model).
2 We suppose we are given an arbitrary consistent set of sentences Φ
and extend it to a special set Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 12 / 35

 Proving strong completeness for FOL

Outline of proof of strong completeness

The proof of strong completeness of PL proceeded as follows:

1 We observe that a deductive system is strongly complete iff if a set Φ

of sentences is consistent, then Φ is satisfiable (has a model).
2 We suppose we are given an arbitrary consistent set of sentences Φ
and extend it to a special set Φ? .
3 We show that Φ? describes an interpretation I in the sense that every
sentence ϕ is true in I iff ϕ ∈ Φ? . (I is a model of Φ? .)
4 We note that Φ has therefore a model, since Φ ⊆ Φ? and Φ? has a
model.
5 We conclude that if a set Φ of sentences is consistent, then Φ is
satisfiable.

Luca Incurvati ([email protected]) Basic Logic 6 12 / 35

 Proving strong completeness for FOL

Making a start on the proof

We assume we are given the deductive system for first-order logic we

have been working with.
We’d like to extend the proof strategy we used to prove the strong
completeness of the propositional calculus to the first-order case.

Luca Incurvati ([email protected]) Basic Logic 6 13 / 35

 Proving strong completeness for FOL

Making a start on the proof

We assume we are given the deductive system for first-order logic we

have been working with.
We’d like to extend the proof strategy we used to prove the strong
completeness of the propositional calculus to the first-order case.
The outline of the proof is the same. We need to check that the
proofs of the various stages carry over to the current case.
This is certainly the case for stage 1; let us assume for the moment
that it is also the case for stage 2. How about stage 3?

Luca Incurvati ([email protected]) Basic Logic 6 13 / 35

 Proving strong completeness for FOL

The problem of quantifiers

Suppose we are given a maximally consistent set Φ? of sentences of

first-order logic.
We want to specify an interpretation I for first-order logic such that
for any sentence ϕ of first-order logic, ϕ is true in I iff ϕ ∈ Φ? .
We’ll need to define I and prove by induction on the complexity of
sentences that it is indeed the case that for any sentence ϕ of
first-order logic, ϕ is true in I iff ϕ ∈ Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 14 / 35

 Proving strong completeness for FOL

The problem of quantifiers

Suppose we are given a maximally consistent set Φ? of sentences of

first-order logic.
We want to specify an interpretation I for first-order logic such that
for any sentence ϕ of first-order logic, ϕ is true in I iff ϕ ∈ Φ? .
We’ll need to define I and prove by induction on the complexity of
sentences that it is indeed the case that for any sentence ϕ of
first-order logic, ϕ is true in I iff ϕ ∈ Φ? .
Let us assume for the moment that we can define an interpretation
which allows us to prove the base clause and the part of the inductive
clause which deals with increases in complexity by way of connectives;
we still need to deal with increases in complexity due to the
quantifiers.

Luca Incurvati ([email protected]) Basic Logic 6 14 / 35

 Proving strong completeness for FOL

The problem of quantifiers

Let’s focus on existentially quantified sentences, sentences of the form

(∃α)ψ.
Since ψ is an open formula, we cannot hope to establish that ψ ∈ Φ?
iff ∃αψ ∈ Φ? , since Φ? only contains sentences.
But we can hope to establish that some instance of ∃αψ ∈ Φ? iff
∃αψ ∈ Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 15 / 35

 Proving strong completeness for FOL

The problem of quantifiers

This suggests the following series of biconditionals to establish the

relevant part of the inductive clause:

(vii) ϕ is ∃αψ. ∃αψ is true in I iff there is some constant β such that
ψ[β/α] is true in I iff there is some constant β such that ψ[β/α] ∈ Φ?
iff ∃αψ ∈ Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 16 / 35

 Proving strong completeness for FOL

The problem of quantifiers

The problem is that we cannot prove the last biconditional in (vii) –

and in particular its right-to-left direction – in the way in which one
proves (¬), (∧), etc.
For, as things stand, from the fact that ∃αψ ∈ Φ? it does not follow
that there is some constant β such that ψ[β/α] ∈ Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 17 / 35

 Proving strong completeness for FOL

The problem of quantifiers

The problem is that we cannot prove the last biconditional in (vii) –

and in particular its right-to-left direction – in the way in which one
proves (¬), (∧), etc.
For, as things stand, from the fact that ∃αψ ∈ Φ? it does not follow
that there is some constant β such that ψ[β/α] ∈ Φ? .
So we solve the problem by brute force: we construct Φ? so that
besides being a maximally consistent extension of Φ, it is indeed the
case that if ∃αψ belongs to it, then so does some instance of it.
That is to say, we require Φ? to be ω-complete:

Definition 3.1 (ω-completeness)

A set Γ of sentences is ω-complete iff for every sentence ∃αψ, where ψ is
an open formula with α free, if ∃αψ ∈ Γ, then there is some individual
constant β such that ψ[β/α] ∈ Γ
Luca Incurvati ([email protected]) Basic Logic 6 17 / 35
 Proving strong completeness for FOL

Stage 2

Since we want the special set Φ? extending Φ to be ω-complete as

well as maximally consistent, we need to revise the proof of stage 2.
In particular, we need to show how to extend an arbitrarily chosen
consistent set of sentences to a maximally consistent, ω-complete set.

Luca Incurvati ([email protected]) Basic Logic 6 18 / 35

 Proving strong completeness for FOL

Stage 2

Since we want the special set Φ? extending Φ to be ω-complete as

well as maximally consistent, we need to revise the proof of stage 2.
In particular, we need to show how to extend an arbitrarily chosen
consistent set of sentences to a maximally consistent, ω-complete set.
We will define a non-decreasing sequence of sets Γ1 , Γ2 , . . . starting
with Φ and such that its union is maximally consistent and
ω-complete.
As before, we can therefore define the required Φ? to be the union of
this sequence.

Luca Incurvati ([email protected]) Basic Logic 6 18 / 35

 Proving strong completeness for FOL

Stage 2

The idea is to first expand the language with denumerably infinitely

many new individual constants.

Luca Incurvati ([email protected]) Basic Logic 6 19 / 35

 Proving strong completeness for FOL

Stage 2

The idea is to first expand the language with denumerably infinitely

many new individual constants.
Then we start with Φ and go through the list of sentences in the
language: if the result of adding the sentence under consideration is
inconsistent, we move to the next one; otherwise, we do add the
sentence.
If in addition the sentence added is of the form ∃αψ with ψ an open
formula, we also add the result of instantiating the sentence with the
first new individual constant not already used and not appearing in
∃αψ.

Luca Incurvati ([email protected]) Basic Logic 6 19 / 35

 Proving strong completeness for FOL

Stage 2

Lemma 3.2
Every consistent set of sentences Φ can be extended to a maximally
consistent, ω-complete set Φ? .

Proof.
We begin by expanding our language with denumerably infinitely many
new individual constants; it can be proved that this does not make the
given set of sentences Φ inconsistent. (This is left as an exercise.) We
observe that there are denumerably infinitely many sentences of the
expanded language. So we can suppose we have a list ϕ1 , ϕ2 , . . .
Now we define (see next slide):

Luca Incurvati ([email protected]) Basic Logic 6 20 / 35

 Proving strong completeness for FOL

Γ1 = Φ;


 Γn ∪ {ϕn } if Γn ∪ {ϕn } is consistent and

ϕn is not of the form ∃αψ,















Γn ∪ {∃αψ, ψ[β/α]} if Γn ∪ {ϕn } is consistent and



Γn+1 = (with β the first of ϕn is of the form ∃αψ,

the new individual





constants not to appear





in Γn or ∃αψ)










Γn if Γn ∪ {ϕn } is inconsistent;

[
Φ? = Γn .
n≥1
Luca Incurvati ([email protected]) Basic Logic 6 21 / 35
 Proving strong completeness for FOL

Stage 2

Proof continued.
Obviously, Φ? is an extension of Φ; we need to check that it is
maximally consistent and ω-complete.
For each n, Γn is consistent. By induction on n. Base clause: As
before, Γ1 consistent because Γ1 = Φ and Φ is assumed to be
consistent. Inductive clause: The sequence Γ1 , Γ2 , . . . is defined in
such a way that if Γn is consistent, then Γn+1 is consistent too. This
is less obvious than before, since we are now adding ψ[β/α] anytime
we add ∃αψ. The proof that this further addition does not introduce
inconsistencies is left as an exercise.

Luca Incurvati ([email protected]) Basic Logic 6 22 / 35

 Proving strong completeness for FOL

Stage 2

Proof continued.
Φ? is consistent. As in the propositional case.
Φ? is maximally consistent. As in the propositional case.

Luca Incurvati ([email protected]) Basic Logic 6 23 / 35

 Proving strong completeness for FOL

Stage 2

Proof continued.
Φ? is ω-complete. Suppose ∃αψ ∈ Φ? . ∃αψ = ϕm for some m and
hence it must be a member of Γm + 1. But then, by construction,
ψ[β/α] (where β is the first of the new individual constants not to
appear in Γm or ∃αψ). Thus, there is some individual constant such
that ψ[β/α] ∈ Φ? .
Thus, we have shown how to extend an arbitrarily chosen consistent
set of sentences to a maximally consistent, ω-complete set: any
consistent set of sentences Φ has a maximally consistent and
ω-complete extension Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 24 / 35

 Proving strong completeness for FOL

Stage 3

Again, we want to use Φ? to specify an interpretation I in which all

and only the members of Φ? are true.
The interpretation is an interpretation of the new language and hence
of the old language.
Given what interpretations look like in the first-order case, we need to
specify a domain D and a valuation function V.

Luca Incurvati ([email protected]) Basic Logic 6 25 / 35

 Proving strong completeness for FOL

Stage 3

We make do with what we have and build the model using the
individual constants of the expanded language.
First, however, we need some facts about maximally consistent,
ω-complete sets.

Luca Incurvati ([email protected]) Basic Logic 6 26 / 35

 Proving strong completeness for FOL

Stage 3

Lemma 3.3
Let Φ? be a maximally consistent, ω-complete set of sentences. Then:
(¬) ¬ϕ ∈ Φ? iff ϕ 6∈ Φ? .
(∧) ϕ ∧ ψ ∈ Φ? iff ϕ ∈ Φ? and ψ ∈ Φ? .
(∨) ϕ ∨ ψ ∈ Φ? iff ϕ ∈ Φ? or ψ ∈ Φ? .
(→) ϕ → ψ ∈ Φ? iff ¬ϕ ∈ Φ? or ψ ∈ Φ? .
(∃) If ψ is an open formula, then there is some constant β such that
ψ[β/α] ∈ Φ? iff ∃αψ ∈ Φ? .
(∀) If ψ is an open formula, then for every constant β, ψ[β/α] ∈ Φ? iff
∀αψ ∈ Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 27 / 35

 Proving strong completeness for FOL

Stage 3

Proof.
We only need to prove the cases (∃) and (∀), since the other cases have
already been dealt with in the proof of the lemma on maximally consistent
sets which we proved towards the proof of strong completeness of PL.
(∃) (⇒) Suppose that the antecedent is true and, for reductio, that the
consequent is false. Then, by (¬), ¬∃αψ ∈ Φ? . Thus, Φ? ` ¬∃αψ.
But ψ[β/α] ` ∃αψ and so Φ? ` ∃αψ. So Φ? is inconsistent.
Contradiction. (⇐) Immediate from ω-completeness of Φ? .
(∀) Exercise.

Note that it is only in the proofs of (∃) and (∀) that the fact that Φ?
is ω-complete as well as being maximally consistent is used.

Luca Incurvati ([email protected]) Basic Logic 6 28 / 35

 Proving strong completeness for FOL

Stage 3
Theorem 3.4
For every maximally consistent, ω-complete set of sentences Φ? , there is
an interpretation I such that ϕ is true in I iff ϕ ∈ Φ? .

Proof.
We need to define the required interpretation I = hD, Ii. The domain is
the set of individual constants of the expanded language. The valuation V
assigns objects to individual constants and set of n-tuples to n-place
predicates as follows:
1 For each individual constant γ, V(γ) = γ.
2 For each predicate θn of degree n and individual constants
γ1 , γ2 , . . . , γn from D, hγ1 , γ2 , . . . , γn i ∈ V(θn ) iff
θn γ1 , γ2 , . . . γn ∈ Φ? .

Luca Incurvati ([email protected]) Basic Logic 6 29 / 35

 Proving strong completeness for FOL

Stage 3

Proof continued.
Next, we prove by induction on the complexity of sentences, that for every
sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .
(i) ϕ is an atomic sentence. An atomic sentence θn γ1 , γ2 , . . . γn is true in
I iff hV(γ1 ), V(γ2 ), . . . , V(γn )i ∈ V(θn ). But we have specified I so
that hV(γ1 ), V(γ2 ), . . . , V(γn )i ∈ V(θn ) iff θn γ1 , γ2 , . . . γn ∈ Φ? .
Thus, θn γ1 , γ2 , . . . γn is true in I iff θn γ1 , γ2 , . . . γn ∈ Φ? . This
establishes that ϕ is true in I iff ϕ ∈ Φ? for ϕ an atomic sentence.

Luca Incurvati ([email protected]) Basic Logic 6 30 / 35

 Proving strong completeness for FOL

Stage 3

Proof continued.
The proof of the cases for the connectives carry over from the
propositional case. We need to examine the two cases for the quantifiers.
(vi) ϕ is ∃αψ and ψ. ∃αψ is true in I iff there is some constant β such
that ψ[β/α] is true in I (by the definition of truth in an interpretation)
iff ψ[β/α] ∈ Φ? (by the induction hypothesis) iff ∃αψ ∈ Φ? (by (∃)).
(vii) ϕ is ∀αψ. ∀αψ is true in I iff for every constant β such that ψ[β/α] is
true in I (by the definition of truth in an interpretation) iff
ψ[β/α] ∈ Φ? (by the induction hypothesis) iff ∀αψ ∈ Φ? (by (∀)).

Luca Incurvati ([email protected]) Basic Logic 6 31 / 35

 Proving strong completeness for FOL

Stage 3

So we have proved that for every sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .

This establishes that there is an interpretation I in which all the
members of Φ? are true (and hence, by definition, that Φ? is
satisfiable).

Luca Incurvati ([email protected]) Basic Logic 6 32 / 35

 Proving strong completeness for FOL

Concluding the proof: stages 4 and 5

We have shown that there is an interpretation I which makes all

members of Φ? true: Φ? has a model.
Since Φ ⊆ Φ? , this interpretation also makes every member of Φ true:
Φ too has a model.

Luca Incurvati ([email protected]) Basic Logic 6 33 / 35

 Proving strong completeness for FOL

Concluding the proof: stages 4 and 5

We have shown that there is an interpretation I which makes all

members of Φ? true: Φ? has a model.
Since Φ ⊆ Φ? , this interpretation also makes every member of Φ true:
Φ too has a model.
But the consistent set of sentences Φ was chosen arbitrarily.
Thus, we can conclude that if Φ is a consistent set of sentences, then
Φ is satisfiable.
And this is equivalent to strong completeness.

Luca Incurvati ([email protected]) Basic Logic 6 33 / 35

 Proving strong completeness for FOL

Concluding the proof: stages 4 and 5

So we have established:

Theorem 3.5 (Strong completeness of FOL)

Let ϕ be a sentence and Γ be a set of sentences of LFOL . If Γ |= ϕ then

Γ ` ϕ.

Luca Incurvati ([email protected]) Basic Logic 6 34 / 35

 Proving strong completeness for FOL

References

The proof of strong soundness:

D.van Dalen, Logic and Structure.
W.Newton-Smith, Logic, Ch. 4, §4 (propositional calculus).
B.Mates, Elementary Logic, Ch. 8 §2 (first-order logic).
The proof of strong completeness:
D.van Dalen, Logic and Structure.
W.Hodges, ‘Classical Logic I: First-order logic’, pp. 27–28. In L.Goble,
Philosophical Logic, pp. 9–32 (sketch of the proof for first-order logic
with identity).

Luca Incurvati ([email protected]) Basic Logic 6 35 / 35