Page 209

		9.22 Lemma (Pitt [149, 150]) Suppose and Np,k denotes . Then,

		(a) , and

		(b) pr(C r k) can be computed by looking at only the first k + 1 levels of .

		Proof: We first argue

		Claim: C r k is the disjoint union of members of .

		Proof of the Claim: For distinct  r 0 and  r 1 in N r ,k, and are disjoint because both nodes  r 0 and  r 1 are at depth k and, since they are distinct, no path can pass through both.

		Suppose . Then, passes through some , and hence .

		Suppose . Since the definition of N r k does not depend on nodes deeper than level k + 1, all paths passing through must be in C r ,k. Hence, .

		The claim thus follows.

		Therefore, by the claim and the countable additivity of pr we have

		and so, part (a) follows.

		It is easy to see that N r ,k can be effectively determined by observing only the first k + 1 levels of . Thus, part (b) follows from part (a).

		We now present a lemma that is crucial to the proof of the main result of this section.

		9.23 Lemma (Pitt [149, 150])Suppose and . Then, there is a finite collection of nodes { r 0, . . .,  r k} such that , for each , and .

		Proof: Let . By Lemma 9.21 we have, for all ,

		Now, if the sum of infinitely many nonnegative quantities is > p, then there is a finite subcollection of these that sum up to some number > p. Therefore, there is a finite such that { r 0, . . .,  r k} are as required.