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

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**_{1}, **x**_{2}, **x**_{3}, 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**_{1}. It will be cleaner to draw if **y**_{1} is not in P, but it could be in P if you want. Draw a circle around **y**_{1} which includes some of P and call that V_{1}. V_{1} could include all of P, but doesn't have to. Now, we are going to mark some other point inside V_{1} and call that **y**_{2}, and draw a smaller circle around **y**_{2}, such that the small circle is entirely inside V_{1}. The placement of **y**_{2} and V_{2} are a little tricky. V_{2} should include some points in P, but also should not include the point **x**_{1}. You always can pick **y**_{2} and V_{2} 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.