Constructive Proof of Material Implication

This is because the first implication is equivalent to the classical law of excluded middle:\left(p\rightarrow q\right)\equiv\left(\neg p \vee q\right)In summary, it is not possible to constructively prove the material implication replacement rule using only intuitionistic rules in a natural deduction system, as it is not intuitionistically valid. Its proof would require a non-intuitionistic rule, such as the conditional proof or the law of excluded middle.
  • #1
Hugo Ferreira
1
0
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.
 
Physics news on Phys.org
  • #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]
 

Related to Constructive Proof of Material Implication

1. What is constructive proof of material implication?

Constructive proof of material implication is a method used in logic and mathematics to show that a statement implies another statement. It is a way of demonstrating that if one statement is true, then another statement must also be true.

2. How is constructive proof of material implication different from other forms of proof?

Unlike traditional proof methods, constructive proof of material implication does not rely on assuming the opposite of the statement and showing a contradiction. Instead, it focuses on constructing a direct path from the initial statement to the final statement.

3. What are some common strategies used in constructive proof of material implication?

There are several techniques that can be used in constructive proof of material implication, such as proof by cases, proof by contradiction, and proof by induction. These strategies involve breaking down the problem into smaller parts and showing that each part implies the next, ultimately leading to the desired conclusion.

4. Can constructive proof of material implication be used in real-world applications?

Yes, constructive proof of material implication is a fundamental tool in logic and mathematics and has practical applications in fields such as computer science, engineering, and physics. It allows for the logical deduction of consequences and helps in problem-solving and decision-making.

5. Are there any limitations to constructive proof of material implication?

Constructive proof of material implication may not always be the most efficient or straightforward method of proof, and it may not be applicable to all types of statements. Additionally, it relies on the use of axioms and logical rules, which can sometimes be subjective or debatable.

Similar threads

I Why are the inverse and converse of an implication not equivalent?
    • Set Theory, Logic, Probability, Statistics
2
Replies
39
Views
3K
I How to find this equivalent of the material conditional?
    • Set Theory, Logic, Probability, Statistics
Replies
3
Views
382
I On a proof of the converse of the supporting hyperplane theorem
    • General Math
Replies
9
Views
620
Reusability of nuts and tapped holes + Choosing the right material
    • Mechanical Engineering
Replies
3
Views
186
B One thing I don't understand about Cantor's diagonal argument
    • Set Theory, Logic, Probability, Statistics
2
Replies
55
Views
5K
Changing the Statement Combinatorial proofs & Contraposition
    • Math Proof Training and Practice
Replies
5
Views
903
I Understanding Cantor's Diagonalization Proof: A Brief Explanation
    • Set Theory, Logic, Probability, Statistics
Replies
17
Views
2K
I Adding random numbers: Tolerance analysis
    • Set Theory, Logic, Probability, Statistics
Replies
11
Views
626
MHB Formal proof using the deduction theorem
    • Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
I Superconductivity energy saved v Cooling/Heating energy loss
    • Other Physics Topics
Replies
4
Views
683

Hot Threads

Recent Insights

Back
Top