Cartesian Product of Countable Sets is Countable/Corollary/Proof 1

From ProofWiki
Jump to navigation Jump to search

Corollary to Cartesian Product of Countable Sets is Countable

Let $k > 1$.

Then the cartesian product of $k$ countable sets is countable.


Proof

Let $S_1, S_2, \ldots, S_k$ be countable sets.

By the same argument, there exists an injection $g: S_1 \times S_2 \times \cdots \times S_k \to \N^k$.


Now let $p_1, p_2, \ldots, p_k$ be the first $k$ prime numbers.

From the Fundamental Theorem of Arithmetic, $f: \N^k \to \N$ defined as:

$f \left({n_1, n_2, \ldots, n_k}\right) = p_1^{n_1} p_2^{n_2} \cdots p_k^{n_k}$

is an injection.

The result follows from Composite of Injections is Injection and Domain of Injection to Countable Set is Countable, as above.

$\blacksquare$


Sources