1

I have the following Infinite Tree that when fully spelled out, contains one row for each natural number. The zeroth row contains one node, the first row contains two nodes, the second row contains four nodes, and, in general, the nth row contains 2^n nodes.

The point of the problem is to determine if the nodes of the tree have a one-to-one correspondence between the natural numbers, as well as if the branches of the infinite binary tree have a one-to-one correspondence between the natural numbers.

My intuition tells me that the nodes will have a one-to-one correspondence and the branches will not. Because there are a defined number of nodes per row of the tree, each row is represented by a natural number, and no two rows are the same, then there will be a one-to-one correspondence. However, I am not sure about the branches.

Any help is appreciated.

Nick
  • 145

1 Answers1

2

You're correct that the nodes are in correspondence with the natural numbers; for example, the $k$th member of the $n$th row can be mapped to $2^n + k$ with no conflicts.

The branches are not - there are many more branches than natural numbers. This is an instance of Cantor's diagonalization result - each branch can be identified with an infinite binary sequence, and there are more binary sequences than natural numbers.

Adapting Cantor's argument to this case: Suppose (for contradiction) that there is a one-to-one correspondence between natural numbers and branches. We build a new branch as follows: at level $n$, turn right if the $n$th branch turns left, and left otherwise. The resulting branch cannot be one of the originally enumerated branches - if it were, it would be the $n$th branch for some $n$, and so it would turn left if it turns right and vice versa, which is nonsense. So this new branch is a branch not on the list, contradicting the supposition that we had a complete list.

Reese Johnston
  • 17,988