# union of sets disjoint sets is equal to the union set difference

Let $A_1,A_2,\ldots$ be a sequence of subsets of $\mathcal{X}$. Let $B_1=A_1$ and define $$B_n=A_n\setminus \bigcup_{i=1}^{n-1}A_i \text{ for } n=2,3,\ldots$$

Show that $$\bigcup_{i=1}^n B_i = \bigcup_{i=1}^n A_i \text{ for all } n\in\mathbb{N}$$

I can see why this is, intuitively, but I can't figure out how to construct a formal proof.

I can see that $\bigcup_{i=1}^n B_i\subset \bigcup_{i=1}^n A_i$, but how do I show the opposite?

## 4 Answers

HINT: If $x\in\bigcup A_i$, let $k$ be the least such that $x\in A_k$, show that $x\in B_k$. Finish the proof.

• $x\in \bigcup_{i=1}^n A_i$. Let $k$ be the least index for which $x\in A_k$. Then $x\in A_k\setminus\bigcup_{i=1}^{k-1}A_i\Rightarrow x\in\bigcup_{i=1}^k B_k$. But does this imply that $\bigcup_{i=1}^n A_n \subset \bigcup_{i=1}^n B_n$? – Rud Faden Nov 16 '14 at 20:06
• It means that $x\in B_k$ and therefore $x\in\bigcup B_i$. Therefore $\bigcup A_i\subseteq\bigcup B_i$, which is what you are asked for, no? – Asaf Karagila Nov 16 '14 at 20:08
• Yes. I just wanted to be sure. Thanks – Rud Faden Nov 16 '14 at 20:10
• Would this also work for infinite unions? E.i. $\bigcup_{i=1}^\infty B_n = \bigcup_{i=1}^\infty A_n$ – Rud Faden Nov 16 '14 at 20:15
• Sure, if the index set is well-ordered (and in this case, the index set is $\Bbb N$) then we can make this argument. Note that from the axiom of choice we can always well-order the index set (although we might lose some of the natural properties of the index set, if we care for them). – Asaf Karagila Nov 16 '14 at 20:20

Suppose $x \in \bigcup_{i=1}^n A_i$. Then there is at least one $n\in\{1,2,3,\ldots\}$ for which $x\in A_n$. Let $n\in\{1,2,3,\ldots\}$ be the smallest index for which $x\in A_n$. Then $x\in A_n\smallsetminus\bigcup_{i=1}^{n-1} A_i=B_n$. Hence $x\in\bigcup_{n=1}^\infty B_n$.

Conversely, suppose $x\in\bigcup_{n=1}^\infty B_n$. Then $\exists n\ x\in (A_n\smallsetminus\text{something})$, so $x\in A_n$; hence $x\in\text{their union}$.

Hint: Suppose $x \in \cup_{i=1}^n A_i$. Consider the first index $j$ such that $x \in A_j$ (there is at least one, so there is a minimal one...).

Let $x\in\bigcup_{i=1}^nA_i$.

Find the smallest index $k\in\{1,\dots,n\}$ with $x\in A_k$.

Then $x\in B_k\subseteq\bigcup_{i=1}^nB_i$