Degrees of functionals

Dag Normann Oslo- 75

In this paper we will discuss some problems of degree-theoretic nature in connection with recursion in normal objects of highertypes.

Harrington [2J and Loewenthal [6J havij proved some results con-

I

cer.riing Post's problem and the Minimal Pair Problem, using recursion modulo subindividuals. Our degrees will be those obtained from

Kleene-recursion modulo individuals. To solve our problems we then have to put some extra strength to ZFC. We will first assume V ⁼ L, and then we restrict ourselves to the situation of a recursive well- ordering and Martin's axiom.

We assume familiarity with recursion theory in higher types as presented in Kleene [3]. Further background is found in Harrington [2], Moldestad

[9]

and Normann [11]. We will survey the parts of these papers that we need.

In section 1 we give the general background for the arguments used later. In section 2 we prove some lemmas assuming V ⁼ L.

In section

3,

assuming V

=

L we solve Post's problem and another problem using the finite injury method. We will thereby describe some of the methods needed for the more complex priority argument of section 4 where we give a solution to the minimal pair problem for extended r.e. degrees of functionals.

In section 5 we will see that if Martin's Axiom holds and we have a minimal well-ordering of tp( 1) recursive in ~ , we may use the same sort of argume~ts as in parts

3

and 4.

- 2 -

1 Preliminaries

1A Notation. For some fixed k ~ 1 , let I be the set of func- tionals of type ~ k • We let S c I be the set of functionals of type < k. The elements of S are called subindiviauals, they are denoted by i, j etc. n, m will be used for natural numbers, e mostly for indices. The elements a, b, c of I are called indivi- duals.

f : I ... w is called a function. We identity subsets of I with their characteristic functions.

F : functions ... w is called a functional. A functional F is called normal i.f k+²E is recursive in F , where

k 2

= {

+ E(f) 0

1

if 3 a E I i.f \1 a E I We will always assume f to be total.

f(a) = 0 f(a)

#

0

By k+1 - sc (F, a) we mean those subsets of I recursive· in F and a.

By k+1 -en (F, a) we mean those subsets of I semi-recursive in F and a.

By extended recursion, we mean recursion modulo an arbitrary indi- vidual.

1 B Companion Theory

In Normann [11] a companion theory for recursion in a normal type k+2 object was developed and studied. The spectrum of a functional F was defined as follows:

Let < be a partial ordering on I . Let a .:::::: b if a < b

and b < a. Let x be a set.

We say that < is a code for x if <;~ is isomorphic to

( E U =)

t

TC (x} ( TC is the transitive closure).

Let x ^E Ma(F) if there is a code for x recursive in a and F •

(Ma(F))aEI is called the spectrum of F and is denoted Spec(F).

Theorem 1.1 (Normann [11]) (For F

=

k+2E also MacQueen [?]) When F is a normal functional, Spec(F) is the least family (Ma>aEI satisfying:

i Each Ma is rudimentary closed in F.

ii If l'fl is a ^.6₀-formula, ^_. X parameters from Ma' and if

_.

'f}b E I 3x _E M(a,b)l'fl(x,x,F) then

3h E Ma (h is a function and \jb E I !'fl(h(b) ,x,F)).

This principle is called ~*-collection.

Remark Since h E M(a,b) and b E 1'\a,b), h(b) E M(a,b). · Definition Following Sacks [13] we say:

Let A ~ V be a set. A is locally of tyPe k+1 if

'Vx

E V ( x E A ~ x has a code in A )

By the definition of the spectrum, it is clear that each Ma(F) is locally of type k+1 •

We will also have that each Ma (F) is uniformly projectable to w •

A subset A c I is ~;-definable if there is a with parameters from Ma . such that

b E A ~ -=!x E M(a,b)l'fl(X, b) •

.6 -formula rfl

0

It is essentially proved both in Harrington [2] and in Normann [11]

that

* (

k+2 )

~a (F) = k+1 - en F, E, a •

- 4 -

MacQueen [7] proved a selection principle for subindividuals and Harrington [2] used this to obtain the following:

Theorem 1.2 (Harrington [2], Simple and further reflection)

a

:2.

Let a E I, F a normal type k+2 functional.

Let (Ma)aEI ⁼ Spec(F) and let cf1,a ⁼

i~SM(a,i)

^•

TC(Ma) <'E1 TC(J\)

Let

c cs

be complete 'E* a among 'E; ~

s .

Identifying C with it's characteristic function we have C E I and obtain

1 C Another approach to recursion in normal functionals

The construction of Spec(F) is relevant when we investigate k+1 - en(F) and k+1 - sc(F) •

The definition of a 'E*-subset of I was simple, but if we are in- terested in other 'semi-recursive sets, the situation is more compli- cated. The following definition may be viewed as a generalization of recursion in a general E and a relation. In sections 2, 3 and 4 we will use it as a technical tool for making some notions pre- cise and handy. In section

5

we use this theory to 'compare' theo- ries on different domains.

Definition of E(R)

Let R c V be a relation. We define the functions recursive relative to R with indices by the following schemes:

i f(x1 , .... ,xn) ⁼ x. e = (1,n,i)

-

^~

ii f(x1

,o ••

,xn) = x. --x. e = (2,n,i,j)

~ J

iii f ( x1 , ••• , ^xn)

=

^{{x. ,x.} e = (3,n,i,j)}

-

^{~ J}

e = ( 4, n, e ' ) where

e' is an index for h.

v f ( :x:₁ , ••• , xn) =:: h ( g_{1 (} x_{1 , ••• ,} xn) , ••• , gm ( x_{1 , ••• ,} xn) )

e = (

5 ,

n , m , e ' , e _{1 , -· ,} em) vi f ( x_{1 , ••• ,} xn) :::::.. xi

n

^{R e = ( 6 , n , i)}

vii f(e₁,x₁,. .... ,xn,y₁,ym)

~

(e₁}R(x₁, ... ,xn) e=(7,n,m).

The functions defined by these schemes are called E-recursive rela- tive to R, and the functions are denoted (e}R.

Remark: All functions rudimentary in R will be E-recursive rela- tive to R. Since for each n E w the constant function n is rudimentary, these functions will be E-recursive. Combining schemes i and v we may commute the arguments in the functions. E-recursion is nothing but the rudimentary function schemes augmented with dia- gonalization.

The schematic definition gives us canonical concepts of i length of a computation

II II

ii subcomputation .iii computation tree

By standard proofs we will obtain the recursion theorems, giving recursive fix-points and least recursive fix-points.

The connection between E-recursion and recursion in a normal functional is given by the following lemma,·which also justifies the term E-recursion:

Lemma 1.3 In E-recursion theory there is an index e such that for arbitrary ....

R, x, e_{1 ,} x

R ...

(e) (x,e1 ,x) ^~

- 6 -

0 if 'fdy E X

if 'r/Y E X

:jyEx where ~ means 'has a value'

Proof: There is a rudimentary function ~ nuch that ~(0)

=

0 and ~(x)

=

¹ for all x -j 0 • So we may assume .that (e_{1 )} takes values 0

= 0

and 1

=

{¢) only.

Let {e) (x,e^R ₁ ,x) ^... =

Corollary 1.4 (Stage comparison)

There is an E-recursive function p such that p(o1^,o2 } ^~ if o1 or ^o2 is a computation and then

if if

llcr1ll

~

llo2!1 llo1ll

>

ll

⁰

2ll

Proof: By Lemma

1.3

and the recursion theorem, the standard proof in higher type function theory is valid.

Remark: Corollary 1.4 may uniformly be relativized to an arbitrary R.

Corollary

1.5

In E~recursion we may uniformly select an element in a semirecursive nonempty subset of w (Gandy Selection).

Proof: By Grilliot [1] this is a consequence of 1.4.

Definition Let R _:: V ,

y

^{E Vm. Let ~} be a partial map from

vn

to

v. ...

We say that ~ is recursive in y relative to R if there is an index e in E-recursion such that

.... n ... R ...

'r/x E V (~(x) ~ (e) (x,y)).

We then obtain the natural definitions of recursive in y relative

...

to R and semirecursive in y relative to R.

...

Remark: I f P is E-recursive in R and ~ is partially P-re- cursive, then ~ is R-recursive.

Definition Let A ~ V, R ~ V. Let the E-recursive closure of A relative to R be

- -

A is E-recursively closed relative to R if 'R,(A;R)

=

A.

If A is E-recursi vely closed relative to R , we may split A up as follows

( l,.( (x} ;R) >xEA

This structure will satisfy the following version of ~*-collection:

If for some z,x in

... 'R (

(x} ;R) and some A -formula ~ 0

VY

E z3r E 1t_([y,x};R)~(L~,i,y,R) then 3f E ·1?_( (x} ;R) (func(f) & dom(f)

=

z

& y E zcp(f(y),x,y,R))

...

Also 'R,( (x} ;R) will be rudimentary closed in R.

On the other hand, if (Ax)xEA is any decomposition of A sa- tisfying ~*(R)-collection and rudimentary closure ·relative to R, it follows by induction on the length of computations that each ^A

X

will be E~recursively closed relative to R and that the computa- tion tree of a computation in x will be in Ax • Combining these two observations we see that when F is a normal functional,

Spec(F)

= (

1{,( (a, I) ;F)) aEI

- 8 -

1 D Semirecursion and relative recursion Definition Let R c V be a relation. Let

Spec(R)

= ( 1tC

(a, I} ;R)) aEI

We will first pose three problems which we have not answered, but believe to have negative solutions:

Problems

Let R ,:: V , (Ma) aEI

=

Spec(R) , M

=

^U Ma. As proved in aEI

Normann [11], each Ma will be locally of type k + 2.

1 • If x E M , is there an a E I such that Ma = 1{_.( (I ,x} ;R) ?

2. If x E M, is

1t (

[I,x} ;R) locally of type k + 1 ?

3.

Is M E-semirecursive in I relative to R ?

We omit some of the difficulties induced by these problems by restricting ourselves to 1M :

Definition When <Ma>aer is a spectrum, let 1M

=

((a,y);yEMa}.

1M is E-semirecursive in I relative to R and problems 1 and 2 are trivially correct for ^X E 1M •

From now on, let R be fixed, (Ma) aEI

=

Spec(R) , M

=

Let, for x E M ,

f\:

⁼

1{,(

(x, I} ;R) • Definition Let Q .:: M, aEI.

i We say that Q is ~;(H)-definable if there is a

~ with parameters from Ma such that

1::. -formula

0

i i

x E Q <=d> 3 y E M(a,x}cp(x,y ,R) Q is weakly ~;(H)-definable

formula cp such that

if there is a

x E Q <=> \f b E I(x E M(a, b) ='" :!y E M(a, b)cp(x,y ,R))

Remark: If Q is ~; (R) , Q will be w - ~; (R) •

b. -₀

If Q ~ ¹ M , or if Problem 1 has a positive solution, the two concepts coincide.

i i i Q is b.;(R) (w-b.;(R)) if both Q and M-.Q are

~; (R) ( w- E; (R)) •

Definition Let Q ~ I

x

M AQ

= (

(a,f); f is the characteristic function of a code for a set x and (a,x) E

Q} •

FQ is the characteristic function of AQ. By some effective iden- tification of tp(k) x tp(k+1) with tp(k+1) , FQ will be of type k+2.

Lemma 1.6 Let Q ~ M.

a Q, AQ

n

M and FQ

n

^M are w- b.*(R) in each other.

b

c

If is weakly Kleene-recursive in

(For definition, see Moldestad [9] or the proof.) If Q E ~;(R) and

in FR, k+2 E,a.

Q ~ 1 M, then AQ is Kleene-semirecursive

Proof: a is trivial since each ~ is locally of type k + 1.

To prove b we must find an index e such that in Kleene-recursion

- 10 -

for arbitary e' E w, <; E ~.

~ -formulas over

rn

^X CPCI)m are computable in k+2E and

0

the unbounded quantifiers over Ma _. needed in the w- ~*-definition

,c a

of FQ from R may be replaced by unbounded quantifiers over k+1-sc(FR,k+~,a,<;) (see Normann [11] for details). We may then perform the wanted computation using Gandy's selection operator.

We use similar arguments to prove .£..

1 F Some more notations

Let R be a relation, Mx(R) = 1t((x,I};R) K~(R)

=

Sup( On n Mx(R))

~(R)

⁼

Sup(K~x,i}(R);

iEtp(n)}= Sup(Onn U M( .}(R)) iEtpG:V x,~

~~(R)

=

Least ordinal not in Mx(R)

=

Ordertype of (a.; there is an E(R)- computation with arguments x,I of length ex.)

Least ordinal not in

U

M .)(R) iEtpQV (x,~

=

Ordertype of (a.; there is an E(R)-computation with arguments x, I and some i E tp(n) of length a. } • The equalities in the definition is fairly easy to show.

Definition

U Ma. CJ

aEI

Let cr E On , R

S

V •

Now assume that we have a Godel-enumeration [ rr' ) _'~"'n nEw of the

~

0

-formulas. Identify w x S with S, so that i

0 E w, i 1 E S.

Our next problem will be to find recursive, monotone approxi-

mations of the w-L:'!' a(R)-subsets of M :

~,

Let i

=

(i

0 ,i1) and let

x E I~ a(R) if for some bE I, cr_{1 .::_} cr

'

(j1

x E M. _~,a, b(R) and

(j

'tj bE I (xEl"'.¹a b(R)

~3yEM<!

b=:\.Z Eycp. (i₁,a,z,x,R))

~, ' ~,a, ~o

Let I. (R)

=

^U I<! a(R) •

~,a crEOn ~,

Lemma

1.7

a

(j (j

I. 2 (R) c I. 1 (R)

~,a - ~,a

b (I. (R); i E S}

=

^[w- L:": (R) ~ j E S}

~,a J,a

Proof: The monotonity is immediate from the definition. To prove b we first prove:

Claim: The following are equivalent:

i

ii

xEI.

~,a

'r/

b ^E I (x EM. b(R) ~ 3 y ^El'1. b=3 z E y cp. (i₁ ,a,z,x,R)).

~,a, ~,a, ~0

s.t. for some b x E l"'. b.

~,a, cr

Proof: ii =;>

i.

^{Pick cr}₁

We may then find a suitable cr by 2:*-collection over (b; x E ~ ¹ } • i ~ ii • Let cr ₁ and cr be as in the definition, and choose cr ₁ minimal, and then cr minimal. Let b be such that X E 1'1. b •

~,a, (j1

If x E 1'1. b there is no problem.

~,a, If not, let

such that x E M. (j2 a b • Then also

~'

'

^{01 E 1'1. ~,a, b}

by definitions.

Choose y

=

^l"' (j ^{E 1.'1.} _~,a, ^{b •}

The claim proves that I. E w- 2:'!' •

~,a 1.,a

cr ₂ be minimal and

- 12 -

Obviously any w- L:j* ,a -set can be defined on the form of ii in the claim. This proves b •

Definition Let a E I , i

=

(i

1, i 2) E S • By J~ a(R)

1, we mean the partial set

X E

J~

a(R) ^{~ X} E I~ a(R)

'

^1'

X

% J~

a(R) ^{~ X} E I~ a(R)

'

^2'

whenever this is consistent ..

When J. (R)

1,a is total and well defined, it will be a general

b. 'If a(R) - subsets of M.

1,

2 V = L and the structure of the spectrum

In this section we will develop some machinery. So, let I, S be as in section 1 and let < be a k+²E-recursive well- ordering of I of length

>--<k .

Each initial segment of < can be put. in a 1-1 correspon- dence with a subset of S •

If a ^E I , let a.(j)

=

a((i,j))

1 and

{b; sb = { c; c ~a}} is uniformly recursive in a (and k+2E which we will always mean when nothing else is said), and by the recursive well-ordering we may pick the least.

This gives us:

Lemma 2.1

If a < b , there is a subindividual i such that a is recursive in b and i •

Now, let

Let (Jvl,a

=

U M( . ) •

iES a, ¹ Lemma 2.1 then gives

a

^{< b =>}

c.fta

~Jib

By simple reflection; TC(Ma) <~ TC(,)ta) , and using the recur-

1

sive well ordering:

so

This gives the following variant of Dependent Choice:

Lemma 2.2 Let

a sequence

a E I and let ~ be a 6

0-formula with parameters Assume 'tjc'c:Jx E M₀ a3 y E,Jvt.,

0 a ~(x,y,x) • Then there is

' '

(x₀ )cEI in Ma such that

\i

c ~(<xd> d<c ,xc

,x)

For the proof we use the reflection described above in combination with Gandy's selection and ~*-collection.

Definition

a a E I is called minimal if for no b < a , a E cAb • b a' (read: a-jump) is the least b such that b f.c.Jvt.,a •

Let II !! be the norm induced by < •

Lemma 2.3

a !I a' ^'I

=

A.~_

1 ⁼

least ordinal not in

J'vL

^a

b

JvL

^{a E} Ma, •

- 14 -

Proof:

a By induction on the ordinals a. < ) .

..(k

it follows that

'r/

b ( a. E Mb <=-

3

c E Mb (

II

c

II =

a.) ) • The lemma follows trivially.

b By a and the equivalent definitions of Ak-1 ^a

'V

b < a' 3 ^{cr E} Ma b a,

(II

b

II

⁼ order type of

' '

we have

(~; a. is the length

of

a computation in a and a subindividual i E S})

Using r*-collection over {b; b <a'} we see that uniform in a •

Now (b <a'; a• ~b'}

=

{b <a'; \fc(b_::c<a' => c Ecfotb)J is r::,-definable.

By Grillict-selection (MacQueen

[7])

we pick a recursive subset of (b < a•; a• = b'} and for each b in that set we find

b a

Kk-1

=

^Kk-1

collection,

Now, if of S , since

c then

uniform in b, a' • But then and r M =

u ~~-1

\./ ''13. b<a' b

0

is the characteristic function of a complete

by I::*-

I:*-subset _a

c

f- (!vta

, so a• < c • On the other hand, c Eclia,

Thus

JvL

^{a, =}

c/1

^{c , and}

JYt,

a <r J\{. a, by 1

further reflection.

Definition Let a be minimal. We say that a is bad if

b ) a

Sup(Kk_ 1 ; b <a ⁼ Kk_ 1 •

We have not been able to decide upon the existence of bad points, but we are inclined to believe that they exist. By lemma 2.3 a jump is not bad, and it can for instance be proved that when a is bad, the order type of the minimal b' s

<

a is

!I

al!

itself.

We will now define two well orderings that will be useful in later proofs:

1, From standard definability theory we know that there is a well ordering of Ma. ' U Ml3 of ordertype Kv.~

,

uniformly recursive in

[3<a.

a. • Let a.(x) be the least a. such that ^X E Ma. •

Now, let ^X <1 if. if a.(x) < a.(y) or a.(x) = a.(y) = a. and

X is less than y in the orderir .. ^g on Mcx. ..._,_ ^U MS

.

(3<a.

Let ^{II !!} 1 be the associated norm.

Remark: To define <¹ we do not need V

=

L , only a recursive in k+2E well ordering of I •

<1

is recursive in the following sense:

Given y , we may uniformly pick x such that ¹)x!l¹ = y • Unfor- tunately the converse, i.e. compute !!xl! 1

from x may not be pos- sible if we do not know for which a , x E Ma • Thus

((x,'lx11¹)} is w-6* but probably not 6*

Let v < l~k • We say that y is in row v if for some 13 ' !ly!l¹

= /{

^{k •}

s

+ v •

2. On each

</'·1

a there is a canonical well ordering length A~_

1

defined by

of

x <<~ y if x is computed from a, I and some i E S before a

y is computed from a, I and some j E S , or if they are com- puted by computations of the same length, but the index (e~i)

of the computation of x is less that that of y •

!__<!.__x ~

w.a(x E Jlia) < w.b (y E c}tb)

or (w.a(x Ec.A{a)

=

w.b(y Eutlb)

=

c & X <c){ y • c

- '16 -

This well ordering has length

}{k ,

but is in no sense recursive.

To be able to use it, we have to use recursive approximations:

x < y _a if we restrict the definition of <² to (-Ma) _v·~a aEI • Let II 112

and II

\Ia

be the associated norms.

For x E Ma, let <af'x

=

<a~(y; Y .:Sax} • To justify the term approximation we prove:

~mma 2.4

a For any ^X (<a rx; a

-

^{E On}} has at most cardinality

rz;

^k-1

b If X E Jvta , then

'i

a a

( < rx jx)

> Kk-1

=

<

-

^a _Kk-1 ^a

c For any X

'

(llx/1 a; a E On} is finite.

Remark: We will not use c in this paper.

Proof:a Let a be the least ordinal such that x E Ma and let a be the least individual such that x E J1l.~. If for some ordinal

{) > a <{)

r

^{X ~ lim <{) ~X,} this is because we for Some b < a

0 ... {) 0 {) 0

have

~

"'- U

~

⁰

I 0.

This only happens when

o

^E J'(,b .::; ..f{,a.

0 < 0

:! 0

Since Jia = ./<:'k-'1 the lemma follows.

b Immediate from the definition and the considerations in the proof of a.

c Since we do not need the result, we will not give the details in the proof:

Claim

Let a be a-minimal if (~t~>aEI

F

a is minimal.

Let a be a-minimal. If ¹¹¹ <a

f'

^U eft~~~

I !I

all, a is not b<a

a+1-minimal.

•

Proof: If

I

^{is > 9} a will be definable from element no ^I! _!I all _II in II< ~ u ,}1, crl!

., cr b<a b. If

I

^{is < U}

^JvL

^cr

b<a b will be definable from cr and the b<a such that !lbll ⁼

I!

<cr

r

_b<a

^{u c.At ~!I}

^•

Now, let ^X be given and let acr be the least a such that

X E ( a -}icr

.

(acr; cr E On} is finite since cr1 ^> cr ^::;:> a cr1

-

< acr In general we prove from the claim that if '!xi! cr

I

lim llx!l . ; cr we

a1 ... cr 1 have acr

I

acr+1 or cr is a successor and a

cr-1

I

acr •

0

Now we will prove a few results about order types of partial orderings on I •

Let -.( be a partial ordering on I • Let A, B, C be sub- sets of fi:eld (-< ) • Let

q:>(A,B,C) ~'r/a,b,c(a E A & bE B & c E C ~

a

-<

^{b 1\ l ( c<'a) 1\ l (} b-(c ) ) •

-<

^satisfies

*

if for all A,B,C ~ field (~) of cardinality

<

-

I •

cp(A,B,C) ____,.> there is a d E field (-<) such that A-< d-<:: B and for all c E C c and d are

-<.

-incomparable.

Lemma 2.5 Let '

-<

1 ^and

-<

2 be two partial orderings on ^I satisfying

*

Then

-<

_{1 and}

-<

2 are isomorphic.

For proof, see e.g. Sacks [12], Theorem 16.3. This is almost the same as proving that countable dense linear orderings are isomor- phic.

Remark: V

=

L is not required in Lemma 2.5.

Lemma 2.6

-

a ^{If GCH} holds, all partial orderings

-<.

^{1 on I}

- 18 ...

can be imbedded in a partial ordering

-<

^{2 on I} satisfying

*

^•

b If V

=

L holds, there is a partial ordering on I , recursive satisfying

*

Remark: Both GCH and V

=

L are too strong asoumptions for the respective statements.

Proof: To prove a ... it is sufficient to find one partial ordering satisfying

* ,

by the proof of Lemma 2.5 we may imbed any partial ordering in one satisfying

effective version of ~·

*

^{• We prove ~'} which will just be an

Let < be the minimal well-ordering of I recursive in k+2E _• For ^\) < )\1'

~k

'

^{let a \)} be element no ^\) in <

.

Let

< ^{, > :}

I 2 ... I be onto and recursive such that va,b, H(a,b)l/ ~ max[wa/I,Ubll}.

We will define [<v; v < ((k} to be an increasing sequence of partial orderings, uniformly recursive in a , such that cardi-

v

nality (field (<v)) ~ /~k-

1

^• We may then for each v find a b uniformly recursive in av such that field (<v)

=

Sb • Since

(32) 3 may be regarded as a subset of I , there is a well-orderin~

of this set recursive in b • This is used for the following:

The tripples A, B, C of subsets of field (< )

\) may be in- dexed uniformly recursive in av in the following way:

When < _\)

(A(a c)' B(a c)' 0 (a c)>cEI

v' · v' v'

is constructed, we automatically perform the indexing described above.

We now describe the construction:

< =

¢

0

If A is a limit, let _<A

= ^u

^<

v<A ^\)

Assume < \) is constructed. Pick tripple (A a ,Ba ,ca

>

^of

\) \) \1

subsets of field ( < ) _•

\)

Let ~ be as in the definition of

*

a to field (< ) ~ and let

If ~(Aa ,Ba ,ca ), add

\) \1 \)

\.1 \)

and for each c E C ,

let av and c be incomparable, and extend ^<\1+1 to a transi- tive relation. (We will not add new relations between elements of field ( < ) • )

\)

If -, ~(Aa ,Ba ,ca ) , let

\1 \1 \)

< _V+ 1

=

^< _V ^•

Since ~ is first order over I , this construction is recursive.

Let <* = U <

v< (<'k v

By construction <* satisfies

* ,

and <* is recursive in k+2E •

2

^V

=

L and the £inite priority method

In this section we will give a solution to Post's problem and a problem requiring a similar proof for extended recursion in functionals. We will assume V = L •

In the proof we also give terminology and methods required for the more complex priority argument in section

4.

Recall the notions in section 2. Let I

=

^{tp(k) • Let}

( k+2 ) 1

<

(Ma)aEI

=

Spec E , M

= (

a,x); x E Ma) • By reasons of con- venience, let 'card(/~

1

^{) 1} mean •finite'.

- 20 -

Theorem 3.1 (V

=

^L)

There is r*-definable subset Q c ¹ M xi such that when (Na)aEI

=

^{Spec(Q) we have}

i a is minimal and not bad =:>

J.l

^{a = JvLa}

i i

-

^a is m-inimal but bad => ^Ar c AA

+ UY a - dvta• •

Let Qb

=

^[x; (x,b) E Q}

Q_b = ((x ,a); (x,a) E Q & b

I

a}

CJ

Remark: Since Qb

S

¹M , 6* a and w - 6* a will be the same.

Using results in section 1 we obtain Corollary 3.2 (V

=

L)

There is a subset A of tp(k+1) x I semirecursive in k+2 E such that

i If a is minimal and not bad:

k+1- sc(A,k+ 2E,a) = k+1- sc(k+ 2E,a) ii If a is minimal but bad:

k+1 - sc(A, k+2E,a) ~ k+1- sc(k+2E,a') i i i

\1

a, b is not weakly recursive in

0

To obtain a solution to Post's problem, let a

I

b be two recursive elements of I • Then for all c E I :

A a is not weakly recursive in k+2

Ab,c,b, E since Ab is recursive in A b k+ 2E _• So A a

I

w Ab, k+2 E,c where < means

-a' ' w

•weakly recursive in! The opposite will hold by symmetry.

By lemmas 2.5, 2.6 and corollary 3.2 we may obtain Corollary 3.3 (V = L)

Let

<(

be a partial ordering on I • Then there are subsets (B ] a aEfield(-<) of tp(k+1) xI such that

i Each Ba is semirecursive in k+2

E and some individual,

ii is recursive in and some individual.

iii l (a-<b) ::;:. B

- a is not weakly recursive in and any individual.

Prodf: By lemmas 2.5 and 2,6 we may assume that ^~- is recursive in k+2

E Let A be.as in corollary 3.2. Let for a E

field(<)~

Ba = [(f,b); (f,b) EA & bsa] •

Then, if a-< b _t Ba is recursive in Bb and a

'

^{while if}

l(a-<b"), Ba is recursive in A-b' a and Ab is recursive in Bb and b _• So, if Bb < B w a,c, k+2E we would have

Ab <w A_b,a,b,c, k+2 E , impossible by corollary 3.2.

L)

The rest of this section is devoted to the proof of theorem 3 .. 1.

If b is recursive in a via subindividual i and natural number e we write b

=

[e,i]a • We code (e,i) to one j E S and write b

=

^{[j]a •}

There are two kinds of conditions we want to meet:

1.i.j.a

2.i.a Protect the statement 3x Ec/Vl.a(Q)cpi(x,a,Q)

where i = ( e, j) and in some GBdel-enumeration cpi(x,a,Q)

=

~

8

^{(x,a,j,Q) •}

- 22 -

Each condition is coded as a pair ( i, a) E S xI , and by the re- cursive well-orderings on S and I , we order the conditions in the antilexicographical ordering. The order type will be /{k • We will let v denote both a condition and its place in the order- ing.

If v

=

(i,a) we call v an a-condition If v

=

1,i.j,a we call v a 1-condition If v

=

2.i.a we call v a 2-condition

We construct Q~ by induction on

s

^{= (v,cr)} in the antilexico- graphical ordering, where v is a condition, cr E M is called the stage and

s

the position. During the construction we will create requirements for a condition v , and if we are able to keep the requirement disjoint from Q , v will be met. If we at some po- sition

s

add something in a requirement to QS+1 , we injure the requirement. A requirement z is active at position

s

^if

c

z n Q ^'=> =

¢ .

Otherwise it is inactive.

To meet the 1-condition ';

=

1.i.j.a. we will appoint

candidates (r,[i]a) for v , where r

=

^(b,r₁^{) for some r}₁ ⁱⁿ

row(v) , b E I such that r 1 E Mb •

We will reject the candidate if we create a requirement for a con- dition v 1 ^< v • A candidate will always be a new element on the construction. Since we only add unrejected candidates to Q , the priority prob.lem is taken care of this way. When we put a candi- date into Q , we realize it.

We will try to meet the a-conditions inside

cAt

^{a • To keep}

control over the construction it is essential that no injury of an a-condition takes place outside eft a • Thus we will. refuse to do anything with a 1.a-condition outside cfita.

We will now describe the construction:

Let Qo

= 0

If ^C' ':> is a limit-position, let Q;

= u

^{Q ;1}

;1<s

Let

~

^{and Qs -b} be as defined in Theorem 3.1.

Let s

=

^(v,cr)

Case 1 v = 1 i.,;.a Do nothing unless there is an E-computation in I, a and some subindividual of length a • (Proceed to the next position)

Ask: Is there an active requirement for v at position s ?

If yes, let QS+1 = Qs and proceed to the next position. If no, let r1 be element no. (v,cr+1) in <1 • If

cJi

~ F= [i]a is defined (=b) , let c be the least individual > a such that r1 ^EM c and let ( (c,

r

1 ), b) be a candidate for ^{\ ) 0}

Ask: j r E

J1

~

[ (

r is a candidate for v that is not rejected)

&ut{ ~ ¹⁼ [i]a is defined (=b) & r = (r1 ,b)

& r1 E

Ij,aCQ~b)]?

I f yes, choose the first appointed such r and let (1"1° xI) - Qs _{-b -b} be a requirement for v.

Reject all unrealized candidates for conditions v1 ^> v.

For v

1 ^> v, let Q(v1,cr) =

Qsu

(r} and proceed to the

next stage.

If no, let QS+1 = Qs and proceed to the next position.

Case 2 v = 2.i.a

- 24 ....

Ask: Is there an active requirement for v ? If yes, proceed to the next position. If no

Ask: ^X E

r_,NL~(Qs)

[ cpi (x,a,QS)]?

If no, proceed to the next position. If yes

Ask: Is this verifiable from negative information about Q con- tained in some active requirement of higher priority? If yes, let the active requirement of highest priority containing such information be a requirement for v and proceed to the next position (we do not reject candidates unnecessarily). If no,

let .l"'a-Qs be a requirement for v and reject all unrealized

candidates for conditions

v

₁ ^>

v.

position.

Then proceed to the next

This ends the construction, now it just remains to prove that it works.

First note that we sometimes proceed to the next stage, some- times proceed to the next position. There are technical reasons for not wanting to add more than one element to Q at each stage while we do not hesitate too much in dealing with the 2 -conditions.

I f we at stage a ask the questions about v given above, we say that we .l?5Y: attention to v at stage a •

By construction, Qs is uniformly recursive in is a subset of 1 1'1 x I • To prove that Q is

s •

'E*

'

Moreover, we must prove that when r = ((c,r1) ,b) is put into Qs, s E ~. _{If r 1} is in row v , v will be recursive in c and some subindi vidual, by choice of c • But the stage a at which we realize r is re- cursive in v and some subindi vidual, so s

= (

v, a) E

J(

c

=:

^{Jtr •}

We make a change on a condition v at position ; 1 if we realize or reject a candidate for v , create or injure a requirement for v at position

s1 •

Claim 1 Let v be a condition

{ ; 1 ; we make a change on v at

s

1 } has at most cardinality }'(' k-1 • Proof: We cannot make a change on a condition v more that once without making a change on a condition < v • Then the proof is by standard induction on v •

Corollary "if v3

s

(After ; we do not make a change on v )

Proof: This follows by claim 1, since the cofinality of our con- struction is 1"-~ k.

Remark: The argument used in claim 1 will be refered to as 'the priority argument'.

Claim 2 Let a be minimal and not bad. Let v be an a-condi- tion. There is a stage a E . .A{,a after which we will always pay attention to v • In particular, after stage a , no injury of a v-requirement will take place.

Proof: After a

0

= Sup{~_ 1 ^;

^b

^~a}

we will only realize candidates for c-condi tions where

c

^~ a • There are at most /"{' k-2 such conditions of higher priority that v , and for each such conditions there will by the priority argument be realized at most ₁'{k_2 can- didates after a

0 • Since the only reason not to pay attention to a condition is that we at the same stage realize a candidate for a con- dition of higher priority, and since

Kk-1

^a has cofinality

X'""'k-

_{1 ,}

the claim follows by the standard argument.

- 26 -

Claim 3 _C/.,, ^AA a is rudimentary closed relative to Q.

Proof: Let x E c.J.1.,.a. Let b be the least individual such that x E TC C~), and let y E~ be transitive such that x E y, x ~ y • By definition, b is minimal and not bad. In E-recursion there is an index e such that y

=

(e)(b,I,i)

vidual i , so tha formula

is protected by some 2.b-condition 'V.

for some subindi-

By claim 2 there will be a cr E~b after which we always pay at- tention to ^{'V •} Thus, at the first cr 1 > cr such that

ll<e,a,I,i,y)ll ~ cr

1 (as a E-computation) there will either be a requirement for 'V or we will create one. This requirement will never be injured. Thus, for some s EJ{b, yn Qs = yn Q EvM.b.

Since b

~

a , Q S E

J1

a , and x n Q S

=

^x n Q E

J{

a •

Definition. Let x E 1"1 • We say that ¹ x E

u\1.

a ( Q) ¹ is finally protected at stage a if for some e E w , i E S , the statement

(e)Q (i,a,I)

=

x is protected by a requirement active at stage a that is never injured.

Claim 4 Let a, c E I . Let 6 EvAi a,c be an ordinal and let

'x

^{E c)4,a (Q) 1} be finally protected at stage 6 • Assume that in E- recursion (e) Q(

x)

^{.=: x •} Then there is a cr > 6 , cr Er..l{{ a c such that

'

( ) Q(o a)

x E<./1-f .. ~(Q o,cr )(x~ (e) ' (x))

Remark: In the _application, x ~ will come from I U (I) , in which case the assumption is trivially true. The assumption on x ~ seems essential to make the inductive proof work.

Proof: We prove this by induction on the length of the computation

~X • We give the cases where schemes ~ or iv is used.

The methods used here cover vii as well. i , ii , iii are trivial and vi is covered by claim

3.

Case v Composition

Let o ₀

=

~~~

•

By the induction hypothesis there will be stages o1 , ••• , on in , .. M. (a,c)' such that for 1 < m < n

o (o,o ) (o,om)

3

Ym Ec}{am(Q m )(ym ~ (em}Q ( i ) ) .

The associated conditions will be a-conditions, so they will be

paid attention to and never injured after o 1 ⁼ Max(o ;1<m<n} > -rzB,,~.

n+ m - - -~-,

Thus at stage on+1 , all ^'y _m ^E

A

_a ^(Q)' is finally protected. By the induction hypothesis again, there is a 0n+2

~

0n+1 in c}{(a,c) '.

such that

Since u\t(a,c) <r;

1 ^c.f.{ (a,c), , we find a cr in cM(a,c) having the same property as on+2 above.

Case iv (e}(x1 , ••• ,xn) ^~ U (e1 )(y,x2 , ••• ,xn) yEx1

where x1 E ^~ a(Q), ••• ,xn E J{a(Q) are all finally protected at stage o •

First note that when x1 is computed from a and I ' there will be a 1 - 1 map f from an initial segment of (I,<) onto x1 uni- formly recursive in the computation of x1 • We regard the case when f is defined on the whole of I • The other case is simpler.

'

For each y

=

f (b) E x1 , 'y E

cA

a, b ( Q)' will be finally protecteQ.

- 28 -

at stage 6 •

We want to find a stage where all computations

(e1}Q(f(b),x2, ••• ,xn) for bE I are convergent, and first we do this for all initial segments of Io

Subclaim

'tj c'tjy EJvla,ct/b E I3crb EJt(c,a,b)(crb > ^Y &

J crb ( o ' crb) Q ( o ,

cr.J

vd~b3xd E}ta d (Q )((e1 ) (f(d),x2 ,_.,xn) =xd))

'

Proof: After

K~c,a,b)

none of the associated conditions will be

K:-1

injured for d ~ b • By the induction hypothesis there will for all d

~

^{b be an} ordinal after

~=1a,b)

at which the computation

is protected, and the associated requirement is n·ever injured.

Thus, using ~*-collection we find a candidate for crb in cJ'{(c a b)'

' ' '

and by reflection we find it incJ\-'t(c,a,b).. This proves the sub- , claim.

Now we use the DC described in section 2.

Let ^u ~

0

^{-- K~a___ k}

1

^{,c). B y th} e su c aLm, ^{b 1 · f' d} ln a sequence ^{(R )} ub bEI ^E c.A1(a, c), such that b₁ < b₂ ~ t>b

1 < E>b

2 and ( ) (o,o )

. AA 6b ⁰ ' (>b · Q b

\Jbtid ~ b3xd Ect"L.-d,a(Q ((e_{1 )} (f(d),x_{2 , •••} ,xn) Let cr

0

=

Sup ( ob ;b E I} . cr ₀ E

c)ll (

^{c , a) , and cr} ₀ ^{> 6 •}

\ l"

Since the cofinali ty of cr

0 is /\ k , we may use the priority argu- ment on the construction below cr

0 , i.e. for each condition v there is some stage such that between crv and cr we do

0

not change on v. The sequence (f>b}bEI is constructed so that for each dE I, the statement (e1 }QS(f(d),x2 , ••• ,xn)

~

^will

be protected cofinally many times below a

0 • Thus for all d , this computation converges at stage (o,a

0) .

a (o,a ) (o,ao)

But then

3

x

Eo'vl,(~,c)(Q

^{0 )(x= U (e}₁^{}Q (f(d),x}_{2 , •••} ^,xn)).

dEI

Using reflection we find a in

vM

(a,c) gaving the same property.

0 Cl.aim

5

If a is minimal and not bad

/

(}\{ (Q) _a =

J1,

_{a •}

If a is minimal and bad

Proof: Let a be minimal but not bad.

If x E ~ _a (Q) there is an index e and subindividual i such that x

= (

e } Q( a , i , I) •

a, I and i are all finally protected as elements of l}'L a from the very beginning. There. will be an a-condition v associated with the statement

By claim 2 there is a a

eJt

_a such that after a we always pay attention to \1 • By claim 4 there is a a 1 ^{> a} in

c}'L

a such that

Since we pay attention to ^\) at stage _•

If there is no active requierment for \1 at stage a

1 , we will create one, and this requirement will never be injured.

.. 30 -

Then X

=

(v,cr₁)

[e}Q (a,i,I)

=

(eJQ(a,i,I) by the same compu- tation. Since

(v,cr₁)

cr1 E ^c:Ma and \1 E u{{a,

[ e

J

^Q (a, i , I) E J{ a • This was what we wanted to prove.

If a is bad, we use claim 4 again, noting that after ~-

1

^,

\1 will always be paid attention to.

0

Remarks

1. We have now verified parts i and

.ii

in the theorem.

2. If a is bad and (.){a ~ c}{a(Q), then ~-

1

will be in

cfi'L.

a (Q) ' a' E cAa (Q) so v~ a (Q)

=

Jta' •

3.

By Gandy's selection operator, the general statement

']x Ev~'ia(Q)cpi(x,a,I)' is equivalent to the convergence of

~ certain computation. Thus we have 'met' all 2-conditions by claim

5.

Claim 6 If a is minimal, not bad and not the jump of a bad, and if \1 is a 1.a-condition, there is a

i We will always pay attention to ^\1 ii No candidate for ^\1 is rejected.

Proof: i is known from claim 2.

To prove ii we prove the following:

a E~ a after which

Subclaim Let v1 be another condition. We reject a candidate for \1 due to v1 if we create a requirement for ^v1 while we re-

ject the candidate.

If we at a stage after K = Sup[K~_

1

^{; b <} aJ reject a candidate for \1 due to a condition v1 , ^v1 is an a-condition.

Proof of subclaim:

Assume that the subclaim is false, let cr > K,v1 constitute a counterexample. Since we are not dealing with 1.b-conditions for b < a after K, v1 is a 2. b-condition for some b <a.

a .(v1,a)

Assume that

3

^{x E oAlb(Q} )cpj(x,b,I) where v1

=

2.j,b.

Let b

0 be minimal such that b E Jib • Then there is an i E S

0

such that

Let v₂ be the condition protecting

=1 x EJ{ b (Q)cp. (x, b , I) •

- l. 0

0

By claim

5,

this will be met inl}{ b if b

0 is not bad, and in

0

ci1b ¹ if b₀ is bad.

0

In any case, since a is neither bad nor the jump of a bad, there is some a

0 < K such that at stage a

0 , v

2 is finally met with a requirement.

Moreover, for some Thus after Max(a

0 ,a

1), if we pay attention to v

1 , all informa- tion we need is contained in the still active requierment for v2 • But then we would not reject anything. This proves the subclaim.

To end the proof of the claim, note that between K and

the set of conditions due to which we reject a candidate for v has cardinality ..:5, /{ k-

2 , and we may apply the priority argument.

0

We are now ready to end the proof of the theorem, i.e. prove iii • To obtain a contradiction, assume that for some a, b, j

0 ,

M'~ = Ij ,a(Q_b).

0

...,. 32 -

Let c be minimal, not bad and not the jump of a bad such that a,b EJvlc.. Then for some i,j E S, b

=

[i]c and Ij ,aCQ_b)

=

0

Ij,a(Q_[i]C) •

Let \) be ( 1 , i, j , c) • By claim 6, let cr E

ct\t

be such that c

after cr , no requirement for \) will be injured, we will always pay attention to \) and no candidate for \) will be rejected.

If we at some stage cr

1 > cr realize a candidate r = (r 1,b) for \), r₁ will be a counterexample to l"' ... ~ = Ij ,aCQ_b) , since

0

r_{1 E} ~ , r E Ij ,a (Q_b) •

0

So let r

=

(r1 ,b) be a candidate that is neither rejected nor realized. Then r 1

Jl

~, so r 1 E Ij,c(Q_b). Using claim

5

we find cr1 ^> cr such that

(J1 (\),CJ1)

r 1 E Ij, c ( ^{Q )} and we pay attention to \) at stage cr 1 • But then we would add something to ~ at stage cr1 , or there would exist an active requierment for \) at stage cr1 •

we obtain a contradiction.

In both cases

This ends the proof of theorem 3.1.

4. V

=

L and the minimal pair problem for extended degrees of functionals

Let (l"'a)aEI = Spec(k+2E) • Recall from section 1 the tion of ^11"1

, r<?

_~,a and the partial set _J ^(J (i, j) ,a ' and the tions of row, ^<1 < etc. from section 2.

'

^(J

defini- defini-

Our aim in this section will be to give a solution to the mini- . mal pair problem, in the style of section

3.

The main theorem will be the following:

Theorem 4.1 (V

=

L)

There exist two disjoint subsets A and B of 1

M (both re- cursive in A U B ) both l:* -definable such that

~

i

V

a E I, neither A nor B are t.*-definable.

ii If a is a jump, then c-J\JL a (AU B)

=

c}{a.

If a is a limit of jumps, ,}I[ a (AU B) ~ (.)~{,a, •

iii If C is w-

t.;

(A)-definable over Spec(A) and

"'T- t\

^(B)-

definable over Spec(B) for some a,b E I, there is a

*

ck+2 )

c E I such that C is w- toe-definable over Spec E o

Corollary 4.2 (V = L)

There exist two subsets A1 and B1 of tp(k+1), both semi- recursive in k+2E such that neither A1 nor B1 is recursive in k+2E and any individual, and whenever a type k+2 functional F is weakly recursive both in A1 and an individual and in B1 and

. d" "d 1 th F ' akl . . . k+2E d . d"

an ^{~n ~ v~} ua , en ^1, s we y ^recurs~ ve ^~n an an ^{~n ~-} vidual.

The rest of this section will be devoted to the proof of theo- rem 4.1. The proof is based on the w-case (Lachlan [4], Yates[5]) as presented in Shoenfield [14], with inspiration from Lerman-Sacks [5]. It will be an advantage to have the proof in Shoenfield [14]

in mind'.

We are led to the following conditions

2.i.a

A

I=

J. 1,a 1.B.i.a Protection of the statement

·j x E J{ a (AU B)cpi (x,a,A U B)

B

I=

^J. _1,a

- 34· -

If and both are total,

then-this set is weakly 6;-definable over (Mb)bEI for some a.

As in section 3. we use the notions a-conditions, 1-conditions, 2-conditions, 3-conditions and in addition A-conditions and B-con- ditions. The meaning of these notions should be clear.

Throughout the construction we will concentrate on the A-cases.

If nothing else is mentioned, there will be an analogue B-case.

As in section 3 we index the conditions by pairs (i,a)

ordered in the antilexicographical ordering. We identify a condition with its place v in this ordering. Define position and stage as in section 3.

To satisfy the 3-conditions we need infinitely many require- ments, and the problem of priority will be more difficult than in section 3. Before we begin on the formal construction we will give a brief idea of what will happen:

For each position s

=

^(v,cr)

1M, uniformly recursive in B

=

U Bs.

of

sEPos.

we define subsets As and Bs v ,cr • We let A

=

U As and

sEPos.

It will follow from the constructton that if r E A there is a s E M such that r E As •

r

The same will hold for B •

Thus A will be :E*-definable.

We only put elements into A to meet the 1.A-conditions, and for each condition, we put at most one element into A. At certain points in the construction we will appoint candidates (a,r) for a 1-condition v , where r w:ill be in row v • These may be realized or rejected. For reasons of convenience, we say that a candidate (a,r) is

.£!:2!:!!

row v if r is in row v •

To meet the 2-conditions we act like we did in section 3.

To meet a 3-condition we need M-infinitely many requirements.

Given y E M, we may want to protect y E J. 1,a (A) or y ~ J. 1,a (A) by a requirement z for A with argument y and value 'yes' or

'No' according to which statement we protect.

We use active and inactive as in section 3. If v is a 3-con- di tion and if z is a v-requirement for A active at position

s ,

we call z effective if there is no v-requirement z1 for B ac- tive at position

s

with the same argument and value as z. Other- wise z is called ineffective. A requirement is called essential if it is effective at position

s

for all sufficiently large

s.

Otherwise it is called inessential.

We use realize and reject for candidates as in section 3.

Through the rejecting of candidates we take care of the priority problem and some other technical problems.

We will now state some important properties about candidates and requirements, and thereby prove a claim:

1. A candidate r for A can only be realized if it is not re- jected, and we realize at most one candidate from each row.

2. When we appoint r at some position

s ,

r will not be in any requirement created at some position

s

₁ ^~

s.

3. When a requirement for a 2-condition v is created, all un- realized candidates from rows > v will be rejected (we will also reject some candidates when we create a 3-requirement~

see the construction).

4. If we realize a candidate from row v '·we reject all unrealized candidates from rows > v •