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


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.

  • 1
    $\begingroup$ I guess the condition $A\cap B\ne\emptyset$ is there mainly for the reason that $\bigcap\emptyset$ is undefined. $\endgroup$ – Martin Sleziak Jan 24 '12 at 20:07
  • $\begingroup$ Dear Asaf: I was going to make the same comment as Martin. $\endgroup$ – Pierre-Yves Gaillard Jan 24 '12 at 20:29
  • $\begingroup$ @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. $\endgroup$ – Asaf Karagila Jan 24 '12 at 20:47
  • $\begingroup$ 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. $\endgroup$ – Asaf Karagila Jan 24 '12 at 20:48

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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