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 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.

share|improve this question
add comment

1 Answer

up vote 8 down vote accepted

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$

share|improve this answer
    
One wonders if we really need the axiom of choice here, though... –  Zhen Lin Aug 19 '12 at 12:55
    
@Zhen Lin: You need a bit of it for the general case of König’s lemma. –  Brian M. Scott Aug 19 '12 at 13:03
    
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... –  Zhen Lin Aug 19 '12 at 13:10
    
@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). –  alancalvitti Aug 19 '12 at 17:46
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.