Skip to main content
Mathematics LibreTexts

7.3.E: Problems on Set Families

  • Page ID
    32345
  • \( \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}\)

    Exercise \(\PageIndex{1}\)

    1. Verify Examples (a),(b), and (c).

    Exercise \(\PageIndex{1'}\)

    Prove Theorem 1 for rings.

    Exercise \(\PageIndex{2}\)

    Show that in Definition 1 "\(\emptyset \in \mathcal{M}\)" may be replaced by "\(\mathcal{M} \neq \emptyset\)."

    [Hint: \(\emptyset=A-A\).]

    Exercise \(\PageIndex{3}\)

    \(\Rightarrow\) Prove that \(\mathcal{M}\) is a field \((\sigma\)-field if \(\mathcal{M} \neq \emptyset, \mathcal{M}\) is closed under finite (countable) unions, and
    \[(\forall A \in \mathcal{M}) \quad -A \in \mathcal{M}.\]
    [Hint: \(A-B=-(-A \cup B); S=-\emptyset\).]

    Exercise \(\PageIndex{4}\)

    Prove Theorem 2 for set fields.

    Exercise \(\PageIndex{*4'}\)

    Does Note 1 apply to semirings?

    Exercise \(\PageIndex{5}\)

    Prove Note 2.

    Exercise \(\PageIndex{5'}\)

    Prove Theorem 3 in detail.

    Exercise \(\PageIndex{6}\)

    Prove Theorem 4 and show that the product \(\mathcal{M} \dot{ \times} \mathcal{N}\) of two rings need not be a ring.
    [Hint: Let \(S=E^{1}\) and \(\mathcal{M}=\mathcal{N}=2^{S}.\) Take \(A, B\) as in Theorem 1 of §1. Verify that \(A-B \notin \mathcal{M}, {\mathcal{M}} \dot{ \times} \mathcal{N}\).]

    Exercise \(\PageIndex{7}\)

    \(\Rightarrow\) Let \(\mathcal{R}, \mathcal{R}^{\prime}\) be the rings \((\sigma\)-rings, fields, \(\sigma\)-fields) generated by \(\mathcal{M}\) and \(\mathcal{N}\), respectively. Prove the following.
    (i) If \(\mathcal{M} \subseteq \mathcal{N},\) then \(\mathcal{R} \subseteq \mathcal{R}^{\prime}\).
    (ii) If \(\mathcal{M} \subseteq \mathcal{N} \subseteq \mathcal{R},\) then \(\mathcal{R}=\mathcal{R}^{\prime}\).
    (iii) If
    \[\mathcal{M}=\left\{\text {open intervals in } E^{n}\right\}\]
    and
    \[\mathcal{N}=\left\{\text {all open sets in } E^{n}\right\},\]
    then \(\mathcal{R}=\mathcal{R}^{\prime}\).
    [Hint: Use Lemma 2 in §2 for (iii). Use the minimality of \(\mathcal{R}\) and \(\mathcal{R}^{\prime}\).]

    Exercise \(\PageIndex{8}\)

    Is any of the following a semiring, ring, \(\sigma\)-ring, field, or \(\sigma\)-field? Why?
    (a) All infinite intervals in \(E^{1}\).
    (b) All open sets in a metric space \((S, \rho)\).
    (c) All closed sets in \((S, \rho)\).
    (d) All "clopen" sets in \((S, \rho)\).
    (e) \(\left\{X \in 2^{S} |-X \text { finite}\right\}\).
    (f) \(\left\{X \in 2^{S} |-X \text { countable}\right\}\).

    Exercise \(\PageIndex{9}\)

    \(\Rightarrow\) Prove that for any sequence \(\left\{A_{n}\right\}\) in a ring \(\mathcal{R},\) there is
    (a) an expanding sequence \(\left\{B_{n}\right\} \subseteq \mathcal{R}\) such that
    \[(\forall n) \quad B_{n} \supseteq A_{n}\]
    and
    \[\bigcup_{n} B_{n}=\bigcup_{n} A_{n}; \text { and}\]
    (b) a contracting sequence \(C_{n} \subseteq A_{n},\) with
    \[\bigcap_{n} C_{n}=\bigcap_{n} A_{n}.\]
    (The latter holds in semirings, too.)
    [Hint: Set \(B_{n}=\bigcup_{1}^{n} A_{k}, C_{n}=\bigcap_{1}^{n} A_{k}\).]

    Exercise \(\PageIndex{10}\)

    \(\Rightarrow\) The symmetric difference, \(A \triangle B,\) of two sets is defined
    \[A \triangle B=(A-B) \cup(B-A).\]
    Inductively, we also set
    \[\triangle_{k=1}^{1} A_{k}=A_{1}\]
    and
    \[\triangle_{k=1}^{n+1} A_{k}=\left(\triangle_{k=1}^{n} A_{k}\right) \triangle A_{n+1}.\]
    Show that symmetric differences
    (i) are commutative,
    (ii) are associative, and
    (iii) satisfy the distributive law:
    \[(A \triangle B) \cap C=(A \cap C) \triangle(B \cap C).\]
    [Hint for (ii): Set \(A^{\prime}=-A, A-B=A \cap B^{\prime}.\) Expand \((A \triangle B) \triangle C\) into an expression symmetric with respect to \(A, B,\) and \(C\).]

    Exercise \(\PageIndex{11}\)

    Prove that \(\mathcal{M}\) is a ring iff
    (i) \(\emptyset \in \mathcal{M}\);
    (ii) \((\forall A, B \in \mathcal{M}) A \triangle B \in \mathcal{M}\) and \(A \cap B \in \mathcal{M}\) (see Problem 10); equivalently,
    (ii') \(A \triangle B \in \mathcal{M}\) and \(A \cup B \in \mathcal{M}\).
    [Hint: Verify that
    \[A \cup B=(A \triangle B) \triangle(A \cap B)\]
    and
    \[A-B=(A \cup B) \triangle B,\]
    while
    \[A \cap B=(A \cup B) \triangle(A \triangle B).]\]

    Exercise \(\PageIndex{12}\)

    Show that a set family \(\mathcal{M} \neq \emptyset\) is a \(\sigma\)-ring iff one of the following conditions holds.
    (a) \(\mathcal{M}\) is closed under countable unions and proper differences \((X-Y\) with \(X \supseteq Y)\);
    (b) \(\mathcal{M}\) is closed under countable disjoint unions, proper differences, and finite intersections; or
    (c) \(\mathcal{M}\) is closed under countable unions and symmetric differences (see Problem 10).
    [Hints: (a) \(X-Y=(X \cup Y)-Y,\) a proper difference.
    (b) \(X-Y=X-(X \cap Y)\) reduces any difference to a proper one; then
    \[X \cup Y=(X-Y) \cup(Y-X) \cup(X \cap Y)\]
    shows that \(\mathcal{M}\) is closed under all finite unions; so \(\mathcal{M}\) is a ring. Now use Corollary 1 in §1 for countable unions.
    (c) Use Problem 11.]

    Exercise \(\PageIndex{13}\)

    From Problem 10, treating \(\triangle\) as addition and \(\cap\) as multiplication, show that any set ring \(\mathcal{M}\) is an algebraic ring with unity, i.e., satisfies the six field axioms (Chapter 2, §§1-4), except \(V(b)\) (existence of multiplicative inverses).

    Exercise \(\PageIndex{14}\)

    A set family \(\mathcal{H}\) is said to be hereditary iff
    \[(\forall X \in \mathcal{H})(\forall Y \subseteq X) \quad Y \in H.\]
    Prove the following.
    (a) For every family \(\mathcal{M} \subseteq 2^{S}\), there is a "smallest" hereditary ring \(\mathcal{H} \supseteq \mathcal{M}\) (\(\mathcal{H}\) is said to be generated by \(\mathcal{M}\)). Similarly for \(\sigma\)-rings, fields, and \(\sigma\)-fields.
    (b) The hereditary \(\sigma\)-ring generated by \(\mathcal{M}\) consists of those sets which can be covered by countably many \(\mathcal{M}\)-sets.

    Exercise \(\PageIndex{15}\)

    Prove that the field \((\sigma\)-field in \(S\), generated by a ring \((\sigma\)-ring \(\mathcal{R},\) consists exactly of all \(\mathcal{R}\)-sets and their complements in \(S\).

    Exercise \(\PageIndex{16}\)

    Show that the ring \(\mathcal{R}\) generated by a set family \(\mathcal{C} \neq \emptyset\) consists of all sets of the form
    \[\triangle_{k=1}^{n} A_{k}\]
    (see Problem 10), where each \(A_{k} \in \mathcal{C}_{d}\) (finite intersection of \(\mathcal{C}\)-sets).
    [Outline: By Problem 11, \(\mathcal{R}\) must contain the family (call it \(\mathcal{M}\)) of all such \(\triangle_{k=1}^{n} A_{k}\). (Why?) It remains to show that \(\mathcal{M}\) is a ring \(\supseteq \mathcal{C}\).
    Write \(A+B\) for \(A \triangle B\) and \(A B\) for \(A \cap B;\) so each \(\mathcal{M}\)-set is a "sum" of finitely many "products"
    \[A_{1} A_{2} \cdots A_{n}.\]
    By algebra, the "sum" and "product" of two such "polynomials" is such a polynomial itself. Thus
    \[(\forall X, Y \in \mathcal{M}) \quad X \triangle Y \text { and } X \cap Y \in \mathcal{M}.\]
    Now use Problem 11.]

    Exercise \(\PageIndex{17}\)

    AUse Problem 16 to obtain a new proof of Theorem 2 in §1 and Corollary 2 in the present section.
    [Hints: For semirings, \(C=\mathcal{C}_{d}.\) (Why?) Thus in Problem 16, \(A_{k} \in \mathcal{C}.\)
    Also,
    \[(\forall A, B \in \mathcal{C}) \quad A \triangle B=(A-B) \cup(B-A)\]
    where \(A-B\) and \(B-A\) are finite disjoint unions of \(\mathcal{C}\)-sets. (Why?)
    Deduce that \(A \triangle B \in \mathcal{C}_{s}^{\prime}\) and, by induction,
    \[\triangle_{k=1}^{n} A_{k} \in \mathcal{C}_{s}^{\prime};\]
    so \(\mathcal{R} \subseteq \mathcal{C}_{s}^{\prime} \subseteq \mathcal{R}.\) (Why?)]

    Exercise \(\PageIndex{18}\)

    Given a set \(A\) and a set family \(\mathcal{M},\) let
    \[A \cap{\dot\} \mathcal{M}\]
    be the family of all sets \(A \cap X,\) with \(X \in \mathcal{M};\) similarly,
    \[\mathcal{N} \dot{\cup} (\mathcal{M} \dot{-} A)=\{\text { all sets } Y \cup(X-A), \text { with } Y \in \mathcal{N}, X \in \mathcal{M}\}, \text { etc. }\]
    Show that if \(\mathcal{M}\) generates the ring \(\mathcal{R},\) then \(A \cap{\dot} \mathcal{M}\) generates the ring
    \[\mathcal{R}^{\prime}=A \cap{\dot} \mathcal{R}.\]
    Similarly for \(\sigma\)-rings, fields, \(\sigma\)-fields.
    [Hint for rings: Prove the following.
    (i) \(A \cap \mathcal{R}\) is a ring.
    (ii) \(\mathcal{M} \subseteq \mathcal{R}^{\prime} \cup(\mathcal{R} \pm A),\) with \(\mathcal{R}^{\prime}\) as above.
    (iii) \(\mathcal{R} \cup(\mathcal{R} \div A) \text { is a ring (call it } \mathcal{N})\).
    (iv) By (ii), \(\mathcal{R} \subseteq \mathcal{N},\) so \(A \cap \mathcal{R} \subseteq A \cap \mathcal{N} \subseteq \mathcal{R}^{\prime}\right.\)
    (v) \(A \cap \mathcal{R} \supseteq \mathcal{R}^{\prime}(\text { for } A \cap \mathcal{R} \supseteq A \cap \mathcal{M})\).
    Hence \(\mathcal{R}^{\prime}=A \cap \mathcal{R}\).]


    7.3.E: Problems on Set Families is shared under a not declared license and was authored, remixed, and/or curated by LibreTexts.

    • Was this article helpful?