Outer Measures Built from Covering Costs

From Covering Costs to an Outer Measure

A useful way to assign a size to every subset of a space is to specify the costs of certain basic covering sets, then charge a set the least total cost of any countable cover. The covering family need not be a sigma-algebra, and its members need not be measurable sets. The construction instead produces a set function on the entire power set, with the outer measure axioms guaranteed by how covers combine.

Let $X$ be a set, let $\mathcal{C}\subseteq\mathcal{P}(X)$ be a family containing $\varnothing$, and let $c:\mathcal{C}\to[0,\infty]$ be a cost function with $c(\varnothing)=0$. A countable $\mathcal{C}$-cover of $A\subseteq X$ is a finite or countably infinite sequence $(C_j)$ of members of $\mathcal{C}$ such that $A\subseteq\bigcup_j C_j$. Repetitions are allowed, and the cost of this cover is $\sum_j c(C_j)$, with the sum interpreted in $[0,\infty]$. The empty set can also be covered by the empty sequence, whose cost is zero.

Definition: For $A\subseteq X$, define its covering-cost outer measure by $$ \mu^*(A)=\inf\left\{\sum_j c(C_j): (C_j)\text{ is a countable }\mathcal{C}\text{-cover of }A\right\}. $$ The infimum of an empty collection of admissible cover costs is $+\infty$. Thus $\mu^*(A)=+\infty$ if $A$ has no countable cover from $\mathcal{C}$.

An outer measure on $X$ is a function $\mu^*:\mathcal{P}(X)\to[0,\infty]$ satisfying $\mu^*(\varnothing)=0$, monotonicity, and countable subadditivity. These properties do not assert countable additivity on all subsets of $X$. The covering construction gives the outer measure axioms without requiring any further assumptions on $\mathcal{C}$ or on the costs beyond those just stated.

Why the Construction Satisfies the Axioms

Theorem: For any set $X$, family $\mathcal{C}\subseteq\mathcal{P}(X)$ containing $\varnothing$, and cost function $c:\mathcal{C}\to[0,\infty]$ with $c(\varnothing)=0$, the function $\mu^*$ defined above is an outer measure on $X$.

Proof. First, the empty set has a cover of cost zero, so $\mu^*(\varnothing)\le 0$. All cover costs are nonnegative, so $\mu^*(\varnothing)\ge 0$, and therefore $\mu^*(\varnothing)=0$.

For monotonicity, suppose $A\subseteq B\subseteq X$. Every countable $\mathcal{C}$-cover of $B$ also covers $A$. Thus the collection of costs admissible for $B$ is contained in the collection admissible for $A$. Taking infima gives $\mu^*(A)\le\mu^*(B)$. This also covers the case where $B$ has no admissible cover: then $\mu^*(B)=+\infty$, and the inequality holds in the extended order.

For countable subadditivity, let $A_1,A_2,\ldots\subseteq X$. If $\sum_{n=1}^{\infty}\mu^*(A_n)=+\infty$, then $\mu^*(\bigcup_n A_n)\le\sum_n\mu^*(A_n)$ holds because the right side is $+\infty$. It remains to consider the case where this sum is finite. Then every $\mu^*(A_n)$ is finite. Fix $\varepsilon>0$. By the definition of the infimum, for each $n$ there is a countable $\mathcal{C}$-cover of $A_n$ whose cost is less than $\mu^*(A_n)+\varepsilon 2^{-n}$. (A finite infimum guarantees that the set of admissible costs is nonempty.) Put all these covers together. A countable union of countable index sets is countable, and the combined family covers $\bigcup_n A_n$. Its total cost is at most the sum of the individual costs, so

\mu^*\left(\bigcup_{n=1}^{\infty}A_n\right) \le \sum_{n=1}^{\infty}\mu^*(A_n) +\varepsilon\sum_{n=1}^{\infty}2^{-n} =\sum_{n=1}^{\infty}\mu^*(A_n)+\varepsilon.

Since this holds for every $\varepsilon>0$, the left side is at most $\sum_n\mu^*(A_n)$. This proves countable subadditivity and completes the proof. $\square$

The small error allowances are essential to the proof’s logic: an infimum need not be attained by any particular cover. Also, there is no need to choose a cover when the total on the right is infinite; subadditivity is then automatic.

Worked Covering-Cost Calculations

Worked Example: Weighted Singleton Covers

Take $X=\mathbb{N}=\{1,2,\ldots\}$, $\mathcal{C}=\{\varnothing\}\cup\{\{n\}:n\in\mathbb{N}\}$, and $c(\{n\})=2^{-n}$, with $c(\varnothing)=0$. Compute $\mu^*(\{1,3\})$.

Any cover of $\{1,3\}$ must include $\{1\}$ at least once and $\{3\}$ at least once, since these are the only nonempty members of $\mathcal{C}$ containing the respective points. Therefore every such cover has cost at least $2^{-1}+2^{-3}$. The cover consisting of precisely these two singletons attains that cost. Hence

\mu^*(\{1,3\})=2^{-1}+2^{-3}=\frac12+\frac18=\frac58.

Check: the two chosen sets cover both points, and their total cost recomputes as $4/8+1/8=5/8$. No cover can omit either singleton, so this cost is minimal.

Worked Example: Finite-Set Costs and a Set with No Cover

Let $X=\mathbb{R}$, let $\mathcal{C}$ consist of all finite subsets of $\mathbb{R}$, including $\varnothing$, and set $c(F)=|F|$. For a finite set $A\subseteq\mathbb{R}$ with $k$ elements, the one-set cover $A$ has cost $k$, so $\mu^*(A)\le k$. Conversely, if $(F_j)$ covers $A$, then the number $k$ of distinct points in $A$ cannot exceed the total number of point occurrences counted across the $F_j$. Thus $k\le\sum_j|F_j|$, giving $\mu^*(A)\ge k$. Therefore $\mu^*(A)=k$. For example, if $A=\{2,5,9\}$, its cost is $3$, and every cover has total cost at least $3$.

Now consider $A=\mathbb{N}$. Every countable family of finite sets has a countable union, so it can cover $\mathbb{N}$; however, every such cover has infinite total cost. Indeed, for each positive integer $k$, the first $k$ points $\{1,\ldots,k\}$ must occur among the covering sets, so $\sum_j|F_j|\ge k$. Since this holds for every $k$, the sum is $+\infty$. Hence $\mu^*(\mathbb{N})=+\infty$.

Finally, $\mathbb{R}$ has no countable cover by finite sets: the union of countably many finite sets is countable, whereas $\mathbb{R}$ is uncountable. Its collection of admissible cover costs is empty, so the convention in the definition gives $\mu^*(\mathbb{R})=+\infty$. Check: $\mathbb{N}$ has covers but every cover costs $+\infty$; $\mathbb{R}$ has no admissible cover at all. Both yield outer measure $+\infty$, for distinct reasons.

Worked Example: A Small Weighted Set-Cover Problem

Let $X=\{a,b,c\}$ and take $\mathcal{C}=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{b,c\}\}$. Assign cost $2$ to each singleton, cost $3$ to each of $\{a,b\}$ and $\{b,c\}$, and cost $0$ to $\varnothing$. Compute $\mu^*(X)$.

A cover using $\{a,b\}$ and $\{c\}$ has cost $3+2=5$, so $\mu^*(X)\le5$. Likewise, $\{a\}$ together with $\{b,c\}$ costs $2+3=5$. To see that no cover costs less, consider how it covers $a$ and $c$. If it uses both $\{a,b\}$ and $\{b,c\}$, those sets alone cost $3+3=6$. If it uses $\{a,b\}$ but not $\{b,c\}$, it must also use $\{c\}$, giving cost at least $3+2=5$. If it uses $\{b,c\}$ but not $\{a,b\}$, it must also use $\{a\}$, again giving at least $3+2=5$. If it uses neither pair, it must use all three singletons, at cost $2+2+2=6$. Additional sets cannot decrease any of these costs because costs are nonnegative. Thus $\mu^*(X)=5$.

Check: the cover $\{a,b\},\{c\}$ covers $a,b,c$ and costs $3+2=5$; the cases above show every cover costs at least $5$.

What the Construction Does—and Does Not—Provide

The choice of $\mathcal{C}$ and $c$ determines what counts as an economical cover. Some subsets may have finite outer measure, some may have infinite outer measure because all their covers are expensive, and some may have infinite outer measure because no cover exists. These are all legitimate outcomes of the construction.

A common mistake is to treat an infimum over no admissible covers as zero. For example, in the finite-subset construction above, there is no countable cover of $\mathbb{R}$ by members of $\mathcal{C}$. Incorrectly replacing the infimum over this empty collection by zero would give $\mu^*(\mathbb{R})=0$. The correct convention is $\inf\varnothing=+\infty$, so $\mu^*(\mathbb{R})=+\infty$. This convention also makes monotonicity work when the larger set has no cover.

Another error is to infer countable additivity from the outer measure axioms. The proof establishes monotonicity and countable subadditivity on $\mathcal{P}(X)$, not countable additivity for arbitrary disjoint subsets. Nor does it show that the covering sets themselves form a sigma-algebra. The outer measure is a set function on all subsets; further questions about which sets interact with it as measurable sets require an additional criterion.

In summary, the method has three ingredients: choose a family of allowed covering sets, assign each one a nonnegative extended-real cost, and take the infimum of total costs over countable covers. Combining covers proves subadditivity, while inclusion of cover collections proves monotonicity. The empty-cover convention handles both the empty set and sets the family cannot cover.

Check Your Understanding

Use the definition and the proof of the outer measure axioms to answer the following.

Why must every countable cover of a set $A$ also be a cover of $B$ when $B\subseteq A$, and what inequality does this give for their outer measures?
In the weighted-singleton construction on $\mathbb{N}$, compute the outer measure of $\{2,5\}$.
For the family of finite subsets of $\mathbb{R}$ with cost $c(F)=|F|$, explain why $\mathbb{N}$ has covers but $\mathbb{R}$ does not.
Where does the proof of countable subadditivity use an $\varepsilon$-allowance, and why is it needed?
What value is assigned to the infimum of an empty collection of admissible cover costs, and how does that apply to an uncovered set?

Outer Measures Built from Covering Costs

What You'll Learn