Difference between revisions of "Proof by contrapositive"

From formulasearchengine
Jump to navigation Jump to search
en>Yobot
m (clean up, References after punctuation per WP:REFPUNC and WP:CITEFOOT using AWB (9345))
en>Anythingcouldhappen
(Reverted to revision 618184849 by Monkbot (talk). (TW))
 
Line 1: Line 1:
 
In [[logic]], the '''contrapositive''' of a [[indicative conditional|conditional]] statement is formed by negating both terms and reversing the direction of inference.  Explicitly,  the contrapositive of the statement "if A, then B" is "if not B, then not A."  A statement and its contrapositive are logically equivalent: if the statement is true, then its contrapositive is true, and vice versa.<ref>Regents Exam Prep, [http://www.regentsprep.org/Regents/math/geometry/GP2/Lcontrap.htm contrapositive] definition</ref>
 
In [[logic]], the '''contrapositive''' of a [[indicative conditional|conditional]] statement is formed by negating both terms and reversing the direction of inference.  Explicitly,  the contrapositive of the statement "if A, then B" is "if not B, then not A."  A statement and its contrapositive are logically equivalent: if the statement is true, then its contrapositive is true, and vice versa.<ref>Regents Exam Prep, [http://www.regentsprep.org/Regents/math/geometry/GP2/Lcontrap.htm contrapositive] definition</ref>
  
In mathematics, '''proof by contraposition''' is a [[rule of inference]] used in [[Mathematical proof|proofs]].<ref>[http://www.jimloy.com/math/proof.htm]</ref> This rule infers a conditional statement from its contrapositive.<ref>[http://zimmer.csufresno.edu/~larryc/proofs/proofs.contrapositive.html]</ref> In other words, the conclusion "if A, then B" is drawn from the single premise "if not B, then not A."
+
In mathematics, '''proof by contraposition''' is a [[rule of inference]] used in [[Mathematical proof|proofs]]. This rule infers a conditional statement from its contrapositive.<ref>[http://zimmer.csufresno.edu/~larryc/proofs/proofs.contrapositive.html Larry Cusick's (CSU-Fresno) How to write proofs tutorial]</ref> In other words, the conclusion "if A, then B" is drawn from the single premise "if not B, then not A."
  
 
==Example==
 
==Example==
Line 15: Line 15:
 
This latter statement can be proven as follows. Suppose ''x'' is not even. Then ''x'' is odd. The product of two odd numbers is odd, hence ''x''² = ''x''·''x'' is odd. Thus ''x''² is not even.
 
This latter statement can be proven as follows. Suppose ''x'' is not even. Then ''x'' is odd. The product of two odd numbers is odd, hence ''x''² = ''x''·''x'' is odd. Thus ''x''² is not even.
  
Having proved the contrapositive, we infer the original statement.<ref>{{cite book|first=J.|last=Franklin|authorlink=James Franklin (philosopher)|year=2011|title=Proof in Mathematics: An Introduction|url=http://www.maths.unsw.edu.au/~jim/proofs.html|publisher=Kew Books|location=Sydney|isbn=0-646-54509-4 |coauthors=A. Daoud}} (p. 50).</ref>
+
Having proved the contrapositive, we infer the original statement.<ref>{{cite book|first=J.|last=Franklin|authorlink=James Franklin (philosopher)|year=2011|title=Proof in Mathematics: An Introduction|url=http://www.maths.unsw.edu.au/~jim/proofs.html|publisher=Kew Books|location=Sydney|isbn=0-646-54509-4 |author2=A. Daoud }} (p. 50).</ref>
  
 
==Relation to proof by contradiction==
 
==Relation to proof by contradiction==

Latest revision as of 06:42, 16 October 2014

In logic, the contrapositive of a conditional statement is formed by negating both terms and reversing the direction of inference. Explicitly, the contrapositive of the statement "if A, then B" is "if not B, then not A." A statement and its contrapositive are logically equivalent: if the statement is true, then its contrapositive is true, and vice versa.[1]

In mathematics, proof by contraposition is a rule of inference used in proofs. This rule infers a conditional statement from its contrapositive.[2] In other words, the conclusion "if A, then B" is drawn from the single premise "if not B, then not A."

Example

Let x be an integer.

To prove: If x² is even, then x is even.

Although a direct proof can be given, we choose to prove this statement by contraposition. The contrapositive of the above statement is:

If x is not even, then x² is not even.

This latter statement can be proven as follows. Suppose x is not even. Then x is odd. The product of two odd numbers is odd, hence x² = x·x is odd. Thus x² is not even.

Having proved the contrapositive, we infer the original statement.[3]

Relation to proof by contradiction

Any proof by contrapositive can also be trivially formulated in terms of a Proof by contradiction: To prove the proposition , we consider the opposite, . Since we have a proof that , we have which arrives at the contradiction we want. So proof by contrapositive is in some sense "at least as hard to formulate" as proof by contradiction.

See also

References

  1. Regents Exam Prep, contrapositive definition
  2. Larry Cusick's (CSU-Fresno) How to write proofs tutorial
  3. {{#invoke:citation/CS1|citation |CitationClass=book }} (p. 50).

Template:Sister