Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

up vote 5 down vote accepted

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]$).

share|improve this answer
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. –  Andres Caicedo May 23 '10 at 7:15
Successor cardinal, not successor ordinal. –  Harry Altman May 23 '10 at 7:40
Also, thanks for the comments! –  Kevin Ventullo May 23 '10 at 8:05
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

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.

share|improve this answer

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

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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