Countability

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.

Comments

[Julian M Bucknall]

Beautiful... I'm just gobsmacked.

[RS]

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?

[Polymath]

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.

[Coconuts]

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?

[Davis]

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

[RS]

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?

[Polymath]

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!

[Peter]

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

[Foxy]

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.

[Jonathan]

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)

[Twinkle]

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)?

[Polymath]

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.

[air jordan]

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

[justin bieber supras]

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.

[supra skytop]

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.

[karen millen outlet]

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

[Red Wing Boots]

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

[Basket Jordan Femme]

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.

[cheap jordan retro]

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