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.

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)

Thanks in advance

share|improve this question
    
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
    
@BrianM.Scott Thanks. I'm still learning about this too. –  Git Gud Jan 17 '13 at 18:51
    
@GitGud: You’re welcome. So am I. –  Brian M. Scott Jan 17 '13 at 18:52
add comment

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
1  
(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
2  
@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$$ –  B. S. Jan 17 '13 at 19:35
    
Cheers @BabakSorouh –  bosra Jan 17 '13 at 19:58
add comment

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 :)

share|improve this answer
1  
Very nice proof –  bosra Jan 17 '13 at 20:13
add comment

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.

share|improve this answer
    
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
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.