wherein is detailed Matt's experiences as he tries to figure out what to do with his life. Right now, that means lots of thinking about math.

Thursday, April 26, 2012

I've been thinking more about yesterday's proof. The proof showed that any perfect set in a Euclidean space is uncountable, and since the real number line is a perfect set in a Euclidean space, this led to the conclusion that the real numbers are uncountable. The downside of the proof is that it requires a ton of structural framework to get to the conclusion, and that makes it hard to follow. If all we want to do is prove that the real numbers are uncountable, we can simplify the argument while following the same basic structure. I want to go through the details because I think it will make the logic of the proof more clear.

To prove that the real numbers are uncountable, we will look at intervals. If a and b are real numbers and a<b, then the interval I=[a,b] consists of every real number x such that a≤x≤b. If we have two intervals, I1=[a1,b1] and I2=[a2,b2], and a1≤a2 and b2≤b1, then I2 is a subset of I1.

This means that we can construct an infinite sequence of subintervals. For any natural number n, the interval In includes the points between an and bn, and the interval In+1 is a subset of In, meaning that an≤an+1 and bn+1≤bn. We've previously formally proved that given an infinite sequence of subintervals, there must be at least one point which is in every interval in the sequence. We can restate the proof informally by saying that as n increases, an increases but bn decreases. They can eventually meet, but they can't cross, so the point where they meet must be in every interval in the sequence.

If we assume that the real numbers are countable, then we could construct a sequence of real numbers, x1, x2, x3, and so forth, which includes every real number. If you specify a natural number n, I could tell you the real number xn which corresponds to that natural number, and if you specify a real number x, I could tell you the natural number n such that x=xn. This all follows from the definition of countable sets. Essentially, there must be an infinite list which contains every real number.

Now, start with an interval I1, which has endpoints a1 and b1. Take a look at the real number x1 from our list of every real number. If x1 is not between a1 and b1, then we can just say that I2=I1 and move on. If a1≤x1≤b1, there are two possibilities. If x1=b1, then we will create a smaller subinterval by moving the right endpoint. Since a1 and x1 are real numbers, there exists some real number between them, which we can call b2. Then a1<b2<x1. We can then set a2=a1 and we have a new interval I2=[a2,b2].

If x1<b1, then we can move the left endpoint instead. There is a real number between x1 and b1, which we can call a2, while keeping b2 equal to b1. Either way x1 may or may not have been a member of I1, but it is not a member of I2.

We can now do this with every point on the list, so for every n, if xn is a member of In, we can create a smaller interval In+1 which does not include xn. Otherwise, we can just keep In+1 as the same as In. This means that no real number xn can be in every interval. However, we know that there is at least one real number which is in every interval, which means that real number can't be on the list. This means that no complete list of real numbers can be constructed, which in turn means that the real numbers are not countable.

This is the same argument as yesterday, but it involves much less overhead involving compact sets and perfect sets and Euclidean spaces. If this argument makes sense but yesterday's didn't, you can look at yesterday's argument again and see how the pieces of this proof can be generalized and turned into the pieces in that proof.

The other argument I want to compare it to is Cantor's diagonalization, which shows that the power set of the natural numbers is not countable. Structurally, the argument has a lot of similarities. For the power set, the first step is to assume that the collection of subsets is countable and make a list of all of the subsets. In this case, we assume that the real numbers are countable and make a list of all of the real numbers. We then use this list to construct either a subset or a real number which both must exist but cannot be on the list. We then conclude that the assumed list cannot exist, so the power set and the real numbers are not countable.

The funny thing is that even though I can see that the two arguments are equivalent, the argument about power sets feels much more brain warping. I think it's the way the set not on the list is created. With power sets, it feels almost like we're using the concept of power sets against itself, but with the real numbers, the reasoning feels more straight forward. It just comes down to presenting this real number that can't be on the list. It's just like, "so you thought you got them all? Well, guess what. You missed one." The power sets feels more like, "Now that I have a list of all the subsets, I will negate them all and create a new subset by denying all of the others! Mwa ha ha ha!" It just feels much more subversive.

FAQ

What does "rolls a hoover" mean, anyway?

"Roll a hoover" was coined by Christopher Locke, aka RageBoy (not worksafe). He enumerated some Hooverian Principles, but that might not be too helpful. My interpretation is that rolling a hoover means doing something that you know is stupid without any clear sense of what the outcome will be, just to see what will happen. In my case, I quit my job in an uncertain economy to try to start a business. I'm still not sure how that will work out.