Re: Cantor and the binary tree

In article <1117983211.825565.129420@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
mueckenh@xxxxxxxxxxxxxxxxx wrote:

>
>
> imaginatorium@xxxxxxxxxxxxx wrote:
> > mueckenh@xxxxxxxxxxxxxxxxx wrote:
> >
> > > We have a law yielding all possible infinite strings of bits.
> > > We have a law connecting each spring-off, i.e., the source of a newly
> > > separated path with a node B:
> > > /
> > > B
> > > /\
> >
> > I don't understand this. As far as I can see, each node 'B' has two
> > branches from it, to left and to right, and neither identifies a single
> > path. Rather, each one leads to another (unending, infinite) subtree.
>
> One path enters that node, such that one path is newly created by the
> node. It does no matter which one is considered as the new one.
> Further, you are right, a whole new tree as large as he old one is
> created by each node. But for this new tree and each of its nodes the
> same holds as for the old one.
> >
> > > This is the basic element of the tree and does nowhere change. Hence it
> > > holds all over the tree. It yields a one-to-one relation between nodes
> > > and paths. Nobody can reasonably even r[a]ise the question whether there
> > > could be more paths than nodes.
> >
> > On the contrary, I raise it. In maths, if the answer to any question is
> > obvious, it can be dealt with quickly. Anyway, we could identify with
> > this node the path going right, and subsequently always going left. In
> > this way we can identify every node with a single path, showing that
> > there cannot be more nodes than paths, but not showing the reverse
> > (because we haven't mapped every path to a node in this way).
>
> Where should the other paths come into being? Where should they be
> separated, if not n a node?
>
> > This does
> > not prove that there is no 1-1 mapping, but if there is one, you still
> > have work to do to show it. (Other considerations of course show that
> > this is indeed impossible.)
>
> It is my purpose to show that there is no consistent math in the
> infinite. Therefore other consideration may yield other results.
> >
> > > ... And if it is meaningful to talk about
> > > infinity and to count infinity, then it is absolutely clear that nodes
> > > and paths have same number.
> >
> > So false. It certainly isn't clear.
>
> If you would not know anything of Cantor, I am sure you would not
> hesitate a second to agree.
> >
> > > Gottfried Helms wrote: [if your quoting levels are reliable]
> > > > The concept "number of" may be assigned to describe an (important)
> > > > property of a finite set, but if we deal with mathematical objects,
> > > > which are constructed to be infinite, it is better to switch to the
> > > > terminus "cardinality" (or maybe a better one), to not apriori throw
> > > > away the ability to include uncountable(*1) infinities in our
> > > > considerations.
> > >
> > > The idea of a bijection of a set with N is a convincing one, in many
> > > respects. But the idea of considering the basic element
> > > /
> > > B
> > > /\
> > > of a tree is at least as convincing. To do the last step, we could even
> > > neglect the terminus "node". Then I assert: There are not more
> > > separated paths in the tree than paths which separate themselves
> > > somewhere in the tree. Set theorists say: There are more separated
> > > paths in the tree than are separated in the tree.
> >
> > Do you have any proper definitions for this "separating" stuff?
>
> It is indeed difficult for me to see where you see problems. Above you
> see the fundamental element of the tree. One path coming in is
> separated into two paths going out. Each element increases the number
> of separately visible paths by 1. You say that the tree contains
> countably many of these elements but uncountably many paths. I think,
> that cannot be mantained. How would you try to explain it?

How does WM explain away the following:

Assume a maximal binary tree in which each node is a parent with
left-child and a rght-child nodes, with one unique root node, and no
maximal path having any terminal or leaf node.

(1) To show the set of nodes has a bijection to N:

Given any node, let the root node be labeled 1 and thereafter, on the
path connecting the root to the given node let each left branch in that
path be labeled 0 and each right branch in that path labeled 1.
Then the given node is represented by the binary integer formed by the
finite sequence of binary digits taken in order along the finite
sub-path from root to the given node.

This shows that for each node there is a unique (binary) natural.

And if the binary tree is maximal as described, for each natural, there
will be a node, by following the appropriate left to right branches, as
indicated by the 0 or 1 digits, from the root to some node finitely many
branches from the root.

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

(2) To show that there is a bijection between the set of all maximal
(unbounded) paths of such a binary tree and P(N), the set of all subsets
of N.

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

It is easily seen that
(a) Every maximal path defines a subset of N,
(b) Different maximal paths define different subsets of N,
(c) And every subset of N is created by some unique maximal 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.
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... to do with paths on a tree, ... > nothing to do with the number of unending paths. ... Actually, if you have an infinite binary tree, with all paths unending, it's ...
    (sci.math)
  • Re: Binary Tree and Pairs of Nodes
    ... was an infinite countable set of nodes" and "iff infinite sets could ... entire infinite complete binary tree. ... This shows that there is no set of all reals. ...
    (sci.logic)
  • Re: Cantor and the binary tree
    ... I consider an infinite tree. ... If you mean that there is a bijection between paths and reals, ... Assume a binary tree in which each node is a parent and has a left-child ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... Now you are talking about an ever increasing finite tree, ... If you are talking about an infinite tree it may be ... And if the binary tree is maximal, having no leaf nodes, there will also ... Thus I have constructed a bijection from the set of infinite paths to ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... >>> For the infinite strings needed to represent paths, ... with the direction being away from the root node. ... A maximal path is one which starts at the root ... > In an infinite binary tree every maximal ...
    (sci.math)