Vitali's covering lemma

Vitali's covering lemma is a useful result in analysis, specifically when one is addressing questions about density. Suppose we are working in Rⁿ, n-dimensional Euclidean space, under Lebesgue measure where we denote by |S| the measure of a subset S of Rⁿ. It's probably best to think of |S| as the volume of S. We have the following result:

Vitali's Covering Lemma. If U is an open set in Rⁿ and c is a constant such that c < |U|, then there exist disjoint open balls B₁, ..., B_N contained in U such that
Σ_1≤j≤N|B_j| > 3^-nc.

This is one of those situations where the ideas in the proof end up being more useful than the result itself.

Proof of Vitali's Covering Lemma. Since we are considering Rⁿ under the Lebesgue measure, we can get approximate |U| as well as we would like to by taking the measure of larger and larger compact (closed and bounded) subsets of U. Thus there is a compact subset K of U such that |K| > c. Since U is open, for every point x in U there is an open ball around x, say B_x, contained within U. Let C := {B_x : x ∈ U}. Now C forms an open cover of K and since K is compact, it has a finite subcover given, say, by the balls B_x1, ..., B_xm for some positive integer m. Let us take all these balls and put them in the set S. We now perform the following process:

1. If S is not empty, there is a ball of maximum radius in S. We shall take this ball and call it B_j where j-1 is the number of times we have already performed the process; if S is empty, stop.

2. Remove all the balls in S that intersect B_j.

So at step j, we are greedily picking a ball B_j of maximum radius in S out of those balls in S that do not intersect any of the previous balls B₁, ..., B_j-1. Since there were only finitely many balls in S when we started the above process, this algorithm must terminate and we end up with some collection of balls B₁, ..., B_N. Now, suppose B is some ball that was deleted from S at the j^th step. Then B had radius at most that of B_j and since B ∩ B_j ≠ ∅, we get that B is contained in the ball centered at the center of B_j of three times the radius of B_j, which we shall denote by 3B_j. Since S was a subcover for K before we started messing with it, we have that the balls 3B₁, ..., 3B_N also provide a cover for K.

Notice moreover that, by the nature of our algorithm, the balls B₁, ..., B_N are disjoint.

Now, since the balls 3B_j cover K, their union has measure at least that of K. As a result

Σ_1≤j≤N|3B_j| ≥ |K| > c.

But |3B_j| = 3ⁿ|B_j| since that's how volume works. Therefore,

Σ_1≤j≤N3ⁿ|B_j| > c,

and dividing by 3ⁿ gives

Σ_1≤j≤N|B_j| > 3^-nc. QED.