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:

A collection $\mathcal S$ of subsets of a set $X$ is a semiring (of sets) if and only if:

$(1):\quad \varnothing \in \mathcal S$
$(2):\quad A, B \in \mathcal S \implies A \cap B \in \mathcal S$; i.e., $\mathcal S$ is $\cap$-stable
$(3):\quad$ If $A, A_1 \in \mathcal S$ such that $A_1 \subseteq A$, then there exists a finite sequence $A_2, A_3, \ldots, A_n \in \mathcal S$ such that:
$(3a):\quad \displaystyle A = \bigcup_{k \mathop = 1}^n A_k$
$(3b):\quad$ The $A_k$ are pairwise disjoint

We prove that criterion $(3)$ can be replaced by:

$(3'):\quad$ If $A, B \in \mathcal S$, then there exist finite sequence of pairwise disjoint sets $A_1, A_2, \ldots, A_n \in \mathcal S$ such that $\displaystyle A \setminus B = \bigcup_{k \mathop = 1}^n A_k$.


Proof

$(3)$ implies $(3')$

Let $X$ be a set, and let $\mathcal S$ be a collection of subsets of $X$.


Suppose that for all $A, A_1 \in \mathcal S$ such that $A_1 \subseteq A$, there exists a finite sequence of sets $A_2, A_3, \ldots, A_n \in \mathcal S$ such that:

$A_1, A_2, \ldots, A_n$ are pairwise disjoint
$\displaystyle A = \bigcup_{k \mathop = 1}^n A_k$

Let $B \in \mathcal S$, and let $A_1 = A \cap B$.

It follows that $A_1 \in \mathcal S$, by definition.

Also, $A_1 \subseteq A$ by Intersection is Subset.

Then:

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

as desired.

$\Box$


$(3')$ implies $(3)$

Now suppose that for all $A, B \in \mathcal S$, there exists a finite sequence of pairwise disjoint sets $A_1, A_2, \ldots, A_n \in \mathcal S$ such that $\displaystyle A \setminus B = \bigcup_{k \mathop = 1}^n A_k$.

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

Let $B \subseteq A$. Then:

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

as desired.

$\blacksquare$