Equivalence of Definitions of Semiring of Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

The following definitions of the concept of Semiring of Sets are equivalent:

Definition 1

Let $\SS$ be a system of sets.


$\SS$ is a semiring of sets or semi-ring of sets if and only if $\SS$ satisfies the semiring of sets axioms:

\((1)\)   $:$   \(\ds \O \in \SS \)      
\((2)\)   $:$   $\cap$-stable      \(\ds \forall A, B \in \SS:\) \(\ds A \cap B \in \SS \)      
\((3)\)   $:$     \(\ds \forall A, A_1 \in \SS : A_1 \subseteq A:\) $\exists n \in \N$ and pairwise disjoint sets $A_2, A_3, \ldots, A_n \in \SS : \ds A = \bigcup_{k \mathop = 1}^n A_k$      


Definition 2

Let $\SS$ be a system of sets.


$\SS$ is a semiring of sets or semi-ring of sets if and only if $\SS$ satisfies the semiring of sets axioms:

\((1)\)   $:$   \(\ds \O \in \SS \)      
\((2)\)   $:$   $\cap$-stable      \(\ds \forall A, B \in \SS:\) \(\ds A \cap B \in \SS \)      
\((3')\)   $:$     \(\ds \forall A, B \in \SS:\) $\exists n \in \N$ and pairwise disjoint sets $A_1, A_2, A_3, \ldots, A_n \in \SS : \ds A \setminus B = \bigcup_{k \mathop = 1}^n A_k$      


Proof

Definition 1 implies Definition 2

Let $\SS$ be a system of sets satisfying the axioms:

\((1)\)   $:$   \(\ds \O \in \SS \)      
\((2)\)   $:$   $\cap$-stable      \(\ds \forall A, B \in \SS:\) \(\ds A \cap B \in \SS \)      
\((3)\)   $:$     \(\ds \forall A, A_1 \in \SS : A_1 \subseteq A:\) $\exists n \in \N$ and pairwise disjoint sets $A_2, A_3, \ldots, A_n \in \SS : \ds A = \bigcup_{k \mathop = 1}^n A_k$      


It remains to be shown that $\SS$ satisfies the axiom

\((3')\)   $:$     \(\ds \forall A, B \in \SS:\) $\exists n \in \N$ and pairwise disjoint sets $A_1, A_2, A_3, \ldots, A_n \in \SS : \ds A \setminus B = \bigcup_{k \mathop = 1}^n A_k$      


Let $A, B \in \SS$.

Let $A_1 = A \cap B$.

By axiom $(2)$:

$A_1 \in \SS$

From Intersection is Subset:

$A_1 \subseteq A$

By axiom $(3)$:

$\exists$ a finite sequence of pairwise disjoint sets $A_2, A_3, \ldots, A_n \in \SS : \ds A = \bigcup_{k \mathop = 1}^n A_k$


Then:

\(\ds A \setminus B\) \(=\) \(\ds A \setminus \paren {A \cap B}\) Set Difference with Intersection is Difference
\(\ds \) \(=\) \(\ds A \setminus A_1\)
\(\ds \) \(=\) \(\ds \paren {\bigcup_{k \mathop = 1}^n A_k} \setminus A_1\)
\(\ds \) \(=\) \(\ds \bigcup_{k \mathop = 1}^n \paren {A_k \setminus A_1}\) Set Difference is Right Distributive over Union
\(\ds \) \(=\) \(\ds \bigcup_{k \mathop = 2}^n \paren {A_k \setminus A_1}\) Set Difference with Self is Empty Set and Union with Empty Set
\(\ds \) \(=\) \(\ds \bigcup_{k \mathop = 2}^n A_k\) Set Difference with Disjoint Set


As $A$ and $B$ were arbitrary, then $\SS$ satisfies axiom $(3')$

The result follows

$\Box$

Definition 2 implies Definition 1

Let $\SS$ be a system of sets satisfying the axioms:

\((1)\)   $:$   \(\ds \O \in \SS \)      
\((2)\)   $:$   $\cap$-stable      \(\ds \forall A, B \in \SS:\) \(\ds A \cap B \in \SS \)      
\((3')\)   $:$     \(\ds \forall A, B \in \SS:\) $\exists n \in \N$ and pairwise disjoint sets $A_1, A_2, A_3, \ldots, A_n \in \SS : \ds A \setminus B = \bigcup_{k \mathop = 1}^n A_k$      


It remains to be shown that $\SS$ satisfies the axiom

\((3)\)   $:$     \(\ds \forall A, A_1 \in \SS : A_1 \subseteq A:\) $\exists n \in \N$ and pairwise disjoint sets $A_2, A_3, \ldots, A_n \in \SS : \ds A = \bigcup_{k \mathop = 1}^n A_k$      


Let $A, B \in \SS : B \subseteq A$.

By axiom $(3)$:

$\exists$ a finite sequence of pairwise disjoint sets $A_1, A_2, \ldots, A_n \in \SS : \ds A \setminus B = \bigcup_{k \mathop = 1}^n A_k$.

Then $B$ is disjoint with each of the sets $A_k$.

Then:

\(\ds B \cup \bigcup_{k \mathop = 1}^n A_k\) \(=\) \(\ds \paren {A \setminus B} \cup B\)
\(\ds \) \(=\) \(\ds A \cup B\) Set Difference Union Second Set is Union
\(\ds \) \(=\) \(\ds A\) Union with Superset is Superset

As $A$ and $B$ were arbitrary, then $\SS$ satisfies axiom $(3)$

The result follows

$\blacksquare$