# 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? – kiss my armpit Mar 16 '14 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. – Mike Miller Mar 16 '14 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. – David G Mar 17 '14 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. – Santiago Canez Mar 17 '14 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. – Jim Belk Mar 18 '14 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. Russel'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. – Santiago Canez Mar 17 '14 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? – Jim Belk Mar 17 '14 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. – Santiago Canez Mar 17 '14 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? – Pete L. Clark Mar 18 '14 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 '14 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.

-
@Jim Belk, you are misquoting Euclid in your first comment. – Matt F. Mar 17 '14 at 5:13
@Jim Belk: I rest my case. – Matt F. Mar 17 '14 at 5:26
@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. – Pete L. Clark Mar 18 '14 at 3:37
See for instance $\S$ 10.1 and 10.2 of math.uga.edu/~pete/4400FULL.pdf. In contemporary mathematics, issues of effectivity are extremely important. Phrasing every proof as a proof by contradiction works against this at least at an elementary/superficial level. (In other words: I am happy to give a proof by contradiction in, say, a graduate-level course, if I feel like it because I can then say: "Exercise: turn this proof into an algorithm" if that is in fact doable. At the undergraduate level this does not work as well.) – Pete L. Clark Mar 18 '14 at 3:41
@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. – Jim Belk Mar 18 '14 at 4:30

## 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.) – Pete L. Clark Mar 18 '14 at 5:01