I know the number of nodes in an infinite binary tree is countably infinite, but I don't understand why.
There are $\aleph_0$ levels, and the number of nodes in a binary tree is $2^{\text{number of levels}}$, so there should be $2^{\aleph_0}$ nodes, which is uncountable. This is wrong, but I can't see why.
Bonus question cause I can't get it either : In an infinite tree where each node has an infinite number of children, what is the number of nodes ?
I guess it's the cardinality of the continuum but I'm not sure, and anyway I don't know how to prove it.
Best Answer
Let $T_n$ be the set of nodes on level $n$ of a complete binary tree of height $\omega$: $T_0$ is just the root, so it has $2^0=1$ node, $T_1$ has $2^1$ nodes, and in general $T_n$ has $2^n$ nodes. If the tree isn’t complete, the levels may be smaller, but the point is that they are all finite. Their union is the set of all nodes of the tree, and the union of countably many finite sets is countable.
Now suppose that each node has countably infinitely many children. Label the root of the tree with the empty sequence, $\langle\rangle$. Label the nodes on level $1$, the children of the root, with $1$-tuples of natural numbers: $\langle 0\rangle,\langle 1\rangle,\langle 2\rangle,\dots~$. Label their children with $2$-tuples; for instance, the first three children of $\langle1\rangle$ are $\langle 1,0\rangle,\langle1,1\rangle$, and $\langle1,2\rangle$. On level $4$ you’ll find nodes with labels like $\langle 3,0,5,3\rangle$: this node is the child of $\langle 3,0,5\rangle$, which is the child of $\langle 3,0\rangle$, the child of $\langle 3\rangle$, the child of $\langle\rangle$, the root. In this way you can assign every node in the tree a unique label that is a finite sequence of natural numbers, and every such finite sequence will be attached to a node of the tree. Thus, there are exactly as many nodes as there are labels.
There is only one empty label, and there are obviously $\aleph_0$ (countably infinitely many) labels on level $1$, one for each natural number. The labels on level $n$ are just the elements of the set $\Bbb N^n$, and it’s a basic fact of infinite cardinalities that $\Bbb N^n$ is countably infinite for each $n\in\Bbb Z^+$. Thus, each level of the tree has countably many nodes, and the union of countably many countable sets is still countable, so this tree also has only countably many nodes, not continuum-many.