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?
$\begingroup$
$\endgroup$
2
asked May 23, 2010 at 4:36
-
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$– Pete L. ClarkCommented 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$– François G. DoraisCommented May 23, 2010 at 4:53
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
4
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]$).
answered May 23, 2010 at 6:06
-
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$ Commented May 23, 2010 at 7:15
-
1$\begingroup$ Successor cardinal, not successor ordinal. $\endgroup$ Commented 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$ Commented May 23, 2010 at 12:11
-
$\begingroup$ Fyi: en.wikipedia.org/wiki/König's_theorem_(set_theory) $\endgroup$ Commented May 25, 2010 at 6:03
$\begingroup$
$\endgroup$
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.
