• Choose a category
• All
• Classic-Fiction

By Root 601 0

the subscript 0, and said that this was the cardinality of the set of natural numbers, or {1, 2, 3, 4, 5…}. Every set whose members can be put in a one-to-one correspondence with the natural numbers also has cardinality . So, because there is a one-to-one correspondence between the natural numbers and their squares, the set of squares {1, 4, 9, 16, 25…} has cardinality . Likewise, the set of odd numbers {1, 3, 5, 7, 9…}, the set of prime numbers {2, 3, 5, 7, 11…} and the set of numbers with 666 in them {666, 1666, 2666, 3666…}, all have cardinality . If you have a set with an infinite number of members, and it is possible to count its members one by one so that eventually every member will be reached, then the cardinality of the set is . For this reason, is also known as a ‘countable infinity’. The reason this is exciting is because Cantor went on to show that we can go higher. Large though it may be, is merely the baby in Cantor’s family of infinities.

I’ll introduce you to an infinity larger than with the help of a story David Hilbert is said to have used in his lectures that concerns a hotel with a countably infinite, or , number of rooms. This well-known establishment, much loved by mathematicians, is sometimes called the Hilbert Hotel.

In the Hilbert Hotel there is an infinite number of rooms and they are numbered 1, 2, 3, 4…One day a traveller arrives at reception only to find that the hotel is full. He asks if there is any way a room can be found for him. The receptionist replies that of course there is! All the management needs to do is to reassign guests to different rooms in the following way: moving the guest in Room 1 to Room 2, moving the guest in Room 2 to Room 3, and so on, moving everyone in Room n to Room n + 1. If this is done, then every guest still has a room, and Room 1 is freed up for the new arrival. Perfect!

The following day a more complicated situation presents itself. A bus arrives, with all the passengers needing rooms. This bus has an infinite number of seats, numbered 1, 2, 3 and so on, all of which are occupied. Is there any way that a room can be found for each and very one of the passengers? In other words, even though the hotel is full, can the receptionist reshuffle the guests into different rooms in a way that leaves an infinite number of free rooms for the bus passengers? Easy peasy, comes the reply. All the management needs to do this time is to move every guest to the room numbered double the room he or she is already in, which takes care of Rooms 2, 4, 6, 8…This leaves all the rooms with odd numbers empty, and the bus passengers can be given the keys for those. The passenger on the first seat gets Room 1, the first odd number, the passenger on the second seat gets Room 3, the second odd number, and so on.

On the third day, even more buses arrive at the Hilbert Hotel. In fact, an infinite number of buses arrives. The buses are lined up outside, with Bus 1 next to Bus 2, which is next to Bus 3, and so on. Each bus has an infinite number of passengers, like the bus that arrived the day before. And, of course, every passenger needs a room. Is there a way to find every passenger in every bus a room in the (already full) Hilbert Hotel?

No problem, says the receptionist. First, he needs to clear an infinite number of rooms. He does this by the trick he used the day before – move everyone to a room with twice the room number. This leaves all the odd-numbered rooms free. In order to fit in the infinite coach parties, all he needs to do is find a way of counting all the passengers, since once he has found a method, he can assign the first passenger to Room 1, the second to Room 3, the third to Room 5, and so on.

He does it like this: for each bus, list the passengers by seat, as in the table below. Each passenger is therefore represented by the form m/n where m is the number of the bus they are on and n is their seat number. If we start at the passenger in the first seat in the first bus (person 1/1), and then form the zigzag pattern below, by letting the second person be the passenger