2.3.4. Reaching decisions

We know that, if a system of derivations has individual rules that are both sound and safe and is, as a whole, sufficient, it will never give us an incorrect answer regarding the validity of an argument. But it is entirely possible that such a system will give us no answer at all. If we ever run out of rules to apply, we will have an answer. For, if this happens without all gaps closing, we will have at least one open gap that has reached a dead-end. However, without some guarantee that we will eventually run out of rules, we have no guarantee that we will eventually have an answer. And such a guarantee is not trivial because, once we get to the last two chapters, we will be working in a system some of whose derivations do go on forever.

We will say that a system is decisive when we always reach a point where either all gaps are closed or there is a dead-end open gap. It should be clear that our system so far is decisive. The rules Ext and Cnj replace conjunctions among the resources and goals of gap by simpler sentences and must therefore eventually eliminate all conjunctions. At that point the only rules that might apply are QED, ENV, and EFQ, but each of these closes a gap and there will be only a limited number of gaps to close. We will say that a rule is direct when it is like one of these—that is, when it closes a gap, replaces a resource by one or more simpler resources, or replaces a goal by one or more simpler goals. All of the rules we have considered so far are direct in this sense.

More broadly, we will say that a rule is progressive when it, in some sense, brings us closer to a point where no more rules can be applied. The qualification in some sense is important because many different measures of distance could be used. We might measure distance from the end first of all by the complexity of sentences appearing as resources and goals and, once all resources and goals are of minimum complexity, by the number of open gaps. If we use a measure of this sort, direct rules are progressive.

But there are many measures of this sort, differing in the way they measure complexity; and this is not the only way measuring distance from the end. We would always want direct rules to count as progressive on any measure of distance we use, but some measures will count more rules as progressive. For example, a rule that introduces a sentence more complex than any previously in the derivation will not be direct, but it might still count as progressive if there is a limit on the number of such sentences that can be introduced in this way. For then a rule that introduces such a sentence brings us closer to the end by reducing the number that can be introduced later. We do need to require that, whatever measure of distance is used, there is some minimum reduction of distance that makes a rule progressive; for we must insure that we cannot squeeze in an infinite series of steps by, for example, going halfway to the end, halfway from the point to the end, and so on.

As we saw in the case of our current rules, a system whose rules are each progressive will be decisive because, if applying a rule always reduces our distance from the end (by at least some minimum amount), then we will eventually reach a point where the distance has been reduced so much that no more rules can be applied. At that point, any gap that is left open will have reached a dead end, and the derivation will have provided an answer about the validity of the original system. We have seen also that if a such system is sufficient and conservative, the answer provided is always the correct one. A system that always eventually provides an answer and a correct one, can be said to provide a decision procedure for validity.

Our current system is sufficient, conservative, and decisive, and it therefore provides a decision procedure. But we can cut up its properties in another way. Because it is decisive as well as accurate in its answers, we can say both of the following about any derivation:

The if parts of these together say that the system is accurate, and we have seen that they follow from its conservativeness (along with sufficiency in the case of the second statement). The only if parts follow from the if parts given decisiveness.

For example, we can show the only if part of the first by showing that, if gaps do not eventually all close, the derivation’s ultimate argument is not valid. Suppose that the gaps never all close; we want to show that in this case the ultimate argument is not valid. Since the system is decisive, if gaps never all close, we must eventually reach a dead-end open gap; and the if part of the second statement then tells us that the argument is invalid. In a similar way, if we suppose that we never eventually reach a dead-end gap, we can show that the argument is not invalid, and this establishes the only if part of the second statement.

Moreover, the only if parts of the two claims above together imply decisiveness since, because an argument will always be either valid or invalid, they imply that eventually either all gaps close or we reach a dead-end gap.

But these two claims, like the properties of soundness and safety, are not of equal importance. The first is closely tied to the use of derivations to establish validity while the second is similarly related to their use to find counterexamples and establish invalidity. The first is of special interest also because it can be established in some cases where decisiveness fails, and we will take it as the key property of our system of derivations in chapters 7 and 8 when we must abandon decisiveness.

It is standard to give different names to the two parts of the first statement:

When we can be sure that the if-statement is true, we say that the system is sound. We have seen that a system will be sound if all its rules are at least minimally sound. When we can be sure that the only-if-statement is true, we say the system is complete because such a system provides a proof for each valid argument.

We can show that a system is complete if we know that its rules are safe and the system as whole is sufficient and we know also that any derivation whose ultimate argument is valid eventually reaches an end. The latter is not full decisiveness since it applies only to derivations whose ultimate argument is valid, this sort of partial decisiveness is something we will be able to establish for the indecisive systems of chapters 7 and 8. Consequently, all systems that we will study in the course are both sound and complete.