Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
    
@wj32 : Math, always weird. –  Joris Valette Nov 4 '12 at 1:01
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
Thanks I get it now. For some reason I thought level 2 of the tree would be $\mathbb{N}^{\mathbb{N}}$ when it's $\mathbb{N} \times \mathbb{N}$... –  Joris Valette Nov 4 '12 at 1:26
    
@Joris: Good. (And yes, that would throw you off pretty badly!) –  Brian M. Scott Nov 4 '12 at 1:27
add comment

It may help to note the following facts:

  • There isn't an $\aleph_0$-th level.
  • $\aleph_0$ is the least upper bound of $\{2^n \mid n \in \mathbb{N}\}$
share|improve this answer
add comment

There are $\omega$ levels, but: On the $n$-th level ($n < \omega$), there are $2^n$ nodes, so alltogether, we have $\sum_{n < \omega} 2^n = \aleph_0$ nodes. If we replace $2$ by some other cardinal $\kappa$, which may also be infinite, we have $\kappa^n$ nodes on the $n$-th level, that is alltogether $\sum_{n < \omega} \kappa^n = \max\{\aleph_0, \kappa\}$ nodes.

share|improve this answer
    
Ok, I have to learn the difference between $\aleph_0$ and $\omega$, the key might be here right ? –  Joris Valette Nov 4 '12 at 0:59
1  
@Joris: No: $\aleph_0$ and $\omega_0=\omega$ are the same thing. People sometimes write $\aleph_0$ to emphasize that they’re talking about cardinality. –  Brian M. Scott Nov 4 '12 at 1:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.