Re: Another set with cardinality |Z|

From: LarryLard (larrylard_at_hotmail.com)
Date: 09/24/04 

Date: 24 Sep 2004 02:28:48 -0700

erayo@bilkent.edu.tr (Eray Ozkural exa) wrote in message news:<fa69ae35.0409230640.82b10f9@posting.google.com>...
> israel@math.ubc.ca (Robert Israel) wrote in message news:<citd77$3o0$1@nntp.itservices.ubc.ca>...
> > In article <fa69ae35.0409221823.682ae186@posting.google.com>,
> > Eray Ozkural exa <erayo@bilkent.edu.tr> wrote:
> > >Let's have an algorithm that starts with
> > >0.1 in binary, and constructs a tree in breadth-first fashion
>
> > > 0.1
> > > 0.01 0.11
> > >0.001 0.011....
>
> > >You get the idea... It's obvious that this tree has the same
> > >cardinality as Z, since this is a nonhalting algorithm (or since I can
> > >give an integer to every node, etc.) Now, I want to prove that such a
> > >subdivision procedure cannot generate all x in (0,1) in an intuitive
> > >way. Is the easiest method proof by contradiction?
> >
> > Hint: can you generate 1/3?
>
> Hmm. In binary, it will go like
>
> 0.01010101...
>
> You mean that it cannot generate because this rational number has an
> infinite binary expansion. I am not sure if that is an intuitively
> acceptable explanation, though, simply because of the fact that the
> tree has an infinite number of nodes, e.g. an infinite depth,
> therefore this number is computed in the limit.
>
> It is obvious that any number with an infinitely long binary expansion
> will not have been generated by this procedure at step k < infinity.
> As you can see, I'm just trying to give a more intuitive proof than
> Cantor's. It seems to me, with my very limited knowledge and a sloppy
> computer scientist's point of view, that this was indeed the
> archetypal idea, the premise that the whole infinite depth tree, with
> an infinite number of nodes, does not contain any labels with an
> infinite binary expansion.
>
> I'm still trying to find a reason "why" that should be true. Could we
> construct a _contradiction_ by assuming the negation of this premise
> (namely that the labels of such a tree can have infinite binary
> expansion!) ? That would be very interesting for me. [Because we'd
> have an elegant proof, I think]

OK try this one on for size.

Suppose we have a node N that is labelled 0.01010101...

The parent of this node is obviously labelled 0.101010101...

And the parent of THIS node is then labelled 0.01010101....

But this is the same as the label on N, when it is clear by the
construction method that no label can appear twice. Contradiction!

How does that grab you?

(
and if that works, consider this:
suppose we DO have a natural number n with binary representation
....10101010
divide by 4
n/4 = ....101010.10
subtract n
n/4 - n = .10
switch to decimal
-0.75n = 0.5
n = -2/3
worried yet?
) 

-- 
Larry Lard
Replies to group please

Relevant Pages

  • Re: Another set with cardinality |Z|
    ... >>Let's have an algorithm that starts with ... infinite binary expansion. ... tree has an infinite number of nodes, e.g. an infinite depth, ... It is obvious that any number with an infinitely long binary expansion ...
    (comp.theory)
  • Re: Another set with cardinality |Z|
    ... >>Let's have an algorithm that starts with ... infinite binary expansion. ... tree has an infinite number of nodes, e.g. an infinite depth, ... It is obvious that any number with an infinitely long binary expansion ...
    (sci.math)
  • Re: Bit-permutation function and Cantor Dust?
    ... Obtain the binary expansion of the fractional part of x (infinitely ... if it "terminates" then just append an infinite ... copies of a Cantor set) that has been skewed and stretched or rotated. ... which is the middle-halves set you describe. ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... > infinite binary expansion. ... > tree has an infinite number of nodes, e.g. an infinite depth, ... > It is obvious that any number with an infinitely long binary expansion ... > (namely that the labels of such a tree can have infinite binary ...
    (sci.math)
  • Re: Dial 999 for the real number line
    ... such a table represents all the reals. ... => the binary expansion of every real number ends with an infinite ... infinite sequence: ...
    (sci.math)