Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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 |
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
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