Cardinality of an infinite tree paths

Question

Suppose a tree with nodes located at levels $1,2,3...$. At each level the nodes branch into several nodes or do not branch.

Does the cardinality of the set of all infinite paths in this tree depend on the growth rate of the nodes by levels?

I mean, if the nodes do not branch at all, then the path is 1.

If the notes add a fixed amount of new nodes at each level, then the number of infinite paths seems to be countable. The same is if the number of nodes grows polynomially.

If the nodes branch at fixed rate at each level, e.g. each node gives 2 nodes, then the number of nodes grows exponentially and the set of all paths has cardinality of continuum.

What about intermediate branching rates?

Answer 1

Assuming each level of the tree is countable, the set of infinite paths is always either countable or has cardinality $\mathfrak{c}$. To see this, let $T_n$ be the $n$th level of the tree. The set of branches can then be considered as a subset $B$ of the product $\prod_n T_n$. In fact, $B$ is a closed subset of $\prod_n T_n$ with respect to the product topology when you give each $T_n$ the discrete topology. Since each $T_n$ is countable by hypothesis, the space $\prod_n T_n$ is a Polish space, and so $B$ is a Polish space as well. In particular, this implies $B$ is either countable or has cardinality $\mathfrak{c}$ (as a consequence of the Cantor-Bendixson theorem).

Answer 2

It’s possible to have $n+1$ nodes at level $n$ (counting the root level as level $0$) and still have $2^\omega$ branches. Here’s the start of an example:

                ---------x----------
                |                  |
          ------x------            °
          |           |            |
          °           °        ----x----
          |           |        |       |
      ----x----       °        °       °
      |       |       |        |       |
      °       °    ---x---     °       °
      |       |    |     |     |       |
      °       °    °     °  ---x---    °
      |       |    |     |  |     |    |
      °       °    °     °  °     °  --x--
      |       |    |     |  |     |  |   |
      x       °    °     °  °     °  °   °

The nodes marked x are the branching nodes. If you collapse the path from each of them up to its nearest predecessor branching node to a single edge, you get the complete binary tree of height $\omega$. I’ve simply taken that tree and inserted nodes of degree $2$ so that there is only one branching node at each level.

This tree grows by $1$ node per level, but you could stretch it out even more and get an arbitrarily small growth rate and still have $2^\omega$ branches.