Infinity within infinity
It was the great 16th-century Italian polymath Galileo Galilei(1564–1642)who wasfirst to alert us to the fact that the nature of infinite collections is fundamentally different fromfinite ones. As alluded to on thefirst page of this book, the size of afinite set is smaller than that of a second set if the members of thefirst can be paired off with those of just a portion of the second. However,infinite sets by contrast can be made to correspond in this way to subsets of themselves(where by the term subset I mean a set within the set itself). We need go no further than the sequence of natural counting numbers 1,2,3,4,···in order to see this. It is easy to describe any number of subsets of this collection that themselves form an infinite list, and so are in a one-to-one correspondence with the full set(see Figure 8):the odd numbers,1,3,5,7,···, the square numbers,1,4,9,16,···and, less obviously, the prime numbers,2,3,5,7,···, and in each of these cases the respective complementary sets of the even numbers, the non-squares, and the composite numbers are also infinite.
The Hilbert Hotel
This rather extraordinary hotel, which is always associated with David Hilbert(1862–1943), the leading German mathematician of his day, serves to bring to life the strange nature of the infinite. Its chief feature is that it has infinitely many rooms, numbered1,2,3,···, and boasts that there is always room at Hilbert’s Hotel.
8. The evensand thesquarespaired with the natural numbers
One night, however, it is in fact full, which is to say each and every room is occupied by a guest and much to the dismay of the desk clerk, one more customer fronts up demanding a room. An ugly scene is avoided when the manager intervenes and takes the clerk aside to explain how to deal with the situation:tell the occupant of Room 1 to move to Room 2 says he, that of Room 2 to move into Room 3, and so on. That is to say, we issue a global request that the customer in Room nshould shift into Room n+1, and this will leave Room 1 empty for this gentleman!
And so you see, there is always room at the Hilbert Hotel. But how much room?
The next evening, the clerk is confronted with a similar but more testing situation. This time a spaceship with 1729 passengers arrives, all demanding a room in the already fully occupied hotel.The clerk has, however, learned his lesson from the previous night and sees how to extend the idea to cope with this additional group.He tells the person in Room 1 to go to Room 1730, that of Room 2to shift to Room 1731, and so on, issuing the global request that the customer in Room nshould move into Room number n+1729.This leaves Rooms 1 through to 1729 free for the new arrivals, and our clerk is rightly proud of himself for dealing with this new version of last night’s problem all by himself.
Thefinal night, however, the clerk again faces the same situation–a full hotel, but this time, to his horror, not just a few extra customers show up but an infinite space coach with infinitely many passengers, one for each of the counting numbers 1,2,3.···.The overwhelmed clerk tells the coach driver that the hotel is full and there is no conceivable way of dealing with them all. He might be able to squeeze in one or two more, anyfinite number perhaps,but surely not infinitely many more. It is plainly impossible!
An infinite riot might have ensued except again for the timely intervention of the manager who, being well versed in Galileo’s lessons on infinite sets, informs the coach driver that there is no problem at all. There is always room at Hilbert’s Hotel for anyone and everyone. He takes his panicking desk clerk aside for another lesson. All we need do is this, he says. We tell the occupant of Room 1 to shift into Room 2, that in Room 2 to shift to Room 4,that in Room 3 to go to Room 6, and so on. In general the global instruction is that the occupant of Room nshould move into Room 2n. This will leave all the odd numbered rooms empty for the passengers of the infinite space coach. No problem at all!
The manager seems to have it all under control. However, even he would be caught out if a spaceship turned up that somehow had the technology to have one passenger for each point in the continuum of the real line. One person for every decimal number would totally overrun Hilbert’s Hotel, and we shall see why in the next section.
Cantor’s comparisons
All this may be surprising thefirst time you think about it, but it is not difficult to accept that the behaviour of infinite sets may differ in some respects fromfinite ones, and this property of having the same size as one of its subsets is therefore a case in point. In the19th century, however, Georg Cantor(1845–1918)went much further and discovered that not all infinite sets can be regarded as having equally many members. This revelation was unexpected in nature but is not hard to appreciate once your attention is drawn to it.
Cantor asks us to think about the following. Suppose we have any infinite list L of numbers a1,a2,···thought of as being given in decimal form. Then it is possible to write down another number,a, that does not appear anywhere in the list L:we simply take a to be different from a1 in thefirst place after the decimal point,different from a2 in the second decimal place, different from a3 in the third decimal place, and so on–in this way, we may build our number a making sure it is not equal to any number in the list.This observation looks innocuous but it has the immediate consequence that it is absolutely impossible for the list L to contain all numbers, because the number a will be missing from L. It follows that the set of all real numbers,thatisalldecimal expansions, cannot be written in a list, or in other words cannot be put into a one-to-one correspondence with the natural counting numbers, the way we saw in Figure 8. This line of reasoning is known as Cantor’s Diagonal Argument, as the number a that lies outside the set L is constructed by imagining a list of the decimal displays of L as in Figure 9 and defining a in terms of the diagonal of the array.
There is some subtlety here, for we might suggest that we can easily get around this difficulty by simply placing the missing number a at the front of L. This creates an enlarged listing M containing the annoying number a. However, the underlying problem has not gone away. We can apply Cantor’s construction again to introduce a fresh number b that is not present in the new list M. We can of course continue to augment the current list as before any number of times, but Cantor’s point remains valid:although we can keep creating lists that contain additional numbers that were previously overlooked, there can never be one specific list that contains every real number.
9. Cantor’s numbera differs from each ak in the kth decimal place
The collection of all real numbers is therefore larger in a sense than the collection of all positive integers. Even though both are infinite, the sets cannot be paired off together the way the even numbers can be paired with the list of all counting numbers.Indeed, if we apply Cantor’s Diagonal Argument to a putative list of all numbers in the interval 0 to 1, the missing number a will also lie in this range. Therefore, we likewise conclude that this collection will also defy every attempt at listing it in full. I mention this as we shall make use of that fact shortly.
Cantor’s result is rendered all the more striking by the fact that many other sets of numbers can be put into an infinite list,including the Greeks’euclidean numbers. A little ingenuity is involved, but once a couple of tricks are learned, it is not hard to show that many sets of numbers are countable,whichistheterm we use to mean the set can be listed in the same fashion as the counting numbers. Otherwise an infinite set is called uncountable.
What we have allowed to happen in casually accepting any decimal expansion is to open the door to what are known as the transcendental numbers, those numbers that lie beyond those that arise through euclidean geometry and ordinary algebraic equations. Cantor’s argument shows us that transcendental numbers exist and, in addition, there must be infinitely many of them, for if they formed only afinite collection, they could be placed in front of our list of algebraic numbers(the non-transcendentals), so yielding a listing of all real numbers,which we now know is impossible. What is striking is that we have discovered the existence of these strange numbers without identifying a single one of them!Their existence was revealed simply through comparing certain infinite collections to one another. The transcendentals are the numbers thatfill the huge void between the more familiar algebraic numbers and the collection of all decimal expansions:to borrow an astronomical metaphor, the transcendentals are the dark matter of the number world.
In passing from the rationals to the reals, we are moving from one set to another of higher cardinality as mathematicians put it. Two sets have the same cardinality if their members can be paired off,one against the other. What can be shown using the Cantor argument is that any set has a smaller cardinality than the set formed by taking all of its subsets. This is obvious forfinite collections:indeed, in Chapter 5 it was explained that if we have a set of n members then there are 2n subsets that can be formed in this way. But how large is the set S of all subsets of the infinite set of natural numbers,{1,2,3,···}?This question is not only interesting in itself but also in the manner in which we arrive at the answer, which is that S is indeed uncountable.
Russell’s Paradox
Suppose to the contrary that S was itself countable, in which case the subsets of the counting numbers could be listed in some order A1, A2,···. Now an arbitrary number nmay or may not be a member of An–let us consider the set A that consists of all numbers nsuch that n is not a member of the set An.NowA is a subset of the counting numbers(possibly the empty subset)and so appears in the aforesaid list at some point, let A=Aj say. An unanswerable question now arises:is j a member of Aj？Ifthe answer were‘yes’then, by the very way A is defined, we conclude that j is not a member of A, but A=Aj,sothatis self-contradictory. The alternative is no, j is not a member of Aj,in which case, again by the definition of A,weinferthatj is a member of A=Aj, and once more we have contradiction. Since contradiction is unavoidable, our original assumption that the subsets of the counting numbers could be listed in a countable fashion must be false. Indeed, this argument works to show that the set of all subsets of any countable but infinite set is uncountable.
This particular self-referential style argument was introduced by Bertrand Russell(1872–1970)in a slightly different context that led to what is known as Russell’s Paradox. Russell applied it to the‘set of all sets that are not members of themselves’, asking the embarrassing question whether or not that set is a member of itself. Again,‘yes’implies‘no’and‘no’implies‘yes’, forcing Russell to conclude that this set cannot exist.
In the 1890s, Cantor himself discovered an implicit contradiction stemming from the idea of the‘set of all sets’. Indeed, Russell acknowledged that the argument of his paradox was inspired by the work of Cantor. The upshot of all this, however, is that we cannot simply imagine that mathematical sets can be introduced in any manner whatsoever, but some restrictions must be placed on how sets may be specified. Set theorists and logicians have been wrestling with the consequences of this ever since. The most satisfactory resolution of these difficulties is provided by the now standard ZFC Set Theory(the Zermelo-Fraenkel set theory with the Axiom of Choice).
The number line under the microscope
10. Rationals separate any given positions on the number line
Returning to our given numbers, a and b, once again let c be their average. If c is irrational, we have a number of the required kind(irrational). If on the other hand, c is rational, put d=c+t,where t is the irrational number of the previous paragraph. By what has gone before, d will also be irrational, and if we take nlarge enough,we can always ensure that d is so close to the average c of the two given numbers a and b that it lies between them. In this way, we see that the irrational numbers too form a dense set and, as with the rational numbers, we can infer that there are infinitely many irrational numbers lying between any two numbers on the number line.
And so the set of rationals and its complementary set of irrationals are in one way comparable(they are both dense in the number line)and in another not(thefirst set is countable, the second not).
Cantor’s Middle Third Set
We now have a clearer idea as to how the rational and the irrational numbers interlace to form the real number line. The rational numbers form a countable set, yet are densely packed into the number line. Cantor’s Middle Third Set is, by way of contrast,an uncountable subset of the unit interval that nevertheless is sparsely spread. It is the result of the following construction.
11. Evolution of Cantor’s Middle Third Set to the 4th level
Next we make an amazing observation. By taking the ternary expansion of any number c in C and replacing each instance of2 by 1, we obtain the binary expansion of some number c in the unit interval. This gives a one-to-one correspondence of C with the set of all numbers in I(written in binary). It follows that the cardinality of C is the same as that of I, and since the latter is an uncountable set(by Cantor’s Diagonal Argument), it follows that the Cantor Middle Third Set is not only infinite but uncountable.
ThereforewehaveasetC that is in one sense negligible in size(has measure zero), but by another way of reckoning C is huge, as it has the same cardinality as I and hence of the whole real line.
What is more, far from being dense, C is nowhere dense.Recall that by saying that a set like the rationals is dense, we mean that whenever we take a real number a, there are rational numbers to be found in any little interval surrounding a, however small that interval might be. We say that any neighbourhood of a contains members of the set of rationals. The Cantor set has quite the opposite nature–numbers not in C might live their lives in the real line without ever coming across any members of C, provided they confine their experiences to a narrow enough locality around where they live. To see this, take any number a that is not in C,so that a has a ternary expansion that contains at least one 1:a=0·....1....., with the 1 in the nth place, say. For a sufficiently tiny interval surrounding a, the numbers b in that interval have a ternary expansion that agrees with that of a up to places beyond the nth, and so all of them will also not be members of the strange set C as their ternary expansions will also contain at least one instance of 1.
On the other hand, any member a of the Cantor set will not feel too isolated, for when a looks out into any interval J that surrounds it in the number line, however small, a willfind neighbours from the set C living alongside it(and numbers not in C as well). We can specify a member b of the given interval J that also lies in C by taking b to have a ternary expansion that agrees with a to a sufficiently large number of places, but with no entry being a 1. Indeed, there are uncountably many members of C in J.
In conclusion, the Cantor Middle Third Set C is as numerous as can be and, to the members of the C club, their brothers and sisters are to be seen all around them wherever they look. To the numbers not in C,however,C hardly seems to exist at all. Not one member of C is to be spotted in their exclusive neighbourhoods,and the set C itself has measure zero. To them, C is almost nothing.
Diophantine equations
An interesting line of study emerges, however, when we take the opposite tack and insist that not only the coefficients of our equations but their solutions have also to be integers. Here is a classic example.
A box contains spiders and beetles and 46 legs. How many of each kind of creature are there?This little number puzzle can be solved easily by trial, but it is instructive to note thatfirst, it can be represented by an equation:6b+8s=46, and second that we are only interested in certain kinds of solutions to that equation,namely those where the number of beetles(b)and spiders(s)are counting numbers. In general, a system of equations is calledDiophantine when we are restricting our solution search to special number types, typically integer or rational answers are what we are after.
There is a simple method for solving linear Diophantine equations such as this one. First, divide through the equation by the hcf of the coefficients, which are in this case 6 and 8 so their hcf is 2.Cancelling this common factor of 2 we obtain an equivalent equation, that is to say one with the same solutions:3b+4s=23.If the right-hand side were no longer an integer after performing this division, that would tell us that there were no integral solutions to the equation and we could stop right there. The next stage is to take one of the coefficients, the smaller one is normally the easiest, and work in multiples of that, in this case 3. Our equation can be written as 3b+3s+s=(3×7)+2;rearranging we obtain s=(3×7)-3b-3s+2. The point of this is that it shows that s has the form 3t+2 for some integer t. Substituting s=3t+2 into our equation and making b the subject, we get
We now have the complete solution in integers to the Diophantine equation:b=5-4t, s=3t+2. Choosing any integral value for t will give a solution, and all solutions in integers are of this form.
Our original problem, however, was further constrained in that both b and s had to be at least zero, as negative beetles and spiders do not exist. Hence there are only two feasible values of t, those being t=0andt=1, giving us the two possible solutions of 5beetles and 2 spiders, and 1 beetle and 5 spiders. If we interpret the puzzle as meaning that there is a plurality of both types of creature, we have the traditional solution:5 beetles and 2 spiders.
12. Lattice points on the line of a linear equation
This type of problem is called linear because the graph of the associated equation consists of an infinite line of points. The Diophantine problem then is tofind the lattice points on this line,which are the points where both coordinates are integral or, if we only admit positive solutions, only lattice points in the positive quadrant will do.
However, once we allow squares and higher powers into our equations, the nature of the corresponding problems are much more varied and interesting. A classical problem of this type that has a full solution is that offinding all Pythagorean triples:positive integers a,b,andc such that a2+b2=c2. A Pythagorean triple of course takes its name from the fact that it allows you to draw a right-angled triangle with sides of those integer lengths.The classic example is the(3,4,5)triangle. Given any Pythagorean triple, we can generate more of them simply by multiplying all the numbers in the triple by any positive number as the Pythagorean equation will continue to hold. For example,we can double the previous example to get the(6,8,10)triple.This, however, gives a similar triangle, one of exactly the same proportions, as the change is only a matter of scale and not of shape. Given thefirst triangle, wefind the second Pythagorean triple simply by measuring the lengths of the sides in units that are half the size of the original units, thereby doubling the numerical size of the dimensions. There are, however, genuinely different triples such as those representing the(5,12,13)and the(65,72,97)right-angled triangles.
In order to describe all Pythagorean triples, therefore, it is enough to do the job for all triples(a,b,c)where the hcf of the three numbers is 1, as all others are merely scaled-up versions of these.The recipe is as follows. Take any pair of coprime positive integers mand n, with one of them even, and let mdenote the larger. Form the triple given by a=2mn, b=m2-n2 and c=m2+n2.Thethree numbers a,b,andc then give you a Pythagorean triple(the algebra is easily checked)and the three numbers have no common factor(also not difficult to verify). The three examples above arise bytakingm=2andn=1inthefirstcase,m=3andn=2inthe second, while for the last triangle we have m=9,n=4.Ittakes more work to verify the converse:any such Pythagorean triple arises in this fashion for suitably chosen values of mand n,and what is more, the representation is unique so that two different pairs(m,n)cannot yield the same triple(a,b,c).
The corresponding equation for cubes and higher powers has no solution at all:for any power n≥3, there are no positive integer triples x, y,andz such that xn+yn=zn. This is the famousFermat’s Last Theorem, which in future might be known as Wiles’s Theorem as it wasfinally proved in the 1990s by Sir Andrew Wiles. Even for the case of cubes,first solved by Euler, this is a very difficult problem. It is, however, relatively easy to show that the sum of two fourth powers is never a square(and so certainly not a fourth power). This is enough to reduce the problem to the case where nis a prime p(meaning that if we solved the problem for all prime exponents, the general result would follow at once), and indeed the problem was solved for so-called regular primes in the19th century. However, the full solution was only realized as a consequence of Wiles settling a deep question called the Shimura–Taniyama Conjecture.
Versions of the Pell equation were studied by Diophantus himself around AD 150 but the equation was solved by the great Indian mathematician Brahmagupta(AD 628)and his methods were improved upon by Bhaskara II(AD 1150), who showed how to create new solutions from a seed solution. In Europe, it was Fermat who exhorted mathematicians to turn their attention to Pell’s equation and the complete theory is credited to the reknowned French mathematician Joseph-Louis Lagrange(1736–1813)(the English appellation‘Pell’is an historic accident).
Fibonacci and continued fractions
Recall the sequence of numbers,1,1,2,3,5,8,13,21,···discovered by Fibonacci and introduced in Chapter 5. Take a pair of successive terms in this sequence and write the corresponding ratio as 1 plus a fraction. If we now‘Egyptianize’this fraction by repeatedly dividing top and bottom by the numerator, a striking pattern emerges. Take, for instance
We obtain a multi-floored fraction consisting entirely of 1s, and each preceding ratio of Fibonacci numbers appears as we wind through the calculation. This must happen every time:by the very way these numbers are defined, each Fibonacci number is less than twice the next, and so the result of the division will leave a quotient of 1 and the remainder is the preceding Fibonacci number. You will recall that the ratio of successive Fibonacci numbers approaches the Golden Ratio,τ,and so this suggests thatτ is the limiting value of the continued fraction consisting entirely of 1s.
The type of continued fractions that emerge from this process are intrinsically important. When we approximate an irrational number yby rationals we naturally turn to the decimal representation of y. This is excellent for general calculations but,being tied to a particular base, is not mathematically natural.Essential to the nature of y is how well our number y can be approximated by fractions with relatively small denominators. Is there any way tofind a series of fractions that best deals with the conflicting demands of approximating y to a high degree of accuracy while keeping the denominators relatively small?The answer lies in the continued fraction representation of a number that does this through its truncations at ever lower floors.
The special example afforded by the Golden Ratio opens the door to the idea that we may be able to represent other irrational numbers not byfinite continued fractions(which are obviously just rational themselves)but by infinite ones. But how is the continued fraction of a number a produced? The reader will need to tolerate a little algebraic trickery in order to see this in action,but here is how it goes.
Next we get