Chapter 1 - Set Theory
1.4 Systems of Sets
Results
Systems of sets are sets of sets, or family of sets. Unless specified, the elements will be
subsets of some fixed set $X$.
Definition 1
A nonempty system of sets $\mathscr{R}$ is called a
ring (of sets) if
$A\bigtriangleup B\in\mathscr{R}$ and $A\cap B\in\mathscr{R}$ whenever $A\in\mathscr{R}$,
$B\in\mathscr{R}$.
Note that, since
$$
A\cup B = (A\bigtriangleup B)\bigtriangleup(A\cap B)
$$
$$
A - B = A\bigtriangleup(A\cap B),
$$
we also have $A\cup B\in\mathscr{R}$ and $A-B\in\mathscr{R}$ whenver $A\in\mathscr{R}$,
$B\in\mathscr{R}$, so a ring is closed under unions, intersections, differences and symmetric differences.
Theorem 1
The intersection
$$
\mathscr{R} = \bigcap_\alpha\mathscr{R}_\alpha
$$
of any set of rings is itself a ring.
Proof.
An immediate consequence of Definition 1. But let's verify it:
$$
A, B\in \mathscr{R} \Rightarrow A, B\in \bigcap_\alpha\mathscr{R}_\alpha
\Rightarrow A, B\in \mathscr{R}_\alpha
$$
for all $\alpha$. Since each $\mathscr{R}_\alpha$ is a ring, then
$$
\forall\alpha, A\bigtriangleup B\in \mathscr{R}_\alpha \Rightarrow
A\bigtriangleup B\in \bigcap_\alpha\mathscr{R}_\alpha \Rightarrow
A\bigtriangleup B\in \mathscr{R}.
$$
The exact same argument holds for the intersection.
■
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 such a $\mathscr{P}$ exists, it is clearly unique. Since there will be a smallest ring
containing $\mathscr{S}$ which will be $\mathscr{P}$. To prove the existence of $\mathscr{P}$,
consider the union
$$
X = \bigcup_{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 of sets contained in $\mathscr{M}(X)$ and containing $\mathscr{S}$.
Then the intersection
$$
\mathscr{P} = \bigcup_{\mathscr{R}\in\Sigma}\mathscr{R}
$$
of all these rings clearly has the desired properties. In fact, $\mathscr{P}$ obviously contains
$\mathscr{S}$. Moreover, if $\mathscr{R}^*$ is any ring containing $\mathscr{S}$, then the intersection
$\mathscr{R} = \mathscr{R}^*\cap\mathscr{M}(X)$ is a ring in $\Sigma$ and hence
$\mathscr{P}\subset\mathscr{R}\subset\mathscr{R}^*$, as required. The ring $\mathscr{P}$ is called
the
minimal ring generated by the system $\mathscr{S}$, and will henceforth be denoted by
$\mathscr{R}(\mathscr{S})$.
■
Definition 2
A system of sets $\mathscr{S}$ is called a
semiring (of sets) if
1) $\mathscr{S}$ contains the empty set $\emptyset$;
2) $A, B\in\mathscr{S} \;\Longrightarrow\; A\cap B\in\mathscr{S}$
3) If $\mathscr{S}$ contains the sets $A$ and $A_1\subset A$, then $A$ can be represented
as a finite union
$$
A = \bigcup_{k=1}^n A_k
$$
of pairwise disjoint sets of $\mathscr{S}$, with the given set $A_1$ as its first term.
Lemma 1
Suppose the sets $A, A_1, \ldots, A_n$ where $A_1, \ldots, A_n$ are pairwise disjoint
subsets of $A$, all belong to a semiring $\mathscr{S}$. Then there is a finite expansion
$$
A = \bigcup_{k=1}^s A_k \qquad (s\geq n) %\tag{$s\geq n$}
$$
with $A_1,\ldots, A_n$ as its first $n$ terms, where $A_k\in\mathscr{S}$, $A_k\cap A_l = \emptyset$
for all $k,1 = 1,\ldots,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,\ldots, A_m, A_{m+1}$ satisfying the conditions of the lemma.
By hypothesis,
$$
A = A_1\cup\ldots\cup A_m\cup B_1\cup\ldots\cup B_p,
$$
where the sets $A_1,\ldots,A_m,B_1,\ldots,B_p$ are pairwise disjoint subsets of $A$, all belonging
to $\mathscr{S}$. Let
$$
B_{q1} = A_{m+1}\cap B_q.
$$
By the definition of a semiring,
$$
B_q = B_{q1}\cup\ldots\cup B_{qr_q},
$$
where the sets $B_{qj}$ ($j=1,\ldots, r_q)$ are pairwise disjoint subsets of $B_q$,
all belonging to $\mathscr{S}$. But then it is easy to see that
$$
A = A_1\cup\ldots\cup A_m\cup A_{m+1}\cup\bigcup_{q=1}^p\left(\bigcup_{q=1}^{r_q}B_{qj}\right),
$$
i.e. the lemma is true for $n = m + 1$. The proof now follows by mathematical induction.
■
Lemma 2
Given any finite system of sets $A_1,\ldots, A_n$ belonging to a semiring $\mathscr{S}$,
there is a finite system of pairwise disjoint sets $B_1,\ldots,B_t$ belonging to $\mathscr{S}$
such that every $A_k$ has a finite expansion
$$
A_k = \bigcup_{s\in M_k}B_s, \quad(k = 1,\ldots, n)
$$
with respect to certain subselections of the sets $B_s$.
(Here $M_k$ is some subset of the set $\{1, 2, \ldots, t\}$ depending on the choice of $k$)
Proof.
The lemma is trivial for $n=1$, since we need only set $t=1$, $B_1 = A_1$. Suppose the lemma
is true for $n=m$, and consider a system of sets $A_1, \ldots, A_n, A_{m+1}$ in $\mathscr{S}$.
Let $B_1,\ldots,B_t$ be sets of $\mathscr{S}$ satisfying the conditions of the lemma with respect to
$A_1,\ldots,A_m$, and let
$$
B_{s1} = A_{m+1}\cap B_s.
$$
Then, by Lemma 1, there is an expansion
$$
A_{m+1} = \left(\bigcup_{s=1}^t B_{s1}\right)\cup\left(\bigcup_{p=1}^q B'_p\right)
\qquad(B'_p\in\mathscr{S})
$$
while, by the very definition of a semiring, there is an expansion
$$
B_s = B_{s1}\cup B_{s2}\cup\ldots\cup B_{sr_s},\qquad (B_{sj}\in\mathscr{S}).
$$
It is easy to see that
$$
A_k = \bigcup_{s\in M_k}\left(\bigcup_{j=1}^{r_s} B_{sj}\right)
\qquad (k=1,\ldots, 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 respect to
$A_1, \ldots, A_n, A_{m+1}$. The proof follows by mathematical induction.
■
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 = \bigcup_{k=1}^n A_k
$$
with respect to the sets $A_k\in\mathscr{S}$.
[In other words: we can make a ring
from a semiring by finding all finite unions of the sets in the semiring].
Proof.
First we prove that $\mathscr{Z}$ is a ring. Let $A$ and $B$ by any two sets in $\mathscr{Z}$.
Then there are expansions
$$
A = \bigcup_{i=1}^m A_i, \qquad (A_i\in\mathscr{S}),
$$
$$
B = \bigcup_{j=1}^n B_j, \qquad (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 = \left(\bigcup_{j=1}^n C_{ij}\right)\cup\left(\bigcup_{k=1}^{r_j} D_{ik}\right)
\qquad(D_{ik}\in\mathscr{S})
$$
$$
B_j = \left(\bigcup_{j=1}^m C_{ij}\right)\cup\left(\bigcup_{l=1}^{s_j} E_{jl}\right)
\qquad(E_{jl}\in\mathscr{S}).
$$
It follows from this that $A\cap B$ and $A\bigtriangleup B$ have the expansions
$$
A\cap B = \bigcup_{i,j} C_{ij},
$$
$$
A\bigtriangleup B = \left(\bigcup_{i,k}D_{ik}\right)\cup\left(\bigcup_{j,l}E_{jl}\right),
$$
and hence belong to $\mathscr{Z}$. Therefore $\mathscr{Z}$ is a ring. The fact that
$\mathscr{Z}$ is a minimal ring generated by $\mathscr{S}$ is obvious.
■
Definition 3
A ring of sets is called a $\sigma$-ring if it contains the union
$$
S = \bigcup_{n=1}^\infty A_n
$$
whenever it contains the sets $A_1,A_2,\ldots,A_n,\ldots$. 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
$$
S = \bigcap_{n=1}^\infty A_n
$$
whenever it contains the sets $A_1,A_2,\ldots,A_n,\ldots$. A $\delta$-ring with a unit $E$ is
called a $\delta$-algebra.
Theorem 4
Every $\sigma$-algebra is a $\delta$-algebra and conversely.
Proof.
An immediate consequence of the "dual" formulas
$$
\bigcup_n A_n = E - \bigcap_n(E - A_n)
$$
$$
\bigcap_n A_n = E - \bigcup_n(E - A_n).
$$
■
The term Borel algebra, or B-algebra, is often used to denote a $\sigma$-algebra.
Theorem 5
Given a nonempty system of sets $\mathscr{S}$, there is a unique, irreducible
B-algebra $\mathscr{B}(\mathscr{S})$ containing $\mathscr{S}$ and contained in every
B-algebra containing $\mathscr{S}$.
Proof.
The proof is virtually identical to the proof 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}$.
■
Adding some more concise definitions that we will use.
Definition - $\sigma$-ring.
A nonempty family of sets $\Sigma$ is a $\sigma$-ring, if
$\bullet$ It contains the empty set. $\emptyset\in\Sigma$.
$\bullet$ It is closed under set difference. $A,B\in\Sigma\;\Longrightarrow\; A-B\in\Sigma$
$\bullet$ It is closed under countable unions;
$$
A_n\in\Sigma\forall n\in\N \;\Longrightarrow\;
\bigcup_{n}A_n\in \Sigma
$$
Source
Definition - Ring.
A nonempty family of sets $\mathcal{R}$ is a ring, if
$\bullet$ It contains the empty set. $\emptyset\in\mathcal{R}$.
$\bullet$ It is closed under set difference. $A,B\in\mathcal{R}\;\Longrightarrow\; A-B\in\mathcal{R}$
$\bullet$ It is closed under union. $A,B\in\mathcal{R}\;\Longrightarrow\; A\cup B\in\mathcal{R}$
If the ring contains a unit set, i.e. a set that contains all other sets, defined as $E\cap A = A$
for all $A\in\mathcal{R}$, then it is called an
algebra.
Source
Theorem - Functions.
Results from section 1.1, repeated here.
$$
f^{-1}\left(\bigcup_\alpha A_\alpha\right) = \bigcup_\alpha f^{-1}(A_\alpha)
$$
$$
f^{-1}\left(\bigcap_\alpha A_\alpha\right) = \bigcap_\alpha f^{-1}(A_\alpha)
$$
$$
f\left(\bigcup_\alpha A_\alpha\right) = \bigcup_\alpha f(A_\alpha)
$$
Functions don't retain intersections.
Problem 1
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?
Proof.
We need to verify the properties of a $\sigma$-ring. Since $\emptyset$ is finite,
then $\emptyset\in\mathscr{R}$ since it contains all finite sets.
For any $A, B\in\mathscr{R}$ we must check if their difference is in $\mathscr{R}$.
If the difference is an infinite set, a finite set or the empty set, then in every case
$A-B\in\mathscr{R}$.
The countable union of the sets $A_1, A_2, \ldots$ is either finite or infinite. In either case
it is contained in $\mathscr{R}$. Since all properties are verified to be true, $\mathscr{R}$
is a $\sigma$-ring.
■
Problem 2
Are open intervals Borel sets?
As noted in the remark, the borel sets are the sets belonging to the minimal B-algebra
on the real line generated by the set of all closed intervals $[a, b]$.
Proof.
The B-algebra $\mathscr{B}$ on the real line is generated by $\mathscr{S} = \{[a,b]\,|\,a,b\in\R\}$.
Since the B-algebra is closed under countable unions, for any $c,d\in\R$ we can take
the union
$$
\bigcup_{n=1}^\infty\big[c + \frac{1}{n}, d - \frac{1}{n}\big] = (c, d)
$$
as shown in Problem 7 in section 1.1. Since all closed sets are included in $\mathscr{B}$,
and since it is a B-algebra, so is the countable union of closed sets. Hence $(c,d)\in\mathscr{B}$.
This is true for any open interval. In conclusion, open sets are Borel sets.
■
Problem 3
Let $y=f(x)$ be a function defined on a set $M$ and taking values in a set $N$, $f:M\rightarrow N$
and $f^{-1}: N\rightarrow M$.
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)$ for $B\in\mathscr{N}$. Prove
the following results.
(a) If $\mathscr{N}$ is a ring, so is $f^{-1}(\mathscr{N})$.
Proof.
We must verify the three properties that define a ring. First that it contains the empty set:
$$
\emptyset\in\mathscr{N}
\;\Longrightarrow\;
f^{-1}(\emptyset) = \emptyset\in f^{-1}(\mathscr{N}).
$$
Verifying closure under set difference:
$$
f^{-1}(A), f^{-1}(B)\in f^{-1}(\mathscr{N})
\;\Longrightarrow\;
A,B\in\mathscr{N}
\;\Longrightarrow\;
A-B \in\mathscr{N}
\;\Longrightarrow\;
f^{-1}(A-B)\in f^{-1}(\mathscr{N})
$$
The preimage of the set difference equals the set difference of the preimages.
$$
f^{-1}(A-B)\in f^{-1}(\mathscr{N})
\;\Longrightarrow\;
f^{-1}(A) - f^{-1}(B)\in f^{-1}(\mathscr{N})
$$
Finally, we need to verify that the set is closed under union.
$$
f^{-1}(A), f^{-1}(B)\in f^{-1}(\mathscr{N})
\;\Longrightarrow\;
A,B\in\mathscr{N}
\;\Longrightarrow\;
A\cup B \in\mathscr{N}
\;\Longrightarrow\;
f^{-1}(A\cup B)\in f^{-1}(\mathscr{N})
$$
The preimage of the union equals the union of the preimages.
$$
f^{-1}(A\cup B)\in f^{-1}(\mathscr{N})
\;\Longrightarrow\;
f^{-1}(A) \cup f^{-1}(B) \in f^{-1}(\mathscr{N})
$$
All properties verified, so we can conclude that when $\mathscr{N}$ is a ring, then
$f^{-1}(\mathscr{N})$ is a ring.
■
(b) If $\mathscr{N}$ is an algebra, so is $f^{-1}(\mathscr{N})$.
Proof.
An algebra is a ring that contains a unit set $E$, i.e. a set that contains all other sets.
This does not change the result from (a), so by the same argument,
if $\mathscr{N}$ is an algebra then $f^{-1}(\mathscr{N})$
is an algebra.
■
(c) If $\mathscr{N}$ is a B-algebra, so is $f^{-1}(\mathscr{N})$.
Proof.
We need to verify the three properties of B-algebras. The first two are exactly the same
as for rings: containment of the empty set and closure under set difference, which are
verified above.
$$
f^{-1}(\emptyset) = \emptyset\in f^{-1}(\mathscr{N}).
$$
$$
f^{-1}(A), f^{-1}(B)\in f^{-1}(\mathscr{N})
\;\Longrightarrow\;
f^{-1}(A) - f^{-1}(B)\in f^{-1}(\mathscr{N})
$$
We must also verify the third property, closure under countable unions.
Assume we have the following sets:
$$
f^{-1}(A_1), f^{-1}(A_2),\ldots \in f^{-1}(\mathscr{N}).
$$
They are sets in $\mathscr{N}$ which is closed under countable unions since it is a B-algebra.
$$
A_1, A_2,\ldots \in \mathscr{N}
\;\Longrightarrow\;
\bigcup_{n=1}^\infty A_n \in \mathscr{N}.
$$
If we take the inverse of this set, we can distribute the inverse to the individual sets,
as mentioned in the 'Functions' theorem.
$$
f^{-1}\left(\bigcup_{n=1}^\infty A_n\right)\in f^{-1}(\mathscr{N})
\;\Longrightarrow\;
\bigcup_{n=1}^\infty f^{-1}(A_n) \in f^{-1}(\mathscr{N}).
$$
This shows that we have closure under countable unions. So we can conclude that if
$\mathscr{N}$ is a B-algebra, so is $f^{-1}(\mathscr{N})$.
■
(d) $\mathscr{R}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{R(\mathscr{N})})$
Proof.
First observe that we have a ring on the left, and by part (a), we have a ring on the
right. We need to show that these rings are the same.
Any set $f^{-1}(A)\in f^{-1}(\mathscr{N})$ will be included in both sides. So we must check
that the sets generated by other sets are included in both sides.
First the empty set.
For any $f^{-1}(A)\in f^{-1}(\mathscr{N})$, the set difference is included in the ring,
so $f^{-1}(A) - f^{-1}(A) = \emptyset$, so $\emptyset\in \mathscr{R}(f^{-1}(\mathscr{N}))$.
For some $A\in\mathscr{N}$, $A-A = \emptyset\in\mathscr{R}(\mathscr{N})$, and it follows that
$f^{-1}(\emptyset) = \emptyset \in f^{-1}(\mathscr{R(\mathscr{N})})$, so both sides contain the
empty set.
Next we check that the rings contain the same generated sets. Starting with sets generated by
set difference.
Assume that $C\in\mathscr{R}(f^{-1}(\mathscr{N}))$.
Assume further that $C\not\in f^{-1}(\mathscr{N})$ and that $C = f^{-1}(A) - f^{-1}(B)$ for some $f^{-1}(A), f^{-1}(B)\in f^{-1}(\mathscr{N})$.
It follows that $A, B\in \mathscr{N}$. When we generate the ring $\mathscr{R}(\mathscr{N})$,
this ring will be closed under set difference, so $A-B\in \mathscr{R}(\mathscr{N})$. When taking
the preimage of this we get:
$$
f^{-1}(A-B)\in f^{-1}(\mathscr{R}(\mathscr{N}))
\;\Longrightarrow\;
f^{-1}(A) - f^{-1}(B)\in f^{-1}(\mathscr{R}(\mathscr{N}))
\;\Longrightarrow\;
C\in f^{-1}(\mathscr{R}(\mathscr{N})).
$$
By the same argument in reverse, we find that $C\in f^{-1}(\mathscr{R}(\mathscr{N}))$ ultimately
leads to $C\in\mathscr{R}(f^{-1}(\mathscr{N}))$ which shows that both sides generate the same
sets with the set difference operator.
Finally, we check that they generate the same sets with the union operator.
Assume that $C\in\mathscr{R}(f^{-1}(\mathscr{N}))$.
Assume further that $C\not\in f^{-1}(\mathscr{N})$ and that $C = f^{-1}(A) \cup f^{-1}(B)$ for some $f^{-1}(A), f^{-1}(B)\in f^{-1}(\mathscr{N})$.
It follows that $A, B\in \mathscr{N}$. When we generate the ring $\mathscr{R}(\mathscr{N})$,
this ring will be closed under unions, so $A\cup B\in \mathscr{R}(\mathscr{N})$. When taking
the preimage of this we get:
$$
f^{-1}(A\cup B)\in f^{-1}(\mathscr{R}(\mathscr{N}))
\;\Longrightarrow\;
f^{-1}(A) \cup f^{-1}(B)\in f^{-1}(\mathscr{R}(\mathscr{N}))
\;\Longrightarrow\;
C\in f^{-1}(\mathscr{R}(\mathscr{N})).
$$
And again, basically the same argument holds in reverse. In conclusion, both sides generate the
same sets and are therefore the same rings.
■
(e) $\mathscr{B}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{B(\mathscr{N})})$
Proof.
Using the same argument as in (d). The arguments for the empty set and closure under
set differences is exactly the same. We just need to extend the closure under union to coutably
many sets.
Assume that $C\in\mathscr{R}(f^{-1}(\mathscr{N}))$.
Assume further that $C\not\in f^{-1}(\mathscr{N})$ and that $C = \bigcup_{n=1}^\infty f^{-1}(A_n)$
for some $f^{-1}(A_n)\in f^{-1}(\mathscr{N})$ for $n\in\N$.
It follows that $A_n\in \mathscr{N}$ for $n\in\N$. When we generate the ring $\mathscr{R}(\mathscr{N})$,
this ring will be closed under countable unions, so $\bigcup_{n=1}^\infty A_n \in \mathscr{R}(\mathscr{N})$.
When taking the preimage of this we get:
$$
f^{-1}\left(\bigcup_{n=1}^\infty A_n\right)\in f^{-1}(\mathscr{R}(\mathscr{N}))
\;\Longrightarrow\;
\bigcup_{n=1}^\infty f^{-1}(A_n)\in f^{-1}(\mathscr{R}(\mathscr{N}))
\;\Longrightarrow\;
C\in f^{-1}(\mathscr{R}(\mathscr{N})).
$$
Again, the same argument goes in reverse, showing that
$\mathscr{B}(f^{-1}(\mathscr{N})) = f^{-1}(\mathscr{B(\mathscr{N})})$.
■
Which of the statements are true if we replace $\mathscr{N}$ with $\mathscr{M}$ and $f^{-1}$ with
$f$?
The statements (a), (b), (c) all become false for the same reason. Since $f(A\cap B)$ does NOT
imply $f(A)\cap f(B)$, closure of set difference is lost.
For the same reason, (d) and (e) also become false, since $f(\mathscr{R(\mathscr{M})})$
is not a ring (and not a B-algebra). $A,B\in\mathscr{R}(\mathscr{M})$ implies that
$A-B\in\mathscr{R}(\mathscr{M})$,
but since the image does not preserve intersections, and by extension set differences,
$f(A), f(B)\in f(\mathscr{R}(\mathscr{M}))$ no longer implies that $f(A)-f(B)\in f(\mathscr{R}(\mathscr{M}))$ and so
it is not a ring.
So in general, all statements become false.