   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.   Friday, April 06, 2012

Friday Random Ten

1. Lorraine Hunt Lieberson - Johann Sebastian Bach: Cantata #82 "Ich Habe Genug"
2. Netherlands Bach Collegium - Johann Sebastian Bach: Cantata #29, "Wir Danken Dir, Gott, Wir Danken Dir"
3. Stephen Preston, Trevor Pinnock, Jordi Savall - Johann Sebastian Bach: Flute Sonata in E Minor, BWV 1034, Adagio Ma Non Tanto
4. The Last Goodnight - Pictures of You
5. Drain sth - Crave
6. Asuka Sakai, Ado Mizumori - A Crimson Rose and a Gin Tonic (from Katamari Fortissimo Damacy)
7. The Sixteen Choir & Orchestra - Johann Sebastian Bach: Mass in B minor, BWV 232, Et Incarnatus Est
8. Alexandre Tharaud - Erik Satie: Heures séculaires et instantanées
9. Anekdoten - King Oblivion
10. Freiburg Baroque Orchestra - Johann Sebastian Bach: Cantata #151, "Lobt Gott, Ihr Christen Allzugleich"

Thursday, April 05, 2012

I have to take compact sets in small steps, which means I'm spending more time on them than I expected. There is a particular payoff that I'm working toward, but it may be a while before I get there. It feels to me like things will start being more challenging with today's post and going forward, but hopefully I'll still be able to makes sense out of it. Lots and lots of overexplaining incoming. You may be reading this and thinking, "duh, we get it. Move on." I will explain things in excessive detail to make sure that I get it.

It can't hurt to start by checking in with what we know. We know the definition of compact sets. We know that compact sets are always compact in any metric space. From there, we showed that compact sets are closed. And this led to showing that closed subsets of compact sets are compact.

Okay, I can't figure out a good way to get into this next fact about compact sets. I want to start with a counterexample involving closed sets in general, and then show that this counterexample does not apply to compact sets, but my counterexample feels really contrived. I don't have a good answer for why you would do this in the first place, but we're going to build an infinite set of closed, but not compact sets, such that while the intersection of any finite subcollection of these sets is non-empty, the intersection of all of the sets is empty.

[UPDATE: The example used in this post has several problems. First, the sets of rational numbers used in this post are not closed sets. Second, we haven't yet established that closed intervals of real numbers are compact, and that fact is what makes this example useful. Third, the sets I'm using are really ugly, which makes this example feel unmotivated. Fourth, the concluding paragraph, as written, may be misleading. I don't want to take the space to deal with all of this here, so I plan to discuss these issues in my next post.]

I have approximately two tools to work with, so I'm going to use them. This is one of those moments where I wish I had more tools, and I wonder if studying topology in more depth would give them to me. But I'm going to press on, and look at closed sets of rational numbers in the real number line metric space. And if I'm using rational numbers, I'll need an irrational number, and as always I'll grab the first one at hand, which is √2.

The goal is to build two infinite collections of sets. The sets in one collection will be mostly less than √2, but will always have some members greater than √2. The sets in the other collection will be mostly greater than √2, but will always have some members less than √2. The idea is that when we merge the two collections together, if we pick some finite collection of sets and look for where they overlap, there will always be a small overlap around √2, so any finite intersection will contain points where they overlap. However, when we take all of the sets, we can show that every point will be excluded, so the intersection of all of the sets is empty.

2 is an irrational number, which means that it can't be expressed as a fraction. However, we can approximate it with fractions, so we're going to look at the approximations. For any denominator, there is a largest rational number less than √2, and there is a smallest rational number greater than √2. The first few examples are: 1/1 < √2 < 2/1. 2/2 < √2 < 3/2. 4/3 < √2 < 5/3. And so on. The important things are that we can bracket √2 between two rational numbers, and that the size of the bracket gets smaller as the denominator increases.

Now, for each bracket, we will make two closed sets. In a particular bracket, call the smaller number p and the greater number q. p and q are both rational numbers, and both have the same denominator, n. The first closed set is the set of all rational numbers x where 1 ≤ x ≤ q. The second set is the set of all rational numbers where p ≤ x ≤ 2. Create one pair of sets for every possible denominator n.

Since p is always less than √2, and q is always greater than √2, if we pick any two sets and take the intersection, there will always be a set in the middle, of rational numbers greater than or equal to p and less than or equal to q, so the intersection is never empty. If we take some finite collection of sets, there will always be a greatest p and a least q, and the points between these will be in the intersection of the sets.

However, if we take the intersection of the infinite collection of all possible sets, then we can look at any rational number x. If x is less than √2, then there exists a rational number between x and √2, and x is not a member of the set greater than or equal to that rational number and less than or equal to 2. Likewise, if x is greater than √2, there is a set mostly less than √2 which excludes x. So the intersection of all the sets does not contain any points.

That was a long set up to say that we can't do this with compact sets. Suppose {Kα} is an infinite collection of compact sets, and the intersection of any finite collection of these sets is always nonempty. If the intersection of the infinite collection were empty, we could choose a set K from the collection, and say that the intersection of all of the other sets must have no points in common with K.

Okay, it's time to draw squares on a piece of paper again. Draw a square and call it K. Draw some other squares, K1, K2, …. For the sake of visualization, all of the numbered Ks should overlap at the same point, but K should not overlap that point. Strictly speaking, K should overlap all of the numbered Ks, but it's easier to draw if we ignore that, because what we really want to look at is the set where all of the other Ks overlap. This set is the intersection of all the other Ks. Now, look at the entire rest of the page. The rest of the page is a set, of course, and is the complement of the intersection of the numbered Ks. K is obviously a subset of the rest of the page.

Now DeMorgan's laws kick in. Symbolically, K ⊂ (∩Kα)c. But (∩Kα)c = ∪(Kαc). For any particular set Kα, Kα is compact, so it is closed. Therefore Kαc is an open set, so the union of open sets is an open cover of K. But K is compact. So a finite subcollection of the open cover is also an open cover of K. Run the sets in this finite open cover back through DeMorgan's law, and we get back to a finite subcollection of {Kα}, such that the intersection of the finite subcollection does not have any points in common with K.

But our starting assumption was that the intersection of every finite subcollection was nonempty, and we've now constructed an empty finite intersection. This contradiction means that the infinite intersection must also be nonempty.

Going back to our counterexample, we haven't shown yet that closed intervals on the real number line are compact sets. We will eventually, but until then this doesn't really count as a demonstration of an infinite intersection of compact sets. However, I'm going through with it anyway. Instead of sets of rational numbers between 1 and q, and between p and 2, look at the sets of real numbers. Now every set includes √2, so the intersection of the infinite collection of sets includes √2, and is not empty.

The proof is constructed around arbitrary infinite collections of sets, as long as every intersection of a finite subcollection is nonempty. The particular case which is easy to visualize is a sequence where each set is a subset of the previous one. K1 is a square on a page, K2 is a square inside K1, K3 is in K2, and so forth. With an infinite collection of squares, if the sets are compact, the squares can shrink down to a point. If the sets are closed but not compact, they can shrink down to nothing.

Wednesday, April 04, 2012

Okay, enough distractions. Let's get back to compact sets. We know that a compact set is compact in any metric space which contains it. We also know that compact sets are closed. By implication, compact sets are closed in any metric space which contains them, which is not true of closed sets in general. This gives a relationship between a compact set and the world around it. Let's go the other direction and look at the interior of compact sets, by considering subsets of compact sets.

Since compact sets are closed, let's look at a closed subset of a compact set. Now it becomes important to clarify what we mean by that. Suppose X is a metric space, and K is a compact set in that metric space. If F is a subset of K, F could potentially be closed relative to K but not be closed relative to X. So let's be clear that F is closed relative to X (and therefore also closed relative to K).

(I don't have an example at hand of a subset of a compact set which is closed relative to the compact set but not closed relative to the space. The discussion earlier this week of closed sets on the rational number line gave examples of sets which are closed relative to the rational number space, but not closed relative to the real number space. On the other hand, the set of rational numbers is not a compact set in the real number space. I'll have to give some thought to whether it's possible to for a set to be closed relative to a compact space but not closed in the surrounding metric space.)

Take an open cover of F, call it {Gα}. {Gα} may be infinite, in which case we can use the following process to find a finite subcollection. Since F is closed in X, Fc is an open set. Add Fc to {Gα}, and this is clearly an open cover of X. Since K is a subset of X, this is an open cover of K. Since K is compact, there is a finite subcollection of {Gα} and Fc which is an open cover of K. Since F is a subset of K, this finite subcollection is also an open cover of F. If Fc is part of the finite open cover of K, we can remove it from the open cover of F since Fc does not intersect F. The resulting finite open cover of F is a subcollection of {Gα}. This is true for any possible starting open cover of F, so F is compact.

There's a little added bonus. Suppose F is any closed set in X. It does not have to be a subset of K. If K is a compact set in X, then K is closed in X. Then we know that the intersection of F and K, F∩K, is closed in X. Furthermore F∩K is a subset of K, so since it is a closed subset of a compact set, it is itself compact. If X is a metric space, F is any closed set in X, and K is any compact set in X, then F∩K is also a compact set.

Tuesday, April 03, 2012

While I'm taking an interruption from discussing compact sets, I want to pick up one more topic that I overlooked when I was talking about closure. This is the idea of connected sets. Connectedness has an intuitive meaning, but we want to define it formally so we can use it mathematically. And as often happens, it's easier to define it by defining the opposite.

Let's look at separated sets. If A and B are two sets in some metric space X, they are separated if they don't touch each other. Formally, what does "don't touch each other" look like? Two sets are separated if, for both pairs of sets, the intersection of one set with the closure of the other contains no points.

Here are some examples on the real number line. Suppose set A is all real numbers greater than or equal to 0, and set B is all real numbers less than or equal to 0. A and B are pretty clearly not separated. For one thing, they both contain the point 0. For another, the union of the two sets is the entire real number line, and if they were separated, you would expect to be able to say that there is a gap of some kind between them.

Let's keep A as the set of real numbers greater than or equal to 0, but exclude 0 from B, so B is now the set of real numbers strictly less than 0. Now the sets don't have any points in common (the intersection of the two sets is the null set), but the union of the two sets is still the entire number line. There's no gap. So, the closure of B includes the point 0, and the intersection of A and the closure of B now does contain a point, so the sets are not separated.

Note that the closure of A is A, so the intersection of the closure of A and B still does not contain any points. That's okay. Either A∩B contains a point, or A∩B contains a point. They do not both have to contain points in order for the sets to not be separated.

Finally, exclude 0 from A as well. Now A is the set of real numbers strictly greater than 0, and B is the set of real numbers strictly less than zero. The union of the two sets is not the real number line, and the point 0 is a gap between the two sets. The gap has a radius of 0, but mathematically, it still exists. Now AB includes the point 0, but that doesn't matter. Neither A∩B nor A∩B contain any points, so the sets are separated.

Really, this all makes intuitive sense, and it doesn't really get more complicated with more complicated spaces or more complicated sets. Two sets do not have to overlap in order to touch each other, but there can't be a gap between them. If two sets don't touch each other, then they are separated.

Now that we have defined separated, we can define connected. A set E, in some metric space X, is connected if it cannot be represented as the union of two separated sets. If some sets A and B exist, such that E = A∪B and A and B are separated, then E is not a connected set. If for any two sets A and B, such that E = A∪B, A and B are never separated, then E is a connected set.

This definition is obvious, but it's also useful, so it's good to go through the trouble of formally defining it now.

Monday, April 02, 2012

Last week we introduced the idea of compact sets, and we started to explore the properties of compact sets. There's more to say about compact sets, and I expect to spend most of this week discussing them. However, before I do that, I want to explore some ideas I've been kicking around comparing metric spaces of real numbers and metric spaces of rational numbers.

Most of my examples when discussing metric spaces for the past couple of weeks have been based on spaces of real numbers, although that has been implied in some cases. My examples involving a piece of paper and sets marked out as squares or circles on the paper are effectively a visualization of a 2 dimensional Euclidean space. Every point on the page corresponds to an ordered pair of real numbers, and the distance function for the space is the straight line distance between the two points.

(An aside which I'm not going to develop right now, but maybe I should someday: Roll the piece of paper into a cylinder, and measure the distance as the straight line distance through the cylinder, rather than along the surface of the cylinder. Is this a valid metric space? I assume it is, but I'd have to actually work through the math to make sure. Anyway, back to the topic at hand.)

The other space I've used in various examples is the real number line, which you could also call the 1 dimensional Euclidean space. I think I've also referred a couple of times to the set of rational numbers, with distance measured as the absolute value of the difference. This space is of course a subspace of the real number line, but because it has holes, it has some different properties.

I want to compare some sets on the real number line with sets on the rational number line, so we can see how they behave differently. Let's start on the real line with the set of real numbers greater than −2 and less than 2. This is an open set. If it included the endpoints, i.e., the set of real numbers greater than or equal to −2 and less than or equal to 2, it would be a closed set. Neither set is a valid set in the space of rational numbers, since both sets include irrational numbers.

On the other hand, we can look, on the rational number line, at the set of rational numbers greater than −2 and less than 2. On the rational number line, this is an open set. However, on the real number line, this set is not open. The holes in the set guarantee that in the real number space, every neighborhood of every point in a set of rational numbers is missing some points, so no set of rational numbers can ever be an open set in the real space. (Note that the set is also not closed in the real space. There is one sense in which open and closed are opposite concepts, and another in which they are not.) This gets back to the previous discussion about how sets are only open or closed relative to the space in which they are defined.

Likewise, the set of rational numbers greater than or equal to −2 and less than or equal to 2 is a closed set in the rational number line space, but is not closed in the real number line space. Closed sets are slightly different than open sets, however. It is possible for a set to be closed on both the rational number line and on the real number line. For example, a set of isolated points can have no limit points, and will therefore be closed in either space.

Okay, now let's look on the rational number line at the set of numbers which is greater than −√2 and less than √2. The critical thing is that since √2 is not a rational number, this set is both open and closed on the rational line. It should be obvious that it is open. It is closed because every rational number which is a limit point of the set is a member of the set. Since √2 is not a rational number, it does not exist in the rational number space, and therefore cannot be a limit point of the set. Once again, of course, this set is neither closed nor open on the real line. Sets of real numbers between −√2 and √2 can be either open or closed, depending on whether the set includes the end points. If the set includes one endpoint but not the other, it's neither open nor closed, but it can't be both open and closed.

Bringing this back to more recent topics, let's look at whether the set of rational numbers greater or equal to −2 and less than or equal to 2 is compact. We know that if it is compact in one space, it is compact in every space. We also know that if it is compact, it is closed. Since it is not closed on the real number line, it can't be compact, but I want to take a look at the reason why.

Let's look at the set on the real number line. Once again, we're going to make use of our favorite irrational number, √2. We are going to build an open cover of the set which does not cover √2, and we are going to build it specifically so that no finite subcollection of the open cover is also an open cover.

We are going to define the open cover inductively. We are going to start by creating a neighborhood of the number 2. For the radius of the neighborhood, we will pick some rational number less than half the distance from 2 to √2. We can try to be greedy and pick a number which is close to half the distance, but we can pick a smaller number too. It will work out the same. Let's pick 1/4. Now, the point 2 − 1/4 is a rational number, and is not included in the neighborhood of 2. (Neighborhoods are open sets, and don't include points on the edge of the set.) However, the neighborhood includes all the points greater than 1 3/4. So let's do it again. Set 1 3/4 as the center of a neighborhood and set the radius to a rational number less than half the distance to √2.

It should be clear that after any finite number of neighborhoods is created, there will be some maximum rational number greater than √2 which is not in any of the neighborhoods, but for which all rational numbers greater than that number are in one of the created neighborhoods. (If the words don't make sense, draw a picture and it should be clear.) However, for any rational number greater than √2, there is also a finite number of neighborhoods after which the number will be included in one of the sets.

We could build a similar collection of sets coming from the other direction, but we don't even have to. We can just take the neighborhood of −2, with radius 2+√2, and we'll pick up all of the rational numbers greater or equal to −2 and less than √2. So now we have an open cover of the set of rational numbers greater than or equal to −2 and less than or equal to 2. This collection of sets was constructed to exclude √2, which is not a problem because √2 is not rational. But the collection was also constructed to be infinite, and so that no finite subcollection would be an open cover of the set of rational numbers greater than or equal to −2 and less than or equal to 2. Therefore, the set of rational numbers greater than or equal to −2 and less than or equal to 2 is not a compact set.

Note that the same definitions of neighborhoods, each with the same center and radius, also builds an open cover of the set on the rational line. There's a slight conceptual difference, because the neighborhoods on the real line are of all real numbers, but the neighborhoods on the rational line are just of rational numbers. It also doesn't quite make sense to say that the open cover on the rational line excludes √2, since √2 is not a point on the rational line, but it is true that all of the neighborhoods with centers greater than √2 overlap, and all of the neighborhoods (if we constructed more than one) with centers less than √2 overlap, but no neighborhood with a center greater than √2 overlaps a neighborhood with a center less than √2. And this is a topic which leads us to tomorrow's digression.         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.

Why is the HTML for this page not valid?

BlogSpot adds the advertisement that appears at the top of this page. That advertisement is not valid HTML and is outside of my control. I believe that aside from that ad, this page is valid HTML.  