## Monday, October 11, 2010

### Diary of Infinity: Part 3

We've now seen how a lot of "different infinities" are actually the same. In this post, we explore why there's at least one different kind of infinity.

Similar to what you do in science, the best way to try to prove something is to hypothesize about the outcome first. Then, once you have a guess at the answer, you have to formulate a plan to prove or disprove your hypothesis.

In this case, I claim (hypothesize) that there are different kinds of infinities. In particular, there are "more" real numbers than whole numbers.

First, we should explore the players before we plan the game.

Whole numbers are the easy ones. They're what we're using as our room numbers: 1, 2, 3, ....

What are real numbers? Real numbers can be thought of as the location of any point on a number line. A rigorous, mathematical definition is very involved, but your intuition is generally correct on this one, so we'll stick to the number line concept.

Now for the plan. I want to lay this out first, because I know you'll want to fight against the claim as we get going and it'll start to not make sense if you're not sure where we're going. I've also found it helpful to lay out a plan for a mathematical proof so that you can know when you're done. Often you can read or follow a proof and at each step say, "Yeah. Ok, I can see that." and then the proof suddenly stops and you wonder where the magic was. So, here's the plan and if we agree on it first, then it'll make the finish a bit easier to reconcile.

The plan (Hilbert Hotel style):

As before, the hotel has infinite amount of rooms numbered 1, 2, 3, ... as the whole numbers. This time, our people who show up will have names of all the real numbers from 0 to 1. I claim that there are more people than rooms, so there is no way to match up one room per person and one person per room.

It's relatively easy to prove there is something: just find one. If I claim that time travel is possible, all I have to do is go out and do it.

On the other hand, it's really hard to prove there is NOT something. If I claim that there is no way that time travel can happen, how can I prove it?

Well, we are going to use a technique called "proof by contradiction" (sometimes called "reductio ad absurdum"). Here's how that method works:

In order to prove that X cannot happen, let's--for a minute--pretend that X can and DID happen. What would be the consequences of X having happened? We will follow some of those consequences logically and arrive at something absurd or contradictory and realize that the only flaw in our logic was the original assumption that X has happened.

For example, one reason people claim time travel cannot happen is that IF it could, we should see some time travelers around once in a while. Since we don't/haven't, the original assumption of time travel being possible must be incorrect.

Here's how it applies to our situation. I'm going to pretend for a minute that we CAN match up our people to rooms. Since we can't check all of the possible ways to match them, I won't be able to tell you exactly how we did it, but we'll pretend that I got it to work. Then, if I can find someone who doesn't have a room and I can prove he doesn't have a room, then we have arrived at a contradiction.

I'll prove that this person cannot be in any room by allowing you to think of any room number you want and I can prove he is not assigned to that room. Since you are allowed to pick any room number, he cannot be assigned to any room.

Another thing I'll use is that two numbers are not equal in their decimal representation if at least ONE of their decimal places does not match (with the one exception being instances of 0.9999... repeating DOES equal 1, but that's for another blog post and we can avoid it here).

Have I convinced you that, if I carry out this plan, then there will be more people (irrationals) than rooms (whole numbers)? Let me know in the comments if you need more convincing.

Carrying out the plan:

So, we have somehow figured out how to match our real numbered people to our whole numbered rooms so that each room has one person and each person has one room. I don't know exactly how we did it, and it doesn't even have to follow any nice pattern, but somehow we've got a list somewhere. If I need to check who is the person assigned to room #573, I can find their name (or number) by looking it up on that list.

Since I don't know the exact order of this list, I'll attempt to put some "random" numbers as examples so you can see some numbers, but any methods we use should be able to be applied to any numbers you want to put in their place.

According to our plan, I need to find someone who DOESN'T have a room and then we'll be done. So, here's how we can find the person (by "the diagonal argument"). We'll call him "x" for now and construct his name in a specific way.

Check the list to see who is in room #1. Since all of our people are real numbers between 0 and 1, room #1's person has a name that goes something like 0.32914514.... All I really care about is the first decimal place (the 3 right after the decimal in that example). I am going to pick person "x" so that his name begins 0.a where a is any number other than what is in that same spot for the guy in room #1. For the example above, I could pick person "x"'s name to start 0.1 or 0.5 or 0.7 or a bunch of others as long as it doesn't start 0.3. Let's just go with 0.1 for this example.

We continue to construct person "x"'s name by checking the list for who is in room number 2. Room #2's person has a name something like 0.42150682.... We will pick person "x"'s name so that the second decimal place is anything other than the second decimal place of the guy in room #2. Also, to avoid the 0.999... problem, let's choose that digit to be something other than 9 as well. In this example, we have to avoid the 2, so pick anything else: 0.17

Continue this way down the whole list. Now, we can continue doing this down the whole list because:

1. There is a unique decimal representation of the room occupant names (if we avoid the .9999... repeating issue and we can).
1a. For room occupants that have terminating decimals (0.5, for example), we will use 0s to fill out the infinite decimal places after the termination point (so, 0.5 = 0.50000000....)
1b. Thus each room occupant has SOME digit in the decimal place that corresponds to his room number.
2. Since each room occupant has only one digit in the required decimal place (corresponding to room number), we have 8 choices for the digit in person x's name (not the one from the room occupant and not 9 to avoid that weird quirk).

So, I claim that person x cannot be assigned to any of the rooms which is what will contradict our original assumption that everyone did have a room meaning our original assumption was wrong.

Well, person x can't be in room number 1 because the person assigned to room 1 has a different first decimal place than person x. Similarly for room 2 and 3 and all the rest by the way we picked out person x.

And we're done! See, I told you that you'd be surprised that we're done. Go back and review our plan from the beginning and see if we carried it out. I think we have, but I agree that it somehow seems unsatisfying.