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.

Wednesday, April 25, 2012

At the beginning of March, I was discussing the cardinality of infinite sets. We showed, for example, that the rational numbers, a set which appears to be much larger than the natural numbers, in fact is the same size as the natural numbers. We also showed that there exist infinite sets which are larger than the set of natural numbers. I looked at the question of whether the set of real numbers is larger than the set of natural numbers, but I didn't come to a definite conclusion. Today, building on the work we've been doing with set topology, we will answer that question.

Before I start, I want to restate some proofs that we've covered recently and that we will need here. Hopefully this way when I draw some conclusions from these theorems, they won't seem to come from out of nowhere. First, given an infinite sequence of compact sets, such that each set in the sequence is a subset of the previous set in the sequence and none of the sets are empty, the intersection of all the sets in the sequence is not empty. (That statement is a mouthful and kind of makes my head spin. And the example in that post is flawed. I also had a follow up post in which the examples work and which hopefully makes more sense, but where I don't restate the proof itself. If you can wrap your head around the example, it should make the logic in this post more clear.)

Another proof which we previously looked at and will need today is the proof that the intersection of any closed set and a compact set is itself a compact set. This one is a little more straightforward, and can be visualized by drawing two rectangles on a page. Call one rectangle the closed set and the other rectangle the compact set, and then their overlapping area is also a compact set.

Finally, we will need the Heine-Borel theorem. This states that in a Euclidean space, any set which is both closed and bounded is also compact.

Before I begin the proof, here's a useful definition. A perfect set is a closed set in which every point in the set is a limit point of the set. The definition of a closed set is that every limit point of the set is a member of the set. Perfect sets go in the other direction and require that every point in the set also be a limit point of the set.

Our standard example of a compact set, the set of all numbers of the form 1/n, where n is any natural number, and the number 0, is closed, but is not perfect, because 0 is the only limit point for the set. In comparison, a k-cell is both compact and perfect.

So take some Euclidean space. (Note that we are requiring a Euclidean space, rather than a metric space in general.) In that Euclidean space, take some nonempty perfect set P. We will now show that P has an infinite number of points, and that those points are not countable.

The first part is obvious. P is not empty, so it has at least one point. That point is a limit point of P, and therefore there must be an infinite number of points in P. To show the second part, we are going to assume the opposite and show a contradiction, so let's assume that the points in P are countable. Let's count them. x is any vector in our k-dimensional Euclidean space. Then xn will be a point in P, for any natural number n. The points will be all distinct, so if a≠b, then xaxb. Since P is countable, every point in P can be labeled as xn for some specific value of n.

Pick some point y1 in the Euclidean space. y1 does not have to be a member of P, but it could be. If it is, y1=xn for some particular value of n, but the value of n doesn't matter. Any neighborhood of y1 is the open set of all points y in the Euclidean space such that |yy1|<r, for some radius r greater than 0. Choose a neighborhood of y1 which includes some points in P. (It could include all of them, but it doesn't have to.) Call the neighborhood V1. V1 can include points in the space which are not members of the set P, but it must also include an infinite number of points in P. Since it includes any points in P, and every point in P is a limit point of P, it must include an infinite number of points in P.

Now, pick some other point in V1, call it y2. y2 again is a point in the Euclidean space, but does not necessarily have to be a member of P. y2 has a neighborhood around it, V2. Let's choose V2 such that V2 is a subset of V1, and V2 includes some points in P, but also so the radius of V2 is strictly less than the distance from x1 to y2. Therefore, V2 excludes x1.

On a piece of paper, representing a Euclidean space, draw some shape and call it P. It could be a rectangle, but it doesn't have to be. It can even extend off the edge of the page. (It doesn't have to be bounded.) The important things are that P is closed, and that P doesn't have any isolated points. Label a bunch of points in P as x1, x2, x3, and so forth. The claim is that we could label every point in P that way, but we want to just do enough to get the idea. Mark a point on the page and call it y1. It will be cleaner to draw if y1 is not in P, but it could be in P if you want. Draw a circle around y1 which includes some of P and call that V1. V1 could include all of P, but doesn't have to. Now, we are going to mark some other point inside V1 and call that y2, and draw a smaller circle around y2, such that the small circle is entirely inside V1. The placement of y2 and V2 are a little tricky. V2 should include some points in P, but also should not include the point x1. You always can pick y2 and V2 so this is possible, but if you just grab the first point and circle that come to mind you could miss.

Now, keep going. For every natural number n, Vn is a circle which includes some points in P. Vn+1 is a circle inside Vn which also includes some points in P, but specifically does not include xn. (The center of Vn is yn, but there is not necessarily a relationship between the y's and the x's, which are all the points in P.) Then {Vn} is an infinite sequence of sets, and each set is a subset of the previous set in the sequence. This sounds suspiciously like the proof I mentioned at the top of the post, but the proof refers to compact sets, and Vn is an open set instead.

I'm going to come back to that in a moment, but first I want to restate that for any n, xn is not a member of Vn+1. This implies that the intersection of all of the sets in the sequence of neighborhoods contains no points in P, even though each set itself does contain points in P.

For any n, Vn is an open set. But we can turn it into a closed set, by taking the closure of Vn. Vn is an open set with center yn and radius rn, and includes any point y where |yyn|<rn. The closure of Vn is the set of any point y where |yyn|≤rn. And we can work with closed sets. Importantly, the closure of Vn is also a bounded set. Since the set is both closed and bounded, and we are in a Euclidean space, the Heine-Borel theorem states that the set is also compact. We know from the proof I restated above that the intersection of a closed set and a compact set is a compact set. Since the closure of Vn is compact and P is closed, the intersection of the closure of Vn and P is compact, for every n. For a given Vn, call the intersection Kn.

Now, look at the sequence of Kn. Kn is always a subset of P. Kn is never an empty set, because of how it was constructed. For each n, Kn+1 is a subset of Kn. And Kn is always compact. So now the proof up top does apply, and the intersection of all the sets Kn is not empty. The point in the intersection is a member of every Kn, and therefore is also a member of P.

However, we have constructed the sequence Vn such that the point xn is not a member of Vn+1. xn is also not a member of the closure of Vn+1, because the radius of Vn+1 is strictly less than the distance from the center of Vn+1 to xn. Kn+1 is a subset of the closure. Therefore, xn is never a member of Kn+1, so the point xn cannot be in the intersection of all of the Kn for any value of n.

We have now shown that there exists some point which is a member of P in the intersection of all Kn, but that no point xn is in the intersection of all Kn. Therefore there must be some point in P which is not labeled by xn. But our starting assumption was that {xn} included all the points in P, because P is countable. The only conclusion is that P is in fact not countable.

We have just proved that if P is a nonempty perfect set in a Euclidean space, then P is not countable. Some examples of uncountable perfect sets include k-cells, closed intervals, and the entire real number line.

Once more, for emphasis, the real numbers are not countable.

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.