Countable Infinities and Strange Outcomes
You know what, I find math delightful. To me the best days are the days spent pondering a good problem (especially now that I don?t have a professor breathing down my neck ? ).
Some people get the warm fuzzies reading a good book, I get the warm fuzzies thinking about beautiful math problems, such as this one?shall we give it a go?
Part 1: No Vacancy at the Grand Hotel
Imagine a Grand Hotel with a (countably) infinite number of floors and rooms. On this particular night, the hotel is completely full.
Late in the evening, you arrive at the hotel and inquire about a room. Although there is no vacancy the hotel manager tells you that since this is an infinite hotel she can easily make room for you!
You?re delighted, but confused. If the infinite hotel is completely filled with an infinite number of guests, how does the manager go about securing a room for you?
What does Countably Infinite mean?
A set is countably infinite if it has a one-to-one correspondence with the natural numbers (you know 1,2,3,4,?).
Don?t let that definition confuse you, if you read the last post on infinity, you?re already familiar with countably infinite sets.
Remember how we proved that the set of all even numbers is the same size (aka: cardinality) as the set of natural numbers? We discovered this by making a one-to-one mapping between the sets. Well that?s all countably infinite means! Simply that we can match them up one by one with the counting numbers, which is infinite.
A Crafty Solution
Now this is perplexing. At first you may think, ?Well since it?s infinite can?t we just put the new guest in the last room?? Except since it?s infinite there really isn?t a last room and even if we were to locate that room it?s occupied.
The trick to solving this problem is to make a mapping from our countably infinite set of rooms to another countably infinite set of rooms that leaves us with an extra unoccupied room.
That sounds confusing but it is similar to how we proved the set of all even numbers was the same size as the set of natural numbers.
There may not be a last room, but there?s always a next room?
Let?s visualize the rooms as a set ranging from 1 to an infinite number n.
There isn?t a last room, but there is always a next room. So the trick is to simultaneously move each person to the next room. For example, move the person in room #1 to room #2, room #2 ? room #3, room #3 ? room #4 and so on.
Believe it or not, that?s our mapping: n ? n + 1.
After we move all of the guests we are left with room #1 unoccupied. In fact we can use this same method to free up any finite number of rooms we need whether it?s 1, 50, or 5 million. Pretty nifty, huh?
Part 2: An Infinite Bus Arrives
Another night, another infinitely full hotel with no vacancy.
This time the manager looks out the window and sees an infinitely long bus filled with an infinite number of passengers each in quest of a room.
Our math savvy manager jumps up and begins preparing an infinite number of rooms for the infinite number of new guests. How does she do this?
I bet you know the answer to this one.
Think about it?you need to move each current guest at the infinite hotel to a new room so that there will be a countably infinite number of unoccupied rooms for the new guests?
This is awfully similar to something we have done before? Have you got it?
Yeah, it?s the same as our proof from the other day where we showed that the set of counting numbers is the same size as the set of even numbers!
So if we move each current guest to 2 times their current room number, we?ll find a new room for each of the current infinite guests and be able to put all of our new guests in the infinite set of odd numbered rooms leftover.
Whoa, whoa, whoa? just think about that mind-blowing fact for a second?
You just took an infinite set, split it into two equivalent infinite sets both of which are the same size as the original infinite set yet also the same as the original infinite set itself when combined.
That?s perfectly paradoxical!
Part 3: An Infinite number of Infinite Busses Arrives
As you can imagine this hotel is a huge success, so it?s no wonder that one night our manager looks out the window to see an infinite number of busses all filled with an infinite number of room-seeking guests!!
Can she make room for an infinite number of infinite people in the infinite hotel?
Okay, this is the trickiest problem we?ve had so far. We need to make room in the infinite hotel for an infinite number of infinite guests?that?s going to take some pretty clever math.
Instead of jumping into it right away, I?m going to leave the solution for the next post so you can ponder it a bit 🙂
Okay, I?ll give you a little hint: There?s a countably infinite number of prime numbers?
Infinite Hotel Paradox, Continued
This is part 2 of the Infinite Hotel Paradox, check out part 1 as well ?
Thanks for reading!