Basic Logic, Lecture 5
Luca Incurvati
[Link]@[Link]
Luca Incurvati ([Link]@[Link]) Basic Logic 5 1 / 33
Outline
1 Proving strong soundness
2 Proving strong soundness for PL
3 Proving strong completeness of PL
Luca Incurvati ([Link]@[Link]) Basic Logic 5 2 / 33
Proving strong soundness
The strategy
Recall that a deductive system is strongly sound iff if Γ ` ϕ, then
Γ |= ϕ.
By definition, Γ ` ϕ iff there is a deduction of ϕ from Γ.
Thus, it suffices to show that for each deduction D of ϕ from Γ,
Γ |= ϕ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 3 / 33
Proving strong soundness
The strategy
Recall that a deductive system is strongly sound iff if Γ ` ϕ, then
Γ |= ϕ.
By definition, Γ ` ϕ iff there is a deduction of ϕ from Γ.
Thus, it suffices to show that for each deduction D of ϕ from Γ,
Γ |= ϕ.
We do this by showing in particular that, for any deduction D,
whatever the length of D, Γ |= ϕ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 3 / 33
Proving strong soundness
The strategy
Deductions can have any finite length.
We associate each natural number n with the set of deductions which
have n or less lines.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 4 / 33
Proving strong soundness
The strategy
Deductions can have any finite length.
We associate each natural number n with the set of deductions which
have n or less lines.
Then we prove strong soundness by induction on the length of
deductions.
We need to prove a base clause and an inductive clause.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 4 / 33
Proving strong soundness
The general shape of the proof
Base clause
For any deduction D of one line, if D is a deduction of ϕ from Γ, then
Γ |= ϕ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 5 / 33
Proving strong soundness
The general shape of the proof
Base clause
For any deduction D of one line, if D is a deduction of ϕ from Γ, then
Γ |= ϕ.
Inductive clause
Induction hypothesis: for any deduction D of ≤ n lines, if D is a deduction
of ϕ from Γ, then Γ |= ϕ. Then, for any deduction D of n + 1 lines, if D is
a deduction of ϕ from Γ, Γ |= ϕ.
So we are using induction on the property for any deduction D of
lines, if D is a deduction of ϕ from Γ, then Γ |= ϕ.
The details of how we establish the base clause and the inductive
clause will depend on the type/specificities of the deductive system
being used.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 5 / 33
Proving strong soundness
The proof for a natural deduction system
In a natural deduction system we proceed as follows.
Base clause
If D has one line and is a deduction of ϕ from Γ, then of course ϕ must be
in Γ. But then Γ |= ϕ, since obviously ϕ |= ϕ.
Inductive clause
This is proved by considering, for each inference rule R, 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 check that if D0 is a
deduction of ϕ from Γ, then Γ |= ϕ. Since given a deduction of n lines, a
deduction of n + 1 lines can only be obtained by an application of one of
the inference rules, this establishes the inductive clause.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 6 / 33
Proving strong soundness for PL
1 Proving strong soundness
2 Proving strong soundness for PL
3 Proving strong completeness of PL
Luca Incurvati ([Link]@[Link]) Basic Logic 5 7 / 33
Proving strong soundness for PL
The proof for PL
Using this strategy, we can prove that the deductive systems for
propositional logic, first-order logic and first-order logic with identity
we have described are sound for the corresponding semantics.
We begin with propositional logic:
Theorem (Strong soundness of PL)
Let ϕ be a sentence and Γ be a set of sentences of LPL . If Γ ` ϕ, then
Γ |= ϕ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 8 / 33
Proving strong soundness for PL
The proof for PL
Proof.
We prove this by induction on the length of deductions.
Base clause. For any deduction D of one line, if D is a deduction of ϕ
from Γ, then Γ |= ϕ.
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 Γ |= ϕ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 9 / 33
Proving strong soundness for PL
The proof for PL
Proof continued.
D
(∧I ) Induction hypothesis: For any Γ containing the hypotheses of and
ψ
0
for any Γ0 containing the hypotheses of D we have Γ |= ψ and
χ
D D0
0 00
Γ |= χ. Let Γ contain the hypotheses of ψ χ . If we let Γ
ψ∧χ
and Γ0 be exactly the sets of the hypotheses of, respectively, D and
D0 , we see that Γ00 ⊇ Γ ∪ Γ0 . Let I be an interpretation in which Γ00 is
true. This is an interpretation in which ψ is true and χ is true (by the
induction hypothesis). But then, I is also an interpretation in which
ψ ∧ χ is true (by the definition of truth in an interpretation).
Luca Incurvati ([Link]@[Link]) Basic Logic 5 10 / 33
Proving strong soundness for PL
The proof for PL
Proof continued.
D
(∧E ) Induction hypothesis: For any Γ containing the hypotheses of
ψ∧χ
D
we have that Γ |= ψ ∧ χ. Let Γ0 contain the hypotheses of ψ ∧ χ
ψ
(the case in which the conclusion is χ rather than ψ is similar) and let
I be an interpretation in which Γ0 is true. This is an interpretation in
which ψ ∧ χ is true (by the induction hypothesis). But then, I is also
an interpretation in which ψ is true (by the definition of truth in an
interpretation).
Luca Incurvati ([Link]@[Link]) Basic Logic 5 11 / 33
Proving strong soundness for PL
The proof for PL
Proof continued.
D
(∨I ) Induction hypothesis: For any Γ containing the hypotheses of we
ψ
D
have that Γ |= ψ. Now let Γ0 contain the hypotheses of ψ and
ψ∨χ
let I be an interpretation in which Γ0 is true. This is an interpretation
in which ψ is true (by the induction hypothesis). But then, I is also
an interpretation in which ψ ∨ χ is true (by the definition of truth in
an interpretation). The case for the other rule of ∨-introduction is
similar.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 12 / 33
Proving strong soundness for PL
The proof for PL
Proof continued.
ψ
(→ I ) Induction hypothesis: For any Γ containing the hypotheses of D we
χ
[ψ]
have Γ |= χ. Now let Γ0 contain the hypotheses of D . Then
χ
ψ→χ
ψ
Γ0 ∪ {ψ} contains all hypotheses of D . Now let I be an
χ
interpretation in which Γ0 and ψ are true. By the induction
hypothesis, this is an interpretation in which χ is true. But then, by
the definition of truth in an interpretation, I is also an interpretation
in which ψ → χ is true.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 13 / 33
Proving strong soundness for PL
The proof for PL
Proof continued.
D
(⊥) Induction hypothesis: For any Γ containing the hypotheses of we
⊥
have Γ |=⊥. Since there is no interpretation which makes ⊥ true, this
means that there is no interpretation which makes all members of Γ
D
true. Now let Γ0 contain the hypotheses of ⊥ and suppose that
ψ
Γ0 6|= ψ. This means that there is an interpretation which makes all
members of Γ0 true and ψ false. But since Γ0 contains the hypothesis
D
D
of ⊥ , a fortiori it contains the hypotheses of But there can be
⊥
ψ
no interpretation which makes all members of Γ0 true. Contradiction.
So Γ0 |= ψ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 14 / 33
Proving strong soundness for PL
The proof for PL
Proof continued.
The remaining cases are left as an exercise.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 15 / 33
Proving strong completeness of PL
1 Proving strong soundness
2 Proving strong soundness for PL
3 Proving strong completeness of PL
Luca Incurvati ([Link]@[Link]) Basic Logic 5 16 / 33
Proving strong completeness of PL
Outline of proof
Assume that we are given a standard, textbook deductive system for
the propositional calculus. Then, the proof of strong completeness
proceeds as follows:
Luca Incurvati ([Link]@[Link]) Basic Logic 5 17 / 33
Proving strong completeness of PL
Outline of proof
Assume that we are given a standard, textbook deductive system for
the propositional calculus. Then, the proof of strong completeness
proceeds 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 ([Link]@[Link]) Basic Logic 5 17 / 33
Proving strong completeness of PL
Outline of proof
Assume that we are given a standard, textbook deductive system for
the propositional calculus. Then, the proof of strong completeness
proceeds 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 ([Link]@[Link]) Basic Logic 5 17 / 33
Proving strong completeness of PL
Stage 2
Definition
A set Φ? of sentences is an extension of a set Φ iff Φ ⊆ Φ? .
Definition
A set Γ of sentences is maximally consistent iff
Γ is consistent;
for any sentence ϕ, if ϕ 6∈ Γ, then Γ ∪ {ϕ} is inconsistent.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 18 / 33
Proving strong completeness of PL
Stage 2
We want to show that every consistent set of sentences Φ can be
extended to a maximally consistent set Φ? .
We do so by defining a non-decreasing sequence of sets Γ1 , Γ2 , . . .
starting with Φ and such that its union is maximally consistent.
Thus, we can define the required Φ? to be the union of this sequence.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 19 / 33
Proving strong completeness of PL
Stage 2
Lemma (Lindenbaum)
Every consistent set of sentences Φ can be extended to a maximally
consistent set Φ? .
Proof.
We begin by observing that there are denumerably infinitely many
sentences. So we can suppose we have a list ϕ1 , ϕ2 , . . .
Luca Incurvati ([Link]@[Link]) Basic Logic 5 20 / 33
Proving strong completeness of PL
Stage 2
Proof continued.
Now we define:
Γ1 = Φ;
(
Γn ∪ {ϕn } if Γn ∪ {ϕn } is consistent,
Γn+1 =
Γn otherwise;
[
Φ? = Γn .
n≥1
Luca Incurvati ([Link]@[Link]) Basic Logic 5 21 / 33
Proving strong completeness of PL
Stage 2
Proof continued.
Now we define:
Γ1 = Φ;
(
Γn ∪ {ϕn } if Γn ∪ {ϕn } is consistent,
Γn+1 =
Γn otherwise;
[
Φ? = Γn .
n≥1
The idea is to start with Φ and go through the list of sentences in the
language: if the result of adding the sentence under consideration to
what we’ve got thus far is consistent, then we do add the sentence;
otherwise, we simply move to the next one.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 21 / 33
Proving strong completeness of PL
Stage 2
Proof continued.
Obviously, Φ? is an extension of Φ; we need to check that it is
maximally consistent.
For each n, Γn is consistent By induction on n. (Γ1 = Φ is assumed
to be consistent, and the sequence Γ1 , Γ2 , . . . is defined in such a way
that if Γn is consistent, then Γn+1 is consistent too.)
Luca Incurvati ([Link]@[Link]) Basic Logic 5 22 / 33
Proving strong completeness of PL
Stage 2
Proof continued.
Φ? is consistent Suppose by reductio that Φ? is inconsistent. Then,
there is a ψ such that Φ? ` ψ and Φ? ` ¬ψ. Since deductions are
finite, there must be a finite ∆ ⊆ Φ? such that ∆ ` ψ and ∆ ` ¬ψ.
Now there must be some sentence ϕm in the list ϕ1 , ϕ2 , . . . such that
each member of ∆ occurs before ϕm . So ∆ ⊆ Γm . Since ∆ is
inconsistent, so is Γm . But this contradicts what we have shown
above, namely that Γn is consistent for each n.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 23 / 33
Proving strong completeness of PL
Stage 2
Proof continued.
Φ? is maximally consistent Take an arbitrary sentence ψ and suppose
that ψ 6∈ Φ? . ψ must appear somewhere in the list ϕ1 , ϕ2 , . . ., i.e.
ψ = ϕm for some m. Thus, ψ 6∈ Φ? because it is left out when Γm + 1
is constructed. But the only reason why this can be the case is that
Γm ∪ {ψ} is inconsistent. But since Γm ⊆ Φ? by definition of Φ? ,
Φ? ∪ {ψ} is inconsistent too.
Thus, we have shown how to extend an arbitrarily chosen consistent
set of sentences to a maximally consistent set: any consistent set of
sentences Φ has a maximally consistent extension Φ? .
Luca Incurvati ([Link]@[Link]) Basic Logic 5 24 / 33
Proving strong completeness of PL
Stage 3
In the case of the propositional calculus, we specify an interpretation
by specifying an assignment of truth-values to the atomic sentences.
This assignment determines the truth-value of every complex
sentence.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 25 / 33
Proving strong completeness of PL
Stage 3
In the case of the propositional calculus, we specify an interpretation
by specifying an assignment of truth-values to the atomic sentences.
This assignment determines the truth-value of every complex
sentence.
We want to use Φ? to specify an interpretation I in which all and
only the members of Φ? are true.
Hence, we specify the an assignment of truth-values to the atomic
sentences by defining an interpretation I for which this the case by
definition as far as atomic sentences are concerned.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 25 / 33
Proving strong completeness of PL
Stage 3
Next, we prove that for every sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .
This will establish that there is an interpretation I in which all the
members of Φ? are true (and hence, by definition, that Φ? is
satisfiable).
Luca Incurvati ([Link]@[Link]) Basic Logic 5 26 / 33
Proving strong completeness of PL
Stage 3
Next, we prove that for every sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .
This will establish that there is an interpretation I in which all the
members of Φ? are true (and hence, by definition, that Φ? is
satisfiable).
In the proof, we’ll make use of some facts about maximally consistent
sets.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 26 / 33
Proving strong completeness of PL
Stage 3
Lemma
Let Φ? be a maximally consistent set of sentences. Then:
(¬) ¬ϕ ∈ Φ? iff ϕ 6∈ Φ? .
(∧) ϕ ∧ ψ ∈ Φ? iff ϕ ∈ Φ? and ψ ∈ Φ? .
(∨) ϕ ∨ ψ ∈ Φ? iff ϕ ∈ Φ? or ψ ∈ Φ? .
(→) ϕ → ψ ∈ Φ? iff ¬ϕ ∈ Φ? or ψ ∈ Φ? .
Luca Incurvati ([Link]@[Link]) Basic Logic 5 27 / 33
Proving strong completeness of PL
Stage 3
Proof.
The proofs employ facts about the deducibility relation, which need to be
proved for the particular deductive system used, and can be proved for the
deductive system we are using.
(¬) Suppose for reductio that both ϕ and ¬ϕ are members of Φ? . Then
Φ? ` ϕ and Φ? ` ¬ϕ. So Φ? is inconsistent. But Φ? is maximally
consistent. So ϕ and ¬ϕ are not both members of Φ? . Suppose, on
the other hand, that neither ϕ nor ¬ϕ is a member of Φ? . Then
Φ? ∪ {ϕ} and Φ? ∪ {¬ϕ} are both inconsistent, since Φ? is maximally
consistent. It follows that Φ? ` ϕ and Φ? ` ¬ϕ. Hence, Φ? is
inconsistent, contradicting the fact that it is maximally consistent.
Thus, at least one of ϕ and ¬ϕ is a member of Φ? . We can conclude
that exactly one of ϕ and ¬ϕ is a member of Φ? .
Luca Incurvati ([Link]@[Link]) Basic Logic 5 28 / 33
Proving strong completeness of PL
Stage 3
Proof continued.
(∧) Exercise.
(∨) Exercise.
(→) Exercise.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 29 / 33
Proving strong completeness of PL
Stage 3
Theorem
For every maximally consistent set of sentences Φ? , there is an
interpretation I such that ϕ is true in I iff ϕ ∈ Φ? .
Proof.
We begin by defining I as follows:
(Atomic). If ϕ is an atomic sentence, then ϕ is true in I iff ϕ ∈ Φ? .
Next, we prove by induction on the complexity of sentences that for every
sentence ϕ, ϕ is true in I iff ϕ ∈ Φ? .
Luca Incurvati ([Link]@[Link]) Basic Logic 5 30 / 33
Proving strong completeness of PL
Stage 3
Proof continued.
(i) If ϕ is an atomic sentence, the claim holds by definition. That is,
(Atomic) tells us that for atomic sentences, ϕ is true in I iff ϕ ∈ Φ? .
(ii) ϕ is ¬ψ. ¬ψ is true in I iff ψ is not true in I (by truth-table) iff
ψ 6∈ Φ? (by the induction hypothesis) iff ¬ψ ∈ Φ? (by (¬)).
(iii) ϕ is ψ ∧ χ. ψ ∧ χ is true in I iff ψ is true in I and χ is true in I (by
truth-table) iff ψ ∈ Φ? and χ ∈ Φ? (by the induction hypothesis) iff
ψ ∧ χ ∈ Φ? (by (∧)).
(iv) ϕ is ψ ∨ χ. Similar to (iii).
(v) ϕ is ψ → χ. Similar to (iii).
Luca Incurvati ([Link]@[Link]) Basic Logic 5 31 / 33
Proving strong completeness of PL
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 ([Link]@[Link]) Basic Logic 5 32 / 33
Proving strong completeness of PL
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 ([Link]@[Link]) Basic Logic 5 32 / 33
Proving strong completeness of PL
Concluding the proof: stages 4 and 5
So we have established:
Theorem (Strong completeness of PL)
Let ϕ be a sentence and Γ be a set of sentences of LPL . If Γ |= ϕ then
Γ ` ϕ.
Luca Incurvati ([Link]@[Link]) Basic Logic 5 33 / 33
