Let's review what soundness comes to. Suppose I hand you a correct derivation. You want to be assured that the corresponding argument is valid. In other words, you want to be sure that an interpretation which makes all the premises true also makes the final conclusion true. Soundness guarantees that this will always be so. With symbols, what we want to prove is
T5 (Soundness for sentence logic derivations): For any set of sentences, Z, and any sentence, X, if ZkX, then Z~X.
with 'k' meaning derivability in the system of sentence logic derivations.
The recipe is simple, and you have already mastered the ingredients: We take the fact that the rules for derivations are truth preserving. That is, if a rule is applied to a sentence or sentences (input sentences) which are true in I, then the sentence or sentences which the rule licenses you to draw (output sentences) are likewise true in I. We can get soundness for derivations by applying mathematical induction to this truth preserving character of the rules.
Consider an arbitrary derivation and any interpretation, I, which makes all of the derivation's premises true. We get the derivation's first conclusion by applying a truth preserving rule to premises true in I. So this first 192 Soundness and Completeness for Sentence Logic Derivations 13-2. Soundness for Derivations: Fonnol Detaik 193 conclusion will be true in I. Now we have all the premises and the first conclusion true in I. Next we apply a truth preserving rule to sentences taken from the premises andor this first conclusion, all true in I. So the second conclusion will also be true in I. This continues, showing each conclusion down the derivation to be true in I, including the last.
Mathematical induction makes this pattern of argument precise, telling us that if all the initial premises are true in I (as we assume because we are interested only in such I), then all the conclusions of the derivation will likewise be true in I.
This sketch correctly gives you the idea of the soundness proof, but it does not yet deal with the complication arising from rules which appeal to subderivations. Let's call a rule the inputs to which are all sentences a Sentence Rub and a rule the inputs to which include a subderivation a Subderivation Rub. My foregoing sketch would be almost all we need to say if all rules were sentence rules. However, we still need to consider how subderivation rules figure in the argument.
What does it mean to say that the subderivation rule, >I, is truth preserving? Suppose we are working in the outermost derivation, and have, as part of this derivation, a subderivation which starts with assumption X and concludes with Y. To say that >I is truth preserving is to say that if all the premises of the outer derivation are true in I, then X>Y is also true in I. Let's show that >I is truth preserving in this sense.
We have two cases to consider. First, suppose that X is false in I. Then X>Y is true in I simply because the antecedent of X>Y is false in I. Second, suppose that X is true in I. But now we can argue as we did generally for outer derivations. We have an interpretation I in which X is true. All prior conclusions of the outer derivation have already been shown to be true in I, so that any sentence reiterated into the subderivation will also be true in I. So by repeatedly applying the truth preserving character of the rules, we see that Y, the final conclusion of the subderivation, must be true in I also. Altogether, we have shown that, in this case, Y as well as X are true in I. But then X>Y is true in I, which is what we want to show.
This is roughly the way things go, but I hope you haven't bought this little argument without some suspicion. It appeals to the truth preserving character of the rules as applied in the subderivation. But these rules include 31, the truth preserving character of which we were in the middle of proving! So isn't the argument circular?
The problem is that the subderivation might have a sub-subderivation to which >I will be applied within the subderivation. We can't run this argument for the subderivation until we have run it for the sub-subderivation. This suggests how we might deal with our problem. We hope we can descend to the deepest level of subderivation, run the argument without appealing to >I, and then work our way back out.
Things are sufficiently entangled to make it hard to see for sure if this strategy is going to work. Here is where mathematical induction becomes indispensable. In chapter 11 all my applications of induction were trivial. You may have been wondering why we bother to raise induction to the status of a principle and make such a fuss about it. You will see in the next section that, applied with a little ingenuity, induction will work to straighten out this otherwise very obscure part of the soundness argument.
EXERCISES 13-1. Using my discussion of the >I rule as a model, explain what is meant by the rule -I being truth preserving and argue informally that -I is truth preserving in the sense you explain. 13-2. Explain why, in proving soundness, we only have to deal with the primitive rules. That is, show that if we have demonstrated that all derivations which use only primitive rules are sound, then any derivation which uses any derived rules will be sound also.
Paul Teller (UC Davis). The Primer was published in 1989 by Prentice Hall, since acquired by Pearson Education. Pearson Education has allowed the Primer to go out of print and returned the copyright to Professor Teller who is happy to make it available without charge for instructional and educational use.