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


Groups > sci.logic > #164951

Re: Distinguishing paths in the Binary Tree

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups sci.logic
Subject Re: Distinguishing paths in the Binary Tree
Date 2017-10-13 22:14 +0100
Organization A noiseless patient Spider
Message-ID <87r2u6g38g.fsf@bsb.me.uk> (permalink)
References <642959dc-1052-4bf4-8aa0-900d83c87b74@googlegroups.com>

Show all headers | View raw


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.

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