Is this Perfect Binary Tree Countably Infinite or Uncountably Infinite?

Question

Given a perfect binary tree which at a certain fixed level has infinitely many leaves, hence each leaf at that fixed level has infinitely many ancestors. From that fixed level the tree also extends to infinite height.

Are the nodes of this tree countably infinite or uncountably infinite?

I know that a rooted binary tree, even if extended to a height of infinity is countably infinite; just start at the root and enumerate level by level. However, I cannot imagine a way to count the nodes of this tree or to apply the idea that the union of countably infinite subtrees is countable. Thus, I’m leaning towards it being uncountably infinite but have serious doubts.

How can a tree look like that?

Imagine that instead of the tree simply growing in height it is also expanding sideways as shown below, so it is infinitely high, infinitely wide and infinitely deep. Getting infinitely wide is illustrated below.

Answer 1

It sounds like you're considering an iterative construction which keeps embedding a binary tree inside a larger binary tree, always growing a bit in each direction. If so, this actually does stay countable: picking an arbitrary node and "rotating" everything around that node, what you have is just three copies of the usual (one-way-)infinite binary tree connected at that chosen node.

Of course it's a bit difficult to prove this, given that the definition you have is still rather vague. But I can't see a way of interpreting what you have in mind which doesn't lead to a countable graph. Certainly any time I define a sequence of finite graphs $G_1\subseteq G_2\subseteq G_3\subseteq ...$, their union $$\bigcup_{i\in\mathbb{N}}G_i$$ is countable, so if you want to wind up with something uncountable your construction has to be substantially more complicated.

Answer 2

Start with arbitrarily chosen node and map it to 1. There're 3 nodes at the distance 1 from it, map them to the numbers from 2 to 4. Then there're 6 nodes at the distance 3, so let's map them to the numbers from 5 to 10. Continuing in this manner you can count all the nodes.

Notice that each vertex has a degree of 3, so from the first node we went to 3 new nodes, but each time after that we can only go to 2 new nodes from each old node, which means that if we consider an arbitrarily chosen node a root each of its three children will be an infinite rooted binary tree.

Answer 3

If the "to infinity" parts are only out to countable infinity, i.e. $\omega$ levels deep, then the number of nodes themselves are also countably infinite. To see this, just consider performing a breadth-first traversal, laying down numbers as you go. Because each level individually is at finite depth and has finitely many members, it will be possible to reach it eventually after a suitably large finite number of steps.

Now if you want to go beyond $\omega$ depth, then the tree can become uncountably large, but then you run into the question of how to "make that leap" since there will be no immediate predecessors for the nodes that you can connect that first transfinite level to. That is, you have to now define just what the transfinite binary tree means, and how you do that may affect the answer to what the cardinal number of its node set is.

That said, one perhaps good way to do that might be to note how that any node of a binary tree at a given depth $d$ can be "addressed" by a string of binary bits $d$ long, hence we could take the $\omega$-th level to have all its nodes for each countably infinite binary string, i.e. of length $\omega$, or equivalently, one node for each possible endless path starting at the root. Then your $\omega$-th level (so $\omega+1$ height of the tree all total) will be uncountably infinite (cardinal $\beth_1$) and so the whole tree also uncountable. But this may not be the only sensible definition to make.

Answer 4

The number of nodes in your infinite binary tree is countable.

In particular, each node at the $k$-the level below the root can be uniquely labelled with a binary $k$-tuple (i.e. an element of the set $\{0,1\}^k$) corresponding to its "address", i.e. the path needed to reach it from the root node (identifying $0$ with a step from a node to its left child, and $1$ with a step from a node to its right child). Thus, every node in the tree can be uniquely labelled with an element of the set of finite-length binary tuples $$\{0,1\}^* = \bigcup_{k \in \mathbb Z^+} \{0,1\}^k.$$

As a countable union of finite sets, $\{0,1\}^*$ is countable. (The definition above also suggests a fairly simple way to construct an explicit enumeration, by starting with the elements of $\{0,1\}^0$, then those of $\{0,1\}^1$, then those of $\{0,1\}^2$, and so on.) Thus, the set of nodes in your tree is also countable.

---

What might be confusing you, however, is that it's also possible to consider (countably) infinite descending paths through your tree, corresponding to infinite binary sequences. The set $\{0,1\}^{\mathbb N}$ of such sequences is uncountable — as shown by Cantor's diagonal argument — and each such sequence corresponds to a distinct path through the tree (in the sense that, for any two distinct sequences in $\{0,1\}^{\mathbb N}$, there is a node in your tree where the corresponding paths diverge and never again meet). However, these infinite paths never reach a final node, and thus do not correspond to the address of any node in the tree.

So if you're only interested in the number of nodes in your tree, it is countable. But there are uncountably many different descending paths through it. This is in sharp contrast to the corresponding situation with finite binary trees, where every descending path must eventually end at a specific node.

---

Ps. Above, I've assumed that your tree in fact remains rooted throughout the construction — i.e. that there is a unique root node that is not a child of any other node, and remains so even at the infinite limit. Probably the conceptually simplest (though not the only) way to construct such an infinite rooted tree is to have it grow only at the branch tips — i.e. at every stage of the construction, take every node that does not yet have children and give it two new child nodes.

However, the picture in your question shows the tree also growing "to infinity" at the root. It's not 100% clear how to interpret that, but one reasonable interpretation would be that, at every stage, the current tree is (also) duplicated, and the root nodes of the two copies are then made children of a new root node.

The tricky part with this "doubly infinite growth" construction is that the tree may or may not actually remain rooted — in particular, depending on how you relabel the (old and new) nodes at each stage, the root might end up escaping to infinity so that, in the final infinite tree, there are no longer any parentless nodes left(!).

However, this will not actually change the number of nodes in (or paths through) the resulting infinite tree. In particular, even if the infinite tree has no root node distinguished by its lack of a parent, we can still pick any arbitrary node in the tree as a starting point and label all other nodes by the shortest path needed to reach them from the start node — which will involve first climbing $k$ steps up (i.e. from each node to its parent) to the closest common parent of the start node and the target node, and then descending $n$ steps towards the target from this common parent. The resulting node addresses can thus be identified with elements of $\mathbb Z^+ \times \{0,1\}^*$, which is still a countable set.

Indeed, more generally, it's not hard to show that any construction that only has countably many stages, and only adds a finite number of new nodes at each stage, cannot produce more than a countable number of nodes in the final tree.