Set Difference of Cartesian Products

From ProofWiki
Jump to navigation Jump to search

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$


Sources