Re: Cantor and the binary tree

On 24 May 2005 05:58:22 -0700, mueckenh@xxxxxxxxxxxxxxxxx wrote:

>
>Cantor and the binary tree.
>
>If we accept that, in binary digits, SUM{n = 1 ... oo} 2^-n = 0.111...
>= 1
>
>then all the real numbers of the interval [0,1] are realized as
>infinite paths of the binary tree
> .
> 0 1
>0 1 0 1
>..................
>
>too (read from top to bottom). Each number is given by a path
>stretching over infinitely many nodes (bits). All nodes (bits) of the
>tree are countable. The paths are not, according to Cantor's famous
>diagonal proof.
>
>But we find that, up to line number n, there are -1 + 2^(n+1) nodes
>whereas 2^n different paths arrive at and 2^(n+1) different paths
>spring off from line number n. Hence, in the enumerated domain, there
>is at most one more path than nodes. After leaving any finite line
>number n (if it is reasonable to make such a distinction) we can no
>longer apply these formulae. But we know that any new branching
>increases the number of paths by 1 and, by definition, the number of
>nodes by 1 too (because any branching is a node). Therefore, the number
>of paths always equals that of the nodes + 1.

All that is true for any finite binary tree, yes.

>It is simply impossible
>to assume that one of these numbers becomes uncountably infinite while
>the other remains countably infinite.

Hint: infinite sets are not the same as finite sets. What you say
is "impossible to assume" is not something we _assume_, but it's
true. And very easy to prove.

>Regards, WM


************************

David C. Ullrich
.

Relevant Pages

  • Re: Approaching the infinite binary tree
    ... But there are infinite paths in the complete binary tree that do ... It is your dogma, not ours, that you are being bit by. ... and all of them can be bijected with N. The set of even naturals, ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >>Cantor and the binary tree. ... >>to assume that one of these numbers becomes uncountably infinite ... infinite sets are not the same as finite sets. ... If no branching is possible without a new node (because a branching is ...
    (sci.math)
  • Re: An uncountable countable set
    ... Because one can biject the set of edges with the naturals and biject the ... members in any power set that in the set itself. ... represents what happens in an infinite tree. ... paths in the infinite binary tree and the power set of the set of paths, ...
    (sci.math)
  • Re: Cantor Confusion
    ... A potentially infinite quantity is always finite. ... representation has a finite index n. ... Note that also the union of all finite initial segments of N, {1, 2, 3, ... A finite binary tree is the infinite binary tree, ...
    (sci.math)
  • Re: An uncountable countable set
    ... Tony Orlow wrote: ... Every H-riffic corresponds to a node in an infinite, but countable, ... along a path in a binary tree. ... produce infinitely recursively-defined H-riffics from your existing ...
    (sci.math)
Loading