1
$\begingroup$

Question:

Prove/disprove: For all sets $A,B,C$, if $B \cap C \subset A$, then $(C \backslash A) \cap (B \backslash A) = \emptyset$

I'm a bit confused about the question, or where to start. When we learned how to prove these, the examples given were usually either sets that were equal (in which case we could prove that they were subsets of each other) or cases where there weren't subsets at all. Unfortunately, looking at my professors solution is only making things more confusing as I can't find any properties of these sets that he is using in his answer.

His answer:

  1. Let us assume that $B \cap C \subset A$. This implies that
  2. $(B \cap C) \cap A^c \subset A \cap A^c = \emptyset$
  3. $(B \cap A^c) \cap (C \cap A^c) = \emptyset$
  4. $(B \backslash A) \cap (C \backslash A) = \emptyset$

I understand that lines 3 and 4 are correct. The thing I don't understand is the jump from lines 1 and 2, and how he goes about getting that.

$\endgroup$
  • 1
    $\begingroup$ I would prefer a more wordy approach. We can translate to symbols later. Suppose $x$ is in $(B\setminus A)\cap (C\setminus A)$. Then $x$ is in $B$ and $C$ but not in $A$. So $x$ is in $B\cap C$ but not in $A$. If $(B\cap C)\subset A$, there is no such $x$. $\endgroup$ – André Nicolas May 20 '14 at 4:04
  • $\begingroup$ In going from line 1 to 2, he is using the fact that $\;\cap\;$ is monotonic w.r.t. $\;\subseteq\;$. Or more symbolically, $\;X \subseteq Y \;\Rightarrow\; X \cap Z \subseteq Y \cap Z\;$. Here he chooses $\;Z\;$ to be $\;A^c\;$. $\endgroup$ – MarnixKlooster ReinstateMonica May 20 '14 at 4:35
2
$\begingroup$

This is really easy to see if you draw a Venn diagram. But going from line 1 to line 2, note that $B\cap C$ is contained in $A$ and since $A$ and $A^c$ are disjoint, so are $B\cap C$ and $A^c$.

Going from line 2 to line 3, note that if all operations are intersections then the order does not matter. So

$$(B\cap C)\cap A^c = B \cap C \cap A^c = B \cap A^c \cap C = B\cap ( A^c \cap A^c) \cap C = (B \cap A^c) \cap (C\cap A^c).$$

$\endgroup$
  • $\begingroup$ How come A^c = (A^c intersects A^c)? $\endgroup$ – Alex May 20 '14 at 4:40
  • $\begingroup$ The intersection of a set with itself is that set since any element of a set belongs to the set. ;) Recall that the definition of an intersection is the collection of points that belong to both sets. $\endgroup$ – JPi May 20 '14 at 9:59
0
$\begingroup$

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\notag \\ #1 \quad & \quad \text{"#2"} \notag \\ \quad & } \newcommand{\endcalc}{\notag \end{align}} $ (This is not a direct answer, but an alternative approach.)

I would prefer a more 'logical' approach, where you start with the most complex side, $\;(C \setminus A) \cap (B \setminus A) = \emptyset\;$, apply the definitions, and then simplify using the laws of logic. That results in $$\calc (C \setminus A) \cap (B \setminus A) \;=\; \emptyset \calcop{\equiv}{basic property of $\;\emptyset\;$} \langle \forall x :: \lnot(x \in (C \setminus A) \cap (B \setminus A)) \rangle \calcop{\equiv}{definition of $\;\cap\;$, and of $\;\setminus\;$ twice} \langle \forall x :: \lnot(x \in C \land x \not\in A \;\land\; x \in B \land x \not\in A) \rangle \calcop{\equiv}{logic: simplify} \langle \forall x :: \lnot(x \in C \land x \in B \;\land\; x \not\in A) \rangle \calcop{\equiv}{logic: DeMorgan -- keeping $\;B,C\;$ together as in our goal} \langle \forall x :: \lnot(x \in C \land x \in B) \;\lor\; x \in A \rangle \calcop{\equiv}{logic: $\;\lnot P \lor Q\;$ is another way to write $\;P \Rightarrow Q\;$} \langle \forall x :: x \in C \land x \in B \;\Rightarrow\; x \in A \rangle \calcop{\equiv}{definitions of $\;\cap\;$ and $\;\subseteq\;$} C \cap B \;\subseteq\; A \endcalc$$

This shows that the two given statements are even equivalent.

$\endgroup$
0
$\begingroup$

To get from line 2 to line 3:

2: $(B \cap C) \cap A^c \subset A \cap A^c = \emptyset$
3: $(B \cap A^c) \cap (C \cap A^c) = \emptyset$

Note that $X\cap Y = X\cap Y\cap Y$.

So $$\begin{align} (B\cap C)\cap A^c & = (B\cap \color{darkblue}{C})\cap \color{darkblue}{A^c} \cap \color{darkred}{A^c}\\ & = B\cap\color{darkblue}{(C\cap A^c)}\cap \color{darkred}{A^c}\\ & = B\cap \color{darkred}{A^c}\cap\color{darkblue}{(C\cap A^c)} \\ & = (B\cap \color{darkred}{A^c}) \cap \color{darkblue}{(C \cap A^c)} \end{align} $$

where the last few lines follow by commutativity and associativity of $\cap$.

To get from line 1 to line 2 you need to know that if $X\subset Y$, then $X\cap Z \subset Y\cap Z$. (“All mothers are women, therefore all tall mothers are tall women.”) You should have seen this theorem already, either in class or as an exercise, but if you don't recognize it, you should try to prove it.

$\endgroup$

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.