# Good examples of proof by contradiction?

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).

• How about proving that the square root of 2 is an irrational number? Mar 16, 2014 at 15:43
• To add on to @WeirdstressFunction's comment, I don't know of a way to prove that $\sqrt 2$ is irrational that isn't a proof by contradiction.
– user37
Mar 16, 2014 at 16:07
• My discrete math professor proved If 3n+2 is odd, then n is odd by contradiction as an example. It's also able to be done using contrapositive, but she highlighted the differences by proving both ways. Mar 17, 2014 at 4:08
• @Mike, $\sqrt2$ is a root of $x^2-2$. Any rational root of this must have denominator dividing $1$ and numerator dividing $-2$, and so must be $\pm 1$ or $\pm 2$. None of these square to $2$, so none are $\sqrt2$ and hence $\sqrt2$ is not rational. Mar 17, 2014 at 4:14
• @Mike The square of a fraction in lowest terms is again in lowest terms, so a rational number is a perfect square if and only if its numerator and denominator are square numbers. Mar 18, 2014 at 4:48

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.

• Cantor's diagonal argument is NOT a proof by contradiction, it is a direct proof that no function from $\mathbb N$ to $\mathbb R$ is surjective. Similarly, your fifth example is actually a direct proof that no function from a set to its power set is surjective. Mar 17, 2014 at 4:16
• @SantiagoCanez I suppose you can phrase the proof that way, but it can also be phrased as a contradiction proof. In particular, you can certainly find lots of books written by perfectly good mathematicians in which the proof is described as a proof by contradiction. As with Matt F.'s comment below, I guess I don't see the point of purposely avoiding the contradiction argument. Is there some reason that contradiction proofs should be avoided at all costs? Mar 17, 2014 at 5:09
• Overuse of proof by contradiction leads students to believe that every proof should be a proof by contradiction, meaning that it becomes the first strategy they attempt eve though most of the time it makes things more confusing. I'm not saying that contradiction couldn't be used here, but that contradiction should only be used when it is necessary so that students develop better intuition as to how to approach proof writing. Mar 17, 2014 at 12:52
• I think that Cantor's argument really is a proof by contradiction. It is true that it brilliantly "constructs" an element not in the image of any given map $f: S \mapsto 2^S$...but the argument for that is by contradiction. What else? Mar 18, 2014 at 5:25
• do you mean Matt Fs answer on infinitude of primes? agree that Euclids proof can be regarded as a proof by contradiction that "the number of primes is finite". why is this less clear? to me they are exactly the same idea. maybe it is in the way it is being taught that confuses students.
– vzn
Mar 27, 2014 at 17:38

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.

• It is true that Euclid himself phrased the proof in a "direct" way, but only by stating the theorem as "every finite set of primes is not equal to the set of all primes". If you use Euclid's proof to prove the statement "the set of primes is infinite", then you are using a proof by contradiction. (Continued in the next comment.) Mar 17, 2014 at 4:54
• Moreover, I don't think this distinction is all that important: you can make almost any contradiction proof into a direct proof by changing the statement of the theorem. For example, it's easy to give a direct proof of the theorem "the square of any rational number is not equal to two", but what of it? Mar 17, 2014 at 4:55
• @Jim Belk: Euclid's proof gives a certain algorithm for, given any set of $N$ prime numbers, producing a prime number which is not in the set. Not every proof can be turned into an algorithm, and it is important to know which can. Now in fact any proof, no matter how indirect, of the infinitude of primes, leads to an algorithm for producing primes (namely trial factorization) but Euclid's proof gives an explicit upper bound on the size of the $n$th prime. This is the beginning of analytic number theory. Mar 18, 2014 at 3:37
• @PeteL.Clark That is a good point. Euclid's original proof is in some sense much more algorithmic that the typical indirect version that is given, and indeed phrasing it as a proof by contradiction obscures its effective nature, and leaves students without an algorithm for generating an infinite list of primes. Mar 18, 2014 at 4:30
• @PeteL.Clark your link does not seem to work anymore. Can you update? Jan 10, 2017 at 8:29

## 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.

• 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$.

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.

• "Recall that 'The square of an even number is even.' It implies that m is also even." Sorry, as a number theorist I have to frown at this. Try it with e.g. "a number divisible by 4" instead of "an even number". (Also, not to pick, but: it seems to me that there is only one circle with a given diameter is geometrically obvious and easier to verbally nail down in other ways: if you have the diameter then the midpoint is the center and half the length of the diameter is the radius. So you know the circle.) Mar 18, 2014 at 5:01
• @Pete L. Clark: reply to an old comment, to be sure, but perhaps they meant the square of only an even integer is even, so $m$ can't be odd? Literally I agree because in some conceivable universe every perfect square might be even in which case one would draw no conclusion, making me think they misspoke a bit sloppily. Sep 22, 2020 at 16:09

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:

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.

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.