Set Systems

The collection $\bigcap_{\alpha \in A} \mathcal{P}_{\alpha }$ is a $\pi$-system on $\Omega$.

Let $\mathcal{A} \subseteq 2^{\Omega }$. Suppose that $\left\{ \mathcal{P}_{\alpha }: \alpha \in A\right\}$ is the "exhaustive list" of all the $\pi$ system that contain $\mathcal{A}$. In other words, each $\mathcal{P}_{\alpha } \supseteq \mathcal{A}$, and any $\pi$-system that contains $\mathcal{A}$ coincides with some $\mathcal{P}_{\alpha }$. Then $\bigcap_{\alpha \in A} \mathcal{P}_{\alpha }$ is a $\pi$-system that contains A. If $Q$ is a $\pi$-system containing $\mathcal{A}$, then $\bigcap_{\alpha \in A} \mathcal{P}_{\alpha } \subseteq Q$. The minimal $\pi$-system generated by A always exists.

Suppose that $\mathcal{P}$ is a $\pi$-system with $\mathcal{P} \supseteq \mathcal{A}$, and suppose that $\mathcal{P}$ is contained in any other $\pi$-system that contains $\mathcal{A}$. Then $\mathcal{P}=\bigcap_{\alpha \in A} \mathcal{P}_{\alpha }$, with notation as in (b). The minimal $\pi$-system containing A [which always exists] is also unique.

$\mathscr {L}$ is a $\lambda$-system iff $\mathscr {L}$ satisfies ( $\lambda_{1}$ ), ( $\lambda_{2}^{\prime }$ ), and ( $\lambda_{3}$ ).

Every $\lambda$-system additionally satisfies ( $\lambda_{4}$ ), ( $\lambda_{5}$ ), and ( $\lambda_{6}$ ).

$\mathscr {L}$ is a $\lambda$-system iff $\mathscr {L}$ satisfies ( $\lambda_{1}$ ), ( $\lambda_{2}^{\prime }$ ), and ( $\lambda_{5}$ ).

${ }^{1}$ The conditions are: $\left(\boldsymbol {\lambda }_{\mathbf{1}}\right) \quad \Omega \in \mathscr {L}$; ( $\boldsymbol {\lambda }_{\mathbf{2}}$) $A \in \mathscr {L} \Longrightarrow A^{c} \in \mathscr {L}$; ( $\boldsymbol {\lambda }_{\mathbf{2}}^{\prime }$) $\quad A, B \in \mathscr {L} \& A \subseteq B \Longrightarrow B \backslash A \in \mathscr {L}$; ( $\boldsymbol {\lambda }_{\mathbf{3}}$) For any disjoint $\left\{ A_{n}\right\}_{n=1}^{\infty } \subseteq \mathscr {L}, \bigcup_{n=1}^{\infty } A_{n} \in \mathscr {L}$; (λ4) $\quad A, B \in \mathscr {L} \& A \cap B=\varnothing \Longrightarrow A \cup B \in \mathscr {L}$; ( h $_{\text{5 }}$) $\forall \left\{ A_{n}\right\}_{n=1}^{\infty } \subseteq \mathscr {L}, A_{n} \uparrow \Longrightarrow \bigcup_{n=1}^{\infty } A_{n} \in \mathscr {L}$; ( $\boldsymbol {\lambda }_{\mathbf{6}}$) $\quad \forall \left\{ A_{n}\right\}_{n=1}^{\infty } \subseteq \mathscr {L}, A_{n} \downarrow \Longrightarrow \bigcap_{n=1}^{\infty } A_{n} \in \mathscr {L}$.

If a collection $\mathscr {L}$ is nonempty and satisfies ( $\lambda_{2}$ ) and ( $\lambda_{3}$ ), then $\mathscr {L}$ is a $\lambda$-system.

The collection $\bigcap_{\alpha \in A} \mathscr {L}_{\alpha }$ is a $\lambda$-system on $\Omega$.

Suppose that $\mathcal{A} \subseteq 2^{\Omega }$ is such that $\mathcal{A}$ is contained in each $\mathscr {L}_{\alpha }$, and suppose that $\left\{ \mathscr {L}_{\alpha }: \alpha \in A\right\}$ is the "exhaustive list" of all the $\lambda$-system that contain $\mathcal{A}$. Then $\bigcap_{\alpha \in A} \mathscr {L}_{\alpha }$ is a $\lambda$-system that contains $\mathcal{A}$. If $\mathcal{Q}$ is a $\lambda$-system on $\Omega$ that contains $\mathcal{A}$, then $\bigcap_{\alpha \in A} \mathscr {L}_{\alpha } \subseteq \mathcal{Q}$. The minimal $\lambda$-system generated by $\mathcal{A}$ always exists.

Let $\mathscr {L}$ denote a $\lambda$-system over $\Omega$ with $\mathscr {L} \supseteq \mathscr {A}$ and where $\mathscr {L}$ is contained in any other $\lambda$-system also containing $\mathcal{A}$. Then $\mathscr {L}=\bigcap_{\alpha \in A} \mathscr {L}_{\alpha }$, with notation as in (b). Therefore, the $\lambda$-system generated by Always exists and is unique.

Some define $A$ to be a semiring iff $A$ is a nonempty $\pi$-system such that both $E, F \in \mathcal{A}$ and $E \subseteq F$ imply the existence of a finite collection $C_{0}, C_{1}, \ldots , C_{n} \in$ A with $E=C_{0} \subseteq C_{1} \subseteq \ldots \subseteq C_{n} \subseteq F$ and $C_{i} \backslash C_{i-1} \in \mathcal{A}$ for $i=1, \ldots , n$. This definition of a semiring is equivalent to our definition of a semiring.

Some define $\mathcal{A}$ to be a semiring by stipulating (SR1), (SR2), and the following property: $A, B \in \mathcal{A}$ implies the existence of disjoint $\mathcal{A}$-sets $C_{0}, C_{1}, \ldots , C_{n}$ with $B \backslash A=\bigcup_{i=0}^{n} C_{i}$. Note that here $B \backslash A$ is not necessarily a proper difference. If $\mathcal{A}$ is a semiring by this definition, then $\mathcal{A}$ is a semiring by our definition, but the converse is not necessarily true.

$\varnothing$ is in every ring.

$\mathcal{R}$ is a ring iff $\mathcal{R}$ satisfies (R1), (R2), and (R4) $A, B \in \mathcal{R}$ with $A \subseteq B$ implies $B \backslash A \in \mathcal{R}$.

Every ring satisfies (R5) $A, B \in \mathcal{R}$ implies $A \Delta B \in \mathcal{R}$.

Every ring is a $\pi$-system.

Every ring is closed under finite unions and finite intersections.

$\mathcal{R}$ is a ring iff $\mathcal{R}$ a nonempty $\pi$-system that satisfies ( $R 4$ ) along with (R6) $A, B \in \mathcal{R}$ and $A \cap B=\varnothing$ imply $A \cup B \in \mathcal{R}$.

$\mathcal{R}$ is a ring iff $\mathcal{R}$ is a nonempty $\pi$-system that satisfies (R5).

Suppose that $\left\{ \mathcal{R}_{\alpha }: \alpha \in A\right\}$ is the "exhaustive list" of all rings that contain $\mathcal{A}$. Then $\bigcap_{\alpha \in A} \mathcal{R}_{\alpha }$ is a ring that contains $\mathcal{A}$, and $\bigcap_{\alpha \in A} \mathcal{R}_{\alpha }$ is contained in any ring that contains $\mathcal{A}$. The minimal ring containing $\mathcal{A}$ is always exists and is unique.

The collection of finite unions of rsc intervals is a ring on $\mathbb {R}$.

Let $\Omega$ be uncountable. The collection of all amc subsets of $\Omega$ is a ring on $\Omega$.

Every ring is a semiring. However, not every semiring is a ring.

Let $\mathcal{A}$ denote a semiring on $\Omega$, and let $\mathcal{R}$ consist of the finite disjoint unions of $A$-sets. Then $\mathcal{R}$ is closed under finite intersections and disjoint unions.

If $A, B \in \mathcal{A}$ and $A \subseteq B$, then $B-A \in \mathcal{R}$.

$A \in \mathcal{A}, B \in \mathcal{R}$, and $A \subseteq B$ imply $B-A \in \mathcal{R}$.

$A, B \in \mathcal{R}$ and $A \subseteq B$ imply $B-A \in \mathcal{R}$.

$\mathcal{R}$ is the minimal ring generated by $\mathcal{A}$.

A semiring that satisfies (R2) is a ring.

Given $\mathscr {C} \subseteq 2^{\Omega }$, let $\mathscr {C}^{*}$ denote the collection of all finite unions of differences of $\mathscr {C}$-sets. If $\operatorname {card}(\mathscr {C})=\aleph_{0}$, then $\operatorname {card}\left(\mathscr {C}^{*}\right)=\aleph_{0}$. Also, $\varnothing \in \mathscr {C}$ implies $\mathscr {C} \subseteq \mathscr {C}^{*}$.

Let $\mathcal{A}_{0}=\mathcal{A}$, and define $\mathcal{A}_{n}=\mathcal{A}_{n-1}^{*}$ for $n \geqslant 1$. Then $\mathcal{A} \subseteq \bigcup_{n=0}^{\infty } \mathcal{A}_{n} \subseteq \mathfrak {R}(\mathcal{A})$, where $\mathfrak {R}(\mathcal{A})$ is the minimal ring generated by $\mathcal{A}$, and where [without loss of generality] $\varnothing \in \mathcal{A}$. Also, $\operatorname {card}\left(\bigcup_{n=0}^{\infty } \mathcal{A}_{n}\right)=\aleph_{0}$.

$\bigcup_{n=0}^{\infty } \mathcal{A}_{n}$ is a ring on $\Omega$, and from the fact that $\mathfrak {R}(\mathcal{A})$ is the minimal ring containing $\mathcal{A}$, we have $\bigcup_{n=0}^{\infty } \mathcal{A}_{n}=\mathfrak {R}(\mathcal{A})$, and thus $\operatorname {card}(\mathfrak {R}(\mathcal{A}))=\aleph_{0}$.

We may generalize: if $\mathcal{A}$ is infinite, then $\operatorname {card}(\mathcal{A})=\operatorname {card}(\mathfrak {R}(\mathcal{A}))$.

If $\mathcal{A}^{\prime }$ is a field on $\Omega^{\prime }$, then $f^{-1}\left(\mathcal{A}^{\prime }\right)$ is a field on $\Omega$.

$f(\mathcal{A})$ may not be a field over $\Omega^{\prime }$ even if $\mathcal{A}$ is a field on $\Omega$.

$\mathcal{F}$ is an algebra on $\Omega$ iff $\mathcal{F}$ is a ring on $\Omega$ with $\Omega \in \mathcal{F}$.

$\mathcal{F}$ is an algebra iff $\mathcal{F}$ is a field. Thus algebra and field are synonymous. proof. (a: ⟹) Suppose $\mathcal{F}$ is an algebra. Then, (R1) $\quad \mathcal{F} \neq \varnothing$ by assumption. (R2) $\quad \mathcal{F}$ is $\cup$-stable follows (F3). (R3) The assumption of $\Omega \in \mathscr {F}$ and (F2) imply that if $A, B \in \mathscr {F}$, then $A^{c}= \Omega -A \in \mathscr {F}$ and $B^{c}=\Omega -B \in \mathscr {F}$. Then

This proves that $\mathcal{F}$ is closed under difference. (a: ⇐) Suppose $\mathcal{F}$ is a ring and $\Omega \in \mathcal{F}$. To prove $\mathcal{F}$ is an algebra on $\Omega$, note that (A1) $\quad \mathcal{F} \neq \varnothing$ since $\mathcal{F}$ is a ring. (F2) Let $A \in \mathcal{F}$. Because $\Omega \in \mathcal{F}$ and (R3), we have $A^{c}=\Omega -A \in \mathcal{F}$. This proves that $\mathcal{F}$ is closed under difference. (F3) $\cup$-stability follows (R2). (b) We need only to prove that $\mathcal{F}$ is an field if $\mathcal{F}$ is an algebra since the reverse direction is trivial.

Suppose $\mathcal{F}$ is an algebra. We want to show $\Omega \in \mathcal{F}$. Since $\mathcal{F} \neq \varnothing$ by definition of an algebra, there must exist $A \in \mathcal{F}$. Then $A^{c} \in \mathcal{F}$ by (F2), and so $\Omega =A \cup A^{c} \in \mathcal{F}$ by (F3). $\square$

If $\mathcal{F}$ is both a field and a monotone class, then $\mathcal{F}$ is a $\sigma$-field.

A field is a monotone class if and only if it is a $\sigma$-field.

$\mathcal{F}$ satisfies (S1), (S2), and closure under amc intersections iff $\mathcal{F}$ is a $\sigma$-field.

Every field that is closed under countable disjoint unions is a $\sigma$-field.

If $\mathcal{F}$ satisfies (S1), closure under differences, and closure under countable unions or closure under countable intersections, then $\mathcal{F}$ is a $\sigma$-field.

A finite union of $\sigma$-fields on $\Omega$ is not necessarily a field on $\Omega$.

If a finite union of $\sigma$-fields on $\Omega$ is a field, then it is a $\sigma$-field as well.

Given $\sigma$-fields $\mathcal{F}_{1} \subsetneq \mathcal{F}_{2} \subsetneq \cdots$ on $\Omega$, it is not necessarily the case that $\bigcup_{n=1}^{\infty } \mathcal{F}_{n}$ is a $\sigma$-field.

An amc union of sets of the first category is of the first category.

Let $\mathcal{F}=\left\{ A \subseteq \mathbb {R}: A \text{ or } A^{c} \text{ is a set of the first category}\right\}$. Then $\mathcal{F}$ is a $\sigma$-field of subsets of $\mathbb {R}$.

Every $\sigma$-ring is closed under finite unions and amc intersections.

$\mathcal{F}$ is a $\sigma$-field iff $\mathcal{F}$ is a $\sigma$-ring with $\Omega \in \mathcal{F}$.

State and prove an existence and uniqueness result regarding the [minimal] $\sigma$-ring generated by a collection $A$ of subsets of $\Omega$.

For any collection $\mathcal{C}$ of sets, let $\mathcal{C}^{*}$ denote the collection of all countable unions of differences of $\mathcal{C}$-sets. Define $\mathcal{A}_{0}=\mathcal{A}$, and for any ordinal $\alpha \succ 0$, define $\mathcal{A}_{\alpha }=\left(\bigcup_{0 \preceq \beta \prec \alpha } \mathcal{A}_{\beta }\right)^{*}$. Then $0 \preceq \alpha \prec \beta$ implies $\mathcal{A} \subseteq \mathcal{A}_{\alpha } \subseteq \mathcal{A}_{\beta } \subseteq S(\mathcal{A})$.

Letting $\omega$ denote the first uncountable ordinal, show that $S(\mathcal{A})=\bigcup_{0 \preceq \alpha \prec \omega } \mathcal{A}_{\alpha }$.

If $\operatorname {card}(\mathcal{A}) \leq \mathfrak {c}$, then $\operatorname {card}(S(\mathcal{A})) \leq \mathfrak {c}$.

If $\Omega$ is finite, then any $\sigma$-field on $\Omega$ is finite.

For the remainder, assume that $\Omega$ is infinite and that there is a countably infinite $\sigma$-field $\mathcal{F}=\left\{ A_{1}, A_{2}, \ldots \right\}$ on $\Omega$. For each $\omega \in \Omega$, let $B_{\omega }=\bigcap \left\{ A_{n}: \omega \in A_{n}\right\}$. For any distinct $\omega , \omega^{\prime } \in \Omega$, either $B_{\omega }=B_{\omega^{\prime }}$ or $B_{\omega } \cap B_{\omega^{\prime }}=\varnothing$.

From (b), there exists a disjoint collection $\left\{ C_{1}, C_{2}, \ldots \right\}$ of nonempty $\mathcal{F}$-sets with $\bigcup_{n=1}^{\infty } C_{n}=\Omega$.

For each sequence $e=\left(e_{1}, e_{2}, \ldots \right)$ of 0's and 1's, let $D_{e}=\bigcup \left\{ C_{n}: e_{n}=1\right\}$. Then $e \neq e^{\prime }$ forces $D_{e} \neq D_{e^{\prime }}$, and a contradiction ensues. Hence, there cannot exist a countably infinite $\sigma$-field on our infinite $\Omega$.

If $\mathcal{A} \subseteq \mathcal{A}^{\prime } \subseteq \sigma (\mathcal{A})$, then $\sigma \left(\mathcal{A}^{\prime }\right)=\sigma (\mathcal{A})$.

For any collection $\varnothing \neq \mathcal{A} \subseteq 2^{\Omega }, \pi (\mathcal{A}) \subseteq \lambda (\mathcal{A}) \subseteq \sigma (\mathcal{A})$.

If the nonempty collection $\mathcal{A}$ is finite, then $\sigma (\mathcal{A})=f(\mathcal{A})$.

For arbitrary collection $\mathcal{A}$, we have $\sigma (\mathcal{A})=\sigma (f(\mathcal{A}))$.

For arbitrary collection $\mathcal{A}$, we have $f(\sigma (\mathcal{A}))=\sigma (f(\mathcal{A}))$.

Let $\mathcal{C}$ denote the class of sets of the stated form. Then $\Omega \in \mathcal{C}$ and $\mathcal{C}$ is closed under intersection.

Show that $\mathcal{C}$ is closed under complementation by first showing that

where if $n_{i}<2$, $\bigcup_{j=2}^{n_{i}}\left(A_{i j}^{c} \cap \bigcap_{k=1}^{j-1} A_{i k}\right)$ is defined as $\varnothing$, $i=1, \ldots , m$.

For $i=1, \ldots , m$, $\bigcup_{j=2}^{n_{i}}\left(A_{i j}^{c} \cap \bigcap_{k=1}^{j-1} A_{i k}\right) \in \mathcal{C}$. Also, by closure under intersection, we have $\left(\bigcup_{i=1}^{m} \bigcap_{j=1}^{n_{i}} A_{i j}\right)^{c} \in \mathcal{C}$.

$\mathcal{C}$ is a field that contains $\mathcal{A}$, and thus $f(\mathcal{A}) \subseteq \mathcal{C}$.

Every $\mathcal{C}$-set must be in any field containing $\mathcal{A}$, hence $\mathcal{C} \subseteq f(\mathcal{A})$.

$f(\mathcal{A})=\left\{ A \subseteq \Omega : A \text{ is finite or } A^{c} \text{ is finite}\right\}$.

When $\Omega$ is amc, $\sigma (\mathcal{A})=2^{\Omega }$.

For general $\Omega$, $\sigma (\mathcal{A})=\left\{ A \subseteq \Omega : A \text{ or } A^{c} \text{ is amc}\right\}$.

Suppose that $\mathcal{A}$ is such that $\sigma (\mathcal{A})=2^{\Omega }$. For each distinct pair $\omega , \omega^{\prime } \in \Omega$ there exists $A \in \mathcal{A}$ with $\omega \in A$ but $\omega^{\prime } \notin A$.

Let $\Omega$ be countable, and suppose that for each distinct pair $\omega , \omega^{\prime } \in \Omega$, there exists a set $A \in \mathcal{A}$ such that $\omega \in A$ but $\omega^{\prime } \notin A$. Then $\sigma (\mathcal{A})=2^{\Omega }$.

$\sigma (\mathcal{A}) \cap B$ is a $\sigma$-field on $B$.

Next, define $\sigma_{B}(\mathcal{A} \cap B)$ to be the minimal $\sigma$-field over $B$ generated by the class $\mathcal{A} \cap B$. Then $\sigma_{B}(\mathcal{A} \cap B)=\sigma (\mathcal{A}) \cap B$.