if a certain natural deduction system is complete, then it is complete without material implication.

Consider 𝒲, the system of natural deduction articulated by the Howard-Snyders and Wasserman (2013). After introducing seventeen rules, some of which include Conditional Proof (CP), two forms of Reductio ad absurdum (RAA), Modus Ponens (MP), Simplification (Simp), Conjunction (Conj), Addition (Add), Commutation (Com), Double Negation (DN), and  Disjunctive Syllogism (DS), they introduce the rule of

    Material Implication (mi): 𝒫 ⊃ 𝒬  ∷ ¬𝒫 v 𝒬  

and they do so with the following justification:

Without material implication, our proof system would lack the capacity to prove valid every argument that is valid according to the truth table method. (p. 380)

One way to understand what the Howard-Snyders and Wasserman are sayings goes as follows: With (mi), 𝒲 can prove sentences of the form ¬𝒫 v 𝒬 from sentences of the form 𝒫 ⊃ 𝒬, and vice-versa. Or

    𝒫 ⊃ 𝒬 ⊢_𝒲 ¬𝒫 v 𝒬  

and

    ¬𝒫 v 𝒬 ⊢_𝒲  𝒫 ⊃ 𝒬

However, if we were to remove (mi) from 𝒲, perhaps forming the natural deduction system 𝒲*, we could not prove ¬𝒫 v 𝒬 from 𝒫 ⊃ 𝒬 and vice versa. That is:

    𝒫 ⊃ 𝒬 ⊬_𝒲*  ¬𝒫 v 𝒬

and

    ¬𝒫 v 𝒬 ⊬_𝒲*  𝒫 ⊃ 𝒬

We will now show that neither one is true—viz., we will show that

    𝒫 ⊃ 𝒬 ⊢_𝒲*  ¬𝒫 v 𝒬

and

    ¬𝒫 v 𝒬 ⊢_𝒲*  𝒫 ⊃ 𝒬

And we will do this by using only the inference rules of 𝒲*, which, as we’ve said is any one of 𝒲 but (mi). We shall begin with

    𝒫 ⊃ 𝒬 ⊢_𝒲*  ¬𝒫 v 𝒬

Consider a substitutional instance of 𝒫 ⊃ 𝒬:

    A ⊃ B

We shall show that

    A ⊃ B ⊢_𝒲*  ¬A v B

Proof:

1. A ⊃ B                                ⊢_𝒲*  ¬A v B

2.     ¬(¬A v B)                        Assume for RAA

3.         A                                 Assume for CP

4.         B                                 1, 3, MP

5.         B v ¬A                        4, Add

6.         ¬A v B                        5, Com

7.         ¬A v B • ¬(¬A v B)    6, 2, Conj

8.   ¬A v B                              2-7, RAA         

And now for

    ¬𝒫 v 𝒬 ⊢_𝒲*  𝒫 ⊃ 𝒬

Consider a substitutional instance of ¬𝒫 v 𝒬:

    ¬A v B

We shall show that

    ¬A v B ⊢_𝒲*  A ⊃ B

Proof:

1. ¬A v B      ⊢_𝒲*  A ⊃ B

2.     A             Assume for CP

3.     ¬¬A        2, DN

4.     B             1, 3, DS

5.  A ⊃ B       2-4, CP

What this shows is that, contra the Howard-Snyders and Wasserman, if their system of natural deduction is complete, viz. if it such that any sentence 𝒫 is a valid inference from a given set of premises, then there is a proof of 𝒫 from those same set of premises, it would still be complete without (mi).

References

Howard-Snyder, D. and F., and Wasserman, R. (2013). The Power of Logic (5^th Ed.) New York: McGraw Hill.