Set Difference of Cartesian Products

Theorem

$\left({S_1 \times S_2}\right) \setminus \left({T_1 \times T_2}\right) = \left({S_1 \times \left({S_2 \setminus T_2}\right)}\right) \cup \left({\left({S_1 \setminus T_1}\right) \times S_2}\right)$

Proof

Let $\left({x, y}\right) \in \left({S_1 \times S_2}\right) \setminus \left({T_1 \times T_2}\right)$.

Then:

	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \left({x, y}\right) \in S_1 \times S_2\)	\(\land\)	\(\displaystyle \left({x, y}\right) \notin T_1 \times T_2\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of set difference
	\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle x \in S_1 \land y \in S_2\)	\(\land\)	\(\displaystyle \neg \left({x \in T_1 \land y \in T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of cartesian product
	\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle x \in S_1 \land y \in S_2\)	\(\land\)	\(\displaystyle \left({x \notin T_1 \lor y \notin T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	De Morgan's Laws
	\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle \left({x \in S_1 \land y \in S_2 \land x \notin T_1}\right)\)	\(\lor\)	\(\displaystyle \left({x \in S_1 \land y \in S_2 \land y \notin T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Rule of Distribution
	\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle \left({x \in S_1 \setminus T_1 \land y \in S_2}\right)\)	\(\lor\)	\(\displaystyle \left({x \in S_1 \land y \in S_2 \setminus T_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of set difference
	\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle \left({\left({x, y}\right) \in \left({S_1 \setminus T_1}\right)\times S_2}\right)\)	\(\lor\)	\(\displaystyle \left({\left({x, y}\right) \in S_1 \times \left({S_2 \setminus T_2}\right)}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of cartesian product
	\(\displaystyle \)	\(\displaystyle \iff\)	\(\displaystyle \)	\(\displaystyle \left({x, y}\right)\)	\(\in\)	\(\displaystyle \left({S_1 \times \left({S_2 \setminus T_2}\right)}\right) \cup \left({\left({S_1 \setminus T_1}\right)\times S_2}\right)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Definition of set union

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

$\blacksquare$

Sources

• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 9 \alpha$