Finite Vitali Selection for Intervals

Why Select Intervals Greedily?

A finite family of intervals can overlap heavily, so summing their lengths may greatly overestimate the size of their union. A useful alternative is to retain a pairwise disjoint subfamily and enlarge its members by a fixed factor. The greedy rule is to choose a longest interval still available, then discard every interval that intersects it. The length comparison built into this rule is what makes the covering conclusion possible.

We work in $(\mathbb{R},\mathcal{L},m)$, where $\mathcal{L}$ is the Lebesgue sigma-algebra and $m$ is Lebesgue measure. This measure space is complete and sigma-finite, but not finite. All intervals below are closed, bounded intervals of positive length; their endpoints are included. For $I=[a,b]$, write $\ell(I)=b-a$, and define its threefold dilation about its center by

3I=\left[\frac{a+b}{2}-\frac{3\ell(I)}{2},\ \frac{a+b}{2}+\frac{3\ell(I)}{2}\right]=[a-\ell(I),\,b+\ell(I)].

Thus $3I$ has the same center as $I$ and three times its length. Intersecting intervals include intervals that share just an endpoint: for example, $[0,1]$ intersects $[1,2]$. This endpoint convention matters because the selected intervals must be disjoint as sets.

The Finite Greedy Selection Lemma

Theorem (Finite Vitali Selection for Intervals): Let $\mathcal{F}$ be a finite family of closed bounded intervals of positive length in $(\mathbb{R},\mathcal{L},m)$. There is a pairwise disjoint subfamily $\mathcal{G}\subseteq\mathcal{F}$ such that every $I\in\mathcal{F}$ is contained in $3J$ for some $J\in\mathcal{G}$. If $\mathcal{F}$ is empty, take $\mathcal{G}$ empty, and the covering assertion is vacuous.

The construction treats the family as indexed if intervals are repeated. While any intervals remain, choose one of greatest length, add it to the selected family, and remove it and every remaining interval that intersects it. If several remaining intervals have the same greatest length, choose any one of them. Since the family is finite, the procedure stops after finitely many choices.

Proof. First suppose $\mathcal{F}$ is nonempty. At each stage the chosen interval has greatest length among the intervals then remaining. The procedure removes at least the chosen interval at every stage, so it terminates after at most the number of members of $\mathcal{F}$ stages. Two distinct chosen intervals cannot intersect: when the earlier of the two was chosen, every interval still remaining that intersected it was removed, so the later interval could not have been chosen. Thus the selected family $\mathcal{G}$ is pairwise disjoint.

Each original interval is either selected or removed at a stage when an interval $J$ is selected. In the latter case it intersects $J$, and its length is at most $\ell(J)$, because it was still available when the longest remaining interval was chosen. A selected interval is itself contained in its own dilation, so it remains to check the removed intervals. Write the removed interval as $I=[a,b]$ and the selected interval that removed it as $J=[c,d]$. Their intersection gives $a\le d$ and $b\ge c$. Also, $\ell(I)\le\ell(J)$. Since $b-a=\ell(I)$, these inequalities imply $$ a=b-\ell(I)\ge c-\ell(I)\ge c-\ell(J), \qquad b=a+\ell(I)\le d+\ell(I)\le d+\ell(J). $$ But $3J=[c-\ell(J),d+\ell(J)]$, so $I\subseteq3J$. This proves the covering assertion for every original interval. If the family is empty, the specified empty selection is pairwise disjoint and covers the empty family. $\square$

Worked Applications of the Selection Rule

Worked Example: A Long Interval Removes Two Overlapping Intervals

Apply the greedy procedure to the family $[0,6]$, $[2,5]$, $[5,9]$, and $[10,12]$. All endpoints are included, so $[0,6]$ and $[5,9]$ intersect at $5$.

The lengths, in the listed order, are $6,3,4,2$. The first choice is $[0,6]$, the unique longest interval. It intersects $[2,5]$ and $[5,9]$, so both are removed. The interval $[10,12]$ does not intersect $[0,6]$, because $10>6$, and is chosen at the next stage. The selected family is therefore $\mathcal{G}=\{[0,6],[10,12]\}$. Its intervals are disjoint, since $6<10$.

The center of $[0,6]$ is $3$, and its length is $6$, so $3[0,6]=[3-9,3+9]=[-6,12]$. The center of $[10,12]$ is $11$, and its length is $2$, so $3[10,12]=[11-3,11+3]=[8,14]$. The original intervals are covered: $[0,6]$, $[2,5]$, and $[5,9]$ lie in $[-6,12]$, while $[10,12]$ lies in $[8,14]$. Check: the removed interval $[5,9]$ intersects $[0,6]$, has length $4\le6$, and is contained in $3[0,6]=[-6,12]$, as the theorem predicts.

Worked Example: Equal Lengths and Endpoint Contact

Consider $[0,4]$, $[3,7]$, and $[6,10]$, each of length $4$. Resolve the tie by choosing the first interval in the displayed order. The interval $[0,4]$ is selected, and $[3,7]$ is removed because it intersects $[0,4]$. The interval $[6,10]$ remains: $6>4$, so it is disjoint from the selected interval. It is then selected. Thus $\mathcal{G}=\{[0,4],[6,10]\}$; the gap between the selected intervals is $(4,6)$.

The centers are $2$ and $8$, and each selected interval has length $4$. Consequently, $3[0,4]=[2-6,2+6]=[-4,8]$, and $3[6,10]=[8-6,8+6]=[2,14]$. The removed interval $[3,7]$ is contained in both dilations, since $3\ge-4$, $7\le8$, $3\ge2$, and $7\le14$. The original intervals are therefore all covered. Check: the two selected intervals are disjoint as sets because $[0,4]\cap[6,10]=\varnothing$; their dilations are allowed to intersect at $8$.

Worked Example: Following Several Greedy Stages

Use the family $[0,8]$, $[7,12]$, $[11,15]$, $[16,20]$, $[19,22]$, and $[30,31]$. Their lengths, in order, are $8,5,4,4,3,1$. First select $[0,8]$; this removes $[7,12]$, which intersects it. Of the intervals remaining, $[11,15]$ and $[16,20]$ tie for greatest length $4$. Choose $[11,15]$ first. It does not intersect $[16,20]$, because $15<16$, so $[16,20]$ remains and is selected next. It removes $[19,22]$, which intersects it. Finally, $[30,31]$ is selected. The resulting family is $\mathcal{G}=\{[0,8],[11,15],[16,20],[30,31]\}$, and each pair of selected intervals is disjoint.

The dilations are calculated from their centers and lengths: $3[0,8]=[4-12,4+12]=[-8,16]$; $3[11,15]=[13-6,13+6]=[7,19]$; $3[16,20]=[18-6,18+6]=[12,24]$; and $3[30,31]=[30.5-1.5,30.5+1.5]=[29,32]$. The removed interval $[7,12]$ lies in $[-8,16]$, and $[19,22]$ lies in $[12,24]$. Each selected interval lies in its own dilation. Thus every interval in the input family is covered. Check: the selected lengths sum to $8+4+4+1=17$, and the unselected intervals have lengths $5$ and $3$, each no greater than the selected interval that removed it.

A Measure Bound from the Covering

Corollary: Under the hypotheses of the finite selection theorem in $(\mathbb{R},\mathcal{L},m)$, if $\mathcal{G}$ is the selected family, then $$ m\left(\bigcup_{I\in\mathcal{F}}I\right)\le 3\sum_{J\in\mathcal{G}}\ell(J) =3m\left(\bigcup_{J\in\mathcal{G}}J\right). $$

Proof. The theorem gives $\bigcup_{I\in\mathcal{F}}I\subseteq\bigcup_{J\in\mathcal{G}}3J$. These are finite unions of closed intervals, hence Lebesgue measurable. Monotonicity and finite subadditivity of Lebesgue measure give $$ m\left(\bigcup_{I\in\mathcal{F}}I\right) \le m\left(\bigcup_{J\in\mathcal{G}}3J\right) \le\sum_{J\in\mathcal{G}}m(3J) =3\sum_{J\in\mathcal{G}}\ell(J). $$ The last equality uses $m(3J)=3\ell(J)$ for each interval $J$. Since the selected intervals are pairwise disjoint and form a finite family, additivity of Lebesgue measure gives $m(\bigcup_{J\in\mathcal{G}}J)=\sum_{J\in\mathcal{G}}\ell(J)$, proving the stated equality. For the empty family both sides are zero. $\square$

This estimate is useful because it controls the measure of the whole original union using only the lengths of disjoint selected intervals. The factor $3$ comes directly from enlarging each selected interval to three times its length; no assumption that the original intervals are disjoint is needed.

A Common Greedy-Selection Pitfall

It is not enough to choose an arbitrary interval and discard everything that intersects it. For example, take $J=[0,4]$ and $I=[3,9]$. They intersect, but $\ell(J)=4<6=\ell(I)$. If $J$ were chosen first, its threefold dilation would be $3J=[-4,8]$, which does not contain $I$: the endpoint $9$ lies outside. This does not contradict the theorem, because the greedy rule would choose the longer interval $I$, not $J$. In fact, $3I=[3-6,9+6]=[-3,15]$ contains $J=[0,4]$. The length comparison is essential to the proof of containment.

The argument depends on finiteness so that a longest remaining interval exists at each stage and the procedure terminates. It also depends on intervals being one-dimensional: the proof uses the order of their endpoints to convert intersection and a length bound into containment in a fixed dilation. The higher-dimensional selection problem requires a separate geometric argument.

Check Your Understanding

For each question, use closed intervals, so that intervals sharing an endpoint count as intersecting.

Apply the greedy procedure to $[0,5]$, $[4,8]$, and $[9,11]$, resolving a tie by choosing the first displayed interval. What is the selected family, and what are its threefold dilations?
Suppose $I=[a,b]$ intersects $J=[c,d]$ and $\ell(I)\le\ell(J)$. Use the intersection inequalities to show that $a\ge c-\ell(J)$ and $b\le d+\ell(J)$.
Explain why two intervals selected at different stages cannot share even one endpoint.
For the family in the third worked example, compute the sum of the selected lengths and the right-hand side of the measure bound in the corollary.
Give an intersecting pair for which the shorter interval’s threefold dilation fails to contain the longer interval. Why does the greedy rule avoid selecting the shorter interval first?