# 7.3.E: Problems on Set Families

$$\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?

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.