How many paths are there in the in the full (infinte) binary tree?

Question

Consider if we have the full infinite binary tree defined co-recursively $ t_1 =\langle t_2,t_3\rangle $ and $ t_n = \langle t_{2n}, t_{2n+1} \rangle $. We can define a path $P$ through this tree as a sequence of nodes starting with $ t_1 $ such that next item in the sequence is an element contained in the previous.

Is the number of possible paths countably infinite?

Answer 1

There is a provably uncountably infinite number of paths in this binary tree. This can be proven by contradiction.

First assume that there exists a countably infinite nmber of paths and label them $ P_0, P_1, P_2, ... $. We will also use the convention that $P(d) = 0 $ indicates that the path $P$ turns left at depth $d$ and $P(d)=1$ indicates that it turns right.

Now consider the path $Q(d) = 1 - P_d(d)$. If all paths are represented by a $P_0, P_1, P_2...$ then there must be a $P_m$ such that $ P_m = Q$ And by the definition of Q it follows $ P_m(d) = 1 - P_m(d) $. We then can substitute in $m$ as the depth $ P_m(m) = 1 - P_m(m) $. However this leads to a contradiction if $P_m(m) = 0$ then substitution gives us $ 0 = 1 -0 $ alternatively $P_m(m) = 1 $ then $ 1 = 1 - 1 $. Therefor there must exist more paths in this structure then there are countable numbers.

Answer 2

Recall that there is a canonical bijection between $\mathcal P(\Bbb N)$ and the infinite binary sequences, given by the map $A\mapsto\chi_A$, where $\chi_A$ is defined as: $$\chi_A(n)=\begin{cases}1 & n\in A\\0 & n\notin A\end{cases}$$

So it is enough to argue that the infinite binary sequences correspond to paths, or branches, in the full binary tree. But this is not hard, since we can look at finite binary sequences as functions from $\{0,\ldots,n-1\}$ into $\{0,1\}$ for some $n\in\Bbb N$, and the tree is just the inclusion order.

Since a branch in the tree is necessarily a maximal chain, it means that it is a set of functions which are compatible. Namely, if $f$ and $g$ belong to the same branch, then either $f\subseteq g$ or $g\subseteq f$ and therefore whenever $n$ lies in the common domain of $f$ and $g$, $f(n)=g(n)$. Therefore if $B$ is a branch we can define the following infinite sequence, $$F(n)=\begin{cases}1 & \exists g\in B: g(n)=1\\ 0 & \exists g\in B: g(n)=0\end{cases}$$ Since $B$ is a maximal chain, every $n$ has to be in the domain of some function which lies in $B$, so $F$ is indeed a function from $\Bbb N$ into $2$, and therefore there is some $A\subseteq\Bbb N$ such that $\chi_A=F$.

And it is not hard to verify that $\mathcal P(\Bbb N)$ is uncountable using Cantor's theorem: whenever $f\colon\Bbb N\to\mathcal P(\Bbb N)$ is any function, then $\{n\mid n\notin f(n)\}$ is not in the range of $f$, so $f$ is not surjective. Therefore there cannot be a surjective function from $\Bbb N$ onto $\mathcal P(\Bbb N)$, and so it is uncountable.