7
$\begingroup$

Consider the standard binary tree. Clearly the number of nodes is a countable infinity. Each node can be mapped bijectively to a rational number. But if we go ahead and "union the tree" with all "limiting nodes" which are all infinite binary sequences of $0$'s and $1$'s. In this sense we have now made the "collection of nodes" in the "completed tree" an uncountable infinity.

Is this "completed tree" still a tree, but just with a countable collection of finite nodes and an uncountable collection of "nodes at infinity"? If so, what is the proper mathematical way to describe it?

So, in an attempt to rephrase, the question is:

Can we "complete" the standard binary tree by adding an uncountable collection of nodes at "the end" and if so, then how do we describe it mathematically?

I envision the standard binary tree as being the countable collection of nodes. But can I "complete the tree" in this way by considering there to be a "level at $\omega$" with an uncountable collection of nodes? I envision this last level of nodes to still be smoothly connected to the branches converging towards it from the rest of the tree.

I can't quite make this rigorous because I think I lack the necessary set theory background, so I hope those with more expertise can see what I am going after here and to correct any errors or misconceptions I have. Maybe set theory is not the way to approach this, so any answer from any field is appreciated.

$\endgroup$
10
  • 4
    $\begingroup$ Well, what is your definition of "tree"? $\endgroup$ – Alex Kruckman Apr 18 at 21:37
  • 3
    $\begingroup$ Yeah, this completion is not a tree. But it is uncountable. You can think of it as all “upward” paths from the root, both finite and infinite. Basically, you treat the tree as directed, from each parent to child, and consider all paths from the root node. $\endgroup$ – Thomas Andrews Apr 18 at 21:41
  • 1
    $\begingroup$ The set of all infinite paths in the standard binary tree is called the Cantor space and it is indeed uncountable. A binary tree can have at most countably many nodes (each node $n$ is determined by a dyadic rational number describing the unique path from the root to $n$), so your "completed tree" is not a tree. $\endgroup$ – Rob Arthan Apr 18 at 22:05
  • $\begingroup$ You could also think your "nodes" at the new level as infinite paths through the tree, if you want a concrete way to realize them. They are naturally homeomorphic to the irrationals if I remember right. $\endgroup$ – Ned Apr 18 at 22:05
  • 3
    $\begingroup$ @jdods: most of the comments here are using the usual definition of a tree in graph theory. I think that is the default use of the term in mainstream mathematics. The broader definition used by some set theorists changes the answer from no to yes. The very first comment on your question was the best: you need to tell us what definitions you are using. $\endgroup$ – Rob Arthan Apr 18 at 23:15
13
$\begingroup$

There is a well-developed theory of trees in set theory that allows transfinite heights. The general definition is that a tree $(T,<_T)$ is a partially ordered set such that for every node $x\in T,$ the initial segment $\{y\in T : y <_T x\}$ is well-ordered.

The idea of a complete binary tree (i.e. a tree where every node has exactly two immediate successors) has a nice representation. First, let's take your example of an infinite binary tree. We can view a node at level $n$ as a function $n\to 2$ (think of the function as the path to the node, where each binary value tells you whether it branches left or right). So the tree is the set of all binary functions whose domain is a natural number. The ordering $<_T$ will just have $f<_T<g$ iff $g$ is an extension of $f$ (so in other words, $f$ to a node on the path up to $g.$

We can generalize this to a complete binary tree of any ordinal height. If $\alpha$ is an ordinal, then the complete binary tree of height $\alpha$ is the set of all binary functions whose domain is an ordinal less than $\alpha$ (often written $2^{<\alpha}).$ Then the standard "infinite complete binary tree" is the complte binary tree of height $\omega,$ denoted $2^{<\omega}.$

And so if we want to extend it another level, that's no problem. Just consider the complete binary tree of height $\omega+1.$ This will include all the nodes of the binary tree of height $\omega,$ plus some nodes at level $\omega$ that are given by functions $\omega\to 2.$ We see each node at this level corresponds to a full path through the tree of height $\omega$, so we can think of each node of height $\omega$ as "sitting atop" one of the infinite branches. (And indeed, there are uncountably many nodes at this level, one for each of the $2^{\aleph_0}$ functions $\omega\to 2.$)

I only described the complete binary trees in detail, but there is considerably more variety than that. In addition to each node not necessarily needing to have exactly two immediate successors, there is considerable freedom in what to do at limit levels. For instance, in the complete tree example, we put a node on top of each path through the subtree below. We could have instead only chosen to extend some subset of these branches. If we chose to only extend countably many branches at level $\omega,$ we could have made a binary tree with height taller than $\omega$ but which still remained countable.

$\endgroup$
3
  • $\begingroup$ Thank you for this. I think I can intuitively grasp what is going on here although I'll have to think carefully about the details/notation. It seems you are saying that the resulting structure is indeed a "set-theoretic tree," correct? And that we can continue adding further levels to our hearts content, yes, as long as there is another ordinal? That was my original intuition. Thank you for the notation clarification too. Can you provide a link to or name of a popular or standard reference text/notes on the set theory of trees? $\endgroup$ – jdods Apr 18 at 22:37
  • 1
    $\begingroup$ @jdods Yes, it's a tree in this generalized sense. For more information, see here for instance, and you can find a section on trees in most general set theory books (Jech, Kunen, Hrbacek/Jech, Just/Weese, for instance). Yes, there are trees of any ordinal height. Trees of height $\omega_1$ (first uncountable ordinal) are particularly important in set theory. For example, Suslin's problem has a formulation in terms the existence of trees of height $\omega_1$ with certain properties. $\endgroup$ – spaceisdarkgreen Apr 18 at 22:57
  • $\begingroup$ Thank you for the references and answer. I appreciate it. I continue my long term goal and digesting set theory bit-by-bit... $\endgroup$ – jdods Apr 18 at 23:01
1
$\begingroup$

In a sense, you just defined which additional nodes we should have in the completion, the problem is that we cannot add edges to them, because then they would be accessible via finite paths and intuitively we would only want them accessible via infinite paths. We cannot get to a good completion in the framework of graphs with the nodes/edges definition. The answer by spaceisdarkgreen describes a more general but still discrete concept of graphs for which such a completion makes sense.

For a more continuous alternative, a graph also gives rise to a topological space by taking unit intervals for edges and points for nodes and gluing them together appropriately. (Note however that the graphs o--o and o--o--o will lead to homeomorphic spaces.) The ends of that space will correspond to the nodes at infinity that you envision, and there is an end compactification, which is the original space with one point added for each node and a topology such that those "points at infinity" can be reached by paths from the root.

$\endgroup$
1
  • $\begingroup$ Yes, so what I am after is not a "graphical" construction, per se, in that we cannot connect the "nodes at infinity" by edges to the rest of the graph. Thank you for the topological perspective/terminology. I hadn't heard of the concept of "ends" before. That is definitely a relevant way to conceptualize this problem too. I may have not realized how distinct the graph theory and set theory structures are. $\endgroup$ – jdods Apr 19 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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