Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Constructive Proof of Material Implication

  1. Jun 3, 2010 #1

    I'm struggling to find a constructive proof (through natural deduction) of the material implication replacement rule (i.e., that (a => b) <=> (~a \/ b). I believe the only possible way would be through contradiction, but I can't seem to get to it. Is it even possible?

  2. jcsd
  3. Jun 4, 2010 #2
    IF by "constructive proof" in a natural deduction system you mean a proof using only intuitionistic rules, then it's not possible: the implication

    [tex]\left(p\rightarrow q\right)\rightarrow\left(\neg p \vee q\right)[/tex]

    is not intuitionistically valid, whereas the reverse one:

    [tex]\left(\neg p \vee q\right)\rightarrow\left(p\rightarrow q\right)[/tex]

    is, so this one may be proved only with intuitionistic rules.

    The first implication is only classically valid, so its proof must use a non-intuitionistic rule, like

    [tex]\Phi,\neg\alpha\vdash\bot \Rightarrow \Phi\vdash\alpha[/tex]
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook