# Prove that the sets $(A\cap B)$ \ C and $(A\cap C)$ \ B are disjoint.

Please could someone validate this proof

Prove that the sets $(A\cap B)$ \ C and $(A\cap C)$ \ B are disjoint.

First we want to show that

(1) $(A\cap B)$ \ C $\not \subseteq$ $(A\cap C)$ \ B

Assume $x \in (A\cap B)$ \ C. Then, by the definition of intersection $x \in A$ and $x \in B$. We are told that $x \notin C$. Given that $x \notin$ C, $x \notin$ $A\cap C$. Furthermore, we know that $x \in$ B. So, by the definition of setminus, $x \notin (A\cap C)$ \ B. This proves (1)

(2) $(A\cap C)$ \ B$\not \subseteq$ $(A\cap B)$\ C

Assume $x \in (A\cap C)$ \ B. Then, by the definition of intersection $x \in A$ and $x \in C$. We know by the definition of setminus that $x \notin B$. Given that $x \notin$ B, $x \notin$ $A\cap B$. Furthermore, we know that $x \in$ C. So, by the definition of setminus, $x \notin (A\cap B)$ \ C. This proves (2)

-
This is the only command I could find \subsetneq which gives $\subsetneq$ <--- not a subset of – bosra Jan 17 '13 at 18:47
try \not \subseteq – Git Gud Jan 17 '13 at 18:48
@GitGud: \nsubseteq works fine. – Brian M. Scott Jan 17 '13 at 18:51
@GitGud: You’re welcome. So am I. – Brian M. Scott Jan 17 '13 at 18:52

You can’t show that $X\cap Y=\varnothing$ by showing that $X\nsubseteq Y$ and $Y\nsubseteq X$: what if $X=\{0,1\}$ and $Y=\{1,2\}$, say?

To show that $(A\cap B)\setminus C$ and $(A\cap C)\setminus B$ are disjoint, just show that if $x\in(A\cap B)\setminus C$, then $x\notin(A\cap C)\setminus B$; that’s all it takes. So suppose that $x\in(A\cap B)\setminus C$; then $x\in A\cap B$, and $x\notin C$. Since $x\notin C$, clearly $x\notin A\cap C$, and it follows at once that $x\notin(A\cap C)\setminus B$.

Note that this is exactly the argument that you gave for your (1). The argument is fine, but it doesn’t show what you thought it showed; instead, it does the whole job for you.

-
(According to the Op's comment, he used $\subsetneq$ as $\nsubseteq$ for lack of knowing the correct tex command.) – Jason DeVito Jan 17 '13 at 18:49
@bosra: You can do the proof as follows also: $$(A\cap B)-C=(A\cap B)\cap C'\\\ (A\cap C)-B=(A\cap C)\cap B'$$ So $$((A\cap B)-C)\cap((A\cap C)-B)=((A\cap B)\cap C')\cap ((A\cap C)\cap B')=\emptyset$$ – Babak S. Jan 17 '13 at 19:35
Cheers @BabakSorouh – bosra Jan 17 '13 at 19:58

Several elementary proofs have been given, but I feel like some of them ran away with element chasing, and I'd like to take a different approach.

$(A\cap B)\setminus C$ is a subset of $B$.

$(A\cap C)\setminus B$ is a subset of the complement of $B$.

Hence, $[(A\cap B)\setminus C]\cap[(A\cap C)\setminus B]\subseteq B\cap B^c=\emptyset$

So the left hand intersection is empty, proving the two sets are disjoint.

There's nothing wrong with the element chasing. In fact that's probably pretty good exercise if you're getting used to basic set theory :)

-
Very nice proof – bosra Jan 17 '13 at 20:13

Your logic is sound, but what you stated you are going to prove in (1) and (2) isn't actually what you proved; what you proved is (correctly):

(1) $\forall x(x \in (A \cap B) \setminus C \to x \not\in (A \cap C) \setminus B)$

and

(2) $\forall x(x \in (A \cap C) \setminus B \to x \not\in (A \cap B) \setminus C)$

Generally, $X$ and $Y$ being disjoint sets is by definition the two statements

(1) $\forall x(x \in X \to x \not\in Y)$

and

(2) $\forall x(x \in Y \to x \not\in X)$

so the breakdown into the two sub-proofs is a good idea.

-
Note that (1) and (2) are completely equivalent, so it is actually sufficient to prove just one of these. – Marnix Klooster May 1 '13 at 20:09