zaterdag 5 december 2015

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 (pq) from false propositions everything follows
PP4 q (pq) everything implies a true proposition
PP5 (pq) (qr) imply or be implied!
PP6 [ (pq) (rs) ] [ (ps) (rq) ] consequent exchange
PP7 [ (pq) r] [ (pr) (qr) ] 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 pq 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 pq PP4 q pq
PP6 (pq) (rs) (ps) (rq)
PP7 (pq) r (pr) (qr)

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 (pq) q pq
connective q pq q pq

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:

pq | qr (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 v0 exists such that v0( P ) = and v0( Q ) = and another valuation v1 exists such that v1( Q ) = and v1( R ) = . Hence, neither for all situations in which P we have Q (because v0 exists) nor for all situations in which Q we have R (because v1 exists). Formally this means that we have an example where both PQ and QR . 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:

(pq) (rs) ps | rq (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 vL( p ) = , vL( q ) = , vL( r ) = and vL( s ) = makes that ps , and valuation vR( p ) = , vR( q ) = , vR( r ) = and vR( s ) = makes that rq .

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:

(pq) r pr | qr (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.

9 opmerkingen:

  1. Hoi Jeroen,

    Een bijzonder interessante bijdrage! Ik zal op mijn blog binnenkort met een uitgebreide reactie komen.

    Hartelijke groet,
    Emanuel

    BeantwoordenVerwijderen
    Reacties
    1. Hi Emanuel,

      Dank voor deze hartelijke eerste reactie op mijn kersverse blog. Ik kijk met belangstelling uit naar het vervolg! Dat we nog vele nieuwe paradoxen mogen ontdekken. Alle reacties over dit interessante onderwerp zijn natuurlijk van harte welkom.

      Vriendelijke groet, Jeroen

      Verwijderen
  2. Hi Jeroen,

    I finally found the time to respond: http://goo.gl/x4YQwK

    Best,
    Emanuel

    BeantwoordenVerwijderen
  3. Hi Emanuel,

    Je hebt me flink aan het denken gezet, maar ik ben er uit! Zeer binnenkort volgt hier op mijn blog een interessante reactie.

    Groet,

    Jeroen

    BeantwoordenVerwijderen
  4. Bert,
    "[1] If Brigitte has yellow paint and blue paint, then Brigitte can mix green,
    [2] Brigitte can mix green with yellow paint or Brigitte can mix green with blue paint. Clearly, no one wants to hold that [2] is a logical consequence of [1]. The argument having [1] as premise and [2] as conclusion should definitely be logically invalid".

    Zo zie ik het ook. Neem een eenvoudig voorbeeld.
    Als ik pen en papier heb kan ik een artikel schrijven.
    Daaruit volgt geenszins dat ik een artikel kan schrijven als ik een pen heb en ook niet dat ik een artikel kan schrijven als ik papier heb.

    groet,
    Jac

    BeantwoordenVerwijderen
  5. Bert,
    Vergeet mijn bovenstaande opmerking.

    P=ik heb een pen
    Q=ik heb papier
    R=ik kan een brief schrijven.
    P^Q->R
    Het ligt er nu maar net aan hoe P^Q->R begrepen moet worden.
    Als wij het begrijpen als: ik heb een pen en papier en dus kan ik een brief schrijven dan volgt uit P^Q->R:
    P->R v Q->R.
    Immers, heb ik een pen dan heb ik pen en papier en heb ik papier dan heb ik ook een pen en papier (ik heb immers beide.
    Lijkt mij niet zo moeilijk; niets schandaligs te ontdekken.
    groet,
    Jac

    BeantwoordenVerwijderen