Cardinality of Cartesian Product

From ProofWiki
Jump to: navigation, search


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


$\card {S \times T} = \card S \times \card T$

where $\card S$ denotes cardinality.

This is convenient, given the symbology.


$\card {S \times T} = \card {T \times S}$

General Result

Let $\displaystyle \prod_{k \mathop = 1}^n S_k$ be the cartesian product of a (finite) sequence of sets $\sequence {S_n}$.


$\displaystyle \card {\prod_{k \mathop = 1}^n S_k} = \prod_{k \mathop = 1}^n \card {S_k}$


Let $\card S = n$ and $\card T = m$.

If either $n = 0$ or $m = 0$, then from Cartesian Product is Empty iff Factor is Empty:

$S \times T = \O$

and the result holds, as $n m = 0 = \card \O$ from Cardinality of Empty Set.

So, we assume that $n > 0$ and $m > 0$.

For each $a \in S$, we define the mapping $g_a: T \to \set a \times T$ such that:

$\forall y \in T: g_a \paren y = \tuple {a, y}$

The mapping $g_a$ is a bijection, so:

$\card {\set a \times T} = m$

Now let:

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

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

$\forall a \in S: h \paren a = \set a \times T$

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

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

Hence from Number of Elements in Partition:

$\card {S \times T} = n m$

and the result follows.