Re: Another set with cardinality |Z|

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

Date: 25 Sep 2004 20:09:21 -0700

Jean-Marc Bourguet <jm@bourguet.org> wrote in message news:<873c16ux10.fsf@news.bourguet.org>...
> erayo@bilkent.edu.tr (Eray Ozkural exa) writes:
>
> [...]
> > 1. Hmm. Yes, I understand all that, but I'm trying to
> > apply the notion of computability in the limit, e.g. a
> > nonhalting procedure that generates digits of pi one by
> > one, each one in a finite number of steps, is said to
> > compute pi in the limit which has infinitely many
> > digits... [*]
>
> When you compute the limit of a serie, you get to choose the
> step *after* having been given the maximum allowed distance,
> exactly like in the infinite depth.

Hmm. I took the limiting tree as in Robert Low's post, e.g. the union
of all trees at all steps of the computation... Am I wrong in thinking
that there is a unique limiting tree?

What's the "maximum allowed distance" here, for computation in the
limit?

> [...]
> > 2. Another problem that I alluded to, but did not make
> > quite explicit it seems. You say that you accept that the
> > tree has infinite depth, e.g. depth(T) = |Z|. OK. Let's go
> > with that. Then, the tree has 2^|Z| = |R|
> > vertices. Contradiction! [+]
>
> Where? You should reread about Cantor's ordinal and cardinal
> numbers and then come back.

What is 2^|Z| (number of vertices as a function of the depth of the
tree)?

Is not that the same as |P(Z)|=c (continuum)? Am I missing some basic
fact here?

If it were |Z|^2, that would indeed be |Z|. But I cannot see my
mistake above. Please elaborate.

-------------------------------------------------------------------------

Here is an alternative approach.

Now, if we consider an even simpler tree:
           1
      0 1
   0 1 0 1 ...

And talk about a function l(.) of paths from the root, which simply
concatenates all the digits from the root. Can this function represent
infinite bit strings or not? We just said that the depth of the
limiting tree is |Z|. Now, let's pick an infinite path p in this nice
infinite limiting tree. Then, I expect that l(p) will be an infinite
bit string. Right or wrong?

Regards, 

--
Eray Ozkural

Relevant Pages

  • Re: Another set with cardinality |Z|
    ... > exactly like in the infinite depth. ... I took the limiting tree as in Robert Low's post, ... concatenates all the digits from the root. ... infinite bit strings or not? ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... a leaf is the number of bits in the binary expansion of the number ... >countably infinite as you seem to suggest above? ... The limiting tree has infinite depth in the sense that ... there is no upper limit to the leaf-root distance. ...
    (comp.theory)
  • Re: Another set with cardinality |Z|
    ... a leaf is the number of bits in the binary expansion of the number ... >countably infinite as you seem to suggest above? ... The limiting tree has infinite depth in the sense that ... there is no upper limit to the leaf-root distance. ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... Eray "are there integers with an infinite number of digits?" ... > what the limiting tree is. ... note especially the blurb on entire tree. ...
    (sci.math)
  • Re: Another set with cardinality |Z|
    ... let's pick an infinite path p in this nice infinite ... >> limiting tree. ... Hmm, so in infinite graph theory, all paths are finite? ... Regards, ...
    (comp.theory)