In this post we’ll expand our toolbox of proof techniques by adding the proof by contradiction. We’ll also expand on our knowledge of functions on sets, and tackle our first nontrivial theorem: that there is more than one kind of infinity.

## Impossibility and an Example Proof by Contradiction

Many of the most impressive results in all of mathematics are proofs of impossibility. We see these in lots of different fields. In number theory, plenty of numbers cannot be expressed as fractions. In geometry, certain geometric constructions are impossible with a straight-edge and compass. In computing theory, certain programs cannot be written. And in logic even certain mathematical statements can’t be proven or disproven.

In some sense proofs of impossibility are hardest proofs, because it’s unclear to the layman how anyone could prove it’s *not* possible to do something. Perhaps this is part of human nature, that nothing is too impossible to escape the realm of possibility. But perhaps it’s more surprising that the main line of attack to prove something is impossible is to *assume* it’s possible, and see what follows as a result. This is precisely the method of proof by contradiction:

Assume the claim you want to prove is false, and deduce that something obviously impossible must happen.

There is a simple and very elegant example that I use to explain this concept to high school students in my guest lectures.

Image you’re at a party of a hundred people, and any pair of people are either mutual friends or not mutual friends. Being a mathematical drama queen, you decide to count how many friends each person has at the party. You notice that there are two people with the *same number of friends*, and you wonder if it will always be the case for any party. And so the problem is born: prove or disprove that at every party of people, there exist two people with the same number of friends at the party.

If we believe this is true, and we can’t seem to find a direct proof, then we can try a proof by contradiction. That is, we assume that there are *not* two people with the same number of friends. Equivalently, we can assume that everybody has a distinct number of friends. Well what could the possibilities be? On one hand, if there are people at the party, then the minimum number of friends one could have is zero (if you’re quite lonely), and the maximum is (if you’re friends with everybody). So there are distinct numbers, and people, and everyone has to have a different number. That means someone has to have zero friends, and someone has to be friends with everybody. But this can’t possibly be true: if you’re friends with everyone (and we’re only counting mutual friendships) then nobody can be friendless. Thus, we have arrived at a contradiction, and our original assumption must have been incorrect. That is, every party has two people with the same number of friends at the party.

There are certainly other proofs of this fact (I know of a direct proof which is essentially the same proof as the one given above), and there are more mathematical ways to think about the problem. But this is a wonderful example of a proof which requires little else than the method of contradiction.

## A Reprise on Truth Tables, and More Examples

Just as with our post on contrapositive implication, we can analyze proof by contradiction from the standpoint of truth tables. Recall the truth table for an implication :

p q p->q T T T T F F F T T F F T

We notice that an implication can only be false if the hypothesis is true *and** *the consequence is false. This is the motivation for a proof by contradiction: if we show this case can’t happen, then there’s no other option: the statement must be true. In other words, if supposing “p and not q” is true implies something which we know to be false, then by the very same truth table argument it must be that either “q” is true or “p” is false. In any of these cases “p implies q” is true.

But all of this truth table juggling really takes us away from the heart of the method. Let’s do some proofs.

First, we will prove that the square root of 2 is not a rational number. That is, we are proving the statement that if is a number such that , then it cannot be true that where are integers.

Suppose to the contrary (this usually marks the beginning of a proof by contradiction) that is a ratio of integers. Then we can square both sides to get , and rearrange to arrive at . Now comes the tricky part: if a number is a divisor of , then its square must divide ; this is true of all square numbers. In particular, it must be the case that the largest power of 2 dividing any square number is *even* (and counts as an even power). Now in the equation the right hand side is a square, so the largest power of two dividing it is even, and the right hand side is two times a square, so the largest power of 2 dividing it is *odd* (2 times an even power of 2 gives an odd power of two). But the two sides are equal! They can’t possibly have *different* largest powers of 2 dividing them. So we have arrived at a contradiction, and it must not be the case that is rational.

This is quite a nice result, and a true understanding of the proof comes when you see why it fails for numbers which actually do have rational square roots (for instance, try it for the square root of 9 or 36/25). But the use of the method is clear: we entered a magical fairy land where the square root of 2 is a rational number, and by using nothing but logical steps, we proved that this world is a farce. It cannot exist.

Often times the jump from “suppose to the contrary” to the contradiction requires a relatively small piece of insight, but in other times it is quite large. In our example above, the insight was related to divisors (or prime factorizations) of a number, and these are not at all as obvious to the layman as our “having no friends” contradiction earlier.

For instance, here is another version of the square root of two proof, proved by contradiction, but this time using geometry. Another example is on tiling chessboards with dominoes (though the application of the proof by contradiction in this post is more subtle; can you pick out exactly when it’s used?). Indeed, most proofs of the fundamental theorem of algebra (these are much more advanced: [1] [2] [3] [4]) follow the same basic recipe: suppose otherwise, and find a contradiction.

Instead of a obviously ridiculous statement like “1 = 0″, often times the “contradiction” at the end of a proof will contradict the original hypothesis that was assumed. This happens in a famous proof that there are infinitely many prime numbers.

Indeed, if we suppose that there are finitely many prime numbers, we can write them all down: . That is, we are assuming that this is a list of *all* prime numbers. Since the list is finite, we can multiply them all together and add 1: let . Indeed, as the reader will prove in the exercises below, every number has a prime divisor, but it is not hard to see that no divides . This is because no matter what some number is, no number except 1 can divide both and (one can prove this fact by contradiction if it is not obvious), and we already know that all the divide . So must have some prime divisor which was not in the list we started with. This contradicts that we had a complete list of primes to begin with. And so there must be infinitely many primes.

Here are some exercises to practice the proof by contradiction:

- Prove that the base 2 logarithm of 3 is irrational.
- More generally that is irrational if there is any prime dividing but not , or vice versa.
- Prove the fundamental theorem of arithmetic, that every natural number is a product of primes (hint: inspect the smallest failing example).

## A Few More Words on Functions and Sets

Last time we defined what it means for a function on sets to be injective: different things in get mapped to different things in . Indeed, there is another interesting notion called *surjectivity*, which says that “hits” everything in by something in .

**Definition: **A function is *surjective* if for every element there is an for which . A surjective function is called a *surjection*. A synonym often used in place of surjective* *is *onto.*

For finite sets, we use surjections to prove something nice about the sets it involves. If is a surjection, then has at least as many elements as . The reader can prove this easily by contradiction. In our previous post we proved an analogous proposition for injective functions: if is injective, then there are at least as many elements of as there are of . If we combine the two notions, we can see that and have exactly the same size.

**Definition: **A function which is both injective and surjective is called a *bijection*. The adjectival form of bijection is *bijective*.

So for finite sets, if there exists a bijection , then and have the same number of elements. The converse is also true, if two finite sets have the same size one can make a bijection between them (though a strictly formal proof of this would require induction, which we haven’t covered yet). The main benefit of thinking about size this way is that it extends to infinite sets!

**Definition:** Two arbitrary sets are said to have the same *cardinality* if there exists a bijection . If there is a bijection then is said to have *countably infinite cardinality*, or simply *countably infinite*. If no such bijection exists (and is not a finite set), then is said to be *uncountably infinite.*

So we can say two infinite sets have the same cardinality if we can construct a bijection between them. For instance, we can prove that the even natural numbers have the same cardinality as the regular natural numbers. If is the set of even natural numbers, just construct a function by sending . This is manifestly surjective and injective (one can prove it with whatever method one wants, but it is obviously true). A quick note on notation: when mathematicians want to define a function without giving it a name, they use the “maps to” arrow . The reader can think of this as the mathematician’s version of lambda expression. So the above map would be written in python: lambda x: 2*x.

So we have proved, as curious as it sounds to say it, that there are just as many even numbers as not even numbers. Even more impressive, one can construct a bijection between the natural numbers and the *rational* numbers. Mathematicians denote the latter by , and typically this proof is done by first finding a bijection from and then from . We are implicitly using the fact that a composition of two bijections is a bijection. The diligent reader has already proved this for injections, so if one can also prove it for surjections, by definition it will be satisfied for bijections.

## Diagonalization, and a Non-Trivial Theorem

We now turn to the last proof of this post, and our first non-trivial theorem: that there is no bijection between the set of real numbers and the set of natural numbers. Before we start, we should mention that calling this theorem ‘non-trivial’ might sound insulting to the non-mathematician; the reader has been diligently working to follow the proofs in these posts and completing exercises, and they probably all feel non-trivial. In fact, mathematicians don’t use trivial with the intent to insult (most of the time) or to say something is easy or not worth doing. Instead, ‘trivial’ is used to say that a result follows naturally, that it comes from nothing but applying the definitions and using the basic methods of proof. Of course, since we’re learning the basic methods of proof nothing can really be trivial, but if we say a theorem is *non-trivial *that means the opposite: there is some genuinely inspired idea that sits at the focal point of the proof, more than just direct or indirect inference. Even more, a proof is called “highly non-trivial” if there are multiple novel ideas or a menagerie of complicated details to keep track of.

In any case, we have to first say what the real numbers are. Instead we won’t actually work with the entire set of real numbers, but with a “small” subset: the real numbers between zero and one. We will also view these numbers in a particular representation that should be familiar to the practicing programmer.

**Definition:** The set of is the set of all infinite sequences of zeroes and ones, interpreted as the set of all binary decimal expansions of numbers between zero and one.

If we want to be rigorous, we can define an *infinite sequence* to either be an infinite tuple (falling back on our definition of a tuple as a set), or we can define it to be a function . Taking the latter view, we add one additional piece of notation:

**Definition:** An *infinite binary sequence* is a function where we denote by the value .

So now we can state the theorem.

**Theorem:** The set of infinite binary sequences is uncountably infinite. That is, there is no bijection .

The proof, as we said, is non-trivial, but it starts off in a familiar way: we assume there is such a bijection. Suppose to the contrary that is a bijection. Then we can list the values of in a table. Since we want to use for all of the values of , we will call

This gives us the following infinite table:

Now here is the tricky part. We are going to define a *new* binary sequence which we can guarantee does not show up in this list. This will be our contradiction, because we assumed at first that this list consisted of all of the binary sequences.

The construction itself is not so hard. Start by taking for all . That is, we are using all of the diagonal elements of the table above. Now take each and replace it with its opposite (i.e., flip each bit in the sequence, or equivalently apply to each entry). The important fact about this new sequence is it differs from every entry in this table. By the way we constructed it, no matter which $lateex n$ one chooses, this number differs from the table entry at digit (and perhaps elsewhere). Because of this, it can’t occur as an entry in the table. So we just proved our function isn’t surjective, contradicting our original hypothesis, and proving the theorem.

The discovery of this fact was an important step forward in the history of mathematics. The particular technique though, using the diagonal entries of the table and changing each one, comes with a name of its own: the *diagonalization argument*. It’s quite a bit more specialized of a proof technique than, say, the contrapositive implication, but it shows up in quite a range of mathematical literature (for instance, diagonalization is by far the most common way to prove that the Halting problem is undecidable). It is worth noting diagonalization was not the first known way to prove this theorem, just the cleanest.

The fact itself has interesting implications that lends itself nicely to confusing normal people. For instance, it implies not only that there is more than one kind of infinity, but that there are an *infinity of *infinities. Barring a full discussion of how far down the set-theory rabbit hole one can go, we look forward to next time, when we meet the final of the four basic methods of proof: proof by induction.

Until then!

This post suffers from the usual confusion about the difference between “proof by contradiction” and “proof of negation”. Andrej Bauer has a nice post about the distinction here: http://math.andrej.com/2010/03/29/proof-of-negation-and-proof-by-contradiction/

The short of it is, proving a negative statement is not a proof by contradiction, in the sense that it is still a constructively valid proof. A proof by contradiction is when you prove a positive statement by assuming its negation.

LikeLike

This comment suffers from the usual confusion about the difference between “studying the properties of an axiomatic logical system” and “doing mathematics.” Claiming these aren’t proofs by contradiction because someone defined it as such is a vapid philosophical debate.

LikeLike

It’s not vapid philosophical debate. The point is that they are distinct ideas, and conflating these two ideas easily leads to confused and muddled proofs. Gowers’ post that sparked Andrej’s reply was confusedly musing about a “direct” proof of the irrationality of sqrt(2). There is no such thing — irrationality is a negative property and so in the end can only be proven by the “proof of negation” technique.

Clarifying this distinction gives one a better understanding of the structure of proofs and how approach proofs — and that, I believe, is the whole point of your original post.

LikeLike

The point is to teach people how to do proofs, and since the proof technique is identical regardless of whether you call it contradiction or “negation,” it’s actually

moreconfusing to point it out. Everyone who actually does mathematics (and doesn’t specifically study intuitionistic logic) doesn’t care about the distinction, because double negations cancel and that’s all there is to it. Nothing about that implicit step makes a proof confused or muddled. It just shows that intuitionistic logic is too stupid to recognize an obvious equivalence of statements. This is a typical thing that happens in logic all the time: intentionally simplified models and axiomatic systems are too dumb to do natural things. It’s not a deep metamathematical insight; it’s a curiosity for logicians to tinker with. And it certainly has no place in a students’ first glimpse at proof technique.LikeLike

Knowing this distinction simplifies the process of proving something for the simple reason that if you are proving a negative statement, you *must* use “proof of negation”. However, if you are proving a positive statement, most of the time you in fact should not use proof by contradiction. In that sense, knowing the distinction is very useful to both learned mathematicians and students.

LikeLike

I don’t think you understand: the distinction only exists in a particular logical framework that nobody uses to actually do mathematics. Sure one might prefer constructive proofs of existence to relate theorems to algorithms, but there is never a time when proving a theorem by contradiction is a

badthing.LikeLike

“If there is a bijection f : N -> X then X is said to have countably infinite cardinality, or simply countably infinite. If no such bijection exists, then X is said to be uncountably infinite.”

Knowing that there isn’t a bijection between N and X only tells us that the two sets have different cardinalities. Don’t we still have to prove that there isn’t a surjection between N and X, before we can say that X is uncountably infinite?

LikeLike

Yes, of course. Thanks for catching that.

LikeLike

Hey j2kun, thanks for this post.

I think I found I typo in “Now in the equation 2q^2 = p^2 the right hand side is a square, so the largest power of two dividing it is even, and the right hand side is two times a square, so the largest power of 2 dividing it is odd”

Did you mean “… and the left hand side is two times a square …”?

LikeLike

Yes of course. No matter how easy a proof is, it’s even easier to make a mistake in writing it down :)

LikeLike

Hi Jeremy,

very nice primers, indeed ! Thanks for your work…

Some typos/suggestions :

* “there is no bijection between the set of real numbers is uncountably infinite”: looks like you changed your mind in the middle of the sentence, as how to express it :)

* “it differs from entry f(n) precisely at digit n”: I would rather write “at least” than “precisely”, which seem to imply that it does not differ elsewhere (which we don’t know for sure, nor care about)

LikeLike

Great article. Thanks!

I am confuse about the Diagonalization. English isn’t my mother language and I’m poor at it, so I hope I can express my question correctly.

Let S be the set of string, where each character comes from a finite set, e.g {a, b}.

It can be show that there exists a bijection f:N->S, just enumerate it as follow:

f(1) = a

f(2) = b

f(3) = aa

f(4) = ab

f(5) = ba

….

But with diagonlization, it can show that there’s no such bijection f:N->S exists, using the same trick when proving no bijection f:N->R exist.

suppose there exist such bijection, then we write it down as an infinite table, as what f:N->[0,1] does.

f(1) = s11 s12 …

f(2) = s21 s22 …

…

If len( f(i) ) = n, then sij(j>n) is an empty character ε. For f(1)=a,

s11=a s12=ε …

and so on.

Now we can define a new string Q that does not in this table, with diagonalization:

Qi = a if sii=b

b if sii=a

a or b if sii=ε

just as what we does in disprove f:N->[0,1] exists.

So we come to a contradition. We can find a bijection, while showing that there is no such bijection.

Could you please tell me What’s going wrong ?

I have tried this on national number f:N->N originally. Pepole replied that a specific natural number can’t be an infinite sequence, while real number can. So I change to string, which doesn’t have such numeric restriction. The Turning Halting Problem are also disproved with string diagonalization. So this example seems OK. It seems can also work on [0,1], with {a,b} replaced by {0,…,9}.

Hoping anyone help me out, sincerely!

LikeLike

Very good question, and it’s one I’ve struggled with myself in the past! The problem is that your construction is only working with

finitestrings, and the set of finite strings is indeed countable. The thing about real numbers is that there is a bijection (indeed, you can define them this way) between the reals and infinite strings of characters in {0,1}. The “finite” decimal expansions correspond to rational numbers (with the infinitely many following zeros being truncated for brevity). Your construction will not be surjective because it misses every infinite string, for instance, the infinite string of “b”s if we’re thinking of b as 1 and a as 0. Indeed, I heard a very clever “false proof” using just the same idea as yours. I posted about it here: False Proof – The Reals are Countable. It uses the misdirection of “square-free” numbers, but it’s the same idea at heart: it only captures finite things.LikeLike

Ah, I got the point. I failed to clarify the set arguing about. As you point out, the bijection constructed is just from N to all finite string S. Although the length of element in S is unlimited, or potentially infinite, no truly infinite string contained in S! while the string defined in diagonlization is a truly infinite one… Subtle but critical. I also read the False Proof series and learned more.

Thank you very much !

LikeLike