Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > sci.logic > #164924

Re: Distinguishing paths in the Binary Tree

Newsgroups sci.logic
Date 2017-10-13 09:53 -0700
References <642959dc-1052-4bf4-8aa0-900d83c87b74@googlegroups.com>
Message-ID <6737f985-9e60-42e9-baf1-9f421fa2d018@googlegroups.com> (permalink)
Subject Re: Distinguishing paths in the Binary Tree
From bursejan@gmail.com

Show all headers | View raw


The problem is even when two paths are different at level
n, this doesn't mean that after level n, they are constant
zero or something otherwise simple. 

This gives the following fractal paradox:

   A complete binary tree has uncountable many infinite paths.

   If you take any node in the tree, and look down from there.

   Then you see another complete binary tree.

   This other complete binary tree has also uncountable many infinite paths.

So there is another Hilbert Hotel. Not the usual countable
Hilbert Hotel. But an uncountable Hilbert Hotel. Well I
didn't really proof that the binary tree is uncountable.

http://freakymath.blogspot.ch/2011/07/uncountable-hotel.html

But the fractal structure can be easily seen,
the infinite sequences are:

  P(N), each sequence of 0 and 1 corresponds to
  a subset of N.

The sub complete binary tree is:

  { x | x is a sequence of 0 and 1 and x starts with a 
        given finite sequence p of length n} corresponds to:

  { x | x subset N and x intersect {0,..,n-1} = p }

Call the above the prefix power set P_prefix(p)(N). Now lets
proof that P(N) and P_prefix(p)(N) have the same cardinality. 
We can use the ordinary countable Hilbert Hotel for that.

By the ordinary Hilbert hotel, N and {n, n+1, ...} have
the same cardinality. {n, n+1, ...} being one of the favorite
sets of WM, he often uses it in argumemts.

The bijective mapping between N and {n, n+1, ...} is:

   f(x) = x+n

Now we can rewrite P_prefix(p)(N) as follows:

   P_prefix(p)(N) = {p union y | y subset {n,n+1,...} }

          = {p} Union {y | y subset {n,n+1,..} }

          = {p} Union P(f(N))
  
But because of the countable Hilbert hotel bijection f(x),
we have of course that P(N) and P(f(N)) have the same
cardinality, and prepending a disjoint singleton doesn't
change this.

Am Freitag, 13. Oktober 2017 08:43:44 UTC+2 schrieb WM:
> Definition: Two infinite paths A and B can be distinguished at level n <==> There are two different nodes a and b at level n, such that a is in A and not in B, and b is in B and not in A. 
> 
> Definition: Two infinite paths A and B are different <==> There exists a level n such that A and B can be distinguished at level n. 
> 
> Theorem   There is no level n where uncountably many paths can be distinguished. 
> 
> Corollary   In the complete infinite Binary Tree at most countably many infinite paths can be distinguished. 
> 
> Proof: In order to distinguish path A from n paths P1, P2, ..., Pn we need n nodes. It cannot be excluded, that one node a of A is sufficient, to distinguish A from all P1, P2, ..., Pn, but these are not n different paths unless there are nodes that distinguish P1 from P2 to Pn, and P2 from P3 to Pn and so on. In total n - 1 nodes are required to distinguish n paths P1, P2, ..., Pn.
> 
> In order to distinguish a further path from the former, there is another node necessary. At most a countable set of nodes is available.
> 
> Regards, WM

Back to sci.logic | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-12 23:43 -0700
  Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-13 02:24 -0700
    Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-13 02:48 -0700
      Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-13 03:45 -0700
        Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-13 09:54 -0700
          Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-13 10:13 -0700
            Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-13 10:21 -0700
              Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-13 10:39 -0700
                Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-13 10:47 -0700
                Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-14 08:04 -0700
                Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-14 09:26 -0700
                Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-14 09:44 -0700
                Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-14 10:25 -0700
                Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-14 12:06 -0700
                Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-14 12:50 -0700
                Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-14 12:59 -0700
        Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-13 12:58 -0700
          Re: Distinguishing paths in the Binary Tree shionoro@googlemail.com - 2017-10-14 08:06 -0700
  Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-13 09:25 -0700
    Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-13 13:01 -0700
      Re: Distinguishing paths in the Binary Tree Julio Di Egidio <julio@diegidio.name> - 2017-10-14 03:30 -0700
  Re: Distinguishing paths in the Binary Tree bursejan@gmail.com - 2017-10-13 09:53 -0700
    Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-13 13:03 -0700
  Re: Distinguishing paths in the Binary Tree Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-13 22:14 +0100
    Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-14 00:30 -0700
      Re: Distinguishing paths in the Binary Tree Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-10-14 21:25 +0100
        Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-15 12:02 -0700
  Re: Distinguishing paths in the Binary Tree George Greene <greeneg@email.unc.edu> - 2017-10-13 22:03 -0700
    Re: Distinguishing paths in the Binary Tree WM <wolfgang.mueckenheim@hs-augsburg.de> - 2017-10-13 23:59 -0700

csiph-web