Page 284

		Fix and that witness Claim 13.6. Let con(., .) denote the predicate such that, for all i and k,

		13.7 Claim

		(a) Suppose that , Q k is total recursive, and con (i, k) holds. Then, for all , con (i, k) also holds.

		(b) For each fixed k, trip predicate con(i, k) is limiting-recursively (in i) decidable.

		Proof: Part (a) follows from Claim 13.6(C). Part (b) is an easy exercise.

		Let f be a limiting-recursive function such that, for all i and x,

		Intuitively, f(i) is a program for a function that extends  s i by diagonalizing against the i-th possible r.e. indexable class of computable functions. Note that since  l i. s i is limiting recursive, such a limiting-recursive f can be constructed using the s-m-n theorem (Theorem 2.1). Finally, we define

		13.8 Claim S is not contained in any r.e. indexable class of computable functions.

		Proof: Suppose by way of contradiction that there is a recursive function p such that . Choose i0 such that Since is total and its range consists of programs for total functions, it follows that . Since , there is a j such that . Thus we have

		a contradiction.

		Fix an arbitrary k such that  Q k is total recursive. Our next goal is to show that . Since our choice of k is arbitrary, this will establish the proposition. To