Cartesian product

For any sets $A$ and $B$, the Cartesian product $A\times B$ is the set consisting of all ordered pairs $(a,b)$ where $a\in A$ and $b\in B$.

The Cartesian product satisfies the following properties, for all sets $A$, $B$, $C$, and $D$:

• $A\times \mathrm{\varnothing }=\mathrm{\varnothing }$

• $(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)$

• ${(A\times B)}^{\mathrm{\complement }}=(A^{\mathrm{\complement }}\times B^{\mathrm{\complement }})\cup (A^{\mathrm{\complement }}\times B)\cup (A\times B^{\mathrm{\complement }})$

Here $\mathrm{\varnothing }$ denotes the empty set, $\cap$ denotes intersection, $\cup$ denotes union, and ${}^{\mathrm{\complement }}$ denotes complement with respect to some universal set $U$ containing $A$ and $B$.