I want to prove that an infinite complete binary tree has countably many infinite nodes. However, most of the tried I made at this were developed from a computer algorithm, such as breadth first search. I am not sure how to mathematically explain the traversal of the tree in order to assign numbers to the nodes, so that I can show that there exists a bijection between the nodes (their numbering) and the set of natural numbers. How does one define BFS in a formal, mathematically correct way? I can't figure this out without doing some kind of traversal.
The full binary tree is defined as follows:
A full binary tree is a graph $T = (V, E_L, E_R)$, where $V$ is the set of vertices, and $E_L$ and $E_R$: $V \to V$ are injective and total functions representing the left and right child, respectively, such that $\text{img}(E_L) \cap \text{img}(E_R) = \emptyset$, where $\text{img}(f)$ denotes the image of the function (the range of the mapping) $f$. Furthermore, it holds that there exists exactly one vertex $r \in V$ such that $\nexists u \in V : (u, r) \in E_L \cup E_R$ and for every $v \in V : (r, v) \in (E_L \cup E_R)^{RT}$, where $A^{RT}$ denotes the reflexive transitive closure of the relation $A$.
Best Answer
I'm assuming that you meant to say "countably infinitely many nodes".
It sounds like the step that you're stuck on is how to number the nodes.
Here's one way to do it:
I assume without proof the existence and uniqueness of a path from the root of the tree to any node, with the path from the root to itself being the empty path.
Let $1$ be the root.
For any other node, consider the path to that node from the root. LRLRLRRRR for example. Replace each $L$ with $0$ and each $R$ with $1$, additionally, add a 1 to the beginning of the string.
For example, $LRL$ maps to $1010$.
You now have a bijection between the positive natural numbers and the node inside the tree.