Cardinality of Cartesian Product

From ProofWiki

Jump to: navigation, search

Theorem

Let $S \times T$ be the cartesian product of two sets $S$ and $T$ which are both finite.

Then:

$\left|{S \times T}\right| = \left|{S}\right| \times \left|{T}\right|$

where $\left|{S}\right|$ denotes cardinality.

This is convenient, given the symbology.

Let $\left|{S}\right| = n$ and $\left|{T}\right| = m$.

$S \times T = \varnothing$

and the result holds, as $n m = 0 = \left|{\varnothing}\right|$ from Cardinality of Empty Set.

For each $a \in S$, we define the mapping $g_a: T \to \left\{{a}\right\} \times T$ such that:

$\forall y \in T: g_a \left({y}\right) = \left({a, y}\right)$

The mapping $g_a$ is a bijection, so $\left| {\left\{{a}\right\} \times T}\right| = m$.

Now let:

$\mathbb T = \left\{{\left\{{a}\right\} \times T: a \in S}\right\}$

We define the mapping $h: S \to \mathbb T$:

$\forall a \in S: h \left({a}\right) = \left\{{a}\right\} \times T$

The mapping $h$ is a bijection, so $\left|{\mathbb T}\right| = n$.

Thus $\mathbb T$ is a partition of $S \times T$ containing $n$ sets.

$\left|{S \times T}\right| = n m$

and the result follows.

$\blacksquare$