# Use elementary set operations to show sequence of sets is disjoint

Let $\{A_n\}_{n=1}^\infty$ be an arbitrary sequence of sets. Construct from it a new sequence $\{B_n\}_{n=1}^\infty$ defined by $B_1=A_1$ and for $n>1$, we let $B_n=A_n\smallsetminus \left(\bigcup_{k=1}^{n-1}A_k\right)$. I want to show the $B_n$ are pairwise disjoint. That is, for any $i \ne j$, without loss of generality $i>j$, \begin{align*} B_i\cap B_j &=\left(A_i \smallsetminus \bigcup_{n=1}^{i-1} A_n\right)\cap \left(A_j\smallsetminus \bigcup_{n=1}^{j-1} A_n\right) \\ &=\left(\bigcap_{n=1}^{i-1}(A_i \smallsetminus A_n)\right) \cap \left(\bigcap_{n=1}^{j-1}(A_j\smallsetminus A_n)\right) \\ &=\bigcap_{n=1}^{j-1} \left((A_i \smallsetminus A_n) \cup (A_j \smallsetminus A_n)\right) \cap \bigcap_{n=j}^{i-1} (A_i \smallsetminus A_n) \\ &=\bigcap_{n=1}^{j-1} \left((A_i \cup A_j) \smallsetminus A_n\right) \cap \bigcap_{n=j}^{i-1} (A_i \smallsetminus A_n) \\ &=\cdots \\ &=\emptyset \end{align*} It's easy enough to argue in words that this intersection must equal the empty set:

For any $x$ in $\left(A_i \smallsetminus \bigcup_{n=1}^{i-1} A_n\right)\cap \left(A_j\smallsetminus \bigcup_{n=1}^{j-1} A_n\right)$, we would have $x \in A_i$ and $x \in A_j$, but $x \notin \bigcup_{n=1}^{i=1} A_n$ and $x \notin \bigcup_{n=1}^{j-1} A_n$, i.e. $x \notin A_n$, $n=1,\ldots,i-1$ and $x \notin A_n$, $n=1,\ldots,j-1$. Since $i>j$, the last statement is redundant. Thus $x \in A_i$ and $x \in A_j$, but $x \notin A_n$, $i=1,\ldots,i-1$. But since $j<i$, the statement $i=1,\ldots,i-1$ implies $x \notin A_j$, which is a contradiction.

However I don't want to prove this in a paragraph of words -- I want to show algebraically that the intersection must equal the empty set using basic set operations (properties of the set difference, unions and intersections, etc.) to manipulate the above equations. But I get stuck along the way and it's not obvious what rules I should use next to manipulate the above equations. Anyone see any neat tricks to use? Thanks!

## 2 Answers

It is proved like: \begin{align} B_i\cap B_j &=\left(A_i -\bigcup_{n=1}^{i-1} A_n\right)\cap \left(A_j-\bigcup_{n=1}^{j-1} A_n\right) \\ &=\left(A_i \cap \bigcap_{n=1}^{i-1}A_n^c\right) \cap \left(A_j\cap\bigcap_{n=1}^{j-1} A_n^c\right) \\ &=\left(A_i \cap \left(\bigcap_{n=1}^{i-1}A_n^c\right)\cap A_j\right) \cap \left(\bigcap_{n=1}^{j-1} A_n^c\right)\tag1 \\ &=\left(A_i \cap \left(\left(\bigcap_{n=1, n\ne j}^{i-1}A_n^c\right)\cap A_j^c\right)\cap A_j\right) \cap \left(\bigcap_{n=1}^{j-1} A_n^c\right)\tag2 \\ &=\left(A_i \cap \left(\bigcap_{n=1, n\ne j}^{i-1}A_n^c\right)\cap (A_j^c\cap A_j)\right) \cap \left(\bigcap_{n=1}^{j-1} A_n^c\right)\tag3 \\ &=\left(A_i \cap \left(\bigcap_{n=1, n\ne j}^{i-1}A_n^c\right)\cap \varnothing\right) \cap \left(\bigcap_{n=1}^{j-1} A_n^c\right) \\ &=\left(A_i \cap \varnothing\right) \cap \left(\bigcap_{n=1}^{j-1} A_n^c\right) \\ &= \varnothing \cap \left(\bigcap_{n=1}^{j-1} A_n^c\right) \\ &=\varnothing \end{align} $(1)$ is because intersection is associative.

$(2):$ $A_j^c$ can be moved out of $\bigcap_{n=1}^{i-1}A_n^c$ because intersection is commutative and associative, as well as $i>j$.

$(3)$ is because intersection is associative.

• This is exactly what I was looking for. Many thanks! – Mathemanic Nov 27 '16 at 5:46

If $i>j$ then $$B_j=A_j\mathbin\backslash\bigcup_{k=1}^{j-1}A_k =A_j\cap A_{j-1}^c\cap A_{j-2}^c\cap\cdots\cap A_1^c$$ and similarly $$B_i=A_i\cap A_{i-1}^c\cap A_{i-2}^c\cap\cdots\cap A_j^c\cap\cdots\cap A_1^c\ .$$ By commutativity and associativity of intersection, \eqalign{B_i\cap B_j &=A_i\cap A_{i-1}^c\cap A_{i-2}^c\cap\cdots\cap (A_j\cap A_j^c)\cap \cdots\cap (A_1^c\cap A_1^c)\cr &=\cdots\cap\varnothing\cap\cdots\cr &=\varnothing\ .\cr}