Cartesian Product of Countable Sets

Theorem

The cartesian product of two countable sets is countable.

Corollary

Let $k > 1$.

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

Informal Proof

Let $S = \left\{{s_0, s_1, s_2, \ldots}\right\}$ and $T = \left\{{t_0, t_1, t_2, \ldots}\right\}$ be countable sets.

If both $S$ and $T$ are finite, the result follows immediately.

Suppose either of $S$ or $T$ (or both) is countably infinite.

We can write the elements of $S \times T$ in the form of an infinite table:

$\begin{array} {*{4}c} {\left({s_0, t_0}\right)} & {\left({s_0, t_1}\right)} & {\left({s_0, t_2}\right)} & \cdots \\ {\left({s_1, t_0}\right)} & {\left({s_1, t_1}\right)} & {\left({s_1, t_2}\right)} & \cdots \\ {\left({s_2, t_0}\right)} & {\left({s_2, t_1}\right)} & {\left({s_2, t_2}\right)} & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ \end{array}$

This table clearly contains all the elements of $S \times T$.

Now we can count the elements of $S \times T$ by processing the table diagonally. First we pick $\left({s_0, t_0}\right)$. Then we pick $\left({s_0, t_1}\right), \left({s_1, t_0}\right)$. Then we pick $\left({s_0, t_2}\right), \left({s_1, t_1}\right), \left({s_2, t_0}\right)$.

We can see that all the elements of $S \times T$ will (eventually) be listed, and there is a specific number (element of $\N$) to index each of its elements with.

Thus we have the required one-to-one correspondence between $S \times T$ and $\N$, and our assertion is proved.

$\blacksquare$

Formal Proof

Let $S, T$ be countable sets.

From the definition of countable, there exists a injection from $S$ to $\N$, and similarly one from $T$ to $\N$.

Hence there exists an injection $g$ from $S \times T$ to $\N^2$.

Now let us investigate the cardinality of $\N^2$.

From the Fundamental Theorem of Arithmetic, every natural number greater than $1$ has a unique prime decomposition.

Thus, if a number can be written as $2^n 3^m$, it can be done thus in only one way.

So, consider the function $f: \N^2 \to \N$ defined by:

$f \left({n, m}\right) = 2^n 3^m$.

Now suppose $\exists m, n, r, s \in \N$ such that $f \left({n, m}\right) = f \left({r, s}\right)$.

Then $2^n 3^m = 2^r 3^s$ so that $n = r$ and $m = s$.

Thus $f$ is an injection.

Since $f: \N^2 \to \N$ is an injection and $\N$ is countably infinite, it follows from Injection from Infinite to Countably Infinite Set that $\N^2$ is countably infinite.

Now we see that as $g$ and $f$ are injective, it follows from Composite of Injections is an Injection that $f \circ g: S \times T \to \N$ is also injective.

Hence the result.

$\blacksquare$

Sources

• Seth Warner: Modern Algebra (1965)... (previous)... (next): Exercise $18.16$
• Allan Clark: Elements of Abstract Algebra (1971)... (previous)... (next): $\S 15 \delta$