Set Theory: Systems of Sets

Definitions of system of sets.

Definition 1 A nonempty system of sets $\mathscr{R}$ is called a ring (of sets) if $A \triangle B \in \mathscr{R}$ and $A \cap B \in \mathscr{R}$ for all $A \in \mathscr{R}$, $B \in \mathscr{R}$.

Since $A \cup B = (A \triangle B) \triangle (A \cap B)$ and $A - B = A \triangle (A \cap B)$, a ring is closed under union and difference too. Since $A - A = \emptyset$, a ring must contain the empty set. $E \in \mathscr{R}$ is a unit if $A \cap E \in A$ for all $A \in \mathscr{R}$. A ring of sets with a unit, is an algebra (of sets).

Theorem 1

The intersection $\mathscr{R} = \cap_\alpha \mathscr{R}_\alpha$ of any set of rings is itself a ring.

Proof

An immediate consequence of Definition 1.

Theorem 2

Given any nonempty system of sets $\mathscr{S}$, there is a unique ring $\mathscr{P}$ containing $\mathscr{S}$ and contained in every ring containing $\mathscr{S}$.

Proof

If $\mathscr{P}$ exists, then clearly $\mathscr{P}$ is unique. To prove $\mathscr{P}$ exists, consider the union \[X = \cup_{A \in \mathscr{S}} A\] of all sets $A$ belonging to $\mathscr{S}$ and the ring $\mathscr{M}(X)$ of all subsets of $X$. Let $\Sigma$ be the set of all rings contained in $\mathscr{M}(X)$ and containing $\mathscr{S}$. Then the intersection \[\mathscr{P} = \cap_{\mathscr{R} \in \Sigma} \mathscr{R}\] of all these rings clearly has the desired properties. $\mathscr{P}$ clearly contains $\mathscr{S}$. Moreover, if $\mathscr{R}^*$ is any ring containing $\mathscr{S}$, then the intersection $\mathscr{R} = \mathscr{R}^* \cup \mathscr{M}(X)$ is a ring in $\Sigma$ and hence $\mathscr{P} \subseteq \mathscr{R} \subseteq \mathscr{R}^*$, as required.

The ring $\mathscr{P}$ is the minimal ring generated by the system $\mathscr{S}$, and will henceforth be denoted by $\mathscr{R}(\mathscr{P})$.

Defintion 2 A system of sets $\mathscr{S}$ is a semiring if

$\mathscr{S}$ contains the empty set $\emptyset$;
$A \cap B \in \mathscr{S}$ for all $A, B \in \mathscr{S}$;
If $\mathscr{S}$ contains the sets $A$ and $A_1 \subseteq A$, then $A$ can

be represented as a finite union \[A = \cup_{k=1}^{n} A_k\] of pairwise disjoint sets of $\mathscr{S}$, with the given set $A_1$ as its first term. (This is called a finite expansion of $A$.)

Lemma 1

Suppose the sets $A$, $A_1$, …, $A_n$, where $A_1$, …, $A_n$ are pairwise disjoint subsets of $A$, all belong to semiring $\mathscr{S}$. Then there is finite expansion \[A = \cup_{k=1}^s A_k (s \geq n)\] with $A_1$, …, $A_n$ as its first $n$ terms, where $A_k \in \mathscr{S}$, $A_k \cap A_l = \emptyset$ for all $k, l = 1, …, n$.

Proof

The lemma holds for $n=1$, by the definition of a semiring. Suppose the lemma holds for $n=m$, and consider $m+1$ sets $A_1$, …, $A_m$, $A_{m+1}$ satisfying the conditions of the lemma. By hypothesis, \[A = A_1 \cup … \cup A_m \cup B_1 \cup … \cup B_p\] where the sets $A_1$, …, $A_m$, $B_1$, …, $B_p$ are pairwise disjoint subsets of $A$, all belonging to $\mathscr{S}$. Let \[B_{q1} = A_{m+1} \cap B_{q}\] By the defintion of a semiring \[B_{q} = B_{q1} \cup … \cup B_{qr_q}\] where the sets $B_{qj}$ ($j=1$, …, $r_q$) are pairwise disjoint subset of $B_q$, all belong to $\mathscr{S}$. But then, \[A = A_1 \cup … \cup A_m \cup _{m+1} \cup_{q=1}^p (\cup_{j=2}^{r_q} B_{qj})\] i.e., the lemma is true for $n = m + 1$. Mathematical induction completes the proof.

Lemma 2

Given any finite system of sets $A_1, …, A_n$ belonging to a semiring $\mathscr{S}$, there is a finite system of pairwise disjoint sets $B_1$, …, $B_t$ belonging to $\mathscr{S}$ such that every $A_k$ has a finite expansion \[A_k = \cup_{s \in M_k} B_s (k=1, …, n)\] with respect to certain of the sets $B_s$. (Here $M_k$ denotes some subset of $\{1, 2, …, t\}$, depending on the choice of $k$.)

Proof

The lemma is trivial for $n = 1$. Suppose the lemma is true for $n = m$ and consider a system of sets $A_1$, …, $A_m$, $A_{m+1}$. Let $B_1$, …, $B_t$ be sets of $\mathscr{S}$ satisfying the conditions of the lemma with repsect to $a_1$, …, $A_m$, and let \[B_{s1} = SA_{m+1} \cap B_s\] Then, by Lemma 1, there is an expansion \[A_{m+1} = (\cup_{s=1}^t B_{s1}) \cup (\cup_{p = 1}^q B’_p) (B’_p \in \mathscr{S})\] while, by the very definition of a semiring, there is an expansion \[B_s = B_{s1} \cup … \cup B_{sr_s} (B_{sj} \in \mathscr{S})\] It is easy to see that $A_k = \cup_{s \in M_k} (\cup_{j=1}^{r_s} B_{sj} (k = 1, …, m)$ for some suitable $M_k$. Moreover, the sets $B_{sj}$, $B’_p$ are pairwise disjoint. Hence the sets $B_sj$, $B’_p$ satisfy the conditions of the lemma with repect to $A_1, …, A_m, A_{m+1}$. Mathematical induction completes the proof.

Theorem 3

If $\mathscr{S)$ is a semiring, then $\mathscr{R}(\mathscr{S})$ coincides with the system $\mathscr{Z}$ of all sets $A$ which have finite expansions \[A = \cup_{k=1}^n A_k\] with respect to the sets $A_k \in \mathscr{S}$ .

Proof

FIrst prove $\mathscr{Z}$ is a ring. Let $A, B \in \mathscr{Z}$. Then there are expansions \[A = \cup_{i=1}^m A_i (A_i \in \mathscr{S}, B = \cup_{j=1}^n B_j (B_j \in \mathscr{S}\] Since $\mathscr{S}$ is a semiring, the sets $C_{ij} = A_i \cap B_j$ also belong to $\mathscr{S}$.

By Lemma 1, there are expansions \[A_i = (\cup_{j=1}^n C_{ij}) \cup (\cup_{k=1}^{r_i} D_{ik}) (D_{ik} \in \mathscr{S})\] \[B_j = (\cup_{i=1}^m C_{ij}) \cup (\cup_{l=1}^{s_j} E_{jl}) (E_{jl} \in \mathscr{S})\] It follows that $A \cap B$ and $A \triangle B$ have the expansions \[A \cap B = \cup_{i, j} C_{ij}\] \[A \triangle B = (\cup_{i, k} D_{ik}) \cup (\cup_{j, l} E_{jl})\] and hence belong to $\mathscr{Z}$. Therefore $\mathscr{Z}$ is a ring. That $\mathscr{Z}$ is the minimal ring generated by $\mathscr{S}$, is obvious.

Definition 3 A ring of sets is a $\sigma$-ring if it contains the union \[S = \cup_{n=1}^\infty A_n\] whenever it contains the sets $A_1, …, A_n, …$. A $\sigma$-ring with a unit $E$ is called a $\sigma$-algebra.

Definition 4 A ring of sets is called a $\delta$-ring if it contains the intersection \[D = \cap_{n=1}^\infty A_n\] whenever it contains the sets $A_1, …, A_n, …$. A $\delta$-ring with a unit is called a $\delta$-algebra.

Theorem 4

Every $\sigma$-algebra is a $\delta$-algebra and conversely.

Proof

From the ‘dual’ formulas: \[\cup_n A_n = E - \cap_n (E - A_n)\] \[\cap_n A_n = E - \cup_n (E - A_n)\]

$\sigma$-algebras (and equivalently $\delta$-algebras) are also called Borel algebras (B-algebras).

A Borel algebra $\mathscr{B}$ is irreducible (with respect to the system $\mathscr{S}$ if it contains no points that do not belong to one of the sets $A \in \mathscr{S}$.

Theorem 5

Given any nonempty system of sets $\mathscr{S}$, there is a unique irreducible (with respect to $\mathscr{S}$) B-algebra $\mathscr{B}(\mathscr{S})$ containing $\mathscr{S}$ and contained in every B-algebra containing $\mathscr{S}$.

Proof

Virtually identical to that of Theorem 2. The B-algebra $\mathscr{B}(\mathscr{S})$ is called the minimal B-algebra generated by the system $\mathscr{S}$ or the Borel closure of $\mathscr{S}$.

Problems

Let $X$ be an uncountable set, and let $\mathscr{R}$ be the ring consisting of all finite subsets of $X$ and their complements. Is $\mathscr{R}$ a $\sigma$-ring?

Yes. (?)
Are open intervals Borel sets?

No, because their complements wouldn’t be included. (?)
Let $y = f(x)$ be a function from $M$ to $N$. Let $\mathscr{M}$ be a system of subsets of $M$, and let $f(\mathscr{M})$ denote the system of all images $f(A)$ of sets $A \in \mathscr{M}$. Moreover, let $\mathscr{N}$ be a system of subsets of $N$, and let $f^-1(\mathscr{N}) denote the system of all preimages $f^{-1}(B)$ of sets $B ∈ \mathscr{N}. Prove that
1. If $\mathscr{N}$ is a ring, so is $f^{-1}(\mathscr{N})$
2. If $\mathscr{N}$ is an algebra, so is $f^{-1}(\mathscr{N})$
3. If $\mathscr{N}$ is an B-algebra, so is $f^{-1}(\mathscr{N})$
4. $\mathscr{R}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{R}(\mathscr{N}))$
5. $\mathscr{B}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{B}(\mathscr{N}))$
Which of these assertions remain true if $\mathscr{N}$ is replaced by $\mathscr{M}$ and $f^{-1}$ by $f$?
1. Evidently closed under union and set difference, hence ring.
2. Same argument as above.
3. Still closed under countable unions.
4. If ring on left, by above, we have ring on right. Need to show the same. Check same under union and set difference. And check reverse.
5. Use same argument, extend for countable unions.
All statements become false, as $f(A \cap B)$ does not imply $f(A) \cap f(B)$.

Set Theory: Systems of Sets

Problems

Christian Christiansen