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

(Update. This is a totally new answer.)

On the one hand, the comments explain that one can have a tree $T$ with continuum many branches, but with a very slow growth rate, adding no branching nodes at almost every level, and only very seldom allowing a node to split, and at most one node splitting on a level at a given time. This is easy to see, since in order to get continuum many branches, one only needs to arrange that every node gets a chance to split eventually, and this can be done in such a very slow manner, simply by usually doing no splitting, but then on a very sparse set, for the $n^{th}$ splitting, making sure that the $n^{th}$ node on the tree is below some very high splitting node.

But conversely, let me argue that having even a very high growth rate does not ensure that there are uncountably 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 allow only half of the nodes to branch, the ones that started out with $1$ in the their first bit, and force the other half, the ones beginning with $0$, 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, beginning with $1$, 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 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 an extremely high growth rate for this tree. For example, at level $n_0$, we have the full $2^{n_0}$ many nodes; at level $n_1$, we have $2^{n_1-1}$ many nodes, and at level $n_k$, I think we have $2^{n_k-k}$ many nodes (please correct me if my calculation of this is off).

By choosing $k\mapsto n_k$ to be very fast, we can arrange that the growth rate of $T$ is very high.

I will give some more thought to exactly how high we can make this growth rate. Perhaps it is something like: we can exceed any $f$ that is not $O(2^n)$. Conversely, it seems conceivable to me that any tree whose growth rate is $O(2^n)$ must have continuum many branches.

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