Skip to main content
Mathematics LibreTexts

7.3: More on Set Families

  • Page ID
    32344
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

    ( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\id}{\mathrm{id}}\)

    \( \newcommand{\Span}{\mathrm{span}}\)

    \( \newcommand{\kernel}{\mathrm{null}\,}\)

    \( \newcommand{\range}{\mathrm{range}\,}\)

    \( \newcommand{\RealPart}{\mathrm{Re}}\)

    \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

    \( \newcommand{\Argument}{\mathrm{Arg}}\)

    \( \newcommand{\norm}[1]{\| #1 \|}\)

    \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

    \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    \( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

    \( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

    \( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vectorC}[1]{\textbf{#1}} \)

    \( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

    \( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

    \( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

    \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

    \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

    \(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)

    Lebesgue extended his theory far beyond \(\mathcal{C}_{\sigma}\)-sets. For a deeper insight, we shall consider set families in more detail, starting with set rings. First, we rephrase and supplement our former definition of that notion, given in §1.

    Definition 1

    A family \(\mathcal{M}\) of subsets of a set \(S\) is a ring or set ring (in \(S)\) iff

    (i) \(\emptyset \in \mathcal{M},\) i.e., the empty set is a member; and

    (ii) \(\mathcal{M}\) is closed under finite unions and differences:

    \[(\forall X, Y \in \mathcal{M}) \quad X \cup Y \in \mathcal{M} \text { and } X-Y \in \mathcal{M}.\]

    (For intersections, see Theorem 1 below.)

    If \(\mathcal{M}\) is also closed under countable unions, we call it a \(\sigma\)-ring (in \(S).\) Then

    \[\bigcup_{i=1}^{\infty} X_{i} \in \mathcal{M}\]

    whenever

    \[X_{i} \in \mathcal{M} \text { for } i=1,2, \ldots.\]

    If \(S\) itself is a member of a ring (\(\sigma\)-ring) \(\mathcal{M},\) we call \(\mathcal{M}\) a set field (\(\sigma\)-field), or a set algebra (\(\sigma\)-algebra), in \(S\).

    Note that \(S\) is only a member of \(\mathcal{M}, S \in \mathcal{M},\) not to be confused with \(\mathcal{M}\) itself.

    The family of all subsets of \(S\) (the so-called power set of \(S\)) is denoted by \(2^{S}\) or \(\mathcal{P}(S).\)

    Examples

    (a) In any set \(S, 2^{S}\) is a \(\sigma\)-field. (Why?)

    (b) The family \(\{\emptyset\},\) consisting of \(\emptyset\) alone, is a \(\sigma\)-ring; \(\{\emptyset, S\}\) is a \(\sigma\)-field in \(S.\) (Why?)

    (c) The family of all finite (countable) subsets of \(S\) is a ring (\(\sigma\)-ring) in \(S\).

    (d) For any semiring \(\mathcal{C}, \mathcal{C}_{s}^{\prime}\) is a ring (Theorem 2 in §1). Not so for \(\mathcal{C}_{\sigma}\) (Problem 5 in §2).

    Theorem \(\PageIndex{1}\)

    Any set ring is closed under finite intersections.

    A \(\sigma\)-ring is closed under countable intersections.

    Proof

    Let \(\mathcal{M}\) be a \(\sigma\)-ring (the proof for rings is similar).

    Given a sequence \(\left\{A_{n}\right\} \subseteq \mathcal{M},\) we must show that \(\bigcap_{n} A_{n} \in \mathcal{M}\).

    Let

    \[U=\bigcup_{n} A_{n}.\]

    By Definition 1,

    \[U \in \mathcal{M} \text { and } U-A_{n} \in \mathcal{M},\]

    as \(\mathcal{M}\) is closed under these operations. Hence

    \[\bigcup_{n}\left(U-A_{n}\right) \in \mathcal{M}\]

    and

    \[U-\bigcup_{n}\left(U-A_{n}\right) \in \mathcal{M},\]

    or, by duality,

    \[\bigcap_{n}\left[U-\left(U-A_{n}\right)\right] \in \mathcal{M},\]

    i.e.,

    \[\bigcap_{n} A_{n} \in \mathcal{M}. \quad \square\]

    Corollary \(\PageIndex{1}\)

    Any set ring (field, \(\sigma\)-ring, \(\sigma\)-field) is also a semiring.

    Indeed, by Theorem 1 and Definition 1, if \(\mathcal{M}\) is a ring, then \(\emptyset \in \mathcal{M}\) and

    \[(\forall A, B \in \mathcal{M}) \quad A \cap B \in \mathcal{M} \text { and } A-B \in \mathcal{M}.\]

    Here we may treat \(A-B\) as \((A-B) \cup \emptyset,\) a union of two disjoint \(\mathcal{M}\)-sets. Thus \(\mathcal{M}\) has all properties of a semiring.

    Similarly for \(\sigma\)-rings, fields, etc.

    In §1 we saw that any semiring \(\mathcal{C}\) can be enlarged to become a ring, \(\mathcal{C}_{s}^{\prime}.\) More generally, we obtain the following result.

    Theorem \(\PageIndex{2}\)

    For any set family \(\mathcal{M}\) in a space \(S\left(\mathcal{M} \subseteq 2^{S}\right),\) there is a unique "smallest" set ring \(\mathcal{R}\) such that

    \[\mathcal{R} \supseteq \mathcal{M}\]

    ("smallest" in the sense that

    \[\mathcal{R} \subseteq \mathcal{R}^{\prime}\]

    for any other ring \(\mathcal{R}^{\prime}\) with \(\mathcal{R}^{\prime} \supseteq \mathcal{M}\)).

    The \(\mathcal{R}\) of Theorem 2 is called the ring generated by \(\mathcal{M}.\) Similarly for \(\sigma\)-rings, fields, and \(\sigma\)-fields in \(S\).

    Proof

    We give the proof for \(\sigma\)-fields; it is similar in the other cases.

    There surely are \(\sigma\)-fields in \(S\) that contain \(\mathcal{M};\) e.g., take \(2^{S}.\) Let \(\left\{\mathcal{R}_{i}\right\}\) be the family of all possible \(\sigma\)-fields in \(S\) such that \(\mathcal{R}_{i} \supseteq \mathcal{M}.\) Let

    \[\mathcal{R}=\bigcap_{i} \mathcal{R}_{i}.\]

    We shall show that this \(\mathcal{R}\) is the required "smallest" \(\sigma\)-field containing \(\mathcal{M}\).

    Indeed, by assumption,

    \[\mathcal{M} \subseteq \bigcap_{i} \mathcal{R}_{i}=\mathcal{R}.\]

    We now verify the \(\sigma\)-field properties for \(\mathcal{R}\).

    (1) We have that

    \[(\forall i) \quad \emptyset \in \mathcal{R}_{i} \text { and } S \in \mathcal{R}_{i}\]

    (for \(\mathcal{R}_{i}\) is a \(\sigma\)-field, by assumption). Hence

    \[\emptyset \in \bigcap_{i} \mathcal{R}_{i}=\mathcal{R}.\]

    Similarly, \(S \in \mathcal{R}.\) Thus

    \[\emptyset, S \in \mathcal{R}.\]

    (2) Suppose

    \[X, Y \in \mathcal{R}=\bigcap_{i} \mathcal{R}_{i}.\]

    Then \(X, Y\) are in every \(\mathcal{R}_{i},\) and so is \(X-Y.\) Hence \(X-Y\) is in

    \[\bigcap_{i} \mathcal{R}_{i}=\mathcal{R}.\]

    Thus \(\mathcal{R}\) is closed under differences.

    (3) Take any sequence

    \[\left\{A_{n}\right\} \subseteq \mathcal{R}=\bigcap_{i} \mathcal{R}_{i}.\]

    Then all \(A_{n}\) are in each \(\mathcal{R}_{i}. \bigcup_{n} A_{n}\) is in each \(\mathcal{R}_{i};\) so

    \[\bigcup_{n} A_{n} \in \mathcal{R}.\]

    Thus \(\mathcal{R}\) is closed under countable unions.

    We see that \(\mathcal{R}\) is indeed a \(\sigma\)-field in \(S,\) with \(\mathcal{M} \subseteq \mathcal{R}.\) As \(\mathcal{R}\) is the intersection of all \(\mathcal{R}_{i}\)(i.e., all \(\sigma\)-fields \(\supseteq \mathcal{M}\)), we have

    \[(\forall i) \quad \mathcal{R} \subseteq \mathcal{R}_{i};\]

    so \(\mathcal{R}\) is the smallest of such \(\sigma\)-fields.

    It is unique; for if \(\mathcal{R}^{\prime}\) is another such \(\sigma\)-field, then

    \[\mathcal{R} \subseteq \mathcal{R}^{\prime} \subseteq \mathcal{R}\]

    (as both \(\mathcal{R}\) and \(\mathcal{R}^{\prime}\) are "smallest"); so

    \[\mathcal{R}=\mathcal{R}^{\prime}. \quad \square\]

    Note 1. This proof also shows that the intersection of any family \(\left\{\mathcal{R}_{i}\right\}\) of \(\sigma\)-fields is a \(\sigma\)-field. Similarly for \(\sigma\)-rings, fields, and rings.

    Corollary \(\PageIndex{2}\)

    The ring \(\mathcal{R}\) generated by a semiring \(\mathcal{C}\) coincides with

    \[\mathcal{C}_{s}=\{\text {all finite unions of } \mathcal{C}-\text {sets}\}\]

    and with

    \[\mathcal{C}_{s}^{\prime}=\{\text {disjoint finite unions of } \mathcal{C}-\text {sets}\}.\]

    Proof

    By Theorem 2 in §1, \(\mathcal{C}_{s}^{\prime}\) is a ring \(\supseteq \mathcal{C}\); and

    \[\mathcal{C}_{s}^{\prime} \subseteq \mathcal{C}_{s} \subseteq \mathcal{R}\]

    (for \(\mathcal{R}\) is closed under finite unions, being a ring \(\supseteq \mathcal{C}\)).

    Moreover, as \(\mathcal{R}\) is the smallest ring \(\supseteq \mathcal{C},\) we have

    \[\mathcal{R} \subseteq \mathcal{C}_{s}^{\prime} \subseteq \mathcal{C}_{s} \subseteq \mathcal{R}.\]

    Hence

    \[\mathcal{R}=\mathcal{C}_{s}^{\prime}=\mathcal{C}_{s},\]

    as claimed.\(\quad \square\)

    It is much harder to characterize the \(\sigma\)-ring generated by a semiring. The following characterization proves useful in theory and as an exercise.

    Theorem \(\PageIndex{3}\)

    The \(\sigma\)-ring \(\mathcal{R}\) generated by a semiring \(\mathcal{C}\) coincides with the smallest set family \(\mathcal{D}\) such that

    (i) \(\mathcal{D} \supseteq \mathcal{C}\);

    (ii) \(\mathcal{D}\) is closed under countable disjoint unions;

    (iii) \(J-X \in \mathcal{D}\) whenever \(X \in \mathcal{D}, J \in \mathcal{C},\) and \(X \subseteq J\).

    Proof

    We give a proof outline, leaving the details to the reader.

    (1) The existence of a smallest such \(\mathcal{D}\) follows as in Theorem 2. Verify!

    (2) Writing briefly \(A B\) for \(A \cap B\) and \(A^{\prime}\) for \(-A,\) prove that

    \[(A-B) C=A-\left(A C^{\prime} \cup B C\right).\]

    (3) For each \(I \in \mathcal{D},\) set

    \[\mathcal{D}_{I}=\{A \in \mathcal{D} | A I \in \mathcal{D}, A-I \in \mathcal{D}\}.\]

    Then prove that if \(I \in \mathcal{C},\) the set family \(\mathcal{D}_{I}\) has the properties (i)-(iii) specified in the theorem. (Use the set identity (2) for property (iii).)

    Hence by the minimality of \(\mathcal{D}, \mathcal{D} \subseteq \mathcal{D}_{I}.\) Therefore,

    \[(\forall A \in \mathcal{D})(\forall I \in \mathcal{C}) \quad A I \in \mathcal{D} \text { and } A-I \in \mathcal{D}.\]

    (4) Using this, show that \(\mathcal{D}_{I}\) satisfies (i)-(iii) for any\(I \in \mathcal{D}\).

    Deduce

    \[\mathcal{D} \subseteq \mathcal{D}_{I};\]

    so \(\mathcal{D}\) is closed under finite intersections and differences.

    Combining with property (ii), show that \(\mathcal{D}\) is a \(\sigma\)-ring (see Problem 12 below).

    By its minimality, \(\mathcal{D}\) is the smallest \(\sigma\)-ring \(\supseteq \mathcal{C}\) (for any other such \(\sigma\)-ring clearly satisfies (i)-(iii)).

    Thus \(\mathcal{D}=\mathcal{R},\) as claimed.\(\quad \square\)

    Definition 2

    Given a set family \(\mathcal{M},\) we define (following Hausdorff)

    (a) \(\mathcal{M}_{\sigma}=\{\)all countable unions of \(\mathcal{M}\)-sets\(\}\) (cf. \(\mathcal{C}_{\sigma}\) in §2);

    (b) \(\mathcal{M}_{\delta}=\{\)all countable intersections of \(\mathcal{M}\)-sets\(\}\).

    We use \(\mathcal{M}_{s}\) and \(\mathcal{M}_{d}\) for similar notions, with "countable" replaced by "finite."

    Clearly,

    \[\mathcal{M}_{\sigma} \supseteq \mathcal{M}_{s} \supseteq \mathcal{M}\]

    and

    \[\mathcal{M}_{\delta} \supseteq \mathcal{M}_{d} \supseteq \mathcal{M}.\]

    Why?

    Note 2. Observe that \(\mathcal{M}\) is closed under finite (countable) unions iff

    \[\mathcal{M}=\mathcal{M}_{s}\left(\mathcal{M}=\mathcal{M}_{\sigma}\right).\]
    Verify! Interpret \(\mathcal{M}=\mathcal{M}_{d}\left(\mathcal{M}=\mathcal{M}_{\sigma}\right)\) similarly.

    In conclusion, we generalize Theorem 1 in §1.

    Definition 3

    The product

    \[\mathcal{M} \dot{ \times} \mathcal{N}\]

    of two set families \(\mathcal{M}\) and \(\mathcal{N}\) is the family of all sets of the form

    \[A \times B,\]

    with \(A \in \mathcal{M}\) and \(B \in \mathcal{N}\).

    (The dot in \(\dot{ \times}\) is to stress that \(\mathcal{M} \dot{ \times} \mathcal{N}\) is not really a Cartesian product.)

    Theorem \(\PageIndex{4}\)

    If \(\mathcal{M}\) and \(\mathcal{N}\) are semirings, so is \(\mathcal{M} \dot{ \times} \mathcal{N}\).

    The proof runs along the same lines as that of Theorem 1 in §1, via the set identities

    \[(X \times Y) \cap\left(X^{\prime} \times Y^{\prime}\right)=\left(X \cap X^{\prime}\right) \times\left(Y \cap Y^{\prime}\right)\]

    and

    \[(X \times Y)-\left(X^{\prime} \times Y^{\prime}\right)=\left[\left(X-X^{\prime}\right) \times Y\right] \cup\left[\left(X \cap X^{\prime}\right) \times\left(Y-Y^{\prime}\right)\right].\]

    Proof

    The details are left to the reader.

    Note 3. As every ring is a semiring (Corollary 1), the product of two rings (fields, \(\sigma\)-rings, \(\sigma\)-fields) is a semiring. However, see Problem 6 below.


    7.3: More on Set Families is shared under a CC BY license and was authored, remixed, and/or curated by LibreTexts.