Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.$$

share|improve this question
1  
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  
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

3 Answers 3

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$.

share|improve this answer

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)$$

share|improve this answer
    
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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.