<<

. 41
( 107 .)



>>

’ Intro: Suppose the ¬rst invalid step derives the sentence Q ’ R
from an application of ’ Intro to an earlier subproof with assump-
tion Q and conclusion R.

.
.
.
Q
.
.
.
R
.
.
.
Q’R
.
.
.

Again let A1 , . . . , Ak be the assumptions in force at Q ’ R. Note
that the assumptions in force at R are A1 , . . . , Ak and Q. Since step
R is earlier than the ¬rst invalid step, R must be a tautological con-
sequence of A1 , . . . , Ak and Q.
Imagine constructing a joint truth table for the sentences A1 , . . . , Ak ,
Q, Q ’ R, and R. There must be a row h of this table in which
A1, . . . , Ak all come out true, but Q ’ R comes out false, by the
assumption that this step is invalid. Since Q ’ R is false in this
row, Q must be true and R must be false. But this contradicts our
observation that R is a tautological consequence of A1 , . . . , Ak and
Q.

⊥ Elim: Suppose the ¬rst invalid step derives the sentence Q from
⊥. Since this is the ¬rst invalid step, ⊥ must be a tautological con-
sequence of the assumptions in force at ⊥. By the same considera-
tions as in the ¬rst case, the assumptions in force at ⊥ are also in
force at Q. Hence ⊥ is a tautological consequence of the assumptions
A1, . . . , Ak in force at Q. But the only way that this can be so is for
A1, . . . , Ak to be tt-contradictory. In other words, there are no rows
in which all of A1 , . . . , Ak come out true. But then Q is vacuously a
tautological consequence of A1 , . . . , Ak .



Section 8.3
218 / The Logic of Conditionals




Figure 8.1: The soundness theorem for FT tells us that only tautologies are
provable (without premises) in FT .

Remaining rules: We have looked at three of the twelve rules.
The remaining cases are similar to these, and so we leave them as
exercises.

Once a contradiction is demonstrated in all twelve cases, we can
conclude that our original assumption, that it is possible for a proof
of FT to contain an invalid step, must be false. This concludes the
proof of soundness.

Having proven the Soundness Theorem, we can be absolutely certain that
no matter how hard someone tries, no matter how ingenious they are, it will
be impossible for them to produce a proof of ¬Happy(Carl) from the premise
¬(Happy(Carl) § Happy(Scru¬y)). Why? There is no such proof because the
former is not a tautological consequence of the latter.
A corollary is a result which follows with little e¬ort from an earlier theo-
rem. We can state the following corollary, which simply applies the Soundness
Theorem to cases in which there are no premises.
Corollary If T S, that is, if there is a proof of S in FT with no premises,
then S is a tautology.
The import of this corollary is illustrated in Figure 8.1. The corollary tells
us that if a sentence is provable in FT , then it is a tautology. The Soundness



Chapter 8
Soundness and completeness / 219



Theorem assures us that this same relationship holds between provability
in FT , with or without premises, and tautological consequence. Notice the
question marks in Figure 8.1. So far we do not know whether there are any
tautologies (or tautologically valid arguments) that are not provable in FT .
This is the second question we need to address: the issue of completeness.
Before turning to completeness, we should reiterate that our use of the
term soundness in this section has little to do with our earlier use of the term sound deductive system
vs. sound argument
sound to describe valid arguments with true premises. What soundness really
means when applied to a deductive system is that the system only allows you
to prove valid arguments. It would be more appropriate to call it a “validness”
theorem, but that is not what it is traditionally called.

Completeness
Sometimes, in doing an exercise on formal proofs, you may have despaired of
¬nding a proof, even though you could see that the conclusion followed from
the premises. Our second question addresses this concern. Does our deductive completeness of a
deductive system
system allow us to prove everything we should be able to prove?
Of course, this raises the question of what we “should” be able to prove,
which again confronts us with the vagueness of the notion of logical conse-
quence. But given the soundness theorem, we know that the most FT will let
us prove are tautological consequences. So we can state our question more pre-
cisely: Can we convince ourselves that given any premises P1 , . . . , Pn and any
tautological consequence S of these premises, our deductive system FT allows
us to construct a proof of S from P1 , . . . , Pn ? Or could there be tautological
consequences of some set of premises that are just plain out of the reach of the
deductive system FT ? The next theorem assures us that this cannot happen.
Theorem (Completeness of FT ) If a sentence S is a tautological consequence completeness of FT
of P1 , . . . , Pn , then P1 , . . . , Pn T S.
The proof of this result is quite a bit more complicated than the proof of
the Soundness Theorem, and requires material we have not yet introduced.
Consequently, we will not be able to give the proof here, but will prove it in
Chapter 17.
This result is called the Completeness Theorem because it tells us that
the introduction and elimination rules are complete for the logic of the truth-
functional connectives: anything that is a logical consequence simply in virtue
of the meanings of the truth-functional connectives can be proven in FT . As
illustrated in Figure 8.2, it assures us that all tautologies (and tautologically
valid arguments) are provable in FT .
Notice, however, that the Soundness Theorem implies a kind of incompleteness, soundness and
incompleteness


Section 8.3
220 / The Logic of Conditionals




Figure 8.2: Completeness and soundness of FT tells us that all and only tau-
tologies are provable (without premises) in FT .

since it shows that the rules of FT allow us to prove only tautological conse-
quences of our premises. They do not allow us to prove any logical consequence
of the premises that is not a tautological consequence of those premises. For ex-
ample, it shows that there is no way to prove Dodec(c) from Dodec(b) § b = c
in FT , since the former is not a tautological consequence of the latter. To
prove something like this, we will need the identity rules in addition to the
rules for the truth-functional connectives. Similarly, to prove ¬Larger(c, b)
from Larger(b, c), we would need rules having to do with the predicate Larger.
We will return to these issues in Chapter 19.
The Soundness and Completeness Theorems have practical uses that are
uses of soundness and
completeness worth keeping in mind. The Completeness Theorem gives us a method for
showing that an argument has a proof without actually having to ¬nd a
such proof: just show that the conclusion is a tautological consequence of
the premises. For example, it is obvious that A ’ (B ’ A) is a tautology so
by the Completeness Theorem we know it must have a proof. Similarly, the
sentence B § ¬D is a tautological consequence of ¬((A § B) ’ (C ∨ D)) so we
know it must be possible to ¬nd a proof of the former from the latter.
The Soundness Theorem, on the other hand, gives us a method for telling
that an argument does not have a proof in FT : show that the conclusion is not
a tautological consequence of the premises. For example, A ’ (A ’ B) is not
a tautology, so it is impossible to construct a proof of it in FT , no matter how




Chapter 8
Soundness and completeness / 221



hard you try. Similarly, the sentence B § ¬D is a not tautological consequence
of ¬((A ∨ B) ’ (C § D)), so we know there is no proof of this in FT .
Recall our earlier discussion of the Taut Con routine in Fitch. This proce-
dure checks to see whether a sentence is a tautological consequence of whatever
sentences you cite in support. You can use the observations in the preceding
paragraphs, along with Taut Con, to decide whether it is possible to give
a proof using the rules of FT . If Taut Con says a particular sentence is a
tautological consequence of the cited sentences, then you know it is possible
to give a full proof of the sentence, even though you may not see exactly how
the proof goes. On the other hand, if Taut Con says it is a not tautological
consequence of the cited sentences, then there is no point in trying to ¬nd a
proof in FT , for the simple reason that no such proof is possible.

Remember

Given an argument with premises P1 , . . . , Pn and conclusion S:

1. (Completeness of FT ) If S is a tautological consequence of P1 , . . . , Pn ,
then there is a proof of S from premises P1 , . . . , Pn using only the
introduction and elimination rules for ¬, ∨, §, ’, ”, and ⊥.

2. (Soundness of FT ) If S is not a tautological consequence of P1 , . . . , Pn ,
then there is no proof of S from premises P1 , . . . , Pn using only the
rules for ¬, ∨, §, ’, ”, and ⊥.

3. Which of these alternatives holds can be determined with the Taut
Con procedure of Fitch.



Exercises

Decide whether the following two arguments are provable in FT without actually trying to ¬nd proofs.
Do this by constructing a truth table in Boole to assess their tautological validity. Submit the table. Then
explain clearly how you know the argument is or is not provable by applying the Soundness and Com-
pleteness results. Turn in your explanations to your instructor. (The explanations are more important
than the tables, so don™t forget the second part!)

8.39 8.40
A § (B ∨ ¬A ∨ (C § D)) A § (B ∨ ¬A ∨ (C § D)) § ¬(A § D)
‚| ‚|
E § (D ∨ ¬(A § (B ∨ D)))
¬(E § (D ∨ ¬(A § (B ∨ D))))
A§B




Section 8.3
222 / The Logic of Conditionals


In the proof of the Soundness Theorem, we only treated three of the twelve rules of FT . The next three
problems ask you to treat some of the other rules.
8.41 8.42
Give the argument required for the ¬ Give the argument required for the ¬
 
Elim case of the Soundness proof. Your Intro case of the Soundness proof. Your
argument will be very similar to the one argument will be similar to the one we
we gave for ’ Elim. gave for ’ Intro.
8.43 Give the argument required for the ∨
 Elim case of the Soundness proof.


Section 8.4
Valid arguments: some review exercises
There is wisdom in the old saying “Don™t lose sight of the forest for the
trees.” The forest in our case is an understanding of valid arguments. The
trees are the various methods of proofs, formal and informal, and the notions
of counterexample, tautology, and the like. The problems in this section are
intended to remind you of the relationship between the forest and the trees,
as well as to help you review the main ideas discussed so far.
Since you now know that our introduction and elimination rules su¬ce to
prove any tautologically valid argument, you should feel free to use Taut Con
in doing these exercises. In fact, you may use it in your formal proofs from
now on, but with this important proviso: Make sure that you use it only in
cases where the inference step is obvious and would go by without notice in an
informal proof. For example, you may use it to introduce the law of excluded
middle or to apply a DeMorgan equivalence. But you should still use rules like
∨ Elim, ¬ Intro, and ’ Intro when your informal proof would use proof by
cases, proof by contradiction, or conditional proof. Any one-step proofs that
consist of a single application of Taut Con will be counted as wrong!
Before doing these problems, go back and read the material in the Re-
member boxes, paying special attention to the strategy for evaluating argu-
ments on page 171.

Remember

From this point on in the book, you may use Taut Con in formal proofs,
but only to skip simple steps that would go unmentioned in an informal
proof.




Chapter 8
Valid arguments: some review exercises / 223



Exercises

In the following exercises, you are given arguments in the blocks language. Evaluate each argument™s
validity. If it is valid, construct a formal proof to show this. If you need to use Ana Con, use it only to

<<

. 41
( 107 .)



>>