# Prove these sets are pairwise disjoint

Let $A_1, A_2, ...$ be a sequence of subsets of $X$. Let $B_1 = A_1$ and define: $$B_n = A_n \backslash \bigcup_{i=1}^{n-1} A_i$$ Show that $B_1, B_2, ...$ are pairwise disjoint. I was wondering how to show this. I started by showing: $$B_2 = A_2 \backslash A_1 = A_2 \backslash B_1$$ So obviously $B_1$ and $B_2$ are disjoint. From here, I should probably use induction to show every step, but I can't even show that $B_3$ is disjoint from $B_2$ and $B_1$, so I doubt I'll be able to show they're all pairwise disjoint. Here's what I got when I attempted to show $B_3$ is disjoint from $B_2$ and $B_1$: $$B_3 = A_3 \backslash (A_1 \cup A_2) = (A_3 \backslash A_1) \cap (A_3 \backslash A_2) = (A_3 \backslash B_1) \cap (A_3 \backslash A_2)$$ So I managed to show $B_3$ is disjoint from $B_1$, but not $B_2$. Any help would be appreciated :-)

• If $j>i$, $B_i\subset A_i$ and $A_i\cap B_j=\emptyset$ by definition. Thus $B_i\cap B_j=\emptyset$. No need for induction. – zuggg Nov 16 '16 at 9:55

You need to show that $B_n \cap B_m = \emptyset$ when $m \ne n$. Assume wlog $m < n$. Then $$B_n = A_n \setminus \bigcup \limits_{i = 1}^{n - 1} A_i = A_n \cap \bigcap \limits_{i = 1}^{n - 1} A_i^c =A_n \cap \left(\bigcap \limits_{i = 1}^{n - 1} A_i^c\right) \cap A_m^c.$$

This implies $$B_n \cap B_m \subset B_n \cap A_m = A_n \cap \left(\bigcap \limits_{i = 1}^{n - 1} A_i^c\right) \cap A_m^c \cap A_m = \emptyset.$$

• Thanks a lot. This seems rather complicated though, atleast considering it's the first problem in my course. How do you get the idea to do this? And would the comment I've gotten above be sufficient to show this, rather than going through these steps you've shown? – Nicolai Kofoed Nov 16 '16 at 10:21
• This is basically just a more formal way to prove that $B_j \cap A_i = \emptyset$ for $i < j$. – Dominik Nov 16 '16 at 10:23
• Thanks a lot, also for the quick answer, Dominik. I'm indeed very impressed by not only you, but this website. After looking further at what you wrote, it seems to make a lot more sense! :-) – Nicolai Kofoed Nov 16 '16 at 10:24

Hint:

• Consider sequence $C_n = \bigcup_{k=1}^{n} A_k$ and observe that $C_n \subseteq C_{n+1}$.
• $B_n$ consists of the additional elements of $C_n$ that are not in $C_{n-1}$ (or in any other $C_k$ for $k \leq n-1$). Here is a possible diagram to give you more intuition:

I hope this helps $\ddot\smile$