proof that the rationals are countable ProofThatTheRationalsAreCountable 2001-11-16 20:56:31 2002-02-25 20:21:25 Proof cardinality of the rationals countable rational number \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{graphicx} \usepackage{xypic} Suppose we have a rational number $\alpha = p/q$ in lowest terms with $q>0$. Define the ``height'' of this number as $h(\alpha) = |p| + q$. For example, $h(0) = h(\frac{0}{1}) = 1$, $h(-1) = h(1) = 2$, and $h(-2) = h(\frac{-1}{2}) = h(\frac{1}{2}) = h(2) = 3.$ Note that the set of numbers with a given height is finite. The rationals can now be partitioned into classes by height, and the numbers in each class can be ordered by way of increasing numerators. Thus it is possible to assign a natural number to each of the rationals by starting with $0, -1, 1, -2, \frac{-1}{2}, \frac{1}{2}, 2, -3, \ldots$ and progressing through classes of increasing heights. This assignment constitutes a bijection between $\mathbb{N}$ and $\mathbb{Q}$ and proves that $\mathbb{Q}$ is countable. A corollary is that the irrational numbers are uncountable, since the union of the irrationals and the rationals is $\mathbb{R}$, which is uncountable.