10
$\begingroup$

Let $X$ be a nonempty set. A collection $S$ of subsets of $X$ is called a semiring if it satisfies the following properties:

  1. The empty set belongs to S; that is $\emptyset \in S$.
  2. If $A,B \in S$; then $A \cap B \in S$; that is, $S$ is closed under finite intersections.
  3. The set difference of any two sets of $S$ can be written as a finite union of pair-wise disjoint members of $S$. That is, for every $A, B \in S$; there exist $C_1, ...,C_n \in S$ (depending on $A$ and $B$) such that $A\setminus B = \cup _{i=1}^n C_i$ and $C_i \cap C_j = \emptyset$ if $i\ne j$.

Now, let $S$ be a semiring of subsets of $X$. A subset $A$ of $X$ is called a $\sigma$-set with respect to $S$ (or simply a $\sigma$-set) if there exists a disjoint sequence $\{A_n\}$ of $S$ such that $A = \cup_{n=1}^\infty A_n$. One can show easily that for every sequence $\{A_n\}$ of $S$, the set $A = \cup_{n=1}^\infty A_n$ is a $\sigma$-set.

I would like to prove that finite intersections of $\sigma$-sets is a $\sigma$-set. For this purpose, suppose $A ,B$ are $\sigma$-sets then $A = \cup_{i=1}^\infty C_i$ , $B = \cup_{j=1}^\infty D_j$.

$$A\cap B=(\cup_{i=1}^\infty C_i)\cap (\cup_{j=1}^\infty D_j)$$

In this step I don't know am I allowed to use distributive law for infinitely many sets? Or the law holds only for finitely many sets?

If it holds only for finitely many sets how do I prove that finite intersections of $\sigma$-sets is a $\sigma$-set?

Thanks.

$\endgroup$
3
  • $\begingroup$ That doesn't sound much like what a semiring usually means. Is there a connection? $\endgroup$ – hmakholm left over Monica Aug 31 '13 at 16:52
  • 2
    $\begingroup$ Well, it wouldn't be the first time that the word "ring" got used for something setty instead of something algebraic. $\endgroup$ – Ben Millwood Aug 31 '13 at 17:09
  • 1
    $\begingroup$ @Henning: Skip down in that article to here, and you’ll find exactly this definition of a semiring of sets. $\endgroup$ – Brian M. Scott Sep 1 '13 at 3:26
11
$\begingroup$

Yes, both distributive laws generalize. (You need only one of the two, but it’s useful to know both.) The first step in verifying the generalization that you want is to check that

$$\left(\bigcup_{i\in I}A_i\right)\cap D=\bigcup_{i\in I}(A_i\cap D)\;,\tag{1}$$

and to verify its mate you’ll want to check that

$$\left(\bigcap_{i\in I}A_i\right)\cup D=\bigcap_{i\in I}(A_i\cup D)\;.\tag{2}$$

Both are easily verified by element-chasing. For $(1)$, if $x\in\left(\bigcup_{i\in I}A_k\right)\cap D$, then $x\in\bigcup_{i\in I}A_i$ and $x\in D$. Since $x\in\bigcup_{i\in I}A_i$, there is an $i_0\in I$ such that $x\in A_{i_0}$, and therefore $x\in A_{i_0}\cap D\subseteq\bigcup_{i\in I}(A_i\cap D)$. Conversely, if $x\in\bigcup_{i\in I}(A_i\cap D)$, then there is an $i_0\in I$ such that $x\in A_{i_0}\cap D$. Then $x\in A_{i_0}\subseteq\bigcup_{i\in I}A_i$, and $x\in D$, so $x\in\left(\bigcup_{i\in I}A_i\right)\cap D$.

For $(2)$, if $x\in\left(\bigcap_{i\in I}A_i\right)\cup D$, then $x\in\bigcap_{i\in I}A_i$ or $x\in D$. Let $i_0\in I$ be arbitrary. Then $A_{i_0}\supseteq\bigcap_{i\in I}A_i$, so $x\in A_{i_0}$ or $x\in D$, and therefoer $x\in A_{i_0}\cup D$. Since this holds for each $i_0\in I$, $x\in\bigcap_{i\in I}(A_i\cup D)$. Conversely, if $x\in\bigcap_{i\in I}(A_i\cup D)$, then $x\in A_i\cup D$ for each $i\in I$. If $x\in D$, then certainly $x\in\left(\bigcap_{i\in I}A_i\right)\cup D$. If $x\notin D$, then we must have $x\in A_i$ for each $i\in I$, in which case $x\in\bigcap_{i\in I}A_i\subseteq\left(\bigcap_{i\in I}A_i\right)\cup D$.

Two applications of $(1)$ will give you the distributive law that you want. Suppose that $C=\bigcup_{i\in I}A_i$ and $D=\bigcup_{j\in J}B_j$. Then

$$\begin{align*} C\cap D&=\left(\bigcup_{i\in I}A_i\right)\cap D\\ &=\bigcup_{i\in I}(A_i\cap D)\\ &=\bigcup_{i\in I}\left(A_i\cap\bigcup_{j\in J}B_j\right)\\ &=\bigcup_{i\in I}\left(\bigcup_{j\in J}(A_i\cap B_j)\right)\\ &=\bigcup_{\langle i,j\rangle\in I\times J}(A_i\cap B_j)\;. \end{align*}$$

In other words, $C\cap D$ is the union of all possible intersections of the form $A_i\cap B_j$. In particular, if $I$ and $J$ are countable index sets, $I\times J$ is also countable.

Similarly, two applications of $(2)$ will give you the other general distributive law of this kind. This time suppose that $C=\bigcap_{i\in I}A_i$ and $D=\bigcap_{j\in J}B_j$. Then

$$\begin{align*} C\cup D&=\left(\bigcap_{i\in I}A_i\right)\cup D\\ &=\bigcap_{i\in I}(A_i\cup D)\\ &=\bigcap_{i\in I}\left(A_i\cup\bigcap_{j\in J}B_j\right)\\ &=\bigcap_{i\in I}\left(\bigcap_{j\in J}(A_i\cup B_j)\right)\\ &=\bigcap_{\langle i,j\rangle\in I\times J}(A_i\cup B_j)\; \end{align*}$$

the intersection of all possible unions of the form $A_i\cup B_j$ as $i$ and $j$ run over their respective index sets.

$\endgroup$
1
  • 2
    $\begingroup$ "[...] element-chasing". What a lovely piece of terminology. It told me exactly how to carry out the proof with no need for explanation or formalization (I supplied the formality myself). $\endgroup$ – Jonas Kölker Mar 24 '19 at 7:42
3
$\begingroup$

Two sets $X$ and $Y$ are equal exactly when, for all $x$, $x \in X \iff x \in Y$.

Now, take $x \in (\cup_i C_i) \cap (\cup_j C_j)$.

This means precisely that $x$ is in $\cup_i C_i$ and also is in $\cup_j D_j$.

A statement of the form $x \in \cup_k S_k$ means precisely "there exists some $k$ such that $x \in S_k$". So we have from $x \in \cup_i C_i$ and $x \in \cup_j D_j$ that there exist $i$ and $j$ such that $x \in C_i$ and $x \in D_j$.

Or in other words, there exist $i$ and $j$ such that $x \in C_i \cap D_j$.

Or in other words, $x \in \cup_i \cup_j (C_i \cap D_j)$.

So, yes, the distributive law works for infinite, even uncountable families of sets.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.