The cardinality of the set of all root paths in the infinite complete binary tree is equal to the cardinality of the Continuum. The same holds true for k-ary trees for any finite k. But what is the case for k infinite?

  • 3
    $\begingroup$ I don't know what you mean by $n$ tending towards infinity, but if you take a rooted tree such that each vertex has $\kappa$ outward nodes for any $2 \leq \kappa \leq \aleph_0$, then there are continuum-many infinite paths. Indeed, you have at least as many paths as you do when $\kappa = 2$ and no more paths than the number of sequences formed by the elements of the (countable) vertex set. $\endgroup$ May 23, 2010 at 4:42
  • 5
    $\begingroup$ Better yet: this is true for $2 \leq \kappa \leq 2^{\aleph_0}$ since $(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}$. $\endgroup$ May 23, 2010 at 4:53

2 Answers 2


Assuming your path has countable length, the set of all paths in a $k$-ary tree will have cardinality $k^{\aleph_0}$. Indeed, at each step you have $k$ choices, and there are $\aleph_0$ steps (think of a path as a function from $\mathbb{N}$ to $[k]$).

  • 3
    $\begingroup$ Kevin, though the number of paths is indeed $k^{\aleph_0}$, this number can be (MUCH) larger than both $k$ and $2^{\aleph_0}$. for example, take as $k$ the $\omega$-th successor of $2^{\aleph_0}$. Then $k^{\aleph_0}$ is obviously larger than the continuum, and it is also larger than $k$ by König's lemma. $\endgroup$ May 23, 2010 at 7:15
  • 1
    $\begingroup$ Successor cardinal, not successor ordinal. $\endgroup$ May 23, 2010 at 7:40
  • 2
    $\begingroup$ Andres, I think you mean König's Theorem, not lemma. There are two Königs, the father a set theorist, the son a graph theorist. But König's Lemma usually refers to the statement that every infinite finitely-branching tree has an infinite branch $\endgroup$ May 23, 2010 at 12:11
  • $\begingroup$ Fyi: en.wikipedia.org/wiki/König's_theorem_(set_theory) $\endgroup$ May 25, 2010 at 6:03

You may be also interested in the following paper by Shelah: http://shelah.logic.at/files/589.pdf

In this paper (section 2) he defines the more general notion of the "tree revised power" of two cardinals k1, k2 as the supremum on the number of k2-branches of trees with k1 nodes. He then proves that certain inequalities involving the tree revised power have some interesting consequences in pcf theory.


Not the answer you're looking for? Browse other questions tagged or ask your own question.