The Beginning of Infinity

by David Deutsch

  The set of natural numbers has as many members as a part of itself.

  In the upper line in the illustration, every natural number appears exactly once. The lower line contains only part of that set: the natural numbers starting at 2. The illustration tallies the two sets – mathematicians call it a ‘one-to-one correspondence’ – to prove that there are equally many numbers in each.

  The mathematician David Hilbert devised a thought experiment to illustrate some of the intuitions that one has to drop when reasoning about infinity. He imagined a hotel with infinitely many rooms: Infinity Hotel. The rooms are numbered with the natural numbers, starting with 1 and ending with – what?

  The last room number is not infinity. First of all, there is no last room. The idea that any numbered set of rooms has a highest-numbered member is the first intuition from everyday life that we have to drop. Second, in any finite hotel whose rooms were numbered from 1, there would be a room whose number equalled the total number of rooms, and other rooms whose numbers were close to that: if there were ten rooms, one of them would be room number ten, and there would be a room number nine as well. But in Infinity Hotel, where the number of rooms is infinity, all the rooms have numbers infinitely far below infinity.

  The beginning of infinity – the rooms in Infinity Hotel

  Now imagine that Infinity Hotel is fully occupied. Each room contains one guest and cannot contain more. With finite hotels, ‘fully occupied’ is the same thing as ‘no room for more guests’. But Infinity Hotel always has room for more. One of the conditions of staying there is that guests have to change rooms if asked to by the management. So, if a new guest arrives, the management just announce over the public-address system, ‘Will all guests please move immediately to the room numbered one more than their current room.’ Thus, in the manner of the first illustration in this chapter, the existing occupant of room 1 moves to room 2, whose occupant moves to room 3, and so on. What happens at the last room? There is no last room, and hence no problem about what happens there. The new arrival can now move into room 1. At Infinity Hotel, it is never necessary to make a reservation.

  Evidently no such place as Infinity Hotel could exist in our universe, because it violates several laws of physics. However, this is a mathematical thought experiment, so the only constraint on the imaginary laws of physics is that they be consistent. It is because of the requirement that they be consistent that they are counter-intuitive: intuitions about infinity are often illogical.

  It is a bit awkward to have to keep changing rooms – though they are all identical and are freshly made up every time a guest moves in. But guests love staying at Infinity Hotel. That is because it is cheap – only a dollar a night – yet extraordinarily luxurious. How is that possible? Every day, when the management receive all the room rents of one dollar per room, they spend the income as follows. With the dollars they received from the rooms numbered 1 to 1000, they buy complimentary champagne, strawberries, housekeeping services and all the other overheads, just for room 1. With the dollars they received from the rooms numbered 1001 to 2000, they do the same for room 2, and so on. In this way, each room receives several hundred dollars’ worth of goods and services every day, and the management make a profit as well, all from their income of one dollar per room.

  Word gets around, and one day an infinitely long train pulls up at the local station, containing infinitely many people wanting to stay at the hotel. Making infinitely many public-address announcements would take too long (and, anyway, the hotel rules say that each guest can be asked to perform only a finite number of actions per day), but no matter. The management merely announce, ‘Will all guests please move immediately to the room whose number is double that of their current room.’ Obviously they can all do that, and afterwards the only occupied rooms are the even numbered ones, leaving the odd-numbered ones free for the new arrivals. That is exactly enough to receive the infinitely many new guests, because there are exactly as many odd numbers as there are natural numbers, as illustrated overleaf:

  There are exactly as many odd numbers as there are natural numbers.

  So the first new arrival goes to room 1, the second to room 3, and so on.

  Then, one day, an infinite number of infinitely long trains arrive at the station, all full of guests for the hotel. But the managers are still unperturbed. They just make a slightly more complicated announcement, which readers who are familiar with mathematical terminology can see in this footnote.* The upshot is: everyone is accommodated.

  However, it is mathematically possible to overwhelm the capacity of Infinity Hotel. In a remarkable series of discoveries in the 1870s, Cantor proved, among other things, that not all infinities are equal. In particular, the infinity of the continuum – the number of points in a finite line (which is the same as the number of points in the whole of space or spacetime) – is much larger than the infinity of the natural numbers. Cantor proved this by proving that there can be no one-to-one correspondence between the natural numbers and the points in a line: that set of points has a higher order of infinity than the set of natural numbers.

  Here is a version of his proof – known as the diagonal argument. Imagine a one-centimetre-thick pack of cards, each one so thin that there is one of them for every ‘real number’ of centimetres between 0 and 1. Real numbers can be defined as the decimal numbers between those limits, such as 0.7071. . ., where the ellipsis again denotes a continuation that may be infinitely long. It is impossible to deal out one of these cards to each room of Infinity Hotel. For suppose that the cards were so distributed. We can prove that this entails a contradiction. It would mean that cards had been assigned to rooms in something like the manner of the table below. (The particular numbers illustrated are not significant: we are going to prove that real numbers cannot be assigned in any order.)

  Cantor’s diagonal argument

  Look at the infinite sequence of digits highlighted in bold – namely ‘6996. . .’. Then consider a decimal number constructed as follows: it starts with zero followed by a decimal point, and continues arbitrarily, except that each of its digits must differ from the corresponding digit in the infinite sequence ‘6996. . .’. For instance, we could choose a number such as ‘0.5885. . .’. The card with the number thus constructed cannot have been assigned to any room. For it differs in its first digit from that of the card assigned to room 1, and in its second digit from that of the card assigned to room 2, and so on. Thus it differs from all the cards that have been assigned to rooms, and so the original assumption that all the cards had been so assigned has led to a contradiction.

  An infinity that is small enough to be placed in one-to-one correspondence with the natural numbers is called a ‘countable infinity’ – rather an unfortunate term, because no one can count up to infinity. But it has the connotation that every element of a countably infinite set could in principle be reached by counting those elements in some suitable order. Larger infinities are called uncountable. So, there is an uncountable infinity of real numbers between any two distinct limits. Furthermore, there are uncountably many orders of infinity, each too large to be put into one-to-one correspondence with the lower ones.

  Another important uncountable set is the set of all logically possible reassignments of guests to rooms in Infinity Hotel (or, as the mathematicians put it, all possible permutations of the natural numbers). You can easily prove that if you imagine any one reassignment specified in an infinitely long table, like this:

  Specifying one reassignment of guests

  Then imagine all possible reassignments listed one below the other, thus ‘counting’ them. The diagonal argument applied to this list will prove that the list is impossible, and hence that the set of all possible reassignments is uncountable.

  Since the management of Infinity Hotel have to specify a reassignment in the form of a public-address announcement, the specification must consist of a finite sequence of words – and hence a finite sequence of characters from some alphabet.
The set of such sequences is countable and therefore infinitely smaller than the set of possible reassignment. That means that only an infinitesimal proportion of all logically possible reassignments can be specified. This is a remarkable limitation on the apparently limitless power of Infinity Hotel’s management to shuffle the guests around. Almost all ways in which the guests could, as a matter of logic, be distributed among the rooms are unattainable.

  Infinity Hotel has a unique, self-sufficient waste-disposal system. Every day, the management first rearrange the guests in a way that ensures that all rooms are occupied. Then they make the following announcement. ‘Within the next minute, will all guests please bag their trash and give it to the guest in the next higher-numbered room. Should you receive a bag during that minute, then pass it on within the following half minute. Should you receive a bag during that half minute, pass it on within the following quarter minute, and so on.’ To comply, the guests have to work fast – but none of them has to work infinitely fast, or handle infinitely many bags. Each of them performs a finite number of actions, as per the hotel rules. After two minutes, all these trash-moving actions have ceased. So, two minutes after they begin, none of the guests has any trash left.

  Infinity Hotel’s waste-disposal system

  All the trash in the hotel has disappeared from the universe. It is nowhere. No one has put it ‘nowhere’: every guest has merely moved some of it into another room. The ‘nowhere’ where all that trash has gone is called, in physics, a singularity. Singularities may well happen in reality, inside black holes and elsewhere. But I digress: at the moment, we are still discussing mathematics, not physics.

  Of course, Infinity Hotel has infinitely many staff. Several of them are assigned to look after each guest. But the staff themselves are treated as guests in the hotel, staying in numbered rooms and receiving exactly the same benefits as every other guest: each of them has several other staff assigned to their welfare. However, they are not allowed to ask those staff to do their work for them. That is because, if they all did this, the hotel would grind to a halt. Infinity is not magic. It has logical rules: that is the whole point of the Infinity Hotel thought experiment.

  The fallacious idea of delegating all one’s work to other staff in higher-numbered rooms is called an infinite regress. It is one of the things that one cannot validly do with infinity. There is an old joke about the heckler who interrupts an astrophysics lecture to insist that the Earth is flat and supported on the back of elephants standing on a giant turtle. ‘What supports the turtle?’ asks the lecturer. ‘Another turtle.’ ‘What supports that turtle?’ ‘You can’t fool me,’ replies the heckler triumphantly: ‘it’s turtles from there on down.’ That theory is a bad explanation not because it fails to explain everything (no theory does), but because what it leaves unexplained is effectively the same as what it purports to explain in the first place. (The theory that the designer of the biosphere was designed by another designer, and so on ad infinitum, is another example of an infinite regress.)

  One day in Infinity Hotel, a guest’s pet puppy happens to climb into a trash bag. The owner does not notice, and passes the bag, with the puppy, to the next room.

  Within two minutes the puppy is nowhere. The distraught owner phones the front desk. The receptionist announces over the publicaddress system, ‘We apologize for the inconvenience, but an item of value has been inadvertently thrown away. Will all guests please undo all the trash-moving actions that they have just performed, in reverse order, starting as soon as you receive a trash bag from the next-higher-numbered room.’

  But to no avail. None of the guests return any bags, because their fellow guests in the highernumbered rooms are not returning any either. It was no exaggeration to say that the bags are nowhere. They have not been stuffed into a mythical ‘room number infinity’. They no longer exist; nor does the puppy. No one has done anything to the puppy except move it to another numbered room, within the hotel. Yet it is not in any room. It is not anywhere in the hotel, or anywhere else. In a finite hotel, if you move an object from room to room, in however complicated a pattern, it will end up in one of those rooms. Not so with an infinite number of rooms. Every individual action that the guests performed was both harmless to the puppy and perfectly reversible. Yet, taken together, those actions annihilated the puppy and cannot be reversed.

  Reversing them cannot work, because, if it did, there would be no explanation for why a puppy arrived at its owner’s room and not a kitten. If a puppy did arrive, the explanation would have to be that a puppy was passed down from the next-higher-numbered room – and so on. But that whole infinite sequence of explanations never gets round to explaining ‘why a puppy?’ It is an infinite regress.

  What if, one day, a puppy did just arrive at room 1, having been passed down through all the rooms? That is not logically impossible: it would merely lack an explanation. In physics, the ‘nowhere’ from which such a puppy would have come is called a ‘naked singularity’. Naked singularities appear in some speculative theories in physics, but such theories are rightly criticized on the grounds that they cannot make predictions. As Hawking once put it, ‘Television sets could come out [of a naked singularity].’ It would be different if there were a law of nature determining what comes out – for in that case there would be no infinite regress and the singularity would not be ‘naked’. The Big Bang may have been a singularity of that relatively benign type.

  I said that the rooms are identical, but they do differ in one respect: their room numbers. So, given the types of tasks that the management request from time to time, the low-numbered rooms are the most desirable. For instance, the guest in room 1 has the unique privilege of never having to deal with anyone else’s trash. Moving to room 1 feels like winning first prize in a lottery. Moving to room 2 feels only slightly less so. But every guest has a room number that is unusually close to the beginning. So every guest in the hotel is more privileged than almost all other guests. The clichéd politician’s promise to favour everyone can be honoured in Infinity Hotel.

  Every room is at the beginning of infinity. That is one of the attributes of the unbounded growth of knowledge too: we are only just scratching the surface, and shall never be doing anything else.

  So there is no such thing as a typical room number at Infinity Hotel. Every room number is untypically close to the beginning. The intuitive idea that there must be ‘typical’ or ‘average’ members of any set of values is false for infinite sets. The same is true of the intuitive ideas of ‘rare’ and ‘common’. We might think that half of all natural numbers are odd, and half even – so that odd and even numbers are equally common among the natural numbers. But consider the following rearrangement:

  A rearrangement of the natural numbers that makes it look as though one-third of them are odd

  That makes it look as though the odd numbers are only half as common as even ones. Similarly, we could make it look as though the odd numbers were one in a million or any other proportion. So the intuitive notion of a proportion of the members of a set does not necessarily apply to infinite sets either.

  After the shocking loss of the puppy, the management of Infinity Hotel want to restore the morale of the guests, so they arrange a surprise. They announce that every guest will receive a complimentary copy of either The Beginning of Infinity or my previous book, The Fabric of Reality. They distribute them as follows: they dispatch a copy of the older book to every millionth room, and a copy of the newer book to each remaining room.

  Suppose that you are a guest at the hotel. A book – gift-wrapped in opaque paper – appears in your room’s delivery chute. You are hoping that it will be the newer book, because you have already read the old one. You are fairly confident that it will be, because, after all, what are the chances that your room is one of those that receive the old book? Exactly one in a million, it seems.

  But, before you have a chance to open the package, there is an announcement. Everyone is to change rooms, to a numb
er designated on a card that will come through the chute. The announcement also mentions that the new allocation will move all the recipients of one of the books to odd-numbered rooms, and the recipients of the other book to even-numbered ones, but it does not say which is which. So you cannot tell, from your new room number, which book you have received. Of course there is no problem with filling the rooms in this manner: both books had infinitely many recipients.

  Your card arrives and you move to your new room. Are you now any less sure about which of the two books you have received? Presumably not. By your previous reasoning, there is now only a one in two chance that your book is The Beginning of Infinity, because it is now in ‘half the rooms’. Since that is a contradiction, your method of assessing those probabilities must have been wrong. Indeed, all methods of assessing them are wrong, because – as this example shows – in Infinity Hotel there is no such thing as the probability that you have received the one book or the other.

  Mathematically, this is nothing momentous. The example merely demonstrates again that the attributes probable or improbable, rare or common, typical or untypical have literally no meaning in regard to comparing infinite sets of natural numbers.

  But, when we turn to physics, it is bad news for anthropic arguments. Imagine an infinite set of universes, all with the same laws of physics except that one particular physical constant, let us call it D, has a different value in each. (Strictly speaking, we should imagine an uncountable infinity of universes, like those infinitely thin cards – but that only makes the problem I am about to describe worse, so let us keep things simple.) Assume that, of these universes, infinitely many have values of D that produce astrophysicists, and infinitely many have values that do not. Then let us number the universes in such a way that all those with astrophysicists have even numbers and all the ones without astrophysicists have odd numbers.