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.

Wednesday, April 18, 2012

Now we can use the result from last time to show that k-cells in Euclidean spaces are compact. First, we need to define k-cells.

On the real number line, an interval is the set of points between two points, including the end points. So if a and b are real numbers, and a<b, then the point x is in the interval [a,b] if a≤x≤b. I tend to refer to "closed intervals" to emphasize that an interval is a closed set, but this is redundant. Intervals include the endpoints, and including the endpoints makes the interval a closed set.

We can extend this idea to multidimensional Euclidean spaces with k-cells. Suppose we are looking at a Euclidean space with k dimensions. Then each point in the space corresponds to an ordered k-tuple of real numbers, so the point x can be represented by (x1,x2,…,xk) where each xi is a real number. A k-cell in this space is a closed box, containing all the points in the interior and on the sides of the box. For each dimension i, there is a minimum value ai and maximum value bi. If ai≤xi≤bi for every i from 1 to k, then x is a member of the k-cell.

For a simple example, look at the two-dimensional plane. If (1,2) and (3,4) are opposite corners of a square, then the square is a k-cell and any point (x1,x2) is in the square if 1≤x1≤3 and 2≤x2≤4.

The same reasoning that shows that intervals are closed also shows that k-cells are closed. Likewise, last time we showed that given an infinite sequence of intervals, where every interval in the sequence is a subset of the previous interval, then the intersection of all of the intervals is not empty. (It's either an interval or a single point.) By considering each dimension in a k-space separately, we can show that the intersection of an infinite sequence of k-cells, where each cell is a subset of the previous cell, is also not empty.

Now we can show that k-cells are compact. Start with an infinite open cover of a k-cell. In two dimensions, the k-cell is a rectangle. I tend to view the sets in the open cover as circles, but they can be any shape, as long as they are open sets. The open cover is an infinite set of circles, and at least one circle overlaps every point in the rectangle. In three dimensions, the k-cell is a box, and again the open cover can be sets of any shape, but I tend to visualize spheres. Note that while we are choosing convenient shapes for the open sets, the k-cells are actually rectangles or boxes, because of how they are defined. They are not arbitrary shapes.

So, we want to prove that the k-cell is compact. That is, given any open cover of the k-cell made of an infinite collection of sets, there is some finite subcollection of those sets which is also an open cover. As we often do, we will assume the opposite and then establish a contradiction. Begin by splitting the k-cell in half in every dimension. In one dimension, split the interval into two equal sized intervals. (A 1 dimensional k-cell is an interval on the real line.) In two dimensions, split the rectangle into four rectangles by drawing lines through the center of the rectangle in each direction. And so forth, so in general a k-cell will be divided into 2k subcells, each of which is also a k-cell.

Now, look at the original open cover of the original k-cell. Since each subcell is a subset of the original k-cell, some subcollection of the open cover must be an open cover of each subcell. (The subcells share points along their borders, so they will also share sets in the open covers. The point isn't to divide the sets in the open cover up, the point is to start with one large set and one large cover, and reduce it to some smaller sets with smaller covers.) Since the open cover is infinite, at least one of the subcells must have an infinite cover. (If they were all finite, then the union of the covers of each of the subcells would be finite, and we are assuming that the open cover must be infinite.)

Now we can subdivide the cell by cutting it in half in each dimension again, starting with the subcell with an infinite cover. (If there are multiple cells with infinite covers, pick one.) Two important things happen as we create an infinite sequence of subcells. First, based on what we showed last time and the extension this time, the sequence of subcells must contain at least one point from the original k-cell. Second, the size of each subcell, and therefore the distance between points in each subcell, shrinks.

Look at the original k-cell, and call a the "bottom left" point in the k-cell, or the point (a1,a2,…,ak). Likewise, call b the "top right" point in the k-cell. (The quote marks are there to imply being the top or the right or whatever in every dimension.) The line from a to b is a diagonal of the cell, and the distance from a to b is the maximum distance between any two points in the cell.

Every time we subdivide the k-cell, the length of the diagonal is cut in half. If the length of the original diagonal is d, then after n subdivisions, the length of the diagonal is 2−nd. So, we can construct an infinite sequence of subcells, each of which has a diagonal half the size of the previous cell, each with an infinite open cover (by our starting assumption), and each containing some fixed point from the original k-cell. (Since the intersection of all of the subcells is not empty, take a point from the infinite intersection, and that point must be in every subcell in the sequence.)

That point must be a member of at least one set from the infinite open cover. (Again, if it's in multiple sets, pick one and move on.) Since that set is an open set, there is a neighborhood of some radius r around the point such that every point in the neighborhood is also in the open set. r is fixed, but the size of the diagonal shrinks with each subdivision. This means that eventually, the length of a diagonal of some subcell must be less than r, but the subcell contains the point we are considering, so every point in that subcell must be of distance less than r from the point.

This means that the single open set which contains the point also contains every point in the subcell, so the subcell has a finite open cover (consisting of one set). Our assumption was the subcell had an infinite open cover. Now that we've shown that the open cover for the subcell is finite after all, that implies that there exists a finite open cover for the entire k-cell. Since the finite open cover exists, the k-cell is compact.

I mentioned this in passing, but it's worth stating again that closed intervals on the real line are k-cells, so we've now shown that closed intervals are compact sets. I tried to use that fact previously in examples, but nothing I've proved has depended on it, and now I've proved that it is in fact true, so my examples work. In the future I'll try to do things in the correct order.

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.