Counting Infinities

Date: 04/29/97 at 14:32:02
From: Gene Garland
Subject: Counting Infinities

Hi,
     
I was re-re-rereading Gamow's _1,2,3...Infinity_ and thought I found a 
flaw in the uncountability proof. My method of listing decimals was to 
enter the numbers in binary, writing them backwards:

  .0, .1, .01, .11, .001, .101, . . . 

I was thinking I would get all possible decimals. The counterproof of 
changing the numbers in the diagonal would produce .111111... = 1, 
which shouldn't be included anyway.
     
Since I don't really think that alph 1 > alph 0 just because we have 
ten fingers, I decided that I must not really be including all 
decimals, but I still can't see why.
     
For instance, I suspect that I don't have 1/3 in my table, but since I 
include the first 10, first 1000, and first googol digits of 1/3 
somewhere (I could tell you which lines, but you don't really care, do 
you?) in my table, it seems, (by induction?) that I should get exactly 
1/3 eventually, but I get myopic around a googolplex.

Date: 04/29/97 at 15:27:02
From: Doctor Rob
Subject: Re: Counting Infinities

Even when the proof is given writing the numbers in decimal, you have
to avoid .9999999.... = 1.0000000...., an artifact of all such
positional numeral systems.  The usual "diagonal construction" 
contains the provision that you pick for the n-th digit a digit other 
than the one in row n, column n, *and also different from 9*.  That 
avoids the ambiguity.  In binary, if you pick a digit other than the 
one in row n, column n, and also different from 1, you may have no 
choices left, as in your example.  You could modify this slightly to 
use *pairs* of bits, avoiding the pair 11 and the pair occurring in 
row n and columns 2n-1 and 2n.  This would fix up your construction.  
Since 1/3 = .01010101...., you can use this method to show that it 
cannot appear.

As to the matter of 1/3, it is not in your list.  The numbers in your
list are just those of the form a/2^b, where a is 0 or odd, and b is
positive.  1/3 cannot be written in this form, because of the 
Fundamental Theorem of Arithmetic (unique factorization into primes).  
If it could, 1/3 = a/2^b <==> 2^b = 3*a = n, and 2 and 3 prime, 
violates unique factorization of n.  You do have excellent 
approximations to 1/3, as good as you like, but you don't have 1/3 
itself.

This is somewhat like the situation where the rational numbers do not
contain sqrt(2), although they do contain excellent approximations, as
good as you like.

-Doctor Rob,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/