Monday, October 19, 2009

The next time you argue about whose infinity is larger, say yours is nondenumerable infinity

 http://www.qwantz.com/index.php?comic=1575

The Infinity Hotel is meant to demonstrate the difference between a "denumerable" and "nondenumerable" infinity. You can do a lot of things to accomodate an infinite number  of guests in an infinite number of rooms, by using arithmetic.

There are higher orders of infinity, though. Paul Cantor first demonstrated this with his "diagnolization proof." We're going to go the "mathy" way first, and then I'll try to apply it to the Infinity Hotel. Also: I generally to do my writing without reference to Wikipedia, but this time, I made liberal use of the Diagonal Proof page. It's okay, though, because I once had a philosophy professor show me this stuff. I just... couldn't remember it.  Anyway. Moving on.

Step 1: suppose that you have a string of 0s and 1s that is infinitely long: 0, 0, 1, 1, 1, 0, 0, and so on. Got it? Okay.

Step 2: now suppose that you have an infinite number of these strings, in a list like this:
A = (0, 0, 0, 0, 0...)
B = (1, 1, 1, 1, 1...)
C = (1, 0, 0, 1, 0...)
D = (0, 1, 0, 1, 0...)
E = (1, 0, 1, 1, 1...)

Step 3: now we are going to make a new set of numbers, which uses the opposite numbers of each of the sets in the first list, going in a diagonal, like so:


A = (0, 0, 0, 0, 0...)
B = (1, 1, 1, 1, 1...)
C = (1, 0, 0, 1, 0...)
D = (0, 1, 0, 1, 0...)
E = (1, 0, 1, 1, 1...)

X = (1, 0, 1, 0, 0...)

No matter how many sets of numbers you make in step 2, set X is going to be different from every one of those sets, because its creation is based on having at least one digit different from each of those sets.

Step 4: from this, it follows that the set T of all infinite sequences of 1s and 0s cannot be put into a denumerable list, because we have sequence X which cannot possibly be part of our initial list of sequences.

Step 5: you just, like, blew my mind, man.

Let's go back to the hotel now. Infinity Hotel wants to expand by having an infinite number of floors, with an infinite number of rooms on each floor. Some of the rooms are empty, and some are occupied. To keep track of them, the manager has a list for the whole hotel with the rooms marked either O (occupied) or U (unoccupied). It looks something like this:

1: U, O, U, U, U...
2: O, O, O, O, U...
3: U, O, U, O, U...
4: U, U, U, U, U...
5: O, O, O, O, O...

One of his favorite things to do is mess with his new employees by asking them to find the floor with a particular room sequence, floor X, which he constructs by using an opposite of something on each floor, like so:


1: U, O, U, U, U...
2: O, O, O, O, U...
3: U, O, U, O, U...
4: U, U, U, U, U...
5: O, O, O, O, O...

X: O, U, O, O, U...

No matter how hard he or she looks, the new employee is never going to find that floor, because Infinity Hotel only has denumerable infinities in it. The employee always comes back to the main floor wanting to punch the manager in the gut, but since it sometimes takes an infinitely long time for the employee to figure out the trick, by then, the manager has usually gone home for the day.

No comments: