# 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 $\mathbb{R}$, 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 |