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

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

-