Page 156

		Begin ( Stage s ) Search for the least such that (a) and (b) If such a is ever found, set  s s+1 to .

		End ( Stage s )

		One of two things happen with this construction. Either (Case 1) it progresses through all the stages, or (Case 2) it progresses only up to some stage so because the search for in that stage never terminates. The f we exhibit depends on which case holds.

		Case 1: We have, for each s, that  s s+1 is defined and, by clause (a) in the search, that and . Hence, is a total recursive function which we call f. Since clause (b) in the search is satisfied for each s, we also have . Hence, , as required.

		Case 2: Let . By Proposition 7.5 there is a recursiVe f such that f and . But, by this case M(f) = p0. Hence, , as required.

		7.9 Lemma Suppose q and r are rationals with Then .

		Proof: Let m and be such that r = m/n. Let . B is thus a recursive set with den(B) = r and . Let for each . Clearly,

		Suppose by way of contradiction that, for some M, . For each , let . Thus, for all , ; hence, . Let M' be such that, for all f, M'(f) = M(f'). We show that , contradicting Lemma 7.8.

		Fix an arbitrary recursive f and let p = M(f') (= M'(f)) and . Since we have . Without loss of generality we assume that . Claim: . (See Exercise 7-5 for the proof.) Since , we have that . Hence, . Since f was arbitrary, we have that , a contradiction.

		Proof (of Proposition 7.7): Fix reals a and b such that . Since the rationals are dense in the reals (Dudley [56], Rudin [162]), there are rationals q and r