# Set Difference of Cartesian Products

## Theorem

$\paren {S_1 \times S_2} \setminus \paren {T_1 \times T_2} = \paren {S_1 \times \paren {S_2 \setminus T_2} } \cup \paren {\paren {S_1 \setminus T_1} \times S_2}$

## Proof

Let $\tuple {x, y} \in \paren {S_1 \times S_2} \setminus \paren {T_1 \times T_2}$.

Then:

 $\displaystyle \tuple {x, y} \in S_1 \times S_2$ $\land$ $\displaystyle \tuple {x, y} \notin T_1 \times T_2$ Definition of Set Difference $\displaystyle \leadstoandfrom \ \$ $\displaystyle x \in S_1 \land y \in S_2$ $\land$ $\displaystyle \neg \paren {x \in T_1 \land y \in T_2}$ Definition of Cartesian Product $\displaystyle \leadstoandfrom \ \$ $\displaystyle x \in S_1 \land y \in S_2$ $\land$ $\displaystyle \paren {x \notin T_1 \lor y \notin T_2}$ De Morgan's Laws: Disjunction of Negations $\displaystyle \leadstoandfrom \ \$ $\displaystyle \paren {x \in S_1 \land y \in S_2 \land x \notin T_1}$ $\lor$ $\displaystyle \paren {x \in S_1 \land y \in S_2 \land y \notin T_2}$ Rule of Distribution $\displaystyle \leadstoandfrom \ \$ $\displaystyle \paren {x \in S_1 \setminus T_1 \land y \in S_2}$ $\lor$ $\displaystyle \paren {x \in S_1 \land y \in S_2 \setminus T_2}$ Definition of Set Difference $\displaystyle \leadstoandfrom \ \$ $\displaystyle \paren {\tuple {x, y} \in \paren {S_1 \setminus T_1} \times S_2}$ $\lor$ $\displaystyle \paren {\tuple {x, y} \in S_1 \times \paren {S_2 \setminus T_2} }$ Definition of Cartesian Product $\displaystyle \leadstoandfrom \ \$ $\displaystyle \tuple {x, y}$ $\in$ $\displaystyle \paren {S_1 \times \paren {S_2 \setminus T_2} } \cup \paren {\paren {S_1 \setminus T_1} \times S_2}$ Definition of Set Union

The result follows from the definition of subset and set equality.

$\blacksquare$