O Sweet Mr Math

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.

Thursday, April 05, 2012

9:36 PM

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.




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.