11:02 PM

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 x_n will be a point in P, for any natural number n. The points will be all distinct, so if a≠b, then x_a≠x_b. Since P is countable, every point in P can be labeled as x_n for some specific value of n.

Pick some point y₁ in the Euclidean space. y₁ does not have to be a member of P, but it could be. If it is, y₁=x_n for some particular value of n, but the value of n doesn't matter. Any neighborhood of y₁ is the open set of all points y in the Euclidean space such that |y−y₁|<r, for some radius r greater than 0. Choose a neighborhood of y₁ which includes some points in P. (It could include all of them, but it doesn't have to.) Call the neighborhood V₁. V₁ 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 V₁, call it y₂. y₂ again is a point in the Euclidean space, but does not necessarily have to be a member of P. y₂ has a neighborhood around it, V₂. Let's choose V₂ such that V₂ is a subset of V₁, and V₂ includes some points in P, but also so the radius of V₂ is strictly less than the distance from x₁ to y₂. Therefore, V₂ excludes x₁.

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 x₁, x₂, x₃, 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 y₁. It will be cleaner to draw if y₁ is not in P, but it could be in P if you want. Draw a circle around y₁ which includes some of P and call that V₁. V₁ could include all of P, but doesn't have to. Now, we are going to mark some other point inside V₁ and call that y₂, and draw a smaller circle around y₂, such that the small circle is entirely inside V₁. The placement of y₂ and V₂ are a little tricky. V₂ should include some points in P, but also should not include the point x₁. You always can pick y₂ and V₂ 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, V_n is a circle which includes some points in P. V_n+1 is a circle inside V_n which also includes some points in P, but specifically does not include x_n. (The center of V_n is y_n, but there is not necessarily a relationship between the y's and the x's, which are all the points in P.) Then {V_n} 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 V_n 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, x_n is not a member of V_n+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, V_n is an open set. But we can turn it into a closed set, by taking the closure of V_n. V_n is an open set with center y_n and radius r_n, and includes any point y where |y−y_n|<r_n. The closure of V_n is the set of any point y where |y−y_n|≤r_n. And we can work with closed sets. Importantly, the closure of V_n 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 V_n is compact and P is closed, the intersection of the closure of V_n and P is compact, for every n. For a given V_n, call the intersection K_n.

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

However, we have constructed the sequence V_n such that the point x_n is not a member of V_n+1. x_n is also not a member of the closure of V_n+1, because the radius of V_n+1 is strictly less than the distance from the center of V_n+1 to x_n. K_n+1 is a subset of the closure. Therefore, x_n is never a member of K_n+1, so the point x_n cannot be in the intersection of all of the K_n 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 K_n, but that no point x_n is in the intersection of all K_n. Therefore there must be some point in P which is not labeled by x_n. But our starting assumption was that {x_n} 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.

0 comments