Definitions and notation for trees.

. If , and , . If , the **concatenation** of and is defined by . If , , then is an **initial segment** of and is an **extension** of (written ), if , for some .

A **tree** on a set is a subset closed under initial segments. The **body** of , . An element of is called **terminal** if and for all .

Let is a tree on . is **finite splitting** if for every there only finitely many such that . is **pruned** if every has a proper extension .

*Fact.* If is finite splitting, for every , the number of strings in of length is finite.

*Proof.*

Assume that for some , the number of strings in of length is infinite. Then, there must be a minimal number , which satisfies the property that infinitely many of the strings differ at position , but agree at all previous positions. Then is not finite splitting.