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


Groups > sci.logic > #164895 > unrolled thread

Distinguishing paths in the Binary Tree

Started byWM <wolfgang.mueckenheim@hs-augsburg.de>
First post2017-10-12 23:43 -0700
Last post2017-10-13 23:59 -0700
Articles 9 on this page of 29 — 6 participants

Back to article view | Back to sci.logic


Contents

  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

Page 2 of 2 — ← Prev page 1 [2]


#164983

FromJulio Di Egidio <julio@diegidio.name>
Date2017-10-14 03:30 -0700
Message-ID<a25eefd0-0bd8-42ec-8340-994927763bdf@googlegroups.com>
In reply to#164939
On Friday, October 13, 2017 at 10:01:34 PM UTC+2, WM wrote:
> Am Freitag, 13. Oktober 2017 18:25:18 UTC+2 schrieb Julio Di Egidio:
> > On Friday, October 13, 2017 at 8:43:44 AM UTC+2, WM wrote:
> > 
> > > In order to distinguish a further path from the former, there is another
> > > node necessary. At most a countable set of nodes is available.
> > 
> > Hence, at most countably many paths can be *distinguished*.
> 
> Obviously.
> 
> >  But that does
> > not in turn imply that at most countably many paths *exist*, unless we
> > first establish that there exist no more paths than we can distinguish.
> 
> What kind of existence would that be?

The kind of existence you get from any incomplete theory...  The point being
that, while the standard (IMO) is indeed broken, specifically in that it
conflates finitary and infinitary, your arguments, both against the standard
and against absolute infinity, remain all invalid.  Of course, the fact that
you deny absolute infinity against all reason and the fact that you will not
recognise the actual problem with standard set theory are directly related.

Julio

[toc] | [prev] | [next] | [standalone]


#164924

Frombursejan@gmail.com
Date2017-10-13 09:53 -0700
Message-ID<6737f985-9e60-42e9-baf1-9f421fa2d018@googlegroups.com>
In reply to#164895
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

[toc] | [prev] | [next] | [standalone]


#164940

FromWM <wolfgang.mueckenheim@hs-augsburg.de>
Date2017-10-13 13:03 -0700
Message-ID<8a744830-fb36-4540-9aa4-5653069916bb@googlegroups.com>
In reply to#164924
Am Freitag, 13. Oktober 2017 18:53:32 UTC+2 schrieb burs...@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.

That is not asked for. If they differ at level n then they differ. More is not asked for. 
> 
> 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.

That is not a paradox. A paradox is that there are really people who believe that there could be more paths than nodes. That's the only paradox.

Regards, WM

[toc] | [prev] | [next] | [standalone]


#164951

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-13 22:14 +0100
Message-ID<87r2u6g38g.fsf@bsb.me.uk>
In reply to#164895
WM <wolfgang.mueckenheim@hs-augsburg.de> writes:

> 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.

Why such a weak theorem?  You can give the exact finite number of paths that
can be 'distinguished' at level n.

> Corollary In the complete infinite Binary Tree at most countably many
> infinite paths can be distinguished.

Nonsense.  Let f(k) be (one of) the supposed bijection(s) between N and
the countable set of infinite distinguished paths.  Let D_f be the path
which differs from f(j) by "going the other way" at level j.  I.e. if
f(1) starts 1, 3 then D_f starts 1, 2.  If f(2) starts 1, 2, 4 then D_f
starts 1, 2, 5.  (The nodes at level n are numbered 2^(n-1) to 2^n - 1.)

It is easy to show by induction that D_f can b distinguished (in your
sense) from every path in the image of f.  I.e. for every k there exists
a level (it's just k) at which D_f and f(k) differ by a node being in
one and not in the other.

> Proof:

Nope.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#164970

FromWM <wolfgang.mueckenheim@hs-augsburg.de>
Date2017-10-14 00:30 -0700
Message-ID<851d6909-f3fa-4613-89cc-7299d66537f9@googlegroups.com>
In reply to#164951
Am Freitag, 13. Oktober 2017 23:14:10 UTC+2 schrieb Ben Bacarisse:
> WM <wolfgang.mueckenheim@hs-augsburg.de> writes:
> 
> > 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.
> 
> Why such a weak theorem?

In order to be easy on set theorists.

>  You can give the exact finite number of paths that
> can be 'distinguished' at level n.

Of course. The number is never infinite, let alone uncountable.


> 
> > Corollary In the complete infinite Binary Tree at most countably many
> > infinite paths can be distinguished.
> 
> Nonsense.

Obviously true.

>  Let f(k) be (one of) the supposed bijection(s) between N and
> the countable set of infinite distinguished paths.

Obviously the notion of complete mapping or finished infinite mapping or bijection between actually infinite sets is nonsense.


  Let D_f be the path
> which differs from f(j) by "going the other way" at level j.  I.e. if
> f(1) starts 1, 3 then D_f starts 1, 2.  If f(2) starts 1, 2, 4 then D_f
> starts 1, 2, 5.  (The nodes at level n are numbered 2^(n-1) to 2^n - 1.)
> 
> It is easy to show by induction that D_f can b distinguished (in your
> sense) from every path in the image of f.  I.e. for every k there exists
> a level (it's just k) at which D_f and f(k) differ by a node being in
> one and not in the other.

Nevertheless it is clear that never more than countably many paths can be distinguished.
> 
> > Proof:
> 
> Nope.

You thnk so, because your premise is nonsense. But you should at least understand that that nonsense has been contradicted.

Look: Here some set theotrists who had a weak moment have recognized the truth:

"If all nodes of a path have been deleted, that does not mean you ever deleted the path!!! You could delete all and only the finite paths from the tree, and that would delete all the nodes, yet you would never have deleted any infinite path, and they would all still exist in any case, regardless of what had been deleted! [George Greene, sci logic (22 Jul 2016)] 

"You seem to be ignoring the fact that, after you have colored a countable family of pathes, say P0, P1, …, Pn,…, there may be other paths Q that are not on this countable list but have, nevertheless, had all their nodes and edges colored. Perhaps the first node and edge of Q were also in P1, the second node and edge of Q were in P2, etc. [...] by choosing the sequence of Pn's intelligently, you can, in fact, ensure that this sort of thing happens for every path Q." [Andreas Blass, MathOverflow (3 Jul 2013)] 

It simply is impossible to give all sets in a constructive way ... and any theory, founded on this assumption, would by no means be a theory of sets. [E. Zermelo, letter to E. Artin (?) (25 May 1930)] 

Regards, WM

[toc] | [prev] | [next] | [standalone]


#165027

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-10-14 21:25 +0100
Message-ID<871sm5tr2z.fsf@bsb.me.uk>
In reply to#164970
WM <wolfgang.mueckenheim@hs-augsburg.de> writes:

> Am Freitag, 13. Oktober 2017 23:14:10 UTC+2 schrieb Ben Bacarisse:
>> WM <wolfgang.mueckenheim@hs-augsburg.de> writes:
>> 
>> > 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.
>> 
>> Why such a weak theorem?
>
> In order to be easy on set theorists.
>
>>  You can give the exact finite number of paths that
>> can be 'distinguished' at level n.
>
> Of course. The number is never infinite, let alone uncountable.
>
>
>> 
>> > Corollary In the complete infinite Binary Tree at most countably many
>> > infinite paths can be distinguished.
>> 
>> Nonsense.
>
> Obviously true.
>
>>  Let f(k) be (one of) the supposed bijection(s) between N and
>> the countable set of infinite distinguished paths.
>
> Obviously the notion of complete mapping or finished infinite mapping
> or bijection between actually infinite sets is nonsense.

This is a common trick of yours.  These are your bijections, in your
mathematics with no "complete" or "finished" infinities.  You know, the
sort you write about in your book like f(x) = x^2 for f: [0,1] ->
[0,1].  The sort that a defined in exactly the same way as they are
defined in any other book about functions.

>>   Let D_f be the path
>> which differs from f(j) by "going the other way" at level j.  I.e. if
>> f(1) starts 1, 3 then D_f starts 1, 2.  If f(2) starts 1, 2, 4 then D_f
>> starts 1, 2, 5.  (The nodes at level n are numbered 2^(n-1) to 2^n - 1.)
>> 
>> It is easy to show by induction that D_f can b distinguished (in your
>> sense) from every path in the image of f.  I.e. for every k there exists
>> a level (it's just k) at which D_f and f(k) differ by a node being in
>> one and not in the other.
>
> Nevertheless it is clear that never more than countably many paths can
> be distinguished.

"Nevertheless" is a silly thing to say in reply to a proof.

Wither induction works for your potentially infinite sets or you need to
re-write your textbook without it.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#165111

FromWM <wolfgang.mueckenheim@hs-augsburg.de>
Date2017-10-15 12:02 -0700
Message-ID<db2f3c1f-84eb-43c7-ba41-ca02ea0d606c@googlegroups.com>
In reply to#165027
Am Samstag, 14. Oktober 2017 22:25:10 UTC+2 schrieb Ben Bacarisse:
> WM <wolfgang.mueckenheim@hs-augsburg.de> writes:


> > Nevertheless it is clear that never more than countably many paths can
> > be distinguished.
> 
> "Nevertheless" is a silly thing to say in reply to a proof.

Not when the "proof" stems from a nonsense theory.

Regards, WM

[toc] | [prev] | [next] | [standalone]


#164963

FromGeorge Greene <greeneg@email.unc.edu>
Date2017-10-13 22:03 -0700
Message-ID<66d2cd84-a24f-49c7-87d5-3addc06c9b20@googlegroups.com>
In reply to#164895
On Friday, October 13, 2017 at 2:43:44 AM UTC-4, WM wrote:
> 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. 

ALL pairs of DIFFERENT paths can be distinguished at some finite level n
(if we are talking about connected paths of countably infinite length, where
every node on the path is a finite distance from the root).  It is not
possible for the paths to be "different" yet "indistinguishable".
If every node at every level n is the same then the "two" paths are ONE path,
NOT two; in other words, A=B.


 
> 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. 

Of course.

> 
> Theorem   There is no level n where uncountably many paths can be distinguished. 

This is not a theorem, you idiot.  It is not even stated coherently.
Your definition of "distinguished" IS PAIRwise.  It does not even apply
TO THREE paths, LET ALONE uncountably many.

And while your theorem is arguably true, its corollaries and implications
are not what you think they are.
~EnApq[ p and q can be distinguished ] DOES NOT MEAN THE SAME THING AS
~ApqEn[ p and q can be distinguished ].  You are just quantifier dyslexic
AS USUAL.   In order for all of uncountably many paths to be distinguished,
IT IS NOT NECESSARY for there to be any particular level at which that happens.
It is ONLY necessary that for every PAIR of paths, there be such a level.
There will be uncountably many pairs (since there are uncountably many paths,
IF you concede the EXISTENCE of [countably] infinitely long paths, and
THEY WILL ALL get distinguished.  In fact, at each level n, UNCOUNTABLY MANY
paths DO get distinguished.  For each node in the whole tree, there are uncountably many paths with that node at the root.

[toc] | [prev] | [next] | [standalone]


#164969

FromWM <wolfgang.mueckenheim@hs-augsburg.de>
Date2017-10-13 23:59 -0700
Message-ID<d7104c58-0639-4088-9574-995b59300371@googlegroups.com>
In reply to#164963
Am Samstag, 14. Oktober 2017 07:03:48 UTC+2 schrieb George Greene:
> On Friday, October 13, 2017 at 2:43:44 AM UTC-4, WM wrote:
> > 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. 
> 
> ALL pairs of DIFFERENT paths can be distinguished at some finite level n

Hence only finitely many pairs can be distingusihed.


> It is not
> possible for the paths to be "different" yet "indistinguishable".

Right.

> > 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. 
> 
> Of course.
> 
> > 
> > Theorem   There is no level n where uncountably many paths can be distinguished. 
> 
> This is not a theorem.

It is.

> Your definition of "distinguished" IS PAIRwise.

That can be applied to arbitrary sets of paths.

> It does not even apply
> TO THREE paths, LET ALONE uncountably many.

It does. All three paths differ pairwise.
> 
> And while your theorem is arguably true, its corollaries and implications
> are not what you think they are.

They are. Otherwise it would not  be necessary to state something like:

"If all nodes of a path have been deleted, that does not mean you ever deleted the path!!! You could delete all and only the finite paths from the tree, and that would delete all the nodes, yet you would never have deleted any infinite path, and they would all still exist in any case, regardless of what had been deleted! [George Greene, sci logic (22 Jul 2016)] 

Regards, WM

[toc] | [prev] | [standalone]


Page 2 of 2 — ← Prev page 1 [2]

Back to top | Article view | sci.logic


csiph-web