The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
Associated Topics || Dr. Math Home || Search Dr. Math

Counting Infinities

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

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 

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!   
Associated Topics:
College Number Theory

Search the Dr. Math Library:

Find items containing (put spaces between keywords):
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.