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.

Let $A$, $B$, $C$, and $D$ be sets. Prove: $$ (A\setminus B)\times(C\setminus D)=(A\times C) \setminus [(A\times D)\cup (B\times C)] $$ I've spend a lot of time on this chasing elements all over the place but I can't seem to simplify it. Everything I seem to do/able to do just makes the entire problem more complex and I feel like I'm missing something. Thanks for you help.

share|improve this question

4 Answers 4

up vote 4 down vote accepted

\begin{align}(x,y)\in (A\setminus B)\times(C\setminus D)&\iff x\in (A\setminus B)\wedge y\in(C\setminus D)\\&\iff x\in A\wedge x\notin B \wedge y\in C\wedge y\notin D\\&\iff(x,y)\in(A\times C)\wedge (x,y)\notin(B\times C)\wedge (x,y)\notin (A\times D)\\&\iff (x,y)\in (A\times C) \setminus [(A\times D)\cup (B\times C)] \end{align}

share|improve this answer
    
Explicitly, How would infer that $(x,y) \notin (A×D)$ from $x∈A $and $y∉D$ –  Matthew Jul 2 at 14:53

Consider the diagram, proof with no words (large letter on the left edge of the diagram should be C, not B.): diagrammatic proof

share|improve this answer
1  
I think the large letter on the left edge of the diagram should be C, not B. –  MJD Apr 30 '13 at 20:44
    
@MJD Yes, my mistake. –  Ma Ming Apr 30 '13 at 20:47

Cartesian product distributes over unions

$$ A \times (B \cup C) = A \times B \cup A \times C$$

If $B \subseteq C$, then because $B = B \setminus C \cup C$, we also have that the cartesian product distributes over set differences:

$$ A \times B = A \times (B \setminus C) \cup A \times C$$

And in this case, the union is a disjoint union, and so

$$ A \times (B \setminus C) = (A \times B) \setminus (A \times C) $$

So, we can adapt our knowledge of elementary school algebra to expand $(A \setminus B) \times (C \setminus D)$ ....

share|improve this answer

Let $\left({x, y}\right) \in \left({ A \setminus B}\right) \times \left({C \setminus D}\right)$

Then:

$x \in \left({ A \setminus B}\right) \land \displaystyle y \in\left({C \setminus D}\right)$

$ \iff \left( x \in A \land x \notin B\right) \land \left(y \in C \land y \notin D\right)$

$ \iff \left(x \in A \land y \in C \land y \notin D\right) \lor \left(x \in A \land x \notin B \land y \in C\right) $

$ \iff \left(x \in A \land y \in \left(C \setminus D \right) \right) \lor \left(x \in \left(A \setminus B \right) \land y \in C \right) $

$ \iff \left(\left({x, y}\right) \in A \times \left(C \setminus D \right) \right) \lor \left(\left({x, y}\right) \in \left(A \setminus B \right) \times C \right) $

$ \iff \left(\left({x, y}\right) \in \left(A \times C\right) \setminus \left(A \times D \right) \right) \lor \left(\left({x, y}\right) \in \left(A \times C\right) \setminus \left(A \times B \right) \right) $

$ \iff \left({x, y}\right) \in \left(A \times C\right) \setminus \left(A \times D \right) \cup \left(A \times C\right) \setminus \left(A \times B \right) $

$ \iff \left({x, y}\right) \in (A\times C) \setminus [(A\times D)\cup (B\times C)] $

share|improve this answer

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.