Product of Finite Sets is Finite

From ProofWiki
Jump to navigation Jump to search


Let $S$ and $T$ be finite sets.

Then $S \times T$ is a finite set.

Proof 1

By the definition of Cartesian product:

$S \times T = \left\{{ (s,t) } \middle\vert {s \in S, t \in T}\right\}$

Then by definition of set union:

$S \times T = \displaystyle \bigcup_{s \in S} \{s\} \times T$

Also, the mapping $g_s: \{s\} \times T \to T$ defined by:

$g_s \left({s, t}\right) = t$

is a bijection.

Therefore, since $T$ is finite, so is $\{s\} \times T$ for all $s \in S$.

Since $S$ is finite, the result follows from Finite Union of Finite Sets is Finite.


Proof 2

Let $\left|{ S }\right|$ denote the cardinal number of $S$.

Let $\cdot$ denote ordinal multiplication.

By Cardinal Product Equinumerous to Ordinal Product, it follows that $S \times T \sim \left|{ S }\right| \cdot \left|{ T }\right|$.

But then $\left|{ S }\right|$ and $\left|{ T }\right|$ are members of the minimal infinite successor set.

Therefore, $\left|{ S }\right| \cdot \left|{ T }\right| \in \omega$ by Natural Number Multiplication is Closed.

Since $S \times T$ is equinumerous to a member of the minimal infinite successor set, it follows that $S \times T$ is finite.