Cartesian Product of Countable Sets is Countable/Formal Proof 2

From ProofWiki
Jump to navigation Jump to search

Theorem

The cartesian product of two countable sets is countable.


Proof

Let $S, T$ be countable sets.

Let $S = \set {s_1, s_2, s_3, \dotsc}$ and $T = \set {t_1, t_2, t_3, \dotsc}$ be enumerations of $S$ and $T$ respectively.

Let $f: S \times T: \N$ be the mapping defined as:

$\forall \tuple {s_k, t_l} \in S \times T: \map f {s_k, t_l} = \dfrac {\paren {k + l - 1} \paren {k + l - 2} } 2 + \dfrac {l + \paren {-1}^{k + 1} } 2 k + \dfrac {1 + \paren {-1}^{k + l - 1} } 2 l$

Then $f$ gives an enumeration of $S \times T$.


This enumeration can be depicted schematically as:

$\begin {array} {} \tuple {s_1, t_1} & & \tuple {s_1, t_2} & \to & \tuple {s_1, t_3} & & \tuple {s_1, t_4} & \to & \dotsc \\ \downarrow & \nearrow & & \swarrow & & \nearrow & \dotsc \\ \tuple {s_2, t_1} & & \tuple {s_2, t_2} & & \tuple {s_2, t_3} & \dotsc \\ & \swarrow & & \nearrow & \dotsc \\ \tuple {s_3, t_1} & & \tuple {s_2, t_3} & \dotsc \\ \downarrow & \nearrow & \dotsc \\ \tuple {s_3, t_1} & \dotsc \\ \vdots \\ \end{array}$

Hence the result.

$\blacksquare$


Sources