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 
remarkably simple. If you're interested in more about this, you might 
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/