Re: Another set with cardinality |Z|

From: Eray Ozkural exa (erayo_at_bilkent.edu.tr)
Date: 09/23/04 

Date: 23 Sep 2004 07:40:26 -0700

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]

Thank you for your answer.

Regards, 

--
Eray Ozkural
PS: For entertaining myself, I'm writing a small draft called
"Algorithmic Set Theory" in which I try to give programmatic
descriptions to numbers and arithmetic operations, and hence this
question.

Relevant Pages

  • Comparing 2 Infinite Trees
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)
  • Ultimate, God-like Algorithm
    ... An infinite tree is described by including "self references" in place ... self reference makes the tree infinite. ... believe that I have an algorithm that can show equality in m * n time. ...
    (sci.math)
  • 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 ...
    (comp.theory)