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

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

- 1965: Seth Warner:
*Modern Algebra*... (previous) ... (next): Exercise $18.16$ - 2008: Paul Halmos and Steven Givant:
*Introduction to Boolean Algebras*... (previous) ... (next): Appendix $\text{A}$: Set Theory: Countable Sets