Proving the contrapositive

  • Thread starter tgt
  • Start date
  • #1
tgt
520
2

Main Question or Discussion Point

It can be proved by proof by contradiction. hence it is just a variant of it?
 

Answers and Replies

  • #2
283
3
Not really. Say you have a statement p, a proof by contradiction would be not p implies false. Contrapositive is a direct proof. Say you have the statement p imples q. To prove this via contradiction you assume p is true and q is false then derive a contradiction, to prove this via contrapositive you assume not q is true (i.e. q is false) and prove that this imples p is false.
 
  • #3
CRGreathouse
Science Advisor
Homework Helper
2,820
0
Statement: p ⇒ q
Proof by contradiction: Assume p and ¬q; prove ⊥.
Proof by contraposition: Assume ¬q; prove ¬p.

A proof by contraposition can be turned into a proof by contradiction by adding the step "p ∧ ¬p ⇒ ⊥". But proofs by contradiction don't need to prove ¬p as an intermediate step; they can prove contradiction in other ways. So proof by contradiction is stronger.

On the other hand, the more constrained proof by contraposition is considered a constructive technique, while proof by contradiction is always considered nonconstructive. So if you have a choice use contraposition.
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
41,793
922
If a statement is "P implies Q" then the contrapositive is "if not Q then not P" and is equivalent. Proving the contrapositive is a kind of proof by contradiction in which we assume the conclusion is false and arrive at a contradiction: "if not Q" is certainly assuming the conclusion is false and proving "not P" would give a contradiction with "if P".

However, "proof by contradiction" more general. You start with "if not Q" but only need to arrive at two statements that contradict one another. I have seen proofs in which the two contraditory statements have no apparent connection with the hypothesis, P.
 

Related Threads for: Proving the contrapositive

Replies
3
Views
1K
  • Last Post
Replies
7
Views
5K
Replies
2
Views
969
  • Last Post
Replies
2
Views
3K
Replies
9
Views
929
  • Last Post
Replies
3
Views
1K
Replies
7
Views
830
Top