Continuing the Debate on Paradoxes of Material Implication

This article continues an interesting debate about the paradoxes of the material implication. The debate started when Emanuel invented two examples that convincingly reveal a paradox. One of his examples is expressed by the following two sentences in natural language:

[1] If Jan is older than 20 years and younger than 30 years then Jan is between 20 and 30 years old.

[2] Whether Jan is between 20 and 30 years old either follows from the fact alone that Jan is older than 20 or from the fact alone that Jan is younger than 30.

Introducing three propositional symbols:

• P: Jan is older than 20 years;
• Q: Jan is younger than 30 years;
• R: Jan is between 20 and 30 years old;

Emanuel renders the argument [1]-[2] as follows in propositional logic:

• [1*] P ∧ Q → R
• [2*] P → R ∨ Q → R

Note that in all situations in which [1*] holds, [2*] holds as well. In modern logic, the logical inference operator ⊨ has been defined to capture this notion of valid reasoning. Indeed, it can be shown that the following holds:

[1*] P ∧ Q → R   ⊨   [2*] P → R ∨ Q → R (EQ1)

Therefore, Emanuel concludes that the reasoning [1]-[2] is logically valid.

My idea was to render the formalization differently. To avoid confusion around the adjunctive and connective reading of the implication, I invoked the logical inference operator rather than the material implication. The paradox is then formalized as follows:

P ∧ Q ⊨ R   ⇒   P ⊨ R or Q ⊨ R (EQ2)

Interestingly, though EQ1 holds, EQ2 does not hold. Hence, EQ2 being false shows us, as expected, that if P and Q entails R then neither P entails R nor Q entails R. To get convinced of the existence of a paradox, we need something along the lines of EQ1.

In his response, Emanuel dismissed EQ2 as a proper formalization by claiming that it is much too strong. But is he justified to make this claim? Certainly not. When proving, say B follows from A, an indirect proof does not suffice. Such a proof needlessly demystifies how exactly A entails B. Once the mystery is clarified, one can see how B follows from A and the paradox is resolved. This is the general idea which I will further explain in the sequel.

So how is one supposed to refute a proponent that starts his reasoning from the premise P ∧ Q -> R? The answer is straightforward. In the dialectical method it is very reasonable to expect the proponent to defend his or her premises. With P, Q and R the selected proposition symbols, the proponent lacks the logical context to be sufficiently justified. The opponent can prove ⊭ P ∧ Q -> R to oppose against the premise. Hence, it appears the proponent starts from a false premise. He or she must show how R follows exactly from P and Q; thereby demystifying the implication.

The correct premise is that Jan must be of a certain age; this clearly cannot be refuted. Now, it immediately follows that exactly one of the following must hold:

P': Jan is 20 years old or younger (i.e., P' ↔ ¬P)

Q': Jan is 30 years old or older (i.e., Q' ↔ ¬Q)

R: Jan is between 20 and 30 years old (R)

Note that it follows that ¬P' ∨ ¬Q', or equivalently P ∨ Q. Also note that P becomes R ∨ Q' and Q becomes R ∨ P'. Suppose R ∨ P' (i.e., Q) and R ∨ Q' (i.e., P). Because either P' or Q' (or both) must be false, it follows that R must hold. This is how the proponent ought to show the implication: (R ∨ P') ∧ (R ∨ Q') → R. Formally, we arrived at the following result:

G ⊨ P ∧ Q → R (EQ3)

where G is the background theory containing at least:

1. P ↔ R ∨ Q'
2. Q ↔ R ∨ P'
3. P ∨ Q

Finally, using EQ1 as an inference rule we obtain the more complete formalization of the paradox:

G ⊨ (P → R) ∨ (Q → R) (EQ4)

Thus far, we have only demystified the material implication in the premise. In order to demystify the two implications in the conclusion, the key is to realize that material implications in a propositional formula may well be conditional. An explicit example is A → (B → C). Here, B → C is a conditional implication meaning that C is only implied by B under the condition that A holds.

In a disjunctive conclusion, implicit conditions of a material implication may occur. Because either P or Q (or both) must hold, both P and Q can become implicit conditions of material implications. The natural deduction proof reveals this:

1. G ⊨ P ∨ Q (from the premise)
2. G ⊨ P ∧ Q → R (from EQ3)
3. G, P ⊨ P (hypothesis)
4. G, P, Q ⊨ Q (hypothesis)
5. G, P, Q ⊨ P ∧ Q (∧-intro, 3, 4)
6. G, P, Q ⊨ R (→-elim, 2, 5)
7. G, P ⊨ Q → R (→-intro, 4, 6)
8. G, Q, P ⊨ P (hypothesis)
9. G, Q, P ⊨ R (reiteration, 6)
10. G, Q ⊨ P → R (→-intro, 8, 9)
11. G, P ⊨ P → R ∨ Q → R (∨-intro, 7)
12. G, Q ⊨ P → R ∨ Q → R (∨-intro, 10)
13. G ⊨ P → R ∨ Q → R (∨-elim, 1, 11, 12)

Note how the natural deduction proof reveals the implicit conditions at steps 7 and 10, because P and Q occur as condition at the left-hand side of ⊨, respectively. How does R follow from P in the conclusion of EQ4? The answer is: it follows conditionally given that Q holds. And how does R follow from Q? Again: it follows conditionally given that P holds.

So yes, R can be implied from P or Q, but otherwise as explicitly stated in natural language (see [2]), R is not implied from P alone or from Q alone. The word alone is just one bridge too far and makes the meaning of [2] very strong. So strong that indeed my formalization (see EQ2) is needed to detect the conditional implications. Hence, EQ2 is not too strong at all. It is EQ1, Emanuel's rendering, that is too weak: corresponding only with the weaker conclusion:

[2'] Whether Jan is between 20 and 30 years old is (conditionally) implied by the fact that Jan is older than 20 or the fact that Jan is younger than 30.

Propositional Paradoxes

It is well known that there is a philosophical controversy around the definition of the material implication in modern propositional logic. To illustrate what the controversy is about, literature has provided numerous propositional paradoxes containing the implication connective. These paradoxes are logical tautologies whose truism is sufficiently counterintuitive to require further explanation. However, many logicians are not bothered by the paradoxes at all. Typically, modern logic is advocated as an ultimate systematic foundation to which all reasoning can be and eventually should be reduced.

Recently, in his lecture titled “Het schandaal van de propositie logica” , Emanuel Rutten recognizes the logician’s systematic foundation to be merely a logica docens: an attempt to teach a logica naturalis which already pre-exists as the natural human skill of correct reasoning. He argues that, whenever in the face of paradoxes, we are obliged to abandon instead of defend our logica docens, and primarily seek explanation in our logica naturalis. In their obsession to achieve ultimate mastery of logical reasoning, logicians are blinded rather than enlightened when granting supreme authority to the formal systems they create.

While Rutten’s advice is generally an effective approach to resolve paradoxes, the examples he provides can be tackled by a more specific metatheoretical explanation. Indeed, as Rutten points out in his lecture, his paradoxes are problematic within the language of propositional logic. But I will show that the paradoxes can be formalized more naturally in the metalanguage (i.e., first-order predicate logic) in which propositional logic itself is defined. As such, we can explain the paradoxes while retaining modern logic’s supremacy.

Logical Preliminaries

In this blog, we will discuss the following propositional paradoxes each written as a single propositional formula containing the material implication:

PP1	⊨ (p∧ ¬ p ) →q	from contradiction everything follows
PP2	⊨ p→ (q∨ ¬ q )	everything implies a logical tautology
PP3	⊨ ¬ p → (p→q)	from false propositions everything follows
PP4	⊨ q→ (p→q)	everything implies a true proposition
PP5	⊨ (p→q) ∨ (q→r)	imply or be implied!
PP6	⊨ [ (p→q) ∧ (r→s) ] → [ (p→s) ∨ (r→q) ]		consequent exchange
PP7	⊨ [ (p∧q) →r] → [ (p→r) ∨ (q→r) ]		Rutten's paradox

To see if and why these seven paradoxes are counterintuitive, we refer the reader to external sources. In his lecture, Rutten provides an excellent presentation of PP7 and he presents a more detailed treatment here. The other paradoxes I borrowed from Wikipedia where also PP7 is briefly discussed and illustrated with a lightswitch example. More in general, attempts to intuitively explain the material implication are abundant: e.g., Matthew Clarke provides an overview with references to the literature.

In the table above, we used lowercase letters p , q , r and s to denote arbitrary propositional formulae and the metatheoretic ⊨ operator to express logical tautology. Model theoretically, writing ⊨ ψ means that a formula of the form ψ is true in all possible situations. Each situation can formally be described by a valuation: a function that assigns either ⊤ (which stands for true) or ⊥ (which stands for false) to each lowercase letter that occurs in ψ . On composite formulae the valuation then assigns according to the truth tables for the logical connectives. As such, the four possible valuations for paradoxes PP1 to PP4 are as follows:

p	q	¬ p	¬ q	p∧ ¬ p	q∨ ¬ q	p→q	PP1	PP2	PP3	PP4
⊥	⊥	⊤	⊤	⊥	⊤	⊤	⊤	⊤	⊤	⊤
⊥	⊤	⊤	⊥	⊥	⊤	⊤	⊤	⊤	⊤	⊤
⊤	⊥	⊥	⊤	⊥	⊤	⊥	⊤	⊤	⊤	⊤
⊤	⊤	⊥	⊥	⊥	⊤	⊤	⊤	⊤	⊤	⊤

The ⊨ operator can also be used to express the logical inference relation. Formally, ψ follows logically from φ , denoted φ⊨ψ , if all possible valuations that make the premise evaluate to ⊤ , the conclusion also evaluates to ⊥ . A central result in model-theoretic semantics is the deduction theorem:

⊨ φ→ψ ⇔ φ⊨ψ

for arbitrary propositional forms φ and ψ . For a proof of the deduction theorem, note that both the left-hand side (lhs) and right-hand side (rhs) are equivalent to the condition that for all valuations, ψ evaluates to ⊤ if φ evaluates to ⊤ .

Normal Forms

As a result of the deduction theorem, we can equivalently rephrase the paradoxes, except PP5, in their normal form:

PP1	p∧ ¬ p ⊨ q	PP2	p⊨ q∨ ¬ q
PP3	¬ p ⊨ p→q	PP4	q⊨ p→q
PP6	(p→q) ∧ (r→s) ⊨ (p→s) ∨ (r→q)
PP7	(p∧q) →r ⊨ (p→r) ∨ (q→r)

Each paradox has now naturally been decomposed from a single propositional formula into a separate premise and a separate conclusion. Note that, after this rewriting, PP1 and PP2 no longer contain a material implication at all. This makes PP1 and PP2 paradoxes of logical inference rather than material implication, but I doubt whether they are paradoxical at all.

In the paradoxes’ normal form, logical truth should be verified by checking that whenever the premise evaluates to ⊤ , the conclusion also evaluates to ⊤ . Using colors and a grey background in the two tables aboves, the verification is illustrated for paradoxes PP3 and PP4. Verifying PP6 and PP7 is left as an exercise to the reader.

Two Meanings of Implication

In natural language, words as “implies” and “if..then..” may at least have two different meanings. At times, we speak the words truth theoretically to indicate our intention to assume an implication as a premise for our argument. Someone who wants to prove our assumption wrong should then show that the consequent of our implication can be false while the antecedent holds. Otherwise, we can rightly assume the implication.

At other times, we speak the words to express a logical dependence (or some other connection) between the antecedent and consequent of the implication. This has been recognized as early as 1947 by Hans Reichenbach. He writes:

It recently happened in Los Angeles that, while the screen of a movie theatre was showing a blasting of lumber jammed in a river, an earthquake shook the theatre. The implication “the blasting of lumber on the screen implied the shaking of the theatre” was then true in the adjunctive sense whereas it was false in the connective interpretation. ... We realise that the word “implies” here has not the same meaning as in conversational language; the implication in this case simply adjoins one statement to the other without connecting the statements. Adjunctive implication has a wider meaning than connective implication; if a connective implication holds, there also exists an adjunctive implication, but not vice versa.

Reichenbach uses the terms adjunctive implication and connective implication. The adjunctive implication is clearly linked to the material implication and its characteristic truth table. The connective implication is naturally linked to logical inference. This distinction must be properly accounted for whenever we formalize a discourse from natural language. For example, when we formalize “if p then q implies p”, we first need to know if the implication was intended adjunctively or connectively. Hence, exactly four possible formalization candidates exist:

inner implication	outer implication
	adjunctive	connective
adjunctive	⊨ q→ (p→q)	q⊨ p→q
connective	⊨ q ⇒ p→q	⊨ q ⫢ p⊨q

Note that the interpretation where both implications are connectively understood required us to use the metametalogical operator ⫢ , which we call entailment, to reason about inference for the first-order predicate logic that is used as metalanguage. The premise and conclusion of the entailment are now first-order statements about logical tautology and inference for the propositional object language.

Also note that we may need to shift some logical connectives from the object language to the metalanguage: e.g., in the adjunctive-connective reading we used the metalogical implication ⇒ instead of → . In the sequel, we will use the metalogical connective | as alternative for the logical connective ∨ . Apart from the language in which the alternatives live, the alternative connectives are equivalent to their originals. Both the originals and the alternatives have exactly the same truth table definitions.

To conclude, we are now able to see that PP3 and PP4 are in fact exactly the same as PP1 and PP2, respectively. The adjunctive-connective reading of PP3 states that if ¬ p is a tautology then from p everything follows. This is the same as saying that from a contradiction everything follows. Paradoxes PP1 and PP2 are actually instantiations of PP2 and PP4, respectively, by filling in the tautology of the form p∨ ¬ p and the contradiction of the form p∨ ¬ p for p and q , respectively.

Correct Formalizations

In the following subsections we will consecutively address the remaining propositional paradoxes PP5, PP6 and PP7. The approach used to resolve them follows a common scheme based on the law of the excluded middle (tertium non datur, abbreviated TND) combined with the previous results for paradoxes PP3 and PP4.

Resolving the Fifth paradox

Let us start by considering PP5. It holds indeed that adjunctively (or materially if you prefer) every proposition, say q , either implies every proposition or every proposition implies q . But this is saying no more and no less than that q can be either false or true (TND). On the one hand, if q is false then from PP3 we already know that from a false proposition everything follows. On the other hand, if q is true then from PP4 we already know that everything implies a true proposition. Hence, by TND and the fact that we argued previously that PP3 and PP4 are not paradoxical, it should be perfectly aligned with our intuition that everything implies q or q implies everything.

However, if for every q, either q follows logically from everything or everything follows logically from q, then this would be a paradox indeed. But to formalize this intuition correctly, we should have chosen the logical inference relation instead:

p⊨q | q⊨r

(EQ1)

where | is the metalogical alternative for the logical connective ∨ .

Fortunately, EQ1 does not generally hold. Counterexamples are easy to find by choosing p , q and r such that they are logically independent. Take for instance the atomic proposition symbols P , Q and R for p , q and r , respectively. Clearly a valuation v₀ exists such that v₀( P ) =⊤ and v₀( Q ) =⊥ and another valuation v₁ exists such that v₁( Q ) =⊤ and v₁( R ) =⊥ . Hence, neither for all situations in which P we have Q (because v₀ exists) nor for all situations in which Q we have R (because v₁ exists). Formally this means that we have an example where both P⊭Q and Q⊭R . Hence, when properly formalized, PP5 is not a paradox, because it is false as we would intuitively expect.

Resolving the Sixth paradox

To see whether we should choose the adjunctive or the connective interpretation on PP6 (and PP7), let us look at some examples where our intuition goes wrong. Wikipedia provides us the following examples:

PP6:	p :=	"John is in Londen"	PP7:	p :=	"switch A is closed"
	q :=	"John is in England"		q :=	"switch B is closed"
	r :=	"John is in Paris"		r :=	"the light is on"
	s :=	"John is in France"

The counterintuitive conclusion of paradox PP6 is that, by consequent exchange, either London appears to be in France or Paris appears to be in England. This sounds absurd! However, on closer look it appears to be due to implicit logical dependence between the four propositions. Similar to how we used TND on PP5, we are in fact saying with the conclusion of PP6 no more and no less than that John must be somewhere. On the one hand, if John is neither in England nor in France then by logical dependence p and r are also false. No wonder the conclusion holds, because from false propositions everything follows (see PP3). On the other hand, if John is either in France or in England then s is true or q is true. No wonder that the conclusion holds, because everything implies a true proposition (PP4) and either s or q is true indeed. Hence, again by TND, PP6 should be perfectly aligned with our intuition.

It would be a real surprise if we could logically derive London to be in France, or Paris to be in England. The correct formulation of the paradox is therefore:

⊨ (p→q) ∧ (r→s) ⇒ p⊨s | r⊨q

(EQ2)

Fortunately, EQ2 does not generally hold. To construct the counterexample, note that the lhs does not rule out sufficient valuations to make the rhs hold. Valuation v_L( p ) =⊤ , v_L( q ) =⊤ , v_L( r ) =⊥ and v_L( s ) =⊥ makes that p⊭s , and valuation v_R( p ) =⊥ , v_R( q ) =⊥ , v_R( r ) =⊤ and v_R( s ) =⊤ makes that r⊭q .

Resolving the Final paradox

Finally, paradox PP7 can be resolved along similar lines. The paradox would only be counterintuitive if we could actually prove a logical inference as a conclusion from the premises. Rutten provides the following two illustrations of PP7:

p :=	"Brigitte has yellow paint"	p :=	"Jan is older than 20 years"
q :=	"Brigitte has blue paint"	q :=	"Jan is younger than 30 years"
r :=	"Brigitte can mix green paint"	r :=	"Jan is between 20 and 30 years old"

The counterintuitive conclusion of PP7 is that, apparently, Brigitte can mix green paint with either yellow paint alone or with blue paint alone. However, along similar lines, the conclusion is in fact stating no more and no less than that Brigitte either has all the required paint or not. On the one hand, if Brigitte has the required paint then, it follows from the premise that she can mix green paint! Since everything implies a true proposition (see PP3), it should not come as a surprise that p and q also exist as members among the collection of everything. On the other hand, if Brigitte is missing either yellow or blue paint then either p or q is false. But from a false proposition everything follows (see PP4), and again it should not come as a surprise that r belongs to the set of everything.

To conclude, a true surprise would the following paradox be:

⊨ (p∧q) →r ⇒ p⊨r | q⊨r

(EQ3)

But, fortunately, EQ3 does not generally hold and we leave it as an exercise to the reader to construct a counterexample. It is also left as an exercise to take the lightswitch example and Rutten’s second example and establish an argument that supports the intuitive understanding of the adjunctive meaning of the implication.

Conclusion

It is well known that the material implication is difficult to understand intuitively on a first encounter. Typically, someone learning propositional logic starts by appreciating logic’s trickery of applying truth tables and logical inference rules, and is usually overwhelmed by the mathematical apparatus required to define the semantics of modern logic. The fact that semantics of modern logic is circularly defined in itself is not making things easier. To even be equipped for the task, logic’s trickery is the first indispensable tool. Yet, in case of paradoxes in modern logic and for what it is worth, my advice is to primarily consult formal semantics in the model-theoretic tradition, and secondary our logica naturalis.