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.

Is this right already?

  • 1
    $\begingroup$ Looks like the sets $B_i\ne \emptyset$ form a partition of the set $A$. $\endgroup$ – 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$,

  • $\begingroup$ Thanks @kavi-rama-murthy but still unclear to me. Do I need to show my proof for each of the three conditionz given above? $\endgroup$ – Mharfe Micaroz Dec 28 '18 at 12:23
  • $\begingroup$ Yes you need to show, for your sets $B_1,\dotsc,B_n$, that a-c hold. $\endgroup$ – palmpo Dec 28 '18 at 12:27
  • $\begingroup$ Can you give just a simple oversight on how to prove each property sir? $\endgroup$ – Mharfe Micaroz Dec 28 '18 at 13:08
  • $\begingroup$ 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}$? $\endgroup$ – Mharfe Micaroz Dec 28 '18 at 13:56
  • $\begingroup$ 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. $\endgroup$ – palmpo Dec 28 '18 at 15:24

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.