-----BEGIN PGP SIGNED MESSAGE----- Perry E. Metzger writes: [Countability proofs deleted...] For simplicity, lets just try to map the reals between zero and one to the integers, and lets consider them expressed as binary numbers. Imagine that I had built a mapping between this subset of the reals and the positive integers. Any such mapping implies a list, that is, that I could build a table like 1 .1010101101010010010010010101001..... 2 .0100001010100010100101001001010010... 3. .11000101001010110100010100010101001.... etc. I can now construct a number that is not in the table. Take the first binary digit from the first number in the table, and complement it. That is the first digit in my constructed number. Take the second digit from the second number and complement it -- that is the second digit of the constructed number. Add in the complement of the third digit of the third, the fourth digit of the fourth, etc. The number I have just constructed can't be the first number in the imaginary table because the first digit didn't match. It can't be the second because the second didn't match. It can't be the third because the third doesn't match. Indeed, it can't be any of them. Thus, you can't map the reals to the integers. The reals are thus in some sense a "bigger" infinite set than the integers. Small but important correction: the number that you contructed may in fact be a binary equivalent to one already in the list. Example: .0111111... .1000000... Claim: For a given real x, there exist at most a finite number of equivalent binary representations. (In fact, just 2.) Proof: Left as an excercise. I think everyone can see how to splice this little lemma into the proof. Of course, the proof isn't nearly as clean as before, so it may take more than 5 minutes for a 12 year old (or 12 minutes for a 5 year old :-). Dietrich Kappe kap1@wimpy.cpe.uchicago.edu - - -finger for PGP public key- -----BEGIN PGP SIGNATURE----- Version: 2.6 iQCVAwUBLjck/zdLyfjamMpJAQHt8AP+LmFAQK2KpjcxrEq8jhW2eUM/qNqVVHsu j53E0TTwfWGB1ih7KttCY/0GrwpeW1DGGdhp6iLTjCwqW/bE52voY/PdmlqTc/PB yjwhC9Tw/Mb+gKUleh45JW5f8szhAxv6tGYCLLitdJ3TQHNkJM520RhuJGskPJxB DUkqzPcL4Yk= =a2fn -----END PGP SIGNATURE-----