PLAYING WITH INFINITY
I ended the page on the Origin of Quantum Probability with the statement that the number of universes in the multiverse was large but not infinite. We shall see why this is true in the next page, The Finite Multiverse, and, moreover, we shall find that each universe in our multiverse is also finite (in both space and time). Before turning to that page, though, we need to play with infinity.
Figure 1 shows how different categories of numbers are used. The basic “counting numbers”, 0, 1, 2, 3,… are called the natural numbers. Although we usually start with the number “one” when we are counting, zero is generally included in the set of natural numbers nowadays.
The set of integers is formed by adding the natural numbers to their negative counterparts (the negative of zero, of course, is the same as zero itself).
Rational numbers are formed by dividing any integer by any other integer.
Two-and-a-half thousand years ago, Pythagoras and his followers believed that all numbers were either natural numbers or (positive) rational numbers (the latter are so called because they are ratios of two natural numbers). So, for instance, pi, the ratio of the circumference of a circle to its diameter, would be the fraction 22 divided by 7 and the square root of 2 would be the fraction 141 divided by 100. These are pretty good approximations to the correct values, but, as you can easily check with a calculator, the fraction for pi is out by about 0.04 percent, and, if you square the above fraction for √2, you get 1.9881 and not simply 2.
Of course, such differences could not have been measured at the time of Pythagoras, but it was one of his followers who discovered a mathematical proof that the square root of 2 could never be expressed as the ratio of any two natural numbers (and, according to legend, he was drowned for upsetting the applecart). Since the square root of 2 cannot be written as a ratio of two natural numbers, it is called irrational.
The set of rational numbers plus the set of irrational numbers form the set of real numbers. You can also picture a real number as the position of a point along a line, measured to infinite accuracy.
How many natural numbers are there? If you give me a very large number – say, a googolplex (which is 10 multiplied by itself a special number of times, where that special number is 1 with 100 zeros after it) – then I can always add one to it. So there is never a natural number that does not have a successor. We say that there is an infinite number of natural numbers.
Looking at Figure 1, you might be tempted to say: “the set of rational numbers must be bigger than the set of natural numbers, since the set of natural numbers is contained within the set of rational numbers (in other words, the red ellipse is contained within the blue rectangle on the left).” Indeed, between any two rational numbers you can find an infinite number of other rational numbers. For example, between the numbers 1 and 2 – which are rational numbers because you can write them as 1/1 and 2/1 – there are indefinitely many fractions: ½, ¼, ¾, ⅓, ⅔… and so on.
So you might even think that the size of the set of positive rational numbers is infinitely greater than the size of the set of natural numbers. After all, we have just seen that, between any two natural numbers, there are infinitely many positive rational numbers. (Notice, by the way, that we are not considering negative rational numbers at the moment.)
However, comparing infinite quantities is not always straightforward. Mathematicians use the term cardinality when talking about the “sizes” of infinite quantities.
The term cardinality was first used by Georg Cantor. He was a German mathematician, and pioneer of the mysteriously sounding transfinite that I refer to on the Plexus page. This is a term he invented in order not to ruffle the feathers of the late-nineteenth-century mathematical establishment for whom dealing with raw “infinity” would have been anathema. (We shall encounter the transfinite again in the page on Gödel’s Incompleteness Theorems as well as in the page on the Fundamental Structure of the Plexus.)
In spite of his linguistic contortions, many powerful mathematicians (and, unexpectedly, some Christian theologians) took a dim view of his work. The founder of the respectable Swedish journal Acta Mathematica, which had previously accepted some of Cantor’s papers, eventually discouraged him from submitting any more, saying his work was “about one hundred years too soon”. A particularly shocking result that he derived was that the cardinality – the size – of the set of real numbers is greater than that of the set of natural numbers.
To show this, we start by proving that the cardinality of the set of rational numbers is the same as that of the natural numbers.
Although Cantor published his proof in 1874, I shall use his so-called diagonal argument, published 17 years later, because it is pictorial and easier to understand.
The table in Figure 2 shows every possible positive rational number, expressed as a numerator sitting over a denominator. How do I know that the table contains every possible positive rational number? Well, the number of horizontal rows extends to infinity. In the first row, every numerator is “1”. In the second row, every numerator is “2”. In the third row, every numerator is “3”, and so on. Similarly, the number of vertical columns extends to infinity. In the first column, every denominator is “1”; in the second column, every denominator is “2”; in the third column, every denominator is “3”, and so on. So this table captures every possible combination of numerator and denominator. Therefore, it contains every positive rational number.
Notice, by the way, that the table contains many duplicates. By this, I mean that 1/1, 2/2, 3/3 and so on are all the same size. So, too, are 1/2 and 2/4, or 1/3 and 2/6 and so on. So, while it is still correct to say that the table contains all of the positive rational numbers, when we make a list of them, we can choose to leave out the duplicates as we come to them.
We start making the list by drawing the light-green zigzag line in the table, and then writing down each rational number that we come to, leaving out the duplicates. As we do this, we pair up each successive rational on the list with each of the natural numbers in turn, just as you see in the two columns at the right edge of the table. We connect each pair of numbers – the natural number on the left and the corresponding rational number on the right – with a double-headed arrow.
This two-column list, with its double-headed arrows, shows that there is a one-to-one correspondence between the natural numbers and the positive rational numbers. In other words, you can count the positive rational numbers, and you never run out of natural numbers to count them with. So the cardinalities of the set of natural numbers and the set of positive rational numbers are the same.
What about negative rational numbers? If we include them, will the set not now be infinitely greater than the set of natural numbers? Let us see – look at Figure 3.
In the left of the figure, I have just copied the list of positive rational numbers that we produced from the table in the previous figure. To the right of Figure 3, I have used the same list, except that for every positive rational number, I have inserted its negative immediately below. However, we still don’t run out of natural numbers to count both types together, the positives and the negatives: there is, once again, a one-to-one correspondence between the natural numbers and the rational numbers – this time, including negative rational numbers. This was Cantor’s astonishing result: the cardinalities of the set of natural numbers and the set of rational numbers are the same, even though there are infinitely many more rational numbers than natural numbers!
When we come across a set of numbers such as the rational numbers that you can put into one-to-one correspondence with the natural numbers, we say that such a set is countable or, to use a rarer adjective, denumerable. Since the set of rational numbers is also infinite, we can also say that it is countably infinite. Now you might ask: just as the set of rational numbers is countably infinite, is the set of irrational numbers, including all the negative irrational numbers, also countably infinite? In other words, can we put the irrational numbers into one-to-one correspondence with the natural numbers just as we did with the rational numbers?
In order to answer this, think of the set of numbers formed from a union of the rational numbers and the irrational numbers (the sets in the two blue rectangles in Figure 1). As I said earlier, this is what we call the set of real numbers. If the set of real numbers is countably infinite, and we already know that one part of the set, the set of rational numbers, is countably infinite, then so must the set of irrational numbers be countably infinite. So how can we tell whether the set of real numbers is countably infinite?
In fact, Cantor published a proof in 1874 that the set of real numbers is not countable. However, to show this, I shall use his so-called diagonal argument, published 17 years later, because it is pictorial and easier to understand.
In many real numbers the digits after the decimal place will all be zeros, as in the natural number 2 (2.000000…) (see footnote 1) and there will be real numbers with only a few non-zero digits as in the rational number ¾ (0.750000…). In some real numbers the digits will repeat indefinitely as in the rational number 17⅓ (17.333333…) and in others the digits will go on forever without any pattern as in the irrational number pi (3.141592…). (Notice that mathematicians use the term “transcendental” for special numbers like pi whose digits have no pattern, but pi is still also an irrational number because it isn’t an exact ratio of any two natural numbers.)
Suppose that, like the set of rational numbers, the set of real numbers is countable. In that case, we can make a list of them showing a one-to-one correspondence with the list of natural numbers, just as we did with the list of rational numbers in Figure 3. To make things simpler for ourselves, let us just consider the list of real numbers between the numbers 0.000… and 1.000… It will be sufficient to do this because, if we find that even this tiny fraction of all the real numbers cannot be counted by the natural numbers, then neither can the complete list of real numbers.
In Figure 4 you can see the first few real numbers in the list I have constructed. It doesn’t matter what order we put them into, as long as we allocate the natural numbers in turn to each one as we go down the list. Just for fun, I started with pi/10 (I couldn’t use pi itself because we are just looking at numbers between 0 and 1). The other numbers have some significance, too, but don’t waste any time trying to figure out what they stand for (for instance, the digits in the number on row 8 will be the Saturday lottery winners on 24 July 2027).
I have only chosen to show the first nine digits of each real number on the list but, of course, each one has an infinitely long line of digits after the decimal point. Also, I have only shown the first nine real numbers on the list, but, as you know, the list is infinitely long. You can think of the heavy horizontal line at the bottom as indicating that the list goes on forever.
You will see that, in each real number, I have highlighted a digit in red, starting with the first digit after the decimal point in the first number, the second digit in the second number, and so on. So we have an infinite sequence of digits forming a diagonal across the list. I have copied down this sequence below the heavy line and turned it into a real number by prefacing the digits in the diagonal with a decimal point.
The last thing I did was to use this diagonal number to construct another real number (in blue) directly below it. For every digit in the diagonal number, I wrote a digit below, making sure that the digit below was different from the digit in the diagonal number above it. There doesn’t have to be a rule connecting the digits in the diagonal with the digits below – they don’t, for example, have to differ by 1 – just as long as they are different.
Now the question is – where does this new number, the one I have written below the diagonal number – fit into the list of real numbers? Remember – we have supposed that the list of real numbers is countable; that is, we assume that there is a one-to-one correspondence between all of the natural numbers and all of the real numbers. In other words, we assume that every real number is on the list that I started in Figure 4 – if that were not so, there would be one or more real numbers not paired up with a natural number (because every possible natural number would already be paired up with a real number on that list).
So, if the list of real numbers is countable, then the real number that I constructed in blue must be somewhere on that list. Clearly, it is not the first number on the list. The first digit of the first number on the list is 3, but I made the first digit of the new number different – I chose 8. It is obviously not the second number on the list, because the second digit of the second number on the list is 7, whereas I chose 2 for the second digit of the new number.
You can go on right down the list of real numbers. The one millionth digit of the millionth number on the list happens to be 4 (although I didn’t have space to show it!), but I made the millionth digit of the new number different – I chose 5.
You see how this goes. The new number cannot be any number on the list of real numbers because of the way I made each digit in the new number differ from a digit in each successive number on the list.
Now you might think – OK, we’ll just add the new number to the list of real numbers. Then the list will be complete. No, not so fast! No matter where we put the new number, we can make a new diagonal number that will include our new number, and we’ll still end up with a number that is not on what we thought was a complete list. That process will go on forever.
So it was wrong in the first place to suppose that the list contained all of the real numbers. Like participants trying to find a seat in a game of musical chairs, there are always going to be more real numbers than there are natural numbers for them to sit upon (see footnote 2). The set of real numbers is not countable.
So this was how Cantor proved that the cardinality – the size – of the set of real numbers is greater than that of the natural numbers. If you try to put the real numbers into one-to-one correspondence with the natural numbers, there will always be some reals – actually, an infinite number of reals – left over. The set of real numbers is uncountable. To distinguish between the sizes of the two sets, Cantor invented the term ℵ0 (“aleph-nought” – or, in the USA, “aleph-null”) – for the cardinality of the set of natural numbers (ℵ – “aleph” – is the first letter of the Hebrew alphabet) and ℵ1 (“aleph-one”) for the cardinality of the set of real numbers, where ℵ1 is infinitely greater than ℵ0 (see footnote 3).
Knowing this, we can now work out whether the set of irrational numbers is countable. The set of real numbers is made by adding the set of rational numbers to the set of irrationals. The set of rational numbers is countable. So, if the set of irrational numbers were also countable, then the set of real numbers would be countable too. But the set of real numbers is uncountable, as we have just seen. Therefore, the set of irrational numbers must be uncountable. The cardinality of the set of irrational numbers is aleph-one, just like that of the reals, and infinitely greater than the cardinality, aleph-nought, of the natural numbers.
In this page, we have seen that, while sets may contain infinite numbers of elements, the cardinalities of these sets – their sizes” – are not all the same. We use the trick of pairing up the elements of the sets, one by one, with the natural numbers. If we don’t run out of natural numbers for this pairing process even if the number of elements in the set is infinite, then the set is countable, and we say that it is countably infinite. The cardinality of all such countably infinite sets is the same as that of the natural numbers, aleph-nought.
We can use the pairing trick to show that it doesn’t make sense to try to divide a countably infinite number by another countably infinite number. For instance, if I want to know the ratio of the number of even numbers to the number of odd numbers, I might try pairing every even number with every odd number (see the left-hand table in Figure 5). In that case, it would seem that there are as many even numbers as odd numbers, so that the ratio would be 1:1.
However, because the numbers of elements in the set of even numbers and in the set of odd numbers is countably infinite, you can do the pairing in an infinite number of different ways. The right-hand table shows a pairing where every successive pair of even numbers is matched to every successive single odd number. As in the first case, you don’t run out of even numbers or odd numbers, so that, again, there is a one-to-one correspondence between pairs of even numbers and single odd numbers. So you might as well conclude that the ratio of even numbers to odd numbers is 2:1 instead of 1:1. This just shows that the idea of a ratio of two countably infinite sets is misguided. No such ratio exists. We shall see in the Finite Multiverse page that this is a crucial clue to the structure of the multiverse.
If, on the other hand, we do run out of natural numbers with which to pair elements of an infinite set, then the cardinality of such a set is greater than that of the natural numbers – it is aleph-one. We shall return to this also in the Finite Multiverse page, when we consider whether the universe is discrete or continuous.
Click here to go to Tree Structure of the Many Worlds Interpretation [13]