# Cardinality of the set of all paths in the infinite complete infinitary tree

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?

• 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. May 23, 2010 at 4:42
• Better yet: this is true for $2 \leq \kappa \leq 2^{\aleph_0}$ since $(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0}$. May 23, 2010 at 4:53

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]$).
• 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. May 23, 2010 at 7:15