Proof: On Semiring $S$ with $A, B_i \in S$ $ \exists$ sets $C_i \in S $ so that $ A\backslash \bigcup_{i=1}^{N} B_i=\bigcup_{i=1}^{M} C_i $

Question

Let $\mathcal S$ be a semiring on the set $X$ and $A, B_1 , \dots , B_N \in \mathcal S$ for a $N \in \Bbb N$.

I have to show the following: There exists a $M \in \Bbb N $ and disjoint sets $C_1 , \dots , C_M \in \mathcal S $ so that $$ A\backslash \bigcup_{i=1}^{N} B_i=\bigcup_{i=1}^{M} C_i $$

I know that from the definition of a Semiring i can write $$A \backslash B_i = \bigcup_{k_i=1}^{M_i} D_{k_i}$$ with $D_{k_i}$ beeing disjoint elements of $\mathcal S$. After rearranging I get:$$A\backslash \bigcup_{i=1}^{N} B_i = \bigcap_{i=1}^NA\backslash B_i=\bigcup_{k_1=1}^{M_1}\bigcup_{k_2=1}^{M_2}\dots\bigcup_{k_N=1}^{M_N} \big[D_{k_1}\cap D_{k_2}\cap \dots \cap D_{k_N} \big]$$

Now I'm stuck. I know that $\big[D_{k_1}\cap D_{k_2}\cap \dots \cap D_{k_N} \big] \in \mathcal S$ but I don't know how to proceed, i.e. how to forge the unions into one.

Any ideas or tipps? Thanks in advance!

Answer 1

It’s easier to write out properly if you index the $D$ sets with double subscripts, so that you can keep track of which $D$s go with which $B$s. I’ll illustrate with $N=2$. You know that there are pairwise disjoint families $\{D_{1,k}:1\le k\le n_1\}$ and $\{D_{2,k}:1\le k\le n_2\}$ such that

$$A\setminus B_1=\bigcup_{k=1}^{n_1}D_{1,k}$$

and

$$A\setminus B_2=\bigcup_{k=1}^{n_2}D_{2,k}\;.$$

Then

$$\begin{align*} A\setminus(B_1\cup B_2)&=(A\setminus B_1)\cap(A\setminus B_2)\\ &=\left(\bigcup_{k=1}^{n_1}D_{1,k}\right)\cap\bigcup_{\ell=1}^{n_2}D_{2,\ell}\\ &=\bigcup_{k=1}^{n_1}\left(D_{1,k}\cap\bigcup_{\ell=1}^{n_2}D_{2,\ell}\right)\\ &=\bigcup_{k=1}^{n_1}\bigcup_{\ell=1}^{n_2}(D_{1,k}\cap D_{2,\ell})\;. \end{align*}$$

You’ve reached this point, but with clumsier notation.

For each $\langle k,\ell\rangle\in\{1,\ldots,n_1\}\times\{1,\ldots,n_2\}$ let $C_{k,\ell}=D_{1,k}\cap D_{2,\ell}$.

Now let $\langle k,\ell\rangle,\langle i,j\rangle\in\{1,\ldots,n_1\}\times\{1,\ldots,n_2\}$;

$$\begin{align*} C_{k,\ell}\cap C_{i,j}&=(D_{1,k}\cap D_{2,\ell})\cap(D_{1,i}\cap D_{2,j})\\ &=(D_{1,k}\cap D_{1,i})\cap(D_{2,\ell}\cap D_{2,j})\;, \end{align*}$$

which is empty unless $k=i$ and $\ell=j$. Thus, the sets $C_{k,\ell}$ are pairwise disjoint, as desired.