Paradoxes of Implication Challenging the Paradigm

Among the sequents provable in orthodox logic, of which our system is one presentation, are some which must strike the reflective observer as somewhat bizarre or even downright wrong. They include such specimens as

p   ⊢   q IMP p
NOTp   ⊢   p IMP q
p, NOTp   ⊢   q
p   ⊢   (q IMP r) OR (r IMP s)

Try filling in actual sentences for the sentence letters in these. In the last one, for instance:

You can fool some of the people all of the time.
Therefore
Either if you're gullible then you'll believe classical logical theory or if you'll believe classical logical theory then you'll believe anything.

This can hardly be claimed as an argument which commends itself intuitively as valid. For one thing, even if the conclusion were true, the premise would be irrelevant to it. Yet the sequent is valid on a truth table test, and it has a proof in our natural deduction system. There is thus an apparent mismatch between the orthodox logical properties of the formal connectives and the intuitive data about validity which the system was designed to capture. The rather startling sequents above, and others like them, are known as the paradoxes of material implication.

Following Alan Anderson and Nuel Belnap in their seminal work on this subject ABE, we might define a paradox of implication loosely as a provable sequent whose proof requires attributing a conclusion to assumptions on which it does not depend—i.e. which were not used in deriving it. The utility of such a definition depends, of course, on what sense can be given to the notion of "use". Let us look at a proof (efq). The overall strategy here, to assume NOTq and derive a contradiction from it, is surely quite reasonable, but the way it is done at line 4 is surely not what we had in mind when setting up the rules. In no real sense did the contradiction come "from NOTq". Someone may attempt to fix matters by reconstructing the proof thus:

Now assumption 3 certainly occurs in the derivation of line 6, so it is "used" in some sense, but it is intuitively clear, if a little difficult to express formally, that it is not used in a way which makes the contradiction depend on it as the motivating talk behind RAA requires. The whole shuffle, in fact, is performed precisely in order to blame the Bad Thing on an innocent bystander. To say that p came "from NOTq" under other assumptions is stretching the ordinary sense of 'from'. This is what Anderson and Belnap wanted logic to avoid.

I believe it is possible to make the definition of paradoxes of implication precise in terms of the proof system. A sequent in which no connectives other than implication and negation occur is a paradox iff (a) it is provable, and (b) every proof of it involves either a detour through some other connective or else vacuous discharge. To extend this characterisation to the whole of the language takes a little more work which must wait until we have explored the problem some more.

It is sometimes said that the paradoxes are not really problematic because they just show that the English locution if. . . then does not mean the same as 'IMP', and perhaps that the same goes for the other formal connectives and their counterparts. This response will not do, however. The rules of the formal system are all motivated by appeal to the inferential properties of the corresponding connectives in natural languages such as English. Since those rules lead to the paradoxes, either the paradoxes are acceptable or the rationale for the rules is not. The proof in efq uses only the rules A, RAA and NOTNOTE. The vacuous discharge can be emulated using ANDI and ANDE. Anyone who thinks that the paradoxes are not valid for the English words 'and' and 'not' must say which of the rules just mentioned is invalid for the English connectives and why. So the paradoxes are genuinely paradoxical: they are quite counter-intuitive, yet they follow from convincing principles culled from our understanding of ordinary reasoning. To resolve the situation, something has to give.

The standard, classical response is to accept the paradoxes as valid principles governing natural connectives and learn to love them. Support for this option comes from proofs like the ones above which derive the disputed principles from ones which it is relatively hard to reject. The most famous of these "independent proofs" was known at least to medieval logicians and maybe even to ancient ones, and was re-discovered in the 20th century by C.I. Lewis. It is a derivation of q from p AND NOTp and goes like this:

This argument has nothing to do with material implication as such, for there are no arrows in it. It does have to do with properties of disjunction and negation, however. The move taking us from line 1 to lines 2 and 4 is just ANDE, while that taking us from 2 to 3 is ORI. The remaining move, from 3 and 4 to 5 is sometimes called the disjunctive syllogism:

Either p is true or q is true
But p is false
So it must be q that is true

This form of argument by elimination is common in practice and very persuasive at first glance. Imagine doing a sudoku puzzle without it! Such arguments have persuaded most philosophical logicians that the classical position is embraceable. It is often presented as the lesser of two outrages; it is claimed that to abandon ANDI or IMPI or something would be much more counter-intuitive than the paradoxes themselves. How cogent such a thought is depends both on intuitions about relative outrageousness and on how great a revision really is forced by avoiding the paradoxes. The latter question is a delicate one and not yet entirely resolved.

Clearly the first problem facing a proponent of the classical response is to explain why, if the paradoxes are valid forms of argument, so many competent thinkers find them startling or unacceptable. A common approach to this problem is to focus on the distinction between appropriateness and truth. There are many reasons why an utterance may be inappropriate even if true. Most of these are of no great interest to logical theory—the utterance may be impolite, for instance, or too long and complicated to be intelligible in the context—but some are very important. Most significantly, it is in general misleading, and therefore inappropriate, to tell part of the truth in a long story if you are in a position to tell all of it more briefly. Thus if you ask me how the logic students fared in their exam and I reply, knowing full well that they all passed, 'Well, they didn't all fail!' then what I say is perfectly true, because passing entails not failing, but by saying it I mislead you into thinking that some of them failed, or that I don't know whether some of them passed or not. So we have two statements, P (Everyone passed) and F (Everyone failed) such that P entails NOTF although the utterance of P is appropriate while that of NOTF is not. Hence appropriateness is not necessarily preserved under the operation of logically valid inference. In the same way, it is held, if I know that q then I mislead by asserting p IMP q, for I convey the false impression that I don't know whether q, or indeed whether p, but only some connection between them. This does not mean that q does not entail p IMP q, for logic is concerned only with preservation of truth, not with any other impressions our premises and conclusions may happen to convey. Reflection on the difference between appropriateness and truth has helped to convince many thinkers that the classical response to the paradoxes faces no serious difficulties. Before we all accept this, however, we should stop and think some more. The weakness of the inappropriateness argument is shown by the fact that we feel much less resistance to the passage from q to p OR q than to that from q to p IMP q, although the two are equally subject to considerations of appropriateness and on the classical view should stand or fall together.

The alternative to giving up our intuitions of paradoxicality is of course to reject the paradoxes as invalid and to amend our formal logic so as to avoid being able to prove them. This option has generally been less popular than the classical one, though it has been gaining ground over the last half century or so since respectable alternative logics became available. The easiest way into one such alternative system is to pay more attention than we have done so far to the ways in which assumptions can be combined with each other in the premise parts of sequents. In the proof in Kproof the assumptions are put together by ANDI and then put asunder by IMPI. Neither ANDI nor IMPI is in itself objectionable; the problem arises from combining them. However, we want to hold onto the idea of logic as the kind of formal system described and motivated at the start of these notes, so it remains important that valid inference should be transitive, meaning that there can be no objection to chaining inference steps together. Hence we are led to blame the paradoxes on equivocation: what we need is a distinction between the way in which ANDI combines assumptions and the way in which IMPI and RAA require them to have been combined. Such a distinction is aimed at matching different ways in which premises can be used to generate a conclusion.

To produce a paradox-free logic in place of the orthodox one we help ourselves to two notations for combining assumption numbers on the left of proof lines. The exact symbols we use for these are unimportant, but it has become customary to use a comma for one such operation and a semicolon for the other. The intention is that X,Y is the result of merely collecting up the set of assumptions from X and Y and "pooling" the information they carry, while X;Y is the result of "applying" X to Y (or perhaps X and Y to each other) so that they interact to produce conclusions. Then conjunction is tied to ',' as in the usual presentation, whereas implication is tied to ';'. So we now have the rules ANDI, IMPE and IMPI exactly as before but with attention paid to the difference between commas and semicolons. Rrules shows how. The rules RAA (or the primitive negation rules going through BAD, if we still remember those) and ORE also have to be modified slightly. For technical details of the logic, see the system specification at the end of these notes. Roughly speaking, the comma behaves in the amended logic just as it does in classical logic, satisfying weakening and contraction principles, but the semicolon is more restricted. Crucially, there is a rule stating that a comma may replace a semicolon anywhere on the left of a sequent, but the converse is not the case. The sample proofs may be studied to gain a feeling for the logic.

Notice how the derivation in Kproof is blocked. It goes through as far as line (4):

p, q   ⊢   q

but to apply IMPI in its new form we should require the stronger

p; q   ⊢   q

which is not forthcoming. It would require a way of involving q in the derivation of p more deeply than just by its coming in and going out again as happens in this proof. This can be shown (though I shall not show it here) to be impossible in the amended system, however ingeniously we complicate the derivation. The other paradoxes are likewise, and for roughly similar reasons, underivable.

It is a matter of unsettled philosophical debate whether such a restricted system, a so-called relevant logic, captures the intuitions better or worse than the standard brand. It is also an open question whether the restricted logic is adequate to allow important theories, in mathematics for example, to be reconstructed formally. The possibilities in this area are intricate and fascinating but quite difficult, both technically and conceptually.

The two formal systems, orthodox and relevant, give different and conflicting accounts of valid reasoning. How can we decide which of the two accounts is the better? Appeal to intuitions about what entails what may take us part of the way but is unlikely to answer many of the more delicate and complicated questions, and will leave our choice of formal logic seriously indeterminate. It is sometimes urged that classical logic should be preferred on the grounds of its simplicity, elegance and convenience. Well, relevant logic is elegant too, while simplicity and convenience are relative to the purposes to which formal systems are put, so these considerations are not clearly decisive.

Part of the interest of formal logic is that it both generates philosophical problems such as that of choice between rival accounts and provides the tools with which these problems may be tackled. We may start by thinking that we have a pretty good intuitive grasp of which forms of argument are the valid ones, but we find that in a curious way our intuitions tend to change—at least they get sharpened—as a result of the formal investigations stemming from them. This section has raised some hard philosophical problems. Well, I make no apology for that: philosophical logic is a difficult subject. At least it may serve to defeat the suggestion one still sometimes hears that "elementary" logic is somehow just trivial.

Notes and further reading

Relevant logic as presented here stems from the work of Alan Anderson and Nuel Belnap in the 1960s, though there were earlier formulations of the pure implication fragmant of R by Alonzo Church and of the implication-negation fragment by Orlov as long ago as 1928. The Stanford Encyclopedia article by Ed Mares Mares gives an overview and notes a number of related logical systems. The natural deduction formulation of R given here is more recent SlaneyGL.

The standard refernce works are the two volumes by Anderson and Belnap and their followers ABE ABE2 and the handbook chapter DunnRestall by Mike Dunn and Greg Restall. The two volumes of Relevant Logics and their Rivals by Richard Routley, Ross Brady and others RLR RLR2 are also useful. For the standard semantic account of R and similar systems, see the encyclopedia article by Mares, Restall's book on substructural logics Restall and the more recent paper by nearly everybody Ternary explaining how to read the semantic theory.