Proof by Contradiction

You can prove that something is true by showing that not something being true would lead to a contradictory, inconsistent, absurd conclusion. Every proof-by-contradiction starts with the same rhetoric: Suppose not. Instead suppose to the contrary that …

Examples

Prove that \(\sqrt{2}\) is an irrational number.

An irrational number is defined to be a number that is not rational. It’s hidden behind vocabulary: the goal is to prove that \(\sqrt{2}\) is not a rational number. How can you directly prove something is not something else though? Suppose that it is, and reach a contradiction. “Suppose \(\sqrt{2}\) is rational, which means … ”

Prove that there are infinitely many prime numbers.

Assuming the contrary, you then get a finite list to work with. “Suppose there are only finitely many prime numbers \(p_1, p_2, \dotsc, p_n\) …”

Prove there is no polynomial function \(f\) of degree at least one with integer coefficients such that the outputs \(f(0), f(1), f(2), \dotsc\) are all prime.

It’s hard to directly prove the non-existence of anything; it’s easier to assume the existence of such a thing — in this case a non-constant polynomial \(f\) with integer coefficients for which \(f(0), f(1), f(2), \dotsc\) are all prime — that you can play with, searching for some inconsistency in the qualities of \(f.\) “Suppose to the contrary that there is such a polynomial \(f(x) = a_nx^n + \dotsb a_1x + a_0\) …”