Proof by contradiction

A proof by contradiction is a method where one assumes the opposite of what one wants to show, and then demonstrates that this assumption leads to a contradiction. When a contradiction arises, it means that the assumption cannot be true, and thus the original statement must be correct.

 

The method is useful when a direct proof is difficult or unclear. Often a contradiction can clarify why a statement must hold, and the technique is used in many of mathematics' most famous proofs.

 

Procedure

A proof by contradiction can be described in three steps:

 

1. Assume that the statement you want to prove is false.
2. Use logical rules, definitions, and previous results to derive consequences of the assumption.
3. Show that you arrive at a contradiction, for example, that something must be both true and false at the same time.

 

 

Example 1

We want to prove that there is no odd number that is divisible by 2. Assume the opposite, that a number \( \large n \) is odd and divisible by 2. Then we can write:

 

$$ \large n = 2a+1 \quad \text{and} \quad n = 2b $$

 

Here \( \large n \) is written in two ways: both as odd and as even. This is impossible, since the two forms exclude each other. Thus the assumption is a contradiction, and the conclusion is that no odd numbers are divisible by 2.

 

 

Example 2

A classic proof by contradiction is that the square root of 2 is irrational. Assume the opposite, that \( \large \sqrt{2} \) is rational, that is, that it can be written as a fraction:

 

$$ \large \sqrt{2} = \frac{p}{q} $$

 

where \( \large p \) and \( \large q \) are integers without common factors. Rewriting this, we get:

 

$$ \large 2 = \frac{p^2}{q^2} \quad \Rightarrow \quad p^2 = 2q^2 $$

 

Thus \( \large p^2 \) is even, which means that \( \large p \) must be even. Let \( \large p = 2k \). Substitute into the equation:

 

$$ \large (2k)^2 = 2q^2 \quad \Rightarrow \quad 4k^2 = 2q^2 \quad \Rightarrow \quad q^2 = 2k^2 $$

 

It now follows that \( \large q \) is also even. But then \( \large p \) and \( \large q \) have a common factor 2, which contradicts the assumption that the fraction was reduced. Therefore \( \large \sqrt{2} \) cannot be rational.

 

 

Proofs by contradiction are one of the most powerful tools in mathematics. They are used not only to show results in number theory, but also in algebra, analysis, and logic, where a direct approach may be impossible. By turning the reasoning upside down, one can show the truth through the impossible.