Next: Taxonomy of proof: counterexample Up: Taxonomy: techniques useful in Previous: Taxonomy of Proof: structural

## Taxonomy of proof: contrapositive

CONTRAPOSITIVE IS A QUITE POWERFUL method in proof: it allows you to attack a proof backwards. Instead of going from the assumptions and trying to derive the result, you start by assuming the result is false and show that this violates one of the assumptions. This makes use of the logical law of contrapositive:

 IF A THEN B is equivalent to IF NOT B THEN NOT A

Since we are assuming that the result is not true and end up by contradicting our assumptions, this is a kind of proof by contradiction known as proof by contrapositive.2We used it back in Section 1 for the very first proof; it is used quite a lot. It gives a lot of flexibility in IF AND ONLY IF, because it allows us to interpret the forward'' and backward'' part of the proof in several different ways:

By applying the law of contrapositive, it is fairly easy to see that all three forms are in fact equivalent. This flexibility in proof methods is yet another reason to prefer the two-step approach to if and only if proofs to the monolithic approach.

Next: Taxonomy of proof: counterexample Up: Taxonomy: techniques useful in Previous: Taxonomy of Proof: structural
Craig Silverstein 2005-08-27