FINITE INJURY ARGUMENTS IN INFINITE COMPUTATION THEOREMS

- 1 -

A significant part of ::pJBt- Friedberg recursion theory has been

succe~ully generalized to recursion theory on an admissible ordinal a. • Such a recursion theory has two properties seemingly important for priority arguments: it is an ''infinite" theory and its domain is recursively wellordered. Kreisel ([5], pp. 172-173) has asked (with some persistence - see his reviews of [6] and [13] ^L~ Zentralblatt

1973 and 1976 respectively) whether these properties are significant for the existence of incomparable roe. degrees. Recently Sy Friedman [4] has considered the first property by doing recursion theory over an arbitrary limit ordinal S , thus clroppi>J.g the ad.mis- sibili ty criteria. His main result is the existence for many 13 of a pair of sets E1 over ^L(S) such that neither is S-recursive in the other. We, on the other hand, are keeping admissibility while relaxing the req~irement of a wellordered domain to that of a pre- wellordered domain, that is we are essentially studying recursion theory over resolvable admissible sets with urelementso

However, rather than restricting our attention to resolvable admissible sets, our approach in this paper is axiomatic. Starting with a precomputation theory in the sense of-Moschovakis [6] with a computable selection operator, we add two axioms to obtain an infinite computation theoryo The first asserts the existence of a prewell- order whose initial segments are uniformly "finite", while the second insures that all "computations" can be effectively generated and that this generation is matched up with the complexity of the domain as expressed by the prewellorder. The class of infinite com- putation theories coincides with the class of Friedberg theories as defined in [6].

- 2 -

It is doubtful (see Simpson [14]whether the axioms for an in- finite theory are quite adequate for giving a positive solution to Post's problem. A trivial but significant observation for a-recur- sion theory (or for any recursively wellordered infinite theory) is that any a-r.e. set bounded strictly below a*, the projectum of a, is a-finite. We call an i:afinite computation theory ade- quate whenever the analogous theorem holds. For adequate theories we prove a strong form of Sacks' splitting theorem [7,10], thereby supporting the conjecture that any of the usual finite injury prioity arguments can be carrj_ed out for such cheories.

In section 1 we give the axioms for an infinite computation theory and prove some elementary results. Section 2 introduces dif- ferent notions of relative computability and gives sufficient condi- tions in terms of regularity and hyperregularity for the notions to coincide. Shore's blocking technique using ~2 functions is devel- oped in section 3 while the proof of the splitting theorem, along with some o.f the usual corollaries, is given in section 4.

S.G. Simpson (see [14] and [13]) has independently studied

recursion theory over resolvable admissible sets. In particular, he was the first to note that Shore's blocking technique could be used to obtain a version of the Friedberg-Huchnik theorem for what he calls thin admissible sets.

- 3 -

1. Infinite Computation Theories

We will be dealing with partial multivalued functions and func- tionals on some set U. An n-ary partial multi valued function is

just an n+1 - ary relation. Following the notation of Moschovakis [6] we mean by f(x1 , ••• ,xn) ^~ z that the partial multivalued func- tion f has z as one of its values at x1 , ••• ,xn, i.e.

(x_{1 , •••} ,xn,z) is an element of the defining relation for f.

In case f is singlevalued we may without confusion Nrite

In this paper partial

multivalued functions on U will simply be called functions, whereas a total singlevalued function will be called a mapping.

The notation used should easily be understood from the context keeping the following 12£selz defined conventions in mind: Functions on u are denoted by f,g,h, .... ,p,q,r, .... ⁰ _{a.' 13} are reserved for ordinals and i, j, m, n for elements in N • Remaining lower case latin and greek letters (except A., 1.J. and v which will have their usual meanings) denote elements of U.

A computation domain is a structure 0( = (U,N,s,M,K,L) where U is a set, N ~ U , (N, s fN) is isomorphic to the natural numbers with th8 successor function, l'1 is a pairing function ~~d K and L are inverses to 1'1. The latter means that if M(x,y) = z then K(z)

=

x and L(z)

=

y. From 1'1, K and L we define the tupling function ( .... ) and its i:th inverse ( ). in the usual fashion.

l.

A set 8 ~ U[Un:n~2} is called a computation set on ()"f...

For a computation set 8 we define the relation

£e:

J~Ci)

...

z

~ ~

iff lh(x) = n

&

(e:,x,z) E @

- 4 -

where lh (i:) ....

denotes the length of the sequence x. Thus ( E: )~

defines an n-ary function for each e: E U and n E N. An n-ary function f on U is 8-computable if there is e E U such that

f = ( e: )~ , in which case e: is a 8-index for f • An n-ary rela-

tion R on U is 8-semicomputable (8-s.c.) with a 8-s.c. index e: if R is the domain of a 8-computable function with 8-index e: • R is 8-computable with 8-index e in case its characteristic mapping cR is 8-computable with 8-index e: • Finally we say that a consistent functional F(f1 , .... ^o ,fk,i) , where fi varies over n.-

~

ary functions, is S-computable with S-index 6 if

The first step in putting some structure on a computation set 8 is to require S to be a precomputation theory in the sense of

Moschovakis. For a precise definition we refer to [6]. Roughly speaking, 8 is a precomputation theory if the constant mappings, the identity mapping, M, K, L and s are S-computable. Further- more the S-computable functions must satisfy the usual closure and enumeration conditions in a uniform way. A basic fact of precompu- tation theories is the second recursion theorem.

The existence of a 8-computable selection operator is normally assumed in order for the S-s.c.. relations to behave nicely.. A selection operator for 8 is a function q such that (henceforth dropping n and S from (e: }~ whenever possible)

q( e:)

t

^<=> 3x[e:} (x)

t

^and

V' z ( q ( e: ) .,. z => ( e: } ( z ) ~ )

where ¹¹

t

¹¹ means "is defined ^{11 o} Note that the existence of a

- 5 -

selection operator implies the existence of a uniform selection ope- rator. That is there exists a 8-computable mapping p(n) such that for each n E N , p(n) is a 8-index for an n-ary selection operator qn • The usual v notation for a uniform selection operator will be

n+1 ~ t n ~

used, namely vz((e} 8 (z,x)'li)

=

q (e,x).

For a precomputation theory

e

with a 8-computablc selection operator, the 8-s .. c. relations are closed under disjunctions and

e~stential quantification and a relation is 8-computable iff it and its complement are 8-s .. c. Furthermore 8-computable functions can be defined by cases in a general way.

In this setting one can define a well behaved notion of "finite".

Following Moschovakis we say that a set K is 8-finite if the con- sistent functional

~(f) ...

if 3x E K ( f ( x) - 0) if 'Vx E K (f(x) ~ 1)

is ®-computable. A 8-index for

EK

is said to be a canonical 8-index for the 8-finite set K .. The usual properties (see [6]) of a generalized notion of finite hold uniformly.

Having asserted the existence of a selection operator it is too

restric~ive to require

e

to be a single-valued theory as this would exclude some of the intended models. However when considering func- tions whose values are (canonical 8-indices for) 8-finite sets, then 8 is essentially single-valued. In the lemma stated below let K'll denote the ®-finite set with canonical ®-index '11 in case

'11 is such an index.

Lemma 1 .. 1. Suppose r is a ®-computable function whose values are canonical ®-indices such that 'Vx,

s,

T)(r(x) ...

s

^& r(x) ... 'll =>

Ks

⁼ K'll).

- 6 -

Then there is a B-computable mapping q obtained uniformly from r such that Vx, n(r(x) .... n => Kn = Kq(x)) •

We now list two additional axioms making

e

into an infinite computation theory.

!1·

There is a ®-computable prewellorder ~ on U such that initial segments of ~ are uniformly ®-finite.

Given a p.rewellorder ,;6 we let x ~ y denote -, (y~ x) and x "' y denote x ~ y & y ~ x •

Definition 1.2. A (~)-enumeration of a set W is a ®-compu- table mepping AcrwP (whose values are canonical ®-indices for the

®-finite sets W0 ) such that

(ii) W = U {Wa : cr E U} •

A2. There is a ®-computable mapping p(n) such that for each n E N , p(n) is a 8-index for a (~)-enumeration of the set

.... .... ....

Tn = {(e,x,y): {e}(x) .... y & lh(x) = n} ..

Definition 1.3. Let 8 be a computation set over a computation domain 0[ ⁰

e

is an infinite computation theory if

(i)

e

i$ a precomputation theory.

(ii) Equality on U is a ®-computable relation.

(iii)

e

has a computable selection operator.

(iv) A1 and A2 hold for some prewellorder .:{ on U.

A basic fact of infinite recursion theories, e.g. recursion on an admissible ordinal a. , is that computations can be coded effec-

- 7 -

tively into the domain in such a way that the complexity of the do- main corresponds to the complexity of the coded computationso It therefore seems reasonable to assert the existence of a 8-computable partial order ~ whose initial segments are well-founded and uniform- ly 8-finite. Here we restrict ourselves to the case where ~ is a prewellorder. A2 then stipulates +:hat all "computations" {e}(i) ... y can be effectively generated and that this generation is matched up with the complexity of the domain. Note that U is not 9-finite for an infinite computation theory.

Following the notation of Barwise [1], let

..417t

be a resolvable admissible set with urelements relative to a language L*

=

L(E, ... ).

By combining Moschovakis' characterization theorem for Friedberg theories with Gandy's theorem for ~1 inductive definitions over asmissible sets (see Barwise (1] p. 208), it is easily verified that

fi<?rt.

constitutes an infinite computation theory.

J. Stavi (unpublished) has shown the converse of Gandy's theorem to be false for some transitive sets. However, for resolvable tran- sitive structures ~ (closed under pairing and satisfying t:. _o -sepa- ration) the converse is true, i.e. for such ..A , J} is admissible iff every ~1 inductive operator over v4 has a ~1 fixed point.

This result, due to A. Nyberg (16], gives some justification for axiom A1.

In the sequel 8 will always denote an infinite computation theory over some computation domain 0{ ..

Lemma 1.4. Suppose f is a 9-computable function. Then there is a 8-computable function g obtained uniformly from f such that dom g = dom f, g ~ f, and for each 8-finite set K ~ dom f there

- 8 -

is a S-finite set N obtained uniformly from K and f such that g(K) c N c f(K) •

- -

Before proceeding with the proof we need to introduce the ^~-

~ ~

operator. By ^~ z R(z,x) we mean a function whose values for x are some minimal z such that R ( z , x) • -+ In particular, if R is S-com- putable we set

~ z R(z,i) = v z (R(z,i) & ('Vy-< z) -, R(y,i)).

Proof ^o Let A cr W⁰ be a (~)-enumeration of

T ₁

= ( (

^{€ ,} X, y) : ( e }(X) ~ y} and 1 et h (X)

=

~ cr [ (3y-<. cr ) ( ( e , X, y) E W0 )]

where ^E is a S-index for f. Whenever f(x) is defined .. let Nx = [y<h(x): (e,x,y) EWh(x)} ^o Note that Nx is well-defined since h(x) ^-+ cr & h(x) ^{-+ T} => cr ,.., ^{T •} It follows from lemma 1.1 that a canonical S-index for Nx is obtained uniformly and single- valuedly from e and x. Let g(x) = v y (y E Nx) • If S-fini te K c dom f , let N = U {Nx: x E K} •

A11 immediate corollary to lemma 1o4 is the existence of a

"selection operator" which single-valuedly chooses a canonical S- index for a non-empty subset of a non-empty S-s.c. set. It is such a "selection operatort', rather than the mu.lti-valued one we assumed, which is needed for our arguments. In [3] Fenstad gives axioms for infinite computation theories which do not assert the existence of a selection operater, but where the existence of a "selection operator"

as above nonetheless is a theorem. Thus Fenstad may and does restrict himself to single-valued theorieso

Definition 1.5. ^A i_~.)-parametrization of S-s.c. sets is a S-computable mapping A e cr W~ such that

- 9 -

(i) ^'T cr

V t. , r , cr ( 'T ~ cr -> W"" c W )

"' - e:

(ii) for each B-s.co set W there is an e: such that W

=

^U {W~ ^: cr E U} •

Axiom A2 asserts the existence of a (~)-parametrization of Gl-s.c. sets. Considering a fixed (~)-parametrization, we let We:

denote U {W~ ^: cr E U} o Note that a Gl-s o c. index for We: is obtained uniformly from e: , using the selection operator. Indices from a

(~)-parametrization can therefore be used in explicit definitions of Gl-computable functions.

Definition 1.6.

(i) A projection into W is a total Gl-com.putable function p whose range is a subset of W such that if x ~ y then

p(x)

n

^{p(y) =} 0 • (Here p(x) denotes the set ( z : p(x) .... z} .. ) (ii) e is prpjectible into w if there is a projection into

w.

(i) Let W = (e::W ;i¢}

€ for a given (~)-parametrization of Gl-s.c. sets. Then Gl is projectib:!.e into W.

(ii) Suppose p is a projection. Then there is a (~)-parame­

trization of Gl-soc. sets such that {e:: We -j 0} ;:=ran p.

Proof.

(i) Define

f(x) = ~cr [(::Je:<-cr)(xEW~ & (V'yEW~)(y=x))]

and let

p(x) = \) ^€ [x E w~Cx) ^& (V'y E w~Cx)) (y = x)] ⁰

- 10 -

Then p is clearly a projection into W •

( J.. J.. ) Let '\ "'" cr Vcre: A~ b e any (<) ~ -parame rJ.za J.on o t · t · f ^r.:;, ~-s.c. se s. t Using lemma 1.4 we have a collection of Bl-finite sets Kx, each obtained uniformly from x, such that ¢ F

ISc

^~ p(x) • Let W = U (Kx : x E U} and let A. cr

if1

be a (~)-enumeration of W. Define

= {

v x [ e E Kx] if e E

\·l

r(e:,cr)

0 if e: ~

if1

⁴

Letting

vcr if e: E Wcr

wcr

= {

r(e,cr)

e:

0

_{if e}

¢

wcr

we obtain a (~)-parametrization with the required property.

fRJ

Due to the negative result in Simpson [14] it is reasonable to formulate yet another condition which isolates a subclass of infinite computation theories for which the priority argument can be carried out. The problem in the general case is that for any (~)-parametri­

zation the set {e: :We: F ^0} may be too "wide". LellliD.a 1. 7 reduces the problem of finding a "narrow" (~)-parametrization to that of finding a "narrow" projection.

A Bl-finite set K is said to be strongly Bl-finite if every

·~ Bl-s.c. subset of K is Bl-finite.

Definition 1.8. An infinite computation theory Bl is said to be adequate if @ is projectible into the field of a Bl-s.c. pre- wellorder whose initial segments are uniformly strongly Bl-finite.

In the sequel we assume that the prewellorder of definition 1.8 is ~ or an initial segment of ~ , for some ~ satisfying A1 and A2. The modifications necessary for the general case are left to the reader.

... 11 -

Let p:.< be the unique order-preserving map from U onto the

"

ordinal 1~1. Often we will be imprecise and write x when we mean ~-< (x) .. Thus x -< a where a is an ordinal stands for

""

p< (x) < a • Throughout the paper we use the following

""'

Convention: Le

=

{x E U : x

<

13} • Definition 1 .. 9.

(i) The projectu.m (~) , denoted I~

I* ,

is the least ordinal 13 such that 8 i..s projectible into L!3 •

(ii) The r.e.-pr0,jectum(.6-) , denoted 1~1+, is the least or- dinal 13 for which there is a 8-s.c. non-8-finite set W ~ Ll3 •

Since the range of a projection is a 8-s.c. non-8-finite set it follows that I~

I+

^<

1.::61

* • Thus, modulo our assumption after 1.8, 8 is adequate if and only if I~

I+

⁼ I~

I*

= limit ordinal.

Every computably wellordered 8 is adequate since for such theories every 8-s.c. non-8-finjte set is the range of an injective 8-computable mapping. Any ( choiceless) standard model of Z F con- stitutes a (non-wellorderable) adequate theory relative to the power set ope~ator

!fJ ..

We may also use urelements to give some further examples of non-wellorderable adequate theories. Let ~

=

^{(M) be}

an infinite structure without relations or let 7n

=

^{(M,<) be a}

dense linear ordering. Then HYPm , the smallest admissible set above

m

(defined in [ 1]), as well as HYP(HYP'»t ) , HYP(HYP(HYP '1?\,)) and so on, can be shown to be adequate.

- 12 -

29 Relative Computability

Equivalent notions of Turing reducibility for ordinary recursion theory become distinct when considering recursion theory on an arbi- trary admissible ordinal a. As Kreisel [5] emphasizes, the differ- ent notions fall into essentially two categories: those concerned with computability and those concerned with definability. Below, a notion from each will be defined (along with some auxiliary notions) corresponding to <

-a and <

-ca. for a.-recursion theory. We will then show that, as in the case of a.-recursion theory, the notions agree on regular hyperregular sets.

By an enurueration of 8-finite sets we mean a 8-computable mapping As Kg with the property that for each 8-finite set K

there is s suet. that K = Ks. Such an enumeration always exists since every 8-finite set is ^We (] for some e and ^cr. A:n enumer- ation can of course be chosen with somewhat care, e.g. we may require Ks ~ L •

s

Definition 2.1. Let A and B be sets, f a function and A s Ks a fixed enUllleration of 8-finite sets.

(i) f is weakly 8-computable in B is a ^~-s.c. set W such that for all

(denoted

...

x,y

f < B)

~ if there

A is weakly 8-computable in B (A

.5w

B) in case cA

.=;.,

B ^o

(ii) A is 8-computable in B (denoted A ^~ B) if there is a 8-s.c. set W such that for all y, 6

Ky ~A & K 6 nA=0' <=> 3S,fl ((y,o,s,T)) E W & KS ~ B & KTlnB =0 ).

- 13 -

The definitions are independent of the particular enumeration of ®-finite sets. We define the upper semi-lattice of degrees in the usual way using the transitive reducibility < • A :;:; B denotes A ~ B & B ~ A o The join of deg(A) and deg(B) , deg(A) v deg(B) , is deg(A<t>B) where A~B = [(x,O): xEA} U [(x,1): xEB} o

The notions of weakly ®-s.c. in and ®-s.c. in ara easily abstracted from (i) and (ii) of definition 2.1. Thus A is ®-soc.

in B if there is a ®-soc. set W such that for each ^y

The sets weakly ®-soc. in B are enumerated by putting

W~ ^{= [x:} 3S,'ll((x,s,T1) EW8 & Ks ~ B & KT1n B = 0)}.

It follows immediately from the definitions that a set is (weakly)

®-s.c. in B iff both it and its complement are (weakly) 8-s.c.

in B , and that a set is weakly ®-s. c. in B iff it is tile domain of a function weakly ®-computable in B •

To define a reducibility notion corresponding to definability is technically somewhat more complicated. From an infinite theory

e

and a set B c U we construct a new theory ®[B] and say that f .=:a_ B if f is ®[B)-computable. In addii:;ion to the obvious re- quirement that ®[B] should have the usual closure and enumeration properties, i.e. that ®[B] should be a precomputation theory, we want B to be ®[B)-computable, ® ~ ®[B] (:: is the relation be- tween precomputation theories given in [6]), and quantification over initial segments of ~ to be ®(B)-computable. The latter means that the functional E~ should be ®(B)-computable where

if 3x-< z (f(x) ... 0) if vx-<z (f(x)- 1).,

- '14 -

Furthermore 9[B] should have a computable selection operator in order for the 9[B]-s.c. relations and 9[B]-finite sets to behave properly.

The theory 9[B] will be the least fixed point of an inductive operator r defined by clauses 0 - VTII ^o Clause 0 introduces the characteristic function of B and clause I makes 9 ~ B[B] using axiom A2 for 9 ⁰ Clauses II - VI correspond to clauses IX ^{I -}

xm

^I

in [ 6]. Finally, clauses VTI and VIJI introduce the functional E '- and a selection operator respectively. Having already opted for multi-valued theories we m~~e the selection operator take all its -r;>ossible values.

The ~-th iteration of r is defined as eS[B]

=

r(e<S[B]) where e<S[B] = U(eY[B] : y < S} ^o Thus the least fixed point of r is 9[B]

=

U ~[B] •

13

There is no need to give the detailed construction. We only note that all clauses have the following important property: .A

tuple ( e:

,x,

z) is added to ei3[B] only if e:,

x,

z and ( e:

,x,

^z)

Li3 • ....

are elements of For (e:,x,z) E 9[B] , set

i

e:

,x,

^{zl 9[B] =}

1 east ordinal ₁₃ such that (e:,x,z) E s"CBJ • Using this notion of length of computations, 9[B] is a computation theory in the

sense of Moschovakis. One can show that 9[B] is either an infinit~

theory or a Spector theory (defined in [3] and [6]) depending on whether U is ®[B]-infinite or 9[B]-finite.

In [9] Sacks defines a-recursion relative to a set Bca

-

^to

be 1:1-recursion on a relative to the structure (L(a.,B), E, B), where L(a,B) is the result of relativizing L(a) to B by adding x E B to the atomic formulas. We regard the theory 9[B] as the relativization of an inf'inite theory 9 to a set B. Suppose 9 is a formulation of a.-recursion theory. Then one can show that

- i

- 15 -

®(B] is an infinite theory if and only if (L(a,B), E, B) is admis- sible, in which case the notions of ®[B)-finite and ®[B]-s.c. agree with a-B-finite and a-B-r.e.

Definition 2 .. 2 ..

(i) f ~ B

(ii) A ~ B

if f is ®[B)-computable.

if cA is ®[B)-computable.

Lemma 2 .. .2_. A ~ B if and only if ®[A] ~ ®[B] • Corollary. ~ is transitive.

The proof of the lemma is standard. The required mapping p is defined by cases using the second recursion theorem for ®[B] •

~

-

The if direction of ( e ,x, z) E ®[A] <::::> (p( e ,n) ,x, z) E ®[B] is

shown by induction on

I

^{p( e ,n)}

,i,

z

I

®[B] , while the only if direction

I -

I

is shown by induction on 1 e ,x, z ®(A] •

Using the corollary we define d-degrees by d-deg(A) =

[B : A ~ B & B ~ A} • The d-degrees form an upper semi-lattice

in the usual way.

Lemma 2 .4. f ~ B => f ~ B • Proof. Let

It follows from the

A.

s Ks

be an enumeration (in ® ) of ®-finite sets.

®[B)-computability of E~ and @ ~ ®[B] that

Ks

5.:

B and K11

n

^{B =} 0 are tB[B]-computable relations. Suppose f -., < B using W , i. e.

f(x) - y <--> ::Js,Tl((x,y,s,Tl)

-

EW & Ks.::: B & K11ⁿ B =

0).

Recalling that v takes all its possible values in ®[B) we have

- 16 -

From the lemma we conclude that A < B => A < B => A S B.

- ....;y.r ~

None of the implications can be reversed since Driscoll [2] has shown that ~ need not be transitive even on 8-s.c. sets.

We now introduce the analogues of two notions due to Sacks [8] ..

Recalling the definition of W~ let

0

W~ =

(x: 3s,Tl((x,s,f1)

EW~

^{& Ks}

~

^{B & K}₁₁

n

^B

=

^0)).

Definition

2.5.

(i) A set B is regular if B

n

K is ®-finite whenever K is ®-finite ..

(ii) A set B is hyPerregular if whenever K ~ W~ and K is El-finite then there is cr such that K ~ ⁰W~ ..

Hyperregularity has the following equivalent formulation in terms of functions: B is hyperregular if and only if whenever f < B,

-w K c dom f and K is 8-finite then 3z(Vx E K)(3y ~ z)(f(x) ... y) ..

Every El-computable set is hyperregular (lemma 1.4) and every hyperregular El-s.c. set is regu:ar (proved in [15]). A useful characterization of the regular 8-s .. c .. sets is the following .. Sup- pose A cr W⁰ is a (.~)-enumeration of a set ^{W •} Let

cr cr { -r }

V =W -UW :-r-<cr. For obvious reasons we say thet A cr V⁰ is a

dis,joint (~)-enumeration of W .. Then W is regular if and only if (V f3 < I~

I ) (

3cr) (V 'r

>

a) (V'r

n

Ls = 0) ..

The problem of non-regularity can be avoided in the usual way when studying 8-s.c .. degrees for adequate theories ..

Theorem 2.6. Suppose

e

is an adequate theory. Then for every El-s .. c .. set B there is a regular 8-s.c .. set D such that B ~D.

D may be chosen such that Vx(Vy..., x) (xED => y ED) •

- 17 -

The theorem is due to Sacks [8] for a-recursion theory. Its proof (which we omit) in our more general setting is modelled on Sacks' original proof in [8]. A proof of a weaker, but for our pur- poses sufficient, version of theorem 2o6 can be found in [15].

Now we set out to show that for any sets A and B ,

A < B <"':.> A .::sa_ B if B is regular and h;yperregular. Given disjoint

sets B1 and B2 we obtain a theory ®[B1 ,B2

J

by altering clause 0 in the definition of ®[B] as follows:

0' If (0,0) , x,O, ((0,0) ,x,O) E L~ & x E B1

then ((O,O),x,O) E e¹³_{[B1 ,B2}

J.

If (O,O),x,1·, ((O,O)x,1) E LS & x E B2

then ((O,O),x,1) E ®~[B

1

^,B

2

^J.

Thus ®[B]

=

®[B,U-B] • For each cr,

s,

^{Tl and m} define

m cr .... .... P!$. ( a ) ....

H~=" _~,T) = {(e,x,y): (e,x,y) E ® [K~,K-n], _~ lh(x)

=

^m}.

'I

Lemm.n

2.z.

^mlfs,Tl is ®-finite uniformly in m, cr,

s,

^T].

Proof. ~~,T) can be defined by induction on cr with respect to ~ considering all cases in the definition of ®[KS,KTl] • ~

By an easy induction on cr we have

Lemma 2. 8. If ( e ,

i,

^{y) E} mH~, T1 & K S 5:: B & KTl n B

=

0

.... P...: ( cr) (e,x,y) E ®- [B].

then

- '18 -

Theorem 2.9. Let B be a regular set. Then (i)- (iii) below are equivalento

(i) B is hyperregular.

(ii) ®[B] is an infinite theory.

(iii) Vf (f

.5w

B <=:> f ~B).

Proof.

(i) => (ii)g To show ®[B] is an infinite theory it suffices to

show

el~l

^{[B] =}

®<I~

^{I [B] D Since}

^1.:61

is a limit O:!'"'dinal we need only consider the case of universal quantification whose inductive clause is:

If ( 7 , 0) , X, ( ( 7 , 0) , e: , x, 1 ) E L ~ & ( V y-< x) [ ( e: , y, '1 ) E ® < ~ [ B] ] then ( (7 ,0), e:

,x,

'1) ^E ®~[B] •

So suppose ⁽ e:,y, "') E ^I 'H'<I~! ^{0 [B]} for each y -<. x. It follows from the regularity of B that for each y

<

x there are o,

s,

^{~ such}

'1 ⁰

that (e:,y,1) E Hs,~ where Ks ~ B and KT1n B = 0. Letting W⁰

=

{(y,S,T1) E L⁰ : (e:,y,1) E ¹H~,T1), this can be reformulated as Lx c wB where A. o W⁰ is a (~ )-enU.IIleration of W o By the hyper-

~

QW

regularity of B,Lx ~

'Tw

for some ^To But then (e:,y,1) E @~ (BJ I-:<

I

for each y-<.. x by lemma 2.8, and hence ((7,0),e,x,1) E e<t- [B].

(ii) => (iii)o Suppose f is ®[B)-computable with a ®[B]-index e:. Then by (ii), 2.8 and the regularity of B,

f(i) ... y <=> 3~ < ~~~ ((e:,i,y) E ef3[B])

It follows that _:f

_,

< B •

- 19 -

(iii) => (i). Assume (iii). Then every ®[B]-s.co set has a (~ )- enumeration in ®[B]. For suppose V is ®[B]-s .. c ..

for some ®-s .. ca W by (iii). Put

Then V = WB

va = {x

<

a : 3

s ,

11 < a ( (x,

s ,

11

>

E wa & K

s s

^{B & KTl}

ⁿ

^{B =} {71) } ..

Then A a Va is a (~)-enumeration in ®[B] of V. It follows that

U is ®[B)-infinite (and in fact that ®[B] is an infinite theory) ..

- ."R a B]

Suppose a ®-finite set K ,S ~ .. Let f(x) = ^1-L a [x E We o Then fer each x E K, Lf(x) is ®[B)-finite uniformly in x o Thus

M = U{Lf(x) : x E K} is ®[B)-finite and hence bounded by some a ^o Then K c aWB so B is hyperregular.

- E:'

Note that regularity was not needed in going from (iii) via (ii) to (i). The regular hyperregular sets can be characterized as those sets B for which every ®[B)-finite set is ®-finite. Of course, whenever (iii) holds for B it follows that A<B

Just let f(y,o) =

o

Before defining the jump of a set we introduce yet another notion of reducibility ..

Definition 2.10. A set A is many-one reducible to a set B,

A ~ B , if there is a ®-computable mapping Ax~ whose values are

(canonical ®-indices for) non-empty ®-finite sets such that (i) x E A <.:;:. H c B

x -

( ii) x y!. A ~ Hx

n

B =

0 ..

Note that A ~ B => A ~ B and A < B & B < C ==> A < C ^o

-m -n -n

Following Shore [12] and Simpson [13] we want the jump of a set B to be a ~ complete set B' weakly ®-s.c .. in B, i.e. when-

- 20 -

ever A is weakly 13-s. c. in B then A .::=m B' • Letting A. E: We;

be a (not necessarily the) standard (~)-parametrization of 13-s.c.

sets we make the following definition.

Definition 2.11. The jump of a set B id the set B • = { e : 3

s ,

11

c < s ,

11

>

E we & K

s

~ B & KTl

n

B =

0 J •

Our only requirement on the (~)-parametrization used in the definition is that (iii) in proposition 2.12 below must hold. This is certainly the case for a (~)-parametrization obtained from the standard one as in lemma 1.7.

Preposition 2.12.

(i) B < B' _--m but not B' < B _-.,{ (so B<B').

(ii) B < D <=> B' < D' _{--m •}

(iii) D is weakly 13-s.c. in B <=> D < B' _{-m. 0} (iv) B' is weakly ®-s.c. in B •

Thus the jump is well defined and increasing on degrees. How- ever, it may not be increasing on d-degrees as is readily seen by considering a non-hyperregular d-degree. This is not surprising since in general is a much stronger reducibility notion than

-

<.

The proper notion of ¹¹semi-computable in B" for ~ is ®[B]-s.c.

Thus we want the jump (in this connection called d-jump) of a set B to be a complete 13[B]-s.c. set.

Definition 2.13. The d-jump of a set B is the set Bd = ((e:,x): {e}I3[B] (x)

tJ •

It is easily verified that the analogue for the d-jump of pro~

position 2.12 holds. Of course, in case B is regular and hyper- regular then

- 21 -

It is clear that in case the domain of an infinite computation theory is not computably wellordered, one cannot consider a unique requirement at a given stage of a priority construction. There is thus a need to consider a ®-finite block of requirements at each stage. The obvious way to block requirements is in terms of the

levels of the given prewellorder letting each level make up one blocko This method suffices for ®-finite injury arguments where elements i~

at most one set of requirements can be injured more than a fixed finite number of timeso In particular, a weak positive solution to Post's problem lvas obtained in [15] for every adequate theory using this method.

In proving the splitting theorem for an admissible ordinal \ a , Shore [11] developed ^~ technique of blocking requirements into

cr2cf(a) many a-finite sets. S.G. Simpson [14] was the first to note that this technique could also be used to prove a version of the

Friedberg-Muchnik theorem for thin admissible sets. This led us to develop Shore's blocking technique for adequate theories ^@ •

A set ^A is said to be ^L:

0 and

n

if it is 8-computable.

0

A is ^I: n+1 if x E A ^~ 3y( (x,y) E B) where B is

n '

n ^{and A} is rrn+1 if its complement is L:n+1 • ^A function f is ^L: _n if its graph Gf = {(i,y) : f(i) ... y} is ^L: no

Let

:.e

be the class of functions on

u

satisfying

& f ( x1 , ••• , x! , • o • , x ) - z ' ^& x. "" x!

=>

z ,.., z ' •

~ n ^{l l}

Functions in ~ will be identified in the obvious way with partial single-valued functions on 1~1

•

Thus by a function in

:£ n

L:n we

- 22 -

will interchangeably mean a Ln-function in

£

or a function on I~

I

induced by a Ln-function in

£: •

It is shmm in [15] that 1~1 is admissible and that every !~!-recursive function is in

:;t ⁿ

^L1 •

Let f'(a,y) be a partial single-valued function on 1~1.

Then li~f'(a,y)

=

⁵ iff 3~(va;:~)(f¹ (a,y) = 6). For f,f¹ E ;£

we say that lima f ^{1 (} cr ,x) ~ f(x) if this is the case for the induced functions on 1~1

,

^{where ~} has its usual meaning.

Lemma 3. 1. Let 9 be an adequate theory. Suppose f E

:£ n

^~₂

is total (on 1~1

).

Then there is a total 9-computable function f' E

!f

such that lim₀ f 1 ( cr ,x) :::. f(x) •

Proof. Since Gf is ~2 it follov.Js that f .=5w A , say using W, where A is ®-s.c. and (by theorem 2.6) regular. Let A cr A⁰ and

A cr W⁰ be ( ~ )-enumeratio.J.1.S of A and W respectively.

the ®-finite set of minimal ~ ~ cr such that

(3y-<.cr)(3x' ... x)((x' ,y,fl) E W⁰ & K~nA⁰ =

0).

Define

=

{

j..J.y[(3~ EN~)(3x¹ ""'X)((x¹ ,y,'Tl) EW0 ) f'(cr,x)

cr else •

Then f ^I iS total and in

:t n

k1 ^o

Let

Suppose f(a)

=

^f3 (on I~

I ) .

Choose x, y such that ~ (x)

=

a , p:c( (y)

=

^~ and f(x) .... y , end choose 'Tl such that

-..;

(x,y,n) E W & K'Tln A =

0.

By the regularity of A we can choose cr sufficiently large so that y -<. cr , (x,y, 'Tl) E W⁰ and (U-A) n L 'Tl = (U-A cr) n L 1l • Suppose T ~ cr • Then N~ f.

0

since 'Tl is a candi- date. Let

s

^{E N~.} There is x' ... x and y' such that

(x' ,y' , s) E Wr & Kg n A r

= 0.

Since s ~ 'Tl and (we may assume our enumeration of 9-fini te sets to satisfy)

Ks

~ L

s , Ks n

A

= 0 •

But

- 23 -

then (x' ,y'

's>

is a correct computation of f ' i.e.. f(x') - y' • Since f E ;£ and x' "" x, we must have y' "' y.. Thus

lim₀ f' (cr ,a) = ~ ..

Definition 3 .. 2. The ~2^-cof(a) is the least ordinal ~ for which there is a function f E ;£

n

r.2 with domain ^~ and range un- bounded in a ..

Lemma 3 .. 3. ^{Let 8} be an adequate theory .. Then ~2^-cof(l~l) =

~2^{-cof( I~}

I*) •

Proof. Let k E ~ be a total ®-computable function with

range in I~

I

* such that ( 13 : k( 13) <a) is bounded for each a <

I;S I

* •

Such a k can be defined from a (~)-enumeration of a 8-s.c .. non- S-computable set

w s. Ll~ I* •

Suppose f. E

:t

ⁿ

~2

with domain 13 is un.bounded in I~

I •

Then g(a) = k(f(a)) is an

2 n

^{r2 func-}

tion unbounded in

I:E: I* •

Thus ~2-cof( I~

I*)

~ ~2-cof( l~l) ^a

For the converse inequality suppose f E

:£ n

~2 with domain ~ is unbounded in I~

I* ..

Let g(x) = 1J. cr [V T 2 cr (f(x)

<

k( T))] • Then g E

£

and g is unbounded in 1~1

•

It follows from lemma 3 .. 1 and some easily shown closure properties of ^~ and

n rrn sets that

By a (~)-sequence of 8-s .. c. sets we mean a 8-oomputable mapping r such that x ~ y => Wr(x) = Wr(y) ..

Lemma 3.4.. Suppose a < r:_2-cof(

I.:SI )

and (Ix : x< a) is a

(~)-sequence of 8-s .. c. sets such that for each x ~ a. , Ix is 8- finite. Then U (Ix: x< a) is 8-finite ..

- 24 -

Proof. Let a be least for which such a sequence exists whose union is not 8-finite.

(~)-enumeration of W ..

Let W = U [Ix : x-< a} and 1 et A cr W⁰ be a Define g(x) = ~ cr [I cW_x- ^{0 ] •} Then g E :t

n

^I:₂

and g is defined on La • But g(U a) is unbounded in U since W is not 8-fini te, i .. e.. I:2-cof( ^1~1

)

^{.:S: a ..}

Assume for the remaining part of this section that 8 is an adequate theory. We are going to divide the projectum Ll~l * _into

I:2-cof( l~l) many 8-finite blocks Ma , each bounded strictly below I~

I*.

Clearly I:2-cof( I~

I)

.:5. l.il * .. Suppose first that I:2 -cof( I~

I)

= 1~1 *. In this case we let Ma = M~ ^{= [x:} x ^{I ' J} a} for each a< l~i *., Then each Ma is 8-finite uniformly in a.

Now suppose _I:2-cof( I~

I)

< ~~I*

.

We are going to define Gl- finite approximations M~ to our bloc~ Ma uniformly from cr and a • Furthermore (I:! a< r:2-cof( ~~)) ( 3cr) (1:1 T 2-o) (v ~ <a) (M~ = M~) ,

i.e. our approximation will be "tame".

Let g : r:2-cof( I~

I )

^-+ I~

I

* be a

:£ n

r:2 function unbounded in I~ I* , and let g' E

:£

be 9-computable such that lim₀ g' (o ,a)~ g(a) and rang';::

Ll~l*.

These functions exist by 3·.1 and 3.3 .. Define h(o,a) = ~Y [(VS<a)(g'(cr,f3)-<.y)]

M_a ⁰ = ( e : h ( o , a ) ~ e: < h ( o , a+ 1 )

J ..

M~ is obtained uniformly from a

and put

Note that a canonical 9-index for and cr and that each Ma ⁰ is bounded strictly below I~

I* •

To show A a oM~ is tame, let

I ₁₃ = {cr: (3T>o)(g'(T,S)fg'(o,f3))}. Fix a< r:2-cof(l~l). Then (IS : ~ < a+1) is a (~)-sequence of 8-s .. c. sets such that each

r

₁₃

is 9-finite. Applying lemma 3.4 we obtain

3cr(Vf3~a)(VTJ':o)(g'(T,I3) ... g'(cr,f3)), i.e. 3o(vf3<a.)(vTj:.cr)(M; = M~).

Let :r113 ⁼ Mcr ₁₃ for sufficiently large o • It remains to show

- 25 -

-

I~

I*

U(Mf3: f3 < L:2-cof( ^~~~ )} - L ^o Fix e: -<.. I~

I*

and choose least a.

for which e: < h(cr,a.) where cr is fixed and sufficiently large.

Such a. exists since g is unbounded in I~

I

^{* •} By the definition of h there is S < a. such that e: ~ g' (cr, S) • But then

e:

-<

^{h( cr,} f3+1) , so by the choice of a. , a. = f3+1 and h( cr, S) ~ e: •

4. The Splitting Theorem

For parts (i) and (ii) of our main theorem we need assume 8 has a reasonable pairing function. By this we mean that for each

a.< 1~1* there is S < 1~1* such that LaxLa = ((x,y):x,yELa.},SLS.

Surely any adequate e that comes to mind has a reasonable pairing function.

Theorem 4.1. Suppose e is an adequate theory with a reason- able pairing function. Let C be a regular 8-s.c. set and let D be a 8-s.c. non-S-computable set. Then there are 8-s.c. sets A and B such that C = A U B , A

n

B = ¢ , A :s_ C , B _::: C and

(i) S[A] and S[B] are adequate theories (so in particular A and B are hyperregular)

(ii) A'

=

^B1

=

^0'

(iii) D

4

^{A and D}

f:.w

^{B •}

Before proving theorem 4.1 we state some of its usual corol- laries. First we need the following lemma.

Lemma 4.2. If A and B are disjoint regular 9-s.c. sets then deg(AU B)

=

deg(A)Vdeg(B) and d-deg(AU B)

=

d-deg(A)Vd-deg(B).

- 26 ..,.

Proof. Clearly AU B ~A 1$ B ^o For the converse we note that U- A = (U- AUB) U B o Using the regularity of B we have

Ky n A = ~ ~ 3T)(KT'l ~Ky & Ky- KT'l ,S B & KT'l n (AUB)

=

~)

,

i.e.

A .!: AU B. The proof for d-degrees does not use regularity.

Let ~'

2, £, £

vary over 8-s.c. degrees (8-s.c. d-degrees) and let a' denote the jump (the d-jump) of a •

(i) (ii)

"' ^"'

Corollary 4.3.

(V £ > Q) ( 3~,£) (£

=

~ v

2

^& ~ < £ ^&

2

^< £ ^& ~

I £) •

(Vd)(O<d<O' => ::Ja(d ,..., I"V ~ ,...., /"tww,...,

I

,..., a & a' =0')). ,..., I"V

The proofs are entirely similar to the ones found in [10] and [11],using the main theorem and lemma 4.2.

(i) ::Ja,b(O <a< b ,...,r-.1,...,,..., ^I"V & ^roJ a' = """"' b') ^o (ii)

(iii) ::Ja, ,...,-.,rw,..., b (a

I

b & ,...., a' = b' ... (a ^,-..J , . . . , , . . . , Vb) ' ) ^o (iv) ::;a, b (a ,...,~I"V

I

~ b & ,..., a' = r-.1 b' = ,..., a v b) • ,....,

We now proceed with the proof of theorem 4o1. Our description of the consti~ction will be in terms of A only whenever the de- scription in terms of B is analogous. In case A. aHa is a (..:6- )- enumeration of 8-fini te sets we use the notation H-<cr = U {H'I": 'I" .1... a} ^o By theorem 2.6 we may assume D to be regular and satisfy

Vx('VY"" x)(x ED => y ED) ^o Let A. aDa be a (~)-enumeration of D and let A. a Ca be a dis.joint (~)-enumeration of C • We are going to define (~)-enumerations A. a A a and A. a Ba of A and B indue-