8:23 PM

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, I₁=[a₁,b₁] and I₂=[a₂,b₂], and a₁≤a₂ and b₂≤b₁, then I₂ is a subset of I₁.

This means that we can construct an infinite sequence of subintervals. For any natural number n, the interval I_n includes the points between a_n and b_n, and the interval I_n+1 is a subset of I_n, meaning that a_n≤a_n+1 and b_n+1≤b_n. 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, a_n increases but b_n 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, x₁, x₂, x₃, and so forth, which includes every real number. If you specify a natural number n, I could tell you the real number x_n 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=x_n. 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 I₁, which has endpoints a₁ and b₁. Take a look at the real number x₁ from our list of every real number. If x₁ is not between a₁ and b₁, then we can just say that I₂=I₁ and move on. If a₁≤x₁≤b₁, there are two possibilities. If x₁=b₁, then we will create a smaller subinterval by moving the right endpoint. Since a₁ and x₁ are real numbers, there exists some real number between them, which we can call b₂. Then a₁<b₂<x₁. We can then set a₂=a₁ and we have a new interval I₂=[a₂,b₂].

If x₁<b₁, then we can move the left endpoint instead. There is a real number between x₁ and b₁, which we can call a₂, while keeping b₂ equal to b₁. Either way x₁ may or may not have been a member of I₁, but it is not a member of I₂.

We can now do this with every point on the list, so for every n, if x_n is a member of I_n, we can create a smaller interval I_n+1 which does not include x_n. Otherwise, we can just keep I_n+1 as the same as I_n. This means that no real number x_n 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.

0 comments