Page 270

		Proof: Let be given.

		. Suppose that  y  is an acceptable programming system and that . Clearly, It suffices to construct recursive functions g and v such that Since  y  and  j  are acceptable, there are recursive functions, r1 and r2, such that, for all i,

		.

		For each i, let Ti be the text such that, for each x and t,

		Thus, Ti is a text for Wi. For each i and n, define v(i) = r2(i) + 1 and

		It is immediate from the definition of g that, for each i, . Now suppose that and Wi = L. Then . Hence, , which is a  j -grammar for L. Therefore, ) as required.

		. Let g and v be recursive functions such that For each , let iL be as in Definition 12.14(a). The following simple observation is crucial in our construction of  y . The proof is obvious.

		12.16 Claim Suppose i is such that there are infinitely many n with g(i, n) = i. Then either of and .

		Let and . For each , define

		We note that r provides a recursive one-to-one correspondence between A and N. For each (i0, j0) and (i1, jl) we write (i0, j0) <l> (i1, j1) if and only if r(i0, j0) <l> r(i1, j1). Since r is a one-to-one correspondence between A and N, this is a total order on A. Moreover, by the definition of r we have