From a Premeasure to a Covering Infimum
A premeasure assigns costs to sets in a ring, but the sets we want to measure may not belong to that ring. The covering construction extends the cost assignment to every subset of the underlying space: cover a set by countably many ring sets, add their costs, and take the infimum over all such covers. The construction is driven by two tasks. One is to find covers whose total cost is small; the other is to show that every possible cover has cost at least a stated bound.
Let \(X\) be a set and let \(\mathcal{R}\) be a ring of subsets of \(X\). Thus \(\mathcal{R}\) contains \(\varnothing\), is closed under finite unions, and is closed under differences. A premeasure on \(\mathcal{R}\) is a function \(\rho:\mathcal{R}\to[0,\infty]\) with \(\rho(\varnothing)=0\) that is countably additive whenever the disjoint union belongs to \(\mathcal{R}\): if \(R_j\in\mathcal{R}\) are pairwise disjoint and \(R=\bigcup_{j=1}^{\infty}R_j\in\mathcal{R}\), then \(\rho(R)=\sum_{j=1}^{\infty}\rho(R_j)\). A premeasure is not yet a measure on a sigma-algebra; its domain is only the ring.
The infimum is a greatest lower bound, not necessarily a cost achieved by one particular cover. In practical calculations, an upper bound comes from exhibiting a cover. A lower bound requires an argument that applies to every admissible cover. The sigma-finiteness assumption from the extension setting means that \(X\) can be covered by countably many ring sets of finite \(\rho\)-cost; it is useful for extension theory, but the formula above makes sense whether or not \(\rho\) is sigma-finite.
Two Basic Properties of the Infimum
Proof. Every countable family of ring sets that covers \(B\) also covers \(A\), because \(A\subseteq B\). Thus the collection of costs of covers of \(B\) is contained in the collection of costs of covers of \(A\). The infimum over the latter collection cannot exceed the infimum over the former. If \(B\) has no cover, then \(\mu^*_\rho(B)=+\infty\), and the claimed inequality holds because every value in \([0,\infty]\) is at most \(+\infty\). \(\square\)
Proof. The collection of costs of covers of \(A\) is nonempty, since its infimum is finite; an empty collection has infimum \(+\infty\). By the defining property of the infimum, if no cover had cost less than \(\mu^*_\rho(A)+\varepsilon\), that number would be a lower bound for all cover costs strictly greater than their greatest lower bound. This is impossible. Therefore at least one cover has cost less than \(\mu^*_\rho(A)+\varepsilon\). \(\square\)
The approximation proposition does not assert that a best cover exists. It says that when the infimum is finite, covers can approach it as closely as desired. Conversely, a lower-bound proof must not rely on a best cover being attained: it must apply to each cover, regardless of whether any cover realizes the infimum.
Worked Covering Calculations
Worked Example: A Weighted Subset of a Finite Space
Let \(X=\{a,b,c\}\), let \(\mathcal{R}\) be the collection of all subsets of \(X\), and assign weights \(w(a)=2\), \(w(b)=5\), and \(w(c)=1\). Set \(\rho(R)=\sum_{x\in R}w(x)\) for \(R\in\mathcal{R}\). This is a premeasure: for disjoint sets, each point's weight appears in exactly one set, so the weight of their union is the sum of their weights. It is finite and sigma-finite. Compute \(\mu^*_\rho(\{a,c\})\).
The single ring set \(R_1=\{a,c\}\) is a cover, and its cost is \(\rho(R_1)=w(a)+w(c)=2+1=3\). Hence \(\mu^*_\rho(\{a,c\})\le3\). For the reverse inequality, take any countable cover \((R_j)\) of \(\{a,c\}\). At least one \(R_j\) contains \(a\), and at least one \(R_j\) contains \(c\). In the sum \(\sum_j\rho(R_j)\), the weight \(2\) for \(a\) and the weight \(1\) for \(c\) are therefore each counted at least once. All other contributions are nonnegative, so \(\sum_j\rho(R_j)\ge2+1=3\). This applies to every cover, giving \(\mu^*_\rho(\{a,c\})\ge3\).
Consequently \(\mu^*_\rho(\{a,c\})=3\). Check: the exhibited cover has cost \(3\), and the lower bound shows no cover can cost less than \(3\); the upper and lower bounds agree.
Worked Example: Even Integers with Summable Weights
Take \(X=\mathbb{N}=\{1,2,\ldots\}\), let \(\mathcal{R}\) consist of all finite subsets of \(\mathbb{N}\), and define \(\rho(F)=\sum_{n\in F}2^{-n}\). This is a premeasure on \(\mathcal{R}\): if pairwise disjoint finite sets have a finite union, only finitely many are nonempty, and the weight sums add. It is sigma-finite because \(\mathbb{N}=\bigcup_{k\ge1}\{k\}\) and \(\rho(\{k\})=2^{-k}<\infty\). Compute the covering infimum of \(E=\{2,4,6,\ldots\}\).
Cover \(E\) by the countable family of singleton ring sets \(\{2k\}\), \(k\ge1\). The total cost is $$ \sum_{k=1}^{\infty}\rho(\{2k\})=\sum_{k=1}^{\infty}2^{-2k} =\sum_{k=1}^{\infty}\left(\frac14\right)^k =\frac{1/4}{1-1/4}=\frac13. $$ Thus \(\mu^*_\rho(E)\le\frac13\).
For a lower bound, let \((F_j)\) be any countable cover of \(E\) by finite subsets of \(\mathbb{N}\). Fix \(K\ge1\). Each of \(2,4,\ldots,2K\) belongs to at least one \(F_j\), so its weight is counted at least once in \(\sum_j\rho(F_j)\). Since all weights are nonnegative, $$ \sum_{j=1}^{\infty}\rho(F_j)\ge\sum_{k=1}^{K}2^{-2k} =\frac14\frac{1-(1/4)^K}{1-1/4} =\frac13(1-4^{-K}). $$ As \(K\to\infty\), the right side tends to \(\frac13\). The cover was arbitrary, so every cover has cost at least \(\frac13\). Therefore \(\mu^*_\rho(E)\ge\frac13\), and together with the singleton-cover bound, \(\mu^*_\rho(E)=\frac13\). Check: the partial sums are \(\frac14\), \(\frac5{16}\), and \(\frac{21}{64}\) for \(K=1,2,3\); the formula \(\frac13(1-4^{-K})\) gives each of these values, and they approach \(\frac13\).
Worked Example: Infinite Cost Despite Sigma-Finiteness
Let \(X=\mathbb{N}\), let \(\mathcal{R}\) again be the finite subsets, and now set \(\rho(F)=|F|\), the number of elements of \(F\). This is a premeasure: when a disjoint union is finite, only finitely many of the disjoint finite sets are nonempty, and cardinalities add. It is sigma-finite because the singleton sets cover \(\mathbb{N}\), each with cost \(1\). Find \(\mu^*_\rho(\mathbb{N})\).
The singleton family \((\{n\})_{n\ge1}\) is a countable ring cover, so covers do exist. Consider any countable cover \((F_j)\) by finite sets and fix \(K\ge1\). The first \(K\) integers must all occur among the sets \(F_j\). Their total number of occurrences across the cover is at least \(K\), so \(\sum_j|F_j|\ge K\). This holds for every \(K\), which forces \(\sum_j|F_j|=+\infty\). Every admissible cover therefore has infinite cost, and \(\mu^*_\rho(\mathbb{N})=+\infty\). Check: the singleton cover itself has cost \(\sum_{n=1}^{\infty}1=+\infty\), consistent with the lower bound. Sigma-finiteness supplies a countable cover by finite-cost sets; it does not guarantee that the sum of the costs in a cover is finite.
A Common Covering Error
A frequent mistake is to minimize over finite covers only. In the weighted example, no finite family of finite subsets of \(\mathbb{N}\) can cover the infinite set \(E=\{2,4,6,\ldots\}\): a finite union of finite sets is finite. If one incorrectly restricts the definition to finite covers, one might assign \(E\) the value \(+\infty\) because there are no such covers. The actual definition permits countable covers, and the singleton cover has cost \(\frac13\).
The correction is to check the permitted covers before estimating their costs. For an upper bound, exhibit a valid finite or countable cover and compute its full cost. For a lower bound, start with an arbitrary valid cover and show that its cost is at least the proposed value. In particular, do not treat an infimum as a minimum, and do not assume that a cover must have finitely many members.
The covering formula is the construction step: it produces a set function on all subsets of \(X\). Further properties, including the verification that this set function is an outer measure and the proof that it agrees with \(\rho\) on the original ring, require separate arguments. The calculations above use only the definition, the infimum properties proved here, and the stated premeasure assumptions.
Check Your Understanding
In each question, distinguish the cost of one chosen cover from a lower bound that applies to every cover.
- For the finite weighted space in the first example, compute \(\mu^*_\rho(\{b,c\})\) by giving a cover and proving a matching lower bound.
- In the weighted-natural-numbers example, what is the cost of covering \(\{1,3,5,\ldots\}\) by singleton sets? What kind of argument would establish that no cover has smaller cost?
- Explain why sigma-finiteness does not imply that \(\mu^*_\rho(X)\) is finite, using the counting-premeasure example.
- State the monotonicity property of the covering infimum and identify the inclusion between the collections of covers that proves it.
- If \(\mu^*_\rho(A)=4\), what does the approximation proposition guarantee for \(\varepsilon=0.01\)? Does it guarantee a cover of cost exactly \(4\)?