3
$\begingroup$

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

2 Answers 2

11

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.

  • 0
    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.2012-01-24
0

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.