Proof by contradiction

The method relies on the fact that a statement and its negation cannot both be true. If negating \(p\) leads to an absurdity, then \(p\) cannot be false. The absurdity is usually a statement of the form «\(r\) and not \(r\)»: for example, a number that is even and odd at once, or a fraction in lowest terms that turns out reducible.

The classic example is the irrationality of \(\sqrt2\). Assume \(\sqrt2=a/b\) with \(a/b\) in lowest terms; then \(a^2=2b^2\), so \(a\) is even, \(a=2c\) and \(b^2=2c^2\), so \(b\) is even too. But then the fraction was not in lowest terms. Another is Euclid's: if the primes were \(p_1,\dots,p_n\), the number \(N=p_1\cdots p_n+1\) is divisible by none of them, so it has a prime factor outside the list.

For an implication \(p\Rightarrow q\), assume \(p\) together with \(\neg q\), since that is the negation of the implication. Do not confuse this with the contrapositive, which proves \(\neg q\Rightarrow\neg p\) directly and looks for no absurdity.

Use it when the statement says something does not exist or is impossible («there is no», «is irrational», «are infinite»), because negating it gives a concrete object to work with.