# Cartesian Product Proof with Set Differences

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.

-

\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}

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

-
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)$ ....

-

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)]$

-
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.


$$\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)\;$.

-