« Yes, I Do Read Books. | Main | You Go, Brother! »

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!

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

The .999... Posts That Made Me Briefly Famous

My Feeble Attempts at Humor

Other blogs I like

  • EvolutionBlog
    He writes mostly about evolution, but he's a math guy.
  • Good Math, Bad Math
    Scienceblogs finally has a math guy!
  • Kung Fu Monkey
    A very smart, high-profile screen writer and comic with sensible politics and an amazing ability to rant
  • Math Spectrometer
    My ideas about life, teaching, and politics
  • Pharyngula
    Biology, lefty politics, and strident anti-Intelligent Design
Blog powered by Typepad