# 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. – Pete L. Clark May 23 '10 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}$. – François G. Dorais May 23 '10 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. – Andrés E. Caicedo May 23 '10 at 7:15
• Successor cardinal, not successor ordinal. – Harry Altman May 23 '10 at 7:40
• 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 – Joel David Hamkins May 23 '10 at 12:11
• – Halfdan Faber May 25 '10 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.

## protected by Scott Morrison♦Jun 28 '13 at 16:28

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).