Pairwise Disjoint Sets Partition Any Sets in Semiring

Lemma

Let $\mathbb S$ be a semiring of sets.

Let $A_1, A_2, \ldots, A_n$ all belong to $\mathbb S$.

Then there exists a finite system of pairwise disjoint sets:

$B_1, B_2, \ldots, B_t \in \mathbb S$

such that every $A_k$ where $k \in \closedint 1 n$ has a finite expansion:

$\ds A_k = \bigcap_{s \mathop \in M_k} B_s$

where $M_k \subseteq \closedint 1 s$.

That is, the nature of a semiring of sets $\mathbb S$ is such that for every collection $\mathbb T$ of elements of $\mathbb S$, there exists a finite collection of disjoint sets of $\mathbb S$ from which you can pick sets from that will build any of the elements of $\mathbb T$.

Proof

If $n = 1$, the lemma follows trivially from the definition of semiring of sets.

Now we suppose that the lemma holds for $n = m$, and we attempt to show it consequently holds for $n = m + 1$.

We consider a system of sets $A_1, A_2, \ldots, A_m, A_{m + 1}$ in $\mathbb S$.

Let $B_1, B_2, \ldots, B_t \in \mathbb S$ satisfy the terms of the lemma for $A_1, A_2, \ldots, A_m$.

Now let $B_{s 1} = A_{m + 1} \cap B_s$.

By Pairwise Disjoint Subsets in Semiring Part of Partition, there exists an expansion:

$\ds A_{m + 1} = \paren {\bigcup_{s \mathop = 1}^t B_{s 1} } \cup \paren {\bigcup_{p \mathop = 1}^q B_p'}$ where $B_p' \in \mathbb S$.

By definition of a semiring of sets, there is an expansion:

$B_s = B_{s 1} \cup B_{s 2} \cup \cdots \cup B_{s r_s}$ where $B_{s j} \in \mathbb S$.

It can be seen that:

$\ds A_k = \bigcup_{s \mathop \in M_k} \paren {\bigcup_{j \mathop = 1}^{r_s}B_{sj} }$ for $k \in \closedint 1 m$

for some $M_k$.

Also, the sets $B_{s j}, B_p'$ are pairwise disjoint.

So, the sets $B_{s j}, B_p'$ satisfy the conditions of the lemma with respect to the sets $A_1, A_2, \ldots, A_m, A_{m + 1}$.

Hence the result by induction.

$\blacksquare$