# Proof about Sequence of Sets

Problem: Let $$A_1,A_2,...,A_n$$ be sets such that $$X=\bigcup_{i=1}^n A_i$$.
Prove that there exists a sequence of sets $$B_1,B_2,...,B_n$$ such that

a) $$B_i \subseteq A_i$$ for each $$i=1,2,...,n$$

b) $$B_i \cap B_j = \emptyset$$ for $$i \neq j$$

c) $$X=\bigcup_{i=1}^n B_i$$

My observation: I look at the "new things" added to $$X$$ by $$A_i$$ and call that $$B_i$$. For example $$B_1$$ is $$A_1$$, $$B_2$$ is $$A_2\setminus A_1$$ and $$B_3$$ is $$A_3 \setminus A_2 \cup A_1$$. In general, the sequence of sets is defined by this $$B_i=A_i-\bigcup_{k=1}^{i-1} A_k$$ for $$k=1,2,...,n$$.

Proof Attempt:

Proof (a)

Let $$x\in B_i$$. Since $$B_i=A_i\setminus\bigcup_{k=1}^{i-1} A_k$$, so by defnition of Set Difference, if something is in $$B_i$$, it must also be in $$A_i$$. Since, $$x\in B_i$$ implies $$x\in A_i$$, we conclude that $$B_i\subseteq A_i$$ (by definition of Subset).

Proof (b)

On which, I found an elementary approach from here.

Proof (c)

To show that $$X=\bigcup_{i=1}^n B_i$$, we must show that $$X\subseteq\bigcup_{i=1}^n B_i$$ and $$\bigcup_{i=1}^n B_i\subseteq X$$.

Part 1. Show that $$X\subseteq\bigcup_{i=1}^n B_i$$. Let $$x\in X$$ then $$x\in\bigcup_{i=1}^n A_i$$ as defined.It implies that $$x$$ is an element of some $$A_i$$'s (by definition of $$\cup$$).If $$i_0$$ is the least such value of $$i$$ such that $$x\in A_{i_0}$$ then $$x\in A_{i_0}\setminus \bigcup_{k=1}^{i_0-1} A_k$$ (by definition of $$\setminus$$). It further implies that $$x\in B_{i_0}$$ and hence $$x\in\bigcup_{i=1}^n B_i$$ by definition of $$\cup$$. Since $$x\in X$$ implies $$x\in\bigcup_{i=1}^n B_i$$, we conclude that $$X\subseteq\bigcup_{i=1}^n B_i$$ (by definition of $$\subseteq$$).

Part 2. Show that $$\bigcup_{i=1}^n B_i\subseteq X$$. Let $$x\in\bigcup_{i=1}^n B_i$$ then $$x\in B_i$$ (for some $$i$$). If $$i_0$$ is the least such value of $$i$$ such that $$x\in B_{i_0}$$ and since $$B_i\subseteq A_i$$ which we proved already above, it implies that $$x\in A_{i_0}$$ which further implies that $$x\in\bigcup_{i=1}^n A_i$$ (by definition of $$\cup$$). Hence, $$x\in X$$. Since, $$x\in \bigcup_{i=1}^n B_i$$ implies that $$x\in X$$, we conclude that $$\bigcup_{i=1}^n B_i\subseteq X$$.

Conclusion. Since, $$X\subseteq\bigcup_{i=1}^n B_i$$ and $$\bigcup_{i=1}^n B_i\subseteq X$$ then $$X=\bigcup_{i=1}^n B_i$$.

Note: The proof is so elementary that fits to beginners like me.

• Looks like the sets $B_i\ne \emptyset$ form a partition of the set $A$. – Wuestenfux Dec 28 '18 at 11:24
Take $$B_1=A_1,B_2=A_2\setminus A_1, \cdots, B_n=A_n\setminus (A_1 \cup A_2 \cup \cdots \cup A_{n-1})$$. The idea here is if $$x \in X$$ then $$x\in A_k$$ for some $$k$$ and there is smallest $$k$$ with this property. For that $$k$$ we get $$x \in B_k$$,
• Yes you need to show, for your sets $B_1,\dotsc,B_n$, that a-c hold. – palmpo Dec 28 '18 at 12:27
• Do you mean the following Sir? That for (a) I will assume first that $x\in A_k$ and do all ways to prove that $x\in B_k$ given $B_i \subseteq A_i$ for each $i=1,2,\ldots ,n$? For (b), I need to prove that $B_i$ is a disjoint set such that $A_{i} \setminus B_{i-1} \bigcap A_{j} \setminus B_{j-1}=\emptyset$ ? Lastly, for (c), I need to prove that $B_i=B_k$ which implies that $A_{i} \setminus B_{i-1} = A_{j} \setminus B_{j-1}$? – Mharfe Micaroz Dec 28 '18 at 13:56
• No, for (a) you first assume $x\in B_i$ and show that $x\in A_i$, for any $i=1,\dotsc,n$. For (b), you should try proof by contradiction by first assuming $B_i\cap B_j\ne\emptyset$ for some $i\ne j$ and showing that this leads to a contradiction. For (c), this is just showing set equality, i.e. $\bigcup^nA_i=\bigcup^nB_i$. Include your attempt by editing your question so that others may see. – palmpo Dec 28 '18 at 15:24