(Exercise 4.12)

Let be a tree on . If is finite splitting, then iff is infinite. Show that this fails if is not finite splitting.

*Proof.*

“”. Suppose is finite. Then, obviously, .

“”. Suppose is infinite. Since is finite splitting, for every , the number of strings in of length is finite. (see Fact here)

Now, there is no terminal string of maximal length. For if there were, would be finite. That is, for each , there exists terminal string , where . Let . Now, there must be an infinite subset such that implies , for otherwise the fact that there are only finitely many sequences of length would be contradicted. Define .

Now, suppose that for , there exists such that is infinite, implies , and . Now, there must exist infinite such that implies , for otherwise the fact that there are only finitely many sequences of length would be contradicted. Also, .

So, we have inductively constructed a sequence with for all . Thus, there exists such that ; that is .

Finally, define . Then is infinite and . But is not finite splitting.

### Like this:

Like Loading...

*Related*