The Implications of Paraconsistency

1 Paraconsistency

So many authors recently have speculated on the ad­ vantages of paraconsistent reasoning for the inference engines of intelligent systems managing large bodies of data that one hesitates to enter the lists again in sup­ port of the idea. Prominent among its champions are Belnap, Dunn, Sylvan, DaCosta, Arruda, Priest, Brady, Mortensen, Urbas and Patel-Schneider. 1

Briefly, paraconsistent logic is motivated by distress at the classically valid form of inference

Given an inconsistent database and a classical logic for deducing information from it, inference might go any­ where. Classical logic is supposed to be the maximal sys­ tem, closed as a logic should be under uniform substitu­ tion for its variables, in which inference always preserves truth. The claim that classically valid inference does preserve truth is already suspect on many grounds-for example such inferences as that from A to B-+ A, that from (A-+B)-+A to A and that from A-+(A-+B) to A-+ B can be assessed for truth-preservation only on the basis of some theory as to what the arrow means, and the opponents of classical logic are not about to accept its theories of meaning without argument-but in any case in the canvassed uses of logic truth preservation by itself is not really enough, because the presented infor­ mation need not be truth-like. Especially, it need not be consistent . When we ask what pronouncements should be made by a mechanical reasoner , we typically have in mind a system on whom the World (Everything that is the Case) impinges not directly, for it has no senses or like means of immediate access, but indirectly through what it has been told. And of course what it has been told is not constrained to be verisimilar, especially if it gets its tellings from many independent sources.

1 See the bibliography below. Speculation is all that any of the noted authors has achieved, for despite the rash of papers extolling the virtues of such reasoning the Great Paraconsis­ tent Database Manager has yet to be written.

So even if it is necessary that the World be closed un­ der classical logic, the best reasoning stratregy for beings like ourselves with access only to a corrupt and patchy version of it may well be to shy from the blithe thought that since inconsistency is impossible it does not matter what conclusions we draw from a contradiction. More­ over, even if we have the wisdom to be as gods, either never having inconsistent belief sets or at least never deducing too much silliness from them, the same is not true of our machines. Outside science fiction, automated reasoners lack the noiis to recognise silliness when it hap­ pens. Now some fast and dirty checks for grossly con­ tradictory data can usually be applied, and in current database technology, without really intelligent manage­ ment systems, these suffice to keep things clean. Where the user interface at the input end is something as so­ phisticated and flexible as first order logical notation, however, they certainly will not. Even in fragments of the language for which consistency is decidable the com­ plexity of known decision methods is exponenti~l, so it is not generally feasible to perform a full consistency check for a large body of information. This is especially so where the information tends to change over a short span, so that the life of data in the record may be shorter than the duration of a consistency check. So where there is little control over the format in which data might be entered, and where the roll-over time for data is short, inconsistency must be treated just like any other false­ hood: we do not want it, and if we discover it we shall isolate or eliminate it, but in the meantime we must con­ tinue to reason in the hope that it does not lead to too many wrong predictions. And there's the rub. What we want overwhelmingly is that our automatic reasoner shall give us predictions, strong and useful ones at that, and also that the claims it makes be true. These desider­ ata are in evident conflict. The sufficient strength re­ quirement cannot be compromised very radically, or our system ceases to be useful, so we have no option but to weaken the second desdideratum to an attainable goal such as that nearly all of the predictions be true. Since inconsistency is widespread, undetectable and dangerous to this weaker goal, it seems prudent to base inference on a fault-tolerant logic in which the odd contradiction is' allowed to occur without rendering the data totally corrupt.

2 First Degree Entailments

There are many paraconsistent logical systems on the menu, but for the remainder of this paper we shall con­ centrate on the suggestion, emanating from work of Smi­ ley's dated around 1960, first given its paraconsistent in­ terpretation by Dunn and taken seriously by Belnap, Syl­ van, Priest, Levesque and Patel-Schneider among others, that we liberate truth table reasoning minimally by al­ lowing statements to take not just truth values but sets of truth values. There are evidently four such sets:

That is, a statement can be true, false, both or neither. To assist readability, these four cases will be abbreviated to the single letters T, F, B and N respectively. Now conjunction, disjunction and negation, are easily seen to correspond to functions on these four cases:

The relation of material implication also extends in the obvious way from truth values to sets of truth values: formula A materially implies formula B iff in passing from A to B we neither lose truth nor gain falsehood. These two conditions are of course independent. They induce an implication order on the sets of values thus:

That is, F implies everything; everything implies T ; B and N imply themselves but not each other.

The logic determined by the four-point structure is the system fde of relevant first degree entailments, sometimes called "tautological entailments". As is well known, 2 the alarming inference from an arbitrary con­ tradiction to All Points West is avoided by fde, but as is again well known this avoidance comes at a price. The price is the invalidity of resolution in the form

and of its special case in which C is null, the disjunctive syllogism

Given the disjunctive syllogism, we could argue thus:

After the shock and horror at the thought of rejecting these principles has begun to subside it usually crys­ tallises into two lines of opposition to this kind of para­ consistent logic. The first is that the disjunctive syllo­ gism at least, and maybe resolution also, is just obvi­ ously good reasoning. This is usually said in a special voice reserved for that emphasis needed in philosophy when labouring the obvious in the face of some para­ doxer inclined to point out that arguments in favour of the obvious are a little hard to come by. The second is that without resolution and material detachment reason­ ing would be hamstrung. This second claim deserves to be taken seriously, and is undecided in the present state of the research program. The present paper is motivated by the need to take it seriously, and will address parts of it below, but first it is necessary to say something in response to the former objection.

The simplest response is to challenge the claim of obvi­ ousness head-on. Given the need to reason under incon­ sistent assumptions, it just is not obvious that the dis­ junctive syllogism, for example, is applicable. What un­ derlies the apparent naturalness of that argument form is perhaps some such thought as this: we are given that one of the disjuncts, either A or B, is the case, and we are given that it is not B; so what can it be but A? That is, a disjunction cannot be barely true, for its truth must arise out of that of one of its disjuncts. So where we have assumed enough to make the disjunction true we must have assumed enough to make it appropriate to go on with one disjunct or the other. Now if "'B also holds under our assumptions, it can't be B that underpins the disjunction, on pain of inconsistency, so it must be A. Now the difficulty I find with this thought is not that the implied argument is circular, appealing precisely to the disjunctive syllogism in the metalogic, but that the claim that "it can't be B that underpins A v B" is in the disputed case plain false. Look at the displayed deriva­ tion: the disjunction does come from B, in the grossest and most blatant way, and if this fact causes us to incur the pain of inconsistency then such a pain we must bear.

2 See for example [Belnap, 1977].

There is a slightly deeper point to be made here, about the nature of logical theory. The starting point of all logic is the question of which are the valid (perfect, reli­ able, necessarily rational) forms of argument. What we do in answer to this question is to think up some argu­ ment forms which seem good to us, isolate what we take to be the logical constants involved, formulate rules of in­ ference to govern the behaviour of these and thus arrive at a formal calculus. It is usually after this that we devise a semantic story suited to the inferences we find accept­ able. What we thus produce is a theory sufficing to cat­ alogue the allowable argument forms across the chosen range. We somehow have the impression that our logic is inexorable, so that to question it is not even intelligible. But clearly this inexorability is an illusion. The formal theory goes a long way beyond the intuitive reflections that gave rise to it, so that it applies to many arguments of sorts not considered at all when we so readily assented to the rules. When we accepted modus ponens as part of the meaning of 'if' we may have been unable to imag­ ine what a counter-example could possibly be like; but later we come across the sorites paradox or the semantic antinomies and perhaps our imagination is expanded to encompass such a thing-at least we might well come to the view that the orthodox formulations of modus ponens miss some of the subtleties of the rules which really are or ought to be parts of the meaning of 'if'. Similarly, when we considered resolution or the disjunctive syllogism we may have thought: yes, I reason like that; I would re­ gard it as quite irrational not to. But of course we were not then thinking of reasoning situations that involve taking inconsistent assumptions seriously. When we do confront the problem of the logic of inconsistent theo­ ries, such as large unstructured databases, we find our intuitions less than ideally firm. It is disquieting to have our logic challenged, but the mature philosophy of logic should start from the reflection that logical theories, like any theories, are perpetually open to challenge and that logic can no more be shielded from the hard questions in its domain of application than can any other study.

So much for the assertion of obviousness. The other major objection to paraconsistent logic in the presently canvassed style is that it is too weak to allow recon­ struction of standard reasonings whether their premises be consistent or inconsistent. Weak it is, and its weak­ ness is of two sorts. Firstly it omits many of the classi­ cally valid inferences, such as the noted resolution and disjunctive syllogism, which turn just on the properties of the extensional connectives. It remains to be seen whether the omitted principles really pay their way in classical logic or whether anything they are good for can be achieved paraconsistently by some other means. This paper is not really about weakness in that sense. The second sense in which fde is weak is slightly less obvious but none the less important. It is weak in that it is frag­ mentary. Classically, all the other connectives needed for truth-table reasoning can be defined in terms of negation and either conjunction or disjunction, so once the logic of these connectives is settled there is no more to be said, but this is not the case once we move to fde. Crucially, the operation of material implication is inexpressible in terms of the given extensional connectives. True, we can define a connective in the classical way

but this is no sort of implication in the present context as it fails to satisfy any suitable principle of detachment. So the language stands in need of enrichment in places where that of classical logic does not.

This need for enrichment is even more obvious at the quantificational level. Clearly we can add quantifiers of the usual classical sort, but the effects of so doing are not the usual classical effects. With a model we may associate a nonempty domain of individuals, letting an interpretation assign to each predicate symbol two subsets of the relevant power of the domain: positively, those n-tuples that satisfy the predicate, and negatively those that dissatisfy it. Then an atomic formula

is true for the interpretation iff the tuple consisting of the individuals assigned to terms t 1 ... tn is in the pos­ itive set assigned to F, and false iff that tuple is in the negative set assigned to F. Truth and falsehood for com­ pounds built up with connectives is as before, and the clauses for quantifiers are that Vv A is true iff A is true for all v-variants of the given interpretation and false iff A is false for some v-variant, while the existential 3v A is true iff A is true for some v-variant and false iff A is false for all of them. This is fine as far as it goes but it does not go far enough. Most of the important forms of quantificational argument are not captured by this logic because they are not even expressible. In order to validate

All footballers are bipeds Socrates is a footballer So Socrates is a biped

- an argument commonly supposed to be of an accept­ able form-we need to be able to say not only that every­ thing is bipedal but that all footballers are. That is, we cannot get by for perfectly ordinary reasoning purposes without restricted quantifiers. Now classically there is a familiar trick available to get us out of this problem: we can re-express 'Every footballer is a biped' as 'Ev­ erything is if-a-footballer-then-a-biped'. The latter we can express using the conditional connective and an un­ restricted quantifier. But where no genuine conditional is available there is no such trick available either.

3 Quantifiers

The simple quantificational devices we were all taught in our first year of learning logic are quite inadequate to ex­ press most of the quantifiers used in reasoning. Even in classical logic, where many conceptually distinct notions are collapsed together in order to allow a poor base vo­ cabulary to give rough and ready expression to as wide a range of constructions as possible, we have no means of proving logically valid such simple arguments as

Most logicians are animals

Most logicians are underpaid

Therefore some animals are underpaid and no convenient way of bringing out the ambiguity of a sentence like Most students are smarter than most wombats.

Nor are we given a logical form, identical up to variations in the quantity indicator, for examples like

All Fs are Gs Several Fs are Gs At least six Fs are Gs Hardly any Fs are Gs Finitely many Fs are Gs

We are unlikely to want to investigate the logic of many such quantifiers: in the case of vague quantifiers like 'sev­ eral', 'few' and 'hardly any' it is insufficiently interesting to repay the effort, while for such examples as 'finitely many' and 'most' it is inconvenient because not compact . Nonetheless, we should give thought to their logical form, if only because the general form of the quantifiers we do need to investigate also underlies the others. 3

So the least we need in the way of notation for quan­ tifiers Q is a tripartite structure

where Q is a quantity indicator ('all', 'some', 'most', 'thirteen', etc.), Vis the variable, or in the more general case the several variables, bound by the quantifier, and R is a formula specifying the subset of the domain over which the quantifier ranges. Thus we might represent 'for every student, x' as ('v'xiSx), and write 'All students are more intelligent than some wombats'

That is, for every thing, x, such that x is a student, for some thing, y, such that y is a wombat, x is more intelli­ gent than y. This connective-free notation for restricted quantifiers can easily accomodate the "non-standard" examples above: given a notation M for 'most' we can write

as in 'Most students, even some Logic 1 students, are smarter than most wombats', and distinguish it from

as in 'Most students are smarter than most wombats; that's even true of Willie the Wonder Wombat'.

So we have some notation for quantifiers which does not depend on the connectives in our logic. Now in the cases of the usual quantifiers to which logical theory ap­ plies, the universal and existential ones, we need to ask what inferences a decent logic should validate. In the classical case the answer is easy. For the universal quan­ tifier we want premises r to entail ('v'viA) B if B can be deduced from r and A taken together without cheat­ ing. Cheating here is appealing to free occurrences of v in the premises r. Conversely, we want the above argu­ ment form about Socrates the footballer: for any term t, 4 from ('v'viA) B and A! we can deduce B!. The existen­ tial quantifier is governed by the dual principles. For any t, (3viA) B follows from A~ and B~, and conversely we want the rule of choice: from (3viA) B we can get from whatever follows from A and B, again without cheat­ ing (in this case, no free v in the conclusion or in any side premises appealed to) . Semantically, the universal ('v'viA) B is true iff whatever individual i from the do­ main is assigned to v , A materially implies B while the existential (3viA) B is true iff the assignment of some individual to v satisfies both A and B .

3 See Belnap's paper [Belnap, 1973] on restricted quantifi­ cation for a start on some of the issues. The line taken here is rather different though not completely incompatible.

For the four-valued paraconsistent logic we can keep the classical truth conditions, making ('v'viA) B true for V iff for every v-variant V' of V

where the order is the relation of material implication as specified earlier. For the existential we may take (3viA) B to be true iff for some v-variant V' of V

However, we also need falsehood conditions, and these are less clearly dictated by the need to capture simple syllogistic inferences. The most natural condition under which a universal claim is to be denied is the existence of a counter-example to it . That is ..lis in V(('v'viA) B) iff there is some v-variant V' of V, such that

For the nonexistence of an A that is B the expected condition would surely be that it be false of everything in the domain that it is an A which is B . That is, ..l is in V((3viA) B) iff for every v-variant V'

The upshot of all this is that the existential quantifier, just as classically, is equivalent to the unrestricted form with a connective (conjunction) .

The universal quantifier, however, is something new.

4 Implication: BN4 and beyond

One oddity of classical logic, retained by some authors in order to smooth the definition of 'formula' and the statements of axioms or rules, removed by others in the interests if intelligibility is the vacuous quantifier. A formula such as

is either nonsense or merely a long-winded way of saying

4 Strictly, t must be free for v in A . The same applies to the introduction rule for the existential quantifier. Techni­ cal detail in these matters is not appropriate to this sketch, however.

Now when quantifiers are correctly construed as being of the t,ype to make two predicates into a sentence, vacuous quantification is no longer just circumlocutionary. Con­ sider the existential quantifier first. What does (3xJA) B mean where x does not occur free in A or B? Well it is true iff some x-variant makes both A and B true, and false iff they all make A or B false; but since x does not occur in either formula what holds for one x vari­ ant holds for all of them. In other words, (3xJA) B is exactly equivalent in the vacuous case to A & B. Since no connectives are needed to define the dyadic existential quantifier, any logic with such a quantifier does not need a primitive conjunction: the connective & is definable in terms of the quantifier. This is so classically and remains so in our present paraconsistent logic-as it does, in fact, over a very wide range of first order systems.

The universal quantifier is even more interesting in this regard. Like the existential one it defines a connec­ tive which we can easily calculate to correspond to the following table of values:

Unlike conjunction, this connective is not definable in terms of the usual extensional ones. It is however famil­ iar, at least to the vast and happy readership of [Meyer et al., 1984], as the implication matrix of the logic BN4. Let us fix it as a properly defined connective, then, by the usual trick of letting w be the first variable in the standard enumeration of variables which does not occur in A or B. Then

and it will readily be seen that ('v'vJA) B is equivalent to 'v'v (A-+ B), so the classical move of confining atten­ tion to unrestricted quantifiers is still available except in some vacuous cases. Once again, the connective has been defined using quantification, so not only conjunc­ tion but also implication is redundant in a logic with dyadic quantifiers. Clearly, if we were to go on with the other Aristotelian primitive 'No S is P' we should be able to define negation as well, and thus arrive at a logic in which the only undefined constants are quanti­ fiers. It is amusing to note that Aristotle was so close to an adequate logical vocabulary and theory: only the fact that he tried to manage without variables prevented him from completely anticipating Frege. It is also worth not­ ing that conjunction, implication and negation continue to be definable in the present way over a wide range of logics, from all of the Anderson-Belnap relevant systems to Lukasiewicz many-valued ones. The motivational sig­ nificance of this fact is considerable, since the intuitions regarding universality are much more firmly rooted than those regarding implication, to the extent that while one still hears complaints that the logic of implication is esoteric and contrived, superfluous to requirements or even downright incomprehensible, no-one dare say such things about the logic of 'all'.

BN4 may be a known logic, but it is not the end of the journey. While its underlying four-point lattice is as a De Morgan lattice polynomially free, so that it tells the whole story about first degree entailments, the same is not obviously true of its theory of implication. Such strange theorems as

are brought about not by any offered insight into the nature of reasoning but simply by the lack of different places to put B. These reflect the fact that the impli­ cation of BN 4 is a material implication. While this is not necessarily a bad thing, and indeed BN4 is an inter­ esting logic, there are related systems which are proof­ theoretically more elegant and philosophically more sat­ isfactory. Hence we move on towards a more refined account of implication.

The simplest way to loosen up BN4, giving it a mini­ mally intensional implication operator, is by basing mod­ els not on a single assignment of values but on a partially ordered set of them. This idea is familiar from intuition­ ist logic: the values being epistemic rather than ontic, the "truth" at any stage is partial. The reasoner should therefore take account not only of the values of propo­ sitions as they are given but also of the values as they might be on receipt of more information. For this pur­ pose deletions from the data are not considered, though if we wished to investigate a non-monotonic construal of logic they could be. Possible extensions to the data, being sets, are partially ordered by inclusion, inducing a natural partial order on the associated valuations. There should be a matching inclusion requirement on the do­ mains of individuals as in the intuitionist case. Since there is addition only-never subtraction-we should ex­ pect that for any atomic formula p, if p is true at a val­ uation point it remains true at all greater points, and if it is false it remains false. After all, one can hardly lose a warrant for assertion or denial as more information comes in. The clauses for evaluating compounds should be so formulated that this heredity fact extends from the atomic case to all formulae.

The extensional connectives, defined if we like in terms of the existential quantifier and negation, behave in just the BN4 way at each individual evaluation point. The conditional, however, like the universal quantifier in terms of which it may be presented, is an inference ticket. As such it requires us to look beyond the presently given state of information to its possible extensions. It assures us of the availability of an inference from its antecedent to its consequent, or from the denial of its consequent to that of its antecedent. Hence we must demand appro­ priate closure not only at the valuation point in question but at all its extensions:

Recall that the order ::; is the partial order of material implication on the four sets of values as for BN 4. On the other side of the street, we may take an implication to be deniable just when there is a concrete counter-example to it. That is

In this way we arrive at another known logic, the system BN (without the "4" since it is no longer 4-valued).

For the formal investigation of DN and its many splendid properties I can do no better than to advertise [Slaney et a/., 1989] . 5 What is worth remarking here is that we have come to BN not in order to secure those formal properties but as the result of a chain of philo­ sophical reflections in which they played no part. We were led here specifically by consideration of the need for paraconsistency, then of the expressive weakness of certain paraconsistent logics and finally of the desirabil­ ity, where our notions of truth and falsehood are epis­ temically based, of looking beyond the given state of in­ formation in order to determine implication. What has not been shown is that BN is the One True Logic. The reader seeking demonstrations that this is the only way to go will seek in vain: as an honest logician I can merely indicate that this is a good way to go. Nor, having got this far, can we rest content. At least, given the moti­ vation in terms of automated reasoning, there must be some attempt to apply the ideas empirically; 6 and to in­ vite such empirical testing is to give hostages to fortune . So be it then: having long urged that logic become an empirical science, I am in no position to flinch from such a thought.