proof that the rationals are countable

Suppose we have a rational numberPlanetmathPlanetmathPlanetmath α=p/q in lowest terms with q>0. Define the “height” of this number as h(α)=|p|+q. For example, h(0)=h(01)=1, h(-1)=h(1)=2, and h(-2)=h(-12)=h(12)=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 numberMathworldPlanetmath to each of the rationals by starting with 0,-1,1,-2,-12,12,2,-3, and progressing through classes of increasing heights. This assignment constitutes a bijection between and and proves that is countableMathworldPlanetmath.

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