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 \emptyset = \emptyset$
• $(A \times B) \cap (C \times D) = (A\cap C) \times (B\cap D)$
• $(A \times B)^\complement = (A^\complement \times B^\complement) \cup (A^\complement \times B) \cup (A \times B^\complement)$

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