Thus, the conjunction of the two properties implies that . We can define a function that has these two properties as follows. Let U be a plan in , let T be a plan in , and let parent be a function from a plan to its parent plan in the tree. U in to all linearizations which share common derivation ancestry. How maps from to We can show that satisfies the totality and disjointness properties by induction on the depth of the search trees.
Detailed proofs are in the appendix.
To prove the first property, we show that for every plan contained in , all linearizations of that plan are contained in . To prove the second property, we note that any two plans at different depths in have disjoint sets of linearizations, and then show by induction that any two plans at the same depth in also have this property. The mapping described above provides an answer. For each plan U in there are distinct plans in TO, where is the number of linearizations of U . The exact number depends on how unordered U is.