The difference between proof by contrapositive and contradiction
can be a bit confusing, at least it was for me at first. A proof by
contradiction is used by assuming the hypothesis to be true and the
conclusion to be false. We then show that this causes and
contradiction and therefore the initial conclusion is true, and thus
prove its legitimacy.
Proof by contrapositive starts the same as proof by contradiction, in
that we assume the conclusion to be false, but we then prove that
the hypothesis is false. This works because of the equivalence
between `If A, then B` and `If not A, then not B`.
Example (Contrapositive):
Prove that for all integers, if 5x+3 is even, then x is an odd
number. For a contrapositive proof we will assume the hypothesis is
false and prove that the conclusion is also false.
1. Suppose x is not odd.
2. If x is not odd then x is even.
3. If x is even then x can be rewritten as x=2a for some
integer a.
4. Then we can say that 5x+3=5(2a)
+3=10a+3=10a+2+1=2(5a+1)+1.
5. Since a is an integer then 5a+1 is an integer.
6. Therefore 5x+3=2b+1where b is an integer.
7. Consequently 5x+3 is odd, the definition of an odd integer
being 2k+1 where k is an integer.
8. Therefore 5x+3 is even.
