Welcome to MathOverflow

Question

1

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?

edited May 23 2010 at 5:26

asked May 23 2010 at 4:36

Halfdan Faber
579●6●15

2

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 2010 at 4:42

3

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 2010 at 4:53

Kevin Ventullo · Accepted Answer · 2010-05-23 07:38:28Z UTC

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

edited May 23 2010 at 7:38

answered May 23 2010 at 6:06

Kevin Ventullo
3,224●10●20

2

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 2010 at 7:15

Successor cardinal, not successor ordinal. – Harry Altman May 23 2010 at 7:40

Also, thanks for the comments! – Kevin Ventullo May 23 2010 at 8:05

1

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 2010 at 12:11

Fyi: en.wikipedia.org/wiki/König's_theorem_(set_theory) – Halfdan Faber May 25 2010 at 6:03

Haim · Answer 2 · 2010-05-23 08:47:45Z UTC

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.

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.