Since there was some discussion of infinity in the whole .999... shebang, I thought I'd post a quick proof related to infinite sets. The result is well-known: the set of rational numbers and the set of natural (counting) numbers have the same cardinality (that is, they are the same size). This is normally shown with Cantor's diagonalization proof.

This result is usually considered counter-intuitive because there are infinitely many rational numbers just between 0 and 1 alone. Yet, the set of rationals is indeed the same size as the set of natruals. All I wanted to do in this post was give you my favorite proof of this. I know there are many. I know you'll be tempted to post your favorite in the comments (feel free). But for some reason, this one is so clever, it's by far my favorite. I learned it from a professor in college.

I will prove that the set of (positive) rational numbers can be associated one-to-one with a subset of the natural numbers. Since it is easy to associate the natural numbers with a subset of the rationals (the reciprocal function will do), the demonstration below completes the proof.

By definition, each positive rational number can be expressed in a unique manner as p/q, where p and q are natural numbers with no common factors. Consider the string of symbols composed of (digits of p)/(digits of q), with a slash between the strings of digits. Now read that string (which is unique for every rational) as an integer in base 11, with the slash being the symbol for 10. There's your integer associated with that rational number. QED.

Beautiful... I'm just gobsmacked.

Posted by: Julian M Bucknall | August 09, 2006 at 11:35 PM

I need some help here, please.

Your goal is to prove that there is a one-to-one mapping from the set of positive rationals to the set of natural numbers and there is a one-to-one mapping from the set of natural numbers to the set of positive rationals. Right?

I see that you've proved there is a one-to-one mapping from the set of positive rationals to the set of natural numbers (thereby also proving there is a one-to-one mapping from the set of positive rationals to the set of subsets of natural numbers.)

Beyond this I don't know what happened. Help?

Posted by: RS | August 10, 2006 at 04:02 AM

RS:

My ultimate goal is to prove a one-to-one correspondence between the naturals and the rationals (but showing it for the positive rationals is enough). Note that once you show it one way, the nature of one-to-one-ness means that it's true the other way too.

My base-11 proof shows a one-to-one correspondence between the rationals and a subset of the naturals, and I'm claiming that's enough.

This is not actually the same as showing as showing the correspondence between the rationals and the set of subsets of the naturals. The set of subsets is always of a greater cardinality than the original set. The set of subsets of naturals is the same cardinality as the set of real numbers.

But surely the rationals are at least the size of the naturals, so if they match up with a subset of the naturals, they must be the same size. That's another reason I'm done after the base-11 part of the proof. I hope that clears things up.

Posted by: Polymath | August 10, 2006 at 08:46 AM

This demonstration is wonderfully intuitive in a way that proofs of these types of facts usually aren't. Did this come from the classroom, and if not, will you use it there?

Posted by: Coconuts | August 10, 2006 at 09:23 AM

That's much nicer than the usual method I've seen for showing countability of the rationals.

Posted by: Davis | August 10, 2006 at 11:01 AM

Thanks for the explanation. It's clear now. There are at least as many rationals as there are integers (thanks, reciprocal function) and there are at least as many integers as there are rationals (thanks, base 11). Done.

One of my stumbling blocks was that when I see "one-to-one", I read "injective function". Another stumbling block was the phrase "every (positive) rational number can be associated one-to-one with a subset of the natural numbers", because this suggests to me that the power set of N is the co-domain. Does that sound reasonable?

Posted by: RS | August 10, 2006 at 11:44 AM

Coconuts: I learned this in college. I've shown Cantor's proof in class many times, but this one can only be appreciated, I think, after being thoroughly familiar with Cantor's, so I don't use it in class.

RS: I see your confusion...I did write it poorly...it's changed now to reflect what I meant. Thanks!

Posted by: Polymath | August 10, 2006 at 01:06 PM

This is really nice --- it's beatiful, and I haven't seen it before.

But I think that it would not be as clear to neophytes as the classic one of first dividing all the rationals by the total of numerator and denominatior, and then, within each of those divisions, by the zize of the numerator.

e.g.

0/1 0/2 1/1 0/3 1/2 2/1

and so on.

But it's nice to have multiple proofs

This looks like a great blog, too. My first time here

Posted by: Peter | August 12, 2006 at 09:45 AM

My mind has just been blown :) That's beautiful. Everything I ever came up with, I've had to do crazy things at infinity, and hope I knew what I was doing.

Just ... infinity*awesome.

Posted by: Foxy | August 12, 2006 at 08:52 PM

That is very nice. Thank you.

An instructor once showed me another one:

Since there are at least as many ordered pairs of integers as rational numbers

and since there are at least as many rationals as naturals,

map the lattice points on the Cartesian plane (integer ordered pairs) to the naturals in a spiral

(0,0) 1

(1,0) 2

(1,1) 3

(0,1) 4

....

The visual is easy to follow (I have used this with groups of interested hs students)

Posted by: Jonathan | August 17, 2006 at 09:29 AM

Doesn't this sort of "prove" that there are actually *more* natural numbers than there are rational numbers, since the base-11 representation of many natural numbers either has some number of slashes (digits representing '10') other than 1 (e.g., 1/2/3), or, at the very least, the interpreted numerator and denominator can have common factors (e.g., 2/4)?

Posted by: Twinkle | September 29, 2006 at 12:10 PM

with infinite sets that's not how it works, exactly. this proof shows that the cardinality of the rationals is smaller than or equal to that of the positive integers. by mapping integers to their reciprocals, we can also show that the cardinality of the positive integers is smaller than or equal to that of the rationals.

the only way that both could be true is if the cardinalities are the same.

Posted by: Polymath | September 29, 2006 at 03:13 PM

None of the turmoil that routinely attends film-star existence ever seemed to visit the Astaire household.

Posted by: air jordan | February 25, 2011 at 07:52 PM

I recently came across your blog and have been reading along. I thought I would leave my first comment. I don't know what to say except that I have enjoyed reading. Nice blog. I will keep visiting this blog very often.

Posted by: justin bieber supras | October 12, 2011 at 04:39 AM

HHH Yes, the design of national policy is important, how our economic development plans for the next five years, how the implementation, how to make our economy even faster. Are designed to advance our focus to invest money in what ways it should be carefully arranged.

Posted by: supra skytop | October 20, 2011 at 03:55 AM

There's your integer associated with that rational number. QED.

Posted by: karen millen outlet | March 12, 2012 at 05:45 AM

I "like" you on Facebook. Would love these for my oldest boy!

Posted by: Red Wing Boots | March 18, 2012 at 03:55 PM

C'est dommage que plus de gens ne cherchent pas pour les journalistes en France! Peut-être que je devrais les faire pointer vers ce blog. Merci de prendre le temps de l'écrire.

Posted by: Basket Jordan Femme | April 10, 2012 at 05:09 AM

I suggest adding a "+ Google" button for the blog!

Posted by: cheap jordan retro | April 17, 2012 at 03:37 AM