Skip to main content
7 of 7
added 68 characters in body
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

On the one hand, the comments explain that a low-growth-rate tree can still have continuum many branches. Indeed, the growth rate can be extremely slow, with most levels having no splitting at all, but then every once in a very long while, a single node splits. Just make sure at the $k^{th}$ such splitting that you are splitting at a node above the $k^{th}$ binary sequence of the tree (in some fixed standard enumeration of all finite binary sequences), and then the resulting tree $T$ will have the property that every node lies below a splitting node. This property will ensure a subtree of type $2^{<\omega}$, and hence give you continuum many branches.

In contrast, it is the converse question that I find extremely interesting, and which could be considered the real content of your question. Namely,

Question. What is a sufficient growth rate on the tree $T$ to ensure that it has continuum many branches?

The answer is that the growth rate must be essentially close to $2^n$, in the precise senses described by the following theorems. On the one hand, such a high growth rate suffices for continuum many paths:

Theorem. If $T\subset 2^{<\omega}$ is a binary tree with growth rate $\Omega(2^n)$ (in the Knuth sense big-Omega notation), then $T$ has continuum many branches.

Proof. What I intend to assume on the growth rate is that is that there is a positive real number $r>0$ such that the number of nodes on the $n^{th}$ level of $T$ is at least $r2^n$. Thus, the complement of the set of paths through $T$ is approximated by the unions of the cones above the omitted nodes on this level, and this has measure at most $1-r$ with respect to the usual coin-flipping probability measure on Cantor space. Since this is true at each level, it follows that the measure of the paths through $T$ is at least $r$, which is positive, and so there must be uncountably many paths through $T$. Since this is a closed set, it follows by the Cantor-Bendixson theorem that $T$ has continuum many paths. QED

On the other hand, any lower growth rate does not ensure continuum many paths.

Theorem. If $f:\mathbb{N}\to\mathbb{N}$ is in $o(2^n)$ (see little-o notation), then there is a tree $T$ with growth rate exceeding $f$, but having only countably many paths.

Proof. The growth rate assumption is that for every $r>0$, it will be true for large enough $n$ that $f(n)<r2^n$.

Let me describe a general procedure for building a tree $T$ with a very high growth rate, but with only countably many branches. We build $T$ in stages. First, we let $T$ use the full binary branching up to some level $n_0$. Then, at this stage, we kill off the future growth of half the branches, the ones beginning with $0$, forcing them to become isolated branches in the tree starting at level $n_0$, continued only with more $0$s after $n_0$. Meanwhile, we let the other "live" nodes, those having $1$ in their first bit, to continue splitting above $n_0$ until some much larger stage $n_1$. At that level, we again kill off half of them. Namely, any node beginning with $10$ will become isolated at $n_1$, and the others, beginning with $11$, will continue splitting up until the very much later stage $n_2$. And so on.

The general procedure is: at level $n_k$, the nodes beginning with $1^k0$ will become isolated at level $n_k$ (which is much larger than $k$), and the nodes beginning with $1^k$ are allowed to continue branching up to level $n_{k+1}$.

The resulting tree $T$ will have only countably many branches, since the only branches will be the isolated branches that we forced to occur, plus the all $11111\cdots$ branch, since whenever a sequence has its first $0$ in position $k$, it will become isolated at level $n_k$.

But now, the main point, is that by choosing the levels $n_0<n_1<n_2<\cdots$ to be very fast growing, we can ensure a growth rate exceeding $f$. Specifically, since $f$ is $o(2^n)$, there is for each $k$ a number $n_k$ such that $f(n)<2^{n-k}$ for all $n\geq n_k$, and we may also assume $n_0<n_1<n_2<\cdots$. Now, with the $T$ as defined above, it follows that the number of nodes of $T$ on level $n_k$ is at least $2^{n_k-k}$, and it remains at least $2^{n-k}$ for $n_k\leq n<n_{k+1}$, and this is larger than $f(n)$, as desired. So the growth rate of $T$ is at least $f$, even though $T$ has only countably many paths. QED

Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k