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.

$A$ and $B$ are non empty sets with non empty intersection.

Prove that

$(\bigcap A)\cap(\bigcap B) \subseteq \bigcap (A\cap B).$

The definition of intersection of a set is something like this, if $M$ is a nonempty set whose elements are themselves sets, then $x$ is an element of the intersection of $M$ if and only if for every element $A$ of $M$, $x$ is an element of $A$.

share|improve this question
    
Prove (verb) not Proof (subject). –  AD. Jan 24 '12 at 19:41
    
As it is your first post here, I think it might be good to mention the policy of this site on homework questions. If this is a homework, you should use homework tag and perhaps you should also read this. –  Martin Sleziak Jan 24 '12 at 19:59
add comment

2 Answers

up vote 10 down vote accepted

Recall that $\bigcap A=\{x\mid\forall Y\in A: x\in Y\}$, also remember that $A$ is a collection of sets.

Suppose $x\in(\bigcap A)\cap(\bigcap B)$ then $x\in Y$ for all $Y\in A$ and $x\in Z$ for all $Z\in B$. In particular, $x\in T$ for all $T\in A\cap B$. Since $A\cap B\neq\varnothing$ there exists such $T$ and therefore $x\in\bigcap(A\cap B)$.

As commented below $\bigcap\varnothing$ is not well defined. The reason is that $\bigcap A=\{x\mid\forall Y\in A:x\in Y\}$ gives us $\bigcap\varnothing$ is everything (there is no $Y\in\varnothing$, so $x\in\bigcap\varnothing$ vacuously); on the other hand $\bigcap A=\{x\in\bigcup A\mid\forall Y\in A: x\in Y\}$ yields $\bigcap\varnothing=\varnothing$. Note that if $A\neq\varnothing$ then both the definitions are equivalent.

If we take the latter definition (which assures that $\bigcap A$ is a set whenever $A$ is a set) then $A=\{\{x\}\}, B=\{\{x,y\}\}$ is a counterexample.

In such situation it is best to have all the relevant definitions written in front of you, and simply unravel them one by one until you have this big diagram of definitions in front of you, and there lies your proof.

share|improve this answer
1  
I guess the condition $A\cap B\ne\emptyset$ is there mainly for the reason that $\bigcap\emptyset$ is undefined. –  Martin Sleziak Jan 24 '12 at 20:07
    
Dear Asaf: I was going to make the same comment as Martin. –  Pierre-Yves Gaillard Jan 24 '12 at 20:29
    
@Martin: True that $\bigcap\varnothing$ is not well defined; however regardless of its definition if $A\cap B\neq\varnothing$ then the claim is surely correct. –  Asaf Karagila Jan 24 '12 at 20:47
    
Dear @Pierre-Yves: Please see the above remark. Either way both yourself and Martin are correct. It is an issue of well-definedness, I'll edit to address this. –  Asaf Karagila Jan 24 '12 at 20:48
add comment

For theorems like these, as Asaf wrote, expanding definitions and simplifying is the way to go. However, I do these kind of things more 'calculationally' using the rules of predicate logic.

In this case, we can easily calculate the elements $\;x\;$ of the left hand side: \begin{align} & x \in \bigcap A \;\cap\; \bigcap B \\ \equiv & \qquad\text{"definition of $\;\cap\;$; definition of $\;\bigcap\;$, twice"} \\ & \langle \forall V : V \in A : x \in V \rangle \;\land\; \langle \forall V : V \in B : x \in V \rangle \\ \equiv & \qquad\text{"logic: merge ranges of $\;\forall\;$ statements -- to simplify"} \\ & \langle \forall V : V \in A \lor V \in B : x \in V \rangle \\ \end{align}

And similarly for the right hand side: \begin{align} & x \in \bigcap (A \cap B) \\ \equiv & \qquad\text{"definition of $\;\bigcap\;$; definition of $\;\cap\;$"} \\ & \langle \forall V : V \in A \cap B : x \in V \rangle \\ \equiv & \qquad\text{"definition of $\;\cup\;$"} \\ & \langle \forall V : V \in A \land V \in B : x \in V \rangle \\ \end{align}

These two results look promisingly similar. We see that latter range implies the former, and predicate logic tells us that $$ \langle \forall z : P(z) : R(z) \rangle \;\Rightarrow\; \langle \forall z : Q(z) : R(z) \rangle $$ if $\;Q(z) \Rightarrow P(z)\;$ for all $\;z\;$. In our specific case, that means \begin{align} & \langle \forall V : V \in A \lor V \in B : x \in V \rangle \\ \Rightarrow & \qquad \text{"using the above rule, with $\;P \land Q \;\Rightarrow\; P \lor Q\;$"} \\ & \langle \forall V : V \in A \land V \in B : x \in V \rangle \\ \end{align}

Putting this all together, with the definition of $\;\subseteq\;$, tells us that $$ \bigcap A \;\cap\; \bigcap B \;\subseteq\; \bigcap (A \cap B) $$ which is what we set out to prove.

share|improve this answer
add comment

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.