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