Good examples of proof by contradiction?

Question

In later courses on automata theory, many students just seem incapable of getting a proof that a language isn't regular right, be it using the pumping lemma (see also the many questions on the matter on http://math.stackexchange.com) or the (often easier) use of closure properties.

As I am also teaching a first course in discrete matematics, were we go over proof techniques, I have tried (rather unsuccessfully, regrettably) to get the idea across. I would like to have more easy to grasp examples where the technique is natural (and needed, contrived examples just lead to "the prof is off his rocker again, this is trivial to do by ...", and so are more a distraction than a help).

Answer 1

Here are some good examples of proof by contradiction:

1. Euclid's proof of the infinitude of the primes. (Edit: There are some issues with this example, both historical and pedagogical. See Mike F.'s answer and the ensuing discussion.)

2. The famous proof that $\sqrt{2}$ is irrational. (I don't particularly like this one---there are better ways of proving this. See my comment above.)

3. The sum of a rational number and an irrational number is irrational.

4. Cantor's diagonal argument that $\mathbb{R}$ is uncountable is a proof by contradiction. (Edit: As Santiago Canez points out in the comments, this example and the next are perhaps better stated as direct proofs.)

5. Similarly, there's the proof that there is no bijection from a set $X$ to the power set of $X$.

6. Russell's proof that there exists no set of all sets.

7. The proof of Gödel's incompleteness theorem.

8. This Math Stack Exchange post has a nice simple proof that $\displaystyle\sum_{k=1}^n \frac1k$ is never an integer for $n\geq 2$.

9. There are lots of basic statements about Diophantine equations that can be proven by contradiction. For example, the statement "the equation $4x^2-y^2 = 1$ has no integer solutions for $x$ and $y$" has a simple contradiction proof. (Factor the left side.)

10. This Math Stack Exchange post has a simple proof that there exist infinitely many primes $p$ such that $p+2$ is not prime.

11. The proof of Eisenstein's criterion for irreducible polynomials is a proof by contradiction. There are many simpler statements along these lines (e.g. proving that specific polynomials have no integer roots) that can be proved by contradiction.

12. This Math Stack Exchange post has a simple proof using the trace that if $A$ and $B$ are $n\times n$ matrices and $AB-BA = B$, then $B$ cannot be invertible.

13. There's a simple proof by contradiction that there does not exist a continuous function $f\colon\mathbb{R}\to\mathbb{R}$ so that $f(f(x))=-x$. (It must be a bijection, so it's either increasing or decreasing, so . . .)

14. You can prove by contradiction that there's no embedding of the complete graph $K_5$ in the plane using Euler's formula.

15. The solution to the Seven Bridges of Königsberg problem is essentially a proof by contradiction.

16. Twenty five boys and twenty five girls sit around a table. Prove that it is always possible to find a person both of whose neighbors are girls.

Answer 2

Many of Jim Belk's answers are good. But let me state for the record, because it always comes up:

Euclid's proof of the infinitude of primes is not a proof by contradiction.

Look at Euclid's text, e.g. the translation here: "Prime numbers are more than any assigned multitude of prime numbers." The proof is constructive.

I have found that proving this theorem by contradiction confuses students. I would encourage others to prove it constructively instead. In any case: do not attribute the proof by contradiction to Euclid.

Answer 3

I would like to use this as an opportunity to make an important distinction.

Proof by contradiction is an argument of the form:

Assume $\neg p$

Argue a contradiction under this assumption.

Conclude $p$.

Proof of negation is an argument of the form

Assume $p$

Argue a contradiction under this assumption.

Conclude $\neg p$

I learned about the difference from Andrej Bauer here:

http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/

A classical mathematician might not distinguish these proofs, because they think $\neg (\neg p) \equiv p$, but a constructive mathematician will make this distinction.

I would like to go through Jim Belk's list to illustrate the difference:

1. Infinitude of primes. As noted, this can be phrased as a proof by contradiction, but it can also be viewed as a completely constructive result: given a list of prime numbers, it gives an algorithm for constructing a new prime which is not in the list.

2. Irrationality of $\sqrt{2}$. This is proof of negation. The definition of "irrational" is "not rational". You prove the negation of "$\sqrt{2}$ is rational" by assuming it is and obtaining a contradiction.

3. Sum of a rational and irrational is irrational. Again, this is proof of negation.

4. Cantor's diagonalization argument: To prove there is no bijection, you assume there is one and obtain a contradiction. This is proof of negation, not proof by contradiction. I will point out that, similar to the infinitude of primes example, this can be rephrased more constructively. Given an injection $\mathbb{N} \to \mathbb{R}$, this argument explicitly produces an element of $\mathbb{R}$ which is not in the image.

5. No bijection from $X$ to $\mathcal{P}(X)$: similar remarks to Cantor's argument apply. As usually phrased it is proof of negation, and it can be rephrased more constructively as a recipe which takes an injection from $X$ to $\mathcal{P}(X)$ and produces an element of $\mathcal{P}(x)$ which is not in the image.

6. Russel's proof that there is no set of all sets. I am not sure this counts as a formal argument. It is more of a metamathematical theorem, that we should not attempt to construct a formal system which allows unbounded set formation.

7. $\vdots$

I think all of the other examples are also proof of negations, rather than proof by contradiction. Many of the theorems can be rephrased more powerfully without using negation in the theorem statement at all, and they have direct proofs in this case. None of them, that I can see, can both be rephrased without negation in the statement and require proof by contradiction, rather than direct proof, to demonstrate them.

Usually proof by contradiction can be avoided, and doing so creates direct proofs which are more constructive. Even for the non-constructive mathematician this is good mathematical hygiene: the intermediate results proven during a proof by contradiction are useless to your later work (they only hold under a false premise), while the intermediate results obtained in the direct proof are all immediately useful in real circumstances.

Proof of negation is unavoidable though. We can actually define $\neg p$ as $p \implies F$. If you are trying to prove that a certain number is not rational, we must show that assuming it is rational leads to contradiction.

Answer 4

Example 1

Question:

Prove that there is only one circle with $AB$ as its diameter.

Assumption:

Assume that there are 3 circles $C_1$, $C_2$, and $C_3$ passing through the points $A$ and $B$. $C_1$ and $C_2$ are concentric and $C_1$ and $C_3$ are not concentric. $C_1$ and $C_2$ have different radii and $C_3$ has any radius. Let $C_1$ be on the midpoint of $AB$ such that $AB$ is its diameter.

Contradicting Arguments:

• As $C_1$ and $C_2$ have different radii, points $A$ and $B$ cannot be on the circle $C_2$.

• As $C_3$ is not on the middle of $AB$, $AB$ cannot be its diameter.

Conclusion:

So there is only one circle $C_1$ with $AB$ as its diameter.

Example 2

Question:

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

Assumption:

Let $\sqrt 2$ be a rational number. So it can be represented as $\sqrt{2}=\frac{m}{n}$ where $m$ and $n$ are natural numbers without common factors other than $1$.

Contradicting Arguments:

Squaring both sides, we get \begin{align} 2 &=\frac{m^2}{n^2}\\ m^2 &= 2n^2 \end{align}

Because $m^2$ is a multiple of $2$ then $m^2$ is an even number. Recall that

The square of an even number is even.

it implies that $m$ is also even. Let $m=2k$ where $k$ is any natural number. Substituting it for $m$, we get \begin{align} (2k)^2 &=2n^2\\ 4k^2 &= 2 n^2\\ n^2 &= 2k^2 \end{align}

With the same reasoning, $n$ is even. As both $m$ and $n$ are even numbers, 2 becomes their common factors so it contradicts the assumption that they have no common factors other than 1.

Conclusion:

$\sqrt 2$ cannot be represented as a ratio of two natural numbers without common factor other than 1. It implies that $\sqrt 2$ is irrational.

Answer 5

Claim: The function $f:\mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^3+x-2$ has one and only one root.

Proof 1 (by contradiction)

We can see that $f(1) = 0$ so $f$ has at least one root. Assume the the contrary that $f$ has an additional root $z$. Then, by the mean value theorem for derivatives, there is a $c$ between $1$ and $z$ so that $f'(c) = 0$. However, $f'(c) = 3c^2 + 1 > 1$. We have arrived at a contradiction, so the hypothesis that $f$ has more than $1$ root false. Thus $f$ has one and only one root.

Proof 2 (direct proof)

Let $x$ be a root.

\begin{align} & \hphantom{fdsfsf} x^3 + x - 2 = 0\\ &\iff (x-1)(x^2+x+2) =0\\ &\iff (x-1)\left[(x+\frac{1}{2})^2 + \frac{7}{4}\right] = 0\\ &\iff x-1 = 0\\ &\iff x= 1 \end{align}

We can justify the equivalence of the third and fourth line by noting that $\left[(x+\frac{1}{2})^2 + \frac{7}{4}\right] \geq \frac{7}{4}$

Answer 6

Something more trivial could be the following one: $$a^2=0\Rightarrow a=0.$$ Assume that $a^2=0$ and at the same time $a\neq0$ for some $a\in\mathbb{R}.$ Then, there exists $a^{-1}\in\mathbb{R}$ so: $$a^2=0\Rightarrow a^{-1}a^2=0\Rightarrow a=0,$$ so you indeed need both $a^2=0$ as well as $a\neq0$ to arrive to a contradiction.

Answer 7

I think proving a variant of the Pigeonhole Principle by contradiction is a nice example, because it's simpler to prove it by contradiction than to prove it constructively (intuitively, a constructive proof has to do more work, because it must determine which hole has two pigeons).

Theorem: given $n+1$ integers in the range $1$ to $n$ inclusive, some two of them must be equal.

Proof by contradiction: suppose none of them are equal, then you have $n+1$ distinct integers in the range $1$ to $n$, a contradiction (a set of size $n+1$ can't be a subset of a set of size $n$).

Constructive proof, by induction on $n$: if two of the numbers are equal to $n$, then you're done. Otherwise, reduce to $n$ numbers in the range $1$ to $n-1$, by throwing away the largest number (the largest number is the only possible occurrence of the number $n$). Now you have $n$ numbers in the range $1$ to $n-1$, so some two of them are equal by induction (base case: if you have two numbers in the range $1$ to $1$, then clearly they're equal).

Possible objection to this example: the proof by contradiction depends on a lemma, namely $A \subseteq B \implies |A| \le |B|$ for finite sets of integers. This lemma seems to be about as obvious as the Pigeon Hole Principle itself, so it may be unfair to assume it...