TAOCP 2.3 Exercise 10
Not every collection of nested sets corresponds to a tree in the sense defined in Section 2.
Exercise 10. [**] [M20] A collection of nonempty sets is said to be nested if, given any pair X, Y of the sets, either $X \subseteq Y$ or $X \supseteq Y$ or $X$ and $Y$ are disjoint. (In other words, $X \cap Y$ is either $X$, $Y$, or $\varnothing$.) Figure 20(a) indicates that any tree corresponds to a collection of nested sets; conversely, does every such collection correspond to a tree?
Verified: no
Solve time: 32s
Not every collection of nested sets corresponds to a tree in the sense defined in Section 2.3. A necessary property of a tree is that each node has a unique parent, except for the root, and that the sets corresponding to nodes must reflect this hierarchical parent–child relationship. While a nested collection ensures that for any two sets $X$ and $Y$, either $X \subseteq Y$, $X \supseteq Y$, or $X \cap Y = \varnothing$, it does not guarantee that there is a unique immediate superset for each nonempty set.
For example, suppose we have three sets $A, B, C$ with $A \subsetneq B$ and $A \subsetneq C$ but $B \cap C = \varnothing$. Here $A$ is contained in both $B$ and $C$, so it would require two parents if we tried to represent it as a tree, which is not allowed. Therefore, a nested collection corresponds to a tree only if each nonempty set has at most one immediate superset among the collection; otherwise, no tree structure can represent it. This completes the proof.
∎