### 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.