$$\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 7.3.E: Problems on Set Families

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\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 \|}$$ $$\newcommand{\inner}{\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 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

## 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}$$.]