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.$
Prove that $\bigcap\limits_{i = 1}^n {\left( {{A_i} - B} \right)} = \bigcap\limits_{i = 1}^n {{A_i}} - B$
-
1Where did this problem come from? What have you tried? It matches [this Yahoo! Answers question](http://answers.yahoo.com/question/index?qid=20111116154729AAZU0xo) word for word. – 2012-10-28
3 Answers
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)$
-
0Thanks for Help, Awesome ! – 2012-10-28
For proving with the help of induction we chronologically follow these steps
- Prove for $n=1$ ,mostly, (the base case) this is the most important step.
- We presume that the statement is true for some integer $n$. This is the Induction Hypotesis.
- 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$.