Page 283

		13.5 Proposition (Fulk [72]) There exists a class of recursive functions such that:

		(a) For all total recursive operators , .

		(b) is not contained in an r.e. indexable class of computable functions.

		Proof: The argument is organized as a series of claims. We first introduce some definitions and notation.

		For this proof, we let  s  and T (with or without decorations) range over INIT. Also, in this proof we shall identify each  s  with , the finite function with graph content ( s ). It will always be clear from context whether  s  is taken as a partial function or a member of INIT.

		Let  h 0 and  h 1 be partial functions. If there is an x such that , we say that  h 0 and  h 1 are inconsistent (written: ); otherwise, we say that  h 0 and  h 1 are consistent (written:  h 0 ~  h 1). So,  h 0 and  h 1 are consistent if and only if is a (single-valued) partial function.

		Let  Q  be an effective indexing of the class of recursive operators. That is, is exactly the class of recursive operators and  l i, is itself a recursive operator (of type ). See Section 9.8 of Rogers [158] for an example of such an indexing. Recall from Chapter 2 that each recursive operator has the following topological property.

		Continuity: For all  a , .

		We shall make strong use of this property in the following.

		Our first claim introduces some technical machinery to help in the definition of . The proof of this claim is left to Exercise 13-1.

		13.6 Claim There are sequences of initial segments, and , that satisfy properties (A), (B), and (C) below.

		(A) and are limiting-recursive functions.

		(B) For all i, and all j > i, and .

		(C) For each k and each , either (C.1) or (C.2) is true.

		(C.1)

		(C.2)