Contrapositive proof

Contraposition is a method where instead of proving a statement directly, one proves the logically equivalent statement.

If we want to prove a statement of the type "if A, then B", we can instead prove "if not B, then not A". Since the two statements are logically the same, the proof is valid.

 

The method is useful when it is difficult to go directly from A to B, but easier to argue backwards from not-B to not-A.

Contraposition thus provides an alternative way to reach the same result.

 

 

Procedure

A proof by contraposition can be divided into three steps:

 

1. Rewrite the statement "if A, then B" as "if not B, then not A".
2. Assume that the conclusion B does not hold.
3. Show logically that this implies that the assumption A also cannot hold.

 

 

Example 1

We want to prove: If \( \large n^2 \) is odd, then \( \large n \) is odd. Directly this may be difficult, but by contraposition it becomes:

 

If \( \large n \) is even, then \( \large n^2 \) is even.

 

Write \( \large n = 2a \). Then we get:

 

$$ \large n^2 = (2a)^2 = 4a^2 = 2(2a^2) $$

 

Thus \( \large n^2 \) is even. Therefore the contraposition is shown, and the original statement is proven.

 

 

Example 2

We want to prove: If an integer \( \large n \) is divisible by 6, then it is divisible by 3. The contraposition reads:

 

If \( \large n \) is not divisible by 3, then \( \large n \) is not divisible by 6.

 

Assume that \( \large n \) is not divisible by 3. This means that \( \large n = 3q + r \) with remainder \( \large r = 1 \) or \( \large r = 2 \). In both cases \( \large n \) is not divisible by 6, since a number must at least be divisible by 3 in order to be divisible by 6. Thus the statement is proven by contraposition.

 

 

Example 3

We want to prove: If a fraction \( \large \frac{a}{b} \) is reduced to lowest terms, then \( \large a \) and \( \large b \) are not both divisible by the same prime number. The contraposition reads:

 

If \( \large a \) and \( \large b \) are divisible by the same prime number, then the fraction \( \large \frac{a}{b} \) is not in lowest terms.

 

Assume that both \( \large a \) and \( \large b \) are divisible by a prime \( \large p \). Then we can write:

 

$$ \large a = p \cdot m \quad \text{and} \quad b = p \cdot n $$

 

The fraction then becomes:

 

$$ \large \frac{a}{b} = \frac{p \cdot m}{p \cdot n} = \frac{m}{n} $$

 

Thus the fraction can be reduced by \( \large p \), which shows that the original fraction was not in lowest terms. The contraposition is therefore shown, and the original statement is proven.

 

 

Proofs by contraposition are often shorter and more manageable than direct proofs when working with number-theoretic properties and divisibility. The technique gives another angle on a problem, but the result is logically exactly the same.