From: "Dietrich J. Kappe" <kap1@wimpy.cpe.uchicago.edu>
Date: Wed, 27 Jul 94 20:25:50 PDT
To: cypherpunks@toad.com
Subject: Continum of numbers and Turing Machines
In-Reply-To: <9407280152.AA02227@snark.imsi.com>
Message-ID: <9407280325.AA23095@tao>
MIME-Version: 1.0
Content-Type: text/plain


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