Page 286

		(13.2), this implies that  Q k( j f(i)) is consistent with  Q k( j f(j)). By the definition of  j f(j) and Claim 13.6(B) we have . Hence, it follows that con(i, k) and

		So this case follows also.

		We now proceed to prove that  Q k(S) belongs to Ex. From Claim 13.9(b) we have . Also as a corollary to Claim 13.9(c) we have:

		13.10 Claim For all j with and all i < j, either  j h(i) =  j h(j) or .

		We now construct a machine M Ex-identifying the class . Let H(i, t) be a recursive function such that . For each , define

		, where i is the least number such that .

		Using Claim 13.10, it follows immediately that M Ex-identifies . Thus the proposition follows.

		We note that M in the above proof can be seen as performing a more general sort of identification by enumeration. M's search space is described by a limiting recursive function h, and not every  j h(i), is total. This may be contrasted with the original notion of identification by enumeration in which the search space of an enumerator is described by a recursive function whose range consists exclusively of programs for total functions.

		§13.3 Exercises

		13-1 Show that and as defined below are as required in Claim 13.6. For convenience, let . Now for each , inductively define  s i and to be the lexicographically least pair from INIT that satisfies