Ring of Sets Generated by Semiring

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\SS$ be a semiring of sets.

Let $\map \RR \SS$ be the minimal ring generated by $\SS$.

Let $\LL$ be the system of sets $A$ with the finite expansions:

$\ds A = \bigcup_{k \mathop = 1}^n A_k$

with respect to the sets $A_k \in \SS$.


Then $\LL = \map \RR \SS$.


Proof

First we need to show that $\LL$ is a ring of sets.

Let $A, B \in \LL$.

Then by definition of $\LL$, they have expansions:

\(\ds A\) \(=\) \(\ds \bigcup_{i \mathop = 1}^m A_i\) where $A_i \in \SS$
\(\ds B\) \(=\) \(\ds \bigcup_{j \mathop = 1}^n B_j\) where $B_j \in \SS$


Since $\SS$ is a semiring of sets, we have:

$C_{ij} = A_i \cap B_j \in \SS$


By Pairwise Disjoint Subsets in Semiring Part of Partition, there exist finite expansions:

\(\ds A_i\) \(=\) \(\ds \paren {\bigcup_{j \mathop = 1}^n C_{i j} } \cup \paren {\bigcup_{k \mathop = 1}^{r_i} D_{i k} }\) where $D_{i k} \in \SS$
\(\ds B_j\) \(=\) \(\ds \paren {\bigcup_{i \mathop = 1}^m C_{i j} } \cup \paren {\bigcup_{l \mathop = 1}^{s_j} E_{j l} }\) where $E_{j l} \in \SS$


From these, it follows that $A \cap B$ and $A \ast B$ have the finite expansions:

\(\ds A \cap B\) \(=\) \(\ds \bigcup_{i, \ j} C_{i j}\)
\(\ds A \ast B\) \(=\) \(\ds \paren {\bigcup_{i, \ k} D_{i k} } \cup \paren {\bigcup_{j, \ l} E_{j l} }\)


Hence both $A \cap B \in \LL$ and $A \ast B \in \LL$.

So by definition, $\LL$ is a ring of sets.


From the details of the above construction, the fact that $\LL$ is the minimal ring generated by $\SS$ follows immediately.

$\blacksquare$