What is the path cardinality of an infinite binary tree with fractal boundary of constant dimension below 1?

Question

Background:

The complete infinite binary tree (CIBT) has path cardinality of continuum size, where path cardinality refers to the size of the set of all paths from the root.

If we consider the random infinite binary tree with constant degree $1+\epsilon$, for an infinitesimal constant $\epsilon$, we get a partial binary tree, which again has path cardinality of continuum size. We can see this by using a pull-down procedure, cutting out any long non-branching sub-path and reconnecting the ends, to show that this sparsely branching tree is isomorphic with the CIBT (see here: Path cardinality for random $(a+b)$-ary infinite trees). It is tempting to believe that all random binary trees, i.e. including those of completely random variant degree almost surely above one, can be pulled down in this manner to become isomorphic with CIBT.

Sub-question: can all partial infinite binary trees of continuum path cardinality be pulled-down, so at least a subset can be put in isomorphic correspondence with the complete infinite binary tree?

Consider now a mapping of CIBT to the $(x,y)$ plane, wherein, the nodes, $(a_i,b_i)$, are as follows (read from root up):

....

Level-4: $(-2-\frac{1}{2}- \frac{1}{4}- \frac{1}{8}, 1+ \frac{1}{2}+ \frac{1}{4}+ \frac{1}{8})$ ……..

Level-3: $(-2-\frac{1}{2}- \frac{1}{4}, 1+ \frac{1}{2}+ \frac{1}{4})$ ……..

Level-2: $(-2- \frac{1}{2},1+ \frac{1}{2})$ $(-2+ \frac{1}{2}, 1+ \frac{1}{2})$ $(2- \frac{1}{2},1+ \frac{1}{2}) (2+ \frac{1}{2}, 1+ \frac{1}{2})$

Level-1: $(-2,1) (2,1)$

root: $(0,0)$

Where the nodes are connected in order, with the usual edges of a binary tree.

Since $\sum_{i=0}^{\infty} \frac{1}{2^i} = 2$, we have now mapped the CBIT into the $(x,y)$ plane so that it forms a visual tree, with non-colliding branches, that extend uniformly from $(0,0)$ upwards, becoming increasingly dense as it approaches its limit, the number line spanning from $(-2,2)$ to $(2,2)$.

Let us call this number line the boundary of CIBT.

Since each point on the boundary corresponds to exactly one infinite path in CIBT, we can conclude that the boundary of CIBT is of continuum size, and is indeed an open real number line of length 4. We could of course instead transform to a finite height, infinitely spanning tree with a boundary covering the entire range of the real number line.

Sub-question: will any binary tree of continuum path cardinality have a boundary containing at least one open subset of dimension 1?

Consider now a procedure to collapse a tree from the top, wherein a node collapses, i.e. is removed from the tree along with its connected edges, if both its children nodes have already collapsed. We define the collapse of a tree, as the recursive collapse that happens once a set of elected leaf vertices are collapsed.

Question:

Let us select a set, F, as a fractal one-dimensional set, uniformly dense, with a Hausdorff dimension strictly less than 1. Let us for example set F to be of dimension equal to the inverse of a googol (i.e. pretty close to zero)

We now impose F on the boundary of CIBT, and collapse CIBT with F, obtaining the F-collapse of CBIT, which we can call FIBT.

We have derived FIBT, a binary tree with the boundary F.

Sub-question: Is FIBT well-defined and unique? (even if informally stated here)

The main question is now: What is the path cardinality of FIBT?

Speculations:

Obviously, FIBT has path cardinality of at most Continuum size.

Clearly, FIBT has path cardinality larger than countably infinite, as it has at least the cardinality of a set of positive Hausdorff dimension.

Now, let us consider whether we can use the pull-down procedure to show that it can be put in one to one correspondence with CIBT.

We can first observe that the infinite random tree of degree 1+e has the same boundary as CIBT, a boundary of uniform dimension 1. “Viewed from “the root” it is very sparse, but it becomes very dense at the boundary. FIBT has the reverse “appearance”, dense at the root, and increasingly sparse at the boundary.

A topological argument can proceed by viewing FIBT as an elastic structure, with nodes, connected by rubber bands, which we can cut and reconnect. Firstly, it is clear that cutting out long non-branching sub-paths and reconnecting at each end (basic pull-down) will not make any difference at the boundary. Secondly, we can then hope to cut and move infinite sub-trees, reconnecting them at other vertices, in order to show that a resulting part of the transformed FIBT achieves a unitary dimension at the boundary. However, an infinite number of additions of subsets, of the same dimension, will result in a set of the same dimension, so there seems to be no hope that any process of cutting and reconnecting can produce a set with different behavior at the boundary.

Since the pull-down procedure or any infinite cut-and-reconnect process cannot put FIBT in one-to-one correspondence with CIBT, it is tempting to think that FIBT has below continuum-size path cardinality.

Answer 1

Your title question seems to be answered by the following theorem:

Theorem. The set of infinite paths through any finitely branching tree is either countable or size continuum.

Proof. This is a consequence of the Cantor-Bendixson theorem. To summarize, suppose that $T$ is a finitely branching tree. Since we are only interested in the set of paths through $T$, we may assume without loss by pruning that there are no leaves in $T$. A branch $b$ through $T$ is isolated, if above some level in the tree, there is no branching off of $b$. One now performs the transfinite process of computing Cantor-Bendixson derivatives, where at each stage, we cast out the isolated points. Specifically, let $T_0=T$ be the initial tree, and let $T_{\alpha+1}$ be the tree obtained by cutting off the isolated points of the tree $T_\alpha$ (and pruning any leaves that may be left as residue). At limit stages, we take $T_\lambda=\bigcap_{\alpha\lt\lambda} T_\alpha$. The Cantor-Bendixson analysis is that there is some countable ordinal $\alpha$ for which $T_\alpha$ is either empty or has no isolated branches, and this ordinal is called the Cantor-Bendixson rank of the tree (or of the set of paths through the tree). If a nonempty tree has no isolated branches, then the set of branches through it is a perfect set, a closed set with no isolated points. Thus, the original set of branches is the union of a countable set with a perfect set, namely, the countably many branches that became isolated along the way and the perfect set of branches left at the end. Every nonempty perfect set is easily seen to have size continuum, and so the set of paths is either countable or has size continuum. QED

So if you've got a tree, then either there are only countably many paths, in which case the fractal dimension will be zero, or there will be continuum many paths.

Original answer:

This was too long for a comment.

Sub-question: can all partial infinite binary trees of continuum path cardinality be pulled-down, to be put in isomorphic correspondence with the complete binary tree?

No, because a binary tree can have isolated points, even if it has continuum many branches, but the complete binary tree has no isolated points. Imagine a tree with a lonely branch extending to the left, but a fully branching component (and hence continuum many paths) coming out of a node to the right.

Sub-question: will any binary tree of continuum path cardinality have a boundary containing at least one open subset of dimension 1?

No, because the Cantor set is the boundary of the associated binary tree, but the Cantor set is nowhere dense. For example, in your tree, take the subtree determined by successively going always left plus left again or right plus right again. The corresponding set of continuum many paths contains no open set.

The main question is now: What is the cardinality of FIBT?

Your question is problematic. The set $F$ is determined by a subtree only when $F$ is a closed set, since the set of paths through a tree is always closed. I don't know what you mean by "uniformly dense", but natural measure-theoretic interpretations of this are impossible by the Lebesgue density theorem. (If you are asking about the cardinality of the tree whose boundary is a closed set $F$, then it is countable, since the whole tree has only countably many nodes.) You indicate in your edit that you are asking for the cardinality of the set of paths through the tree. But the cardinality of the set of paths through any partial binary tree is always either countable or size continuum. This corresponds to the fact proved by Cantor that every closed set is either countable or size continuum. In other words, Cantor proved that the continuum hypothesis holds in the case of closed sets.