Countable Subadditivity by Epsilon Allocation

From Individual Covers to a Cover of the Union

Lebesgue outer measure is built by covering a set with intervals and taking the infimum of the total lengths. To bound the outer measure of a countable union, it is natural to cover each set separately and then combine those covers. The subtlety is that an infimum need not be attained: for each set we may have to use a cover whose cost is slightly larger than its outer measure. Countable subadditivity follows by making all those small excesses add up to an arbitrarily small total.

Throughout, the ambient space is $\mathbb{R}$, and $E,A_1,A_2,\ldots$ are arbitrary subsets of $\mathbb{R}$, not necessarily Borel or Lebesgue measurable. There is no measure space assumption here: $m^*$ is an outer measure on the power set of $\mathbb{R}$. Using the interval-covering definition, $m^*(E)$ is the infimum of $\sum_j |I_j|$ over all finite or countable covers $E\subseteq\bigcup_j I_j$ by open intervals $I_j$, where $|I_j|$ is the length of $I_j$. The empty set has the empty cover, of cost zero. The infimum and sums take values in $[0,\infty]$.

Definition (near-minimizing cover): If $m^*(E)<\infty$ and $\eta>0$, a cover of $E$ whose total interval length is less than $m^*(E)+\eta$ is an $\eta$-near-minimizing cover. Such a cover exists by the defining property of an infimum; it need not have cost exactly $m^*(E)$.

Allocating the Error Budget

Suppose the total outer measure $\sum_{n=1}^{\infty}m^*(A_n)$ is finite. To choose a cover of every $A_n$, we need a positive error allowance $\eta_n$ for each one. Choosing the same allowance for all $n$ would generally produce an infinite total error. Instead, fix $\varepsilon>0$ and set $\eta_n=\varepsilon/2^n$. The geometric series gives $\sum_{n=1}^{\infty}\eta_n=\varepsilon$, so all the individual errors fit within one prescribed budget.

\sum_{n=1}^{\infty}\frac{\varepsilon}{2^n} =\varepsilon\left(\frac12+\frac14+\frac18+\cdots\right) =\varepsilon.

The cover chosen for $A_n$ may depend on $n$. Once each has been chosen, the collection of all intervals in all those covers is countable: its members are indexed by pairs of positive integers, and the set of such pairs can be enumerated. It therefore forms an admissible countable interval cover of $\bigcup_n A_n$.

Countable Subadditivity

Theorem (Countable subadditivity of Lebesgue outer measure): For every sequence $(A_n)_{n\ge1}$ of subsets of $\mathbb{R}$, $$ m^*\left(\bigcup_{n=1}^{\infty}A_n\right) \le \sum_{n=1}^{\infty}m^*(A_n). $$ The inequality is in the extended nonnegative real numbers, so an infinite right-hand side is allowed.

Proof. Write $S=\sum_{n=1}^{\infty}m^*(A_n)$. If $S=\infty$, the claimed inequality holds because every outer measure is at most $+\infty$. Now suppose $S<\infty$, and fix $\varepsilon>0$. Each $m^*(A_n)$ is finite, since it is a nonnegative term in a finite sum. For each $n$, the definition of the infimum supplies a finite or countable open-interval cover $\{I_{n,j}\}_j$ of $A_n$ such that $$ \sum_j |I_{n,j}|<m^*(A_n)+\frac{\varepsilon}{2^n}. $$ The combined family $\{I_{n,j}:n\ge1,\ j\}$ is countable and covers $\bigcup_n A_n$. Its total length is the sum of the nonnegative lengths over all pairs $(n,j)$. Regrouping a nonnegative countable sum by its first index gives the same sum, and hence its cost is $$ \sum_{n=1}^{\infty}\sum_j |I_{n,j}| \le \sum_{n=1}^{\infty}\left(m^*(A_n)+\frac{\varepsilon}{2^n}\right) =S+\varepsilon. $$ The definition of outer measure bounds $m^*(\bigcup_n A_n)$ by the cost of this particular cover, so $m^*(\bigcup_n A_n)\le S+\varepsilon$. This holds for every $\varepsilon>0$. If the left side were greater than $S$, choosing $\varepsilon$ smaller than that positive difference would contradict the inequality. Therefore $m^*(\bigcup_n A_n)\le S$, as claimed. $\square$

Corollary (Finite subadditivity): For any finite collection $A_1,\ldots,A_N\subseteq\mathbb{R}$, $$ m^*\left(\bigcup_{n=1}^{N}A_n\right)\le\sum_{n=1}^{N}m^*(A_n). $$

Proof. Set $A_n=\varnothing$ for $n>N$. The union does not change, and the added terms in the right-hand sum are $m^*(\varnothing)=0$. The stated inequality is then the countable subadditivity theorem. $\square$

Worked Applications

Worked Example: A Family of Short Intervals

For each $n\ge1$, let $A_n=(3n,3n+2^{-n})$. Bound the outer measure of their union using the given intervals as a cover.

The interval $A_n$ itself covers $A_n$ and has length $(3n+2^{-n})-3n=2^{-n}$. Taking all these intervals together covers $\bigcup_{n\ge1}A_n$. Their total length is $$ \sum_{n=1}^{\infty}2^{-n} =\frac{1/2}{1-1/2} =1. $$ Thus the definition of outer measure gives $m^*(\bigcup_{n\ge1}A_n)\le1$. Equivalently, countable subadditivity gives the same bound because $m^*(A_n)\le2^{-n}$ for every $n$. Check: the first three interval lengths are $1/2$, $1/4$, and $1/8$; their partial sum is $7/8$, and the remaining geometric tail is $1/8$, giving total length $1$. This is an upper bound, not a claim that the union has outer measure exactly $1$.

Worked Example: Choosing Covers from Given Outer-Measure Values

Suppose a sequence of sets satisfies $m^*(A_n)=2^{-n}$ for every $n\ge1$. Use an error budget $\varepsilon=1/8$ to bound the cost of covers chosen separately for the sets.

Here $\sum_{n\ge1}m^*(A_n)=\sum_{n\ge1}2^{-n}=1$. Allocate $\eta_n=\varepsilon/2^n=1/2^{n+3}$. For each $n$, choose a cover of $A_n$ with cost less than $$ 2^{-n}+\frac{1}{2^{n+3}} =\frac{8}{2^{n+3}}+\frac{1}{2^{n+3}} =\frac{9}{2^{n+3}}. $$ Combining the covers gives a cover of the union with total cost at most the sum of these bounds: $$ \sum_{n=1}^{\infty}\frac{9}{2^{n+3}} =\frac{9}{8}\sum_{n=1}^{\infty}2^{-n} =\frac98. $$ Consequently $m^*(\bigcup_n A_n)\le9/8=1+1/8$. Check: the individual error allowances sum to $\sum_{n\ge1}1/2^{n+3}=1/8$, exactly the prescribed budget. The assumed outer-measure values are the input to this illustration; the argument does not require the infima to be attained.

Worked Example: When the Sum of the Bounds Is Infinite

Let $A_n=(2n,2n+1)$ for $n\ge1$. What does countable subadditivity say if we use these intervals as individual covers?

The length of each interval is $(2n+1)-2n=1$, so $m^*(A_n)\le1$ for every $n$. The resulting sum of these upper bounds is $\sum_{n\ge1}1=\infty$. Thus this information only yields $m^*(\bigcup_n A_n)\le\infty$, which is true but gives no finite bound. For instance, the first $N$ intervals in the chosen cover have total length $N$, which grows without bound as $N$ increases. Check: for $N=3$, the three lengths sum to $1+1+1=3$, and the sum of the first $N$ lengths is $N$. The theorem remains valid; it is the available upper bound that is uninformative.

Why the Allocation and the Infimum Matter

Common mistake: assigning the same error to every set. If one asks for a cover of each $A_n$ with cost less than $m^*(A_n)+0.1$, the total allowances over the first $N$ sets are $0.1N$. As $N$ grows, these allowances are unbounded; the argument cannot conclude a bound of $S$ plus a fixed finite error. The correction is to choose a summable budget, such as $\eta_n=\varepsilon/2^n$. For $\varepsilon=0.1$, its total is $0.1\sum_{n\ge1}2^{-n}=0.1$, regardless of how many covers are combined.

Common mistake: assuming the best cover exists. The definition gives an infimum of covering costs, not necessarily a cover with cost equal to that infimum. The proof uses only what the infimum guarantees: for every positive $\eta_n$, there is a cover with cost strictly less than $m^*(A_n)+\eta_n$, provided $m^*(A_n)<\infty$. When the sum of the outer measures is finite, every term is finite and this choice is available. When the sum is infinite, the desired inequality is already automatic in the extended-real order, so no near-minimizing covers are needed.

Countable subadditivity is a basic structural property of outer measure. Its proof uses only the interval-cover definition, the approximation property of an infimum, and a summable error allocation. It makes no measurability assumption on the sets in the union and does not assert countable additivity; it is an upper bound obtained by combining covers.

Check Your Understanding

For each question, distinguish the cost of a particular cover from the outer measure, which is the infimum over all admissible covers.

For $\varepsilon>0$, verify that $\eta_n=\varepsilon/2^{n+1}$ has total sum $\varepsilon/2$. Would this allocation still suffice for a total error budget of $\varepsilon$?
In the proof, why does a finite value of $\sum_n m^*(A_n)$ imply that each $m^*(A_n)$ is finite?
Suppose $m^*(A_n)\le 3^{-n}$ for all $n\ge1$. What finite upper bound does countable subadditivity give for $m^*(\bigcup_n A_n)$?
Explain why a countable collection of countable interval covers is still a countable collection of intervals.
What part of the proof changes when $\sum_n m^*(A_n)=\infty$, and why does the desired inequality then hold automatically?