Constructive Proof of Material Implication

  • #1
Hi,

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?

Thx.
 

Answers and Replies

  • #2
402
1
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]
 

Related Threads on Constructive Proof of Material Implication

Replies
2
Views
6K
Replies
1
Views
3K
  • Last Post
Replies
10
Views
821
Replies
4
Views
671
Replies
3
Views
34K
Replies
25
Views
5K
  • Last Post
Replies
10
Views
4K
Replies
4
Views
3K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
2
Views
4K
Top