7.3.E: Problems on Set Families
- Page ID
- 24412
1. Verify Examples (a),(b), and (c).
Prove Theorem 1 for rings.
Show that in Definition 1 "\(\emptyset \in \mathcal{M}\)" may be replaced by "\(\mathcal{M} \neq \emptyset\)."
[Hint: \(\emptyset=A-A\).]
\(\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\).]
Prove Theorem 2 for set fields.
Does Note 1 apply to semirings?
Prove Note 2.
Prove Theorem 3 in detail.
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}\).]
\(\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}\).]
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\}\).
\(\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}\).]
\(\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\).]
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).]\]
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.]
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).
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.
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\).
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.]
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?)]
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}\).]