Re: Cantor and the binary tree

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

> Gottfried Helms wrote:
>
> > I always understood "transfinite number" not being a "count-of-elements"
> > (which would be impossible with uncountable sets) but being an index of
> > the *type* of infinity (already in mind, that that types have
> > somehow an order).
>
> It was Cantor's pride to have extended the domain of numbers having
> found arithmetic laws connecting the new numbers, the second (zweite
> Zahlenklasse) and even higher classes of numbers, as he expressed it.
>
> > in the -possible- case, that your tree represents a rule to describe
> > a continuum(*1): since then it is referring to a "number of all nodes",
> > which cannot be given, if it possibly is "un-countable".
>
> 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
> /\
> 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 rise the question whether there
> could be more paths than nodes. 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.


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.


(1) Card(N) < Card(P(N)) because of {n e N: n ~e f(n)}, and it is clear
from what I have posted that, despite WM's objections, for a maximal
binary tree, in which all maximal paths are without terminal or leaf
nodes and every node is a parent node:
(2) Card(the set of nodes) = Card(N) and
(3) Card(the set of maximal paths) = Card(P(N))
.

Relevant Pages

  • Re: Cantor and the binary tree
    ... 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 ... And if the binary tree is maximal as described, for each natural, there ... Given any maximal path in this maximal binary tree, ...
    (sci.math)
  • Re: abundance of irrationals!)
    ... >> Each node can be represented by a finite string of zeros and ones, ... A maximal path is one which starts at the root ... In an infinite binary tree every maximal ...
    (sci.math)
  • Re: Cantor and the binary tree
    ... >>> You have shown that set theory is inconsistent. ... > The basic element of the binary tree is the branching where a path is ... Given any node, let the root node be labeled 1 and thereafter, on the ... Given any maximal path in this maximal binary tree, ...
    (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)
  • Re: Cantor and the binary tree
    ... >>> number of separated paths is equal to the number of branchings. ... > more paths than paths origins? ... In a maximal binary tree, or, indeed, any tree, every maximal path ...
    (sci.math)