Cartesian Product of Countable Sets is Countable/Corollary

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 1

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$


Proof 2

Proof by induction:

Basis for the Induction

When $k = 2$, the case is the same as Cartesian Product of Countable Sets is Countable.

So shown for basis for the induction.


Induction Hypothesis

This is our induction hypothesis:

$\exists f_k: S_1 \times S_2 \times \cdots \times S_k \to \N$

where $f_k$ is an injection.

Now we need to show that for $n = k + 1$:

$\exists f_{k+1}: S_1 \times S_2 \times \cdots \times S_k \times S_{k+1} \to \N$

where $f_{k+1}$ is an injection.


Induction Step

This is our induction step:

By the induction hypothesis:

$\exists f_k: S_1 \times S_2 \times \cdots \times S_k \to \N$

where $f_k$ is an injection.

Thus by definition, $S_1 \times S_2 \times \cdots \times S_k$ is countable.

By hypothesis $S_{k + 1}$ is countable.

So by the basis for the induction:

$\exists g: \left({S_1 \times S_2 \times \cdots \times S_k}\right) \times S_{k+1} \to \N \times \N$

where $g$ is an injection.

By Cartesian Product of Countable Sets is Countable,

$\exists r: \N \times \N \to \N$

where $r$ is an injection.

Therefore, by Composite of Injections is Injection:

$f_{k+1} = r \circ g: S_1 \times S_2 \times \cdots \times S_k \times S_{k+1} \to \N$

is an injection.

The result follows by induction.

$\blacksquare$


Sources