Cartesian Product

Let $A$ and $B$ be two sets, the Cartesian Product of $A$ and $B$ is

$$ A \times B \triangleq \{(a, b): a \in A, b \in B\}

$$

• If $|A| = m$ and $|B| = n$, then

$$ |A \times B| = m \times n $$

• In general,

$$ \begin{aligned} A_1 \times A_2 \times ... \times A_k &\triangleq \{(a_1, a_2, ..., a_k): a_1 \in A_2, ...\}, \\ A^k &\triangleq \overbrace{A \times A \times ... \times A}^{k}

\end{aligned} $$

Relation

A subset of $A \times B$ is called a relation from $A$ to $B$

• A relation can be $\emptyset$

A subset of $A \times A$ is called a binary relation on $A$

• $\{(a, b): a < b, \text{ where } a, b, \in \mathbb{Z}\} \subseteq \mathbb{Z} \times \mathbb{Z}$
• $\{(a, b): b = a^2, \text{ where } a, b, \in \mathbb{Z}\} \subseteq \mathbb{Z} \times \mathbb{Z}$

If $|A| = m$ and $|B| = n$, then there are

$$ 2^{mn} $$

relations from $A$ to $B$

• Each one of the $mn$ 2-tuples $(a, b) \in A \times B$ can be either in the relation or not.
• Alternative proof: $|A \times B| = mn$, so there are $2^{mn}$ subsets of $A \times B$
• $|2^{A \times B}| = 2^{mn}$

Functions