Cartesian Product of Semirings of Sets

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\mathcal S$ and $\mathcal T$ be semirings of sets.


Then $\mathcal S \times \mathcal T$ is also a semiring of sets.

Here, $\times$ denotes Cartesian product.


Proof

Recall the conditions for $\mathcal S \times \mathcal T$ to be a semiring of sets:

$(1): \quad \varnothing \in \mathcal S \times \mathcal T$
$(2): \quad \mathcal S \times \mathcal T$ is $\cap$-stable
$(3'):\quad$ If $A, B \in \mathcal S \times \mathcal T$, then there exists a finite sequence of pairwise disjoint sets $A_1, A_2, \ldots, A_n \in \mathcal S \times \mathcal T$ such that $\displaystyle A \setminus B = \bigcup_{k \mathop = 1}^n A_k$.


Proof of $(1)$

From Empty Set is Subset of All Sets:

$\varnothing \in \mathcal S$

and:

$\varnothing \in \mathcal T$

So:

$\varnothing \times \varnothing \in \mathcal S \times \mathcal T$

From Cartesian Product is Empty iff Factor is Empty:

$\varnothing \times \varnothing = \varnothing$

$\Box$


Proof of $(2)$

Let $S_1 \times T_1$ and $S_2 \times T_2$ be in $\mathcal S \times \mathcal T$.

Then from Cartesian Product of Intersections:

$\left({S_1 \times T_1}\right) \cap \left({S_2 \times T_2}\right) = \left({S_1 \cap S_2}\right) \times \left({T_1 \cap T_2}\right)$

Since $\mathcal S$ and $\mathcal T$ are $\cap$-stable, $S_1 \cap S_2 \in \mathcal S$ and $T_1 \cap T_2 \in \mathcal T$.


Hence $\left({S_1 \times T_1}\right) \cap \left({S_2 \times T_2}\right) \in \mathcal S \times \mathcal T$.

$\Box$


Proof of $(3')$

Let $S_1 \times T_1$ and $S_2 \times T_2$ be in $\mathcal S \times \mathcal T$.

Let $\sqcup$ signify union of disjoint sets.


Then:

\(\displaystyle \left({S_1 \times T_1}\right) \setminus \left({S_2 \times T_2}\right)\) \(=\) \(\displaystyle \left({S_1 \times \left({T_1 \setminus T_2}\right)}\right) \cup \left({\left({S_1 \setminus S_2}\right) \times T_1}\right)\) Set Difference of Cartesian Products
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle S_1\) \(=\) \(\displaystyle \left({S_1 \setminus S_2}\right) \sqcup \left({S_1 \cap S_2}\right)\) Set Difference Union Intersection
\(\displaystyle \implies \ \ \) \(\displaystyle S_1 \times \left({T_1 \setminus T_2}\right)\) \(=\) \(\displaystyle \left({S_1 \setminus S_2}\right) \times \left({T_1 \setminus T_2}\right) \ \sqcup \ \left({S_1 \cap S_2}\right) \times \left({T_1 \setminus T_2}\right)\) Cartesian Product Distributes over Union
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle T_1\) \(=\) \(\displaystyle \left({T_1 \cap T_2}\right) \sqcup \left({T_1 \setminus T_2}\right)\) Set Difference Union Intersection
\(\displaystyle \implies \ \ \) \(\displaystyle \left({S_1 \setminus S_2}\right) \times T_2\) \(=\) \(\displaystyle \left({S_1 \setminus S_2}\right) \times \left({T_1 \cap T_2}\right) \ \sqcup \ \left({S_1 \setminus S_2}\right) \times \left({T_1 \setminus T_2}\right)\) Cartesian Product Distributes over Union
\(\displaystyle \) \(\) \(\displaystyle \)
\(\displaystyle \implies \ \ \) \(\displaystyle \left({S_1 \times T_1}\right) \setminus \left({S_2 \times T_2}\right)\) \(=\) \(\displaystyle \left({S_1 \setminus S_2}\right) \times \left({T_1 \setminus T_2}\right) \ \sqcup \ \left({S_1 \cap S_2}\right) \times \left({T_1 \setminus T_2}\right) \ \sqcup \ \left({S_1 \setminus S_2}\right) \times \left({T_1 \cap T_2}\right)\)


Now recall that $\mathcal S$ and $\mathcal T$ are semirings of sets.

Thence the expressions $S_1 \setminus S_2$ and $T_1 \setminus T_2$ may be written as finite disjoint unions.

Applying Cartesian Product Distributes over Union again, each of the three $\sqcup$-operands in the expression above may thus be written as a finite disjoint union.


This yields the same fact for $\left({S_1 \times T_1}\right) \setminus \left({S_2 \times T_2}\right)$ as well, completing the proof.

$\blacksquare$


Sources