Cardinality of Cartesian Product of Finite Sets

From ProofWiki
Jump to navigation Jump to 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 $\ds \prod_{k \mathop = 1}^n S_k$ be the cartesian product of a (finite) sequence of sets $\sequence {S_n}$.


Then:

$\ds \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$


Examples

Sets with $3$ and $5$ Elements

Let $S$ be a set whose cardinality is $3$.

Let $T$ be a set whose cardinality is $5$.

Then the cardinality of $S \times T$ is $15$.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Cardinality_of_Cartesian_Product_of_Finite_Sets&oldid=613322"