Beautiful... I'm just gobsmacked.

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?

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.

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?

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

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?

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!

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

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.

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)

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

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.

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

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.

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.

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

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

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.

The comments to this entry are closed.

## Other blogs I like

• EvolutionBlog
He writes mostly about evolution, but he's a math guy.