This lecture note is still being edited: the text may contain typos, inaccuracies, and passages that have not yet been fully polished. If you find something, please let the author know (contact info on the course page).
The material of this chapter is abstract: \(X\) is an arbitrary set, \(\mathcal S \subset 2^X\) is an arbitrary system of subsets (a semiring, unless stated otherwise), \(\mu\) is an arbitrary nonnegative set function on it.
Let \(\mathcal{S} \subset 2^X\) be some collection of subsets of \(X\). By a nonnegative set function (on \(\mathcal{S}\)) we mean any function of the form \(m: \mathcal{S} \to [0, +\infty ]\). Note that it may take infinite values.
Definition 1 A nonnegative set function \(m: \mathcal{S} \to [0, +\infty ]\) is said to be
monotone if \(\forall A, B \in \mathcal{S}, A \subset B\) we have \(m(A) \leq m(B)\)
finitely additive (or simply additive) if for any finite disjoint collection \(A_1, A_2, \dots , A_n \in \mathcal{S}\) such that \(A := \bigsqcup_{k=1}^n A_k \in \mathcal{S}\), we have \(m(A) = \sum_{k=1}^n m(A_k)\):
\[
\left.\begin{array}{r} A \in \mathcal{S} \\ A_1, \ldots , A_n \in \mathcal{S} \\ A_i \cap A_j = \varnothing , \; \forall i \neq j \\ A = \bigsqcup _{i=1}^n A_i \end{array}\right\} \quad \; \Rightarrow \; \quad m(A) = \sum _{k=1}^n m(A_k)
\]
In other words, if an element \(A\) of \(\mathcal{S}\) splits into a disjoint union of other elements \(A_1, A_2, \ldots\) of \(\mathcal{S}\), then the value of \(m\) at \(A\) equals the sum of its values at \(A_1, A_2, \ldots\).
Countable additivity is defined analogously. A countably additive set function is also called \(\sigma\)-additive.
finitely subadditive (or simply subadditive, semiadditive) if
\[
\left.\begin{array}{r} A \in \mathcal{S} \\ A_1, \ldots , A_n \in \mathcal{S} \\ A \subset \bigcup _{i=1}^n A_i \end{array}\right\} \quad \; \Rightarrow \; \quad m(A) \leq \sum _{k=1}^n m(A_k)
\]
In other words, if an element \(A\) of \(\mathcal{S}\) is covered by a union of other elements \(A_1, A_2, \ldots\) of \(\mathcal{S}\), then the value of \(m\) at \(A\) does not exceed the sum of its values at \(A_1, A_2, \ldots\). Too lazy to draw a picture, imagine it yourself.
Note that in this case \(A_1, \ldots , A_n\) need not be disjoint.
Countable subadditivity is defined analogously. A countably subadditive set function is also called \(\sigma\)-subadditive.
finitely superadditive if for any \(A \in \mathcal{S}\) and any collection of disjoint subsets \(A_1, A_2, \ldots , A_n \in \mathcal{S}\) such that \(\bigsqcup_{i=1}^n A_i \subset A\), we have \(\sum_{i=1}^n m(A_i) \leq m(A)\):
\[
\left.\begin{array}{r} A \in \mathcal{S} \\ A_1, \ldots , A_n \in \mathcal{S} \\ A_i \cap A_j = \varnothing , \; \forall i \neq j \\ A \supset \bigsqcup _{i=1}^n A_i \end{array}\right\} \quad \; \Rightarrow \; \quad m(A) \geq \sum _{k=1}^n m(A_k)
\]
In other words, if an element \(A\) of \(\mathcal{S}\) contains pairwise disjoint elements \(A_1, A_2, \ldots\) of \(\mathcal{S}\), then the value of \(m\) at \(A\) is no less than the sum of its values at \(A_1, A_2, \ldots\).
Countable superadditivity is defined analogously.
finite if \(\forall A \in \mathcal{S}: \; m(A) < +\infty\)
\(\sigma\)-finite if \(X\) can be exhausted by a countable collection of sets of finite measure, i.e., \(\exists A_1, A_2, \dots \in \mathcal{S}: X = \bigcup_{k=1}^\infty A_k, \; m(A_k) < \infty \; \forall k \in \mathbb {N}\).
continuous from below if \(m(A_n) \xrightarrow [n\to \infty ]{} m(A)\) for every \(A \in \mathcal{S}\) and every increasing sequence \(A_1, A_2, \ldots \in \mathcal{S}\) such that \(A_n \uparrow A\).
continuous from above if \(m(A_n) \xrightarrow [n\to \infty ]{} m(A)\) for every \(A \in \mathcal{S}\) and every decreasing sequence \(A_1, A_2, \ldots \in \mathcal{S}\) such that \(A_n \downarrow A\) and \(m(A_{n_0}) < +\infty\) for some \(n_0 \in \mathbb {N}\).
The last condition is added because otherwise the counting measure \(\mu\) on \((\mathbb {N}, 2^{\mathbb {N}})\) would fail to be continuous from above, since \(\{ n, n+1, n+2, \dots \} =: A_n \downarrow \varnothing\), yet \(+\infty = m(A_n) \not\to 0 = \mu (\varnothing )\).
continuous at zero if it is continuous from above at \(A = \varnothing\).
Definition 2 Let \(\mathcal{S}\) be a semiring of subsets of \(X\). A function \(m: \mathcal{S} \to [0, +\infty ]\) with the property \(m(\varnothing ) = 0\) is called
a content (content) if \(m\) is additive;
a pre-measure (pre-measure) if \(m\) is countably additive;
a measure (measure) if \(m\) is countably additive and \(\mathcal{S}\) is a sigma-algebra;
a probability measure (probability measure) if \(m\) is a measure on a sigma-algebra \(\mathcal{S}\) and \(m(X) = 1\).
The property \(m(\varnothing ) = 0\) is added so that the identically-infinite map \(m \equiv +\infty\) is not counted as a content or a measure.
The only measure we have seen so far is the counting measure. Let us give an example of a measure on \(\mathbb {R}\) that is neither the counting measure nor (looking ahead) Lebesgue measure, which we will construct next week β just to get a feel for how broad the notion of measure is.
Let \(q_1, q_2, \ldots\) be an arbitrary enumeration of \(\mathbb {Q}\) (a countable set). Define on \((\mathbb {R}, 2^{\mathbb {R}})\) the set function \[
\mu (A) := \sum _{k \; : \; q_k \in A} \frac{1}{2^k}, \qquad A \subset \mathbb {R}.
\] (i.e., \(\mu = \sum_{k=1}^\infty \frac{1}{2^k}\delta_{q_k}\), a weighted sum of Dirac measures over all rational points). Check that \(\mu\) is a probability measure on \((\mathbb {R}, 2^{\mathbb {R}})\).
Nonnegativity is obvious. Countable additivity: let \(A_1, A_2, \ldots\) be disjoint subsets of \(\mathbb {R}\), \(A = \bigsqcup_i A_i\). For each \(k\), the index \(q_k\) lies in exactly one of the \(A_i\) (or in none of them), so the term \(\frac{1}{2^k}\) is counted in the sum \(\mu (A) = \sum_{k: q_k \in A} 2^{-k}\) exactly when it is counted in one (and exactly one) of the sums \(\mu (A_i)\); hence \(\mu (A) = \sum_i \mu (A_i)\) is simply a regrouping of the absolutely convergent (all terms nonnegative) series \(\sum_k 2^{-k}\), which does not depend on the order of summation. Finally, \(\mu (\mathbb {R}) = \sum_{k=1}^\infty \frac{1}{2^k} = 1\), i.e., \(\mu\) is a probability measure. Let us note for later (the chapter on signed measures): this measure is singular with respect to Lebesgue measure β it βlivesβ entirely on the countable set \(\mathbb {Q}\), whose Lebesgue measure is zero.
Why these terms? The standard scheme for constructing a measure:
We introduce a set function \(m\), based on our needs, on some simple sets. Usually these form a semiring \(\mathcal{S}\), and it is almost always obvious that \(m\) is additive on \(\mathcal{S}\). Hence \(m\) is a content.
We prove that \(m\) is countably additive on \(\mathcal{S}\). I.e., \(m\) is a pre-measure.
Then CarathΓ©odoryβs extension theorem (see next week) extends the pre-measure \(m\) from the semiring \(\mathcal{S}\) to a measure on the \(\sigma\)-algebra \(\sigma (\mathcal{S})\).
For an application of this scheme to the example of Lebesgue measure, see below.
This is why a countably additive nonnegative function not on a sigma-algebra is called a pre-measure in the modern literature: it is needed almost always only in order to become a countably additive function on the generated sigma-algebra, i.e., to become a genuine, full-fledged measure.
Properties of a set function
Lemma 1 (Properties of a nonnegative set function on a semiring) Let \(\mathcal{S}\) be a semiring on \(X\), \(m: \mathcal{S} \to [0, +\infty ]\) (nonnegative), \(m(\varnothing ) = 0\) (nondegenerate, not identically \(+\infty\)). Then
Properties of a nonnegative set function on a semiring: implications among additivity/content, monotonicity, super-/subadditivity, and continuity from above/below/at zero.
In particular, for a nonnegative nondegenerate additive function on a ring (in particular, on a sigma-algebra), we have:
The same properties for a nonnegative nondegenerate additive function on a ring (in particular, on a sigma-algebra).
Lebesgue measure: construction plan
Goal: to obtain a nonnegative function on the Borel sigma-algebra on \(\mathbb {R}\) (more generally: on \(\mathbb {R}^{k}\)) that is a measure, i.e., is countably additive, and that agrees with the ordinary length (the difference between the endpoint and the starting point) on intervals, i.e., sets of the form \((a,b)\), \((a,b]\), \([a,b)\), \([a,b]\). For simplicity we will carry out the construction on \(\mathbb {R}\), although a measure on \(\mathbb {R}^{k}\) can be built by an analogous algorithm. Plan:
On the semiring \(\mathcal{S} = \left\{ (a,b] \; : \; -\infty < a \leq b < +\infty \right\}\) of subsets of \(\mathbb {R}\), introduce the nonnegative function \(\lambda \left((a, b]\right) := b-a\). It is clearly finitely additive, hence \(\lambda\) is a content.
Prove that \(\lambda\) on \(\mathcal{S}\) is countably subadditive. In that case, by the lemma above, we obtain that \(\lambda\) is a pre-measure on the semiring \(\mathcal{S}\).
Now the pre-measure on the semiring \(\mathcal{S}\) of half-open intervals must be transformed somehow into a measure on \(\sigma (\mathcal{S}) = \mathscr {B}\left(\mathbb {R}\right)\). This is done by means of CarathΓ©odoryβs theorem, which constructs a measure as follows: for an arbitrary subset \(A \subset \mathbb {R}\), using the pre-measure \(\lambda\), introduce the so-called outer measure by taking the infimum of the total values of \(\lambda\) over countable covers:
\[
\lambda ^*(A) := \inf \left\{ \sum _{B \in \mathcal{S}'}\lambda (B) \; : \; \mathcal{S}' \text{ is an at most countable cover of } A \text{ by elements of } \mathcal{S}\right\}
\]
Prove that for elements of the semiring \(\mathcal{S}\) itself, the values of \(\lambda\) and \(\lambda^*\) coincide.
\(\lambda^*\) is introduced on all of \(2^{\mathbb {R}}\), but it will not be a measure there (if we accept the axiom of choice). It is necessary to restrict the domain somewhat, by introducing the notion of \(\lambda^*\)-measurability. It will turn out that the \(\lambda^*\)-measurable subsets of the line, which we will denote \(\mathcal{M}(\mathcal{\lambda^*})\), form a sigma-algebra. Moreover, all sets from \(\mathcal{S}\) will be \(\mu^*\)-measurable. Thus the sigma-algebra generated by the semiring will also be measurable: \(\sigma (\mathcal{S}) \subset \mathcal{M}\).
It remains to note that for the semiring of half-open intervals, \(\sigma (\mathcal{S}) = \mathscr {B}\left(\mathbb {R}\right)\).
By means of CarathΓ©odoryβs theorem we will obtain a measure not only on Borel sets but even on some non-Borel sets. It is necessary to restrict its domain to the Borel sets, and we will obtain the measure we wanted. Looking ahead, what we will construct is called the LebesgueβBorel measure.
Let us finish step II.
Let \(\mathcal{S} = \left\{ (a, b] \; : \; -\infty < a \leq b < +\infty \right\}\) be the semiring of half-open intervals.
Let \(\lambda \left((a, b]\right) := b-a\). Prove countable additivity of \(\lambda\) on \(\mathcal{S}\).
A more general case: let \(F: \mathbb {R} \to \mathbb {R}\) be a nondecreasing, right-continuous function. Let \(\lambda_F\left((a, b]\right) := F(b) - F(a)\). Prove that \(\lambda_F\) is countably additive on \(\mathcal{S}\).
Use the topological properties of \(\mathbb {R}\). Namely, that from any cover of a closed interval by open intervals one can extract a finite subcover.
Let us prove the more general case, for \(\lambda_F\). For the case of \(\lambda\) one can take \(F(x) = x\).
It is obvious that \(\lambda_F(\varnothing ) =0\) and \(\lambda_F\) is finitely additive, hence a content, hence countably superadditive. It remains only to prove countable subadditivity: if \((a_1, b_1], (a_2, b_2], \ldots\) are such that \((a, b] \subset \cup_{n=1}^{\infty }(a_n, b_n]\), then
\[
F(b)-F(a) = \lambda _F \left((a, b]\right) \stackrel{?}{\leq } \sum _{n=1}^{\infty } \lambda _F\left((a_n, b_n]\right) = \sum _{n=1}^{\infty } (F(b_n) - F(a_n))
\]
Let \(\varepsilon > 0\) be arbitrary. Let us use some topological properties of \(\mathbb {R}\). Let \(a_\varepsilon \in (a,b)\) be a number such that \(F(a_\varepsilon ) - F(a) < \varepsilon /2\) (such an \(a_\varepsilon\) can be found since \(F\) is right-continuous). Next, for an arbitrary \(n \in \mathbb {N}\) let \(b_{n,\varepsilon } > b_n\) be such that \(F(b_{n,\varepsilon }) - F(b_n) \leq \varepsilon /2^{n}\). We have the compact set \([a_\varepsilon , b]\), which is covered by infinitely many intervals:
\[
[a_\varepsilon , b] \subset (a, b] \subset \bigcup _{n=1}^{\infty }(a_n, b_n] \subset \bigcup _{n=1}^{\infty } (a_n, b_{n, \varepsilon })
\]
Let us extract a finite subcover from these intervals:
\[
[a_\varepsilon , b] \subset \bigcup _{m=1}^{M} (a_{i_m}, b_{\varepsilon , i_m})
\]
\(\lambda_F\) is finitely additive, hence monotone and finitely subadditive. Therefore
\[
\begin{align} (F(b) - F(a)) - \frac{\varepsilon }{2} & < F(b) - F(a_{\varepsilon }) = \lambda _F\left([a_\varepsilon , b]\right) \leq \lambda _F\left(\bigcup _{m=1}^{M} (a_{i_m}, b_{\varepsilon , i_m}]\right) \leq \\ & \leq \sum _{m=1}^{M} \lambda _F\left((a_{i_m}, b_{\varepsilon , i_m}]\right) = \sum _{m=1}^{M} \left(F(b_{\varepsilon , i_m}) - F(a_{i_m})\right) \leq \sum _{n=1}^{\infty } \left(F(b_{\varepsilon , n}) - F(a_n)\right) \leq \\ & \leq \sum _{n=1}^{\infty } \left(\frac{\varepsilon }{2^{n}} + (F(b_n) - F(a_n))\right) = \frac{\varepsilon }{2} + \sum _{n=1}^{\infty }(F(b_n) - F(a_n)) \end{align}
\]
Altogether
\[
F(b) - F(a) \leq \varepsilon + \sum _{n=1}^{\infty }(F(b_n) - F(a_n))
\]
Since we took \(\varepsilon\) to be arbitrary, we obtain
\[
F(b) - F(a) \leq \sum _{n=1}^{\infty }(F(b_n) - F(a_n))
\]
QED.
We will take up step III in the next chapter.
Proofs of properties of set functions
Finite properties
Lemma 2 (Auxiliary lemma, a strengthened condition for a semiring) Let \(\mathcal{S}\) be a semiring, \(A, A_1, A_2, A_3, \ldots , A_n \in \mathcal{S}\). Then there exist \(B_{1}, \dots , B_{n'} \in \mathcal{S}\), a disjoint collection from \(\mathcal{S}\), such that: \[
\begin{align} A \setminus \bigcup _{i=1}^{n} A_i = \bigsqcup _{j=1}^{n'} B_k \end{align}
\]
Strengthened semiring condition: \(A \setminus (A_1 \cup A_2 \cup A_3)\) splits into finitely many pairwise disjoint elements \(B_1,\ldots,B_4\) of the semiring. Hover over a shaded region to see which piece it corresponds to.
Prove that additivity does indeed imply monotonicity for \(m: \mathcal{S} \to [0, +\infty ]\), \(m(\varnothing ) = 0\), where \(\mathcal{S}\) is a semiring.
Prove that the condition of additivity is indeed equivalent to subadditivity together with superadditivity for \(m: \mathcal{S} \to [0, +\infty ]\), \(m(\varnothing ) = 0\), where \(\mathcal{S}\) is a semiring.
Countable properties
Prove that in lemma Lemma 1, additivity does indeed imply \(\sigma\)-superadditivity.
Let \(A, A_1, A_2, \ldots \in \mathcal{S}\) and \(\bigsqcup_{n=1}^{\infty } A_n \subset A\). We must prove that \(m(A) \geq \sum_{n=1}^{\infty }m(A_n)\).
Let \(N \in \mathbb {N}\) be an arbitrary fixed number. Let us prove that \(m(A) \geq \sum_{n=1}^{N}m(A_n)\). Then, letting \(N \to \infty\), we obtain exactly \(m(A) \geq \sum_{n=1}^{\infty }m(A_n)\).
If \(\mathcal{S}\) were a ring, we could immediately say \(\bigsqcup_{n=1}^{N}A_n \in \mathcal{S}\), and by the properties of monotonicity and additivity, \(m(A) \geq m(\bigsqcup_{n=1}^{N}A_n) = \sum_{n=1}^N m(A_n)\).
Our situation is more difficult: \(\mathcal{S}\) is a semiring, i.e., it is not closed under unions. However, by the auxiliary lemma Lemma 2 we have
\[
A \setminus \bigsqcup _{n=1}^N A_n = \bigsqcup _{j=1}^{m}B_n, \quad B_j \in \mathcal{S}, \; \forall j
\]
Thus,
\[
A = \left(\bigsqcup _{n=1}^N A_n\right) \sqcup \left(\bigsqcup _{j=1}^{m}B_j\right)
\]
and, using finite additivity and nonnegativity of the content, we obtain
\[
m(A) = \left(\sum _{n=1}^N m(A_n)\right) + \left(\sum _{j=1}^{m}m(B_n)\right) \geq \sum _{n=1}^N m(A_n)
\]
Prove that countable additivity of \(m\) on a semiring \(\mathcal{S}\) implies countable subadditivity.
Let \(A, A_1, A_2, \ldots \in \mathcal{S}\) and \(A \subset \bigcup_{n=1}^{\infty } A_n\). We must prove that \(m(A) \leq \sum_{n=1}^{\infty }m(A_n)\).
A semiring is closed under intersections, i.e., \(A_n \cap A \in \mathcal{S}\), \(\forall n\). Hence, without loss of generality, we may assume that \(A_n \subset A\), \(\forall n\).
Let \(B_1 := A_1\), \(B_n := A_n \setminus \bigcup_{i=1}^{n-1} A_i\). We have \(A = \bigsqcup_{n=1}^{\infty } B_n\). The \(B_n\) themselves need not belong to the semiring \(\mathcal{S}\), since a semiring is not closed under taking differences. However, by the auxiliary lemma Lemma 2 \(B_n\) can be decomposed into a finite disjoint union of subsets from the semiring: \(\forall n\) we have
\[
B_n = C_{n,1} \sqcup C_{n,2} \sqcup \ldots \sqcup C_{n,M_n}, \quad C_{n, i} \in \mathcal{S}, \; \forall i
\]
Thus, we have \(A = \bigsqcup_{n=1}^{\infty }\bigsqcup_{i=1}^{M_n} C_{n,i}\), with \(C_{n,i} \in \mathcal{S}\), so we may use countable additivity:
\[
m(A) = \sum _{n=1}^{\infty }\sum _{i=1}^{M_n}m(C_{n,i})
\]
It remains to note that for every \(n\) we have \(\bigsqcup_{i=1}^{M_n}C_{n,i} \subset A_n\), and by the property of finite superadditivity we get \(\sum_{i=1}^{M_n}m(C_{n,i}) \leq m(A_n)\). QED.
Let \(X = (0,1]\), \(\mathcal{S} = \left\{ (a,b] \cap \mathbb {Q} \; : \; 0 \leq a \leq b \leq 1\right\}\), \(m\left((a,b] \cap \mathbb {Q}\right) := b-a\). Prove that
\(m\) is a finitely additive function on the semiring \(\mathcal{S}\);
\(m\) is continuous from above and from below;
\(m\) is not countably additive.