# Prove that $\bigcap\limits_{i = 1}^n {\left( {{A_i} - B} \right)} = \bigcap\limits_{i = 1}^n {{A_i}} - B$

Prove that if $A_1, A_2, \ldots , A_n$ and $B$ are sets, then $$(A_1 − B) \cap (A_2 − B) \cap \cdots \cap (A_n − B) = (A_1 \cap A_2 \cap \cdots \cap A_n) − B.$$

-
Where did this problem come from? What have you tried? It matches this Yahoo! Answers question word for word. – Douglas S. Stones Oct 28 '12 at 1:59
1. Is this homework? Please tag if it is. 2. Please be a little more descriptive with the question and the title. Why do you want to do this with induction? An inclusion-exclusion proof would probably be a good option. – Inquest Oct 28 '12 at 1:59

This is pretty straightforward, so I’m going to give only a fairly small hint.

It’s obviously true for $n=1$. You’ll need to prove it for $n=2$ as well, but that’s straightforward. Now suppose that $$(A_1\setminus B)\cap(A_2\setminus B)\cap\ldots\cap(A_n\setminus B)=(A_1\cap A_2\cap\ldots\cap A_n)\setminus B$$ for some $n\ge 2$; this is your induction hypothesis. Then

$$(A_1\setminus B)\cap\ldots\cap(A_n\setminus B)\cap(A_{n+1}\setminus B)=\color{red}{\Big((A_1\setminus B)\cap\ldots\cap(A_n\setminus B)\Big)}\cap(A_{n+1}\setminus B)\;;$$ now apply the induction hypothesis to the red quantity and use the fact that you know that the theorem is true when $n=2$.

-

The tricky case is the base case. You need to prove that $$\left( A_1 - B\right) \cap \left( A_2 - B\right) = \left( A_1 \cap A_2 \right) - B$$ In general, to prove that two sets say $X$ and $Y$ are equal, one goes about proving that $X \subseteq Y$ and $Y \subseteq X$.

In your case, we will first prove that $$\left( A_1 - B\right) \cap \left( A_2 - B\right) \subseteq \left( A_1 \cap A_2 \right) - B$$ Consider an element $x$ in $\left( A_1 - B\right) \cap \left( A_2 - B\right)$. Since $x \in \left( A_1 - B\right) \cap \left( A_2 - B\right)$, we have that $x \in \left( A_1 - B\right)$ and $x \in \left( A_2 - B\right)$. This gives us that $x \in A_1$, $x \in A_2$ and $x \notin B$. This means that $x \in A_1 \cap A_2$ and $x \notin B$. Hence, $x \in \left( A_1 \cap A_2 \right) - B$. This shows that $$\left( A_1 - B\right) \cap \left( A_2 - B\right) \subseteq \left( A_1 \cap A_2 \right) - B$$

Now prove the converse. $$\left( A_1 \cap A_2 \right) - B \subseteq \left( A_1 - B\right) \cap \left( A_2 - B\right)$$ i.e. if $x \in \left( A_1 \cap A_2 \right) - B$, then $x \in \left( A_1 - B\right) \cap \left( A_2 - B\right)$ to conclude that $$\left( A_1 \cap A_2 \right) - B = \left( A_1 - B\right) \cap \left( A_2 - B\right)$$

-
Thanks for Help, Awesome ! – Alpha Oct 28 '12 at 2:05

For proving with the help of induction we chronologically follow these steps

1. Prove for $n=1$ ,mostly, (the base case) this is the most important step.
2. We presume that the statement is true for some integer $n$. This is the Induction Hypotesis.
3. We prove the statement true for integer $n+1$ with the help of Induction Hypothesis.

Now if we want to use Strong Induction : We assume the statement to be true for integers $1,2,3,\ldots,n$ and try to prove for $n+1$.

-