A classical beginning
A selection from Proof and Art of Mathematics, concerning the classical theorem establishing the irrationality of the square root of 2
Welcome to this free extended excerpt from from my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing, for aspiring mathematicians who want to learn how to write proofs.
Proof and the Art of Mathematics teaches the art of proof-writing in the diverse contexts of a variety of mathematical subjects—number theory, finite combinatorics, discrete mathematics, order theory, game theory, geometry, set theory, real analysis, and others. The proof-writing ideas are thus presented in the context of different mathematical topics, but always with mathematical theorems and statements that carry their own inherent interest and fascination—compelling mathematical results with interesting, elementary proofs.
So welcome to this first installment—I shall be regularly featuring additional excerpts from the book here on Infinitely More, and so look for them in the Proof and the Art of Mathematics section.
I particularly recommend this book to instructors who are teaching the art of proof-writing. But the book also serves well for any interested reader.
A Classical Beginning
One of the classical gems of mathematics—and to my way of thinking, a pinnacle of human achievement—is the ancient discovery of incommensurable numbers, quantities that cannot be expressed as the ratio of integers.
The Pythagoreans discovered in the fifth century BC that the side and diagonal of a square have no common unit of measure; there is no smaller unit length of which they are both integral multiples; the quantities are incommensurable. If you divide the side of a square into ten units, then the diagonal will be a little more than fourteen of them. If you divide the side into one hundred units, then the diagonal will be a little more than 141; if one thousand, then a little more than 1414. It will never come out exactly. One sees those approximation numbers as the initial digits of the decimal expansion:
The discovery shocked the Pythagoreans. It was downright heretical, in light of their quasi-religious number-mysticism beliefs, which aimed to comprehend all through proportion and ratio, taking numbers as a foundational substance. According to legend, the man who made the discovery was drowned at sea, perhaps punished by the gods for impiously divulging the irrational.
The number √2 is irrational
In modern terminology, the claim is that √2 is irrational, since this is the ratio of diagonal to side in any square, and the rational numbers are those expressible as a fraction of integers p / q, with q ≠ 0. So we may state the claim as follows.
Theorem. The number √2 is irrational.
In plainer words, the theorem asserts that √2 cannot be expressed as a fraction. Let us prove the theorem.
Proof. Suppose toward contradiction that √2 is rational. This means that
for some integers p and q, with q ≠ 0. We may assume that p / q is in lowest terms, which means that p and q have no nontrivial common factors. By squaring both sides, we conclude that
and consequently
This tells us that p2 must be an even number, which implies that p also is even, since the square of an odd number is odd. So p = 2k for some integer k. From this, it follows that
and therefore
So q2 also is even, and therefore q must be even. Thus, both p and q are even, which contradicts our assumption that p / q was in lowest terms. So √2 cannot be rational. ☐
That was a traditional argument, and my impression is that if you were to knock on doors down the hall of a university mathematics department asking for a proof that √2 is irrational, then first of all, every single mathematician you find will be able to prove it and second, the odds are good for you to get a version of that argument. To my way of thinking, just as every self-respecting educated person should know something of the works of Shakespeare and of the heliocentric theory of planetary motion, similarly everyone should be able to prove the irrationality of the square root of 2. Mathematicians now have dozens of proofs of this beautiful classical result—the reader can find various collections online—and by the end of this chapter, we shall see several.
Notice that the proof proceeded by contradiction. In such a proof, one assumes (“toward contradiction”) that the desired conclusion is not true, aiming to derive from this assumption a contradiction, an impossible consequence. Since that consequence cannot be the true state of affairs, the assumption leading to it must have been wrong, and so the desired conclusion must have been true.
In the proof we gave, we had appealed to some familiar mathematical facts, such as the fact that the product of two odd numbers is odd and the fact that every rational number can be expressed as a fraction in lowest terms. These facts, of course, require their own proof, and indeed we shall provide proofs presently.
If √2 is not rational, then what kind of number is it? One can view certain developments in the history of mathematics as a process of recognizing problematic issues in our number systems and addressing them with new and better number systems. In ancient days, one had the whole numbers 1, 2, 3, and so on. This number system, however, lacks an additive identity, and by including such an identity, the number zero, we thereby form the natural numbers ℕ with 0, 1, 2, 3, and so on. Although one can always add two natural numbers together and still have a natural number, this is not true for subtraction, and so we are led to the integers ℤ, which include negative numbers ...,-2, -1, 0, 1, 2,... and thereby become closed under subtraction. While one can always multiply two integers and still have an integer, this is not true for division, and so we form the rational numbers ℚ to accommodate ratios of integers. The fact that √2 is irrational shows the need for us to extend our number systems beyond the rational numbers, to the real numbers ℝ and eventually to the complex numbers ℂ.
In truth, the actual historical development of the number systems was not like that; it was confused and incoherent. The ancients had the whole numbers and their ratios, and the positive rational numbers, but the number zero was strangely delayed and complicated, appearing early on in some places merely as a placeholder but taken seriously as an actual number only much later. The actual historical development of mathematical ideas is often messy and confounding, riddled with confusion and misunderstanding, yet afterward one can reinvent an imaginary but more logical progression. One can gain mathematical insight from the imaginary history; not every mistake in the actual historical development of mathematics is interesting.
The number √2, while irrational, is nevertheless still an algebraic number, which means it is the root of a nontrivial integer polynomial, in this case a solution of the equation x2 - 2 = 0. The existence of transcendental real numbers, or nonalgebraic numbers, was proved in 1844 by Joseph Liouville. I view Liouville's result as an analogue of the classical √2 result, because it shows once again the need for us to extend our number system: the algebraic numbers do not exhaust the numbers we find important. Indeed, we now know that numbers such as e and π are transcendental, and in 1874 Georg Cantor proved in a precise sense that most real numbers are transcendental.
Meanwhile, the complex numbers extend the real numbers with the imaginary numbers, starting with the imaginary unit
Since the number i solves the equation
it is an algebraic complex number, but there are also transcendental complex numbers. Mathematicians continue to extend our various number systems, and we now have number systems with various kinds of points at infinity, such as the extended real numbers, which are the real numbers plus ±∞, as well as other number systems, such as the quaternions, the ordinal numbers, the hyperreal numbers, the surreal numbers, and more.
Returning to the integers and the rationals, let us consider our proof above more closely. We had used some fundamental properties of the integers and the rational numbers, such as the fact that every fraction can be put into lowest terms. That may seem familiar, but can we prove it? Actually, we can completely avoid the issue of lowest terms by arguing as follows.
Proof. (Alternative slightly revised proof) Suppose toward contradiction that √2 is rational. So √2 = p / q for some integers p and q, and we may assume that the numerator p is chosen as small as possible for such a representation. It follows as before that 2q2 = p2, and so p2 and hence also p is even. So p = 2k for some k, which implies that q2 = 2k2 as before, and so q2 and hence also q is even. So q = 2r for some r, and consequently
We have therefore found a rational representation of √2 using a smaller numerator, contradicting our earlier assumption. So √2 is not rational. ☐
This way of arguing, although very similar to the original argument, does not require putting fractions in lowest terms. Furthermore, an essentially similar idea can be used to prove that indeed every fraction can be put in lowest terms.
Lowest terms
What does it mean for a fraction p / q to be in lowest terms? It means that p and q are relatively prime, that is, that they have no common factor, a number k > 1 that divides both of them. I find it interesting that the property of being in lowest terms is not a property of the rational number itself but rather a property of the fractional expression used to represent the number. For example, 3 / 6 is not in lowest terms and 1 / 2 is, yet we say that they are equal:
But how can two things be identical if they have different properties? These two expressions are equal in that they describe the same rational number; the values of the expressions are the same, even though the expressions themselves are different. Thus, we distinguish between the description of a number and the number itself, between our talk about a number and what the number actually is. It is a form of the use/mention distinction, the distinction between syntax and semantics at the core of the subject of mathematical logic. How pleasant to see it arise in the familiar elementary topic of lowest terms.
Lemma. Every fraction can be put in lowest terms.
Proof. Consider any fraction p / q, where p and q are integers and q ≠ 0. Let p' be the smallest nonnegative integer for which there is an integer q' with
That is, we consider a representation p' / q' of the original fraction p / q whose numerator p' is as small as possible. I claim that it follows that p' and q' are relatively prime, since if they had a common factor, we could divide it out and thereby make an instance of a fraction equal to p / q with a smaller numerator. But p' was chosen to be smallest, and so there is no such common factor. Therefore, p' / q' is in lowest terms. ☐
This proof and the previous proof of the theorem relied on a more fundamental principle, the least-number principle, which asserts that if there is a natural number with a certain property, then there is a smallest such number with that property. In other words, every nonempty set of natural numbers has a least element. This principle is closely connected with the principle of mathematical induction, which we shall discuss in a later chapter. For now, let us simply take it as a basic principle that if there is a natural number with a property, then there is a smallest such number with that property.
A geometric proof
Let us now give a second proof of the irrationality of √2, one with geometric character, due to Stanley Tennenbaum. Mathematicians have found dozens of different proofs of this classic result, many of them exhibiting a fundamentally different character from what we saw above.
A geometric proof of the theorem. If √2 is rational p / q, then as before, we see that
which means that some integer square has the same area as two copies of another smaller integer square.
We may choose these squares to have the smallest possible integer sides so as to realize this feature. Let us arrange the two medium squares overlapping inside the larger square, as shown here.
Since the large blue square had the same area as the two medium gold squares, it follows that the small orange central square of overlap must be exactly balanced by the two smaller uncovered blue squares in the corners. That is, the area of overlap is exactly the same as the area of the two uncovered blue corner spaces. Let us pull these smaller squares out of the figure to illustrate this relation as follows.
Notice that the squares in this smaller instance also have integer-length sides, since their lengths arise as differences in the side lengths of previous squares. So we have found a strictly smaller integer square that is the sum of another integer square with itself, contradicting our assumption that the original square was the smallest such instance. ☐
Generalizations to other roots
Let us generalize the theorem in a few ways. For example, an essentially similar argument to our original proof works also for the cube root of 2.
Theorem. The number ∛2 is irrational.
Proof. We can basically follow our first argument for √2. Namely, suppose that
in lowest terms. By cubing both sides, we conclude that
So p3 is even and therefore p is even, since odd × odd × odd is odd. So p = 2k for some k, and therefore
Dividing by 2, we conclude that q3 = 4k3, and so q3 is even and therefore q is even, contrary to our assumption that p / q is in lowest terms. ☐
This argument works essentially the same with
and so on, as the reader will verify in the exercises. Another way to generalize the result is to consider the square roots of numbers other than 2. For example:
Theorem. The number √3 is irrational.
Proof. Suppose that √3 = p / q in lowest terms. So 3q2 = p2. So p2 is a multiple of 3. This implies that p is a multiple of 3, since otherwise it would not arise in the prime factorization of p2. So p = 3k for some integer k; therefore,
and so q2 = 3k2. Thus, q2 is a multiple of 3, and so q is a multiple of 3. This contradicts our assumption that p / q was in lowest terms. ☐
This proof relied on the existence and uniqueness of prime factorizations, a familiar fact, which will also be covered in detail in a later chapter. In the exercises, the reader is asked to prove further generalizations. Some generalizations can be handled as a consequence of what we have already done. A corollary is a theorem-like statement having an easy proof as a consequence of an earlier theorem.
Corollary. The number √18 is irrational.
Proof. Notice that
If 3√2 = p / q were rational, then √2 = p / (3q), and so √2 would also be rational, which it is not. So √18 cannot be rational. ☐
Let us also prove this corollary directly, without relying on the earlier theorem.
Alternative direct proof of the corollary. Assume toward contradiction that √18 is rational. So √18 = p / q for some integers p and q, and we may assume that p / q is in lowest terms. Squaring both sides and simplifying, we see that
and so p2 is even. So p = 2k for some integer k; consequently,
and so
So 9q2 is even, but since 9 is odd, it must be that q2 is even and hence also that q is even. So both p and q are even, contrary to our assumption that p / q was in lowest terms. So √18 cannot be rational. ☐
All the theorems and corollaries in this chapter are unified by a grand universal theorem, asserting that
is irrational unless n is itself a perfect integer kth power, meaning that n = rk for some integer r. This is equivalent to saying that all the exponents in the prime factorization of n are multiples of k.
Meanwhile, see my musical proof of the classic theorem on √2, in collaboration with Hannah Hoffman:
Mathematical Habits
State claims explicitly. Do not allow ambiguity in your mathematical claims and theorem statements. Distinguish between similar but inequivalent statements. Formulate your claim to state exactly what you intend.
Know exactly what you are trying to prove. Before embarking on an argument or proof, get completely clear about the meaning and content of the claim that is to be proved.
Insist on proof. Be prepared to prove essentially every mathematical statement you make. When challenged, be prepared to give further and more detailed justification. Do not make assertions that you cannot back up. Instead, make weaker statements that you can prove. Some of the exercises ask you to “prove your answer,” but this is redundant, because, of course, you should always prove your answers in mathematical exercises.
Try proof by contradiction. When trying to prove a statement, imagine what it would be like if the statement were false. Write, “Suppose toward contradiction that the statement is false, ...” and then try to derive a contradiction from your assumption. If you succeed, then you will have proved that the statement must be true.
Try to prove a stronger result. Sometimes a difficult or confusing theorem can be proved by aiming at the outset to prove a much stronger result. One overcomes a distracting hypothesis simply by dispensing with it, by realizing it as a distraction, an irrelevant restriction. In the fully general case, one sometimes finds one's way through with a general argument.
Generalize. After proving a statement, seek to prove a more general statement. Weaken the hypothesis or strengthen the conclusion. Apply the idea of the argument in another similar-enough circumstance. Unify our understanding of diverse situations. Seek the essence of a phenomenon.
Exercises
Prove that the square of any odd number is odd. (Assume that a positive integer is odd if and only if it has the form 2k+1.)
Master several alternative proofs of the irrationality of √2, such as those available at http://www.cut-the-knot.org/proofs/sq_root.shtml, and present one of the proofs to the class.
Prove that
\(\sqrt[4]{2}\)is irrational. Give a direct argument, but kindly also deduce it as a corollary of theorem on √2.
Prove that
\(\sqrt[m]{2} \)is irrational for every integer m ≥ 2.
Prove that √5 and √7 are irrational. Prove that √p is irrational, whenever p is prime.
Prove that √20 is irrational as a corollary of the fact that √5 is irrational.
Prove that √(2m) is irrational, whenever m is odd.
In the geometric proof that √2 is irrational, what are the side lengths of the smaller squares that arise in the proof? Using those expressions and some elementary algebra, construct a new algebraic proof that √2 is irrational. [Hint: Assume that p2 = q2 + q2 and that this is the smallest instance in the positive integers. Now consider 2q - p and p - q.]
Criticize this “proof.” Claim. √n is irrational for every natural number n. Proof. Suppose toward contradiction that √n = p / q in lowest terms. Square both sides to conclude that nq2 = p2. So p2 is a multiple of n, and therefore p is a multiple of n. So p = nk for some k. So nq2 = (nk)2 = n2k2, and therefore q2 = nk2. So q2 is a multiple of n, and therefore q is a multiple of n, contrary to the assumption that p / q is in lowest terms. ☐
Criticize this “proof.” Claim. √14 is irrational. Proof. We know that √14 = √2·√7, and we also know that √2 and √7 are each irrational, since 2 and 7 are prime. Thus, √14 is the product of two irrational numbers and therefore irrational. ☐
For which natural numbers n is √n irrational? Prove your answer. [Hint: Consider the prime factorization of n, and consider especially the exponents of the primes in that prime factorization.]
Prove the unifying theorem mentioned at the end the chapter, namely, that
\(\sqrt[k]{n}\)is irrational unless n is itself an integer kth power.
Prove that the irrational real numbers are exactly those real numbers that are a different distance from every rational number. Is it also true if you swap “rational” and “irrational”?
A full discussion of the exercises, their solutions (often by multiple distinct methods), and the further ideas to which they lead can be found the supplemental volume:
Is there a proof the irrationality of sqrt(2) that generalizes further than “integer roots of integers that are not integers are irrational”?
Conway and I gave one in our paper “Extreme Proofs”. Originally due to Laczkovich:
For positive integers n, (sqrt(2)- 1)^n has the form a(sqrt(2))+ b where a and b are integers, not necessarily positive. But if sqrt(2) were rational with denominator D, then for integral a,b, a(sqrt(2)) + b would be rational with denominator dividing D, and so could not approach a limit of 0, as (sqrt(2)-1)^n must, since 0<(sqrt(2) - 1)<1.
The proof can be generalized to show that any real algebraic integer (root of a polynomial with integer coefficients and a highest-degree coefficient of 1) is either integeral or irrational. All you have to note is that higher powers of the root can be replaced recursively by sums and differences of lower powers, because the root satisfies a monic polynomial.
It’s also easy to see that any algebraic irrational is an integer divisor of an algebraic integer (if the leading coefficient is ax^n, multiply the whole polynomial by a^(n-1), and set y=ax, and you have a monic polynomial for y).
For any SPECIFIC algebraic irrational, there is a trivially easy proof that it is, by using the rational root theorem: for any rational root, the denominator must divide the leading coefficient and the numerator must divide the constant term, so you just check all possibilities.
(“Easy”, but not short—you might have difficulty factoring those two coefficients if they are large, and if on the other hand they’re not difficult to factor they may have lots of divisors so you will have a lot of checking!)