09 June 2009

When do you learn that the rationals are countable, and the reals aren't?

I'm currently teaching a course "Ideas in Mathematics" in our summer session. This is a course generally taken by students not in technical fields; quickly speaking, my syllabus is some basic number theory, different notions of infinity, some bits of geometry (polyhedra, letting them know that there is such a thing as non-Euclidean geometry, etc.), fractals and chaos, and a smattering of probability. This is a course that's not a prerequisite for anything and the students aren't going into fields where they'll need math, so I, like a lot of other people teaching this class, take the approach of showing them that "math is beautiful" rather than that "math is useful".

So today I'm showing my students that the rationals are countable, first by the standard proof and then by the superior Calkin-Wilf proof. I find the Calkin-Wilf proof aesthetically superior because the "standard" proof, in my opinion, is "really" a proof that the set of pairs of natural numbers is countable; we then just cross off the pairs which aren't in lowest terms as a sort of afterthought. As a result, it's difficult to answer questions like "what's the 1000th rational number in the `standard' enumeration?". Then I will show them that the reals are uncountable, using Cantor's diagonalization argument.

While preparing today's class, I realized that I don't know when I learned that the rationals are countable and the reals are uncountable. Is this even part of the "standard" curriculum for math majors? These feel like facts that I have always known; presumably I picked them up from some popular mathematics book at an early age. Do any of you remember when you learned this?

28 comments:

jason murphy said...

I'm pretty sure I learned this during my first real analysis course.

bk drinkwater said...

First picked it up in Penrose's The Emporer's New Mind; I was youngish (about 12). I wasn't precocious or anything of the sort: it was just a book lying around.

The bit on uncountability was the only part of the book I actually understood. The shock I got on reading that chapter was what turned me on to math.

Then, I learned the fact again—uncountably many times—at uni (in phil logic papers, math logic papers and DM papers).

intrinsicallyknotted said...

My college had a course called Intro to Logic and Set Theory, which was a prerequisite for all "higher-level" math courses--the ones involving proofs. Most math majors would take it freshman year, as I did. At the end of the class when we talked about infinite sets, that's when we did both proofs.

I've subsequently explained it to others, in particular a high school student I was tutoring, who told me in the following tutoring session that she'd been explaining this crazy thing to all of her friends, and "the weird thing is, I actually understand it!"

Anonymous said...

In High School (and middle school, but I don't think that's when I took the relevant class) I went to a thing the weekend before Thanksgiving taught by MIT undergraduates which would give a bunch of quick introductions to all sorts of neat topics, and there was a general sort of "weird math" class which touched upon some set theory stuff. Maybe tenth grade?

Todd Trimble said...

I remember vividly. I was 15, and looking around at universities to go to, among them Duke. I had had an interview with a professor there (Seth Warner), who kindly gave me a copy of his textbook on Algebra.

My brother was avidly into golf, and as part of the trip south we went to the Masters Tournament in Georgia. I wasn't avidly into golf, and spent most of the time on the links with my nose in the Algebra book. It was there that I first learned this fact (maybe it wasn't the reals, but the power set at first, and the reals came soon after). I remember this so vividly because I was utterly blown away that there could be degrees of infinity. It counts as one of the big intellectual experiences of my early teen years. (But eclipsed in the excitement it gave me by my accidental discovery of Euler's fantastic formula

e^{ix} = cos(x) + i sin(x)

which I experienced as an enormous revelation, and a huge relief. That was when I was 14.)

It's experiences like that that definitely decide one to pursue mathematics. We're junkies for that sort of experience!

Yan Zhang said...

It is a popular real analysis topic near the beginning, but yes, you forget about ever having done it there because you read about it in some popular book first. In my case, it was "One, Two, Three.. Infinity" by George Gamow.

I still have very fond memories of it, it introduced basic math, cryptography, and chemistry in a very nicely streamlined yet frivolous manner.

melted-snowball said...

I was in elementary school, maybe 10? I think it was in some book my dad gave me.

By contrast, I learned about undecidability (which I teach together with the uncountability of the reals) in college. At a frat party.

Michael Lugo said...

I would find that utterly ridiculous, except I know where you went to college.

Anonymous said...

I first heard that the reals were not countable from a coworker.

I still don't "understand" it. I guess the intuitionist in me thinks that the proof is bogus.

Anonymous said...

during the first year of studying maths at a uk uni

Sachi said...

Learned about it in middle school, I think from Charles Seife 'Zero, Biography of a Dangerous Idea' but possibly another book. Since then have showed it to more than one amazed friend or classmate when the idea of bigger or smaller infinities is necessitated and they start looking at me like I'm crazy but eventually accept it. I feel like it's one of those things that everyone should learn early on as a 'math is beautiful' thing—it certainly doesn't require lots of advanced math.

Qiaochu said...

Popular math book in middle school; I don't remember the exact title. I picked up rather a lot of folklore from such books (Pickover's "Wonder of Numbers," for example) before learning it properly. The Seife book Sachi mentions is another great one, as is "Euclid's Window."

Blaise Pascal said...

When I was 10, my father assigned me "Gödel, Escher, Bach" as a summer reading project. I believe it's in there somewhere.

Sue VanHattum said...

I have no idea when I first saw it, but if it's in "One, Two, Three.. Infinity" by George Gamow, as someone mentioned, I probably saw that in my early teens.

A great book for sharing ideas about infinity with kids (maybe even adults) is The Cat in Numberland. It's hard to get, unfortunately. It has countability of the 'fractions', but doesn't talk about uncountability of the reals.

unapologetic said...

No clue when I learned it. It was definitely by the end of elementary school.

Veky said...

High school, from a guy that I shared a room with, on some competition (I think it was physics:).

Of course, some people _never_ learn it: http://front.math.ucdavis.edu/math.GM/0403169 ;-)

.mau. said...

I have a dim recollection that it was enunciated in high school (but in Italy programs are different), but I am not sure because I read elsewhere when I was 14 or so.

Jr said...

In high school when I was 17 or something. I attended a special group for interested students taught by a university teacher and that is when I learned it.

Anonymous said...

Be careful with the Calkin-Wilf bijection. It's very beautiful, but it can leave beginners with the wrong impression. The key lesson about the countability of the rationals it that it is obvious and can be done in any number of variant ways (just remember the main idea and then follow your nose to work out the details). By contrast, the Calkin-Wilf bijection is delicate and surprising. It will take you five much longer to explain it as the usual method, and by the time you're done it will occupy a disproportionately large part of your students' memories of the lesson.

Flooey said...

Similarly to a lot of folks, the first that I remember being taught it in school was in my first analysis course, but I'm fairly certain I already knew it at that point. When I picked it up, though, I can't recall.

Can D said...

I learned it from David Foster Wallace's book Everything and More at around 17. Very good popular math book that could be used in a course like the one you describe.

Maria H. Andersen said...

I learned it in my first year of grad school. I try to always have time to teach it to my Calc II students. It's a bit off-topic, but fun and challenging for them.

Mark Dominus said...

I think I learned it when I was a kid from Mathematics and the Imagination by Kastner and Newman.

But I'm pretty sure it's also at the beginning of the little Rudin analysis book, which is a pretty common text for third-year analysis classes.

Anna said...

First grade of high school.

But when I was a kid, my dad told me the story of two infinite gropus of tourists that got booked in one infinite hotel and the staff moved the tourist from room n to room 2n and there was room for everyone.

Jacob said...

Oddly, I never encountered these proofs during my undergrad math major. (American State Uni.)

3rd year I took a logic course required for philo grad students, and that's the first and only place I've done this work in an academic setting.

Thank you Professor Tennant.

Kooglesmith said...

b

vlorbik said...

can't remember.
great thread.

jd2718 said...

I don't recall where I learned it, but I sat in a set theory class where it was presented, and several of my classmates acted as if they had not previously encountered it.

Jonathan