Excluded Middle – Bas van Fraassen's philosophy blog

A reductio ad absurdum to eliminate a negation is not valid in Intuitionistic logic. But that is not the only place in logic where arguments by reductio are considered invalid. And historically, reductio arguments have been criticized on many grounds since even before Descartes and the Port Royal Logic regarded them with disfavor.

1. The principles of Explosion and Reductio

There is a close relation between reductio arguments and the principle:

Explosion. (p & ~p) implies q.

I will give a similar name to its (putative) dual:

Implosion. q implies (p v ~p),

There are two forms of reductio arguments (where f is the falsum, which may or may not be a sentence of form (p & ~p)):

(Reduc-Int) if X, p implies f, then X implies ~p

(Reduc-Elim) if X, ~p implies f, then X implies p

For example, Intuitionistic logic has both Explosion and Reduc-Int, but Intuitionists sharply reject Reduc-Elim. In their honor I tend to refer to the first as the good Reductio and to the latter as the bad Reductio. In classical logic where (p& ~p) is the falsum and (p v ~p) the verum, there is not much to discuss. The questions I want to address are about these principles in contexts where very little is assumed about negation.

2. Assuming only a very minimal background logic.

What I would like to do here is to start with just the &-v fragment common to these logics. The syntax will be the sentential syntax with connectives &, v, ~, and a propositional constant f, but the logic will have no principles governing ~ or f. (Our quest is to find out what principles re ~ and/or f will be needed to arrive at, eventually, the bad Reductio.)

For semantics I take it that any admissible interpretation will assign to each sentence as semantic value (“the proposition expressed”) and element of a lattice (“the family of propositions expressed”), with &, v, ~ paired with respectively the meet ∧, the join v, and a special unary operation *. But to begin we have no principles pertaining to *, we only have the lattice laws:

Definition 1. x ≤ y iff x ∧ y = x

Definition 2. x ≤ y iff x v y = y.

Lattice laws. x ≤ x v y, y ≤ x v y, x ∧ y ≤ x, x ∧ y ≤ y

if x ≤ z and y ≤ z then x v y ≤ z,

if z ≤ z and z ≤ y then z ≤ (x ∧ y)

The definitions are equivalent, but I will sometimes use one, sometimes the other. The defined relation ≤ on the family of propositions corresponds to implication for the sentences expressing those propositions. On the side of the sentences, the logical principles assumed at the outset are therefore the corresponding principles, with “⊢” for “implies”:

p ⊢ p v q, q ⊢ p v q, p & q ⊢ p, etc.

This logic I will call lattice logic.

When examining proofs I will write (L) if the move is valid by the lattice logic, or the lattice laws, alone.

Terminology. We note the following principles for reference, to fix terminology.

Disjunctive Syllogism (DisjSyl) : ~p & (p v q) implies q

Material Modus Ponens (MatMP): p & (~p v q) implies q

In classical logic these are equivalent, but that is due to the principle of Double Negation, which we won’t assume at any point.

Once we begin to focus on the semantic side I will give the corresponding lattice-theoretic formulation of all the above logical principles, and will (without expecting any confusing) give them the same names.

3. Disjunctive Syllogism entails Explosion

This is the famous argument by C. I. Lewis.

[T1] p & ~p ⊢ q, by DisjSyl

p & ~p assume
p 1, (L)
p v q 2, (L)
~p 1, (L)
q from 3, 4 by DisjSyl

How could the last move be justified in lattice logic? We can continue for 4. with

5-1 ~p & (p v q) 4, 3, (L)
5-2 (~p & p) v (~p & q) 5-1, distribution
5-3 ~p & q 5-2, emptiness of p&~p
5-4 q 5-3, (L)

It would be interesting enough if we could justify Reductio with just distribution as extra principle. But that is not so. The move to 5.3 appears to rest on principle that

(p & ~p) v q implies q

or in lattice terms (x ∧ x*) v y ≤ y, and since the converse is obvious, that is equivalent to (x ∧ x*) v y = y. But that is by Definition 2 the same as (x ∧ x*) ≤ y, which is exactly the principle of Explosion. So the ‘proof’ would assume Explosion, which begs the question.

4. Material Modus Ponens entails Explosion

[T2] p & ~p ⊢ q, by MatMP

Adaption of the previous argument:

p & ~p assume
~p 1, (L)
~p v q 2, (L)
p 1, (L)
q from 3, 4 by MatMP

5. Given distribution, Explosion, DisjSyl, and MatMP are equivalent

The arguments above establish that Disjunctive Syllogism and Material Modus Ponens, in the context of just the basic lattice laws, each entail Explosion. The converses can be proved if we add Distribution to the lattice logic.

Now it will be most convenient to focus on the semantic side. We have the following results for distributive lattices:

[T3] Explosion implies Disjunctive Syllogism

1. x ∧ x* ≤ y Assumption (which includes that the lattice is bounded below, with special element 0 (bottom), and (x ∧ x*) = 0).

2. (x* ∧ x) v y = y Definition 2, (L).

3. (x* v y) ∧ (x v y) = y 2, distribution

4. [x* ∧ (x v y)] v [(y ∧ (x v y)] = y 3, distribution

5. [x* ∧ (x v y)] v y = y (L)

6. [x* ∧ (x v y)] ≤ y 5., Definition 2.

[T4] Explosion entails Material Modus Ponens :

1. x ∧ x* ≤ y Assumption (which includes that the lattice is bounded below, with special element 0 (bottom), and (x ∧ x*) = 0).

2. (x* ∧ x) v y = y Definition 2, (L).

3. (x v y) ∧ (x* v y) = y 2, distribution, and (L)

4. [x ∧ (x* v y)] v [(y ∧ (x* v y)] = y 3, distribution

5. [x ∧ (x* v y)] v y = y (L)

6. [x ∧ (x* v y)] ≤ y 5., Definition 2.

Corollary. In distributive lattices, Disjunctive Syllogism is equivalent to Material Modus Ponens (although Double Negation is not valid).

6. When the good Reductio is valid

Since the good Reductio is formulated using the propositional constant f we need to restrict the interpretations of the syntax to ones that give f a semantic value. So from here on we will restrict our attention to lattices that are bounded below, with least element 0 (bottom), that is to say, for all elements x, 0 ≤ x. And the proposition expressed by f is 0.

Definition 3. Lattice elements x, y are disjoint iff x ∧ y ≤ 0 (equivalently, iff x ∧ y = 0).

The good Reductio is

(Reduc-Int) if X, p implies f, then X implies ~p

For the lattice of propositions, that means that for all elements x, y:

(Reduc-Int) If x ∧ y ≤ 0 then x ≤ y*.

Though we have no special principles yet pertaining to operation *, we know that it is a map of the lattice into itself.

Hence it is clear what Reduc-Int says:

y* is an element which is at least as weak as any element disjoint from y.

It follows from this that the lattice must also be bounded above, with largest (weakest) element 1 (top). For all elements are disjoint from 0, and if the lattice does not have a top then no element is at least as weak as any element disjoint from 0. 1 is disjoint from 0, and is at least as weak as any element whatsoever, hence 1 = 0*. Moreover, only 0 is disjoint from 1, so 1* = 0.

A traditional definition of negation is that ~p is the logically weakest statement such that (p & ~p) ⊢f. For lattices in general there need not exist a largest (weakest) element in the family of elements disjoint from a given element (other than 0 or 1).

So the good Reductio does not suffice to identify the operation *. For that we need to add Explosion.

[T5] If Explosion and Reduc-Int both hold in lattice L then x* is the greatest (weakest) element disjoint from x.

This connects very well with a major topic in lattice theory: the pseudo-complement. Its definition amounts to the combination of Explosion and the good Reductio:

Definition 4. Unary operation * on a lattice is a pseudo-complement iff, for all elements x, y, (y ∧ y*) = 0 and if x ∧ y ≤ 0 then x ≤ y*.

Corollary. If Explosion and Reduc-Int both hold in lattice L then x* is a pseudo-complement.

7. When the bad Reductio is valid

The pseudo-complement has many of the familiar features of negation in general, but it specifically lacks Excluded Middle.

Now, look at

(Reduc-Elim) if X, ~p implies f, then X implies p

also called Indirect Proof, which is, for the lattice of propositions,

(Reduc-Elim) If x ∧ y* ≤ 0 then x ≤ y,

equivalently, if x ∧ y* = 0 then x ≤ y.

We note that Implosion entails that the lattice has a top element, call it 1, and that for any element x, 1 = x v x*.

Implosion entails the bad Reductio, given distributivity. Precisely:

[T6] If the lattice is distributive, bounded above with top 1, and (x v x*) = 1 for all elements x, then Reduc-Elim holds in that lattice.

To prove: If x ∧ y* = 0 then x ≤ y.

x ∧ y* = 0 Assume
x = x ∧ 1 (L)
x = x ∧ (y v y*) 2, Given (Implosion)
x = (x ∧ y) v (x ∧y*) (L), Distribution
x = (x ∧ y) v 0 1, 4, (L)
x = (x ∧ y) 5, (L)
x ≤ y. 6, Definition 1.

Notice that this argument does not depend on any special properties of *.

Implosion has much to answer for.

The relation between negation and infinity loomed large in the Intuitionist critique of mathematics. But when we come to Intuitionistic logic, it turns out to be all about the conditional. Negation comes in just by means of a definition: ~A =_def A → f.

It is in the logic’s realizations that the intimate relation between negation and infinity comes to the fore. Recall from the previous post that the lattice of theories of any distributive logic is a complete Heyting lattice with zero element Cn(𝜙), and

T → T’ is the weakest (largest) theory X such that T ∩ X ⊆ T’;

T → T’ = ⊕{T’’: T ∩ T’’ ⊆ T’)

The pseudo-complement ¬T of T, if it exist, must be the weakest element X which is contrary to T, that is, it is such that T ∩ X ⊆ Cn(𝜙). So we instantiate the above: ¬ T is the weakest element X such that T ∩ X ⊆ Cn(𝜙)), hence:

¬ T = T → Cn(𝜙). Equivalently, ¬ T = ⊕{T’: T ∩ T’ ⊆ Cn(𝜙)}.

So much, so general. How does it happen that the Laws of Excluded Middle and of Double Negation fail in Intuitionistic logic, and their corresponding principles fail in the calculus of systems?

To continue, let L be classical propositional logic, with & and ~ as primitive connectives and let S be the set of all sentences. Thus S = Cn(S) is the unit (top) of the lattice. For brevity, if A is a sentence I will write “Cn(A)” for “Cn({A})”.

Note: Contrariety, the condition T ∩ T’ ⊆ Cn(𝜙), is different from mutually inconsistency. With p, q atomic sentences, Cn(𝜙) is contrary to but consistent with Cn(p), Cn(p) and Cn(~p) are both mutually inconsistent and contrary. But Cn(p & q) and Cn(~p & q) are mutually inconsistent, their join is S, but not contrary for their intersection contains non-theorem q. Contrariety is this:

Theorem 1. T ∩ T’ ⊆ Cn(𝜙) iff for every non-theorem A in T there is a consistent extension of T’ that includes ~A.

To prove this we can appeal to the general features of theories in classical logic:

any consistent theory is part of a maximal consistent theory
every theory is the intersection of all its maximal consistent extensions
for all sentences A, if T is a maximal consistent theory then T contains either A or ~A
if T does not imply A then T has a maximal consistent extension that includes ~A

Proof.

Let A be any L-non-theorem in T. Suppose that T’ has no consistent extension that includes ~A. Then A is in all the maximal consistent extensions of T’, hence in T’, hence in T ∩ T’, which is thererfore not included in Cn(𝜙).
Suppose that for every L-non-theorem A in T, T’ has a consistent extension which includes ~A. Then if A is an L-non-theorem in T, A is not in T’, and hence not in T ∩ T’. If A is an L-non-theorem that is not in T then it is also not in T ∩ T’. Therefore T ∩ T’ contains only L-theorems, and is Cn(𝜙).

Lemma 1. Cn(~A) ⊆ ¬Cn(A)

If E is in Cn(A) there is a sentence B such that E is equivalent to A v B. For each such sentence Cn(~A) has a consistent extension that includes ~(A v B).

If ~A entails B then it too entails A v B, so then A v ~A entails A v B, hence A v B is an L-theorem.
If ~A does not entail B then Cn(~A) has a maximal consistent extension that includes ~B, which includes ~A & ~B.

So by Theorem 1, Cn(A) ∩ Cn(~A) ⊆ Cn(𝜙). Hence Cn(~A) ⊆ CnA) → Cn(𝜙) = ¬Cn(A).

Theorem 2. If T is finitely axiomatizable then T Θ ¬T = S

Because of the classical conjunction rules, if T is finitely axiomatizable then there is a sentence A such that T = Cn(A). By the lemma, Cn(A) Θ Cn(~A) ⊆ Cn(A) Θ ¬Cn(A). But Cn(A) Θ Cn(~A) = Cn(Cn(A) ∪ Cn(~A)) = S.

It follows then that violations of Excluded Middle can only be by theories that are not finitely axiomatizable.

To pursue this we need to improve on the above lemma.

Lemma 2. T ∩ T’ ⊆ Cn(𝜙) iff for every non-theorem A in T there is a maximal consistent extension of T’ that includes ~A.

This follows at once from Theorem 1.

Lemma 3. If T ∩ T’ ⊆ Cn(𝜙) then T’ ⊆ ∩ Cn({~A: A is in T})

Suppose T ∩ T’ ⊆ Cn(𝜙) and that A is an L-non-theorem of T. Let KT’(A) be the set of all consistent extensions of T’ that include ~A. So ∩KT’(A) ⊆ Cn(~A). Let MT’ be the set of all maximal consistent extensions of T. Then for each L-non-theorem A of T:

T’ = ∩MT’ ⊆ ∩KT’(A) ⊆ Cn(~A).

Since T’ has a consistent extension that includes ~A for each L-non-theorem in T it follows that T’ ⊆ ∩{Cn(~A): A is an L-non-theorem in T}. From this the lemma follows because if A is an L-theorem then Cn({~A}) = S, which has no effect on the intersection.

Theorem 3. ¬T = ∩({Cn{~A}: A in T}).

First, it is clear that for every L-non-theorem A in T, ∩({Cn{~A}: A in T}) has a consistent extension that includes ~A. Therefore ∩({Cn{~A}: A in T}) ⊆ ¬T by theorem 1 and definition.

Secondly, T ∩ ¬T ⊆ Cn(𝜙), so by Lemma 3, ¬T ⊆ ∩ Cn({~A: A is in T})

Corollaries: Cn({~A}) = ¬Cn(A), ¬Cn(𝜙) = S, ¬S = Cn(𝜙)

This theorem gives us a way to identify the pseudo-complement of theories that are not finitely axiomatizable.

Example. Let AT be the infinite list of atomic sentences p₁, …, p_m , … and T = Cn(AT). Let AT_fin be the set of finite conjunctions of atomic sentences. Every member of T is equivalent to a finite conjunction C of atomic sentences disjoined with some other sentence A (e.g. p v q).

So ¬T = ∩ Cn({~(C v A): C in AT_fin})

As an example, consider the L-non-theorem (p₁ & ~p₂). Could it belong to ¬T? It does not belong either to Cn(~p₁) or to Cn(~p₂). Nor does it belong to Cn(~q) for any q in AT_fin other than p₁ or p₂.

We can generalize this reasoning to cover any L-non-theorem. Since L is classical propositional logic, we can think in terms of truth-table rows or their generalization:

a finite state-description is a consistent conjunction p^*₁ & …& p^*_m of atomic sentences each of which either has or does not have an appended negation sign.

In classical propositional logic, A is an L-non-theorem if and only if there is a finite state-description B such that B├_L~A. For any such B, since B is finite and AT is infinite, there is an atomic sentence q which does not appear in B. But then B is not in Cn(~q), hence not in ¬T. Therefore there is no derivation of ~A in ¬T. Hence ¬T = Cn(𝜙).

This gives us a counterexample to both Excluded Middle and Double Negation, with T = Cn(AT):

T ⊕ ¬T = T and T ≠ S

¬ ¬T = ¬ Cn(𝜙) = S and S ≠ T

The following analogy strikes me as apt. Remember that ¬T is also the join of its contraries. There are uncountably many infinite state descriptions, all inconsistent with each other. So we can look to continua for analogies. In a geometric space, the join of a family of subspaces is the least subspace that contains all. Suppose P is a plane, its subspaces are the straight lines through the origin. Take away one such straight line: the join of the remaining ones is still the entire plane.

Tag: Excluded Middle

About Explosion and Reductio ad Absurdum