Cardinality of Cartesian Product

From ProofWiki
Jump to: navigation, search

Theorem

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


Then:

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

where $\card S$ denotes cardinality.

This is convenient, given the symbology.


Corollary

$\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}$.


Then:

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


Proof

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: \map {g_a} 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: \map h 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.

$\blacksquare$


Sources