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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.