proof that the rationals are countable

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,\mathrm{\dots }$ 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 $ℝ$, which is uncountable.

Title	proof that the rationals are countable
Canonical name	ProofThatTheRationalsAreCountable
Date of creation	2013-03-22 11:59:53
Last modified on	2013-03-22 11:59:53
Owner	alozano (2414)
Last modified by	alozano (2414)
Numerical id	9
Author	alozano (2414)
Entry type	Proof
Classification	msc 03E10
Related topic	RationalNumber
Related topic	IrrationalNumber
Related topic	Countable
Related topic	Irrational