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