6:00 PM

Friday Random Ten

1. Dietrich Fischer-Dieskau, Daniel Barenboim - Johannes Brahms: 6 Gesänge, Op. 6, "Der Frühling"
2. Dietrich Fischer-Dieskau, Daniel Barenboim - Johannes Brahms: 6 Gesänge, Op. 3, "In Der Fremde"
3. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #168, "Kapital Und Interessen"
4. NDR Chorus Hamburg - Johannes Brahms: 12 Lieder Und Romanzen, Op. 44, "Die Müllerin"
5. Scars On 45 - Breakdown
6. Birdsongs of the Mesozoic - The Simpsons
7. The Doors - Twentieth Century Fox
8. Luc Devos - Wolfgang Amadeus Mozart: Andantino & Variations in E Flat, K 236
9. ABBA - He Is Your Brother
10. Billy Joel - I Go To Extremes

0 comments

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

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

10:53 PM

Now that we know that k-cells are compact sets and that infinite subsets of compact sets have a limit point in the compact set, we can establish some relationships between sets in Euclidean spaces in general.

Suppose E is some set in some Euclidean space, such that every infinite subset of E has a limit point in E. Last time we showed that for a compact set K, every infinite subset of K has a limit point in K, but we have not shown that this works in the opposite direction. We can't conclude yet that E must be compact. But let's see what we can prove based on this starting point.

Given that every infinite subset of E has a limit point in E, what can we say about E? First question: is E bounded? Well, assume that E is not bounded. (This assumption is a giveaway that we are about to prove the opposite by contradiction.) Then given any starting point p in E, we can choose any distance d, and there is always some point in E at a greater distance from p than d. Pick a point p₁ in E. Pick another point p₂ in E such that the distance from p₁ to p₂ is at least 1.

Then there must exist a point p₃ in E, such that d(p₁,p₃) is greater than d(p₁,p₂) + 1. (We need the additional distance to ensure that the points are not close to each other.) This allows us to construct an infinite sequence of points, such that the distance from any point to any other point in the sequence is at least 1. (If d(p₁,p_n+1)≥d(p₁,p_n)+1, then d(p_n,p_n+1)≥1 by the triangle inequality.) This sequence is a subset of E, and contains no limit points. This contradicts our premise that every infinite subset of E has a limit point in E, so the conclusion is that E must be bounded.

Next question: is E closed? Again, assume E is not closed, so there exists a limit point of E which is not a member of E. (The limit point is a member of the Euclidean space which contains E, but is not a member of E.) Then for every natural number n, there is a point in E such that the distance from that point to the limit point is less than 1/n. Take the set of these points for every value of n, and this is an infinite set. This infinite set is an infinite subset of E, which has a limit point, but that limit point is not a member of E.

Importantly, the subset has no other limit points. Pick some other point in the Euclidean space. This point is at a distance d from the limit point. There exists an n such that 1/n<d/2. All of the points in the subset which are closer to the limit point than 1/n are farther from the other point than d/2. This implies than that there can only be a finite number of points with distance less than d/2 from the other point, so the other point can't be a limit point of the set. Therefore, the subset is infinite but does not have a limit point which is a member of E. This again contradicts our premise, so E must be closed.

So now we've shown that if E is a set in a Euclidean space such that every infinite subset of E has a limit point in E, then E is both closed and bounded. So, if a set is compact, every infinite subset of the set has a limit point in the set. But also, if a set has the property that every infinite subset of the set has a limit point in the set, it is both bounded and closed.

Continuing the chain, suppose E is some set in some Euclidean space, such that E is both closed and bounded. At this point we are not making any other assumptions about E. Then E is a subset of some k-cell in that space. A k-cell looks like a box, although it can be a multidimensional box, which can be hard to think about. (Check out the iOS app The Fourth Dimension if thinking about what a 4-dimensional box looks like appeals to you.) Since E is bounded, we can set the bounds of the k-cell to the bounds of E, and we have now contained E in the k-cell. Since E is closed, it is a closed subset of the k-cell, which is compact. Therefore, E is also compact.

And we have completed the loop. Take a set in a Euclidean space. If it has any one of these three properties, it must have the other two. The three properties are:

1. The set is closed and bounded.
2. The set is compact.
3. Every infinite subset of the set has a limit point which is a member of the set.

The proof that a set in a Euclidean space is closed and bounded if and only if it is compact is the Heine-Borel theorem.

The proof as constructed here relies on the set being in a Euclidean space. As I previously encountered, in the space of rational numbers with d(p,q)=|p-q|, sets can be closed and bounded without being compact, so the Heine-Borel theorem does not hold in metric spaces in general. (A set of rational numbers can have a limit point equal to an irrational number. In the real space, this set is not closed. In the rational space, the irrational number does not exist, so the set is closed, but it is no longer true that the set has a limit point at all, so the set does not have the second or third listed properties.)

However, we've shown that if a set is compact, every infinite subset has a limit point in the compact set, and this is true in any metric space. I have not shown, but it is also true, that if every infinite subset of a set (in any metric space) has a limit point in that set, the set is compact.

0 comments

10:57 PM

Now that we've shown that k-cells, and in particular, closed intervals on the real number line, are compact, I feel like we have actual useful examples of compact sets. Until now we had sort of an abstract definition, and we were working off that definition to prove properties of compact sets, but they weren't really attached to anything. We also had one example which I've used a couple of times, and will use again in this post, but which feels kind of limited. In discussing the proofs I've used a square on a piece of paper, where the paper represents some metric space and the square represents some compact set. It's something of a relief that we can now say that closed rectangles on the complex plane are in fact compact sets.

There's one more fact about compact sets in general that I want to prove, and then we can focus on k-cells some more. Start with a compact set. Take any infinite subset of that set. That subset must have a limit point in the compact set.

I want to go back to the first example we had of a compact set to discuss this. Our compact set includes all rational numbers of the form 1/n, where n is any natural number, and also includes the number 0. Our proof that this set is compact is dependent on the fact that 0 is a limit point of the set, so any open set which contains 0 also contains an infinite number of other points in the set. Now we can turn that around and say that any infinite subset of this set must have 0 as a limit point. 0 itself doesn't have to be in the subset, but the only way we can get to an infinite number of points in the subset is by letting n go to infinity, which makes 0 a limit point of the subset. (Looking at the example, I'm happy thinking informally. I can see this is true, so I don't feel a need to work through the details formally. For the general proof, though, I should be a little more formal.)

For the formal proof, take any compact set and call it K. Take any infinite subset of K and call it E. Assume for the moment that E has no limit points. Pick a point p in K. Since E has no limit points, there exists a neighborhood of p which contains no points in E, unless p is a member of E. If p is a member of E, there exists a neighborhood of p which contains p and no other points in E. This neighborhood of p is an open set. For every point in K, there is an open set which contains that point, and at most one point in E. The union of all of these open sets is an open cover of K. However, no finite subcollection of these neighborhoods can be a cover of K, since there is an infinite number of points in E, and every point in E is in exactly 1 set in the open cover. Since we know that K is compact and therefore a finite subcover must exist, the conclusion is that E must have a limit point in K.

The limit point of E doesn't have to be a member of E, but must be a member of K. From the example, 0 is always the limit point of any infinite subset, but 0 doesn't have to be a member of the subset. However, 0 is a member of the original compact set. If 0 is not a member of the subset in this example, the subset is an open set. If 0 is a member of the subset, the subset is closed, and is therefore also compact.

0 comments