A contradiction that stays where it is

Classical logic has a property that sounds like a strength and behaves like a fragility. If a set of premises contains a contradiction — some statement and its negation — then every statement whatever follows from it. The rule has a Latin name, ex falso quodlibet, “from a falsehood, anything”, and a modern one, explosion. It means a single inconsistency anywhere in a body of assumptions makes the whole body useless, since it then proves both every claim and its opposite.

The derivation is two lines, and in this form it is usually credited to C. I. Lewis and C. H. Langford in 1932. From $p$, infer $p \vee q$, since a disjunction is true when either side is. From $p \vee q$ and $\neg p$, infer $q$, since if one side of a disjunction is false the other must be true. So from $p$ and $\neg p$ together, $q$ follows, for any $q$. Each step is a rule nobody would want to give up, and the conclusion is one that a person reasoning from inconsistent information — a database with a typo, a legal code with two clauses that conflict, the assumptions of a scientist whose theories disagree — plainly does not draw.

A paraconsistent logic is one in which a contradiction does not explode. The simplest, and the one this essay draws, is Graham Priest’s logic of paradox of 1979, anticipated by Florencio Asenjo in 1966. It is classical logic with one extra truth value, and the most surprising thing about it is how little it changes.

Three values, two of which hold #

The tables are the classical ones with a middle value inserted. Negation turns true into false and false into true, and leaves the middle value $b$ where it is: the negation of something both true and false is itself both. Conjunction takes the lesser value and disjunction the greater, in the order false, both, true. These are exactly the tables of the three-valued logic Stephen Kleene introduced in 1938, and of Łukasiewicz’s logic restricted to three values for these connectives; the tables are not where the novelty is.

The novelty is in which values count as holding. Priest’s choice is that a statement holds when it is at least partly true: when its value is $t$ or $b$. A conclusion follows from premises when every valuation that makes all the premises hold makes the conclusion hold. With that definition, the valuation $p = b$, $q = f$ makes $p$ hold, makes $\neg p$ hold — since $\neg b = b$ — and makes $q$ fail. So $q$ does not follow from $p$ and $\neg p$. The explosion has a countermodel, and it is the simplest one possible: a single statement both true and false, and another merely false.

The value $b$ is called a glut — a statement with too many truth values rather than too few. A logic in which statements can have no truth value has gaps, and the two kinds of logic turn out to be mirror images, as the next figure shows.

Which rules survive #

The census below takes eight familiar rules of classical reasoning and tests each against every valuation, in three logics at once.

In the logic of paradox, five of the eight rules survive untouched: double negation, simplifying a conjunction, weakening to a disjunction, De Morgan’s law, and excluded middle as a law. Three fail, and they fail together for one reason. Explosion fails, as already shown. Modus ponens for the material conditional fails: from $p$ and $\neg p \vee q$ it does not follow that $q$, with the same countermodel, because $\neg p \vee q$ holds when $\neg p$ holds. And the disjunctive syllogism — from $p \vee q$ and $\neg q$, infer $p$ — fails when $q$ is both and $p$ is false: the disjunction holds because of $q$, the negation of $q$ holds because $q$ is a glut, and $p$ is simply false.

Those three are exactly the rules that eliminate a possibility by appeal to a negation: they reason “this is false, so it must be the other one”. When a statement can be both true and false, its negation holding no longer rules it out, and every rule that relies on ruling it out has a countermodel. Lewis’s two-line derivation of explosion used disjunctive syllogism in its second line, and that is the line the logic of paradox refuses.

Kleene’s gap logic uses the same tables and lets only $t$ hold. It keeps every elimination rule — if $\neg q$ holds, $q$ is genuinely false — and loses excluded middle, since $p \vee \neg p$ is merely $b$ when $p$ is $b$, and $b$ does not hold. The two logics divide the classical rules between them. A logic of gluts gives up the inferences that pass through a contradiction; a logic of gaps gives up the laws that say a statement has a truth value. That is the same split as between the constructive logic, which loses excluded middle, and its duals, and it is why paraconsistent logics are sometimes called the mirror image of constructive ones.

Same laws, fewer consequences #

The most surprising fact about the logic of paradox is how much of classical logic it keeps. The figure below checks it on every formula up to a size.

Among the 56 functions that small formulas in $p$ and $q$ define, nine are classical tautologies — true under every classical valuation — and the same nine always hold in the logic of paradox. That is not a coincidence of small formulas. It is a theorem: the tautologies of the logic of paradox are exactly the classical tautologies. The reason is that the connectives respect information: changing a variable’s value from $b$ to $t$ or to $f$ only removes information, and can only move the formula’s value from $b$ to $t$ or $f$, never between $t$ and $f$. So if the formula were $f$ at some three-valued valuation, it would be $f$ at the classical valuation obtained by resolving every $b$ — which a tautology never is. The logic proves every classical law.

What it loses is inferences. Of the 1,313 one-premise inferences between those formulas that are classically valid, 1,147 survive — 87.4 per cent — and the 166 that fail are all of the eliminating kind. So the logic of paradox has exactly the same laws as classical logic and fewer consequences: it believes everything classical logic believes, and is more careful about what follows from what. The gap logic is the opposite extreme: with only $t$ holding, no formula of this kind is always true — at the valuation where every variable is $b$, every formula is $b$ — so it has no tautologies at all, while keeping the inferences.

A body of information with one mistake in it #

The difference between the logics is easiest to see on a small body of information with a contradiction in it — the situation that motivates the whole subject.

The premises say that $p$ holds, that $p$ fails, that $q$ holds, and that either $q$ fails or $r$ holds. Classically, the first two cannot both be true, no valuation satisfies all four, and so every conclusion follows vacuously — including $s$ and $\neg s$, about which the premises say nothing at all. A reasoner using classical logic on this information can be made to conclude anything, and the reasoner’s answers carry no information.

The logic of paradox answers differently, and the pattern of its answers is the point. Everything the premises say directly still follows: $p$, $\neg p$, $q$. The question about $s$ is open, as it should be, and $s \vee \neg s$ follows, as a law. But $r$ does not follow, although classically it is the conclusion of a perfectly ordinary disjunctive syllogism from $q$ and $\neg q \vee r$. The reason is that the logic does not know which statements are the contradictory ones. It knows $p$ is a glut, but it cannot exclude that $q$ is one too, and if $q$ is both true and false then $\neg q \vee r$ holds because of $\neg q$, and $r$ need not hold.

That is the honest cost of the approach. A paraconsistent logic quarantines a contradiction by refusing every inference that could carry it elsewhere, and since it cannot tell in advance where contradictions are, it refuses some inferences that pass through perfectly consistent parts of the information. Practical systems for reasoning with inconsistent data usually combine a paraconsistent core with an extra assumption — that statements are consistent unless shown otherwise — which restores the disjunctive syllogism wherever no contradiction has been found. The logic of paradox is the core, and what it gives up is exactly what such an assumption has to buy back.

Why classical logic accepted explosion #

Explosion was not an accident of classical logic; it was accepted with open eyes, and it is worth seeing why. The two-line derivation uses only addition, from $p$ to $p \vee q$, and the disjunctive syllogism, and both are valid in the two-valued semantics. In a world where every statement is exactly one of true and false, a contradiction can never be true, so a rule that says what follows from one is never tested, and saying that everything follows is the simplest rule consistent with the tables. The truth tables that make classical logic so easy to check — one connective is enough to build them all — are the same tables that make explosion unavoidable.

The cost appears only when contradictions are taken seriously as things one might hold. A mathematical theory that proved a contradiction would, classically, prove everything, and that is why consistency is the property Gödel’s second incompleteness theorem is about: a classical theory that is inconsistent is useless, and no sufficiently strong theory can prove its own consistency. Paraconsistent logic asks whether that uselessness is a fact about inconsistency or a fact about classical logic, and the logic of paradox answers that, at least for propositions, it is the latter.

Four values, for a computer told conflicting things #

Nuel Belnap proposed in 1977 that the right logic for a computer receiving information from several sources has four values, not three, because a source can be silent as well as contradicted.

Each value is a pair of yes-or-no answers: was the computer told that the statement is true, and was it told that the statement is false? Both no is $n$, a gap; both yes is $b$, a glut. The four values carry two orders. Ordered by truth — how far towards true — $f$ is lowest and $t$ highest, with $b$ and $n$ side by side between them. Ordered by information — how much the computer has been told — $n$ is lowest, $b$ highest, with $t$ and $f$ between. The connectives follow the truth order, so a conjunction of $b$ and $n$ is $f$, the lowest value below both, and their disjunction is $t$.

This four-valued logic, first-degree entailment, contains both of the three-valued logics as fragments: drop $n$ and it is the logic of paradox, drop $b$ and it is Kleene’s gap logic. It loses both excluded middle and explosion, and it has no tautologies at all, but it has a clean set of valid inferences that a database can use: when two sources disagree about a fact, the database stores $b$ for it, and answers about other facts are unaffected. A contradiction stays where it is, and the computer’s answer to a question about it is not yes or no but the honest report that its sources disagree.

The surprising connection: the liar #

Priest’s motivation was not databases. It was the oldest paradox in logic, the sentence that says of itself that it is false. If it is true, it is false; if it is false, it is true. Self-reference alone is harmless — a program can print itself, and a sentence can say of itself that it is short — and the trouble comes only when self-reference is combined with negation. Classical logic has no consistent truth value to give the liar, and every classical treatment either bans such sentences, as Tarski did by separating a language from the language that talks about its truth, or adds a gap, so that the liar is neither true nor false — which then fails for the “strengthened” liar, “this sentence is not true”, which is true if it is a gap.

Priest’s proposal, dialetheism, is that the liar is both true and false, and the logic of paradox is the logic in which that can be said without everything following. The liar takes the value $b$; its negation also takes $b$; both hold; and nothing else is affected. The same treatment applies to the paradoxes of self-reference that this subject has met in other forms — the list that cannot contain itself, the word that cannot describe itself — which in classical logic are refutations and in the logic of paradox are true contradictions, quarantined.

Whether any contradiction is actually true is a philosophical question, and most logicians answer no. The usual alternatives treat the liar as a gap, which the strengthened liar defeats, or restrict which sentences may mention truth, which defeats the ambition of a language that can describe itself; the dialetheist accepts one strange consequence in exchange for avoiding both. But the mathematical fact behind the proposal is independent of the philosophy: there is a logic, with the same laws as classical logic and almost all of its inferences, in which a contradiction can be held without consequence, and its countermodels are found by checking nine valuations.

Eight rules checked, and the theorems that cover the rest #

The census of rules is finite. Eight rules were tested, and each test is complete for its rule, since a rule in two variables has nine three-valued valuations to check. Which rules hold in general — all of them, for formulas of any size — is described by theorems about the logic, of which the census is a sample, not a proof.

The tautology theorem is checked for small formulas and stated for all. The figure confirms that the classical tautologies and the logic of paradox’s tautologies coincide among the 56 functions of formulas up to size four. The general statement, for formulas of any size, follows from an argument about replacing $b$ by $t$ or $f$, given in words above and not drawn.

The logics here are propositional. Paraconsistent logics with quantifiers, and paraconsistent theories of sets in which Russell’s set is allowed to exist without collapsing the theory, are a large subject whose results depend delicately on which classical principles are kept. Nothing in the figures speaks to them.

Still open: a paraconsistent mathematics #

The logic of paradox handles a contradiction among propositions. The ambition of Priest and others has been to do mathematics in such a logic — naive set theory, in which every property defines a set, including the property of not belonging to oneself; or naive truth theory, in which every sentence can talk about its own truth. In classical logic both are inconsistent and therefore trivial: they prove everything. In a paraconsistent logic they can be inconsistent without being trivial, and the question is how much ordinary mathematics survives inside them.

The answer is partial and contested. Naive set theory over the logic of paradox is non-trivial, but in it the material conditional is too weak to support much reasoning, because modus ponens fails; stronger conditionals bring back paradoxes of their own, such as Curry’s, which derives any statement from a sentence that says “if this sentence is true, then $q$”. Which conditional, if any, allows a paraconsistent set theory strong enough for the arithmetic of infinite sets while staying non-trivial is an open question, and it is where the logic of three truth values, simple enough to check by hand, meets the foundations of mathematics.