Re: Cantor and the binary tree

In article <85acmheyyy.fsf@xxxxxxxxxxxxxx>, David Kastrup <dak@xxxxxxx>
wrote:

> mueckenh@xxxxxxxxxxxxxxxxx writes:
>
> > David Kastrup wrote:
> >> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> writes:
> >>
> >> > Virgil said:
> >> >> In article <MPG.1cffa7b573ce1926989d33@xxxxxxxxxxxxxxxxxxxxxxxxx>,
> >> >> Tony Orlow (aeo6) <aeo6@xxxxxxxxxxx> wrote:
> >> >>
> >> >> > > In an infinite tree there are as many *finite* paths as nodes.
> >> >> > > Again, I think you can count on general agreement (although
> >> >> > > there will be some grumbling that there are infinite numbers of
> >> >> > > both and I may be off by a factor of 2 but let's forget about
> >> >> > > that).
> >> >> >
> >> >> > If "there are as many *finite* paths as nodes", then what do the
> >> >> > infinite paths consist of? Don't they have nodes as well? Are
> >> >> > there infinite paths, if all the nodes are used up in the finite
> >> >> > paths?
> >> >>
> >> >> We can pair off the finite paths with their terminal nodes, but
> >> >> infinite paths do not have terminal nodes. If we identify
> >> >> left-child branches with zeros and right-child branches with ones,
> >> >> each infinite path can be matched with an infinite string of zeros
> >> >> and ones.
> >> > Well, that makes the infinite paths rather countable, doesn't it,
> >>
> >> It doesn't, since the set of non-terminating binary strings is not
> >> countable.
> >
> > That is a mere statement withot any backing, not even from Cantor,
> > because a tree is not a list. (Therefore I choose it.)
>
> But that tree is isomorphic to the binary expansions of numbers
> between 0 and 1, with the single difference that 0.010000... and
> 0.0011111... and similar path expansions denote _different_ paths.
> Which actually makes the diagonal argument easier.
>
> >> > since there is easily a bijection between binary strings and
> >> > integers.
> >>
> >> Uh, no. Not unless you are only talking about terminating binary
> >> strings.
> >
> > Unfounded assertions are of no value.
>
> Quite so, which is why the "there is easily a bijection" idiocy is
> completely without value.

But I later supplied that easy bijection to "found" my assertion.

<QUOTE>>

> In a maximal binary tree, the set of nodes easily bijects to N and the
> > number of unleafed paths easily bijects to P(N), and Card(N) < Card(P(N))
> >
> Show me the proof so I can show you the mistake. It probably has to do with
> some unjustified assumption about your imaginary "unleafed paths". How do you
> get a path without a node at the end of it anyway?

One gets a path with no last node the same way one gets a binary or
decimal fraction with no last digit.

(1) Given any finite path, let the root node be labeled 1 and
thereafter, let each left node be labeled 0 and each right node labeled
1.
Then the last node in that finite path is represented by the binary
integer of the digits for all those nodes taken in order from root to
the node in question.

And if the binary tree is maximal, having no leaf nodes, there will also
be a node for each binary integer.

Thus, I have created a bijection from the set of nodes to the set of
naturals, N = {1,2,3,...}. QED

(2) Given any infinite path in a maximal binary tree,
create a subset S of N as follows:
if the nth child node of the tree is on a right branch from
its parent node, n is to b a member of s, but if on a left branch,
n is to be excluded.

It is easily seen that
every infinite path defines a subset of N,
different infinite paths define different subset of N
every subset of N is created by some infinite path

Thus I have constructed a bijection from the set of infinite paths to
the set of all subsets of N, i.e., to P(N). QED.

Both bijections constructed as requested.

<\QUOTE>
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... >>> In a maximal binary tree, the set of nodes easily bijects to N and the ... > Given any infinite path in a maximal binary tree, ... > Thus I have constructed a bijection from the set of infinite paths to ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >> the root node, but no node is the end node of an infinite path from the ... And if the binary tree is maximal, having no leaf nodes, there will also ... I have created a bijection from the set of nodes to the set of ... Given any infinite path in a maximal binary tree, ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >> Then the last node in that finite path is represented by the binary ... >> And if the binary tree is maximal, having no leaf nodes, there will also ... >> Given any infinite path in a maximal binary tree, ... >> Thus I have constructed a bijection from the set of infinite paths to ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >> In a maximal binary tree, the set of nodes easily bijects to N and the ... And if the binary tree is maximal, having no leaf nodes, there will also ... Given any infinite path in a maximal binary tree, ...
    (sci.math)
  • Re: Binary Tree and Pairs of Nodes
    ... It differs from the path you map to 0 digit-position 0. ... that every infinite path that exists ... in the infinite binary tree has one node mapped onto it. ...
    (sci.logic)