-3
$\begingroup$

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? Well, yes.

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?

Since there are intermediate growth rates between polynomial and exponential growth, can we make any conclusions about continuum hypothesis here? Will the most intermediate rates produce either continuum or countable cardinality of the paths anyway?

P.S. Assume all nodes are equal (branch at equal rate).

$\endgroup$
1
  • 1
    $\begingroup$ This would be more appropriate at math.stackexchange. $\endgroup$ Commented Jan 1, 2021 at 21:58

2 Answers 2

7
$\begingroup$

The set of all branches is a closed set of reals. Cantor proved that closed sets are either countable or of size continuum.

$\endgroup$
10
$\begingroup$

If the nodes add a fixed amount of new nodes at each level, then the number of infinite paths seems to be countable.

It does not seem so for me. Even if the number of nodes $k_n$ on level $n$ satisfies $k_n\leqslant k_{n+1}\leqslant k_n+1$, the number of infinite paths may have cardinality continuum. For constructing an example take an infinite binary tree and replace each edge to a path of certain length, choosing lengths so that all branchings occur at different levels. This is possible, just choose the lengths successively.

$\endgroup$
1
  • 2
    $\begingroup$ I've reformatted to make it clearer that the first paragraph is a quote; feel free to revert if you disapprove. $\endgroup$ Commented Jan 1, 2021 at 21:59

Not the answer you're looking for? Browse other questions tagged .