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

5 Answers 5

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$ –  Mathman Jul 2 '14 at 14:53
    
The third $\;\iff\;$ step is rather a big leap: see the answer I just added for more detail on that step. –  Marnix Klooster Mar 23 at 21:37

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
    
The last step seems wrong: it looks like all $\;\cup\;$ except the last, and all $\;\lor\;$, should be replaced by $\;\cap\;$ and $\;\land\;$, respectively. –  Marnix Klooster Mar 23 at 21:31

Here is a late alternative answer, with several features which the earlier ones lack: it goes fully back to the definitions instead of using set theory laws; it uses only small steps; and it explains all those steps.

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\followsfrom}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $Looking at the original statement, it is obvious that both sides contain only pairs. So let's start at the most complex side, the right hand side, and calculate which pairs $\;(x,y)\;$ it contains:

$$\calc (x,y) \in (A \times C) \setminus [(A \times D)\cup (B \times C)] \op\equiv\hint{definition of $\;\setminus\;$; definition of $\;\lor\;$} (x,y) \in (A \times C) \;\land\; \lnot ((x,y) \in (A \times D) \lor (x,y) \in (B \times C)) \op\equiv\hint{definition of $\;\times\;$, three times} x \in A \land y \in C \;\land\; \lnot ((x \in A \land y \in D) \lor (x \in B \land y \in C)) \op\equiv\hints{logic: use $\;x \in A\;$ on other side of first $\;\land\;$;}\hint{use $\;y \in C\;$ on other side of second $\;\land\;$} x \in A \land y \in C \;\land\; \lnot ((\true \land y \in D) \lor (x \in B \land \true)) \op\equiv\hint{logic: simplify; DeMorgan} x \in A \land y \in C \;\land\; x \not\in B \land y \not\in D \op\equiv\hint{logic: reorder conjuncts; definition of $\;\setminus\;$, twice} x \in A \setminus B \;\land\; y \in C \setminus D \op\equiv\hint{definition of $\;\times\;$} (x,y) \in (A \setminus B) \times (C \setminus D) \endcalc$$

Therefore, by set extensionality, $\;(A \times C) \setminus [(A \times D)\cup (B \times C)] \;=\; (A \setminus B) \times (C \setminus D)\;$.

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.