Monday, December 18, 2017

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 𝒬  
    ¬𝒫 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 𝒬
    ¬𝒫 v 𝒬 βŠ¬π’²*  𝒫 βŠƒ 𝒬
We will now show that neither one is trueβ€”viz., we will show that
    𝒫 βŠƒ 𝒬 βŠ’π’²*  ¬𝒫 v 𝒬
    ¬𝒫 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
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
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).
Howard-Snyder, D. and F., and Wasserman, R. (2013). The Power of Logic (5th Ed.) New York: McGraw Hill.


Post a Comment

<< Home

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 United States License.