Countable Times Countable Is Countable

Union of a countable number of countable sets is countable.

Proof

Let amn denote the nth element of the mth set. With no loss of generality we may assume that the sets do not intersect so that all amn 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 {amn} of the union of the given sets.

Corollary

  1. 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.)
  2. The set Q of all rational numbers is equivalent to the set N of all integers.

Countability of Rational Numbers

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

Copyright © 1996-2017 Alexander Bogomolny

 61175799

Search by google: