Can we "complete" the standard binary tree to have a "level at infinity"?

Question

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.

Answer 1

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.

Answer 2

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.