\(\newcommand{\R}{\mathbb{R}}\) \(\newcommand{\N}{\mathbb{N}}\) \(\newcommand{\ms}{\mathscr}\)
  1. Random
  2. 0. Foundations
  3. 1
  4. 2
  5. 3
  6. 4
  7. 5
  8. 6
  9. 7
  10. 8
  11. 9
  12. 10
  13. 11
  14. 12
  15. 13
  16. 14
  17. 15
  18. 16
  19. 17
  20. 18
  21. 19

13. Special Set Structures

There are several other types of algebraic set structures that are weaker than \( \sigma \)-algebras. These are not particularly important in themselves, but are important for constructing \( \sigma \)-algebras and the measures on these \( \sigma \)-algebras. You may want to skip this section if you are not intersted in questions of existence and uniqueness of positive measures.

Basic Theory

Definitions

Throughout this section, we assume that \( S \) is a set and \( \ms S \) is a nonempty collection of subsets of \( S \). Here are the main definitions we will need.

\( \ms S \) is a \( \pi \)-system if \( \ms S \) is closed under finite intersections: if \( A, \, B \in \ms S \) then \( A \cap B \in \ms S \).

Closure under intersection is clearly a very simple property, but \( \pi \) systems turn out to be useful enough to deserve a name.

\( \ms S \) is a \( \lambda \)-system if it is closed under complements and countable disjoint unions.

  1. If \( A \in \ms S \) then \( A^c \in \ms S \).
  2. If \( A_i \in \ms S\) for \( i \) in a countable index set \( I \) and \( A_i \cap A_j = \emptyset \) for \( i \ne j \) then \( \bigcup_{i \in I} A_i \in \ms S \).

\( \ms S \) is a semi-algebra if it is closed under intersection and if complements can be written as finite, disjoint unions:

  1. If \( A, \, B \in \ms S \) then \( A \cap B \in \ms S \).
  2. If \( A \in \ms S \) then there exists a finite, disjoint collection \( \{B_i: i \in I\} \subseteq \ms S \) such that \( A^c = \bigcup_{i \in I} B_i \).

For our final structure, recall that a sequence \( (A_1, A_2, \ldots) \) of subsets of \( S \) is increasing if \( A_n \subseteq A_{n+1} \) for all \( n \in \N_+ \). The sequence is decreasing if \( A_{n+1} \subseteq A_n \) for all \( n \in \N_+ \). Of course, these are the standard meanings of increasing and decreasing relative to the ordinary order \( \le \) on \( \N_+ \) and the subset partial order \( \subseteq \) on \( \ms{P}(S) \).

\( \ms S \) is a monotone class if it is closed under increasing unions and decreasing intersections:

  1. If \( (A_1, A_2, \ldots) \) is an increasing sequence of sets in \( \ms S \) then \( \bigcup_{n=1}^\infty A_n \in \ms S \).
  2. If \( (A_1, A_2, \ldots) \) is a decreasing sequence of sets in \( \ms S \) then \( \bigcap_{n=1}^\infty A_n \in \ms S \).

If \( (A_1, A_2, \ldots) \) is an increasing sequence of sets then we sometimes write \( \bigcup_{n=1}^\infty A_n = \lim_{n \to \infty} A_n \). Similarly, if \( (A_1, A_2 \ldots) \) is a decreasing sequence of sets we sometimes write \( \bigcap_{n=1}^\infty A_n = \lim_{n \to \infty} A_n \). The reason for this notation is because of the continuity theorems for positive measures. With this notation, a monotone class \( \ms S \) is defined by the condition that if \( (A_1, A_2, \ldots) \) is an increasing or decreasing sequence of sets in \( \ms S \) then \( \lim_{n \to \infty} A_n \in \ms S \).

Basic Theorems

Our most important set structure, the \( \sigma \)-algebra, has all of the properties in the definitions above.

If \( \ms S \) is a \( \sigma \)-algebra then \( \ms S \) is a \( \pi \)-system, a \( \lambda \)-system, a semi-algebra, and a monotone class.

If \( \ms S \) is a \( \lambda \)-system then \( S \in \ms S \) and \( \emptyset \in \ms S \).

Details:

The proof is just like the one for an algebra. There exists \( A \in \ms S \) since \( \ms S \) is non-empty. Hence \( A^c \in \ms S \) and so \( S = A \cup A^c \in \ms S \). Finally \( \emptyset = S^c \in \ms S \).

Any type of algebraic structure on subsets of \( S \) that is defined purely in terms of closure properties will be preserved under intersection. That is, we will have results that are analogous to how \( \sigma \)-algebras are generated from more basic sets, with completely straightforward and analgous proofs. In the following two theorems, the term system could mean \( \pi \)-system, \( \lambda \)-system, or monotone class of subsets of \( S \).

If \( \ms S_i \) is a system for each \( i \) in an index set \( I \) and \( \bigcap_{i \in I} \ms S_i \) is nonempty, then \( \bigcap_{i \in I} \ms S_i \) is a system of the same type.

The condition that \( \bigcap_{i \in I} \ms S_i \) be nonempty is unnecessary for a \( \lambda \)-system, by . We can now construct the system generated by a collection of basic sets of some sort.

Suppose that \( \ms B \) is a nonempty collection of subsets of \( S \). Then the system \(\ms S\) generated by \( \ms B \) is the intersection of all systems that contain \( \ms B \): \[ \ms S = \bigcap\{\ms T: \ms T \text{ is a system and } \ms B \subseteq \ms T\}\] The system \( \ms S \) is characterized by the following properties:

  1. \( \ms B \subseteq \ms S \).
  2. If \( \ms T \) is a system and \( \ms B \subseteq \ms T \) then \( \ms S \subseteq \ms T \).

Note however, that and do not apply to semi-algebras, because the semi-algebra is not defined purely in terms of closure properties (the condition on \( A^c \) is not a closure property).

If \( \ms S \) is a monotone class and an algebra, then \( \ms S \) is a \( \sigma \)-algebra.

Details:

All that is needed is to prove closure under countable unions. Thus, suppose that \( A_i \in \ms S \) for \( i \in \N_+ \). Then \( B_n = \bigcup_{i=1}^n A_i \in \ms S \) since \( \ms S \) is an algebra. The sequence \( (B_1, B_2, \ldots) \) is increasing, so \( \bigcup_{n=1}^\infty B_n \in \ms S \), since \( \ms S \) is a monotone class. But \( \bigcup_{n=1}^\infty B_n = \bigcup_{i=1}^\infty A_i \).

By definition, a semi-algebra is a \( \pi \)-system. More importantly, a semi-algebra can be used to construct an algebra.

Suppose that \( \ms S \) is a semi-algebra of subsets of \( S \). Then the collection \( \ms S^* \) of finite, disjoint unions of sets in \( \ms S \) is an algebra.

Details:

Suppose that \( A, \, B \in \ms S^* \). Then there exist finite, disjoint collections \( \{A_i: i \in I\} \subseteq \ms S \) and \( \{B_j: j \in J\} \subseteq \ms S \) such that \( A = \bigcup_{i \in I} A_i \) and \( B = \bigcup_{j \in J} B_j \). Hence \[ A \cap B = \bigcup_{(i, j) \in I \times J} (A_i \cap B_j) \] But \( \{A_i \cap B_j: (i, j) \in I \times J\} \) is a finite, disjoint collection of sets in \( \ms S \), so \( A \cap B \in \ms S^* \). Suppose \( A \in \ms S^* \), so that there exists a finite, disjoint collection \( \{A_i: i \in I\} \) such that \( A = \bigcup_{i \in I} A_i \). Then \( A^c = \bigcap_{i \in I} A_i^c \). But \( A_i^c \in \ms S^* \) by definition of semi-algebra, and we just showed that \( \ms S^* \) is closed under finite intersections, so \( A^c \in \ms S^* \).

We need yet one more definition

A nonempty collection \( \ms S \) of subsets of \(S\) is closed under proper set difference if \( A, \, B \in \ms S \) and \( A \subseteq B \) implies \( B \setminus A \in \ms S \)

The following theorem gives the basic relationship between \( \lambda \)-systems and monotone classes.

Suppose that \( \ms S \) is a nonempty collection of subsets of \( S \).

  1. If \( \ms S \) is a \( \lambda \)-system then \( \ms S \) is a monotone class and is closed under proper set difference.
  2. If \( \ms S \) is a monotone class, is closed under proper set difference, and contains \( S \), then \( \ms S \) is a \( \lambda \)-system.
Details:
  1. Suppose that \( \ms S \) is a \( \lambda \)-system. Suppose that \( A, \, B \in \ms S \) and \( A \subseteq B \). Then \( B^c \in \ms S \), and \( A \) and \( B^c \) are disjoint, so \( A \cup B^c \in \ms S \). But then \( (A \cup B^c)^c = B \cap A^c = B \setminus A \in \ms S \). Hence \( \ms S \) is closed under proper set difference. Next suppose that \( (A_1, A_2, \ldots) \) is an increasing sequence of sets in \( \ms S \). Let \( B_1 = A_1 \) and \( B_n = A_n \setminus A_{n-1} \) for \( n \in \{2, 3, \ldots\} \). Then \( B_i \in \ms S \) for each \( i \in \N_+ \). But the sequence \( (B_1, B_2, \ldots) \) is disjoint and has the same union as \( (A_1, A_2, \ldots) \). Hence \( \bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty B_i \in \ms S \). Finally, suppose that \( (A_1, A_2, \ldots) \) is a decreasing sequence of sets in \( \ms S \). Then \( A_i^c \in \ms S \) for each \( i \in \N_+ \) and \( (A_1^c, A_2^c, \ldots) \) is increasing. Hence \( \bigcup_{i=1}^\infty A_i^c \in \ms S \) and therefore \( \left(\bigcup_{i=1}^\infty A_i^c\right)^c = \bigcap_{i=1}^\infty A_i \in \ms S \).
  2. Suppose that \( \ms S \) is a monotone class, is closed under proper set difference, and \( S \in \ms S \). If \( A \in \ms S \) then trivially \( A \subseteq S \) so \( A^c = S \setminus A \in \ms S \). Next, suppose that \( A, \; B \in \ms S \) are disjoint. Then \( A^c \in \ms S \) and \( B \subseteq A^c \), so \( A^c \setminus B = A^c \cap B^c \in \ms S \). Hence \( A \cup B = (A^c \cap B^c)^c \in \ms S \). Finally, suppose that \( (A_1, A_2, \ldots) \) is a disjoint sequence of sets in \( \ms S \). We just showed that \( \ms S \) is closed under finite, disjoint unions, so \( B_n = \bigcup_{i=1}^n A_i \in \ms S \). But the sequence \( (B_1, B_2, \ldots) \) is increasing, and hence \( \bigcup_{n=1}^\infty B_n = \bigcup_{i=1}^\infty A_i \in \ms S \).

The following theorem is known as the monotone class theorem, and is due to the mathematician Paul Halmos.

Suppose that \( \ms A \) is an algebra, \( \ms{M} \) is a monotone class, and \( \ms A \subseteq \ms{M} \). Then \( \sigma(\ms A) \subseteq \ms{M} \).

Details:

First let \( m(\ms A) \) denote the monotone class generated by \( \ms A \), as defined in . The outline of the proof is to show that \( m(\ms A) \) is an algebra, so that by , \( m(\ms A) \) is a \( \sigma \)-algebra. It then follows that \( \sigma(\ms A) \subseteq m(\ms A) \subseteq \ms{M} \). To show that \( m(\ms A) \) is an algebra, we first show that it is closed under complements and then under simple union.

Since \( m(\ms A) \) is a monotone class, the collection \( m^*(\ms A) = \{A \subseteq S: A^c \in m(\ms A)\} \) is also a monotone class. Moreover, \( \ms A \subseteq m^*(\ms A) \) so it follows that \( m(\ms A) \subseteq m^*(\ms A) \). Hence if \( A \in m(\ms A) \) then \( A \in m^*(\ms A) \) so \( A^c \in m(\ms A) \). Thus \( m(\ms A) \) is closed under complements.

Let \( \ms{M}_1 = \{A \subseteq S: A \cup B \in m(\ms A) \text{ for all } B \in \ms A\} \). Then \( \ms{M}_1 \) is a monotone class and \( \ms A \subseteq \ms{M}_1 \) so \( m(\ms A) \subseteq \ms{M}_1 \). Next let \( \ms{M}_2 = \{A \subseteq S: A \cup B \in m(\ms A) \text{ for all } B \in m(\ms A)\} \). Then \( \ms{M}_2 \) is also a monotone class. Let \( A \in \ms A \). If \( B \in m(\ms A)\) then \( B \in \ms{M}_1 \) and hence \( A \cup B \in m(\ms A) \). Hence \( A \in \ms{M}_2 \). Thus we have \( \ms A \subseteq \ms{M}_2 \), so \( m(\ms A) \subseteq \ms{M}_2 \). Finally, let \( A, \, B \in m(\ms A) \). Then \( A \in \ms{M}_2 \) so \( A \cup B \in m(\ms A) \) and therefore \( m(\ms A) \) is closed under simple union.

As noted in , a \( \sigma \)-algebra is both a \( \pi \)-system and a \( \lambda \)-system. The converse is also true, and is one of the main reasons for studying these structures.

If \( \ms S \) is a \( \pi \)-system and a \( \lambda \)-system then \( \ms S \) is a \( \sigma \)-algebra.

Details:

\( S \in \ms S \), and if \( A \in \ms S \) then \( A^c \in \ms S \) by definition of a \( \lambda \)-system. Thus, all that is left is to show closure under countable unions. Thus, suppose that \( (A_1, A_2, \ldots) \) is a sequence of sets in \( \ms S \). Then \( A_i^c \in \ms S \) for each \( i \in \N_+ \). Since \( \ms S \) is also a \( \pi \)-system, it follows that for each \( n \in \N_+ \), \( B_n = A_n \cap A_1^c \cap \cdots \cap A_{n-1}^c \in \ms S \) (by convention \( B_1 = A_1 \)). But the sequence \( (B_1, B_2, \ldots) \) is disjoint and has the same union as \( (A_1, A_2, \ldots) \). Hence \( \bigcup_{i=1}^\infty A_i = \bigcup_{i=1}^\infty B_i \in \ms S \).

The importance of \( \pi \)-systems and \( \lambda \)-systems stems in part from Dynkin's \( \pi \)-\( \lambda \) theorem given next. It's named for the mathematician Eugene Dynkin.

Suppose that \( \ms A \) is a \( \pi \)-system of subsets of \( S \), \( \ms B \) is a \( \lambda \)-system of subsets of \( S \), and \( \ms A \subseteq \ms B \). Then \( \sigma(\ms A) \subseteq \ms B \).

Details:

Let \( \ms L \) denote the \( \lambda \)-system generated by \( \ms A \). Then of course \( \ms A \subseteq \ms L \subseteq \ms B \). For \( A \in \ms L \), let \[ \ms L_A = \{B \subseteq S: B \cap A \in \ms L\}\] We will show that \( \ms L_A \) is a \( \lambda \)-system. Note that \( S \cap A = A \in \ms L\) and therefore \( S \in \ms L_A \). Next, suppose that \( B_1, \, B_2 \in \ms L_A \) and that \( B_1 \subseteq B_2 \). Then \( B_1 \cap A \in \ms L \) and \( B_2 \cap A \in \ms L \) and \( B_1 \cap A \subseteq B_2 \cap A \). Hence \( (B_2 \setminus B_1) \cap A = (B_2 \cap A) \setminus (B_1 \cap A) \in \ms L \). Hence \( B_2 \setminus B_1 \in \ms L_A \). Finally, suppose that \( \{B_i: i \in I\} \) is a countable, disjoint collection of sets in \( \ms L_A \). Then \( B_i \cap A \in \ms L \) for each \( i \in I \), and \( \{B_i \cap A: i \in I\} \) is also a disjoint collection. Therefore, \( \bigcup_{i \in I} (B_i \cap A) = \left(\bigcup_{i \in I} B_i \right) \cap A \in \ms L \). Hence \( \bigcup_{i \in I} B_i \in \ms L_A \).

Next fix \( A \in \ms A \). If \( B \in \ms A \) then \( A \cap B \in \ms A \), so \( A \cap B \in \ms L \) and hence \( B \in \ms L_A \). But \( \ms L \) is the smallest \( \lambda \)-system containing \( \ms A \) so we have shown that \( \ms L \subseteq \ms L_A \) for every \( A \in \ms A \). Now fix \( B \in \ms L\). If \( A \in \ms A \) then \( B \in \ms L_A \) so \( A \cap B \in \ms L \) and therefore \( A \in \ms L_B \). Again, \( \ms L \) is the smallest \( \lambda \)-system containing \( \ms A \) so we have now shown that \( \ms L \subseteq \ms L_B \) for every \( B \in \ms L \). Finally, let \( B, \, C \in \ms L \). Then \( C \in \ms L_B \) and hence \( B \cap C \in \ms L \). It now follows that \( \ms L \) is a \( \pi \)-system, as well as a \( \lambda \)-system, and therefore by , \( \ms L \) is a sigma-algebra. But \( \ms A \subseteq \ms L \) and hence \( \sigma(\ms A) \subseteq \ms L \).

Examples and Special Cases

Suppose that \( S \) is a set and \( \ms A \) is a finite partition of \( S \). Then \( \ms S = \{\emptyset\} \cup \ms A \) is a semi-algebra of subsets of \( S \).

Details:

If \( A, \, B \in \ms A \) then \( A \cap B = \emptyset \in \ms S \). If \( A \in \ms S \) then \( A^c = \bigcup\{B \in \ms A: B \neq A \}\)

Euclidean Spaces

The following example is particulalry important because it will be used to construct positive measures on \( \R \). Let \[ \ms B = \{(a, b]: a, \, b \in \R, \; a \lt b\} \cup \{(-\infty, b]: b \in \R\} \cup \{(a, \infty): a \in \R \} \]

\( \ms B \) is a semi-algebra of subsets of \( \R \).

Details:

Note that the intersection of two intervals of the type in \( \ms B \) is another interval of this type. The complement of an interval of this type is either another interval of this type or the union of two disjoint intervals of this type.

It follows from that the collection \( \ms A \) of finite disjoint unions of intervals in \( \ms B \) is an algebra. Recall also that \( \sigma(\ms B) = \sigma(\ms A) \) is the Borel \( \sigma \)-algebra of \( \R \), named for Émile Borel. We can generalize all of this to \( \R^n \) for \( n \in \N_+ \)

The collection \( \ms B_n = \left\{\prod_{i = 1}^n A_i: A_i \in \ms B \text{ for each } i \in \{1, 2, \ldots, n\} \right\} \) is a semi-algebra of subsets of \( \R^n \).

Recall also that \( \sigma(\ms B_n) \) is the \( \sigma \)-algebra of Borel sets of \( \R^n \).

Product Spaces

The examples in this discussion are important for constructing positive measures on product spaces.

Suppose that \(\ms S\) is a semi-algebra of subsets of a set \( S \) and that \(\ms T\) is a semi-algebra of subsets of a set \( T \). Then \[ \ms U = \{A \times B: A \in \ms S, B \in \ms T\} \] is a semi-algebra of subsets of \( S \times T \).

Details:
  1. Suppose that \( A \times B, \, C \times D \in \ms U \), so that \( A, \, C \in \ms S \) and \( B, \, D \in \ms T \). Recall that \( (A \times B) \cap (C \times D) = (A \cap C) \times (B \cap D) \). But \( A \cap C \in \ms S \) and \( B \cap D \in \ms T \) so \( (A \times B) \cap (C \times D) \in \ms U \).
  2. Suppose that \( A \times B \in \ms B \) so that \( A \in \ms S \) and \( B \in \ms T \). Then \[ (A \times B)^c = (A^c \times B) \cup (A \times B^c) \cup (A^c \times B^c) \] There exists a finite, disjoint collection \( \{A_i: i \in I\} \) of sets in \( \ms S \) and a finite, disjoint collection \( \{B_j: j \in J\} \) of sets in \( \ms T \) such that \( A^c = \bigcup_{i \in I} A_i\) and \( B^c = \bigcup_{j \in J} B_j \). Hence \[ (A \times B)^c = \left[\bigcup_{i \in I} (A_i \times B)\right] \cup \left[\bigcup_{j \in J} (A \times B_j)\right] \cup \left[\bigcup_{i \in I} \bigcup_{j \in J} (A_i \times B_j)\right] \] All of the product sets in this union are in \( \ms U \) and the product sets are disjoint.

This result extends in a completely straightforward way to a product of a finite number of sets.

Suppose that \( n \in \N_+ \) and that \( \ms S_i \) is a semi-algebra of subsets of a set \( S_i \) for \( i \in \{1, 2, \ldots, n\} \). Then \[ \ms U = \left\{\prod_{i=1}^n A_i: A_i \in \ms S_i \text{ for all } i \in \{1, 2, \ldots, n\}\right\} \] is a semi-algebra of subsets of \( \prod_{i=1}^n S_i \).

Note that the semi-algebra of products of intervals in \( \R^n \) described in is a special case of this result. For the product of an infinite sequence of sets, the result is bit more tricky.

Suppose that \( \ms S_i \) is a semi-algebra of subsets of a set \( S_i \) for \( i \in \N_+ \). Then \[ \ms U = \left\{\prod_{i=1}^\infty A_i: A_i \in \ms S_i \text{ for all } i \in \N_+ \text{ and } A_i = S_i \text{ for all but finitely many } i \in \N_+\right\} \] is a semi-algebra of subsets of \( \prod_{i=1}^n S_i \).

Details:

The proof is very much like the previous ones.

  1. Suppose that \( A = \prod_{i=1}^\infty A_i \in \ms U \) and \( B = \prod_{i=1}^\infty B_i \in \ms U \), so that \( A_i, \, B_i \in \ms S_i \) for \( i \in \N_+ \) and \( A_i = S_i \) for all but finitely many \( i \in \N_+ \) and \( B_i = S_i \) for all but finitely many \( i \in \N_+ \). Then \( A \cap B = \prod_{i=1}^\infty (A_i \cap B_i) \). Also, \( A_i \cap B_i \in \ms S_i \) for \( i \in \N_+ \) and \( A_i \cap B_i = S_i \) for all but finitely many \( in \in \N_+ \). So \( A \cap B \in \ms U \).
  2. Suppose that \( A = \prod_{i=1}^\infty A_i \in \ms U \), where \( A_i \in \ms S_i \) for \( i \in \N_+ \) and \( A_i = S_i \) for \( i \gt n \), for some \( n \in \N_+ \). Then \( A^c = \bigcup_{j=1}^n B_j \) where \[ B_j = A_1 \times \cdots \times A_{j-1} \times A_j^c \times S_{j+1} \times S_{j+2} \times \cdots, \quad j \in \{1, 2, \ldots, n\}\] Note that the product sets in this union are disjoint. But for each \( j \in \{1, 2, \ldots, n\} \) there exists a finite disjoint collection \( \{C_{j,k}: k \in K_j\} \) such that \( A_j^c = \bigcup_{k \in K_j} C_{j,k} \). Substituting and distributing then gives \( A^c \) as a finite, disjoint union of sets in \( \ms U \).

Note that this result would not be true with \( \ms U = \left\{\prod_{i=1}^\infty A_i: A_i \in \ms S_i \text{ for all } i \in \N_+\right\}\). In general, the complement of a set in \( \ms U \) cannot be written as a finite disjoint union of sets in \( \ms U \).