Countable Times Countable Is Countable

Union of a countable number of countable sets is countable.

Proof

Let a_mn denote the n^th element of the m^th set. With no loss of generality we may assume that the sets do not intersect so that all a_mn are distinct. Consider the function

f(m, n) = (m + n - 1)(m + n - 2)/2 + m

It's an interesting exercise to prove that if pairs (m, n) and (m', n') are different, then f(m, n) ≠ f(m', n'). The following diagram demonstrates how the function f was obtained.

I hope that the picture is self-explanatory. The formula for f and the picture above show how to enumerate all the elements {a_mn} of the union of the given sets.

Corollary

A Cartesian product of two countable sets is countable. (Cartesian product of two sets A and B consists of pairs (a, b) where a ∈ A (a is element of A) and b ∈ B.)
The set Q of all rational numbers is equivalent to the set N of all integers.

Countability of Rational Numbers

71547901