TAOCP 2.3 Exercise 11

Section 2.3: Trees

Exercise 11. ▶ [**] [HM32] Extend the definition of tree to infinite trees by considering collections of nested sets as in exercise 10. Can the concepts of level, degree, parent, and child be defined for each node of an infinite tree? Give examples of nested sets of real numbers that correspond to a tree in which

a) every node has uncountable degree and there are infinitely many levels;

b) there are nodes with uncountable level;

c) every node has degree at least 2 and there are uncountably many levels.

Verified: no
Solve time: 27s

The concepts of level, degree, parent, and child extend naturally to infinite trees defined as collections of nested sets. The level of a node can be defined as the length of the chain of nested sets from the root to that node; the degree of a node is the cardinality of the set of immediate subsets contained within it; a node $X$ is the parent of $Y$ if $Y \subset X$ and there is no $Z$ with $Y \subset Z \subset X$; $Y$ is a child of $X$ in that case. These definitions are consistent for both countable and uncountable collections.

Examples of nested sets of real numbers illustrating the requested properties can be constructed using intervals and points. For part (a), let the root be the interval $[0,1]$ and for each $x \in [0,1]$ let there be a child node ${x}$; each ${x}$ is a leaf. This tree has uncountable degree at the root and infinitely many levels if we further subdivide each ${x}$ into nested intervals converging to $x$. For part (b), let $[0,1]$ be the root and define nodes as $[0, r]$ for each real $r \in [0,1]$; the node $\varnothing$ is the limit of intervals approaching 0, giving a node with uncountable level. For part (c), consider the tree of all finite binary sequences viewed as intervals in $[0,1]$ under the standard binary expansion; each node has degree 2 and the set of infinite binary sequences provides uncountably many levels.

This completes the proof.

∎