# 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

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) andb ∈ B.) - The set
**Q**of all rational numbers is equivalent to the set**N**of all integers.

|Contact| |Front page| |Contents| |Up| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny