It is now April! Did you know that April is one of the months in which every compact metric space is separable?

Proof. Let it be April, and let M be a compact metric space. Because M is compact, it is totally bounded, so for all n∈ℕ, we can cover M with finitely many open balls of radius 1/n. The centers of all such balls are a countable set which we can call C. But C is dense, because an arbitrary point p∈M is a limit point of C: an ε-neighborhood of p must contain the center of one the balls in our covering of M with ε/2-balls. Thus M contains a countable dense subset.

If a sequence of real numbers (a_n) is bounded and monotone (and I'm actually going to say nondecreasing, without loss of generality), then it converges. I'm going to tell you why and I'm going to tell you twice.

If our sequence is bounded, the completeness of the reals ensures that it has a least upper bound, which we'll call, I don't know, B, but there have to be sequence elements arbitrarily close to (but not greater than) B, because if there weren't, then B couldn't be a least upper bound. So for whatever arbitrarily small ε, there's an N such that a_N > B – ε, which implies that |a_N – B| < ε, but if the sequence is nondecreasing, we also have |a_n – B| < ε for n ≥ N, which is what I've been trying to tell you—

—twice; suppose by way of contraposition that our sequence is not convergent. Then there exists an ε such that for all N, there exist m and n greater or equal to N, such that |a_m – a_n| is greater or equal to ε. Suppose it's monotone, without loss of generality nondecreasing; that implies that for all N, we can find n > m ≥ N such that a_n – a_m ≥ ε. Now suppose our sequence is bounded above by some bound B. However, we can actually describe an algorithm to find sequence points greater than B, thus showing that this alleged bound is really not a bound at all. Start at a₁. We can find points later in the sequence that are separated from each other by at least ε, but if we do this ⌈(B – a₁)/ε⌉ times, then we'll have found a sequence point greater than the alleged bound.

Theorem. An open set in real sequence space under the ℓ^∞ norm is not totally bounded.

Proof. Consider an open set U containing a point p. Suppose by way of contradiction that U is totally bounded. Then for every ε > 0, there exists a finite ε-net for U. Fix ε, and let m be the number of points in our ε-net, which net we'll denote {S_i}_{i∈{1, ..., m}}. We're going to construct a very special point y, which does not live in U. For all i ∈ {1, ..., m}, we can choose the ith component y_i such that the absolute value of its difference from the ith component of the ith point in the net is strictly greater than ε (that is, |y_i – S_i,i| > ε) but also so that the absolute value of its difference from the ith component of p is less than or equal to ε (that is, |y_i – p_i| ≤ ε). Then for j > m, set y_j = p_j. Then |y – p| ≤ ε, but that means there are points arbitrarily close to p which are not in U, which is an absurd thing to happen to a point in an open set! But that's what I've been trying to tell you this entire time.

The idea of total boundedness in metric space (for every ε, you can cover the set with a finite number of ε-balls; discussed previously on An Algorithmic Lucidity) is distinct from (and in fact, stronger than) the idea of mere boundedness (there's an upper bound for the distance between any two points in the set), but to an uneducated mind, it's not immediately clear why. What would be an example of a set that's bounded but not totally bounded? Wikipedia claims that the unit ball in infinite-dimensional Banach space will do. Eric Hayashi made this more explicit for me: consider sequence space under the ℓ^∞ norm, and the "standard basis" set (1, 0, 0 ...), (0, 1, 0, 0, ...), (0, 0, 1, 0, 0, ...). The distance between any two points in this set is one, so it's bounded, but an open 1-ball around any point doesn't contain any of the other points, so no finite number of open 1-balls will do, so it's not totally bounded, which is what I've been trying to tell you this entire time.

So we have this metric space, which is this set of points along with a way of defining "distances" between them that behaves in a basically noncrazy way (points that are zero distance away from "each other" are really just the same point, the distance from one to the other is the same as the distance from the other to the one, and something about triangles).

Let's say (please, if you don't mind) that a sequence of points (x_n) in our space is fundamental (or maybe Cauchy) iff (sic) for all positive ε, there's a point far enough along in the sequence so that beyond that point, the distance from one point to the next is less than ε. Let's also agree (if that's okay with you) to say that our metric space is sequentially precompact iff every sequence has a fundamental subsequence. If, furthermore, the precompact space is complete (all fundamental sequences actually converge to a point in the space, rather than leading up to an ætherial gap or missing edge), then we say it's compact. It turns out that compactness is an important property to pay attention to because it implies lots of cool stuff: like, compactness is preserved by homeomorphisms (continuously invertible continuous maps), and continuous functions with compact domains are bounded, and probably all sorts of other things that I don't know (yet). I'm saying sequentially precompact because I'm given to understand that while the convergent subsequences criterion for compactness is equivalent to this other definition (viz., "every open cover has a finite subcover") for metric spaces, the two ideas aren't the same for more general topological spaces. Just don't ask me what in the world we're going to do with a nonmetrizable space, 'cause I don't know (yet).

But anyway, as long as we're naming ideas, why not say that our metric space is totally bounded iff for every ε, there exists a finite number of open (that is, not including the boundary) balls that cover the whole space? We can call the centers of such a group of balls an ε-net. Our friend Shilov quotes his friend Liusternik as saying, "Suppose a lamp illuminating a ball of radius ε is placed at every point of a set B which is an ε-net for a set M. Then the whole set M will be illuminated." At the risk of having names for things that possibly don't actually deserve names, I'm going call each point in an ε-net a lamp. Actually Shilov, and thus likely Liusternik, is talking about closed balls of light around the lamps, not the open ones that I'm talking about. In a lot of circumstances, this could probably make all the difference in the world, but for the duration of this post, I don't think you should worry about it.

But this fear of having too many names for things is really a very serious one, because it turns out that sequential precompactness and total boundedness are the same thing: not only can you not have one without the other, but you can't even have the other without the one! Seriously, like, who even does that?!

Continue reading →