Date: Mar 24, 2013 7:48 PM
Author: ross.finlayson@gmail.com
Subject: Re: Matheology § 224

On Mar 24, 4:16 pm, Virgil <vir...@ligriv.com> wrote:
> In article
> <ab63154d-ab7e-4a03-be1b-17ac93226...@hd10g2000pbc.googlegroups.com>,
>  "Ross A. Finlayson" <ross.finlay...@gmail.com> wrote:
>
>
>
>
>
>
>
>
>

> > On Mar 24, 2:51 pm, fom <fomJ...@nyms.net> wrote:
> > > On 3/24/2013 4:34 PM, WM wrote:
>
> > > > On 24 Mrz., 21:29, Virgil <vir...@ligriv.com> wrote:
> > > >> In article
> > > >> <729f073f-8948-4eb9-991a-2bd249ac5...@c6g2000yqh.googlegroups.com>,

>
> > > >> A binary tree that contains one path of each positive natural number
> > > >> length will necessarily also contain exactly one path of infinite length.

>
> > > > Like the sequence
> > > > 0.1
> > > > 0.11
> > > > 0.111
> > > > ...
> > > > that necessarily also contains its limit?

>
> > A binary tree that contains one path, of all zero-branches, of each
> > finite length, will necessarily contain a path of 0-branches of
> > infinite length.

>
> Better is
>
>     root
>       |  \
>       0   1
>       |  \
>       0   1
>       |  \
>       0   1
>       |  \
>       0   1
>       |  \
>       0   1
>       |  \
>       0   1
>       |  \
>       0   1
>       |  \
>
>   And so on
>
> --



A binary tree, of all 0's or 1's (0- or 1- branches) with paths of
each finite length, has a path of infinite length: that is a subtree
of the intersection[*], of the finite paths. A tree with paths of
each length n having 0's except the last 1 shows a binary tree with an
infinite path: that is a subtree of the union of the finite paths.
As a space-complexity problem it's simpler to maintain the
intersection[*] than the union.

* [ To be sure, to well-define intersection (i.e. to keep it true), it
is as the union where the existence of a disjoint leaves the result
undefined. Basically this of the difference among unary and
infinitary, and binary and n-ary.]

Basically in entropy coding and Huffman coding there are codes with
the prefix property that codes of arbitrary width can be put into a
sequence and demarcated courtesy the prefix property. Then, an idea
is that with paths as codes with the prefix property and distinct
length, there would be in the tree a path of each finite length, but
that paths of greater length would have a different prefix than each
preceding path.

https://en.wikipedia.org/wiki/Prefix_code
https://en.wikipedia.org/wiki/Huffman_coding

Then, where Huffman coding is to find the largest alphabet with the
prefix property with the least average length of the path, here the
idea for dense bounded tree coding is to find an alphabet with the
prefix property with one code for each length: with the maximum suffix
of the path that is disjoint the other code's paths, that each pair is
mutually disjoint.

Basically this is about codes with the prefix property (that there
would be a branch from lesser length codes, and the next), the
palindrome property, or otherwise with the prefix property, and that
the suffix was not following the suffix of another code initial
segment, in reverse as it were. Basically it is that the reverse of
the code of length n as path, would have the prefix property, to the
initial segment of length n of any code of greater length.

Then, saying that there would always be an infinite path in the union
of paths of each finite length of the binary tree is that there is no
"dense bounded" coding as here. Basically that is a question of what
are the most paths and most lengths (and as to complexity and entropy)
there can be with the least amount of infinite paths.

Here, again, the intersection[*] of the 0-paths is infinite, the union
of the 0*1-paths has a subtree that is infinite, a distinct
difference: the least number of finite paths, with an infinite path.

There is a difference among representations, of unary, infinitary,
binary, and n-ary (in spaces), structural difference with
concomitantly various results, as of their variety.

Regards,

Ross Finlayson