Associated Topics || Dr. Math Home || Search Dr. Math

### Counting Rationals and Integers

```
Date: 10/06/1999 at 15:36:25
From: Michael Kelley
Subject: Proof of rationals and integers

Dr. Math,

My teacher wants us to prove that there is the same amount of
rational numbers as integers. He has said that is it an extremely hard
proof, and I have tried, but I cannot prove it. I have tried to
disprove by counterexample, but that did not work. Since I am working
with infinite sets, I cannot prove by example. The only clue my
teacher gave me was it has something to do with Cantor. Can you help
me?

Michael Kelley
```

```
Date: 10/06/1999 at 17:04:17
From: Doctor Rob
Subject: Re: Proof of rationals and integers

Thanks for writing to Ask Dr. Math, Michael.

The key to these proofs is to show that each set is in one-to-one
correspondence with a subset of the other. Then they must have the
same size.

Every integer n corresponds in a one-to-one fashion to a rational
number of the form n/1. The set of rational numbers of the form n/1
is a subset of all the rational numbers. This implies that the number
of integers is no larger than the number of rational numbers.

That's the easy part. Now we need to show the reverse is also true.

Write the rational numbers in a doubly-infinite array, putting the
fraction a/b with b > 0 at the point (a,b) in the upper half of the
xy-plane. It should look a bit like this:

...    :     :     :     :     :     :     :    ...

...  -3/3  -2/3  -1/3   0/3   1/3   2/3   3/3   ...

...  -3/2  -2/2  -1/2   0/2   1/2   2/2   3/2   ...

...  -3/1  -2/1  -1/1   0/1   1/1   2/1   3/1   ...

...    :     :     :     :     :     :     :    ...

It should be clear that every rational number appears somewhere in
this array. Some appear more than once, such as 1/1 = 2/2 = 3/3.

Now make a broken line spiraling out from the center (-1/1, mark it
with X) in the following way:

o---o-- ...
|
o   o---o---o---o---o---o---o---o---o
|   |                               |
o   o   o---o---o---o---o---o---o   o
|   |   |                       |   |
o   o   o   o---o---o---o---o   o   o
|   |   |   |               |   |   |
o---o   o---o   X---o---o---o   o---o

To each point along the spiral, assign a nonnegative integer according
to its distance from X along this line. Then to every rational number
in lowest terms there will correspond a positive integer. Every
rational number is covered, and the correspondence between the
rational numbers in lowest terms and a certain subset of the integers
is one-to-one.

Here is part of it:

-1/1 <--> 0
0/1 <--> 1
1/1 <--> 2
+++++++++++ End of max(a,b) = 1
2/1 <--> 3
(skip 4 because 2/2 is not in lowest terms)
1/2 <--> 5
(skip 6 because 0/2 is not in lowest terms)
-1/2 <--> 7
(skip 8 because -2/2 is not in lowest terms)
-2/1 <--> 9
++++++++++++ End of max(a,b) = 2
-3/1 <--> 10
-3/2 <--> 11
(skip 12 because -3/3 is not in lowest terms)
-2/3 <--> 13
-1/3 <--> 14
(skip 15 because 0/3 is not in lowest terms)
1/3 <--> 16
2/3 <--> 17
(skip 18 because 3/3 is not in lowest terms)
3/2 <--> 19
3/1 <--> 20
++++++++++++ End of max(a,b) = 3
4/1 <--> 21
:       :

The spiral covers all rational numbers in systematic fashion. If
max(a,b) = m, then the integer that corresponds to a/b is between
(2*m-1)*(m-1) and (2*m-1)*(m+1), inclusive. One could write this
correspondence out explicitly if desired, but it's not necessary for
the proof.

That proves that the number of rational numbers is no more than the
number of integers.

Putting the two parts together, the number of rational numbers and the
number of integers must be the same, since neither number is larger
than the other.

By the way, the spiral I drew is only one way to assign an integer to
every rational number in lowest terms in a one-to-one fashion. There
are lots of other possibilities which can also work.

- Doctor Rob, The Math Forum
http://mathforum.org/dr.math/
```

```
Date: 10/06/1999 at 17:10:42
From: Doctor Peterson
Subject: Re: Proof of rationals and integers

Hi, Michael.

It's actually not a very hard proof, but it took a genius who did
things no one else had ever thought of to invent it. Georg Cantor
essentially invented the whole idea of set theory, and of how to count
infinite sets and compare different infinities, by himself.

Here are a couple answers in our archives that deal with proving that
the set of rational numbers is "countable", that is, you can number
them 1, 2, 3, ..., showing that there are the same number of rationals
as integers:

Countability
http://mathforum.org/dr.math/problems/stephanie9.9.98.html

Infinite Sets
http://mathforum.org/dr.math/problems/lee7.17.97.html

The first of these also includes Cantor's proof that the real numbers
are NOT countable. Both proofs (at least in their basic concepts) are
try searching the Web (or a library or encyclopedia) for pages
containing both "Cantor" and "countable". Here's a page from which you
can find an article about Georg Cantor himself:

MacTutor Math History Archive - St. Andrews
Indexes of Biographies - Names beginning with C
http://www-history.mcs.st-and.ac.uk/history/Indexes/C.html

- Doctor Peterson, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search