One of the aspects of mathematics that I find extraordinary and exciting is that it is possible to *prove* that some things are impossible. Not just difficult, but genuinely impossible. I hope at some point to write about one famous example of this, the insolubility of the quintic by radicals (including what that phrase means!), but this week I thought that I’d write about another famous example, the irrationality of the square root of 2. These are both examples of theorems that say that something is impossible — but the latter is a bit easier than the former!

### Types of numbers

Let’s start by talking about different types of number. (If you know about this already, please feel free to skip to the next section.)

Small children start by learning the counting numbers: 1, 2, 3, … (and perhaps 0). Mathematicians call these the *natural numbers*, and represent the set of natural numbers by the symbol . I am being deliberately vague about whether 0 is a natural number: opinions differ, and it depends on the context.

When children get a bit older (and mathematicians more sophisticated — I think that the order in which children meet these ideas mirrors the historical development), they discover that various things become easier if they are allowed negative numbers too. The whole numbers (positive, negative and 0) are called *integers*, and the set of integers is represented by . (The letter comes from the German word “Zahlen”, meaning “numbers”.)

Another type of number that children meet quite early on is the fraction. (It’s important to be able to distinguish between half a cake and a whole cake!) Mathematicians call these the *rational numbers*, or the *rationals*. They are the numbers that can be written as the ratio of two integers. That is, the rationals are the numbers , where and are integers, and is not 0. The set of rationals is denoted by (for quotient).

The other set of numbers that I want to mention here is the set of real numbers, . One way to think of the real numbers is as all decimals. If you imagine the number line, with the integers marked, the rationals occupy some of the points between (and including) the integers, but the real numbers are *all* of the points on this line.

I’ve described the sets in this order because they are nested sets. For example, every natural number is also an integer: the natural numbers form a subset of the integers. The mathematical way to write this is . Then the integers form a subset of the rationals, and the rationals form a subset of the real numbers.

One quick warning. I’ve often seen students write things along the lines of “3 isn’t a fraction”. While I know what they mean, 3 *is* a fraction (a rational number): it’s 3/1. It is a lot more convenient to include the integers as rationals than to exclude them in some artificial way.

### The square root of 2

So, back to the square root of 2. Tim Gowers has a very nice discussion about the existence of the square root of 2, but I’ll assume that we’re willing to believe in its existence for now! The ancient Greeks were: the diagonal of a square with side length 1 has length . (This follows from Pythagoras‘s theorem — perhaps that will be the theorem of a week in the future!) Indeed, the story is that the irrationality of was first discovered by one of the followers of Pythagoras. Let’s state the theorem properly (so that I can use the nice WordPress blockquote environment!).

TheoremThe square root of 2 is irrational.

This is an old chestnut that can be proved in many ways. I’ll describe one version of the most common proof here, since it’s a very good example of *proof by contradiction*, a useful tool when proving the impossibility of something.

Why do I keep mentioning impossibility in the context of the irrationality of the square root of 2? Well, how can we tell whether is irrational? We are interested in whether we can solve the equation

,

where and are integers, and is not 0. The square root of 2 is irrational precisely if it impossible to solve this equation.

How can one go about proving that something is impossible? It’s no good just testing values of and and discovering that they don’t work: no matter how many values we test, we can never test all of them, because there are infinitely many possibilities! So we need a more cunning strategy.

This is where proof by contradiction comes in. It’s very difficult to go anywhere when dealing with a negative statement (“there are no solutions”). So instead we suppose that we *can* solve the equation (that is, that is rational). That gives us a positive statement that we can manipulate. Then we make various deductions from that supposition, and come to some absurdity (a contradiction). But if we arrive at an absurdity, then we must have had a false statement somewhere. Everything followed legitimately from the supposition, so it must be that the supposition is false. That is, it cannot be the case that is rational, so it must be irrational. Let’s see how the details work.

So, we start by supposing that we have integers and (with not 0) such that

.

I think that this is crying out for us to square both sides, to get rid of the scary square root. This gives

,

so .

Let’s think about the power of 2 in the prime factorisation of each side. (This is assuming the Fundamental Theorem of Arithmetic, which tells us that talking about “the” prime factorisation is a legitimate thing to do.)

What can we say about the power of 2 in the prime factorisation of ? Without knowing , it might seem that we can’t say anything. But in fact there is one thing that we *can* say. If the exponent of 2 in the prime factorisation of is (so , where is odd), then , and is odd. So the exponent of 2 in the prime factorisation of must be even.

What can we say about the power of 2 in the left-hand side, ? Just as above, the exponent of 2 in the prime factorisation of is even. So the exponent of 2 in the prime factorisation of is odd (it’s one more than that in the prime factorisation of ).

Now , so they must have the same prime factorisation (by the Fundamental Theorem of Arithmetic). But we’ve just established that the powers of 2 are different! This is the contradiction that we wanted.

Since our deductions have led to a contradiction, our initial assumption must have been false, and so is indeed irrational.

### Further reading

Wikipedia presents a slightly different version of the above proof, one that avoids using the Fundamental Theorem of Arithmetic.

If you didn’t read it when I referenced it above, I recommend that you look at Tim Gowers’s dialogue concerning the existence of the square root of two.

There’s an article about proof by contradiction on NRICH.

There are many proofs that the square root of 2 is irrational collected at Cut The Knot. The first time I saw Proof 8”’ (which was a while back, elsewhere), I laughed out loud!

October 6, 2009 at 6:33 pm

[…] to understand but difficult to solve. Their solution often involves leaving the safe world of the integers and using tools and techniques from other areas of mathematics before “projecting” the […]

October 25, 2009 at 10:00 pm

[…] used this principle to prove a result about approximating irrational numbers by rationals. The square root of 2 is irrational, but is it close to a rational? That’s a rather vague question. We can approximate […]

February 24, 2010 at 10:07 pm

[…] infinite sets. (An infinite set is one that cannot be matched to any finite set.) We use the natural numbers as our counting set, and try to match numbers to the naturals. If we can do that, we say that the […]

March 3, 2010 at 9:37 pm

[…] previously written about the fact that the square root of 2 is irrational. That is, it can’t be written as the ratio of two whole numbers (as a fraction, if you […]

March 18, 2010 at 7:59 am

[…] had a previous example of a proof that something is impossible, when we saw that the square root of 2 is irrational. That is, we showed that it’s impossible to write as the ratio of two whole numbers. […]

August 16, 2012 at 11:47 am

[…] and we learned about modular arithmetic. In the third and final lecture, we mentioned that is irrational, and talked about continued fractions. There are many proofs that is irrational. We mentioned […]

August 15, 2013 at 9:11 am

[…] and we learned about modular arithmetic. In the third and final lecture, we mentioned that is irrational, and talked about continued fractions. There are many proofs that is irrational. A couple of […]