3
$\begingroup$

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?

$\endgroup$
2
  • 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

6
$\begingroup$

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

$\endgroup$
4
  • 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
1
$\begingroup$

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.

$\endgroup$

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