Monday, April 24, 2006

Hotel Infinity; some infinities are larger than others

Note: The story of Hotel Infinity has absolutely nothing to do with the fact that some infinities are larger than others. That is an altogether different story that is treated seperarely below.

I’ll start off by narrating the story of Hotel Infinity before talking about the actual topic of today.

Hotel Infinity is an infinitely large hotel with an infinite number of rooms. The rooms are labelled with the natural numbers 1, 2, 3, 4…

On a particularly busy weekend, every room was occupied. A man came into the lobby, asking for a room. Despite the every room being occupied, the manager told him of course he may have a room.

A message was sent requesting existing guests to move from their current rooms to the adjacent room. The guest in room 1 moved to room 2; the guest in room 2 moved to room 3; the guest in room 3 moved to room 4…
Thus room 1 was made empty, and the man had a place to spend the night.

The next day, an unexpected busload of infinitely many tourists turned up. To accommodate them, the manager cannot ask the guests to advance their room numbers by infinity- that would be senseless.

Instead, guests were requested to move from their current rooms to the room whose number is double of the current room number. The guest in room 1 moved to room 2; the guest in room 2 moved to room 4; the guest in room 3 moved to room 6…

Thus all the odd numbered rooms 1, 3, 5, 7… were made empty and the infinite busload of tourists had rooms to stay.

It so happened that the Infinity Chain owns an infinite number of Hotel Infinities in all parts of the universe. The Infinity Chain was downsizing, and our Hotel Infinity would be the only to remain. Guests in all other hotels would be moved into the remaining Hotel Infinity.

The posed a headache to the manager, until he devised a plan. Each hotel was to be assigned a number, starting with his own hotel, labelled 1. The other hotels would be labelled 2, 3, 4, 5…

To uniquely identify the guests, they needed to quote their hotel numbers and room numbers in the following format, (H, R) such that a guest from the fifth hotel’s 9th room would be labelled (5,9).

These numbers were then arranged in the following order:
(1,2) (2,1)
(1,3) (2,2) (3,1)
(1,4) (2,3) (3,2) (4,1)

The ordering is done such that the sum of H and R in each row is the same. For example, the second row of (1,2) (2,1) results in 1+2 and 2+1, both equalling to 3.

Having ordered the infinite hotels full of infinite guests, they can then be shuffled into the only remaining hotel infinity. The room assignation is such that their new room numbers in hotel infinity would follow their order in the chart:


And thus Hotel Infinity has demonstrated it can accommodate an infinite number of infinities.

By the way, this final trick was part of a proof to show that there are equally as many rational numbers as natural numbers by associating one rational number with exactly one natural numbera. Instead of H and R, the terms were Numerator and Denominator, and only relatively prime N and D were allowed into the list to disallow double counting. After all, 1/2, 2/4 and 54/108 are same and only need to be counted once.


Some infinities are larger than others

Now, consider a set of three elements, such as
S = {A,B,C}

There are 8 subsets of this set S:
a = {} the empty set that contains none of the 3 elements
b = {A}
c = {B}
d = {C}
e = {A,B}
f = {A,C}
g = {B,C}
h = {A,B,C}

The set S contains 3 elements, but there are 8 subsets of S, each being a unique combination of the elements of S.

If we collectively call the subsets of S as another set, S2 = {a,b,c,d,e,f,g,h}, then there are 256 possible subsets of S2 (since 2^8 = 256).

If the original set S did not contain 3 capital letters A, B and C, but instead contained ALL the natural numbers,
S= {1, 2, 3, 4, 5, 6… }
Clearly, the size of S in infinite.

However, as we have seen with the illustration using 3 capital letters, there are more possible subsets of S than the number of elements of S.

The number of elements in S is infinite, but the number of elements in S2 is infinitely larger than S.

The quantity of natural numbers (the size of S) is then denoted by Aleph-0 while the number of elements in S2 is denoted by Aleph-1.

One can repeat this process from Aleph-0 to Aleph-n, each step being infinitely many times bigger than the previous.

I’ll stop here, purely because I have no rigorous demonstration of why there cannot be one-to-one correspondence between the elements of the set S and the elements of set S2. This is especially so after having been able to stuff an infinite number of infinities into one infinity as demonstrated in the final Hotel Infinity trick. Something is wrong, since I appear to be able to produce a one-to-one correspondence between S and S2. Oh dear me, I hope I’m right and I’ll be able to upstage Cantor’s infinities. In reality, it’s probably a conceptual glitch on my part.