2
$\begingroup$

I am reading a book of Michael Sipser "Introduction to the theory of computation", and there is a theorem, which he gives without a proof: "If every node of a tree has only finitely many children and every branch of the tree has finitely many nodes, the tree itself has only finitely many nodes."

Could you, please, help with a proof of this theorem.

1 Answers 1

8

This is more often stated in the form "if a tree $T$ is infinite and every node has only finitely many children then there exists an infinite path in $T$" (see König's Lemma). The infinite path may be constructed as follows: Let $x_0$ denote the root of $T$. Now $x_0$ has only finitely many children but $T$ is infinite so there must be at least one child of $x_0$ such that the subtree under it is infinite. We call this child $x_1$. Now the subtree with root $x_1$ has also the property that every node has only finitely many children so we may continue in the same way as before and choose a child $x_2$ of $x_1$ such that the subtree with root $x_2$ is infinite etc. This yields an infinite path $x_0,x_1,x_2,\ldots$

  • 0
    One wonders if we really need the axiom of choice here, though...2012-08-19
  • 0
    @Zhen Lin: You need [a bit of it](http://en.wikipedia.org/wiki/K%C3%B6nig%27s_lemma#Relationship_with_the_axiom_of_choice) for the general case of König’s lemma.2012-08-19
  • 0
    Indeed, hence my comment! Yet for some reason my mind thinks that the theorem, when phrased this way entirely finitistic terms, should admit a solution without AC. Maybe that's just bad intuition...2012-08-19
  • 0
    @ZhenLin, and Brian Scott: suppose each node has degree 2 or 3, and that the tree is "asymmetric", ie at leach level (distance from root) the degrees of the neighborhood of each node are onto {2,3} (might need some other assumptions here). How would such a tree relate to choice as opposed to a complete binary tree? (Bertrand Russell in "Philosophy of Mathematics" describes the sequence of identical socks versus distinct shoes as making the difference in choice assumption).2012-08-19