Proceedings of the 7th & 8th Asian Logic Conferences: Hsi-Tou, Taiwan, 6-10 June 1999, Chongqing, China, 29 August-2 September 2002

< p,

sa

For the sake of clarity, we record the following. 2.5 Proposition. Let I = (Pp I ordinal L,3 < u, the following hold.

p <

u)

be an iteration. For any limit

c

(UP)* G PO (UP)* and

E

Go iff for

Here is a necessary and sufficient condition to form a limit stage of an iteration. Since we observed the inverse limit is indeed a limit, the verification of this proposition takes nothing. 2.6 Proposition. Let I = (P, I a < u ) be any iteration with the limit ordinal u . For a n y X C I* with 1, E X , the following are equivalent. 0 0

I n ( ( X , < I * [X, l u ) )is an iteration. ( X is called a limit of I ) For any z E X , a < v and u E P,, if u 5, z [ a , then u n z [ [ a ,u ) E

X. Therefore we look for X I* with the set theoretic closure property as above to define a limit. Since any limit is necessarily a suborder of the inverse limit I* of I , we may omit mentioning the order relations on the limits. The direct limit I , is the &-least closure with 1, in it. More generally, we observe the following.

2.7 Proposition. Let I = (P, I Q < v) be any iteration with the limit ordinal u. For any z E I * , let us define (.) = {u-x[[a,u ) I a < u,u E P, and u 5 , z [a}U I,. Then we have

308

0

0

0

(The single element closure) -I n ( ( z ) ) is an iteration and x is in the limit. In particular, (1,) = I*. (The closure) For any X C I * , let us define = 1 zE X}. Then I n ( x ) is an iteration and X is contained in the limit. (The meet and join) If both I n ( X ) and I - ( Y ) are iterations, then so are I n ( X n Y ) and I n ( X U Y ) .

x u{(.>

This means that the set of possible limits is a lattice under the inclusion whose minimum is I* and whose maximum is I*. Now we may ask which ones with what properties are important and when ? We close this section with the following on the dense subsets and the intermediate stages.

2.8 Lemma. Let I = (P, I a < u ) be any iteration. Suppose i 5 a 5 j < u, G , is a Pa-generic filter ouer V and set Gi = G,ri as usual. If D E V [ G J is a dense subset of Pij, then for any x E Pj with x [ a E G,, there is y 5 z s.t. y [ a E G, and y[[i,j) E D . Proof. The case a = j suffices. The rest is standard.

0

3. The Dynamical Stages, Simple Limit and Iterations

The following is a modified version of p. 539 of [3]. 3.1 Definition. Let J = (Pa 1 a 5 u> be any iteration with the limit ordinal u . Any P,-name ci is called a P,-dynamical stage ( or simply stage), if the following two hold. 0

It-p""&

5 u".

If p I ~ p v " c i= omit - 's)

p , then p [ J n l , [ [ J , u ) (kpv"d!= p .

(We usually

The idea is we want ci < u in relevant cases and use the value as a stage of the iteration below u. We also demand ci = u in irrelevant cases. We do not just set ci = 0 in irrelevant cases. We present typical dynamical stages.

3.2 Proposition. Let J = (Pa I a 5 u ) be any iteration with the limit ordinal u. The following are typical. 0

(Checks) For any Q

5 u, the P,-name fi is a P,-dynamical stage.

309

0

(Max) If both d! and ,b are P,-dynamical stages, then so is any P,-name for the maximum (in Vpu) of these two ordinals.

Dynamical stages enjoy the following properties. 3.3 Proposition. Let J = (Pa I a 5 u ) be any iteration with the limit ordinal u . Then for any P,-dynamical stage d! and 7 5 u, we have independences as follows.

wdr,

itpv vcp(&,

If P II-~,, f j ) ’7, then PrV-1, r[q, f j ) 77, where “ q ( d ! , i j ) ” stands for any of “d! < f j ” , % = f j ” , ‘Yj < &”, “d! < q”7 or ‘Yj _< d!”. We consider conditions with associated dynamical stages as follows. The comments in the parentheses are easy to verify.

3.4 Definition. Let J = (Pa 1 a 5 u ) be any iteration with the limit ordinal v. For any x E P, and P,-dynamical stages (8, I n < w ) , we say (6, 1 n < w ) is a sequence of P,-dynamical stages for x, if the following three hold. 0 0

For any n < w , lkpu“8, 5 &+I 5 u ” . (increasing) For any n < w , x lkpv“h, < u” . ( x may not decide the values of &, but knows that they are all strictly less than u. This is equivalent then &, < Y”.) to lkp,, “if x [ & E G,[in, I~p,,“If8 = SUp{Jn I n < w } ( < u ) and x [ 8 E G,[8, then x E G,”. ( x [ b knows that the rest of x is equivalent to l,[[&,u)in 4 , . Namely, this is equivalent to ( k p ,“if 8 =sup{& 1 n < w } and x [ &E G, 18, then XI[&, u ) G 1, “8, u)”.)

In the above, we may also say that x has (a sequence of) P,-dynamical stages (8, I n < w ) . We say 6, is a lc-th P,-dynamical stage (or simply k-th stage) for x. It is clear that for any < u , (( 1 n < w ) is a sequence of P,-dynamical stages for 1,. In general, x E P, may or may not have any sequence of P,-dynamical stages.

<

We now observe some of the important properties of dynamical stages.

3.5 Lemma. (Hooking) Let J = (Pa I a 5 u ) be any iteration with the limit ordinal u. Suppose y 5 , x, (inI n < w ) and (rj, I n < w ) are P,-dynamical stages for x and y , respectively. Then we have P,-dynamical stages ( ~ 1kn < w ) for y s.t. for any n < w , Ikp,, ‘$,+I 5 rjk and rjn 5 rjk ”.

310

Proof. This is easy. Just let

ik

= the maximum of

(An+l,in}

in V p u . 0

We are free to move stages forward and choose a O-th stage. This is a specific case of Hooking above. 3.6 Corollary. Let J = (Pa 1 Q

5 u ) be any iteration with the limit ordinal

u. The following hold. 0

0

If x E P, has P,-dynamical stages (8, I n < w ) and E < u, then there are P,-dynamical stages (in1 n < w ) for x s.t. for any n < w , x I ~ P ,‘Gn, , 5 I +n ”If x E P, has P,-dynamical stages and < v, then we may prepare P,-dynamical stages (Ak I IC < w ) for x s.t. ~t-p,, 4 0 = E”.

<

We consider an operation on the limit stages. 3.7 Definition. Let J = (Pa1 Q 5 v) be any iteration with the limit ordinal v. The suborder D(P,) = {x E P,, 1 x has P,-dynamical stages} of P, is called the dynamical kernel of P,.

Sometimes nothing new happens.

3.8 Proposition. Let J = (Pa I ordinal u. The following hold. 0

0

Q

5

u)

be any iteration with the limit

If P, = ( J [ u ) * (i.e., P, is the direct limit of Jru), then D(P,) = p,. Ifcflv) = w , then D(P,) = P,.

The dynamical kernel provides us a limit and the operation D enjoys that D2 = D. Namely, P,-dynamical stages are turned D(P,)-dynamical stages. The following are both crutial. 3.9 Lemma. Let J = (Pa I Q 5 u) be any iteration with the limit ordinal u. And we write I = J [ u for short. (1) Then I n ( ( D ( P u ) 5 , , [D(P,), 1,)) is again an iteration. Namely, we have the closure as follows. 0 0

1, E D(P,,).

I f x E D(P,), a u ^ x [ [ a ,u ) E D(P,).

<

u, u E

Pa and u La

X[Q,

then

31 1

(2) And D(D(P,)) = D(P,) holds. Namely, we have 0

For any x E D ( P V ) ,there is a sequence of D(P,)-dynamical stages for x. (In general, given limits X, Y of I with X C Y and x E X, Y-dynamical stages for x naturally give rise to X-dynamical stages for x.)

Proof. Since we are free to choose a 0-th stage, it is easy to observe the closure properties so that D(P,) is indeed a limit. We provide some details to the latter half. Let X and Y be any limits of I with X C Y . Namely, both I - ( X ) and I - ( Y ) are iterations. In particular, both X and Y are suborders of I*. Suppose x E X has Y dynamical stages (&, I n < w ) . We may define a sequence (8, I n < w ) of X-names as follows, where G x denotes the X-generic filter over V .

i,

=

{ <,v,

<

if < v and a-1 otherwise.

11-y "&,

=

for some a E G X I<.

We claim this (8, I n < w ) is a well-defined sequence of X-dynamical stages for x. We only verify two conditions.

x I k X " 6 , < v".

<

Proof. Suppose x1 5 x in X . We want to find 2 2 5 x1 in X and < u s.t. 2 2 IFxLL6, = t". Since both x and x1 are in X and X C Y , these belong

to Y.By assumption, x IkyL'&,< v". So we have x1 I ~ Y " & , < u " . Hence there is (a,<) s.t. < u , a E Pc with a 5 XI[[ and a-1 Iky"&,= 5". Let x2 = anxl[[<, v). Since x1 E X, we have x2 E X . This 2 2 works. 0

<

0

Ikx "If h = sup{& I n < w } and x[8 E G X [&,then x E G x " .

Proof. Suppose x1 E X, S < v, x1 1kx"d-= sup{& I n < w } = 6" and x1rS 5 x[S. We show x1 5 x and this suffices. To this end, we first observe x1 [S-1 IFy"sup{&, I n < w } = 6" as follows. Let G y be any Y-generic filter over V with x1[6-1 E G y . We would like to calculate SUP{(&,)G~ I n < w } . TOdo this, we fix an X-generic filter G x over V s.t. 21 E G x and G x [S = G y [S. This is possible, since both I - ( X ) and I - ( Y ) are iterations. For each n < w , let = ( 8 , ) ~ ~in V [ G x ] . Since 5 6 < u , there is a, E Gxr<, s.t. a;l IkyLL&, = 5,". Notice that a z l E G y by the way we fixed G x . So ( & ) G ~ = <., Therefore (<, I n < w ) = ( ( & , ) G ~ I n < w ) E V [ G y ]and SUP{(&,)G~I n < w } = 6.

<,

<,

312

Since (& I n < w ) is a sequence of Y-dynamical stages for x and we have seen x1 [S-1 I~yi‘sup(ciYn I n < w } = 6 and x1 [S E GyrS”, we get x1 [S-1 Iky“x E Gy”. Hence x1rS-1 5 x. In particular, x1 5 x holds. 0 Let us close this section by defining the limit and iterations we are interested in. 3.10 Definition. Let I = (Pa I a < v) be any iteration with the limit ordinal v. The simple limit of I is the suborder D ( I * )of I* (i.e., ( D ( I * ) 51. , [ D ( I * )lv), , where D ( I * ) denotes the dynamical kernel of the inverse limit I*of I ) . 3.11 Definition. An iteration I = (Pa I a if the following two hold.

< v) is called a simple iteration,

+

(The fullness at the successors) For any a with a 1 < v, if p l k p , “ ~E P,+l with ~ [ Ea G:,”, then there is q E P,+l s.t. q[a = p and p I ~ P , “qr[a,a 1) ~ [ [ aa , 1 ) in P:,:,+l”. For any limit a < v , Pa is the simple limit of Ira.

+

0

+

The fullness at the successors differentiates the (simple) iterations from (mere) products. The usual recursive construction would satisfy this requirement. And we just recursively take the simple limit at every limit stage to construct our iteration. We sum up as follows. 3.12 Proposition. Let I = (Pa I a < v) be any simple iteration. For any limit ordinal j < v, the following hold.

0

0

( I [ j ) *C Pj 5 ( I [ j ) * For any x E ( I [ j ) * x, E Pj i$x has a sequence of (I[j)*-dynamical stages. And so if c f ( j ) = w , then Pj = ( I [ j ) * . (This is the same as countable support iterations. However at j with cf(j) 2 w1, we may get bigger Pj than the direct limit.) For a n y x , y E P j , x Lj y i f fVcu < j z[cu 5, y r a . For any i < j and x E Pj, x has Pj-dynamical stages (An I n < w ) s.t. Ikpj ‘80 = i”.

4. Nested Antichains and Fusion Structures

We would like t o introduce nested antichains. We motivate this object in relation to an analysis of dynamical stages as follows. Let J = (Pa 1 a 5 v)

313

be any (simple or not) iteration with the limit ordinal v. Suppose we have given a sequence (& I k < w ) of Pu-dynamical stages for some z E P,. We want to analyze this situation. The following construction would come up with a single dynamical stage. And this construction will be recursively nested, since we have countably many dynamical stages. 4.1 Proposition. Let J = (Pa I a 5 v) be any iteration with the limit ordinal v. If x E Pu, is a P,-dynamical stage , J < v and a E Pt s.t. a 5 x[J and a - z [ [ J , v ) lkpv 5 < v ” (and so we m a y replace a-z[[J,v) by a-l,[[<,v>), then there is B g U{Pa I a < v} s.t.

b

a a a

‘x b

For b E B , J = l ( a ) 5 l ( b ) < v, b 5 u ^ x [ [ J , l ( b ) ) and b-11t-p” = l(b)”. { b [ l ( a )I b E B } is a maximal antichain below a in Pl(a). For any b, b’ E B , b[l(a)= b‘[l(a) implies b = b’.

q

It is conceivable that B = { a } . And when B has more than one elements, the lengths l ( b ) may vary with the b’s. So a gets partitioned into B[J and each element in B [ J end-extented to a unique b. With this motivation in mind, we make the following. (This and the next defined in [4].) 4.2 Definition. Let I = (Pa I a < v) be any iteration with the limit ordinal v. A nested antichain in I is a triple (T, (T, I n < w ) , ( suc; I n < w ) ) s.t. a

0

0

T = U{Tn I n < w } . To = {ao} for some a0 E U{Pa I a < v}. For any n < w , T, g U{Pa I a < v} and suc;

: T, + P(T,+l). For any a E Tn and b E suc$(a), l ( a ) 5 Z(b) and b[l(a) 5 a. For any a E T,, {b[l(a)I b E suc;(a)} is a maximal antichain below a in Pl(,). For any a E T, and b, b‘ E SUC$(~), if brZ(a) = b’[Z(u),then b = b’. Tn+1 = U{SUC$(~) I a E Tn}.

We talk about nested antichains by just writing T for brevity. Now we move on to consider a binary relation between the set of nested antichains T and the inverse limit I*. The T’s in the domain of this relation specify equivalent elements in I* via this relation. Hence the T’s in the domain represents a set of conditions in I * . It is known that this set of conditions forms a limit stage of I and is called the nice limit in [4].

314

4.3 Definition. Let I = (Pa I a < u ) be any iteration with the limit ordinal u. For any nested antichain T in I , x E I* is called (T,I)-nice, if the following hold. 0

0 0 0

x [ l ( a o ) ao, where {ao} = TO. For any a E T,, a 5 xrl(a). For any a E T, and b E sucF(a), b = b[l(a)-x[[l(a),Z(b)). For any a < v and w Pa with w 5 x [ a , if w I t p a “ there is a sequence (a, I n < w ) (this is called a generic cofinal path through T in v[G:,]) s.t. a. E T ~for, any n < w , a, E T,, a,+l E s u c ~ ( a , ) , /(a,) 5 a and a, E Ga[l(a,)”, then w - z [ [ a , u ) = w - l u [ [ a , u ) .

Nested antichains with associated nice sequences can be regarded as conditions as follows. 4.4 Proposition. Let I = (Pa I a

< u ) be any iteration with the limit ordinal u . Suppose T is a nested antichain in I and x E I* is (T,I)-nice. If x E X and I n ( X ) is any iteration (i.e., X is any limit stage of I ) , then the following holds, where GX denotes the X-generic filter over V . 0

I ~ ‘xx

E G x i f f there is a generic cofinal path through T in

V[GX]”. Proof. Suppose x E G x . We construct a generic cofinal path by recursion. Since x rl(a0) ao, where ao E TO,we have a0 E G x [l(ao). Suppose we have gotten a, E T, n (Gx[l(u,)). Then there is a,+l E sucF(a,) s.t. an+1 ri(an) E Gxri(a,). B U ~a,+l a,+l [l(an)-xr[l(a,),l(a,+l)) and ~ ( a ~ + his ~ ) . xr[i(an),~ ( a , + ~ )E) G~ r[l(an),G , + ~ ) ) . so a,+l E completes the construction. Conversely, suppose we have a generic cofinal path (a, 1 n < w ) through T in V [ G x ] .Since a, 5 x [ l ( a n ) ,we have x [ l ( a n ) E Gx[l(a,). Set a = sup{l(a,) I n < w } . Then x [ a E Gxra. Now if a = u, then we are done. So suppose a < v. We note that (a, I n < w ) E V [ G x r a ] .This is because we may define the sequence via G x [a. So we may take w E G x [a s.t. w 1t-p- “there is a generic cofinal path through T in V[Ga]”.Hence wnxC[a, v) w n l u [ [ a , u )and so x E G x . 0

=

cx

Although it is more tedious than above, we may prove the following equivalence along the same line. 4.5 Proposition. Let I = (Pa I a

<

u)

be any iteration with the limit

315

ordinal Y and T be a nested antichain in I . For x E I * , the following are equivalent. 0

x is ( T ,I)-nice. For any a < v, lkp? “xra E G, i f f (either there is a E T s.t. Q < l ( a ) and ara E G, or there is a generic cofinal path through T in V[G,])”.

As we see below nice sequences belong to dynamical kernels. 4.6 Proposition. Let I = (P, 1 a! < u ) be any iteration with the limit ordinal u. If x E I* is ( T ,I)-nice for a nested antichain T in I , then x E D( I *) . (i.e., x belongs to the simple limit of I.)

Proof. We must exhibit I*-dynamical stages (b, I n < w) for x. For each n < w,we define an I*-name b, as follows, where GI* denotes the I*-generic filter over V .

&+I =

if a E T,, b E suc$(a), b[l(a) E otherwise.

We claim this (b, I n and left.

GI* [Z(a) for some a and b.

< w)is well-defined and works. Details are routine 0

Now we move on to consider a type of basic construction at the limit stages of iterations. We would like to introduce what we call fusion structures. For the sake of motivation, we first mention a typical diagonal construction.

4.7 Proposition. Let J = (P, I Q 5 w) be a simple iteration. (So J is a usual countable support iteration of length w.)If (P, I n < w) is a sequence of elements of P, s.t. f o r all n < w,p,+l 5 p , and pn+l [(n 1) = p n [ ( n l), then there is p E P, s.t. for all n < w,p 5 p , hold. In fact, we may coastructp = (pn(n)I n < w) so that f o r all n < w,p [ ( n 1) = p , [(n 1) get satisfied.

+

+

We generalize the above as follows. (This defined in [4].)

+

+

316

4.8 Definition. Let J = (PaI a 5 v) be any iteration with the limit ordinal v and T be any nested antichain in Jrv. A structure F = ((a,n)I+ ( X ( ~ I ~(df’”) ) , I k < w))1 a E T,,n < w)is called a fusion structure in J , if the following three hold. 0 0

0

(6f’”) I k < w)is a sequence of P,-dynamical stages for x ( a , n )E P,. a 5 rl(a) and a-1 lkp,,“&g’n) = Z(a)”. (a-1 decides the ~

(

~

1

~

)

value of the 0-th stage for x ( ~ > ~ ) ) For any b E sucF(a) and k < w, and Ikp,, 5 < &f“n+l)”. ( With the Boolean value 1, the k-th stage for x(b,n+l) is ahead of and bounds the (k 1)-st stage for x ( ~ , ~ ) . )

“&hy)

+

A condition y E P, is called a fusion of the fusion structure F,if y is (T,J [v)-nice. 4.9 Lemma. (Fusion) Let J = (Pa I a 5 v) be any iteration with the (8f’”’ I k < w))I a E T,,n < w) limit ordinal v. If F = ((a,n)c) is a fusion structure in J with a fusion y E P,, then y Ikp,, “there is a generic cofinal path (a, I n < w) through T in V[G,] s.t. for each n < w, (

X(GL>4E

G,

~

(

~

1

~

1

,

J’.

Proof. Straightforward.

0

As far as simple iterations are concerned, every nested antichain may be regarded a single condition. Namely, nice sequences exist for all nested antichains. This is a main technical lemma stated as follows. 4.10 Lemma. Let J = (Pa I a

5 u ) be any simple iteration with the limit ordinal v. Then for any nested antichian T in J r v , there is x E P, s.t. x is (T,Jrv)-nice.

Proof. x has the only possible definition and we prepare a right induction hypothesis as follows. The harder part is to show x [ a E Pa for limit a 5 v. We must exhibit an appropriate sequence of (J[a)*-dynamical stages for xra. Some details follow. For i < v , we first define .ri E Vpi in four cases as follows. 0 0

+ +

.ri = aor(i l),if i < l ( a 0 ) and aori E Gi,where ao E TO. .ri = b[(i l), if there is (n,a,b) s.t. n < w,a E T,, b E sucF(a), l ( a ) 5 i < l ( b ) and b [ i E Gi.

317

0

~i = l i + ~ if , there is a generic cofinal path (a, I n < w ) through T in V[Gi].(This case explicitly mentioned to indicate the mutual exclusiveness precisely.) ~i = l i + l , otherwise.

The term

lkpi “

ri

is well-defined. We have

~ iE

Pi+l and ~i [i E Gi”.

We next define pi E Pi+l as follows. Here we use the fullness of the iteration at the successors. 0

pi E Pi+l s.t. piri = l i and

Ikpi “ ~ i [ [+i ,1) i

+

pi[[i,i 1)”.

We lastly set z = (pi(i) I i < v). We claim this z works. We show the following by induction on a for a 5 v.

zra

E P,. PI(”): If a0 E TOand Z = min{a,Z(ao)}, then ao[Z x[Z. p z ( a ) : If a E T, and I = min{a,Z(a)}, then arZ 5 zrl. p 3 ( a ) : If a E T,, b E suc$(a), Z(a) 5 a and Z = min{a, Z(b)}, then b[Z E b[l(a)-z[[Z(a),Z). ’p4(a):If t 5 a, w 5~ zrt and w I t p E“there is a generic cofinal path through T in V[G,]”,then w-z[[t, a ) w-1, a).

=

[[r,

Since all but showing ‘po(a)are routine, we provide more on this. We first fix a correspondence ( ( i , u )++ ( & ( i , u )1 k < w ) 1 u E Pa,i< a 5 v for some limit ordinal a ) s.t. 0

(&(i,u) I k < w ) is a sequence of (J[a)*-dynamical stages for u E Pa with Jk(Jr,)*“iyo(i,u)= i”.

This is possible, since P, is, by definition, the dynamical kernel of ( J [ a ) * and we are free t o choose 0-th stages. Let us recall TO= {ao}. We have two cases.

=

5 Z(a0): By induction, we have uo[a zra in (.Ira)*.So the (J[a)*-dynamical stages (&(O,ao[a) I k < w ) work not only for a0 [a but also z [a. We conclude z [a E P,. Case 2. Z(a0) < a: We define (J[a)*-dynamical stages (& I k < w ) as follows. Given any (Jra)*-generic filter G* over V , we form the generic extension V[G*]. Now we first define (the interpretation of) &, by Case 1. a

318

0

cio = l(ao),if a0 E G* [Z(ao).

0

cio = a , otherwise.

We next define (the interpretation of)

&+I

by

- l ( b ) (< a ) , if there is (a,b) s.t. a E Tk, b E suc$(u), Z(b) < a and b[Z(a)E G*[Z(a). &+I = cik+l(#?(a),b[CX)G* ( 5 a ) , if there is ( n , a , b ) s.t. n 5 k, a E T,, b E suc$(a), l ( a ) < a 5 Z(b) and b[Z(a) E G*[Z(a). &+I = a , otherwise.

&+l

0

0

So the basic idea is that we descend through T along the nodes ao, a1 and so forth which are in the corresponding generic filters as much as we can. And once we are about to hit any node whose length is greater than or equal to a , then we cut short the condition at a and switch to the stages which are already associated to the cut one. So if we arrived at some a, and a,+l s.t. a , E T,, a,+l E SUC$(U,), Z(an) < a 5 Z(a,+l), a, E G*[Z(an)and a,+l [Z(an) E G* [Z(an),then we begin to use (&+I @ ( a n )a,+l , [a)I n 5 k < w ) . We claim that these (J[a)*-stages (& I lc < w ) are well-defined and that work for x [ a , so that x [ a E P,. Since the verification of this is quite routine using the induction hypothesis, we leave it to the readers.

4.11 Corollary. Let J = (P, I a 5 v) be any simple iteration with the limit ordinal u. For any fusion structure .F in J, there is a fusion x E P, of

F.

The following generalizes the fullness at the successors. A name of a condition is indeed a condition, so to speak.

4.12 Corollary. Let I = (P, I a < u ) be any simple iteration. If a 5 p < v, p E P, and T is a P,-name s.t. p lkpa (5- E Pp and T[a E G, ”, then there is w E Pp s. t. w [a = p and p [/-pa ‘5-[[a, p) w [[a,p) in P,p ”.

=

+

Proof. We may assume P w < u by lengthening I , if necessary. We construct a nested antichain T in I [ ( P+ w ) so that

. 0

To = { P I . For all b E T I ,b[aIt-p,“b[[a,p) = ~ [ [ a , p ) ”(So . bra decides the value of T , bra 5 Tra and may set b = b [ a - ~ [ [ p).) a,

319

a

T,+1 = T, and suc$(b) = { b } for all n 2 1 and all b E T,.

So we first partitioned p to form TI deciding the values of r. We then just keep attaching the same condition below each element of T, for n 2 1. Let y E be a fusion of T . We may assume y[a = p . Then it is easy to see w = y r p works. 0 5 . Constructions of Fusion Structures

We first quickly review relevant definitions. For a regular cardinal 6 , He denotes the set of all sets which are hereditarily of size less than 8. If a preorder P is in He, then I/-~‘‘{T& 1 T is a P-name s.t. r E H F } =

H r [ G 1 ”An . elementary substructure N of He means ( N ,E) is an elementary substructure of (He,E). We write N 4 He for short. We only consider countable ones in this note. If P E N 4 He, then It-p“{re I r is a Pname s.t. r E N } 4 Hr[G1”. And we write N[G]to denote this c-least

c

elementary substructure M of HrlG1 s.t. N U {G} M . In this section, we prepare for recursive constructions at limit stages of simple iterations. These constructions amount to forming fusion structures. And we have seen that fusions exist for all fusion structures. Here is a typical single step.

5.1 Lemma. (A step forward) Let I = (Pa I (Y < v) be any simple iteration. Suppose we have given (a,i,j,x,(jk(x) 1 k < w ) , D ) s.t. a

a

a E Pl(a),i 5 Z(a) < j < v and j is a limit ordinal. z E Pj has Pj-dynamical stages ( & k ( x )I lc < w ) . u 5 xrl(a) and a-1 IFpj %,(x) = I(u)”. D is a Pi-name and a [ i Ikpi “D is a dense subset of Pij ”.

Then a forces that there is ( y , ( & k ( y ) I k V[Gl(,)]s.t. the following hold. Y E pj, 7J (&k(y)

all lc E u-1 ‘1L

< w ) , u)in the generic extension

5 x, Y V ( a ) E G ( a ) and Y “ i , j )

E

D.

I k < w ) is a sequence of Pj-dynamical stages for y

< w , IFPj %+I(%) 5 & ( y ) ” . S(,)l, ( a. ) I l(u) < j, ‘1L I Y r w IFFj ‘%J(y)

.rl(.>

s.t. for

E G ( a ) and

= Z(u)”.

Furthermore, if 6 is a regular cardinal, N is a countable elementary substructure of He s.t. I € N and a JFq(,)“NU{x, (8k(x) I k < w ) , b , G ~ ( ~ ) }

s

320

" assume (y, (8k(y) 1 k < w ) , u ) E ilk in the above. (We do not require url(a) 5 a , since a would be somewhere out side of M and we want u to be in ilk.)

ilk 4 H,VIG'(a)l hold, then we may

Proof. Straightforward. Use lemmas 2.8 on dense subsets and intermediates, 3.2 on stages and 3.5 on hooking. 0 We present a typical recursive construction at limit stages.

I = (Pa 1 a < u) be any simple iteration. We fix a regular cardinal 6 and a countable elementary substructure N of He with I E N . Assume we have given i and a limit ordinal j with i < j < u. There is no need to assume i , j E N . Suppose we are given ((a,P)H E a p I i 5 a 5 p < j ) s.t. for each a , @with i 5 a 5 p < j , E a p is a Pa-name and the following hold. 5.2 Lemma. (Weaving) Let

1

0

Ikp, "If N

0

w [a E G a }?,. It-p, "If NU {Ga,u}C M 4 Hy[G"l,u E Pp and u[a E Ga,then there is w 5 u s.t. w E E a p ( M )".

U {Ga,/3}C M

< H:[G"], then & p ( M ) E { w

E Pp

(This is going to be realized as an induction hypothesis in the next section).

Now if we start as follows:

a E Pi, x E Pj with a 5 x [ i , (D,I n < w ) is a sequence of Pinames and E HBp' s.t. a 1t-p; YV U {Gi,x} 5 & +I Hy[G'l (and so i , j are in M ) and (D,I n < w ) enumerates the set of all dense subsets of Pij which are members of A?"

M

Then we may construct a* 5 x s.t. a* [i = a and a* forces the following: There is ((an,an,un,wn, M,,x,) 1 n < w) in the generic extension V[Gj] s.t. 0

a. = i, a0 = a , uo = wo = xri, MO= h;rci and xo = x. i < ( Y , < j , a , , u , , w n E P , n , a , ~ ~ n ~ U , anda,EG,,,. N u { G a n } E Mn 3 H;[G"nl and M , E Hy[G"nI

0

x , E Gj n M,, u, decides the value of some 0-th stage for x, to be a,, U , 5 x,[Q, and un E M,.

321

Proof. We combine lemmas 5.1 on a step forward (with M ) and 2.8 on dense subsets and intermediates. We construct a fusion structure T = ( ( a , n ) c) (dazn), (8p.”)I k < w ) ) I a E T,,n < w ) together with (j$f(uin) I a E T,, n < w ) as follows. We first define objects for n = 0 so that 0

I k < w ) and j$f(”olo)

a. = a , d a o l o ) = z, z has Pj-stages

=

M. Since we are free to choose 0-th stages, we may assume

IFPj

= $7

“ @ O N

Since we have I E N 4 He, the above kind of correspondence (i.e., ( i , j , x ) C ) Pj-stages (& I k < w ) with Ikpj “60 = i” for i < j < v, j is a limit ordinal and z E Pj) is available in N . But a Ikpi “NU {Gi,z} C A2 4 ~ ~ [ G, so i we l ~may ~ assume 0

Ikp, LL(6k’o) I k <w) E

a0

We proceed recursively.

( d a t n ) , (8Ftn) 1 k < ~ ) ,

j$f7,.

Suppose we have constructed ( ( a , n ) ++ d (1 ~ a E*T,) ~ )s.t.) for each a E T,, the fol-

lowing hold. 0

0 0

a E Pqa) with i 5 Z(a) < j . E Pj has Pj-stages (8p’”’ I k < w ) . (fusion structure) [Z(a) and a-1 Ikpj “6~’”’ = Z(a)”. (fusion structure) a< -

~

(

~

3

~

)

a I F F l @ )“A2 u {Gq+

Z(a+),

(q“) I k

<

Matn) 4

w)}

H,VIG,,a,l,,

w e construct ( ( b ,n + 1) C ) ( z ( b I n + l ) , ( 6 ~ ~ n +1 1 ) < w ) , A2(bi”+l) ) l b E sucF(a)) t o form T,+1 s.t. for each b E sucF(a), there are u and w with the following. 6, U , w E Pl(b),Z ( U ) 5 Z(b) < j and b

5 w 5 u5

~

(

~

1

”

~

’

rZ(b). )

322

0 0

0 0

z(b’n+l)E Pj has Pj-stages (hr”+” I k < w ) . dbyn+’) < z(a>n). (fusion structure) (fusion structure) Ikpj 6‘ 6k+1 .(a’) < - k bri Ikpie e ~ ( b ~ n[[i, + l )j ) E &”. u decides the value of df’nf’) to l(b). (u-1 lkpj r‘d-f’n+l) brl(a) IkpIca, “z(~J’+’), u E A&’,”’’. ccw E G ( ~ ) ~ ( j$f(w4),,. ~)( b r w

blt-Pl(b) < i & f ( b , n + l ) = j$f(a,n)G

( b )

r[l(.)>

= Z(b)”)

V[G(b)l,,

l(b))l 4 H0

The construction is straightforward via lemma 5.1 on a step forward. We now take a fusion a* of F via lemma 4.10 on the existences of nice sequences for the nested antichains. We may assume a* [i = a . So we are done. 6. The Simple Iterations of Semiproper Preorders

We recall relevant definitions. A preorder P is called semiproper iff for all sufficiently large regular cardinals t9 and all countable elementary substructures N of Ha with P E N , if p E P n N , then there is q p s.t. q lkp“N[G]n w r = N n w y ” . In this case, q is called (P,N)-semi-generic. It is known that club many N ’ s at a sufficiently large regular cardinal 8 suffices in the above. (pp. 102, 483, 484 in [3])

<

6.1 Definition. A simple iteration I = (Pa I a < v) is called a simple iteration of semiproper preorders, if for any a with a 1 < v, 1t-p- “Para+l is semiproper”.

+

Here is our preservation theorem for the semiproper preorders. 6.2 Theorem. Let I = (Pa I a < v) be any simple iteration of semiproper preorders. Then f o r any i 5 j < v, we have [bpi“Pij is semiproper”. More technically, we have the following. Let B be a suficiently large regular cardinal and N be a countable elementary substructure of H0 with I E N . Then f o r any j < v, the following holds. 0

<

For any ( i , z , a , & f ) s.t. i 5 j , z E Pj, a zri and aIkpj “NU {Gi,z} E j$f 4 HBVIGil”, there is a* E Pj s.t. a* 5 5, a * [ i = a and a Ikpi “a*r [ i , j ) is (Pij,&f)-semi-generic”.

323

Since we have the fullness of names for conditions by corollary 4.12, the above is equivalent t o the following.

For any i with i 5 j < v, 1t-p; “if N U {Gi} & M 4 H ,V[GiI, x E Pj n M and xri E Gil then there is y 5 x s.t. y r i E Gi and y[[i,j) is (Pij, M)-semi-generic”.

Proof. We proceed by induction on j < u. If i = j, then there is nothing to prove. We may assume i < j. Now we have two cases . Case 1. j is a limit ordinal:

Suppose we have given (i, x,a , M) as in the statement. We make use of lemma 5.2 on weaving. We first define (I& 1 i 5 a 5 ,Ll < j). For each a and ,L? with i 5 a 5 p < j , we set

II-P~“&/J(M)= {w E PO I wr.: E G a , wr[a,p) is ( P , ~ , M ) semi-generic} for all M with N u {Ga,/3} & M 4 HYIGal (and so Pap E M ) ” . By induction, for any a and /? with i 0

5 a 5 /3 < j, we have the following.

lkpa“If N U {Ga,u}E M 4 Hr‘Gal, u E Pp and ura E G,, then there is w 5 u s.t. w E E u p ( M ) . (i.e., wra E Ga and wr[a,P)is (Pap,M)-semi-generic)” .

Since we assume 0

a

5 xri and a Itp; “ N u { G i , x } & h!f 4 HY[Gi1”.

We may take a sequence (D,1 n 0

< w ) of Pi-names s.t.

a lkpi “(b, 1 n < w ) enumerates the set of all dense subsets of Pij which are members of A?”.

Now by lemma 5.2, we get a* 5 x s.t. a*[i = a and a* forces, among others, that there is a sequence of objects ( ( a n M,, l w,,x,) 1 n < w ) in the generic extension ~ [ G j s.t. l 0

i = a0 5 a, 5 a,+1 < j . 2 G i = M,, M , 4 H~V[GL-,I and M , E

0

Mn C Mn+l = Mn[Ga,an+l]. x = xo 2 x, 2 x,+1 in Pj.

c

H,V[~~~I.

324

Since the D,’s have been taken care of, we may conclude

But we have

Case 2. j is a successor ordinal:

<+

Let j = 1. Notice that since we assume i by induction, we have a* E Pc s.t. 0

< j, we have i 5 <. Now

a*[i = a, a* 5 x[< and a IFpi “a*[[i,<) is (Pie, $if)-semi-generic”. 1Fpc “Gt E

$if[Gic]4 Hr‘G‘l and so Pcc+1,x[[<,J+l) E & f [ G i ~ ] , where $if[Git]abbreviates (G)(bcri)[Gt [[i, <)I”. So we have But a*

a* 1Fpc “There is 7r semi-generic”.

5 x[[<, < + l )in Ptc+1 s.t.

7r

is (Pee+,,$if[Gie])-

Now by the fullness at the successors, we may take a* E P C +s.t. ~ a* [<= a* and a* lFpc “a* [[<, 1) G A”. It is easy to check this a* works. 0

<+

The following would be a working knowledge on the simple iterations of semiproper preorders.

6.3 Lemma. (Weaving after preservation theorem) Let I = (PaI Q < v) be a n y simple iteration of semiproper preorders. W e fix a suficiently large regular cardinal 9 and a countable elementary substructure N s.t. I E N as usual. Let j < Y be any limit ordinal in N . Suppose we have ( F a p 1 Q 5 p < j ) s.t. f o r a n y Q and p with a 5 p < j , the following hold.

325

0

Jtp_ “If N U { G a , D } C M 4 H r [ G a l ,then p a p ( M ) C {w E Pp I w [ a E Ga}”. lkpa ‘YfNU{G:,,u} M 4 H r [ G a l , N n W 1 = M n w l , u E and u [ a E G a , then there is w 5 u s.t. w E M n Fap(M) and so there is v 5 w s. t. v [ a E Ga and v [ [ a D) , is (Pap,M)-semi-generic”.

Then for any x E Pj n N , there is y 5 x s.t. y forces the following: There is ((a,,M,)

I n < w ) in the generic extension V[G:j]s.t.

o=arJ
N = M o , M oU {GaY,,an+l}C Mn 3 Ho“[Ga,I ,M , E H,V[~Q*Iand Mn+1 = Mn[GanLYn+ll, Mn fFl anan+l ( M n )n Ga,+, # 0. ivnnwl =Nnw,. M o [ G j ] n H f C U { M , n H f I n < w } and so Mo[Gj]nwl= Monwl.

. 0

Proof. Similar to lemma 5.2 on weaving with i = 0. We also incorporate elements from theorem 6.2 on the preservation for semiproper. Details are left. We finish this note with the following observation on the chain conditions of simple iterations. We are sort of free to get the chain conditions. 6.4 Theorem. Let n be a Mahlo cardinal and J = (Pa 1 a 5 K ) be any simple iteration. If for all a < n, I Pa I< n, then Pn has the n-C.C.

Proof. We first make two claims and observe that these suffice for showing the n-C.C.We then show these two claims.

Claim 1. Let i L K. be a limit ordinal. For any x E Pi, there is (T,y) s.t. T is a nested antichain in Jri, y E Pi is ( T ,J[i)-nice and y 5 2. Claim 2. Let i 5 n be a regular uncountable cardinal s.t. for all (Y < i, Fix any ( T ,y) s.t. T is a nested antichain in J [ i and y E Pi is (T,J[i)-nice. Then there is a < i s.t. y = y[a-li[[a,i>in Pi. To observe these suffice, let (pi 1 i E A ) be any indexed family of conditions of Pn,where A = {i < n I i is a regular uncountable cardinal and V a < i I Pa I< i}. For some f ( i )< i < g ( i ) < n, we may assume

1 Pa (
Pi = ~ ~ [ ~ ( i ) - i ~ [ [ f ( ~ ) , i ) - P i r [ i , g ( i ) ) - i ~ [ .[I.g ( ~ ) ,

326

By Fodor’s lemma, we may also assume f(i) = f(j)and pirf(i) = p j rf(j) for all i , j E A. So we may find i < j in A with g ( i ) < j . Let p = p i [ j ^ p j [ [ j , n ) . Then p E P, and p 5 p i , p j . Hence P, has the K-C.C.

(8-k

Proof of Claim 1. Since x E Pi, we may fix its Pi-dynamical stages I 5 < w ) . We construct a nested antichain T in J r i as follows. a. E

Fj(a,,),Z(ao)< i , a o 5 xrl(ao) and

This is possible, since x lkp, “8-0

< 3’. Now

acl lkp,“$ = l ( a o ) ” .

suppose we have constructed

T, so that 0

a E Pl(a),Z(u) < i , a

5 xrZ(a) and a-1 IFpi“S,

= Z(a)”.

We want suc?(a) for all a E T,. But a-x[[Z(a), i) Ikpi “Z(U) = d‘, 5 Jn+l” and &,+I is a Pi-dynamical stage. So it is routine t o construct suc$(a). This completes the construction of T . Now let y E Pi be (T,Jri)-nice. Then y Ikp, “there is a generic cofinal path through T in V[Gi]”. Hence ylkp;“if 8- = sup{& I n < w } , then 0 x [8- E Gi and so x E Gi” . We conclude y 5 x.

r8-

Proof of Claim 2. Since i is a regular uncountable cardinal and for all a < i, I Pa I< i assumed, there is a < i s.t. for all n < w , T, C U{fl 11 5 a}. Hence for any ( T ,J ri)-nice sequence y E Pi, we have y y [a^ 1. (We may not have y = yra-1. But it does not matter.) The following is related to remark 3.26 on p. 68 of [5]. 6.5 Theorem. Let n > w1 be a regular cardinal and J = (P, I a 5 n) be a simple iteration of semiproper preorders. If f o r all a < n, 1 P, I< K , t h e n

P, has the n-C.C. Proof. Similar to theorem 6.4. We may prepare the following claim to replace claim 1 in the previous proof. And we may use this claim together with claim 2 as before. Here we set A = {i < n I cf(i) = w1) which is stationary in n.

Claim. Let i < K be a limit ordinal with cf(i) = w1. For any 2 E Pi, there is a < i and a E P, s.t. a 5 x r a and a^x[[a,i) G a n l i r [ a , i ) 5 x. Proof of Claim. We first take a sufficiently large regular cardinal 0 and a countable elementary substructure N of He with x ,P i E N .

327

Since Pi is semiproper, we may then take y E Pi s.t. y 5 x and y is (Pi,N)-semi-generic. Since cf(i) = w1, we may assume this is true n w1 = N n w ~ but ” in N as well. So we have not only y Jkpi“N[G:i] also ylt - pi “ sup( ~[ G :i] n i) sup(^ n i)”. Since x E N , we may also assume that x has Pi-dynamical stages (in 1 n < w) in N . Since 3 5 z and z It-p, “& < i”, we have y lFpi “in E N [ G J n i”. Let us set a = s up( N n i ) < i. Then y I ~ P ~ “ s u ~ { I ~ n~ < w} 5 a”. Since yItpi“xra E G:i[a”,we certainly have yIkpi“x[[a,i) li[[a,i) in Psi". Hence we must have a E Pa s.t. a 5 z [ a and anx[[a,i) a-li[[a,i). 0

=

Note. I would like to thank David Aspero for many comments on this

note.

References 1. H. Donder and U. F‘uchs, To appear in Handbook of Set Theory. 2. C . Schlindwein, Simplified RCS iterations, Archive for Mathematical Logic 32 (1993), 341-349. 3. S . Shelah, Proper and Improper Forcing, Perspectives in Mathematical Logic, Springer-Verlag, 1998. 4. T. Miyamoto, O n iterating semiproper preorders, Journal of Symbolic Logic 67 (2002), 1431-1468. 5. H. Woodin, The Axiom of Determinacy, Forcing Axioms, and the Nonstationary Ideal, de Gruyter Series in Logic and Its Applications 1, de Gruyter, 1999.

328

AN APPLICATION OF N D J ~ R o TO ~ THE CATCH AND THROW MECHANISM

MASAHIRO NAKATA Kobe University 1-1 Rokkodai, Nada, Kobe, 657-8501 Japan E-mail: [email protected]

NORIMICHI SANETO Setoda Highschool Setodachou, Toyotagun, Hiroshima 722-24417 Japan E-mail: [email protected]

MARIKO YASUGI Kyoto Sangyo University Motoyama, Kamigamo, Kita, Kyoto 603-8555 Japan E-mail: [email protected]

Abstract Catch and throw is a mechanism in the programming language dealing with exceptional processes. Nakano in [4,5,6,7] introduced a typing system, named L z v ,that can express the exceptional processes. He proved its soundness by interpreting it by a term (program) system with catch and throw operators. Here we will make use of a system of propositional calculus, named NDJ,,,,, and modify it to obtain a deductive system NDJ,/t as an alternative to L z " . We show that there are maps in both directions between Nakano's term system and NDJ+ that (in a certain sense) preserve reductions. If we regard a term as a program, then this assertion means that a proof and a program directly correspond to each other, and the correspondence is attained by the above maps.

1. Introduction In [4,5,6,7], Nakano defined a term system (named 7 here) which contains the constructs of catch and throw, and he also introduced a typing system,

329

named LZVlthat can represent the catch and throw mechanism. The terms of 7 are supposed to represent programs. Using these, he first gave an operational semantics of I and then proved the soundness of L Z ” by a realization interpretation in terms of 7 . He also reformulated L Z ” in sequent style and proving a cut-elimination theorem. In order to explain the purpose of this article, let us first give an account of the catch and throw mechanism, as well as the use of a connective called exception, at some length. The catch and throw mechanism is a means of non-local exit used in programming languages such as Lisp, C++ and Java. The throw construct throws exceptions and the thrown exceptions are caught by the catch construct. The notion of exceptions in programming languages represents “unusual situations” in computation. Typical exceptions are errors such as the one that happens when one tries to compute When an exception such as the error of division by zero happens, the exception is thrown to the top of the computation tree. If the thrown exception is caught by a catch construct, the catch construct can handle the exception just like usual data. Thus the mechanism of exceptions allows a program to recover from its own errors by itself and is very important in practice. The catch and throw mechanism could be used to handle unusually good situations as well. For example, in computing I17=lf(i), we may stop the computation as soon as we encounter an i such that f (i) = 0, since then the result of the computation must be zero. The logical formula AaB represents the situation “Usually A holds, but, if an exception happens, then B holds.” For example, if f ( i ) = 0 or f ( i ) = i, then the possibility of an “exceptionally good situation” mentioned above is formulated as follows: rI?.lf(i) = n! a ( 3 i . f ( i )= 0 A rIy=lf(z) = 0). The contribution of the present article is to formulate a natural deduction style formal system NDJ+ that corresponds to the term system I, and to define maps between the terms of I and the proofs in NDJ+ that (in a certain sense) preserve reductions. (The result is summarized as Theorem 3.1.) The system NDJ+ is a modification of NDJ,,,,, the constructive propositional calculus formulated in the natural deduction style. The map from NDJ+ to 7 mentioned above is also expected to be useful for proof animation, proposed by Hayashi, in [2] for example. Namely, the validity of a formal (supposed) proof is to be tested by computing the term (program) extracted from the (supposed) proof for some examples of inputs. The map from 7 to NDJ,,, will be also useful in giving a proper proof once

h.

330

a program is corrected (if erroneous). In [13,14,15], Yasugi, Ryu and Nakata proposed and investigated a system of classical predicate calculus in the natural deduction style, named NDK, whose characteristic is that introductions and eliminations of any logical connective can be executed at any place in the disjunctive components of a formula. In this way, the law of the excluded middle can be deduced as a consequence of an inference, not as an axiom. For example, the inference rule A-elimination applies to C V ( A A B ) V D to deduce the consequence C v A v D; the inference rule +-introduction applies t o r V B V A with a live assumption [A] to deduce the consequence r V (A -+ B ) V A with [A] discharged, where I? and A represent zero or more formulae. In [8] Nakata considered the propositional part of NDK, named NDK,,,,, and proposed a variation of the implicational part of NDK,,,,, named NDK’. In [ll],Saneto made some observations about the constructive part of NDK,,,,, named NDJ,,,,, that is obtained from NDK,,,, by restricting the introduction of + or -,t o only the whole formula in the premise. For example, the +-introduction as above is allowed only t o conclude A + (I’v B v A). He then applied it to define a system NDJ,p, which expresses the catch and throw mechanism, modelled after Nakano’s method in [4,5,6,7]. With NDJc/t, the correspondences between a term system and a logical system immediately follow. The map from the deductive system NDJClt to the term system ‘T is modelled following Nakano’s idea, while the converse map is modelled after [12]. This article has emerged from Sections 6 and 7 of [ll]and also from [9]. In Section 2 of this article, we introduce the system NDJ+; in Section 3, we first review the definition of the term system 7, and then define correspondences between terms of ‘T and proofs in NDJ+ (Propositions 3.1 and 3.2, Theorem 3.1). At the end, in Section 4, Nakano’s example of realizing the catch and throw mechanism is presented in our language. Related work can be seen in [3]. A comprehensive report on the propositional subsystems of NDK has been presented in [9]. We have followed the notations of [l]and [lo] for systems of natural deductions.

2. A system NDJ+ representing catch and throw We now define the system NDJ+. NDJ@ a modification of NDJ,,,,, a formulation of the constructive propositional logic, t o a system that can express the catch and throw mechanism. In the conclusion of an inference of NDJc/t, there occurs a formula of the form A V AT. Here T represents a

331

set of assignments of tag variables. Tag variables, a new logical connective a and new rules of inferences are added to NDJ,,,, based on Nakano's ideas ([4,5,6,7]).

Note Although the logical connective 1is employed in NDJ,,,, (being the usual propositional calculus), we do not need it for our purpose as it does not represent any computational operation and hence we do not include it in the system NDJ+. Definition 2.1. 1) The propositional formulae are defined as usual using the connectives A,Vand -+ as well as round brackets, although these will be omitted in order to avoid notational complication, unless confusion is likely. 2) A new logical connective a will be introduced, so that, if A and B are formulae, then A a B is also a formula. It is called exception by Nakano. (a is a kind of disjunction, details of which have been explained in the introduction.) 3) Tag variables are denoted by u, v,. . .. A formula B with an assignment of a tag variable u is written as B". B and B" are identical as propositions, but their roles are different. A formula with a tag assigned is called an error message. 4) The disjunctive components of a formula A are defined as follows. 1. If A is an atomic formula, then the disjunctive component of A is A itself. 2. If A is of the form BVC,then disjunctive components of A are the disjunctive components of B , the disjunctive components of C and A itself. 3. If A is of the form BAC,B ---f C or BaC,then the disjunctive component of A is A itself. For example, if r = (AA B)V (CV D)where A , B, C and D are atomic, then the disjunctive components of are I?, A A B ,CVD,C and D. 5 ) Formal proofs in NDJc/t will be defined below. Labels of assumptions will be denoted by z, y , . . .. Signs such as (z),( x ,y) written at the left of the name of an inference rule will indicate the label(s) of the discharged assumption(s).

We note that, in an assumption of an NDJ,+-proof as defined below, no error message occurs. In the conclusion of an inference, a formula of the

332

form A V (BY' V BY2 V . . . V BEn) may occur. Here, n 2 0, and we may abbreviate a disjunctive formula with tags such as (BY' V BZ2 v . . . v BXn) by A T . In A V AT, A will be called the main part, and AT will be called the exceptional part. Prior to the definition of proofs, we define the set of substitution contexts, written sCont. Let tFormula denote a tagged formula. sCont*, the extended substitution context, is first defined, introducing an atomic symbol a. sCont* ::= a 1 tFormula I sCont* A sCont* I sCont* V sCont* I sCont* ---f sCont* 1 sCont* a sCont+.

A substitution context, sCont, is defined to be an extended substitution context in which the atom Q does indeed occur. For an sCont, say E T , we write ET[E"] for the result of substituting a tagged formula E" for all occurrences of the atom a in ET. It is a tagged formula. E T [ ] will denote the tagged formula obtained from ET by deleting Q together with the connectives that introduced Q in the construction of ET. The formula E T [ ] is a tagged formula. For example, if ET is X" V (Q vY"), then ET[E"] is X u V (E" V Y") and E T [ ] is X" V Y". Proofs in NDJ,/,: A proof in NDJ+ is built from assumptions and inference rules as listed below. [Assumption] [ x : A] will denote an assumption A (a formula without tag variables) with label x. [Inference rules of NDJ+] In the following, AT will denote a tagged formula, while ET will denote a substitution context.

[x: A] AVET[] (weak) A v ET[Eu]

EvST[] A v ET[E"]

(throw)

sT

A V [A"] (catch) AvET[]

333

(A1 A A 2 ) V AT (AiE) Ai V AT

AV'AT BV'AT ( A A B ) v aT

V

A~ AT (A1 V A2) V AT

(VJ

(Z

= 1,2)

(i = 1,2))

[x:A]

[y : B]

[x: A]

A v ET[E"] ( A a E ) v ET[ ]

(AaEjvET[] A v sT[E"] (aE)

(4

A v AT AT (Contraction) A V A ~ A in the conclusion of throw is an arbitrary formula; AT in the conclusion of (-+ I) is arbitrary, while the exceptional part in the premise of (-+ I) is empty. Definition 2.2. (Reduction.) We define reductions of proofs in NDJ,lt. The reductions we employ are the so-called innermost reductions. In the following, V and M will denote parts of proofs to which reductions no longer apply; M' will denote a simulation of M , that is to say that M' is obtained from M by replacing each formula D in M by D V AT for an appropriate taggcd formula AT. Similarly for Ml. then M' is For example, if M is AA

B

,

( A A B ) v nT BvAT

334

Now here are the reductions.

:v AvET[] (throw) A v ET [A"] (catch) AvZT[]

:v ==+

AvZT[]

:v EvET[] (throw) A V ET[E"]

:v

:M E V ET [E"] (catch) EVET[]

*

EvET[] (throw) E V ST [E"] (catch) EVET[]

:v

:v

[x: A] : M

A V. AT : M' 3

c vCATV AvTaT (Contraction)

[x: A] : M

:v

EvET[] (throw) A v ET [E"]

:v EVETI1 ===+

I . .

335

Notice that a common tag variable u occurs in the premise of in the conclusion of (aE).

(GI)

and

:v EvzT[] (throw) A V ET [E"] A a E v E T [] ( 4 4 (aE) A v zT[E"]

:v EvET[] (throw) A v ET [E"]

Notice the change of tag variables.

:v Ai

AT : M,!

(i = 1 , 2 )

:v

Let II denote a proof in NDJ,/t, and let II[IT'] denote the fact that II' is a subproof of II,that is, IT' c II and II' is itself a proof. II[II,] is said to be reduced t o II[II2] (written II[II,] =+ I I [ I I 2 ] ) if IT1 ==+ I I 2 . In general, for proofs II and II*,we write II =j 11*when II is reduced to II* in the sense above.

336

3. NDJ,/t and the term system We first introduce Nakano’s terms and their reductions (cf. [4,5,6,7]), and then give a term-representation of NDJ+ using these terms. A converse map will then be defined. 3.1. Review: Nakano’s terms and reductions

Definition 3.1. Three mutually exclusive sets of symbols are assumed. Const : a set of individual objects c, d , . . . Var ! : a countable set of individual variabIes 2,y, z , . . . Tvar ! : a countable set of tag variables u, v, w ,. . . Definition 3.2. Terms of the term system T are defined as follows. Term ::= Const I Var I let Var = T e r m . Term I throw Tvar Term I catch Tvar Term 1 X Var . Term* 1 Term Term I ( Term , Term ) I proj1 Term I pro5 Term I injl Term I inj2 Term I case Term Var . Term Var . Term I K Tvar . Term I Term Tvar Here Term* denotes a Term that has no free occurrences of tag variables. M , N , K , L, . . . will be used to denote terms. A Term that has no free occurrences of variables will be called a closed term. Definition 3.3. The set of values, Val, will now be defined. Val ::= Const I Var 1 X Var . Term 1 ( V a l , Val ) I injl Val I inj2 Val I K Tvar . Val I K Tvar . throw Tvar Val V ,V‘, W,W’, . . . will be used for elements of Val. Definition 3.4. The set of term-like expressions with an atom *, Cont, will be defined next. A member of Cont is called an evaluation context, and * is called a hole. Cont ::= * I let Var = Cont . Term I throw Tvar Cont I catch Tvar Cont 1 Cont Term I Val Cont I ( Cont , Term ) I ( Val , Cont ) I proj, Cont I proj, Cont

337

I injl Cont I injz Cont I case Cont V a r . T e r m V a r . T e r m I K Tvar . Cont I Cont Tvar The result of filling all the occurrences of the hole a context C will be denoted by C [ M ] .

* with a term M

in

Definition 3.5. Call-by value rewriting His defined by the rules below.

C denotes any evaluation context which is not * itself. V denotes a value . M [ V / x ]denotes the result of substituting V for x in M . catch u V H V catch u C[throw u V ] catch u (throw u V ) catch u [throw u V ] H V let x = V . M M[V/x] (A x . M ) v M[V/x] K u . C[throw u V ] H K u . throw u V

---

( K U . V ) V

v

u . throw u V ) v H throw v V v Projl (V , W ) W PrOjz (V , W ) case ( i n j l V ) z . M y . N M[V/x] case (injz V ) x . M y . N H N [ V / y ] C [ M ]is said t o be reduced to C [ N ]if M N , and this fact is written (K

-

as C [ M ]

C"].

A call-by value rewriting expresses the innermost computation. 3.2. Assignment of terms t o NDJ,.t-proofs We will assign a term from I to each proof in NDJc/t. Given a proof in NDJ,/,, say II, then

:11 t:CkAT will express the fact that the term t is assigned to II. t is meant to represent the computation process of deducing the main part, C , of the conclusion of the proof II. Proposition 3.1. Let II be a n NDJ,/,-proof (see Definition 2.1), and let r(II) denote the assignment of a term from I to II as defined below in Definition 9.6. Then r preserves the reduction. That is to say, suppose

338

-

~ ( n i'f)~ ( I 2i)s not a value; ~ ( n=) ~ ( 1 1 ' if) ~ ( nis )a value; -r(II)i s a value i f no reduction applies to II. II 3 II'. Then ~(n)

Definition 3.6. (Assignment of terms by x is assigned t o

T.)

[x : A] (assumption) That is, x : [ x : A ] ,or T ( [ X : A ] )= x. The label x is regarded as a term (variable) deducing the assumption A. For a compound proof II,~ ( n is )defined inductively according to the rule of inference 5) in Definition 2.1.

[x : A]

N : A V AT M : C VAT (let) let x = N . M : C v AT

t : A V ET[ ] (weak) t : A V ZT[E"] M : E V ET[ ] (throw) throw u M : A V ZT[E"]

M : A v ZT[A"] (catch) catch u M : A v Z T [ ]

[x: A]

xx

M': B . A~ + B

v nT

M : A ~ B V A TN : A V A T (+El

I)

(4

M N : B V A ~

A'

M : A B v AT (A l E ) projl M : A v AT

[ x : A]

M : A A'B v AT proj, M : B V AT

(A2E)

[Y : BI

L ~ A V B V A TM : C V A T N : C V A T( v E ) case L x.M y.N : C v AT

339

It is routine work to prove the proposition. 3.3. Assignment of proofs t o terms Conversely, one can assign a proof to a term. Suppose first, that a map ,B from variables to formulae is arbitrarily chosen with p ( x ) = A .

Definition 3.7. d ( x ) = [z : A] if p ( x ) = A.

d(1et x = N . M )

=

[x : A] d(N) d(M) AvAT C v A T (x) CvAT

d(M) d(throw u M ) = E v Z T [ ]

A v ZT [E"]

d(X2.M) =

d ( i n j i M )=

[x: A] d(M) lIvAT

( A+ B ) v aT

d(catch u M ) =

(x) d ( M N )

Ai v AT (A1 V A2) v AT

d(M) A v sT[A"] AVZT[]

d(M) d(N) (A+B)VAT AvAT

-S

B V A ~

340 [ z : A]

d(L)

d(M)

(AvB)vAT CvAT CvAT (x,Y 1 CvAT

d(case L x.M y.N) = d(M)

d(Ku.M) =

[ y :B ] d(W

A v ET [E"] ( A a E )V E T [ ]

d(W

d(Mu)=

( A a E )v s T [] A V ET [E"]

Proposition 3.2. Given an arbitrary map p from variables to formulae with P(z) . , = A. Then the assignment d , given in Definition 3.7, of a n NDJ,+-proof to a term relative to /3 such that d preserves reductions, that is, i f t Hs, then d(s). d(t)

*

The proposition can be proved by examining the definitions. We now sum up our results.

Theorem 3.1. The NDJ,/,-proofs and I - t e r m s are related as follows. such that the comThere is a map from NDJ,/,-proofs to 7 - t e r m s , T(II), putation of 4 3 ) is reflected in the reduction of TI, and, i f ~ ( r Iis) a value, then the reduction of ll preserves the same value. Conversely, there is a map from 'T to NDJ,/,, d ( t ) , such that d preserves reductions. 4. Realization of catch and throw: an example

We will explain how to realize the catch and throw mechanism in terms of the term assignments to NDJ,/t-proofs using an example from 1.2 of [7]. Let P be a program which, for a sequence of input data satisfying specifications A l , . ,. ,A,, either outputs data satisfying a specification C or returns an error message E . Let us write this condition of P by:

P : A 1 ,..., A , H C ; E Let P* denote a program that does the following task. Given programs Q, R, S such that

Q : A 1 ,..., A , H D ; E R : A1,. . . ,A,, D

t--)

F;

S : A1 . . . ,An, E

t-+

F;

341

P* first runs Q. If the output satisfies D ,then it proceeds to R, and if the output satisfies E , then it proceeds to S. P* can be represented in NDJ,+ as follows, where [A] abbreviates [ A l l . .. [A,]. (We will omit the parentheses enclosing a term and the corresponding main part of a formula.)

throw u ( l e t x = Q.R) : E v E" v F" SIF catch u (throw u (let x = Q.R)): E v F" throw v S : F V F" (Y> let y = (catch u (throzo u ( l e t x = Q.R))).(throwu S ) : F V F" catch u ( l e t y = (catch u ( t h r o w u ( l e t x = Q . R ) ) ) . ( t h r o w u S ) ) : F

Acknowledgement The authors are grateful to Hiroshi Nakano and Susumu Hayashi for supplying us with knowledge and information about catch and throw mechanism. We are also indebted to the referee, according to whose penetrating comments and advice the manuscript has been revised. References 1. S. Hayashi, Surironrigaku (Muthematical Logic), in Japanese, Korona Pub.Co., 1989. 2. S.Hayashi, R.Sumitomo and K.Shii, Towards animation of proofs-testing proofs b y examples, TCS 272, 177-195, 2002. 3. Y.Kameyama and M.Sato, Strong normalizability of the non-deterministic catch/throw calculi, TCS 272, 223-245, 2002. 4. H.Nakano, A constructive formalization of lhe cutch and throw mechanism, Proc. 7th LICS, 82-89, 1992. 5. H.Nakano, A constructive logic behind the catch and throw mechanism, APAL, 69, 269-301, 1994. 6. H.Nakano, The non-deterministic catch and throw mechanism and its subject reduction property, Logic, Language and Computation, LNCS 792, 61-72, Springer, 1994. 7. H. Nakano, Logical structures of the catch and throw mechanism, PhD Dissertation, University of Tokyo, 1995. 8. M.Nakata, Classical system NDK and its propositional subsystem NDKp', Master's Thesis (in Japanese), Kyoto Sangyo University, 1998.

342 9. M.Nakata, N.Saneto and M.Yasugi, Classical and constructive propositional subsystems of NDK (in Japanese), Bulletin of the ICS, Kyoto Sangyo University, 15, 37-81, 1999. 10. D. Prawitz, Natural Deduction, Almqvist and Wiksell, 1965. and system Nc,t which realizes 11. NSaneto, Constructive system NDJp,,, catch and throw, Master’s Thesis (in Japanese), Kyoto Sangyo University, 1998. 12. M.Yasugi and S.Hayashi, Interpretations of transfinite recursion and parametric abstraction in types, Words, Languages and Combinatorics I1 (edited by M. Ito and H. Jurgensen), 452-464 ,World Scientific Publ. Co., Singapore, 1994. 13. M.Yasugi and M.Nakata, O n natural proofs in NDK (in Japanese), Proceedings of RIMS, 976, 13-26, 1997. 14. M. Yasugi and M.Nakata, NDK and Natural Reasoning, Proceedings of the 6th ALC, 285-309, 1998. 15. M. Yasugi and K. Ryu, NDK, A New Classical System, Bull. of the Inst. of Computer Science of Kyoto Sangyo University, 11, 1-25, 1994.

343

THE CURRY-HOWARD ISOMORPHISM ADAPTED FOR IMPERATIVE PROGRAM SYNTHESIS AND REASONING

IMAN POERNOMO AND JOHN N.CROSSLEY School of Computer Science and Software Engineering, Monash University, Australia E-mail:{ ihp,jnc}@csse.monash.edu.au

Abstract The Curry-Howard isomorphism permits the representation of intuitionistic logic as a constructive type theory. It has often been exploited in the implementation of interactive theorem provers. It also forms the basis of the proofs-as-programs paradigm, an approach to the synthesis of functional programs from intuitionistic proofs (see e.g., [l,2,3, lo]). In this paper, we present a constructive version of a Hoare logic (cf. [9]) for reasoning about imperative programs t o which the Curry-Howard isomorphism may be adapted. This allows us to take advantage of the isomorphism for theorem proving implementation, and for the synthesis of correct imperative programs with return values, following the proofs-as-programs paradigm. 1. Introduction

It is well-known that intuitionistic logic can be presented as a constructive type theory where proofs correspond to terms, formulae t o types, logical rules correspond to type inference and proof simplification corresponds to term evaluation. This property, known as the Curry-Howard isomorphism, is often used in the implementation of interactive theorem provers. Amongst other advantages, the isomorphism permits the automation of proof simplification, and complex proof tactics and parametrized lemmata to be given simply as functions over terms. Various authors have used the Curry-Howard isomorphism for the synthesis of functional programs from constructive proofs [1,2,3] - an approach known as the proofs-as-programs paradigm. The idea is as follows. A description of the required program behaviour is given as a formula,

344

P , for which an intuitionistic proof is given. The constructive nature of the proof allows us to transform this proof into a functional program whose behaviour meets the requirements of P. For example, the formula Vx : Int.Vy : I n t . 3 ~: Int. gcd(x, y , z ) can be interpreted as a specification of a program that takes x and y as input values, and returns as output value z , the greatest common divisor of x and y . An intuitionistic proof of this formula enables the construction of a witness term for z . The proof is then transformed into a functional program f satisfying the formula as its specification. In most modern approaches to proofs-as-programs, the proof is represented as a term of a constructive type theory, with the required program given as a term of a simply typed lambda calculus (such as a subset of the programming language ML). The transformation is given as an extraction mapping from the former type theory to the latter. This paper provides a constructive version of a Hoare logic (see [9]) for reasoning about imperative programs, to which the Curry-Howard isomorphism and a proofs-as-programs approach may be adapted. Theorems of the logic consist of an imperative ML program and a formula that describes the program’s side-effects (see below, Section 2) by means of pre- and postconditions. Our logic uses a natural deduction proof system. Therefore our calculus can be understood as a constructive type theory where proofs correspond to terms and formulae to types. We can give an extraction map from proof-terms of this type theory to programs (in SML). This enables SML programs to be synthesized from proofs of their specifications. This approach to synthesis adapts approaches to intuitionistic proofs-as-programs synthesis. In particular we adapt our work from [14] and [lo] and Berger and Schwichtenberg’s from [l], where a notion of modified realizability defines when a program of a simply typed lambda calculus satisfies a intuitionistic formula as a specification. Note that a theorem in the Hoare logic consists of an imperative program and a truth about the program. Thus, the logic can already be used to synthesize programs. However, such programs do not involve return values. We adapt modified realizability to specify, prove properties about required return values, and an extraction map to synthesize required return values from proofs in the logic. The advantage of our adaption is that the user need not think about the way the return value is to be coded, but can still reason about and later automatically generate required return values. For example, given a

345

constructive proof in Hoare logic of the form program s := 10

0

truth such as

3z.Even(z)

we shall be able to synthesize a return value f in a program of the form s := 10;f

where the function f (with program f ) is a side-effect-free program (such as !s * 2) that realizes the existential statement and acts as a witness for the z. (Here s is the argument o f f and choosing !s * 2 guarantees that we get an even number computed.) The user should have no need to manually code the return value, but instead works within the Hoare logic to prove a theorem, from which the return value is then synthesized. This paper proceeds as follows: In section 2 we present some preliminary syntactic and semantic assumptions about imperative programs. In section 3, we explain how the formulae of our calculus describe side-effect and return values of imperative programs. Our calculus is presented in section 4. Section 5 outlines how we adapt the Curry-Howard isomorphism and to our calculus, and section 6 shows how proofs-as-programs-style program synthesis can be achieved using this adaption. We also outline how these results are implemented and provide a small case study illustrating our work. We briefly review related work and provide concluding remarks in section 8. 2. Preliminary definitions and assumptions

Our results are given with respect to a set StateRef, whose elements denote possible SML state references. We consider a subset of SML programs, SML(StateRe8, whose only state references are elements of StateRef. In this subset, the state references of StateRef can be treated as global, and we assume their declaration as implicit, prior to executing code. For instance, if r € StateRef, then we also have r :=!r + 1;!r; ; € SML(StateRe3, where we assume that r has previously been given a declaration of the form l e t r = ref 0. We distinguish the side-effect-free programs of SML as Pure ML. These programs involve a lambda calculus and may use dereferenced state references (of the form ! r T € StateRef), but cannot change the value of state references. Our results assume a set of pre-defined SML programs, Prog. Our calculus is used t o build larger programs from the basic constructs of SML and this set of (black-box) programs.

346

Our results are parametrized with respect to a many-sorted algebraic signature AVT, consisting of sorts and sorted constant, function and predicate symbols. Terms of AVT (for abstract data type) are formed as usual using constant and function symbols over a distinguished set of variables VaTdvr. We assume that every closed term of AVT, Closed(AD7) can be executed as a side-effect-free (and state-reference-free) program of SML, and each sort is a type of SML. Elements of CZosed(AVT) form the evaluated return values of our programs. We use typewriter font to denote when a AVT term is to be used in an S M L program, and Times Roman font when terms axe used in our calculus. For our present purposes, we take AVT to include a simply typed lambda calculus over the basic data types of S M L with appropriate predicates, and require that we have disjoint union types: type ‘a’b disjointUnion=Inl of ’a I Inr of ‘b;;. Given a first-order many-sorted formula P formed from A D T , and an interpretation L of the variables V a r d v r , we write 11, P when P is true in the intended model for AVT under L. Because dVT terms are S M L programs, the intended model of AVT can be defined using the operational semantics of AVT terms in SML. For instance, for any L, It, Vx : int. ( f u n y => y)(x) = x holds, because, for any S M L integer x, the lambda application (fun y => y)(x) is equal to x. We represent the state of a program’s execution by a collection of value assignments, one for each state reference of StateRef. Formally, we define the set of states C to consist of functions, a : StateRef --+ ADT. Each 0 E C represents a possible state of the computer’s memory, where a ( . ) is the value assigned to state reference s which is in StateRej For example, if is the state after executing r := 40, then a ( . ) = 40,because we know that r stores an integer reference ref 40. A side-effect is the result of executing an imperative program: a transition from an initial state of a computer’s memory to a final state. Because SML(StateRe8 programs only use global state references from StateRef, we can define a simple semantics for representing the side-effect of a program’s execution. Given an SML(StateRe8 program, we write (p,a) 6 (1,a’) to mean that, starting from an initial state a, the program p will terminate and result in the value 1 and a final state 0‘. For the purposes of this paper, we take 6 to be the transitive closure of the relation D given by the operational semantics presented in Fig. 1. For instance, if r E StateRef, then (r :=!r 1;!r;;,0) 6 (1,a’) holds,

+

347

a(b) --+AD7 true

( i f b then p else q, a) D (p, a)

(condl1

false

a(b)

( i f b then p e l s e q, a)D (q,a)

(cond2)

u(b) - ) A D 7 f a l s e (whilel) (while b do c; done, a) D ((>,a)

(c, a) D (r,u‘) (while2) (while b do c; done, a) D (while b do c; done, a’) a(b)

true

Figure 1. Operational Semantics for our programs.

when, for instance, a(.) = 14 and a’(r) = 15. The execution of an imperative program will produce a whole range of side-effects, depending upon the initial state of the memory. We formally denote such a range by a set-theoretic relation, a side-effect relation, between initial and final states. The set of side-effect relations, R e l , is defined as a subset of the power set P(C x C) of pairs from the set of states C. As usual, we write a R a’ if (u,u’) E R. A side-effect relation provides a semantics for an imperative program when the relation’s state pairs consist of the possible initial and final states for the program.

Definition 2.1. Side effect relations. A side-effect relation R is the semantics of an SML(StateRefi program p, written R = [p], when, for all

348

states IT, IT'E 2, (T

* (p,

R IT'

IT)

6 (*, IT') for some value *.

It follows from this definition that if aRa' and ITRO", then is uniquely determined by the initial state c.

IT'= IT",

i.e.

(T'

3. Specification of side-effects and return values

Our logic is used to specify and reason about two aspects of imperative program behaviour: possible side-effects and possible return values. Possible side-effects are specified as pre- and post-conditions (in a single formula style (as opposed to the semantically equivalent Hoare-triple style of [9]). Because a program's side-effect is described in terms of initial and final state reference values, prior to and after execution, these initial and final state reference values are respectively denoted by the name of the state reference with a ()i and with a ()f subscript. For instance, the formula rf > ri describes every possible side-effect of the program r :=!r 1. It specifies side-effects whose final value of r, denoted by r f , is greater than the initial value, denoted by ri. Possible return values are specified as the required constructive content of a formula, in the same way that functional programs are specified in constructive type theories. So, for instance, the formula 3y : int.Prime(y)A y > ri describes a return value y of a program, such that, for any side-effect, y is prime and greater than the initial value of r.

+

3.1. Formulae The formulae of our basic (intuitionist) logic are defined as usual. Our quantifiers are sorted, and take sorts from ADT. For instance, if int E AVT, then 3x : int.x = 0 and Vx : int.x = x are well-formed. To enable the specification of side-effects, our formulae involve terms of ADT, extended over the subscripted StateRef symbols (which denote initial and final state reference values). For instance, if r E StateRef then ri * 20 r f is a wellformed term that may be used in our logic.

+

3.2. Specification of side-eflects

In order to define when a formula is true of a program's execution, we define when a formula is true of a side-effect relation from Rel. Take a formula P of our calculus. Let IT and IT' be initial and final states for some side-effect

349

relation. We write P,"' for the formula formed from P by replacing every initial state reference value symbol si (s E StateRefi by an actual initial state reference value u ( s ) , and similarly for final state references. Then, given a relation R E Rel, an initial state u and a final state u' such that u R u', then we write R It: P when R It, P,"'. Definition 3.1. A formula P is true of a side-effect relation under the interpretation L R, written R It, P , when (a,~') ER

+ R It-, P,"'

A formula is true of a program p under the interpretation L if it is true of the relation for the program for L: that is, when [p] It, P. When this holds for every 1, we write [p] It P. 3.3. Specification of return values

It is also possible t o use formulae to specify possible return values of imperative programs. This is done by extending the way that formulae of intuitionistic logic specify a functional programs, according to the proofsas-program paradigm. To understand this form of specification, we first need some definitions.. We first need to define Harrop formulae. Definition 3.2. Harrop formulae, see [8]. A formula F is a Harrop formula if it is 1) a n atomic formula, 2) of the form ( A A B ) where A and B are Harrop formulae, 3) of the form ( A + B ) where B (but not necessarily A) is a Harrop formula, or 4) of the form (Vx : s.A) where A is a Harrop formula. We write Harrop(F) if F is a Harrop formula, and THarrop(F) if F is not a Harrop formula.

We also need to define a sort-extraction map xsort which extracts the sort from formulae to sorts of AV'T. This is given by the axioms of Fig. 2. We can now define the Skolem form of a program-formula pair. This is the usual definition for first-order many-sorted logic over d V 7 (e.g., that of [l]).However, because our formulae are first-order many-sorted logic over AV'T extended by state identifiers, the definition can be used for our formulae. As usual inl(z) and inr(x) are the first and second encodings of x in pairs and fst(y) and snd(y) are the first and second components of the pair y.

350

F

AAB AVB A+B Vx : S.A 32 : S.A

I

xsort(F)

Unit if not Hurrop( B ) xsort ( A ) xsort(B) if not Hurrop(A) xsort(A)* xsort(B) otherwise xsort(A)Ixsort(B) xsort ( B ) if not Hurrop(B) xsort(A)-+ xsort(B) otherwise s -+ xsort(A) if Harrop(A) s * xsort(A)otherwise Unit

{

{ {"

Figure 2. Inductive definition of xsort(F),over the structure of F, where P is an atomic predicate.

Definition 3.3. Skolem form and Skolem functions. Given a closed formula A, we define the Skolemization of A to be the Harrop formula Sk(A)= Sk'(A,@),where Sk'(A,AV) is defined as follows. A unique function letter f~ (of sort xsort(A))called the SkoZem function, is associated with each such formula A. AV represents a list of application variables for A (that is, the variables which will be arguments of f ~ ) .If AV is (21 : s1,.. . ,x, : s,} then f ( A V )stands for the function application

Wdf, ( x 1 , .. .,4 ) . If A is Harrop, then Sk'(A,AV) If A B V C , then

= A.

Sk'(A,AV) = (Vx : x s ~ r t ( A ) . f ~ ( A =V inZ(x) ) -+ S l c ' ( B , A V ) [ x / f ~ l ) A ( b : xsort(B).f~(AV) = inr(y)-+ Sk'(C,A V ) [ y / f c ] ) If A

B A C , then

351

In the proofs-as-programs approaches of [l]and [14], a formula A specifies a functional program p if, and only if, the program is an intuitionistic modified realizer of A , now defined. Definition 3.4. Intuitionistic modified realizers. Let p be a term of CZosed(dD7) (and so, by the assumptions of Section 2, p.3, p can be considered to be a functional SML program that does not contain any state references). Let A be a first-order many-sorted formula predicating over A D 7 (but not using state identifiers). Then p is an intuitionistic modified realizer of A under the interpretation L when

Recall that, as discussed in Section 2 (p.3), the elements of Closed(dD7) are the return values of SML programs. So we can use the definition of intuitionistic modified realizability to define how our formulae specify return values. Definition 3.5. Return-value modified realizer. We say that an SML program p is a return-value modified realizer of a formula A under the interpretation L , when for for every n, n' such that (P,4

6 (a,4

the SML program a is an intuitionistic modified realizer of A,"' under this case, we write p retrnr, A. If p retrnr, A holds for every L , we write p retrnr A.

L.

In

A formula A of our logic specifies the return value of an imperative program p if p retrnr A. As a simple example, the Skolem form of the formula A z 3y : int.y = r i 1 is f~ = ri 1. It is true that, for any initial state n, (r :=!r + I;!r,0)C; (n(r)+i,n'). Also, ( f = ~ ri 1):' is f~ = o(r) 1.

+

+

+

+

352

I-1.A

(Axiom-I) if A E AX (assign) where s E StateReL

I- s := v 0 sf = tologici(v) I- p

0

c)

(tologic;(b)= true -+ k q 0 (tologici(b) = f a l s e -+ I- if b then p else q C

c) (if-then-else)

t- p (A[si/G] -+ B [ S f / B ] )

9 0 (B[Bi/G] -+ C[Sf/V]) (sed I- p; q 0 A[Si/G] -+ C [ S ~ / B ]

where A and B are free of state identifiers. I- q 0 (tologici(b) = true A A[si/v]) -+ A[sf/Uv] E A[&/v]-+ A[Sf/U] A tologicf(b) = fa lse

(loop)

where A is free of state identifiers.

F p o P I-l,,P-+A tpoA

(cons)

Figure 3. The basic rules of our calculus. Intuitionistic deduction is given in Fig. 4 based on the axioms Az(dDD7).

So, for every initial state (T,o(r)+l is an intuitionistic modified realizer of A. In this way, the formula A can be interpreted as a specification of an imperative program that returns an integer value equal to the value of r (prior to execution) plus 1. 4. The Calculus

Assertions of our calculus are of the form POA

consisting of a program p and a formula A. The formula is to be taken as a statement about the side-effect relation associated with p, provided that p terminates. Our calculus is a version of Hoare logic, providing a natural deduction system for constructing new program/formula pairs from known program/formula pairs.

353

x is not free in A

c : T is a valid sort inference

Figure 4. The basic rules of many-sorted intuitionistic logic, Int, ranging over terms with initial and final state identifiers. We assume that z , y are arbitrary d V 7 variables of some sort T, and that a is a term of arbitrary sort T. The map tologic takes programs to their logical counterparts if they give a Boolean value (see Def. 4.1).

The basic Hoare logic rules are presented in Fig. 3. It can be seen that each of these rules is equivalent to a rule of the more common presentation of the Hoare logic that uses Hoare triples instead of program/formula pairs - see [13] for a proof of this. The Hoare logic rules allow U S to build new programs from old and to prove properties of these new descriptions (cf. [9,4]). For example, the conditional (if-then-else) rule allows us to build a conditional program from given programs, and to derive a truth about the result. Hoare logic is defined with respect to a separate logical system [4]. Usu-

354

ally, this is classical logic (but we use intuitionist logic). The Hoare logic ~ and the logical system interact via a consequence rule. Assume M t - N denotes provability of formula N from formula M in the separate logical system L. Then the consequence rule can be formulated as follows

t- w p p

t -L

A (cons)

t-woA The meaning of this rule is that, if P implies A in the system L , and P is known to hold for the program w, then A must also hold for w. In this way, the separate logical system is utilized to deduce new truths from known ones about a given program. For the purposes of extending known results on program extraction, we define a Hoare logic that takes intuitionistic logic as its separate logical system. The standard rules that define our intuitionistic logic are given in Fig. 4. In these, in order to go from the programs to the logic we require the map tologici, which transforms an SML boolean function b into a boolean term, for use in formulae. The map replaces all state identifiers of the form !s with initial state identifiers of the form si.

Definition 4.1. Given any term b, we define tologici(b) = b[si/!s] where !8 is every dereferenced state reference in b, and 8i the corresponding list of initial state identifiers. We also define tologicf(b) = b[Sf/!S] where 5 is every dereferenced state reference in b, and Sf the corresponding list of final state identifiers. For the purposes of reasoning about an intended model, our calculus can be extended with axioms and schemata (including induction schemata). For the purposes of this paper, we do not deal with schemata. We shall assume a set of axioms A X , consisting of 1) program/formula pairs satisfying p 0 A E AX if, and only if, [p] It A in the intended model and 2) formulae, so that A E A X if, and only if, It A.

Remark 4.1. In [13] we give a proof of soundness for our calculus over SML execution traces. See [4] for proofs of soundness and a form of relative completeness for a wider range of models.

355

5. Adapting the Curry-Howard isomorphism Our calculus forms a type theory, LTT, with proofs represented as terms (called proof-terms), labelled formulae represented as types, and logical deduction given as type inference. The inference rules of the type theory are given in two figures: Fig 6 which gives the rules of the underlying intuitionistic logic and 7 which gives the rules connecting this logic into the full logic of proof terms for our calculus for the imperative language. We omit the full grammar of proof-terms, but the general syntax of proof-terms can be seen from the inference rules. (See [13] for full details.) Observe that, because of the ( c o n s ) rule, proof-terms corresponding to Hoare logic rule application involve proof-terms corresponding to intuitionistic logic rule application. We define a one-step proof-term normalization relation .us in Fig. 5, extending the usual /?-reduction of the lambda calculus. An application of this relation corresponds to simplifying a proof by eliminating redundant rule applications. For example, the reduction app(abstract X . C ~ - a+A~) .us , c[a/XlB

corresponds to simplifying a proof of B by deleting an occurrence of the (4-1) rule that is immediately followed by an (-+-E) inference. As in the Curry-Howard isomorphism for intuitionistic logic (see 171 or [5]) , proof normalization is given by the transitive closure of applications of this relation. Proof-term normalization does not remove any proof-terms corresponding to Hoare logic rule application. This results from the fact that a Hoare logic rule builds a program label from a given program, but there are no matching rules for reversing this construction.

Theorem 5.1. Strong normalization T h e theory LTT i s strongly normalizing: repeated application of o n a proof-term will terminate. r*g

Proof. See [13] for the proof of this and other proof-theoretic results (including the Church-Rosser property and type decidability). The theorem follows easily using rule 9 of Fig. 5, which shows that only intuitionistic 0 sub-proofs may be simplified in a Hoare logic proof. 6. Program synthesis

From a proof of a theorem, we can extract an imperative program which satisfies the theorem as a specification. For a proof/formula pair 1 A, a

356 1. 2. 3. 4. 5. 6.

7. 8.

app(abstract X . aA-'B,bA) -.+ u[b/XIB specific(use z : S. uvz:S.A,'u : S) -.+ a [ ' u / z ~ ~ [ ~ / ~ ] f s t ( ( a , b ) A A B )-.+ a A snd((a, b)AAB)

* bB

case tnI(u)AvB of Inl(zA).bc, Inr(yB 1.cC -.+ + / z ~ z case Inr(a)AVBof Inl(zA).bC, Inr(yB).cc us c[a/y] select (show(v, a)3Y.P)in zP.y.bC -.+ b[u/z][v/ylC a[b/z] and b -.+ c entails a[b/z] -.+ u[c/z] Figure 5. The eight reduction rules inductively defining -+.

program p is said to satisfy a program/formula pair 11 0 A when 0

0 0

the the the the

programs p and 1 have the same side efffects, program 1's side-effects make the formula A true, and program's return value is a return-value modified realizer for formula A (that is to say, p retmr A ) .

When this is the case, we say that p is a SML modified realizer of 1 A , and we write p mr 1 0 A. In Figs. 8 and 9 we define an extraction map extract : LTT + SML(StateRef), from the terms of the logical type theory, LTT, to programs of SML(StateRef). This map satisfies the following extraction theorems, which tell us that the map produces a SML modified realizer of the specification from a proof of that specification.

Theorem 6.1. Extraction of modified realizers from intuGiven any intuitionistic proof Flnt pA, then itionistic proofs. extract(pA) is an intuitionistic modified realizer of A . Proof. In [l,14,131, it has been shown that modified realizers can be obtained from ordinary intuitionistic proofs from the extract map. The only difference between ordinary intuitionistic proofs and formula A in the proofterm pA is that A may now involve initial and final state identifiers. However, this will not affect this proof (we can consider these identifiers to be distinguished variables in an ordinary intuitionistic proof to arrive at the 0 required result). Theorem 6.2. Extraction produces programs that satisfy proved then [extract(p)] It P . formulae. Given a proof I- pWoP,

357

A

t-lnt pAIAAz

A Elnt inr(p)Az

A t i n t pA1 A

(A-E2)

(V-11)

t i n t fSt(p)A1VA2

x is not free in A

c : T is a valid sort inference

a : T is a valid sort inference

x does not occur free in Q or A2

Figure 6. The basic rules of many-sorted intuitionistic logic, Int, presented as type inference rules, where proof-terms denote proofs and types are formulae with initial and final state identifiers. We assume that z , y are arbitrary AD7 variables of some sort T , and that a is a term of arbitrary sort T.

Proof. When P is Harrop, by the definition of extract, extract(p) = w and so [extract(p)] IF P follows from soundness (see Remark 4.1). When P is not Harrop, the proof involves showing that extract(p) always produces the same side-effect as w over all the state references that are used in P. This is routine but long and we omit it. Then the result follows from the fact that, if (u,o')IF P , then (o,o")IF P for any state u'' that differs from (TI at most on states not used in P.

358

I- Axiom(A)loA 1assign(s,

I- ite(ql,42)if

if A E AX (assign)

lzotologici (b)=false+C

I- 42

then b e l s e 111zoC

qwo(tologici(b)=trueAA[8~/B])

I- ,d(4)uhile

I>

D)s:=~osf=tologici(v)

11otologici (b)=true+C

I- 41

(Axiom -

af-then-else

1q u o A [ ~ f / ~ ]

do b;donewoA[8;/B]+A[B~/B]Atologiy(b)=false

(loop)

where A does not contain any state identifiers

Figure 7. The structural rules of our calculus. In A X , TZ is a constant, uniquely associated with the axiom A E A X .

Theorem 6.3. Extraction produces return-value realizers Take any proof I- tuoTand let L be any interpretation. Then extract(t) retmr, P.

Proof. To prove this, we take any pair of state u,u' such that extract(t) terminates with an execution sequence of the form (extract(t), u) 6 (answer, 0')

(1)

yielding a return value answer. Observe that answer has a representation answer = tologic(answer) in Term(dD7). We are then required to show that (u,a') It, Sk(P)[answer/fp]. We present only a few of the cases. Full details may be found in [13]. Case I: T is Harrop. In this case, by the definition of the Skolem form, we are required to prove that, if (w, 0)6 (answer, 0')then (0,~') It, T

(2)

359 extract ( p V o P )

any term where P is Harrop 0 uvoA

zu not H ( A )

0 H(A) fun xu => extract(a) not H ( A ) abstract uVoA.avoB extract ( a ) not H ( A ) extract(c) not H ( A ) (extract(c) extract(a)) not H ( A ) use x : T . awe* Eun x : T => extract(a) sDecificfcv*vz.A .ul -, (extract(a) v) ( P A , bW*B) (extract(a). extract(b)) case aWoAVB of inlff*A'l.bV*c. match extract(a) with I n l ( x t ) => extract(b) I Inr(x,) => extract(c) \ -

1

H(A)

V

(v, extract(a)) not H(A) (fun x => extract(b))extract(a) (fun x => fun xu => extract(b))

# ( a ) where #

f st(extract(a)) snd(extract(a)) is id, inr, fst or snd # ( w a r t f a ) ) abort( a V * l )

not H ( A )

} not H ( A )

Figure 8. Definition of extraction map extract, defined over the intuitionistic proofterms of terms used in formulae. Note that we can treat the resulting terms as MiniML program terms with state identifiers are treated as free variables.

But this is the case by soundness of the calculus (see Remark 4.1). Case 2: Proof ends in application of (loop). Assume that tnoTis of the form d,,,,

(q)while

do b;donel*A[I;/B]~(A[Bt

/B]Atologic'(b)=false)

By the induction hypothesis, we know that extract(q) retmr,

A[si/o]A tologiq(b) = true -+ A [ s f / f i ]

(3)

This means that, for any 7,T' and pure program value answer,, if (extract(q),~) 6 (answer,, 7')

we know that, for answer, = tologic(answer,), (7,~') It S k ( A [ s i / e ]A

tologiq(b) = true

-+ A[sf/ij])[answer,/fp]

(4)

where P stands for A [ s i / ~A]tologici(b) = true -+ A["/u]. There are two cases, depending on whether A is Harrop or not. We prove the more interesting latter case.

360

Then A[&/C]is not Harrop, and extract(t) is rv1 := fun x : xsort(A) => X; while b do rv2 := extract(q); rv1 := (fun xp :: x1 => fun x : xsort(A) => xp(rv1x)) rv2 r v l ; !rvl

We wish to show that answer is such that

By the definition of Skolem form and the fact that A [ % / @ and ] A [ s f / C ]are not Harrop, the required statement ( 5 ) may be rewritten

First we make some observations about the execution of the extracted program. Beginning of observations. Because we know that extract(t) terminates, by the definition of D, the program must have an execution sequence that results in states a = ao,a1,. . . ,a, = a’

where

(

[

rv1 := fun x : xsort(A) => x; while b do rv2 := extract(q); r v i := (fun x2 :: x i => fun x : xsort(A) => xz(rvix)) rvp r v l ; !rvi

(7) while b do rvz := extract(q); rv1 := (fun x2 :: XI => fun x : xsort(A) => x ~ ( r v ~ xrvz ) ) rvi;

6

(!rv1, a,) so that answer = a,(rv1), and where

36 1

and

(b, ai)D ( t r u e , ai)

(9)

(i = 1,.. . ,n - 1) and (b, %) D (false,a,)

(10)

It can be shown that (9) entails (a,,IT,+^) I!- tologiq(b) = true

(11)

for i = 1,.. . , n - 1. and (10) can be used to prove that, for any state 7 (7, a ,)

It- tologicf(b) = f a l s e

(12)

The execution sequence can also be used to show : a and ai+l differ only at rv1 and rv2 in

((

rvz := extract(q); := (fun x~ :: xi => fun x : xsort(A) => xZ(rv1x)) rv2 rvt

TVI

), ) ui

D (rvi I c i + i )

for i = 1,.. . , n - 1. By inspection of the evaluation sequence (7), ol(rv1) = f u n x : xsort(A) => x

(13)

(14)

Also, because rv1 does not occur in extract(q), the execution of extract(q) from ai to a: will not affect the value of rv1: that is, ai(rv1) = ai(rv1). So, by inspection of the evaluation sequence (8): a i + l ( r v ~ is ) the reduced normal form of fun x : xsort(A) => fll(rv2)(ai(rvt)x) for i = 1,.. . , n - 1.

362

That is, ui+l (rvl) is the reduced normal form of fun x : xsort(A) => answer,,(oi(rvl)x)

So, because answer = pn(rvl), when n normal form of

for i = 1,.. ,, n - 1.

> 1, answer must be the reduced

fun x : xsort(A) => (answer,,,-, ( f u n x : xsort(A) => answer,,,-, 14 (. . . answer,, (fun x : xsort(A) => x x) . . .)x

That is, if n

>1

answer = fun x : xsort(A) => answer,,-,(answer,,-,

. . . (answer,,x) . . .) (15)

Also, by (14), when n = 1 (that is, when u‘ = u l ) , answer = f u n x : xsort(A) => x

(16)

Take arbitrary r,r” such that (extract(q),

T)

I ;(answer,,

7“)

By the induction hypotheses (3), (4), the definition of Skolem form and the fact that A[&/ij]and A [ ~ f / i are j ] not Harrop, (7,7”)IFL

)

: xsort(A[%/ij]) .Sk(A[si/ij]) [x/f A [ s i / o ] ] Atologki(b) = true -+ A [ s f / ~ ] [ a n s w exr/,f A [ s f / c ] ]

Vx

(

(17)

Recall that rv1 and rv2 do not occur in

vx : xsort(A[Si/ij])SL(A[si/ij])[z/ f A [ s i / g ] ]A tologici(b) 4

= true

A [ s f / g ] [ a n s w e rx~/ f A [ a f / o ] ]

It can then be shown that this implies the following. For any r’ that differs from T” at most on state variables rv1 and rvg, (TJ’)

11’

(Vx

)

: xsort(A[si/ij]).SL(A[si/V])[x/f~[~~/c]] Atologici(b) = true -+ A[Sf/v][answer, “/fA[sf/o]]

End of observations. We wish to show (6): (07

a’)

b’x : xsort(A[Si/ij]) .Sk(A)[Si/V] [ x / f ~ [/ #s I;] -+

( S k ( A ) [ s f / V ] [ a n s w x/ e r f A [ s f / g ] ]A tologicr(b) = f a l s e )

(18)

363

To do this, we take an arbitrary x : xsort(A[$i/i~])-variantL‘ of assumption (a,0’)

L

with the

Sk(A)[si/vl[x/fA[s;/8]]

(19)

Sk(A)[gf/v][answer x/fA[sf/o]]

(20)

and we prove

(a,a’) and

(a,a’) It,! tologicr(b) = false

(21)

Proof of (21). By (12), ( 7 , a n ) It tologicf(b) = false for any T. So, in particular, (a0,an) lk,~ tologicr(b) = false which is the same as writing (20), as required. End of proof of (21). Proof of (20). There are two subcases: 1) a = 00 and a’ = 01 ( n = 1) and 2) G = 00 and a‘ = an (n > 1). Subcase I. In this case, by (16), answer = fun x : xsort(A) => x

in our model of ADT, and so answer x = x. It can be shown that this and (19) entail (no, a l )

Sk(A)[&/6][answer x/fA[s;/8]]

(22)

Now, observe that 00 = a and a1 = a’ differ at most on rv1, which does not occur in Sk(A)[a,/v][answer x/fA[s,/o]]. It can be shown, using the definition of It, that these facts and (22) result in (a,0‘) I ~ L ! Sk(A)[gf/fl][answer x/fA[Sf/8]]

(23)

Subcase 2. If a’ = an for n > 1, we proceed as follows. Define a1 F 2

ak

= answer,,-,

(ak)

for k = 2 , . . . ,n. As usual, we take ai to be defined as tologic(ai). It will be important to note that, as answer,, is state-free, it is the case that each ak is also state-free. Consequently, the only state references in

Sk (A)[Bf

iaj

/ f A[Sf / 8 ]1

364

are S f . By expanding the definition of a,, we obtain a, = answerun-,(answerun-,. . . (answer,,x)

. . .)

We will show, for any j = 2 , . . .,n - 1 (gj 7

aj+l)

Sk(A)[Sf/v][aj+l/fA[rf/~]]

We proceed by induction. Base case. First, note that (19) can be written as ( 0 0 , 0,)

But, because

differ only at rv1, which does not occur in Sk(A)[Si/v][z/f~[~~/~]], by reasoning about the definition of IF, we can show that this means 00

and

IF'! sk(A)[si/v][Z/fA[B;/B]]

01

((Jl,u,)

Sk(A)[si/a][z/fA[~~/~]]

Also, because final states are not used in Sk(A)[Si/o][z/f~[a~/~]], we can then derive

Sk(A)[si/v][z/fA[~;/~]l

(ul,u2)

(25)

So we can instantiate (18) with (25) and (11 with i = l),to give

( a 02) , It,! A[Sf/@][answer,, z/fA[rf/~]] and we are done. Inductive step. Assume that

,

((Jk uk+l) IF'!

Sk(A)[sf/v][ak+l /fA[Bf/B]]

holds for some k < n - 2. /0],by reasoning Because no initial state references occur in Sk(A)[Sf over the definition of IF, this means

,

( ( ~ k + l 0k+2)

Sk(A[Si/v])[~i/~I[ak+l/f~[,-;/~]I (26)

w e can instantiate (18 setting T = ok+l and r' = ak+2) With (26) and with (11)setting i = k 1) to give

+

(vk+l,uk+2) IF'!

A[Zf/v][answeru,+, ak/fA[Bj/B]]

which means

(ck+l,gk+2) 11)' A[sf/a][ak+Z/fA[rf/~)]

as required and (24) is proven.

365

Now by (24), we know in particular that (ffn-1, f f n )

Sk(A)[i?f/v][an/fA[af/o]l

Now, because initial state references do not occur in Sk(A[i?f/a]), it can be shown that this means

S k ( A )[sf/a][an/fA[iif/ B ] 1 Also, because n > 1, (15) must hold, i.e.: (go, 0,)

answer = fun x : xsort(A) => answer(,n_l,,:_l)(answer(,n_,,,~_z)

. . . (answer(,, ;,, p ). . .) we know that answer x = a,

in our model of dV‘T, and so it can be shown that (go, an)

Sk:(A)[sf/f][answer x / f A [ a /fi i ] ]

End of proof of (20). Finally, by the definition of IF, because we took an arbitrary L’ (ff,ff’) IF,

vz : xsort(A[Sz /v]) .Sk(A)[q/v] /.[ f A [ &, B ] ] + ( S k ( A ) [ g f / v ] [ a n s m e rf xA/[ g f / 0 ] A ] tologicf(b) = f a l s e )

Case: Proof ends in application of (if-then-else). Suppose that twoTis of the form b pwl otologic; (b)=true-tC 1 qw2 otologic; (b)=faZse+C (zf-then-else) ite(p,q)if then b else wlzuzoC We need to show that (u, 0’)IF, Sk(C)[answer/f c ]

(27)

Because tologici(b) = true is Harrop, so by the induction hypothesis extract(p) retmr, tologici(b) = true

+C

(28)

Similarly, tologici(b) = false is Harrop, by the induction hypothesis extract(q) retmr, tologici(b) = false

-$

C

(29)

Therefore, by definition of s and S k , (28) means that, for any states 7,T’

*

(extractb), T ) [ ;(answerp,7’) ( T ,T ’ )

IF, tologici(b) = true + Sk(C)[answer,/ f c ]

(30)

366

and (29) means that, for any states T,T'

*

(extract(q),~ ) f(answerq, j 7') ( 7 , ~ 'It, )

tologici(b) = false + Slc(C)[answer,/ fc]

(31)

Either a(b) = true or a(b) = false. We reason over these two cases to obtain (27). Subcase 1: a(b) = true. so (b, a ) D (true, a )

and so, by the interpretation of = over side-effect-free terms, this means that (a,a') IF, tologici(b) = true

(32)

Also, the operational semantics of extract(t) demands the following hold: ( i f b then extract(p) e l s e extract(q), a ) 6 (answer, a')

(extract(p),a ) 6 (answer, a')

so, (extract@),a ) 6 (answer, a')

(33)

Instantiating (30) with (33) gives (a,a') It, tologici(b) = true + Sk(C)[answer/fc]

Instantiating this with (32) gives (a,a') IF, Sk(C)[answer/fc]

which establishes (27), as required. Subcase 2: a(b) = false. Similar reasoning to the previous subcase will establish (27). Case: Proof ends in application of (cons). Suppose tWoTis of the form c o n s V P , qP+A)w*A

derived by

By the induction hypothesis, we know that extractb) retmr, P

(34)

367

There are two cases, depending on whether P is Harrop or not. We consider the more complicated, latter case. By Theorem 6.1, fun x, : xsort(P) => extract(q) is an intuitionistic modified realizer of P -+ A, and so, for any (7,~') (777')I t

vxu : xsort(P).sk(P)[xu/fP]

-h

s k ( A ) [ ( azu)/fA]

(35)

for any a = tologic(a) where a = f u n x, : xsort(P) => e x t r a c t ( q ) [ ~ ( ~ ) / ~ i ] [ ~ ' ( S ) / ~ f ]

(36)

Now, the execution of extract(t) must result in a sequence of states (T

= 00,01,02,~3 = (T'

such that

-i .-

I ;rvp := extract(p);

B

:= I;

(fn Ii :: Sf 3 fun x, : xsort(~)=> extract(q)) !I :: B !rvp

)

(fn ~i :: Sf 3 fun x, : xsort(P) => extract(q)) ,0 3 !i:: B !rvp

(37)

I ; (answer,g3) where answer = fun xv : xsort(P) => extract(q)[a3(i)/Bi]['~3(?)/Sf] 03(rvp) (38)

and

(i := s , ( T ~ )C; (a1,crl) (rvp := extract(p), 01) C; (ap,0 2 ) (P := s , ( T ~I;) ( a 2 , ( ~ 3 )

(39)

so that u1 = ao[iI+ 0,,(s)]a3= 0 2 [ I

I+ 0

2 ( ~ ) ] ~ ( r= v ap ~)

(40)

Now, because the 5 do not occur in extract(p), formula (40) and inspection of (39) reveal that 03(F)

Also, because the values of

= 01(i) = 0o(S)

(41)

are unchanged in the assignment ? := S

(Tg(3)

= (T2(I) = 0 3 ( a )

(42)

368

So, using (40), (41) and (42) in (38) gives answer = f u n x, : xsort(P) => e x t r a c t ( q ) [ a ( ~ ) / ~ i ] [ a ’ ( ~ ) / ~ ap f]

in our model of d D 7 . Define a4 = fun

xv : xsort(~)=> e x t r a c t ( q ) [ a ( g ) / ~ i ] [ d ( ~ ) / ~ f ]

So that answer = a4 ap

in our model. By (35), it is the case that (a,.’)

1 1V X U : xsort(P).Sk(P)[Xv/fp] + S k ( A ) [ ( a q%

)/f~]

Also, given that (rvp := extract(p), al) 6 (ap,uz) we let a: be the state such that (extract(p), 01) & (ap,a;) Now, recall the induction hypothesis: extract@) retmr,

P

(47)

This means that (al,.:)

IF’ Sk(P)[ap/fpI

(48)

Note that (TO can differ from a1 only on i, and a3 can differ from a: only on I and rvp. So, because i, 3 and rvp do not occur in Sk(P)[a,/fp],as for (22) ( a , 411‘ Sk(P”p/fPl

We instantiate (46) with (49) to give a’)

S k ( A ) [ ( a qap)/fA]

But then, by (45) it can be seen that

(a,a’)IFL s k ( A ) [ a n s w e r / f ~ ] as required. This last case concludes our proof.

(49)

369

7. Implementation We have implemented our calculus by encoding the LTT within SML.The proof-terms and labelled formula types are defined as data-types, the LTT typing relation is represented as pairs of terms of the respective data-types, and the rules of the calculus are treated as functions over such pairs. One of the advantages of our calculus is that it has a natural deduction presentation. This makes it easier to reason with than, say, the usual Hilbertstyle presentations of Hoare-style logics. Further, the Curry-Howard isomorphism can be exploited to enable intuitive user-defined development of proof tactics and parametrized lemmata, treated here as SML functions over proof-terms. In this way, the user can develop a proof in the way mathematicians naturally reason: using hypotheses, formulating conjectures, storing and retrieving lemmata, usually in a top-down, goal-directed fashion. The strong normalization property can also be used to simplify proofs, which is valuable in the understanding and development of large proofs.

Example 7.1. We illustrate our approach to program synthesis with an example, involving code for part of an internet banking system. We require a program that, given a user’s details, will search through a database to obtain all accounts held at the bank by the user, and then returns them in a list. For the sake of argument, we simplify our domain with the following assumptions: We assume two SML record datatypes have been defined, user and account. Instances of the former contain information to represent a user in the system, while instances of the latter represent bank accounts. We do not detail the full definitions of these types. Howver, we assume that an account record type contains a user element in the owner field, to represent the owner of the account. So the owner of the account element myAccount : account is accessed by myAccount .owner. We also assume that user is an equivalence type, so that its elements may be compared using =. We assume a constant currentUser : user that represents the current user who is the subject of the account search. The database is represented in SML as an array of accounts, db : account array

370

Following the SML API, the array is 0-indexed, with the ith element accessed by sub(db, i)

and the size of the array given as

length db Assume we have an array of size Size, accounts. Although SML arrays are mutable, for the purposes of this paper we shall consider db to be an immutable value, and therefore it will be represented in our logic as a constant. We assume a state reference, counter : int ref, to be used as a counter in searches through the database. We take a predicate

alZAccountsAt(u: user, x : account list, y : int) whose meaning is that x is a list of all accounts found to be owned by the user u,up to the point y in the database db. The predicate defined by the following axioms in AX Vu : user.Vx : (account Zist).Vy : int.aZlAccountsAt(u,x,y)-+

Vz : int.z

5 y + sub(&, z).owner = u (50)

V u : user.Vx : (account Zist).Vy : int.

< (length d b ) - l

(y

= true)Asub(db,y+l).user = uAaZZAccountsAt(u,x , y)

aZlAccountsAt(u,sub(db, y

+ 1) :: x,y + 1)

+

(51)

Vu : user.Vx : (account Zist).Vy : int. y

< (length db) - 1A isub(Z,y + l).user = u A allAccountsAt(u,x,y) + aZZAccountsAt(u,x , y Vu : user.Vy : i n k y = 0 + aZZAccountsAt(u,[I, y)

+ 1)

(52)

(53)

(these axioms are available for intuitionistic proofs, so they do not involve programs). Applications of these axioms are used in the LTT with axiom names given by their equation numbers. For instance, an application of (50) is denoted by Axiom(50).

37 1

Our requirement is to obtain a program that returns a list of accounts y : (account list) such that

EistAlIAccounts( current User,y , (length d b ) ) To extract this program from a proof, we unSkolemize this formula, to derive

3y : (account list) .listAllAccounts( currentuser, y , counterf) A

(counterf < (length db) - 1) = false

Extraction of a modified realizer for this formula will produce an imperative program whose return value is the required list of accounts. The previous axioms are Harrop. We also have a non-Harrop axiom y

< (length db)-I + sub(l,y+l).owner = u\/isub(I,y+I).owner = u (54)

Because this axiom is to be used in intuitionistic proofs, we assume that this axiom is associated with a side-effect-free program that is an intuitionistic modified realizer of (54). From (51),(52) and (54),we can derive an intuitionistic proof y

< (length db) - 1 = true, allAccountsAt(u,1, y )

+

kl,t 3 1 : (account Zist).alZAccountsAt(u,l,y 1) ( 5 5 )

By assuming 3 1 : (account list).allAccountsAt(u,l,y), we can apply 3 elimination to (55) and then obtain klntV y : int.Vu : user.(y < (length db) - 1) = true A 3 1 : (account l~st).alZAccountsAt(u, I,y)

+

3 1 : (account list).aIlAccountsAt(u,I , y

+ 1)

(56)

by (+-I) over our assumptions, and successive (V-I) over free variables. We can transform (56) into

klnt V y : int.Vw : int.w = y + 1 + (Vu : user.(y < (length db) - 1 ) = true A 3 1 : (account Zist).allAccountsAt(u,l,y) -+ 3 1 : (account list).alIAccountsAt(u,I , w)) (57)

372

We then use (58) with counteri and counterf and currentUserfor for y, v and u,to give klnt

+

counterj = counteri 1 + (counteri < (length db) - 1) = trueA 3 1 : (account list).allAccountsAt(currentUser,I , counteri) -+ 3 1 : (account list).allAccountsAt(currentUser,I , counterf) (58)

There is a proof-term corresponding to this proof, which we shall denote by and that a program PP : i n t - > int can be extracted from p5g that is a modified realizer of (58) (for brevity, we omit the full description). We also have the following, by the (assign) rule of the Hoare logic:

p58,

k counter := counter

+1

counterj = counteri + 1

This has a corresponding proof-term assign(counter, counter And so, by applying (cons) to (59) and (58), k counter := counter

+1

(59)

+ 1).

(counteri < (length db) - 1) = trueA

3 1 : (account list). alMccountsAt(current User,1 , counteri) -+

3 1 : (account list).allAccountsAt(currentUser,1, counterj) (60) The corresponding proof-term is

cons(assign(counter,counter

+ l),p5g)

Then we apply (loop) on (60) k while counter

< (length db) - 1 do counter

:= counter

+ 1;done.

3 1 : (account list).allAccountsAt(current User,1, counteri) -+

3 1 : (account l~st).allAccountsAt(currentUser, 1, counterf)A (counterj < (length db) - 1) = false (61) with resulting proof-term

wd(cons(assign(cmnter,counter

+l ) , ~ ~ ~ ) )

From the axiom (53) we can derive

counterj = 0 + 3y : (account list).allAccountsAt(currentUser,y, counterj)

(62)

with a proof-term p62. By application of (assign) k counter := O

counterf = 0

(63)

373

with proof-term assign(cmnter,0). Then, applying (cons) to (63) and (62) gives

counter := 0e3y : (account list).allAccountsAt(currentUser,y , counterf) (64) with proof-term cons(assign(counter,O ) , P ~ ~ )This . can be weakened to include a true hypothesis true:

counter := 0 true + 3y : (account list).aZlAccountsAt(currentUser,y , counterf) (65)

with a proof-term of the form cons(cons(assign(cmnter,

O), p 6 2 ) , ptrue)

where ptrue is a proof-term for an intuitionistic proof of P -+ (true + P ) ( P 3y : (account Zist).aZZAccountsAt(currentUser,y , counterf)). So, using (seq) on (65) and (61), we can obtain

t- counter := counter + I; while y < (length db) - 1 do counter := counter + 1;donee true + 3y : (account list).allAccountsAt(currentuser, y , counterf)A (counterf < (length db) - 1) = false (66) with proof-term

seq(cons(cons(assign (counter,0 ) , p62), ptrue),wd(cons(assign(counter,counter+ l),p58)))

which can be simplified to the required form I- counter := counter while y

+ 1;

< (length db) - 1 do counter := counter + 1;done.

3y : (account list).aZlAccountsdt(current User,y , counterf)A

(counterf < (length db) - 1) = false

(67)

with a corresponding proof-term of the form: cons(seq(cons(cons(assign( counter,0 ) ,

psz),ptrue),wd(cons(assign(counter, counter

+ l),p58))),qtrue)

(68)

374 p T

!xtract( t )

any term t with H ( T ) Axiomln\voA

'Kn

rv1 := fun x : xsort(A) wd(u)vhile

do b;donsl*P

where P A [ s i / e ] -+ ( A [ s f / " ]A tologicr(b) = f a l s e )

=> x;

vhile b do rvz := extract(q); rv1 := (fun x2 :: x i => fun x : xsort(A) => x2 (rv1 x)) !rv2 !rv1; !rvl: f b then extract(q1) else extract(q2) - 2

not H ( A ) , not H ( B ) and not H ( C ) : rvp := extract(p); rvq := extract(q); (fun x, :: xq => fun x : xsort(A) => rvq (rvpx)) !rvp !rvq

H ( A ) , not H ( B ) and not H ( C ) : rvp := extract(p); rvq := extract(q); rvq rvp

H ( A ) , H ( B ) and not N(C): "; rvq := extract(q); !rvq

not H ( A ) , H ( B ) , and not H ( C ) : v; rvq := extract(q); (fun xq => fun x : xsort(A) => xq x) !rvq

not H ( P ) and not H ( A ) : i := g. C V := ~ extract(p);

1 .- s;

'fn ~i :: sf => fun xv : xsort(P) => extract(q)) !rvp !I :: ? H ( P ) and not H ( A ) : I := I; v; ? := I ; (fun si :: gf => extract(q))

!I:: i Figure 9. Definition of extraction map extract from proof-terms to SML programs. Here we assume that rv1, rv2, rvp, rvq, I and 5 are state references that do not occur in extract(p) and extract(q), and whose corresponding state identifiers do not occur in any of the formulae used in the proof of p or q.

375

where qtrue is a proof of (true + A ) t A for

A

3y : (account list).aZlAccountsAt(currentUser,y, counterf) A (counterf

< (length db) - 1) = false.

Finally we apply extract to (68), obtaining the required program r v l := f u n x:account l i s t => x ; while counter<(length db) - 1 do ( r v 2 := ( i c := !counter; c o u n t e r : = c o u n t e r + l ; i f := ! c o u n t e r ; ( f u n c o u n t e r - i => f u n counter-f => (PP c o u n t e r - i currentuser)) i c i f ) r v l := f u n x-2::x-l=> f u n x => (x-2 ( r v l x ) ) ! r v 2 ! r v i ; ) ! r v l [I ;

8. Related work and conclusions Various authors have given type-theoretic treatments to imperative program logics. It has been shown in [6] how a Hoare-style logic may be embedded within the Calculus of Constructions through a monad-based interpretation of predicate transformer semantics, with an implementation in the Coq theorem prover [3]. Various forms of deductive program synthesis, with its roots in constructive logic and the Curry-Howard isomorphism, have been used successfully by [ll],[12] and [15]. The difference between our approach and those mentioned is that we do not use a meta-logical embedding of an imperative logic into a constructive type theory, but rather give a new logic that can be presented directly as a type theory. Apart from the novelty of our approach, our results are useful because they present a unified means of synthesizing imperative program according to specifications of both side-effects and return values. Further, from the perspective of theorem prover implementation, the advantage of our calculus over others is the use of a natural deduction calculus for reasoning about imperative programs and the consequent adaption of the Curry-Howard isomorphism. References 1. Ulrich Berger and Helmut Schwichtenberg.Program extraction from classical proofs. In D. Leivant, editor, Logic and Computational Complexity, International Workshop LCC '94, Indiapolis, IN, USA, October 1994, pages 77-97, 1995. 2. Robert L. Constable, Stuart F. Allen, H. M. Bromley, W. R. Cleaveland, J. F. Cremer, R. W. Harper, Douglas J. Howe, T. B. Knoblock, N. P. Mendler,

376

3.

4.

5.

6.

7. 8. 9. 10.

11.

12.

13.

14.

15.

P. Panangaden, James T. Sasaki, and Scott F. Smith. Implementing Mathematics with the Nuprl Development System. Prentice-Hall, NJ, 1986. Thierry Coquand. Metamathematical Investigations of a Calculus of Constructions. In Piergiuorgio Odifreddi, editor, Logic and Computer Science, pages 91-122. Academic Press, 1990. Patrick Cousot. Methods and logics for proving programs. In Jan Van Leeuwen, editor, Formal Models and Semantics: Volume B, pages 841-994. Elsevier and MIT Press, 1990. John Newsome Crossley and John Cedric Shepherdson. Extracting programs from proofs by an extension of the curry-howard process. In John Newsome Crossley, Jeffrey B. Remmel, Richard A. Shore, and Moss E. Sweedler, editors, Logical Methods, pages 222-288. Birkhauser, Boston, MA, 1993. J. C. Filliatre. Proof of imperative programs in type theory. In International Workshop, T Y P E S '98, Kloster Irsee, Germany, volume 1657 of Lecture Notes in Computer Science, pages 78-92. Springer-Verlag, 1998. Jean-Yves Girard, Yves Lafont, and Paul Taylor. Proofs and types. Cambridge University Press, Cambridge, 1989. Ronald Harrop. Concerning formulas of the types A 4 BVC, A + ( E z ) B ( z ) in intuitionistic formal systems. Journal of Symbolic Logic, 25:27-32, 1960. C. A. R. Hoare. An axiomatic basis for computer programming. Communications of the Association f o r Computing Machinery, 12(10):576-80, 1969. John S. Jeavons, Bolis Basit, Iman Poernomo, and John Newsome Crossley. A layered approach to extracting programs from proofs with an application in Graph Theory. In these Proceedings. Zohar Manna and Richard J. Waldinger. The deductive synthesis of imperative LISP programs. In Sixth A A A I National Conference on Artificial Intelligence, pages 155-160, 1987. Mihhail Matskin and Enn Tyugu. Strategies of Structural Synthesis of Programs. In Proceedings 12th IEEE International Conference Automated Software Engineering, pages 305-306. IEEE Computer Society, 1998. Iman Poernomo. The Curry-Howard isomorphism adapted for imperative program synthesis and reasoning. PhD thesis, Monash University, Australia, 2002. In preparation. A Technical Report, which is an extended version of this paper, is available at http: //www. csse .monash.edu. au/-ihp/karma, DSTC, Melbourne, Australia, 2001. Iman Poernomo and John Newsome Crossley. Protocols between programs and proofs. In Kung-Kiu Lau, editor, Logic Based Program Synthesis and Transformation, 10th International Workshop, L O P S T R 2000 London, UK, July 24-28, 2000, Selected Papers, volume 2042 of Lecture Notes in Computer Science, pages 18-37. Springer, 2001. Jamie Stark and Andrew Ireland. Towards automatic imperative program synthesis through proof planning. In Proceedings 13th IEEE International Conference Automated Software Engineering, pages 44-51, 1999.

377

PHASE-VALUED MODELS OF LINEAR SET THEORY

MASARU SHIRAHATA Division of Mathematics, Keio University, Hiyoshi Campus, 4-1-1 Kohoku-ku, Yokohama 223-8521, Japan E-mail: [email protected] The aim of this paper is a model-theoretic study of the linear set theory. Following the standard practice in intuitionistic and quantum set theories, we define a set to be a function from its members to non-standard truth values. In our case, the truth values are facts in a phase space as defined by Girard. We will construct the universe V p from the phase space P and verify a number of set-theoretic principles which are linear logic versions of the Z F axioms.

1. Introduction

In this paper, we will extend the Boolean-valued model for classical set theory [5,9] to linear logic. This is in analogy to the locale (Heyting)valued model for intuitionistic set theory [l],and, Takeuti and Titani’s ortholattice-valued model for quantum set theory [8]. The general idea is as follows. Given a propositional logic and its algebraic model, we can regard an element of the algebra as a (non-standard) truth value. Then we can extend the notion of characteristic functions, or sets, so that their range becomes the set of the extended truth values. In the case of linear logic, such an underlying set of truth values is given by the set of facts in a phase space as defined by Girard [3]. It is worth noting the similarity of the set of facts with the ortholattice in quantum logic. In short, the ortholattice is the lattice of closed subspaces of a Hilbert space ordered by inclusion. To each Hilbert space corresponds a physical system. Each vector in the space represents a state that a physical system can assume and each closed subspace represents an observable property of the physical system. Duals are defined by the orthogonality in the Hilbert space. Then, the correspondence is the following. 0

phase space/Hilbert space, facts/closed subspaces.

378

In fact, this is not at all surprising since Girard has this similarity in mind from the beginning: There is a Tarskian semantics for linear logic with some physical flavour: w.r.t a certain monoid of phases formulas are true in certain situations. ... One of the wild hopes that this suggests is the possibility of a direct connection with quantum mechanics ... but let's not dream too much! ([3], pp. 7-8.) The change of viewpoint occurring in linear logic is simple and radical: we have to introduce an observer, in order to verify a fact A, the observer has to do something, i.e., there are tasks p , 4,.. . which verify A ... These tasks can be seen as phases between a fact and its verification; ([3], p. 18.) The point stating the similarity explicitly here is to give the reader some assurance that the approach taken in quantum set theory can be transferred to linear set theory, at least to some extent. 2. Preliminary

In this section, we review the phase space semantics for linear logic and the construction of the Boolean-valued model.

Definition 2.1. A phase space is a quadruple P = (P,1,., I)where 0

(P,1,.) is a commutative monoid;

OIGP. 1 is the unit of the multiplication.

We will write p q for p . q. If A and B are subsets of P , we will write A . B , or AB, for the set { p q I p E A and q E B } .

Definition 2.2. Given a subset A of P , the dual or the linear negation of A, denoted A l , is defined by A' = { p E P I (Vq E A) pq E I}. Definition 2.3. A subset A of P is a fact if A = A l l . We denote the set of facts in P by Factp. Note that we always have A 5 A l l since p q E I for any p E A and q E A*. Furthermore, A G B implies B* C A' since p q E I for any p E A C B and q E B*. Then it immediately follows that A l = A l l L ,

i.e. A' is a fact for any A C_ P .

379

Definition 2.4. A fact A is valid if 1 E A. Proposition 2.1. Facts are closed under arbitrary intersection.

ni,,

We understand the arbitrary intersection Ai as the operation on the power set of P. In particular, Ai = P if I = 0.

ni,,

niE,

Proof. Let {Fi}iE, be a family of facts and A = Fi. Then, A E Fi for any i E I. Hence, A l l C F k l = Fi. Therefore, ALL & Fi. 0

ni,,

Proposition 2.2. AI" is the smallest fact containing A for any A 5 P . The order is given by the set inclusion. Proof. Let A C_ B with B = B l l . Then BL C_ A*, and this implies ALL B'-l = B. 0

Definition 2.5. We define the multiplicative operations on the set F a c t p of facts in P as follows. F @ G= ( F G ) l l , FVG = ( F L G " ) I , F -o G = ( F G l ) * . F @ G and FVG are called the multiplicative conjunction and the multiplicative disjunction, respectively. F -o G is the linear implication. FVG is defined via the DeMorgan duality as (F* @ G * ) l , and F defined as F*vG.

-o

G is

Definition 2.6. We define the additive operations on the set F a c t p as follows. F&G=FnG, F CB G = ( F u G)*% F&G and F @ G are called the additive conjunction and the additive disjunction, respectively. Definition 2.7. In addition to I,we define the constants in P as follows. 0 0

1 = I I, T=P,

I o O = T .

380

Note that I= (1)'- and T = P = 0'-. All those constants are facts since they are linear negations. Furthermore F 8 1 = F for any fact F. To see this, let p E F . 1 with p = qr for some q E F and r E 1. Then, for any s E F L , we have qs E I and qsr E 1.Hence p = qr E FLL= F . This implies F €3 1 F . The other direction follows from 1 E 1. Now we define the semantics for the multiplicative-additive fragment of linear logic (MALL). Definition 2.8. A phase structure for MALL is a phase space with a function which assigns a fact to each propositional letter. The interpretation of a sentence is a fact assigned to the sentence by extending the function inductively. Definition 2.9. A sentence is valid if the unit 1of the commutative monoid P is in its interpretation. A sentence is a linear tautology if it is valid in any phase structure. Proposition 2.3. MALL is sound and complete with respect to the validi t y in phase structure. For the proof of Proposition 2.3, we refer the reader to Girard's original paper [31. The phase semantics can be easily extended to predicate logic. We simply interpret quantifications as infinitary additive conjunction Fi and and disjunction (U Fi)'-'-.

n

Definition 2.10. Let { F i } i €be ~ a family of facts. We define the infinitary Fi and the infinitary additive sum CiEr Fi as follows. additive product

ni,,

n i E I Fi =

Fi,

~ i c Fir = (UiezFi)LL* We often omit the index set I .

ni,,

As before, we understand the infinitary intersection Fi and union UiEIFi as the operations on the power set of P. In particular, Fi = P = T and CiEr Fi = 0l'- = 0 when I = 0.

ni,,

For exponentials, we need to extend the phase space. Definition 2.11. A topolinear space is a phase space paired with the set F of the closed facts such that

381

(i) 3 is closed under arbitrary intersection (additive conjunction); (ii) F is closed under finite multiplicative disjunction; (iii) I is the smallest fact in (iv) for all A E F ,A g A = A . The linear negations of closed facts are called open facts.

Definition 2.12. We define the exponential operations on the set Factp as follows. 0 0

!F = the greatest open fact included in F , ?F = the smallest closed fact containing F .

The order is given by the set inclusion. There is a new simplified version of the definition of exponentials in the phase space [4]. For our present purpose, however, the above definition suffices.

Proposition 2.4. Linear logic is sound and complete with respect to the validity in the topolinear spaces. We now collect some useful propositions for the later calculations.

Proposition 2.5. Let F and G be facts. The following are equivalent.

IEF-oG, C G, (iii) F G ~ I. (2)

(aa) F

Proof. From (iii) t o (ii): Let FGI C 1.Then F C Gl' = G . From (ii) to (i): Let F C G. Then (1). FGL = FG' C GG' g 1.Hence 1 E ( F G l ) l = F 4 G . From (i) to (iii): Let 1 E F 4 G . Then ( l } . F G * = FGI

I.

0

Proposition 2.6. Let F and G be facts in P . Then for any p E F and q E F -oG, we havepq E G . Proof. Let r E G I . Then pr E FGI and pqr E I,since q E ( F G l ) ' . Hence pq E G I L = G. Proposition 2.7. Let A C P and F be a fact. Then, ALL @ F = ( A F ) l L .

382

Proof. AF C A l l F C (A * * F )l I = A L L 8 F . So ( A F ) * l C A l l 8 F by Proposition 2.2. For the other direction, let p E ( A F ) I . Take any q E F. Then pqr E 1for any r E A. Hence p q E A l . Since the choice of q is arbitrary, we have A"F. { p } C 1.Hence p E ( A l l F ) I . Then ( AF) ' - C_ (A"F)I and it follows that ( A L l F ) I L E ( A F ) l l . Proposition 2.8. Let Fi and G be facts. Then

(c

{(u

Proof. By Proposition 2.7, Fi) 8 G = Fi) G}lL = {U (FiG)}". Then, {U (FiG)}'l C {U (Fi 8 G ) } l l = C (Fi 8 G ) . On the other hand, Fi 8 G = (FiG)l' C {U(FiG)}l' for any i. Hence, U ( F i 8 G ) {U ( F i G ) } l l and C (Fi 8 G ) C_ {U ( F i G ) } l l by Proposition 2.2. Proposition 2.9. Let F,G and H be facts. Then

( F 8 G )8 H = ( F G H ) I L . Proof. ( F 8 G ) 8 H = ( F G ) I l 8 H = (FGH)"

by Proposition 2.7. 0

Proposition 2.10. Let {Fi} be the family of facts. Then ( n F 5 ) ' CFi.

n

=

n

Proof. It suffices to show that F? = (U Fi)'. Let p E F k and q E Fi for some i. Then pq E 1. Hence p E (U Fi)'. For the other direction, let p E (UF i ) l and q E Fi C U Fi. Then p q E 1. So p E F t . Hence p E nFk. 0 Proposition 2.11. Let F be an open fact. Then the following holds.

c

(2) F 1, (a) F 8 G G for any fact G , (ii) F = F 8 F . Proof. (i) Let F = G I with closed G. The claim follows from 1C G. (ii) F @ G C l @ G = G . (iii) Let F = G I with closed G. The claim follows from G = GvG.

Proposition 2.12. For any facts F and G, we have ! F 8 ! G = ! (F&G).

383

Proof. Note that open facts are closed under finite multiplicative conjunction. Hence ! F @ ! G is an open fact. Now !F @ !G C ! F F. Similarly ! F @ !G C G. Hence ! F @ !G C F n G = F&G. This implies !F @ ! G C ! (F&G). On the other hand, we have ! (F&G) = ! ( F & G ) @!(F&G)c_ ! F @ ! G .

s

Proposition 2.13. Let F be a fact. If F i s valid, so is ! F . Proof. Suppose 1 E F . Then F L C 1.Hence 1 = Therefore 1 E 1 C F .

ILC F * l = F . 0

We now turn our attention to Boolean-valued models. Let 23 be a complete Boolean algebra. We first define the 23-valued universe V".

Definition 2.13. We define the sets V," and the class V" by the transfinite induction on ordinals a as follows.

{

:v

= 0, Vt+l = {u I u is a function with dom(u) C V," and ran(u) = B}, Vf = V," where X is a limit ordinal.

ua.,x

v" = U a E O r d Kt3 . Ord is the class of all ordinals.

Next we define the interpretation of atomic propositions. Note that we can assign the rank p(u) to each u E Va by p(u) = t h e least a such that u E Vz+,,

Furthermore, we will use the canonical ordering [5] on Ord x Ord defined by

* [m=(a, P ) < mad?, 811 or

(a,P ) < (7,s)

[max(a,/?)= max(y,S) and a

< 71 or

[max(a,@)= max(y,S) and a = y and

P < 61.

The canonical ordering on Ord x Ord x Ord is defined similarly.

Definition 2.14. For u , v E V " , we define [u= v],[u2 w] and [uE v] by the transfinite induction on ( p ( u ) ,p ( v ) ) as follows.

*

' I[. 0

0

1') = VzEdom(v) ('(.I I[. = u ] > 7 [uC v] = AzEdom(.cl)(~(x) + [z E v]) where a .6 = = iu v] A I[ c_ . .I.

c

+ b = T a V b,

384

The idea behind the above definitions is the following translation. 0 0

*

21 E 21 (3x E w)(x = u), u g v w (Vx E u)(xE v), u=v(ju~vandvEu.

Notice that universal and existential quantifications are interpreted as infinitary conjunction (meet) and disjunction (join), respectively.

Proposition 2.14. For every u,v E V",

(i) I[ = .= 1, (ii) iu = = 1. = (iii) I[ = .A I[ =. w j 5 I[ =. wj, (iu) [uE v] A [w = u]A [t = v ] 5 [[wE t].

un,

The proof is by the transfinite induction on the canonical ordering of (p(u),p(v)). Now we extend this assignment to every sentence.

Definition 2.15. For every formula cp(z1,. . . ,xn), we define the Boolean value of cp ucp(ul, . . . , un)n

(Ul,

..., U n

E V")

as follows. (a) If cp is an atomic formula, the assignment is as we defined above; (b) if cp is a negation, conjunction, etc., u+(u1,. . . ,un)i = - w ( u l , .. . ,un)n,

111, AX(^^,. . . ,u,)n = u+(ul,. . . +,in A [x(ul, . . . ,un)n, 111, v x(ul,. . . ,un)n = w ( u l , . . . ,un)n v I [ X ( ~ .~. ,. ,un)n, 1111, + x ( u l , . . . ,u,)n = w ( u l , . . . , un)n + ux(ul,. . . ,un)n, 111, x ( u l , .. . ,un)n = 1111,+ A . . . ,un)n A XII -++ ( u l , . . . , un)n; (c) if cp is 3x11,or Vx11, 1 [ 3 ~ $ (ul, ~ , . . . ,u,n =

V A

M U , ul,.. . ,u,n,

UEV"

PTG(~, ul,. . . ,unn =

MV,

u1

. . . ,unn.

UEV"

Definition 2.16. A sentence cp is valid in V" if top element of the boolean algebra B.

[[(PI= 1, where 1 is the

Proposition 2.15. Every axiom of ZFC is valid in V".

385

3. The Phase-valued Model V p We now define our model V p . The construction is essentially the same as that of V“ except that we will use the set Factp of facts in the topolinear space (P,F)instead of the boolean algebra B. Definition 3.1. We define V,” and V p by the transfinite induction on ordinals a as follows:

{

vop = 0,

Vz+l = {u I u is a function with dom(u) C V’, and ran(u) = Factp}, V r = Ua<XV,” where X is a limit ordinal.

v p = UaEOrd v,” *

The rank p(u) is defined similarly as in V”.

Proposition 3.1. VF C V,” for

0 < a.

Proof. The proof is by the transfinite induction on a. Assume that V: C V g holds for any y < p with 0 < a. If a is a limit ordinal, the proposition holds by the definition. Suppose that Q = a’ + 1. Let u E V r with 0 < a, and p‘ = p(u). Then /?‘+ 1 5 p and u E Hence dom(u) VF with p’ < a‘. So dom(u) C V$ by the inductive hypothesis. Hence u 6 V z . 0 Definition 3.2. For u , v E V p , we define [u= v],[u & v] and [uE v] by the transfinite induction on ( p ( u ) ,p ( v ) ) as follows.

.[I E .]I = C z E d o m ( v ) ( v ( z ) 8 8. = 4l) , I[. C ‘1 = nz,,om(u,(u(.) --o.[I E vll), .1 = = !I[. 2 8 !I[. E .I. We note that .[I E .]I

= 0 when dom(v) =

0, and [uC .]I

= T when

dom(u) = 0.

Proposition 3.2. For every u,v E V p ,

(i) 1 E u(z) -O [z E u]for all z E dom(u), (ii) 1 E I[ =. u], (iii) 1 E = = .I.

nu

Proof. We prove (i) and (ii) by the simultaneous transfinite induction on p(u). Note that the base case p(u) = 0 is subsumed under the case dom(u) = 0.

386

(i) We show that for all z E dom(u),

I[ E.

I.

If dom(u) = 8, this holds trivially. Otherwise, 1 E [z = x] by the inductive hypothesis. Then u ( z ) = u ( z ) . (1) (u(z) . . I[ E. unL = IL c - UyEdom(u)(u(Y) . uz = ~ence 4.1 . (UyEdom(u) ( 4 ~ 8b ) = Yll))"' = ' (Uy€dom(u) ( u ( Y ) @ I[ =. 1. (ii) It suffices t o show 1 E !I[. u].NOW [U u]= --o Otherwise, [z E u]). If dom(u) = 0, we have 1 C P = [uC u]. u ( z ) . [z E .]IL I for all z E dom(u) by (i) so that 1 = n,Edo,(u,(u(z) --o [z E u]).Since Iis the smallest closed fact, 1 is the greatest open fact. Hence 1 = ![uC u]and clearly 1 E 1. (iii) We show [u = w] . [v = u ] ' C 1.Since the multiplicative conjunction is commutative, [u = v] = [v = u ] and the claim immediately follows. 0

w*.

w) mLc

c

nzEdom(u)(+)

c

c

c

Proof. The proof is by the simultaneous induction on (p(u),p(v),p(w)) along the canonical ordering, which is sensitive to the permutation of u,w and w. To carry the induction through, we divide (ii) and (iii) into two separate cases:

(ii-a) (ii-b) (iii-a) (iii-b)

1E 1E 1E 1E

lv E wi 8 I[ = .--o I[ E wi, . uv E 8 I[=.w]-+ E ui, uu E 8 I[=. --o I[ E wi, . 8

E

nu

=

E

So, we in fact prove (i), (ii-a), (ii-b), (iii-a) and (iii-b) simultaneously.

c

(i) First we show [uC v] 8 [w = w] [uC 2.1. By Proposition 2.2, Definition 2.5 and Definition 3.2, it suffices to show

n

).(.(

zEdom(u)

--o

8.

E

n

(W

z Edom( u )

I[ E. wn).

387

Let p E n,E,o,~,,(u(z) --o [z E u])and q E [v = w].We want to show p q E ( u ( y ) [y E w]l)lfor any y E dom(u). Let T E u ( y ) . [y E w ]' and T = tt' with t E u(y) and t' E [y E w]'. Since p E u(y) 4 [y E w],we have pt E [y E w].By the inductive hypothesis of (iii-a),

Hence ptq 6 [y E w].Therefore pqr = ptqt' E I,and it is done. Similarly, we can show [w 5 v] 8 [u= v] 5 [w C u] with the roles of u and w being exchanged, using the inductive hypothesis of (iii-b). With the above preparation, we show [u= v] 8 [v = w] [u= w].Using Proposition 2.11,

c

Now open facts are closed under finite multiplicative conjunction. Hence ![uC_ w] 8 [w = is open. Therefore, we have ![ug v] 8 [w = u] ![u5 w]. Similarly, ![w w] 8 [u= u] 5 ![.I u]. Hence, [u= w] 8 [U = w]C [u= w]. (ii-a) We want to show [u E w]8 [u= w] C [u E w].By Proposition 2.8 and Proposition 2.9,

c

E w]8

c

= .] =

(CC I €do,(

)

( ' ~ ( 8~ I 1[ =. .])

I Edom(w)

=

c

8 [U = .]

(w(z) . I[ =. .]I. I[ =. .]) 'I

w)

By the inductive hypothesis for (i),

Hence [V E w ] 8 [U = .] E &dom(w)(~(z) 8 [X = u ] )= [U E w]. (ii-b) is proved similarly, using the inductive hypothesis of (i). Note that (i) is symmetric with respect to the roles of u and w.

388

c

(iii) We want t o show [uE u]8 [[w = w] [uE w]. By Proposition 2.8, Proposition 2.7 and Proposition 2.9, E .] 8 I[ =. w] =

(

).(.(

8

z€dom(v)

C

=

C

=

qw C_

. !I[.

).(

I[.1

C_ w ] .

= w]

8

II

I[. = .])

zEdorn(v)

.K. c n

Let y E dom(v). By Proposition 2.6,

m

c s V(Y)

![. wn

wn

= w(y) . (

).(w

--o

u.

E wn)

x€dom(v)

c v(y) . MY) c uy E wn.

--o

BY E wn)

Therefore it suffices to show [y E w j .

uy = c .1 E w].

c

However we have [y E w] 8 [[y = u] [uE w] by the inductive hypothesis of (ii-a). Hence, by Proposition 2.11, ~[yE w]

.

c

.I [ = ~

g

E w] 8 qw

c I[Y E wn 8

c

8

uy =

= un

2 I[ E w]. . (iii-b) is proved similarly with the roles of u and w being exchanged, using the inductive hypothesis of (ii-a). 0 Definition 3.3. For every formula cp(z1,. . . , xn), we define the phase value of cp

[v(u1, . . . ,un)n

(u1,. .. ,u,E V P )

as follows. (a) If cp is an atomic formula, the assignment is as we defined above; (b) if cp is a linear negation, multiplicative conjunction, etc.,

w ( u l , . .. = [+(ul,.. . ,un)nL, 8 x(ul,.. . ,unn = u+(ul,. . .,un)n8 [X(ul,. . .,un)n, I [ + V X ( ~ ~. ., . ,unn = w ( u l , . . . , u n ) m ( u l , . . . ,un)n7

389

Proposition 3.4. 1 E [u=

@ I[+(.)]

Q

[+(v)Jj for any formula

4.

Proof. The proof is by induction on the construction of 4, using that [u= v] is an open fact. For example, 1 E [u= u]8 [$(v)] Q [+(u)]implies 1 E I[. = W] @ I[$+)] 4 [$I(v)]. Similarly 1 E .[I = v] @ [$(u)] 4 I[$(u)ll and 1 E [U = .]I @ [X(u)B--o [x(w)] implies 1 E [u= u] @ [Q @ x(u)l 4 @Xwn. 0

u+

We now start checking the validity of the basic set-theoretical principles. We will write (3y E z) +(y) and (Vy E z) +(y) for 3y (y E IC 8 $(y)) and Vy (y E z --o d(y)), respectively.

Proof.

(a) By Proposition 2.8 and Proposition 3.4,

UP^ E +wn

=

C (UYE n. 8 umn) yEVP

390

yEVP zEdom(s)

z Edom( z)

For the other direction, note that if y E dom(z), we have z(y) [y E z] since 1 E [y = y]. Hence,

C

MY)

€3

u$(dn)c_

y €don( z)

C ( l [ ~E zn €3 [wn) C ([Y E zn 8 nwn)

yEdom(z)

E

gEVP

= u3y (Y E

2

8 4wn.

(b) The proof is by Proposition 2.10 and (a).

0

Let us verify a number of formulas which are intended to be the linear logic counterparts of the classical ZF axioms. For the moment, we do not have any canonical way to translate classical set-theoretical formulas into linear logic. In particular the choice between multiplicative and additive connectives are rather arbitrary. Theorem 3.1. The following formulas are valid in V p .

(Empty Set):

3YVz(zE Y)l.

(Extensionality):

VXVY(!Vu(u E x -0u

E

Y)€3!Vu(uE Y -Ou E X ) -0 x = Y).

(Pair): VuVv3aVz(z = u @ z = o -0 3: E a ) . (Union):

VX3YVu(3z(z E X 8 u E z) 4 u E Y ) .

(Separation):

VX3Y(!Vu(u E Y -0 u E x 8 $(u)) 8 !Vu(u E x €3 $(u)-0 u E Y ) ) . (Collection): Vu((Vz E u)3yd(z,y)

-o

3o(Vz E u)(3y E w ) +(z,y)).

391

(Infinity): 3 Y ( ! 0 p E Y €3!Vx(x E Y -ozu{x} E Y ) ) .

0 p and X U{x} are the elements of V p which will be explained in the proof. Proof. (Empty Set): Let Y E V p be such that dom(Y) = 0. Then, for any x E V p ,we have UvEdom(Y)(Y(w) €3 [[x= w]) = 0. Then

(U

( Y ( v )8 [X =.]I)

vEdom( Y )

Hence, [(x E Y)'] = P and p x ( x E Y ) q = P. Obviously, 1 E P. (Extensionality): Recall f X = Y ] = ! [ X g Y ] ~9 ![Y g X ] . Then the axiom holds by Proposition 3.5.

(Pair): Let a E V p be such that dom(a) = {u,w} with 1 E a(.) and 1 E a(.). Then, 1 E [uE a] and 1 E [w E a ] . Now for any x E V p , we have [x = u]€3 [uE a] g [x E a] so that [x = u] [x E a]. Similarly, [x = u ] c [X E a ] . Hence [X = u @ x = u] = ([x = u]u [X = V])ll E

.]**

=

E

.I.

(Union): Let Y E V p be such that dom(Y) = U { d o m ( z )I z E dom(X)} and for any u E d o m ( Y ) , writing S(u) for { z I u E dom(z) and z E dom(X)},

Y ( u )=

c

( X ( Z >8 z(.)>.

Z€S(U)

Then for any z E dom(X) and u E dom(z), we have X ( z ) €3 z ( u ) C Y ( u ) C [uE Y ] so that X ( z ) C z ( u ) --o [uE Y ] . Hence, by Proposition 3.5, X ( z ) g [Vu(u E z --ouE Y ) ] . This means that 1 E p z ( z E X 4 Vu(u E z --o u E Y ) ) ] .The axiom then follows.

(Separation): Let Y E V p be such that dom(Y) = dom(X) and Y ( u ) = X ( U )€3 [p(u)] for all u E dom(Y). Then Y ( u ) C [uE X €3 p(u)] for all u E dom(Y) so that 1 E [Vu(u E Y -ou E X €3p(u))] by Proposition 3.5. Also X ( u ) €3 [p(u)] = Y ( u ) C [uE Y ] for all u E dom(X) so that X ( u ) g [p(u)] -O [u E Y ] . By proposition 3.5, 1 E E y ) ) ]= pu(. E x €3 p(u) u E y)n. p q u E x --o (p(u)

+,

392

(Collection): Given z E Vp, let

Fz = {S E Factp 139 E Vp([cp(z,y)] = s)} Then F, is a set and (Vs E Fz)3a3y ([cp(z,y)] = s and p ( y ) = a ) . Hence by the Collection principle of ZF, 3 4 V s E F X ) ( 3 aE v)3y ([cp(z,y)] = s and p ( y ) = a ) .

Let

CY, =

U{CY+ 1 I

Q

E Y and

LY E Ord}.

Then

393

(Infinity): We denote the phase-valued set obtained in (Empty Set) by {z, {z}} and z U {z} denote the phase-valued sets obtained by (Pair) and (Union) for now. Define Y E V p in such a way that

0 p . Similarly

dom(Y);

0

0p E

0

if z E d o m ( Y ) , then z U {z} E d o m ( Y ) ; 1E Y(0p); Y ( z )g Y ( zU {z}) for all 2 E dom(Y).

Notice that if p ( z ) = a , then p ( { z } ) = a + l and p ( { z , { x } } ) = a+2. Also, p(z U {z}) = p ( U { z , {z}}) 5 p ( { z , {z}}). Hence, given 0.p E V,”, we can have Y E V,”++w+l.Therefore, Y E V p . Since 1 E Y(0.p)5 [ 0 p E Y ] ,it suffices to show

Now for any z E d o m ( Y ) ,

4. Relating

V F to the Heyting-valued model

Let’s begin with the following observation, which is what is behind the Girard’s second translation [3] of intuitionistic predicate logic into linear predicate logic given as follows.

A* = ! A for A atomic, ( A V B)* = A* @ B*, ( AA B)* = A* 8 B*, ( A 3 B)* = ! (A* 4 B * ) , O* = 0, @A)* = 3zA*. (VzA)* = !Vz A*, Proposition 4.1. Let 0 be the set of all open facts in P . Then 0 is a frame (locale or Heyting algebra) in the sense of Vickers [lo].

394

Proof. The order is given by the set-inclusion. The arbitrary join V Fi is defined as (U F i ) l l . Let {Fi} be a family of open facts. By Propowhere F: are closed facts, so that sition 2.10, (UFi)l* = (UF i ) l l is an open fact since closed facts are closed under arbitrary intersection. The binary meet of the open facts F and G is F @ G, since F @ G = ! F @ ! G = ! ( F n G) by Proposition 2.12. Furthermore the distributivity of the binary meet over the arbitrary join holds by Proposition 2.8. 0 Frames and Heyting algebras are the same structures, although they differ when we consider homomorphisms. Locales are frames together with the set of "points." For our purpose, it is harmless to use those terms interchangeably. Then we can obtain the Heyting-valued universe V o as the subuniverse of V p by restricting facts to open facts in the construction of V p . Definition 4.1. We define V," and V o by the transfinite induction on ordinals a as follows.

v,0=0, 0

0

V s , = {u I u is a function with dom(u) E V," and ran(u) = O } , V p = Ua<XV," where X is a limit ordinal, = Ua€OrdVcuO.

'v

Definition 4.2. A phase-valued set u E V p is static if u E V o . Proposition 4.2. Let all x E v P .

E

V p be static. T h e n [x E u] is a n open fact for

Proof. [x E u]= CzEdom(u)(u(z) @ [x = z ] ) . Since open facts are closed under finite multiplicative conjunction, u ( z ) @ I[x = z ] is an open fact. Furthermore, open facts are closed under infinitary additive disjunction by Proposition 2.10. Hence [x E u]is an open fact. I3

We introduce the restricted quantifications over Vo as follows.

w $ ( ~ ,ul, . . . ,u,)n = I[v.*$(~, ul,.. . ,un)n =

zvEVo I[$(., ul,. . . ,un)n,

nVEvo I[+(., ul,.. . ,un)n.

Proposition 3.5 holds with those restricted quantifiers as well. The proofs are exactly the same.

395

For the counterparts of the power set axiom and H. Friedman’s Einduction [2,6], it seems that we need to use those restricted quantifiers.

Theorem 4.1. The following formulas are valid in V p .

(Static Set): Vx*Vy (y E z -o ! (y E z)). (Static Power Set): Vu*3v*Vz*(!V’y(y E z -o y E u)-o x E w)). (Static €-induction): !Vz*((Vy (y E z -o $(y))

-o $(z)) -o Vz*$(z).

Proof.

(Static Set): This follows from Proposition 4.2. (Static Power Set): Let w E V o be such that dom(w) = {f

I f is static with dom(f)

= dom(u)}

and 1 E w(x) for all x E dom(v). We want to show 1 E pz*(!Vy(y E z -oy E u)-o x E w)]. For this, we define z’ E dom(v) for each x E V o which satisfies

I[!vy(y E

E

-o

= qz

c c iz‘ = .I.

Given such an z’, the validity of the formula immediately follows since 1 E [x’ E w] and !I[. c_ [x‘ = x] [z‘= z] 8 [z’ E .]I [x E w] for all x E vo. The definition is as follows. Given z E V o , let x’ E V o be such that dom(z’) = dom(u) and z‘(y) = [y E z] for all y E dom(z‘). Clearly, 2’ E dom(v). Now for any y E V p ,

c

c

c

C C

[Y E x’n =

( ~ ‘ ( 2 )8

I[ =. Yn)

zEdom(u)

=

(UZ

E zn 8 I[ =. yn)

r Edom( u)

c UY E 4. Hence 1 E [Vy(y E x’ -oy E z)] = [x‘

ly E

8 E

=

c z]. Next for any y E V”,

C w)8 uz = yn 8 b E .]I) zEdom(u)

E

C zEdom(u)

( [ z = y] 8 I[ E. since u ( z ) is open

396

z€dom(u)

They are special consequences of the more general principle. Proposition 4.3. For the static u and v, our definitions of [uE w] and [u= v] in V p yield the same open facts as the Heyting-valued interpretations an vo.

Proof. Since the meet in 0 is the tensor in P and the supremum coincides in both of them, it suffices to confirm that !I[. C v] in the phase-valued model is the same as [u v] in the Heyting-valued model for u , v E V*.

c

397

n

Note that the infimumof open facts Fi in 0 is given by ! Fi. Furthermore ! Gi = ! !Gi holds for any family {Gi}iElof facts in ?. To see this, just notice ! Gi E !Gi for any i E I. Hence we only need to show that !(u(z) -O [z E u]) in P is indeed u(z) 1%E u]in 0. Now F@!(F-G) C G holds for any facts F and G. Suppose F @ H 5 G for open facts F , G and H . Then H C F 4 G and H ! ( F4 G ) since H is open. By the uniqueness of the residual F G, we can conclude that

ni,,

n,,,

n

+

+

! ( F +J G ) = ( F + G).

Since u ( z ) and [z E u]are open facts, the above argument shows that !(u(z)4 [z E u])is the same as u(z) [z E u]. 0

+

Then the formulas in the intuitionistic set theory evaluated in V o retain

the same interpretations under the Girard’s second translation with all the quantifiers modified t o the restricted ones. Furthermore, if the quantifiers are bounded, then there is no need to restrict them due t o Proposition 3.5. We hope to explore this point in more detail in the sequel of this paper. Acknowledgments The early version of this paper is included in my dissertation “71. I thank the anonymous referee for the meticulous and helpful comments.

References 1. M.P. Fourman and D. Scott. “Sheaves and logic.” Application of Sheaves, Springer Lecture Notes in Mathematics 753, 1979, 302-401. 2. H. Riedman. “The consistency of classical set theory relative to a set theory with intuitionistic logic.” The Journal of Symbolic Logic 38, 1973, 315-319. 3. J.Y. Girard. “Linear logic.” Theoretical Computer Science 50, 1987, 2-102. 4. J.Y. Girard. “Linear logic: Its Syntax and Semantics.” Advances in Linear Logic, (eds.) Girard, Lafont, Regnier, London Mathematical Society Lecture Notes Series 222, Cambridge University Press 1995, 1-42. 5. T.J. Jech. Set Theory, Academic Press, New York, 1978. 6 . A. SEedrov. “Intuitionistic set theory.” Harvey Friedman’s Research on the Foundations of Mathematics, Studies in Logic and the Foundations of Mathematics Vol. 117, North-Holland, 1985, 257-284. 7. M. Shirahata. Linear Set Theory, dissertation, Department of Philosophy, Stanford University, 1994. 8. G. Takeuti. ”Quantum set theory.” Current Issues in Quantum Logic, Plenum, New York, 1981, 303-322. 9. G. Takeuti and W.M. Zaring. Asiomatic Set Theory, Springer, New York, 1973. 10. S. Vickers. Topology Via Logic, Cambridge University Press, 1989.

398

A PROBLEM ON THEORIES WITH A FINITE NUMBER OF COUNTABLE MODELS

AKITO TSUBOI Institute of Mathematics, University of Tsukuba, Ibaraki 305-8571, Japan E-mail: [email protected] In this paper we discuss non-w-categorical theories with a finite number of countable models. The question remains open whether such theories should be unstable or not. We briefly explain known results concerning this question, and discuss related topics.

1. Introduction In this paper we discuss the following problem and related topics.

(*) Is there any non-w-categorical stable theory T with a finite number of countable models? Nowadays it is widely believed that there exists such a complete theory. However, in the author’s opinion there are not so many works aiming for constructing such theories. Many authors have proved the non-existence of such theories under additional finiteness conditions. (See [8],[3],[5],[12]and [19].) Such finiteness conditions are, for example, superstability, admitting finite coding, supersimplicity and so on. Superstability is a finiteness condition on the length of forking sequences of types. Admitting finite coding is a finiteness condition on the size of canonical bases. Unfortunately, without these assumptions, very few things are known. Since the instability is equivalent to the order property (existence of order structures in a very weak sense), (*) can rewritten as:

(**) Does any theory T with a finite number (> 1) of countable models have the order property? In fact, in [12],[19]and [4],they found definable order structures in theories with finitely many countable models (under some additional finiteness

399

conditions). In section 1, we recall some examples of non-w-categorical theory with a finite number of countable models. We also recall some basic facts for these theories. For the reader’s convenience, outline proofs will be given. In section 2, we consider theories with three countable models. By Vaught’s result,. non-w-categorical theories have at least three countable models. If a given theory is not small, of course it has infinitely many models. If T is small, there are at least three countable models: a prime (and atomic) model over 0, a prime (and atomic) model over a finite tuple realizing a non-principal type, and a countably saturated model. In [4],by assuming the almost w-categoricity of T , the existence of dense linear order in T was shown. A slight generalization of this fact will be given. In section 3, we discuss Lachlan’s theorem ([8]) and it’s generalizations. The theorem states that there is no superstable theory T with 1 < I ( w ,T ) < w . Besides Lachlan’s original proof, there are several other proofs (see [9],[14] and [15]). In these newer proofs, in particular in [9], the open mapping theorem (or a weaker version of it) seems to have an important role. In a simple unstable theory, the open mapping theorem does not hold in general. But Kim [5] showed that Lachlan’s theorem can be generalized t o supersimple theories. In (201, a restricted version of the open mapping theorem was shown for simple theories. We give a proof of Kim’s result using this restricted version. In this paper, T denotes a complete theory formulated in a countable language. I ( w , T ) denotes the number of nonisomorphic countable models of T . Models of T are denoted by M ,N , .... We fix a sufficiently saturated model of T . Usually we work in this model. A , B , .. will denote subsets of this model. Finite tuples of elements in this model are denoted by a , b, .... We write AB for denoting the set A U B. Finite tuples of variable are denoted by x,y, .... Types are complete types unless otherwise stated. S(A) denotes the set of all types over A. If p is a type, p M denotes the set of all realizations of p in M .

2. Examples and Basic Facts. As is well-known, w-categorical theories T are characterized by the property that for each finite tuple x of variables, T has only finitely many types in x. Such a good characterization is not known for theories with 1 < I ( w ,T ) < w . First we recall basic facts.

400

Fact 2.1. (1) Let I(w,T) 5 w. Then T is small, i.e. S(0) is countable. So f o r each finite set A there is a prime model over A. There is also a countably saturated model of T . (2) (Vaught) IfI(w,T) > 1 then I(w,T) 2 3.

Proof. (1) Each type in S(@)is realized in some countable model. On the other hand, each countable model realizes only countably many types. So we have (S(0)(I II(w, T ) ( w. (2) We can assume 1 < I(w,T) 5 w. So there are a prime model MO and a countably saturated model M2. Let a realize a non-principal type and let M I be a prime model over a. Then easily we have M I Mo, M z o

+

The most well-known and fundamental example with three countable models is the following one due to Ehrenfeucht.

Example 2.1. Let T = Th(Q,<, 0,1, ...). Then I ( w , T ) = 3. Other than the standard model (Q,< 0,1, ...), there are two nonstandard models M I and M2. M I has the nonstandard part { u E M I : a > 0 , a > 1,...} with the minimum element, while the nonstandard part of MZ has no minimum element.

If we want to have a theory T with I(w,T) = n(> 3), we only have to prepare n - 3 new unary predicates U1,...,Un--9 with the properties (i) the interpretations of these predicates give a partition of (Q,<, 0,1, ...) and (ii) each predicate is a dense subset of (Q, <, 0,1, ...). (See [2].) There is also an example with a dense tree structure.

Example 2.2. Let M = (M, < , A ) be a dense w-branching tree with the meet operator A. Let {ci : i < w} c M be a strictly increasing sequence. Then the theory of (M, <, Q, c1, ...) has three countable models. Miller [lo] gave a series of examples using such tree structures. The two examples above are constructed from unstable w-categorical theories by adding infinitely many constants. By the following fact we see that we cannot construct a non-w-categorical stable theory with a finite number of countable models using a similar construction to that mentioned above.

Fact 2.2. ([19]) Let T be a complete theory with 1 < I(w,T) < w. If any reduct of T to a finite language is w-categorical, then T is unstable, in fact it has the strict order property.

401

All the examples given above have infinite languages. However there is a complete theory T in a finite language with 1 < I ( w , T ) < w . Example 2.3. Let L = {+}, where 4 is a binary predicate symbol. Let T be the theory of the following structure.

(1) 4 is a preorder of the universe. The associated ordered set is isomorphic to the rational numbers Q. (2) For each n, let X , be the set of all classes having 5 n elements. Each X , has the maximum element (class), and {X, : n < w } is a strictly increasing sequence of initial segments of the preordered set.

For the same reason as in Example 2.1, we have I ( w , T ) = 3. Even though this example has a finite language, it @-interpretsthe theory of Example 2.1. Concerning extensions of a theory by constants, there are several results. Fact 2.3.

( I ) (Millar [lo]) There is a theory T with infinitely m a n y countable models such that some extension of T by a constant has only finitely m a n y countable models. (2) (Peretyat’kin [ll]) There is a theory T with three countable models such that any extension of T by a constant has infinitely m a n y countable models. According to Pillay [14], we will say that a type q(x) = tp(a/b) is semiisolated if there is a formula p(x, b) E q(z) such that p(x,b) -/ tp(a). In [13], he says a semi-isolates b if tp(a/b) is semi-isolated in the above sense. Notice that the relation on tuples given by semi-isolation is a preorder. Fact 2.4.

(1) (Benda [l])If 1 < I ( w , T ) < w , then there is non-principal type p ( x ) E S(0) such that whenever a model realizes p then it realizes all types in S(0). Such a type p is called powerful. (2) (Pillay [14]) Let p ( x ) be a powerful type. Then we can find two realizations a and b such that (i) tp(a/b) is semi-isolated and (ii) tp(b/a) is not semi-isolated.

402

Proof. (1) Suppose that there is no powerful type. Then we can inductively choose an increasing sequence of complete types {pi(xi)}iEu and a sequence of countable models {Mi}iEwsuch that Mi realizes pl, . . . , p i but does not realize pi+l. Then Mi’s are mutually non-isomorphic. (2) Let a1 be any realization of p . By compactness, we can choose a2 p such that tp(a2lal) is not semi-isolated. Let a3 be another realization of p and M a prime model over a3. Since p is powerful, we may assume that a1a2 C M . Then tp(aila3) is semi-isolated, whereas tp(aa/al) is not semi-isolated. 0 3. Theories with three countable models.

A model is called weakly saturated if it realizes all types in S(0). If I ( w , T ) = 3, then the three countable models are a prime model, a weakly saturated (non-saturated) countable model and a countably saturated model. (See [all.) Theories with exactly three countable models have strong properties, which are not expected for those with more than three countable models (see facts below). In this section, we assume I ( w , T ) = 3 unless otherwise stated. The following two facts are easy to verify.

Fact 3.1. Every non-principal type is powerful. In other words, non-prime models are weakly saturated. Fact 3.2. L e t p ( x ) E S(0) be a non-principal type and M a model. If f o r any realization a E p M there is a realization b E p M such that tp(b/a) is n o t (semi-)isolated, then M i s saturated. Definition 3.1. We will say that T is almost w-categorical if for any types pl(xl), . . . , p n (xn) E S(0), pl(x1) U...Up,(x,) has afinite number of completions. All known theories with a finite number of countable models interpret a dense linear order. We don’t know whether there is a theory T with 1 < I ( w , T ) < w such that T does not interpret a dense linear order. However, with the assumption of the almost w-categoricity, we know the following:

Fact 3.3. ([4]) If a theory T with three countable models i s almost w categorical, then T interprets a n infinite dense linear order using parameters. Here we prove a slightly stronger result:

403

(*) Let T be an almost w-categorical theory with 1 < I ( w , T ) < w . If every weakly saturated (and non-saturated) model is prime over a finite set, then T interprets an infinite dense linear order using parameters (cf. Fact 3.2). Proof. As in [4], the denseness follows easily. So we prove the existence of an infinite linear order. Let M I ,..., M , be the list of all weakly saturated non-saturated models modulo isomorphisms. For each i, choose a tuple ai of elements in Mi such that Mi is prime over ai. We may assume that all ai's have the same length. Notice that p i = tp(ai) is a powerful type. Let M be a countably saturated model and D the set Uii,p?. By the almost w-categoricity and the fact that T is small, there are formulas pi($) E pi(z) (i 5 n) and a binary formula z 5 1~ such that

(1) a 5 b w tp(b/a) is semi-isolated, for any a, b E D; (2) p i ( z ) is the unique non-principal type extending pi(z) (i 5 n), In general 5 is a preorder on a definable set extending D. Modulo the equivalence relation 2 5 y 5 z, we have the associated order. For simplicity, we may assume that 5 is an order from the first. Let a E D. We show that the set defined by {z 5 a} U p ( z ) is linearly ordered by 5. Assume otherwise. Then there are two elements b, d E D with (i)b, d 5 a, (ii)b $ d and (iii)d f b. So in a prime model over ad, we can find b' 5 a with b' $ d and d b'. But b' does not realize any pi(x), since otherwise we would have b' 2 d. So, by the condition (2) above, we can assume that b' realizes a principal type. Since each pi is a powerful type, we can choose e having the same type as b' such that e <_ D, i.e. e <_ z for any z E D. For each i 5 n, let I'i(z) be the following set of formulas: pi($) U {z

zf a : a E D}.

Since tp(e) is an isolated type, I'i(z) cannot be implied by a single formula over {e}UD. (Use the almost w-categoricity.) So there is a countable model M* 3 { e } U D that omits each I'i(z). So e 5 u p ? ' . M * is weakly saturated, since it realizes powerful types p l , ...,p,. Moreover, each p?' has no minimal element with respect to 5. So M* cannot be isomorphic to neither of the Mi's, hence M* is a saturated model by our assumption. Since M* is saturated, there must be an element d' E M * with tp(ed) = tp(ed'). Then we have that e and d' are not comparable. This is a contradiction. 0

If an L-theory T with I ( w , T ) = 3 is almost w-categorical, then any extension of T by finitely many constants has finitely many countable models.

404

This can be seen as follows. Let T, be any complete extension of T by the constants c and p ( z ) the L-type of c. ( p ( z ) is assumed t o be a powerful type.) By the almost w-categoricity, there are only finitely many (say n ) completions of q(s) U q ( y ) . By way of contradiction, assume that there are non-isomorphic countable models M I , ...,Mn+2 of T,. If the L-reducts MilL and MjIL are saturated, then they are isomorphic as T,-models. So we may assume that MIIL,...,MnIL are all weakly saturated. So there are di (i = 1,..., n) such that each MilL is atomic over di. Indeed, each MilL is atomic over cM;di. By our choice of n, there are i # j with tp(cMidi)= tp(cMjdj). Then Mi and Mj are isomorphic, a contradiction. So the theory constructed in [ll] is an example of non almost wcategorical theory with three countable models. However the theory constructed in [ll]interprets a dense binary tree, so it interprets a dense linear order (using parameters). 4. Stability, Simplicity and Countable Models.

In early 70’s Lachlan [8] showed that there is no superstable theory T with 1 < I ( w , T ) < w. His proof uses his Rank, which assigns an element of ww to each formula. Besides Lachlan’s original proof, there are several other proofs. In [9] Lascar proved a version of the open mapping theorem for superstable theories. (The open mapping theorem will be explained below.) Using it, he gave a very nice proof of Lachlan’s result. Shelah introduced the notion of weight, and gave another proof of Lachlan’s proof (see [IS]). Pillay introduced the notion of semi-isolation and gave a very short proof (see [14]). The proofs in [16] and [14] do not use the full strength of superstability. In fact, the following condition (FW) (a finiteness condition for weight) is sufficient. Since the open mapping theorem holds for any stable theory, Lascar’s proof can also be done under (FW). (FW) Let I be an A-independent set with a L Ab for all b E I. Then I is finite. Lachlan’s result stated above has been strengthened in many ways. In the following, we explain some such results. In [3] Hrushovski showed that if T is small (i.e. IS(@)lis countable) and T admits finite coding (i.e. every global type is based on a finite set) then any type has a finite weight in the sense of (FW) above.

Fact 4.1. ([3]) Let T be a stable theory such that every global type is based o n a finite set. T h e n T is w-categorical, or T has infinitely m a n y countable

405

models. The open mapping theorem for a stable theory states that for RAE = { p ( a ) E S(B) : p ( z ) does not fork over A } with A c B , the restriction map p E RAB ++ plA is an open mapping in the Stone topology. The following (OM) can be considered as a version of the open mapping theorem. Pillay’s proof in [14] uses (OM).

(OM) If tp(a/b) is semi-isolated and tp(a) is not isolated then a and b are dependent.

(OM) holds for stable theories and can be easily deduced from the open mapping theorem. Also, it can be proven directly, using the following characterization of independence: tp(a/b) does not fork over 0 iff tp(a/b) is finitely satisfiable in any model M 2 b. Unfortunately this characterization is not true for simple theories in the sense of Shelah [16]. The following example given by Kim illustrates the situation. Example 4.1. Let M be the { E ,R, C O , c1, ...}-structure defined by: (i) E is an equivalence class with two classes. Each class is infinite. (ii) For any two disjoint finite sets A and B contained in one class, there is a point d from the other class such that each point in A is R-related to d and no point in B is R-related to d. (iii) No two points in the same class are R-related. (iv) ti's are distinct elements contained in one class. Choose a 6 {ci : i < w } from the class containing the ti's. Choose b that is R-related to a but not R- related to any elements from {ci : i < w } . Then tp(a/b) is semi-isolated by R(a, b), but tp(a) is not isolated. Note that a and b have different types. However Kim succeeded to prove a supersimple version of Lachlan’s theorem without using (OM).

Fact 4.2. ( [ 5 ] ) Let T be a supersimple theory. T h e n T i s w-categorical, o r T has infinitely m a n y countable models. For proving his theorem, instead of using (OM), Kim showed the following fact for simple theories:

(*) Suppose that a and b are two independent realizations of a given type. Then tp(a/b) is semi-isolated if and only if tp(b/a) is semiisolated. However, examining his proof of the fact above, in fact we can show

(OM) if a and b have the same type (see Fact 4.3). The following ter-

406

minology is used in Fact 4.3. Let K be an infinite cardinal. We will say that a (partial) type is n-isolated over A if the type is implied by a consistent set of L(A)-formulas of cardinality < n. If p ( z ) is a complete type over A, p ( x ) will be called n-isolated if it is n-isolated over A. A complete type p ( x ) will be called (6, A0)-semi-isolated if there is a subtype q ( x ) with 1q(x)1 < 6 such that q ( x ) proves plA0. In this case we also say that q ( x ) (n,A)-semi-isolates p ( x ) . In the remainder of this section, T is simple.

Fact 4.3. ([20]) Let p ( x ) E S(A) be a non-n-isolated type. Let a and b be two realizations of p ( z ) such that tp(a/Ab) is (6, A)-semi-isolated. Then a and b are dependent over A.

Remark 4.1. Using the independence theorem for simple theories, we can show a little bit stronger result: Let p ( z ) E S(0) be a type such that p ( x 1 )U . . . Up(x,) has a finitely many completions. Let n 1 elements bl, ..., b,, a be independent realizations of p ( x ) . Suppose moreover that b l , ..., b, have the same Lascar strong type. If tp(a/bl, ..., b,) is semi-isolated then tp(a) is isolated

+

Proposition 4.1. Let [A]5 n. Let p ( x ) E S(A) be a non-6-isolated type. (1) Let I be a finite Morley sequence of p ( x ) . Then there is a model M 3 A in which I is a maximal Morley sequence over A. If n = No, we can find such a model even for a Morley sequence of infinite length. (2) Suppose that T is supersimple. Let a realize p ( x ) . Then there is a model M 3 Aa with dimN(p) = 1 (i.e. any two realizations of p ( x ) in M are dependent over A). (3) Let I = {ai : i E w} be a Morley sequence of p ( x ) . For each n E w there is a model M 3 A U {ai : i < n } that has no indiscernible sequence {bi : i < an} over A with tp({ai : i < n}/A) = tp({bi : i < n}/A). (4) 051) There is no supersimple theory T with 1 < I ( w , T ) < w. Proof. (1). By Theorem 2.2.19 in [2], it is sufficient to prove the following statement by induction on n 2 1: (*) If {ai : i 5 n} is a Morley sequence of p(x), then r(z) = {{ai : i 5 n} U { x } is a Morley sequence} is not 6-isolated. . Suppose that r ( x ) is 6-isolated. Let b realize r ( x ) . Then both b and a, realize the type q ( x ) = tp(a,/A, ao, ..., an-l). By the induction hypothe-

407

sis, q(z) is not K-isolated. On the other hand, tp(b/A, ao, ...,a,-l, a,) is ( K , (A, ao, ...,a,-1))-semi-isolated. So by Fact 4.3, b and a, are dependent over A, ao, ..., a,-1, contradicting the fact that {ai : i 5 n } U { b } is a Morley sequence. (2). Let A ( q ) be the following set of formulas:

p ( z )Up(y) U {z and y are independent over A}. Suppose that A(zy) is K-isolated over Aa. Then there are two realizations bo and bl such that (i) tp(bi/Aa) is ( K , A)-semi-isolated (i = 0 , l),and (ii) bo and b l are independent over A. From this, using a usual method, we can easily construct an independent (over A) sequence { b i : i = 1,2, ...} such that each tp(bi/Aa) is ( K , A)-semi-isolated. By Proposition 4.3, each bi and a are dependent over A. This contradicts the supersimplicity of T. So A(zy) is not K-isolated over Aa. Thus there is a model N 3 Aa which omits A(xy). (3). Clear by part (2). (4). We assume that T is small and non-w-categorical. Let p ( z ) be a nonprincipal type. Let {ai : i E w } be a Morley sequence of p . Let M , be a prime model over {ui : i < 2,). Then, by part (3), the M,’s are mutually 0 non-isomorphic.

Question 4.1. Is the assumption of supersimplicity necessary in part (2)? 5. An approach by Sudoplatov. Sudoplatov [17] used his geometric object called a polygonometry in a n approach to constructing a stable theory T with 1 < I ( w ,T ) < w . Roughly speaking, a polygonometry is a triple (G, (P,L , E), go) where G is a group, (P,L , E) is a pseudoplane and go is a fixed element in G. G is used to measure both the distance between two points in P and the angle between two lines in L. A trigonometry is a special kind of polygonometry such that any n-gon is expressed by a joint of 3-gons. He defines a certain language and considers a trigonometry (more precisely, the set P of points) as a structure for this language. He is trying to construct a stable theory T, with I ( w , T,) = n by applying Hrusovski’s generic construction method to his trigonometries. So far he has not obtained a complete counterexample, but his object seems to be a good’candidateof a tool for constructing such examples.

408

References 1. M. Benda, Remarks on countable models, Fund. math. 81 (1974), no. 2, 107-119. 2. C. C. Chang and H. J. Keisler, Model Theory 3rd ed., North-Holland, 1990. 3. E. Hrushovski, Finitely based theories, The Journal of Symbolic Logic, vo1.54 (1989), 221-225. 4. K . Ikeda, A. Pillay and A. Tsuboi, On theories having three countable models, Mah. Log. Quart. vol. 44 (1998), 161-166. 5. B. Kim, On the number of countable models of a countable supersimple theory. J. London Math. SOC.(2) 60 (1999), no. 3, 641-645 6. B. Kim, A note on Lascar strong types in simple theories, J. Symbolic Logic 63 (1998), no. 3, 926-936. 7. B. Kim and A. Pillay, Simple theories, Annals of Pure and Applied Logic, V O ~ .88 (1997), 149-164. 8. A. H. Lachlan, On the number of countable models of a countable superstable theory, Logic, methodology and philosophy of science IV (Proceedings, Bucharest 1971), North-Holland, Amsterdam (1973), 45-56. 9. D. Lascar, Ranks and definability in superstable theories, Israel Journal of Mathematics, vol. 23 no. 1(1976), 53-87. 10. T. Millar, Finite extensions and the number of countable models, The Journal of Symbolic Logic, vol. 54 (1989), 264-270. 11. M. G. Peretyat’kin, Theories with three countable models, Algebra i Logica, V O ~ .19 (1980), 224-235. 12. A. Pillay, Instability and theories with few models, Proc. Amer. Math. SOC. vol. 80 (1980), 461-468. 13. A. Pillay, Countable models of stable theories, Proceedings of American Mathematical Society 89 (1983) 666-672. 14. A. Pillay, An introduction to stability theory, Clarendon press, 1983 (Oxford logic guides:8). 15. S. Shelah, Classification Theory (2nd edition), North-Holland, 1990. 16. S. Shelah, Simple unstable theories, Annals of Mathematical Logic 19 (1989), pp. 177-203. 17. S. V. Sudoplatov, Group polygonometries and related algebraic systems (an informative survey), Contributions to General Algebra 11. Klagenfurt: Verlag Johannes Heyn (1999), pp. 191-210. 18. S. V. Sudoplatov, w-stable trigonometries on a projective plane, Siberian Advances in Mathematics, vol. 21 no. 4 (2002), pp. 1-28 19. A. Tsuboi, On theories having a finite number of nonisomorphic countable models, The Journal of Symbolic Logic, vol. 50 (1989), 806-808. 20. A. Tsuboi, Isolation and dependence in simple theories, in Proceedings of Model Theory at St. Catherine’s College Kobe Institute (1998). 21. R.L. Vaught, Denumerable models of complete theories, Infinitistic methods: proceedings of the symposium on foundations of mathematics, Warsaw, Pergamon Press (1961), 303-321.

409

PROBABILISTIC LOGIC PROGRAMMING WITH INHERITANCE*

JIE WANG

't3,

SHIER JU1 , XUDONG LUO 1,2 AND JUELIANG HU

Institute of Logic and Cognition, Zhongshan University, Guangzhou 510275, P. R. China Email: hspOOwjQstudent.asu.edzl.cn, [email protected] Department of Electrics and Computer Science, University of Southampton, Highfield, Southampton SO1 7 lBJ, United Kingdom Email: [email protected] Department of Philosophy, Beijing Normal University, Beijing, 100875, P.R. China School of Faculty of Science Zhejiang Institute of Science and Technology, Hangzhou 310033, P.R.China Email: hjlQzist.edu.cn

The paper proposes a new knowledge representation language that extends our probabilistic logic programming language [29], by using notation of inheritance. By introducing the mechanism of inheritance into the language, default reasoning with exceptions can be naturally represented but no inconsistent conclusions will be drawn. We illustrate these by encoding some non monotonic problems in the extended language. Its declarative model-theoretic semantics is developed, which is shown to generalise the answer sets semantics of probabilistic logic programs. We also analyse its complexity and show that inheritance does not cause any more computational overhead (i.e., its reasoning has exactly the same complexity as that in the probabilistic logic programming [29]).

'this work is supported by the key research project of Chinese ministry of education under grand no. 09050-3142003.

410

1. Introduction

As an important formalism for reasoning with classical knowledge, logic programming [14,1] started in the early 1970’s [12] based on earlier work in automated theorem proving, and began to flourish especially with the spreading of PROLOG. Now logic programming becomes a well-established knowledge representation and reasoning formalism in artificial intelligence and deductive databases. Further, since many applications in practice require knowledge representation and reasoning system to be able to deal with uncertainty, many efforts [21,22,23,24,5,15,16,17,18]have been made for integrating logic programming frameworks and probability-based representation and reasoning formalisms. Probabilistic logic programs are now widely recognized as a valuable tool for knowledge representation and commonsense reasoning of probabilistic information. In [29], we also presented a probabilistic logic programming language. In particular, we extend the answer set semantics of Gelfond and Lifschitz [7] by associating a probability with each atom in a program in this language. However, sometimes probabilistic inconsistencies can generate in this framework. For instance, consider the famous nonmonotonic reasoning example: 80% of all birds can fly while penguins do not fly. Assume that our knowledge about a particular individual, called tweety, is that “tweety is a bird” and “tweety is a penguin”, we conclude “tweety can fly with the possibility 80%” and “tweety can not fly” as well. This is inconsistent. In order to remove this kind of inconsistence, this paper integrates the technique of reference-class reasoning [28,13,26] into our probabilistic logic programming language [29]. That is, to take the following ideas behind reference-class reasoning into our language: any class containing the particular individual can be considered as reference class, and the smaller reference classes are preferred to larger ones. More precisely, this paper proposes an extension of our probabilistic logic programming language [29] by adding some machinery for inheritance with overriding from default reasoning, denoted PLP<. That is, a subclass inherits all properties from its superclass, but a subclass may refine some of the inherited properties and introduce extra definitional properties local to itself. Possible probabilistic inconsistencies are resolved in favor of the rules which are “more specific” according to the inheritance hierarchy. In this way, a direct and natural representation of default reasoning with exceptions is achieved. It turns out that such an approach can be developed as a probabilistic generalization of classical default reasoning.

41 1

The rest of the paper is organized as follows. In Sections 2 and 3, we formally define our PLP< language based on probabilistic logic programming [29], and provide a declarative model theoretic semantics of PLP<. Section 4 illustrates the knowledge modelling features of the language by encoding classical nonmonotonic problems in PLP<. In Section 5 , we analyse the computational complexity of reasoning over PLP< programs. Section 6 discusses the relate work. Finally, Section 7 summarises the paper and pout out the direction of further research. 2. Syntax of PLP<

Let q5 be a first order vocabulary that contains a finite set of predicate symbols and finite set of variable symbols. Let Q be a set of object constants and ,B be a set of probabilistic constants. Object constants represent elements of a certain domain, while probabilistic constants represent real number in the unit interval [0,1]. A term is either a variable or an object constant. An atom is a construct of the form A(t1,.. . ,tn),where A is a predicate of arity n in q5 and t l , . . . , tn are terms. In addition, in PLP< language, we define a finite partially ordered set of symbols (A, <), where A is a set of strings, called object identifiers, and < is a strict partial order (i.e., the relation < is: (i) irreflexive, c { c, VCE A; and (ii) transitive, (u < b) A ( b < c ) (a < c ) , Vu, b, c E A). In order to manipulate probability information, we introduce a new notation:

*

Definition 2.1. A special literal patom is an expression of the form L / p , where L is an atom, and p E [0,1] is the probability that L occurs. Intuitively, when p = 1, L/1 means L is true (we abbreviate L / 1 by L ) ; when p = 0, L/O means 1 L (i.e., L is false); and when p E [0,1], L / p means L probably occur (i.e., L is probabilistic true). Thus, if toss is a unary predicate in our language, toss(head)/0.5 means that the probability that a tossing a coin yields head is 0.5. Definition 2.2. A rule

T

is an expression of the form:

LO/PO + L I / P I ,.. . , L m / ~ mnot , Lm+l/~rn+l,.* . ,not Ln/Pn,

(1)

where n 2 rn 2 0; each Li is an atom; 0 _< pi _< 1, and Li/pi (0 5 i _< n) is a patom; not is a connective called negation as failure or default negation, and not L / p means there is no reason to believe that the probability that L occur is p E [0,1]. The expression of the form LO/po is the head of

412

r. L l l p l , . . . ,L,/p, is called the positive part of the body of r and not L,+llp,+l,. . .,not L J p , is called the negation as failure part of the body of r. We often denote the sets of patom appearing in the head, in the positive part of the body, and in the negation as failure part of the body of a rule r by Head(r),Body+(r)and Body-(r), respectively. So we abbreviate rule (1) by Head(r) t Body+(r),Body-(r).

(2)

The intuition of the above rule is: if the probability that Li is believed true is pi ( 1 i m) respectively, and have no reason to believe in L,+I,. . . ,L , with the probability p m + l , . . ., p n respectively, then the probability Lo is believed true is PO. In the context of probabilistic logic programming with inheritance, there are two major kinds of negation: the first one is classical negation, given that the probabilistic of an atom L is p, it is easy to verify that the probability of E , the classical negation of L is 1- p, the second kind of negation is default negation not L.

< <

Definition 2.3. An object o is a pair < oid(o),C(o) >, where oid(o) is an object identifier in A and C ( o ) is a (possible empty) set of rules. A knowledge base on A is a set of objects, one for each element of A. The relation < induces a partial order on program II in the obvious way, that is given oi = (oid(oi),C ( o i ) ) and oj = (oid(oj),C ( o j ) ) ,oi < o j , iff d d ( o i ) < oid(oj) (read “oi is more specific than o j ” ) . Informally, a knowledge base can be viewed as a set of objects embedding the definition of their properties specified through probabilistic logic rules.

Definition 2.4. Given a knowledge base k and an object identifier o E A, the PLP< program for o on k is the set of objects II = {(o‘,C(o’)) E k I o = 0‘ or o < 0’). Thank to the inheritance mechanism, a PLP< program II for an object o incorporates the knowledge explicitly defined for o plus the knowledge inherited from the higher objects. If a knowledge base admits a bottom element (i.e., an object less than all the other objects, by the relation <), we usually refer to the knowledge base as “program”. Since it is equal to the program for the bottom element. Moreover, we represent the transitivereduction a of the relation < on the object. In order to represent the a(a,b) is in the transitive-reduction of

< iff a < b and there is no c such that a < c and

413

numbership of a pair of objects (resp., object identifiers) ( 0 2 , o l ) to the transitive-reduction of < we use the notation 0 2 : 01 , and say that 0 2 is a sub-object of 01.

Definition 2.5. A term, an atom, a p-atom, a rule, or a PLP< program is ground if and only if it does not contain any variable symbols. Example 2.1. Consider the following program 11: (PhD-student)

{get-PhD(Jane)/0.8 t PhD-student( Jane), not master-student (Jane), PhD-student (Jane)10.9 t} oz(Jane) : ol(PhD-student) {get-PhD(Jane)/O t, has-publication( Jane) t PhD-student( Jane)}

01

Clearly, II consists of two object 02 and 01 , 0 2 is a sub-object of 01. Since Jane is just probably a PhD student, it is possible that she is a bachelor student. If she is a a bachelor student indeed, it is impossible for her to get a PhD. So, the above program is reasonable. 3. Semantics of PLP<

Suppose that a knowledge base k is given and an object o has been fixed. Let II be a PLP< program with respect to o on k. The universe an of II is the set of all object constants and ,On is the set of all probabilistic constants appearing in the rules. The basic base bn of II is the set of all possible ground atoms constructible from the predicates appearing in the rules of II and the object constants occurring in an. For an arbitrary set S , its power set exists and is the set of elements T ( S )= {z 1 z C S } .

Definition 3.1. For an arbitrary set S and its power set T(S). If A E T ( S ) , product of the set A is the product of all elements which belong to A, denoted IAl. Product set of S is

4 s )= (1-41 I A E 491.

c < b.

(3)

414

The em base bn of II is the set of all possible ground p-atom constructible from the atoms appearing in the basic base bn and the probabilistic constants occurring in J ( ~ u ) Note . ~ that, the Base of a PLP< program contains all possible combination of the basic base bn and J ( p n ) . Given a rule r occurring in II, a ground instance of r is a rule obtained from r by replacing every variable X in r by o ( r ) , where o is a mapping from the variables occurring in r to the object constants in the rules occurring in an. We denote by grovnd(II) the finite multiset of all instances of the rules occurring in II. The reason why grovnd(II) is a multiset is that a rule may appear in several different objects of II, and we require the respective ground instances be distinct. Hence, we can define a function obj- of from ground instance of rules in g r m n d ( I I ) onto the set A of the object identifiers, associating with a ground instance F of r (i.e., the unique object of T).

Definition 3.2. A subset of ground patom in II is said to be consistent if whenever p-atom of the form L / a and L i b are in it simultaneity, then a = b. An interpretation I is a consistent subset of Bn. Definition 3.3. Given an interpretation I E Bn, if L / p E I holds (denoted I k L i p ) , a ground patom L i p is true w.r.t. I; otherwise, L i p is false w.r.t. I. Definition 3.4. Given a rule r E g r m n d ( I I ) , the head of r is true in I if Head(r) E I . The body of r is (probabilistic) true in I if (i) every patom in Body+(r) is true w.r.t. I , or there exist patom L / 1 in Body+(r) and L / l E I , but 3p E ( O , l ) , L / p E I ( 1 5 i 5 m ) ; and the other p-atom in Body+(r)is true w.r.t. I ; and (ii) every p-atom in Body-(r) is false w.r.t. I. Definition 3.5. Given a rule r E grovnd(II),rule r is satisfied in I if either the head of r is true in I or the body of r is not true in I . Definition 3.6. Given a rule r E ground(II), Head(r) = Lo/po, rule r is probabilistic satisfied if (i) the body of r is (probabilistic) true in I , without loss of generalisation, assume L i / l , . . . ,L j / l E Body+(r) and Lilai,. . . , L j / a j E I (ah # 1 , k = i,. . . , j ) ; (ii) every atom in Body+(r)is probabilistic independent of each other; and (iii) Lo/(po x ai x . . . x a j ) E I. bThis is because the element of /3n belong to [0, 11, so all element of J(j3n) also belong to [O, 11.

415

Definition 3.7. Two ground rules r1 and 7-2 are inconsistent on L if L / a is the head of rule T I and L/b is the head of rule r2 but a # b. In particular, two ground rule r1 and 1-2 are conflict on L if L / 1 is the head of rule r1 and L/O is the head of rule r2. Next we introduce the concept of a model for a PLP< program. Unlike in traditional logic programming, the notion of satisfactory of rules is not sufficient for this goal because it does not take into account the present of explicit inconsistency. Hence, we first present some preliminary definitions.

Definition 3.8. In an interpretation I , for two arbitrary ground rules q , r 2 E ground(II), suppose that L / a is the head of rule 7-2. Then we say that T I overrides 7-2 on L in I if (i) obj-of(r1) < o b j - o f ( r ~ )(ii) , 3b E [0, 11, L / b E I ( a # b), and (iii) the body of r2 is (probabilistic) true in I . A rule r E ground@) is overridden in I , if for the head L / a of r there exists r1 in ground(II) such that r1 overrides r on L in I . Intuitively, the notion of overriding allows us to solve inconsistent or conflict arising between rules with inconsistent even consistent head. For instance, suppose that both L / a and L / b ( a # b ) are derivable in I from rules r and r’, respectively. If T is more specific than T ‘ in the inheritance hierarchy, then r’ is overruled meaning that L / a should be preferred to L / a because it is derivable from a more trustable rule.

Example 3.2. Consider the program IT of Example 1. Let I = {get-PhD(Jane)/O,has-pubZication(Jane)/O.S, PhD-student(Jane)/0.9} be an interpretation. Rule

get-PhD(Jane)/O c in the object

02

overrides rule

get-PhD( Jane)/0.8 t PhD-student( Jane), not master-student(Jane) in

01

on the atom get-PhD(Jane) in I .

Example 3.3. Consider the program 01

(PhD-student)

oz(Jane) : 01

IT0

{get-PhD( Jane)/0.8 t PhD-student( Jane), not master-student( Jane), PhD-student(Jane)/0.9 t} (PhD-student) {get-PhD(Jane)/0.8t, has-publication( Jane) t PhD-student( Jane)

416

Let I = {get-PhD(Jane)/0.8, has-publication( Jane)/O.S, PhD-student(Jane)/0.9}, the first rule, rl, of 01: and the first rule, 7-2, of o2 have the same head get-PhD(Jane)/0.8, because the bodg+(rl) of is (probabilistic) true in I . So inconsistency generates. Rule 7-2 overrides rule 7-1 on the atom get-PhD(Jane) in I . Definition 3.9. Let I be an interpretation for II. I is a model for II if each rule in ground(Il) is satisfied, probabilistic satisfied or overridden in I . I is a minimal model for II if no proper subset of I is a model for II.

Definition 3.10. Given an interpretation I for IT, the reduction of II w .r .t. I , denoted by Gr(II), is the set of rules obtained from ground(II) by: (i) removing each rule that is overridden in I , (ii) removing each rule T that has property Body-(r) n I = 4, and (iii) removing the negation as failure part from the bodies of the remaining rules. Example 3.4. Consider the program 11 of Example 1. Let its interpretation I = {get-PhD(Jane)/O, has-publication( Jane)/O.S, PhD-student( Jane)/O.9}. (4) As shown in Example 3, the first rule in 01 is overridden in I . Thus, Gl(II) is the set of rules {get-PhD(Jane)/O c , PhD-student(Jane)/0.9 t, has-publication( Jane) t PhD-student( J a n e ) } . Consider now another interpretation

M = {get-PhD(Jane)/O,PhD-student(Jane)/O.S}. It is easy to see that Gn.r(II) = Gr(II).

(5)

We can see that the reduction of a program is simply a set of ground rules that do not contain not. Definition 3.11. Let M be a model for II. We say that M is an (PLP<) answer sets for II if M is a minimal model of the Gn.r(II).

Example 3.5. Consider the program II of Example 1. It is easy to see that the interpretation (4) is a minimal model for GI@).Moreover, it can be easily realized that I is the only answer set for II. On the other hand,

417

the interpretation ( 5 ) is not an answer set because it is not a model for GM(II) since the the second rule in 0 2 in ground(GM(II)) is not satisfied or probabilistic satisfied.

4. Knowledge representation with PLP< In this section, we present a number of examples which illustrate how knowledge can be represented using PLP<. To start, we show that PLP< encodes the famous nonmonotonic reasoning example stating that 80% of all birds can fly while Penguins do not fly.

Example 4.1. Consider the following program I'I with A(II) consisting of three objects bird, penguin and tweety, such that penguin is a sub-object of bird: bird ( f l y ( z ) / 0 . 8t bird(z)} penguin : bird { f l y ( z ) / O t}. Unlike in probabilistic logic programming [8], we may derived a pair of inconsistent ground patom fZy(penguin)/0.8 and f l y (penguin)/O from the set of rules. According to the inheritance principles, the ordering relationship between the objects can help us to assign different levels of reliability to the rules, and thus allow us to solve possible inconsistency or conflicts. For instance, in our example, the inconsistent conclusion penguin both possibly flies and does not fly to be entailed from the program (as penguin is a bird). However, this is not the case. Indeed, the lower rule fZiesCpenguin)/O t specified in the object penguin is considered as a sort of refinement to the general rule, and thus the meaning of the program is rather clear: tweety probably flies and penguin does not fly. That is, flies(penguin)/O t is preferred to the rule fZies(penguin)/0.8 t as the hierarchy explicitly states the specificity of the former. Intuitively, there is no doubt that M = {flies(tweety)/0.8,fZies(penguin)/O} is the only reasonable conclusion. Let us see another example.

Example 4.2. Consider the following knowledge base representing a set of security specification about a simple part-of hierarchy of objects. {TI

01

: authorize(Bob)/0.9 t not

authorize(Ann)/l, authorize(Ann)/0.6 t not authorize(AZice)/O} : authorize(AZice)/O t} : authorize(Bob)/O t}

r2 : 02

03

: 01 : 01

(7-3 (7-4

418

Objects 0 2 and 03 are, respectively, a part of the object 01. Access authorisations to objects are specified by rules with head predicate authorise and subject to which authorisations are granted appear as arguments. Inheritance implements the automatic propagation of authorisations from an object to all its sub-objects. The overriding mechanism allows us to represent exceptions: for instance, if an object o inherits a possible authorisation with probability a but another probability b for the same subject is specified in 0 , then the latter authorisation prevails on the former one. Consider the program 11 03 = ( ( 0 1 , (7-1,T Z } ) , (02, (7-3))) for the object 0 2 on the above knowledge base. This program defines the access control for the object 0 2 . Thanks to the inheritance mechanism, authorisations specified for the object 01, to which 0 2 belongs, are propagated also to 0 2 . It consists of rules 7-1, 7-2 (inherited from 01) and 7-3. Ruler 7-1 states that Bob is authorised with probability 0.9 to access object 0 2 provided that no authorisation for Ann to access 0 2 exists. Rule 7-2 authorises Ann with probability 0.6 to access 0 2 provided the fact that Alice is authorised with probability 0 to access 0 2 is not derive. Finally, rule 7-3 defines a denial for Alice to access object 0 2 . Due to the absence of authorisation for Ann, the authorisation to Bob of accessing the objects 0 2 with probability 0.9 is derived by rule T I . Further, the explicit denial to access the object 02 for Alice (rule 7-3) does not allow us derive the authorisation for Ann with probability 0.6 by rule 7-2. Hence, the only answer set of this program is {authorize(Bob)/0.9, authorize(Alice)/O}. Consider now the program II 03 = { ( 0 1 , { 7 - 1 , ~ } ) , ( 0 3 , { 7 - 4 } ) } for the object 0 3 . Rule 7-4 defines a denial for Bob to access object 0 3 . The authorisation for Bob with probability 0.9 defined by rule 7-1 is no longer derived. Indeed, even if rule 7-1 allow us derive such an authorisation due to the absence of authorisation for Ann, it is overridden by the explicit denial (rule 7-4 ) define in the object 0 3 , i.e., at a more special level. The body of rule 7-2 inherited from 01 is true for the program. Since no denial for Alice can be derived. The program IT 0 3 has answer set {authorise(Bob)/O, authorise(Ann)/0.6}.

5. Computation complexity In this section, firstly we analyse the computation complexity of the decision problems corresponding to Brave Reasoning in the propositional case: Given a PLP< program II and a patom L / p , decide whether there exists an answer set M for IT such that L/p is true w.r.t. M .

419

We next prove that the complexity of reasoning in PLP< is exactly the same as in probabilistic logic program [29]. That is, inheritance comes for free, as the inheritance adding does not cause any computational overhead. For the sake of space, we discuss this only in the propositional case (i-e., the case of ground PLP< programs).

Lemma 5.1. Given a ground PLP< program II and an interpretation M for II, deciding whether M is an answer set for II is in CoNP. Proof. We check in NP that M is not an answer set of II as follows. Guess a subset I of M , and verify that: (i) M is not a model for GM(II),or (ii) I is a model for GM(II) and I c M . The construction of GM(II) is feasible in polynomial time, and the tasks (i) and (ii) are clearly tractable. Thus, deciding whether M is not an answer set for II is in NP, and consequently, deciding whether M is an answer set for II is in CoNP. In order to prove the following theorem, we need two more lemmas. In [7], Gelfond and Lifschitz propose answer set semantics which is the most widely acknowledged semantics. We also defined the semantics of probabilistic logic programming [29] which is a variant of answer set semantics, for this reason, while defining the semantics of our language, we took care of ensuring full agreement with answer set semantics on inheritance-free programs.

Lemma 5.2. Let 11 be a PLP< program consisting of a single object o = (oid(o),C(o)). Then M is an answer set of ll if and only if it is a consistent answer set of C(o) (according to [29]). Lemma 5.3. Probabilistic logic programming under answer sets semantics is ng-complete. Proof. The semantics of probabilistic logic programming defined in [29] is a variant of answer set semantics proposed by Gelfond and Lifschitz [8]. The main difference is lie in the conditional transformation in step 1 in Section 3 which is in NP, while extended logic programming under answer sets semantics is Ci-complete [4]. So the problem is IIg-complete. Theorem 5.1. Brave reasoning on PLP< programs is Cg-complete. Proof. Given a ground PLP< program II and a ground p a t o m L l p , we verify that L / p is a brave consequence of 11 as follows. Guess a set M 5 Bn of ground patom, check that (i) M is an answer set for II, and (ii) Llp is true w.r.t. M, Task (ii) is clear polynomial; while (i) is in CoNP, by virtue

420

of Lemma 1. The problem therefore lies in C;. Further, Cg-hardness follows 0 from Lemmas 2 and 3. So, the theorem holds.

6. Related work

The work that is the closest to this paper is the one by Buccafurri et al. [3]. It describes a knowledge representation language to disjunctive logic programs with inheritance. The disjunctive logic programming only deals with disjunctive knowledge and non monotonic negation, while probabilistic logic programming aims handle with numerical uncertainty. In other words, [3] does not handle uncertainty, but ours does. Lukasiewicz [17] expresses an intention similar to ours, where he also discussed probabilistic logic programming under inheritance with overriding (PLPIO). In fact, he investigated a kind of approach of strengthening the notion of logic entailment in probabilistic logic programming. The approach is inspired by reference-class reasoning to Reichenbach [28] that can be interpreted as inheritance with overriding as it is known from objectoriented programming languages. There the notation of inheritance means that any class containing the particular individual can be considered as reference class, while the notation of overriding means that smaller reference classes are preferred to larger ones. However, the work is different from ours in a number of aspect. First, the language of PLPIO does not include default negation 1,while our PLP< includes it. Second, PLP< and PLPIO present different framework of probabilistic logic programming, and so they have completely different semantics. Third, our PLP< generalises consistent answer set semantics to probabilistic logic programming with inheritance, while PLPIO does not.

7. Conclusion This paper presents the syntax and semantics of a probabilistic logic programming language with inheritance, which is based on recent approach to probabilistic logic programming [29]. Moreover, we analyse the computational complexity of probabilistic logic programming with inheritance, and conclude that inheritance does not cause any more computational complexity (i.e., reasoning in PLP< has exactly the same complexity as reasoning in probabilistic logic programming). In the future, we plan to investigate the applications of this framework beyond default reasoning. It must be interesting to apply our work (that

42 1

combines logic and uncertainty) in the active research area of agent-based automated negotiation. This is possible since there are already some work (e.g., [27,10,11]) that bridges logic and agent-based automated negotiation, a n d some work t h a t bridges uncertainty and agent-based automated negotiation [19,20]. References 1. K. R. Apt. Logic programming, Handbook of Theoretical Computer Science, volume B, Chapter 10,pp. 493-574,MIT Press, 1990. 2. F. Bacchus, A. Grove, J.Y. Halpern, and D. Koller. From statistical knowledge bases to degrees of belief, Artificial intelligence, 87, pp. 75-143,1996. 3. F. Buccafurri, w. Faber, N. Leone. Disjunctive logic programs with inheritance. Theory and practice of logic programming, 2 (3): 293-321,2002. 4. E. Dantsin, T. Eiter, G. Gottlob and A. Voronkov. Complexity and expressive power of logic programming. In proceedings of the Twelfth annual IEEE conference on computational complexity, June 24-27,pages 82-101,1997, 5. M. I. Dekhtgar, A.Dekhtgar and V. S. Subrahmanian. Hybird probabilistic programs: Algorithms and complexity. In proceedings UAI-99, pages 160-

169,1999. 6. R. Fagin, J. Halpern and N. Meggido. A logic for reasoning about probabilities. Information and Computation, 87: 78-128,1990. 7. M. Gelfond and V. Lifschitz. The stable model semantics for logic programming. Logic programming: Proc. of the Fifth Int. Conf. and Symp., pages

1070-1080,1988. 8. M. Gelfond and V. Lifschitz. Classical negation in logic program and disjunc-

tive databases. New generation computing, pages 365-387,1991. 9. J. Y.Halpern. An analysis of fist-order logics of probability. Artificial Intelligence, 46(3): 311-350,1990. 10. M. He and N.R. Jennings. SouthamptonTAC: Designing a Successful Trading Agent. Proceedings of the Fifth European Conference of Artificial Intelligence, pages 8-11,2002. 11. M.He, H.F. Leung, and N.R. Jennings. A fuzzy logic based bidding strategy in continuous double auctions. IEEE Transactions on Knowledge and Data Engineering. 2003. To appear. 12. R.A. Kowalski. Predicated logic as a programming language. In information processing’74, pages 569-574,1974. 13. H. E. Kybur. Jr.The reference class. Philos.Sci,50:374-397,1983. 14. J. Lloyd. Foundations of logic programming. Springer, 1984. 15. T. Lukasiewicz. Probabilistic logic programming. In proc of the 13th Beinnial European Conf. On Artificial Intelligence, pages 388-392,1998. 16. T.Lukasiewicz. Many-Valued Disjunctive Logic Programs with Probabilistic Semantics. Proceedings of the 5th International Conference on Logic Programming and Nonmonotonic Reasoning, Volume 1730 of LNAI, pages 277-289,

1999.

422

17. T. Lukasiewicz. Probabilistic logic programming under inheritance with overriding. Technical report IN-FSYS RR-1843-01-05, Institut fur Information SSYS-teme, TU wien, 2001. 18. T. Lukasiewicz. Probabilistic logic programming with conditional constraints. ACM trans. Computat, logic 2(3), pages 289-337, 2001. 19. X. Luo, C. Zhang, and N.R. Jennings. A Hybrid Model for Sharing Information between Fuzzy, Uncertain and Default Reasoning Models in Multi-Agent Systems. International Journal of Uncertainty, Fuzziness and KnowledgeBased Systems 10(4), 401-450, 2002. 20. X. Luo, N.R. Jennings, N. Shadbolt, H.F. Leung, and J.H.M. Lee., A fuzzy constraint based model for bilateral, multi-issue negotiation in semicompetitive environments. Artificial Intelligence, 2003. To appear. 21. R. Ng and V. S. Subrahmanian. Probabilistic logic programming. Information and computation, lOl(2): pages 150-201, 1992. 22. R. Ng and V. S. Subrahmanian. A semantical framework for supporting subjective and conditional probabilities in deductive databases. J. autom. reasoning, lO(2): pages, 191-235, 1993. 23. R. Ng and V. S. Subrahmanian. Stable Semantics for Probabilistic Deductive Databases, Information and Computation, 110 (l), pages 42-83. 1995. 24. L. Ngo, P. Haddawy. Probabilistic Logic Programming and Bayesian Networks. ASIAN 1995, pages 286-300, 1995. 25. N. J. Nilsson. Probabilistic logic. Artificial Intelligence, 28(1): 71-87, 1986. 26. J. L. Pollock. Nomic probabilities and the foundations of induction. Oxford university press,1990. 27. S. Parsons, C. Sierra, and N.R. Jennings. Agents that reason and negotiate by arguing. Journal of Logic and Computation. 8(3), 261-292, 1998. 28. H. Reichenbach. Theory of probability. University of California Press, Berkeley, CA, 1949. 29. J. Wang and S. Ju. Probabilistic logic programming. Proceedings of the 8th joint international computer conference. Zhejiang University Press, 2002.

423

SEQUENT SYSTEMS FOR CLASSICAL AND INTUITIONISTIC SUBSTRUCTURAL MODAL LOGICS

OSAMU WATARI Division of Systems and Information Engineering, Graduate School of Engineering, Hokkaido University, Kita 13 Nishi 8, Kita-ku, Sapporo 060-8628, Japan E-mail: [email protected]

TAKESHI UENO Department of Mathematics, Hokkaido University, Kita 10 Nishi 8, Kita-ku, Sapporo 060-0810, Japan

KOJI NAKATOGAWA Department of Philosophy, Hokkaido University, Kita 10 Nishi 7, Kita-ku, Sapporo 060-0810, Japan

MAYUKA F. KAWAGUCHI AND MASAAKI MIYAKOSHI Division of Systems and Information Engineering, Graduate School of Engineering, Hokkaido University, Kita 13 Nishi 8, Kita-ku, Sapporo 060-8628, Japan

We introduce sequent style inference rules for classical and intuitionistic substructural modal logics. Using these inference rules, we define modal full Lambek calculi. We extend the algebraic interpretations, which have been given to the substructural (non-modal) logics in the previous investigations, so as to provide algebraic interpretations for modal full Lambek calculi. Using these interpretations, we proved soundness and completeness theorems for each of the modal full Lambek calculi.

1. Introduction

Among sequent systems for substructural logics, FL (full Lambek calculus) provides the basic framework for the investigation of substructural logics (see [4],151). Extending FL by adding structural inference rules (exchange, contraction, weakening), one obtains a series of substructural logics.

424

Addition of modal operator and their inference rules to the sequent system LK for classical logic led some researchers (Ohnishi, Matsumoto [3] and others) to the introduction of the sequent systems for classical modal logics. Intuitionistic versions of these systems are obtained by restricting the right hand side of a sequent in the well-known manner. Our main purpose here is to construct both classical and intuitionistic substructural modal sequent systems which result from FL and CFL, (classical full Lambek calculus with exchange) through the addition of modal operators 0 and 0 together with appropriate inference rules. (When we delete the exchange rule from classical systems, essentially different systems axe yielded through the change of the order of formulas in the left and right sides of sequents occurring in some inference rules [5]. Detailed investigations of these systems will be carried out in a separate paper. We consider here only extensions of CFL,.) We will prove soundness and completeness theorems for them through algebraic interpretations. 2. Formal system 2.1. Language, formula In this section, we introduce the language C for substructural modal logic. The basic propositional connectives of C consist of multiplicative conjunction * (called “asterisk”), multiplicative disjunction (called “plus”), additive conjunction A (called “and”), additive disjunction V (called “or”), implication 3 and >’, negation 1 and 4 , necessity 0 (called “box”), and possibility 0 (called “diamond”). We use t to denote the unit element for multiplicative conjunction. f denotes the unit element for multiplicative disjunction. T is called “top”, and it denotes the unit element for additive conjunction. I is called “bottom”, and it denotes the unit element for additive disjunction. As in FL, 1 A is an abbreviation of A > f , and 4 A is an abbreviation of A 3‘ f . For the propositional variables of C,we use symbols p o , p l , . . . . The set F of formulas of C is the smallest set which contains all the propositional variables of C as well as all the unit elements of C,and which is closed under the following rules:

+

(1) A E F (2) A , B E

* i A , - ‘ A , o A ,O A E F F

+ A * B , A + B , A A B , A v B , A 3 B , A 3‘ B E F

The classical substructural modal logics which we investigate in this

425

paper have the exchange rule. Under the presence of the exchange rule, there is no need to differentiate 3 and 3’.In classical cases, we therefore delete 3’.Since 4 A is defined as A 3’f , 4 is to be deleted from classical cases. It should be noted that the language of intuitionistic substructural modal logics do not contain the multiplicative disjunction In a sequent system, * corresponds to the “comma” on the left side of the sequent, and + corresponds to the “comma” on the right hand side. + is the dual of *. In intuitionistic sequent calculus, the “comma” never occurs on the right hand of the sequent. This is because, in an intuitionistic sequent system, one cannot write the inference rules for in such a way that the duality of and * is represented in inference rules. A sequent of substructural modal logics is a list of formulas having the following form:

+.

+

+

AI,.. .,A,

+ B1,. . . , B ,

where each Ai and Bj are any formula. Note that both sides of + is allowed to be empty. For the intuitionistic cases, no formula or just a single formula occurs on the right-hand-side of the sequent. 2.2. Inference rules

2.2.1. Classical substructural modal logics We introduce the system called CFL:, which is the basis for the other classical substructural modal logics. CFLF is obtained from the standard classical substructural logic CFL, [4,5] by adding the following inference rule (0-K):

or + AO A +

(0-K)

This rule was introduced and shown, in [3], to correspond to the axiom K for modality:

K : o ( A 3 B ) 1 ( O A 3 OB) Definition 2.1. (Inference rules for classical modal substructural logics) CFL: have the following axioms and inference rules: 0

Axioms and rules for logical constants:

A+A

426

-+t

r,rl-+ A -+ A tw

I',t,"I

f-+

r -+ A , A I + A , f , A l fw

Structural inference rule:

r , A ,B,r' -+ A (e left) r , B , A , F -+ A

r + A, A, B , A' r -+ A, B , A , A/

r -+ A , A r ' , A + A' r,rl-+A, A! 0

(e right)

(cut)

Logical inference rules:

7 -+ ~ A,-+,rAA r,A , ri -+ n r,AAB,P+A r,B , r1-+ A F , A A B , P -+ A

(1

left)

(A left) (A left)

r , A -+ A iA,A

r -+

right)

(1

r

-+ A,A,A' -+ A , B , A ' (A right) r -+ A , A A B,Al

427

The set of sequents provable in CFLq is defined to be the intersection of sets X’s each of which satisfies the following two conditions: 0 0

All the axioms of CFLE are members of X . If the upper sequent(s) of an inference rules of CFLE is in X , then its lower sequent is also in X .

The other systems, CFLfD, CFLqT, CFLfT4 and CFLFT5are obtained from CFLF by adding the following inference rules:

Or

A (0-4)

or -+ O A -+

These rules correspond to the following axioms for modality:

D : OA>iOiA T : OA>A 4 : OA>OOA 5 : i0-A > OTCI~A Among the above four rules, the first rule (0-D) is due to Valentini [7]. The rest of them are adopted from [3]. The provability for the above systems is defined similarly for the provability of CFLq

428

2.2.2. Intuitionistic substructural modal logics We introduce the basic system of intuitionistic substructural modal logics, called FLK. In case of classical modal logics, 0 and 0 are mutually definable with the help of 1.However, this mutual definability of 0 and 0 does not hold for intuitionistic modal logics[6]. As a result, FLK has the inference rule for the 0-modality and the inference rule for 0-modality. The classical modal logic K has two axioms: O ( A 3 B ) 3 ( O A 3 U B ) and O ( A 3 B ) 3 (OA 3 OB). The first axiom corresponds to the inference rule:

r+A

or + O A The second axiom corresponds to the inference rule:

A+C OA + OC These inference rules are investigated in [3]. In case of intuitionistic logic, the right-hand-side of the sequent is restricted to one or zero occurrence of a formula. Therefore, one cannot use the second inference rule for the 0-modality. Instead, we introduce two inference rules (O-Kl) and (O-Kz) for the +-modality:

as well as the (0-K) rule which is the same rule as in the classical cases. (The lack of the exchange rule forces us to device the inference rule for the 0-modality into two cases.) These three inference rules are used to introduce FLK.

Definition 2.2. (Inference rules for intuitionistic substructural modal logics) FLK have the following axioms and inference rules: 0

Axioms and rules for logical constants:

A+A

429

r,r/+ c t w r + fw r,t,r/-+c r+f 0

Structural inference rule:

rl + A r 2 , ~ ,+r 3c r2,r1,r3+ c 0

(cut)

Logical inference rules:

r + A B,r'+C r,A +B (3 left) (3 right) A 3 B,F,l-" + C r+A>B

r + B~, r / + c (3'left) r , A 3' B,r' + C A

left)

l ~ , -+ r +

r

(1

y A+ ~

+

left)

(1)

A,r + B (3' right) I'+AYB

r,A+

r+

A,F

right)

(1

l~

+

r + 1 ' (-2 ~

right)

r,A,r/+ c

(A left) F , A A B,I" + C r,B,r' + c (A left) r,AA B,P +C

(A right)

430

In the above axioms and inference rules, the formula C may not occur on the right-hand-side of a sequent. The other systems, FLKD,FLKTand FLKT4are obtained from FLK by adding the following inference rules:

These rules correspond to the following axioms for modality:

D : oA>OA T : UA>A,A>OA 4 : UA > DOA, OOA

> OA

The first rule (00-D) is due to Valentini[7]. The next three rules, namely (0-T),(0-T),and (0-4), are adopted from [3]. The last two rules, (0-41) and (0-42), are introduced here in order to circumvent the same sort of difficulty which we have faced with in the introduction of (O-K1) and (O-Kz). The provability for the above systems is defined similarly for the provability of CFLF 3. Algebraic interpretation

In this section, we will introduce algebraic structures, called modal fuZZ Lambek algebra. An algebra corresponding to (non-modal) full Lambek calculus was introduced in [2]. He called it “uni-residuated lattice-ordered groupoid” ,

431

which does not have an operation corresponding to 3’. Ono[4] introduced an “FL-algebra” where both 3 and 3’ are took into consideration. Furthermore, Ono extended it by adding the modalities (!, ?) for linear logics. They were called “modal full Lambek algebras” [4]. We will investigate modal full Lambek algebras for modalities such as K, K D , KT, KT4 and KT5. Definition 3.1. (Modal full Lambek algebras) A structure A = (V,U, n, 0,+,+’,L, M , 1,0,T, I)is a FLK-algebra if the following conditions are satisfied: (1) (V, U, n,0,+ , + I ,

1,0,T, I)is a FL-algebra:

(a) (V,U, n, T, I)is a lattice with the least element I and the greatest element T for which T = I -+ I holds, (b) (V,0 ,1) is a monoid with the identity 1, (c) Vx,y,z,wEV z o ( x u y ) o w = ( z o x o w ) u ( z o y o w ) , (d) Vx,y, z E V ((x o y 5 z e x 5 y + z ) and (x o y 5 z u y 5 IC +‘z ) ) , (e) 0 E V .

(2) L and M are maps from V to V satisfying: (a) (b) (c) (d) (el

Vx,y E V LxoLy < L ( x o y ) , L(a:ny) 5 L x n L y , 1 5 L 1 5 LT ( 5 T), vx, y E v Mx u My 5 M(x u y), (I5 ) M I 5 MO 5 0, VX,Y E V L(x+y) 5 Mx-+My , L(x+’y) 5 M x 4 M y .

To obtain FLKD-algebra,which corresponds to FLKD,we add to FLKalgebra the following condition (2)-(f) for operators L and M : (2)-(f) vx E

v Lx 5 Mx

We obtain the FLKT-algebra, which corresponds to FLKT, by adding to FLK-algebra the following condition (2)-(g), instead of (2)-(f): (2)-(g) VX E V LX 5 x

, z 5 MX

If we add the following condition (2)-(h) to FLKT-algebra, we obtain the FLKT4-algebra,which corresponds to FLKT4: (2)-(h) Vx E V Lx 5 LLx , MMx 5 Mx

432

To handle classical substructural modal logics, we introduce the basic algebra which is called CFLF-algebra. It is obtained by requiring the commutativity for the monoid mentioned in the condition (b) of the definition of FL-algebra, and furthermore by adding the “classical” condition (f) which is specified below. In classical cases, we do not need to distinguish +’ from + due to the commutativity of the monoid. Therefore, -+’is not necessary in the definition in CFLFalgebra, so that the last clause of (1)-(d) is deleted. Furthermore, L and M become mutually definable with the help of the “classical” negation. Thus, the conditions (2)-(c),(d) and (e) are to be discarded. Putting all these together, one comes down to the following definition of CFLF-algebra.

A structure A = (V,U, n, 0,+,L , M , 1,0, T, I)is a CFLE-algebra if the following conditions are satisfied: (1) (V,U, n, 0 , +,1,0, T , I)is a CFL,-algebra: (a) (V,U, n, T, I)is a lattice with the least element I and the greatest element T for which T = I + I holds, (b) (V,0,1) is a commutative monoid with the identity 1, (c) V x , y , z , w E V z o ( x u y ) o z u = ( z o x o z u ) u ( z o y o w ) , (d) V x , y , z ~ Vx o y < z @ x < y + z , (el 0 E (f) vx E v ( x c 0 )+ o = 2.

v,

(2) L is map from V to V satisfying: (a) v x , y ~ VL x o L y < L ( x o y ) , L ( x n y ) s L x n L y , (b) 1 5 L1 5 LT ( 5 T ) , To obtain CFLFD-algebra, which corresponds to CFLED, we add to CFLf-algebra the following condition (2)-(f) for operators L and M : (2)-(f) vx E

v Lx 5 L(x+O) + o

We obtain the CFLFT-algebra, which corresponds to CFLfT, by adding to CFLf-algebra the following condition (2)-(g), instead of (2)-(f): (2)-(g) vx E

v Lx 5 x

If we add the following condition (2)-(h) to CFLfT-algebra, we obtain the CFLET4-algebra, which corresponds to CFLFT4: (2)-(h) VX E V LX 5 LLx

433

We obtain the CFLFT5-algebra, which corresponds to CFLET5, by adding to CFLrT-algebra the following condition (2)-(i), instead of (2)(h): (2)-(i) Vx E V L ( x -+ 0) -+ 0 5 L ( L ( x-+ 0) -+ 0) Next, we define valuation map v : 7.=

+V.

Definition 3.2. (Valuation map) Let P be the set of propositional variables and let 210 be a mapping from P to V, then v is defined by the following recursion: (1) 4 P i > = voki) (2) v ( i A ) = w(A)+ 0 , v(1’A) = v ( A )+’0 (3) v(A > B ) = v(A) +v(B), v(A >’ B ) = v(A) +‘v(B) (4) v ( A * B ) = v ( A ) 0 w(B), v(A B ) = v ( i ( i A * -8)) ( 5 ) v ( A A B ) = v ( A ) n v ( B ) , v(A V B ) = v(A) U v ( B ) (6) v ( 0 A ) = Lv(A) , v(OA) = Mw(A) (7) v(t) = 1 , v(f) = 0 , v(T) = T , v ( l ) = I

+

In order to keep our exposition somewhat simpler, we will use a new parameter “L”. Let L be one of the following systems: CFLE, C F L r D , C F L f T , C F L r T 4 ,CFLtT5, FLK, FLKD,FLKT and FLKT4

Definition 3.3. (Validity of a sequent) A sequent I‘ + A is valid in L iff for any L-algebra and any valuation v we have v(r,) 5 .(A*), where l?* is the multiplicative conjunction of all the formulas in r and A* is the multiplicative disjunction of all the formulas in A. If r is the empty list of formulas, l? is treated as t. If A is empty, A is treated as f . Note: Classical modal logic K is characterized by the axiom O ( A > B ) > (CIA 3 O B ) . An alternative way to characterized K is to use the axiom O ( A A B ) OAAOB.This alternative method leads readily to an algebraic interpretations of non-substructural modal logics, as in [l],just by requiring L ( x n 3) = LXn Ly to hold. If one moves from non-substructural modal logics to substructural modal logics, then one can not always expect that O A A OB + O ( A r\ B ) is provable. In substructural logics, however, there are two kinds of logical conjunctions: Adaptation of one of them, i.e., multiplicative conjunction,

434

makes it possible to prove OA figure shows:

* O B -+ O(A * B ) , as the

A -+ A A , B -+ A * B UA

following proof

(* right)

* O B ?r D(A * B )

Based on these consideration, we have chosen the inequality Lx o L y L ( x o y) in the clause (2)-(a) of the definition 3.1.

5

4. Soundness

Theorem 4.1. (Algebraic soundness) If I‘ -+ A is provable in L, then r -+ A is valid in L.

Proof. It suffices to show that all the axioms are valid in L, and that every inference rule preserves validity, i.e., that for every inference rule of L, if the upper sequent(s) are valid, then the lower sequent is valid. The subsystem obtained from F L by deleting 3‘ has the “uni-residuated lattice-ordered groupoid”(0btained from FL-algebra by deleting -+‘) as its model, and the soundness of the subsystem is already proved in Lemma 2 of [2]. This Lemma can be applied not only to F L but also to CFL,. Therefore, we consider only the inference rules involving modality. ‘‘means j” that “from this (these) it follows that”. We use the following two simple facts. First, if y 5 y‘ then z o y o z 5 x o y‘ o z , because z o y‘ o z = z o (y U y’) o z = x o y o z U x o y‘ o z . Second, if x _< y then Lx 5 Ly, because Lx = L(z n y) _< Lx n L y 5 Ly.

(0-K) Assume that A l , . . . , A, -+ B is valid in L. Then, v(Al * . . . * A,) 5 v(B)is hold for any L-algebra. + v(UA1 * . * . * OA,) = Lv(A1) o . . . o Lv(A,) 5 L ( v ( A l ) o . . . o ~ ( A , ) ) = Lv(Ai*...*A,) 5 L v ( B ) = W ( U B ) Therefore, O A , , . .. ,UA, -+ O B is valid in L.

.

(O-K1) Assume that Al,. . . ,A,, B -+ C is valid in L (for intuitionistic cases). Then, v ( A l * . . . * A, * B ) 5 v(C) is hold for any L-algebra. + v(A1 * . . . * A,) 0 v ( B ) 5 w(C)

435

.

(V-K2) Assume that A, B1, . . . ,B, + C is valid in L (for intuitionistic cases). Then, v ( A* B1* . . . * B,) 5 v(C) is hold for any L-algebra. + v(A)0 v(B1 * . . . * B,) 5 w ( C ) + v(B1 * . . . * B,) 5 v(A)-+‘v ( C ) L w ( B ~.*. * * B,) 5 L ( v ( A )+’w ( C ) )5 M w ( A )+’ M v ( C ) Mv(A)0 L w ( B ~... * * B,) 5 M v ( C ) + v(OA * OBI * * * OB,) = M w ( A )o v(OB1 * . . . * OB,) 5 M I J ( A 0) L w ( B ~ * .* B,) 5 M w ( C )= w(OC) Therefore, OA, O B I , .. . , O B , + VC is valid in L.

+ +

(0-D) Assume that A1 , . . . , A, + is valid in C F L t D . Then, v(A1 * . . . * A,) 5 v(f) = 0 is hold for any CFLFD-algebra. v(A1 * . . . * A,-l) 0 v(A,) 5 0

+ + I J ( A ~* *. .* An-i) 5 v(An)+ O + Lv(A1 * . . . * An-l)

5 L(w(A,) -+ 0 ) 5 L((v(A,) -+ 0 ) + 0) + O = Lv(A,) + 0 + L z J ( A* .~. * An-1) 0 Lv(A,) 5 0 + v(OA1 * . . * OA,) = v(OA1 * . . . * CIA,-,) o v(OA,) 5 Lv(A1 * . . . * A,-I) o Lv(A,) 5 0 Therefore, OAl,. . . ,OA, + is valid in C F L r D . *

*

.

(UV-D) Assume that A1 , . . . ,A, -+ B is valid in FLKD. Then, v(A1 * . . . * A,) 5 v ( B ) is hold for any FLKD-algebra. + Lv(A1 * ... * A n )5 L v ( B ) 5 M v ( B ) + v(OA1 * . . . * DA,) 5 Lv(A1 * ... *A,) 5 M w ( B )= w ( V B ) Therefore, KIA,, ...,OA, + V B is valid in FLKD.

436

(0-T) Assume that A l , . . . , A , + B1,. . . , B , is valid in L (for CFLfT, CFLfT4, CFLFT5,FLKT and FLKT4). Then, v(Al *. . . *A,) 5 v(B1+. . . + B,) is hold for any L-algebra. j v(A1 * . * . * Ai-1 * DAi * Ai+l * * * . * A,) = v(A1 * . . * * Ai-1) 0 L v ( A ~0)v(Ai+l * . . . * A,) 5 v(A1 * . . * * Ai-1) o v(Ai)o ~ ( A i +*l . . * * A,) = v(A1 * . * * An) 5 v(B1 -I- . * . B,) Therefore, Al, . . . ,Ai-1, OA,, Ai+l,. . . , A , + B1,. . . ,B, is valid in L.

+

(0-T)

Assume that A l , . . . , A, + B is valid in L (for FLKT and FLKT4). Then, v(A1 * . . . * A,) 5 v(B)5 M v ( B ) is hold for any L-algebra. Therefore, A l , . . . , A , + O B is valid in L. 0

(0-4) Assume that OA,, . . . , OA, + B is valid in L (for CFLFT4 and FLKT4). Then, v(OA1 * . * OA,) 5 v ( B ) is hold for any L-algebra. jLv(OA1 * * . . * OA,) 5 L v ( B ) + v(OA1 * * * * OA,) = Lv(A1) o . . . O Lv(A,) 5 LLv(A1) 0.. . O LLw(A,) 5 L(Lv(A1)o . * * o Lv(An))= Lv(oA1 * . . . * DA,) < Lv(B)= v ( 0 B ) Therefore, OA,,. . . ,OA, + O B is valid in L. (0-41) Assume that CIA,, . . . , OA,,B + OC is valid in FLKT4. * OA, * B ) 5 v(0C) is hold for any FLKT4Then, v(OA1 * algebra. + v(OA1 * . . * * DA,) 0 v ( B ) _< M v ( C ) + v ( o A l * * * . * O A , )~ U ( B ) + M V ( C ) + Lv(OA~***.*OA,) 5 L(v(B)+Mv(C))5 M w ( B ) + M M v ( C ) + Lv(oAi* * . * * =A,) o M v ( B ) 5 M M v ( C ) 5 M v ( C ) 3 v(OAi* . - * * CIA, * OB) = v(oA1* . * * * OA,) 0 M v ( B ) 5 Lv(oAi* . . . * OA,) 0 M w ( B )5 M v ( C ) = v ( 0 C ) Therefore, OAl,. . . , DA,, Q B OC iis valid in FLKT4.

437

(0-42) Assume that A, O B I , .. . ,UB, -+ OC is valid in FLKT4. Then, v(A*UB1*.. .*LIB,) 5 v ( 0 C ) is hold for any FLKT4-algebra. =+ v ( A ) 0 v(OB1* . . . * OB,) 5 M w ( C ) jv(oB1 * * . . t OB,) 5 v ( A )-+'M v ( C ) jLv(OB1* . * . * OB,) < L(w(A)-+'M v ( C ) ) 5 Mv(A)-+'M M v ( C ) jMv(A) 0 Lv(oB1 * . * .* OB,) 5 M M w ( C )5 M w ( C )

+v(OA*OB1 * . . . * OB,)=MV(A)O~(OB~*...*OB,) 5 Mv(A)o L v ( O B ~ **.. * LIB,) 5 M w ( C )= v ( 0 C ) Therefore, OA, O B I , .. . , U B , -+ OC is valid in FLKT4. 0

(0-5) We use the following facts which hold for CFLzT5-algebra. ( L ( L x+ 0) -+ 0 ) 5 Lx holds, because: L ( ( x-+ 0) + 0) + 0 5 L ( L ( ( x-+ 0) 4 0) -+ 0 ) =+ LX-+O5 L(Lx-+O) = (L(L2+0)+0)+0 =+ (LZ-kO) 0 (L(Lx-+O)+O) 5 0 (L(Lx-+O)-+O)5 (Lx+O)-+O = Lx x 5 L ( z 0) -+ 0 holds, because: L(2 3 0) 5 (x-+ 0 ) =+ x 5 L ( x -+ 0 ) -+ 0 Lx 5 LLx holds, because: L x ~ L ( L z t O ) - , O ~ L ( L ( L x - + O ) - +5OL)L x is valid in Assume that OA,,. . . , OA, + B , OC1,. . . , OC, CFLfT5. holds for Then, v(OAl * - .. * OA,) 5 v ( B OC1 . . . UC), CFLET5-algebra. j v(OA~*****OA 5, (v(B)+O)o(v(OC1 ) +...+OC,)+O)-+O jv ( O A i * . . .* OA,) o ( v ( B )4 0 ) o ( ~ ( 0 C i ...+ + OC,) + O ) 5 0 jv(oA1 * . . . * OA,) o ( w ( B-+ ) 0) < (v(OC1+ . .. OC,)+O) 4 0 = v(OC1 * .. OC,)

*

+

+

+

+

+ +

438

5. Completeness Definition 5.1. (The Lindenbaum algebra) We define IAl to be the set { B : A + B and B + A are provable in L}. Each J A Jconstitute an equivalent class, and it does not depend on the choice of the representable element. Among these equivalent classes, we introduce algebraic operations in the following way:

IAl o IBI = [ A* BI J A ( r l [ B I = [ A A B ,J( A ( U I B [ = ( A V B ( \A(+ IBI = \A 3 B ( , (A1+‘ IB( = ( A3’B ( LlAl = IoAl , MIA1 = 10-41 Let F*= {IAJ : A E 3). The Lindenbaum algebra of L is defined to be the algebra:

v*, n, u,

+’, L , M , Itl, Ifl, ITI, 14)

0 ,+>

(For classical cases, +’ and M are excluded.)

L e m m a 5.1. The Lindenbaum algebra of L is an L-algebra. Proof. As in the proof of Theorem 4.1, we check here only the conditions involving modality. (For the other conditions, we refer the reader to Lemma 3 of [2].) Take A and B to be any formulas.

439 We need to show the fact that (A1 5 IBI is hold in the Lindenbaum algebra of L if A + B is provable in L. Assume that A + B is provable in L. Then, we have the proof

A

A A -t B (A left) A A (A right) A-+AAB AAB-+A

+

+

From this, it follows that JAl= IAABI = IAl n IBI holds in the Lindenbaum algebra of L. Hence, IAl 5 (BI holds. Using the above fact, we can show that the Lindenbaum algebra of L satisfies the conditions of L-algebra in the following ways.

5 L(IAI o IBI) holds, because we have

0

LlAl

0

L(IAI n IBI) 5 LIA( n LIB1 holds, because we have

o

LIB1

A + A (A left) A A B B (A left) AAB+A O(A A B ) -+ O B (0-W ~ ( ABA) + UA (A right) U(AA B ) + OA A UB -+

+

It1 5 Lltl 5 LIT1 5 IT1 holds, because we have

L(IAI + IBI) 5 MIA1 + MIBI L(lAI +’ PI) holds for intuitionistic cases. because we have 7

I

MIA1 -+’MlBl

440

(I( 5 MIL( 5 M(f(5 If1 holds for intuitionistic cases, because we have f + I + f

01+ Of (0-K1) Of

I + Ol(axiom) 0

LIA( _< L((AI+ lfl)

+ If(

-$

(O-K1) (fw)

holds for CFLFD, because we have

L/AI 5 MIA1 holds for FLKD,because we have A + - A (00-D) UA + OA 0

L J A J5 IAJ holds for CFLrT, CFLfT4, CFLFT5, FLKT and FLKT4,because we have

*

A A (0-T) OA + A 0

IAJ 5 MIA1 holds for FLKT,FLKT4,because we have A+A A+OA

(0-T)

0

L J A J5 LLJAJholds for CFLfT4 and FLKT4,because we have

0

IMMJAI5 MIA( holds for FLKT4,because we have

441

0

L()AI+If[) + If) 5 L(L(IAI+ If[)+ If[) holds for CFLFT5,because we have

Theorem 5.1. (Algebraic completeness) If a sequent I' + A is valid in L, then I? + A is provable in L. Proof. Suppose that A -+ B is valid in L. Then, IAl 5 lBl holds in the Lindenbaum algebra of L. From this, it follows that )A1 = ) A )n ) B )= ) A A B ) . By the definition of equivalence classes, A + A A B is provable in L. Now then, we can construct a following proof of A + B in L.

'

( A left) A-+AAB A A B + B (cut) A+B +

The above argument for A

+ B carries over for I? -+ A.

6. Conclusion

We have extended the sequent systems FL and CFL,, which constitute the basis of substructural logics, to obtain nine new systems for substructural modal logics CFL:, CFLFD,CFLFT,CFLfT4, CFL5T5,FLK, FLKD, FLKTand FLKT4by the addition of inference rules for the modal operators 0 and 0.These systems are proved to be both sound and complete through algebraic interpretations. Non-substructural modal logics have been recently a target of extensive research activities motivated by not only theoretical interests, but also various kinds of intentions to apply them to fields related to foundations of computer science, AI, and control engineering, to mention a few. We think that substructuralization of these modal logics will make it possible to obtain more detailed and finer arguments and analysis in these fields than those obtained by merely applying non-substructural modal logics. In this

442

regards, our soundness and completeness theorems may be regarded as providing a methodological foundation t o future applications of substructural modal logics. References 1. B. Chellas. Modal Logic: an introduction. Cambridge University Press, Cambridge, UK, 1980. 2. K. Dogen. Sequent systems and groupoid models. I. Studia Logical 47:353-385, 1988. 3. M. Ohnishi and K. Matsumoto. Gentzen method in modal calculi. Osaka Mathematical Journal, 9:113-130, 1957. 4. H. Ono. Semantics for substructural logics. In K. Dogen and P. ShroederHeister, editors, Substructural Logics, pages 259-291. Oxford University Press, Oxford, UK, 1993. 5. H. Ono. Proof-theoretic methods in nonclassical logic - an introduction. In Theories of Types and Proofs, MSJ Memoirs, pages 207-254. Mathematical Society of Japan, Tokyo, Japan, 1999. 6. A. Simpson. The Proof Theory and Semantics of Intuitionistic Modal Logic. PhD thesis, University of Edinburgh, 1994. 7. S. Valentini. The sequent calculus for the modal logic D. Bollettino della Unione Matematica Italiana, 7-A:455-460, 1993.

443

DIAMOND EMBEDDINGS INTO THE D.C.E. DEGREES WITH 0 AND 1 PRESERVED

GUOHUA WU School of Mathematical and Computing Sciences Victoria University of Wellington P.O. Box 600, Wellington New Zealand email: wu(0mcs. vuw. ac .nz

1. Introduction

Say that a set A C w is computably enumerable (c.e. for short), if A can be listed effectively. Thus we can define a set D C_ w to be d.c.e. if D is the difference of two c.e. sets. A Turing degree is c.e. (d.c.e.) if it contains a c.e. (d.c.e.) set. Let R be the set of all c.e. degrees and D2 be the set of all d.c.e. degrees. Since any c.e. set is d.c.e., R C_ Dz. Cooper [4] showed that there are d.c.e. degrees containing no c.e. sets (these d.c.e. degrees are called properly d.c.e. degrees), and hence R c D2. In [6], Cooper, Lempp and Watson proved that the properly d.c.e. degrees are densely distributed in the c.e. degrees. Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree, and so the downwards density holds in D2. Thus as noticed by Jockusch, Dz is not complemented. The first two structural differences between Dz and R are:

Theorem 1 (Arslanov’s Cupping Theorem [2]) Every nonzero d.c.e. degree cups to 0’ with an incomplete d.c.e. degree. Theorem 2 (Downey’s Diamond Embedding Theorem [lo]) There are two d.c.e. degrees dl, d2 such that dl U d2 = 0’, dl n d2 = 0.

By Theorem 2, the diamond lattice can be embedded into the d.c.e. degrees preserving 0 and 1. In this paper, we will refer to such embeddings as Downey ’s d i a m o n d embeddings. In [16], Li and Yi constructed two d.c.e. degrees dl,d2 such that any nonzero c.e. degree cups one of dl, d2 to 0’. As a corollary, any nonzero d.c.e. degree below dl is a complement of dz, and hence, one of the atoms

444

in Downey’s diamond can be c.e., which was demonstrated first by Ding and Qian in [9]. In [5], Cooper et al. proved that D2 is not densely ordered, which gives a more striking difference between R and D2: Theorem 3 (Cooper, Harrington, Lachlan, Lempp and Soare [5]) There

is a maximal incomplete d.c.e. degree. By Lachlan’s observation, the dual version of Theorem 3 is not true. However, as proved by Cooper and Yi [7], and independently by Ishmukhametov [12], the following weak density holds in the d.c.e. degrees: Theorem 4 (Cooper and Yi [7], Ishmukhametov [12]) For any c.e. degree a and d.c.e. degree d, if a < d, then there is a d.c.e. degree e such that

a<e
It is easy to see that d is isolated by a if and only if the interval (a,d) contains no c.e. degree. The isolated and the nonisolated d.c.e. degrees are densely distributed in the c.e. degrees (see Ding and Qian [8], LaForte [15], and Arslanov, Lempp and Shore [3]). In 1131, Ishmukhametov and Wu proved that there is an isolation pair (a,d) such that a is low and d is high. Thus, in the sense of the highflow hierarchy, the isolated degree can be far from the isolating degree. This paper is mainly concerned with the relationship between Downey’s diamond embeddings and the isolation phenomenon. First, we have the following observation: Proposition 6 (Wu [19]) For any c.e. degree c and isolation pair (a,d), if c n a = 0, then c n d = 0.

Proof of Proposition 6: Suppose not. Let c be any nonzero c.e. degree. Then by Lachlan’s observation that any nonzero d.c.e. degree bounds a nonzero c.e. degree, there is a c.e. degree e E (0,c n d). Thus, e < d and hence e < a since a bounds all c.e. degrees below d. an c 2 e > 0. A contradiction. 0 Based on this observation, Wu [19] gives an alternative proof of the existence of Downey’s diamond embedding:

445

Theorem 7 (Wu [19]) There are an isolation pair (a,d) and a c.e. degree c such that c u d = 0‘, c n a = 0. Thus, (0, c, d, 0’} is a Downey’s diamond embedding. The main idea involved in Theorem 7 is to ask d to be responsible for cupping c t o 0’ and a to be responsible for capping c to 0. This appears to be as close as we can get to overcoming the obstacle to constructing the diamond embedding into the c.e. degrees preserving 0 and 1, which first became apparent in Lachlan’s Non-Diamond Theorem [14]. Furthermore, Wu [22] showed that this idea can also be used to prove that for any high c.e. degree h, the nondistributive lattice M:, can be embedded into the interval [0,h] preserving 0 and 1. As a consequence, the nondistributive lattice S8 can be embedded into the d.c.e. degrees with 0 and 1 preserved. Say that a c.e. degree c is cappable in R if there is a nonzero c.e. degree b such that c n b = 0. Let M be the set of all cappable degrees. Obviously, 0 E M. Let NC = R - M. Ambos-Spies et al. [l]showed that M is an ideal in R and N C is a strong filter in R. They also showed that a c.e. degree c is cappable if and only if no low c.e. degree can cup c to 0‘ if and only if c contains no promptly simple sets. Downey, Li and Wu [ll]gives a new characterization of cappable degrees: c is cappable in R if and only if c has a nonzero complement in the d.c.e. degrees.

Theorem 8 (Downey, Li and Wu [ll]) For any c.e. degree c > 0, c is cappable in R if and only if there is an isolated degree d such that cud = 0’, cnd=O. Theorem 8 says that any nonzero cappable degree can always have an isolated degree as its complement. Again, the proof of Theorem 8 involves a construction of an isolation pair (a,d), such that c caps a to 0 and cups d to 0’. In this paper, we prove that any nonzero cappable degree can always have a nonisolated degree as its complement.

Theorem 9 For any c.e. degree c > 0, c is cappable in R if and only if c can be complemented in the d.c.e. degrees by a nonisolated degree. To prove Theorem 9, it’s necessary to prove:

Theorem 10 For any c.e. degree c > 0, if c is cappable in R, then there are two d.c.e. degrees b < d such that (1) b is properly d.c.e. and nonisolated; (2) b n c = 0, d U c = 0’; (3) b bounds all c.e. degrees below d.

446

Proof of Theorem 9: First, suppose that c has a complement d in the d.c.e. degree. Then by Lachlan's observation, we know that there is a nonzero c.e. degree e below d. c n e = 0. c is cappable in R. Now fix c > 0 as a degree cappable in R. By Theorem 10 (2) and (3), c is complemented by d. Now we show that d is nonisolated. Let e be any c.e. degree below d. Then by the fact that b bounds all c.e. degrees below d, we have e < b. Since b is nonisolated, there is some c.e. degree O f between e and b, and hence between e and d. d is nonisolated.

(b,d) in Theorem 10 is called a pseudo-isolation pair. For more details on the pseudo-isolated degrees, see Wu [HI, [20], [21]. We organize the paper as follows. In section 2, we list the requirements needed to prove Theorem 10, and describe the basic strategies to satisfy these requirements. In section 3, we give the construction, and in section 4, we verify that our construction satisfies all the requirements. Our notation and terminology are quite standard. During the construction, when we define a parameter as a fresh number x at stage s, we mean that z is the least number greater than any number mentioned so far. Particularly, x > s. For others, see Soare [17]. 2. Requirements and basic strategies Given a cappable c.e. degree c > 0, let C E c be any c.e. set. To prove Theorem 10, we will construct two d.c.e. sets B , D ,an auxiliary c.e. set E , and a partial functional satisfying the following requirements:

6: K = r(C, D); PE: E # P,": D # @ ;: Me: B # @,W. V We # iP:; N, : @: = @f= g total + g computable; R, : +pD = we+ ~ A , ( A : = we); Q, : W, = 0:

+ (3c.e. U, ST B ) ( v ~ ) (#u ,OF).

(2-1) (2.2) (2.3) (2.4) (2.5) (2.6) (2.7)

where e E w , {(@,,We) : e E w } is an effective enumeration of all pairs (a, W ) such that cf, is a partial computable functional, W is a computably enumerable set. K is a fixed creative set. Let b , d , e be the Turing degrees of B , B CBD, E respectively. By the requirement G, c U d = 0'. By the N-requirements, c n b = 0 . By the M-requirements, b is a properly d.c.e. degree. By the PE-requirements, d is incomplete. Thus, c and d are incomparable.

447

We now show that d is pseudo-isolated by b. By the PD-requirements, b < d. The Q-requirements guarantees that b is nonisolated and the Rrequirements guarantees that b bounds all c.e. degrees below d.

2.1. The 8 - s t r a t e g y

In the construction, the G-strategy will be responsible for coding K into C @ D . The G-strategy proceeds as follows: If there is an z such that r(C, D ; z ) [ s ]$# K,(x), then let k be the least such z, enumerate y(lc)[s] into D , and for any 1~ 2 Ic, let r(C, D ; y) be undefined. Otherwise, let k be the least number z with r(C, D; z)[s] f. If r(C, D ; z) has never been defined so far, then set r(C, D ; k ) [ s ]= K,(k) with y(k)[s] fresh. If not, let t be the last stage at which r ( C , D ; k ) [ t ]4. If one of the following holds, then set r(C, D; k)[s] = K,(k) with y(k)[s] fresh.

(a) There is some y < k with y(y)[s] > y(k)[t]; (b) There are some y-markers less than or equal to y(Ic)[t]enumerated into D or removed from D after stage t;

(In the construction, if a y-marker z is enumerated into D at stage and moved out at stage s2 > s1, then between these two stages, C will have a change below z, which allows us to list this y-marker to a larger number.) (c) C has a change below an active requesting number (as defined later), z say, and z 5 y ( k ) [ t ] . s1

If (a)-(.) do not apply, then set r(C, D ; k ) [ s ]= K,(k) with y ( k ) [ s ]= y ( k ) [ t ] . The G-strategy guarantees that r(C,D ) is totaIly defined and computes K correctly. Obviously, y-markers have the following properties:

448

2.2. A PE-strategy

A PE-strategy, a say, will satisfy a PE-requirement, E #

say. a is the Friedberg-Muchnik strategy, with some modification to cooperate with the coding of K . That is, during the construction, the coding procedure may enumerate infinitely many numbers into D and hence may injure the standard Friedberg-Muchnik strategy infinitely often. To avoid this, we use the threshold strategy as follows. Set a parameter k ( a ) first as a fresh number. k ( a ) acts as a threshold for the enumeration of y-markers. Whenever K changes below k ( a ) , reset a by canceling all parameters of a , except k ( a ) . Since k ( a ) is fixed, such a reset procedure can happen at most finitely many times. Let SO be the last stage at which a is reset or initialized. Suppose that at some stage s l , @:@D(z(a))[sl] converges to 0, then instead of putting .(a) into E immediately, we put y ( k ( a ) ) [ s l into ] D first to lift y(z) for z 2 k ( a ) to big numbers, and request that y ( k ( a ) )be undefined whenever C has a change below y ( k ( a ) ) [ s l ] .Correspondingly, we call y ( k ( a ) ) [ s l ]a requesting number. Say that y(k(a))[s1]’srequest is realized if C has a change below y ( k ( a ) ) [ s l and ] that y ( k ( a ) ) [ s 1 ] % request remains active if a has not been initialized or reset or y ( k ( a ) ) [ s l ] ’request s has not been realized. Note that the enumeration of y ( k ( a ) ) [ s linto ] D prevents the G-strategy from now on. However, from injuring the computation Qi:@D(z(a))[sl] ] into D may injure the computation the enumeration of y ( k ( a ) ) [ s l itself + : @ D ( z ( a ) ) [ ~Such l ] . injuries are called the “capricious injury” , which was first used by Lachlan in his nonsplitting theorem. Now suppose that y ( k ( a ) ) [ s l ] ’ srequest is realized at stage $ 2 , i.e., Cszr y ( k ( a ) ) [ s l # ] C,, y ( k ( a ) ) [ s l ] .Then y ( k ( a ) ) [ s 2 ]is redefined as a big number as requested by Y ( k ( 4 ) b l I (particularly, Y(k(Q))[S21> r(k(a)>[s11),and r ( k ( a ) ) [ s 1 I 1 s request becomes inactive forever. Let s3 2 s2 be the next a-stage. Then, by taking y ( k ( a ) ) [ s l out ] of D , the computation 4jf@D(z(a)) is recovered [ ~ ~y]( k, ( a ) )is undefined again by D,, ty(lc(a))[sz]# to @ : @ D ( z ( a ) )and Dsz t y ( k ( a ) ) [ s 2 ] Furthermore, . in the construction, to cooperate with the R-strategies (see below), at stage s3, when we take the number y ( k ( a ) ) [ s l ] out of D , we also put s1 into B. The enumeration of s1 does not injure the PE-strategy described above because s1 > cp,(z(a))[sl]. We now describe the a-strategy in details. First, choose z ( a )as a fresh number. Particularly, .(a) > k ( a ) . a runs cycles ( n ) n, E w . Fix n. Cycle (n)runs as follows: (1) Wait for a stage sn at which @:@D(z(a))[~n] $= 0.

449

(2) Put r ( k ( a ) ) [ s ninto ] D. For those z < r(k(a))[s,]with g m ( z ) f - , define g a ( z ) = Cs,(z). Declare that y(k(a))[s,] requests that C have a change below it to perform the Friedberg-Muchnik strategy. Start cycle ( n l),and simultaneously, wait for C to change below Y ( ~ ( Q ) [) ~ n l . (3) Enumerate .(a) into E , and simultaneously, take r ( k ( a ) ) [ s nout ] of D ,enumerate sn into B. Stop.

+

Since C is noncomputable, g , cannot be totally defined. That is, not every cycle can reach (2) and wait at (2) permanently. Let (n)be the first cycle reaching (3). Then a is satisfied because E ( x ( ~= ) )1 #

o = @feD(z(a))[~nl = +feD(~(a)).

a has the following outcomes:

0

."


where n means that the cycle ( n ) waits at (1) forever, and d means that some cycle reaches (3) eventually. 2.3. A IPD-strategy

A PD-strategy, p, is a standard Friedberg-Muchnik strategy. follows:

p works as

(1) Define x(P) as fresh. (2) Wait for a stage s at which + f ( z ( p ) ) [ s ] $= 0. (3) Enumerate z(@)into D and stop. ,O has two possible outcomes, 0 , l with 0 < L 1, where 0 indicates that ,B arrives at step (3) eventually, and 1 indicates that a keeps waiting at step

(2). 2.4. A n M - s t r a t e g y

An M-strategy, q say, working for an M-requirement, Me, attempts to find a number witnessing B # @? or We # Q:.

q works as follows:

(1) Choose ~ ( qas) a fresh number, (2) Wait for a stage s such that 0 = Bs(z(q))= +?(X(~))[S]

Qt:

and

t ve,s(z(q)). We,, t pe,s(z(q)) = (If this never happens, then z ( q ) is a witness to the success of Me.)

450

(3) Put z(q) into B. Protect B, r s from other strategies. (4) Wait for a stage s‘ such that 1 = B,, ( z ( q ) )= a? (x(q))[s’]and

We,sl tpe,s(x(q)) =

tpe,s(x(q))-

(If this never happens, then again x ( q ) is a witness to the success of M e . If it happens, then the change in (x(q)) between stages s and s‘ can only be brought about b y a change in We rpe,s(x(q)), which is irreversible since We is a c.e. set.) (5) Remove x(q) from B and restrain B r s from other strategies. (Now x ( q ) is a permanent witness to the success of M e because We tpe,s(x(q)) # tpe,s(x(q)).)

*:

q has two outcomes, 0
To satisfy an N-requirement, N, say, we will define (partial) computable functions q!Je,i,i E w such that for some i, q!Je,i = he, provided that = = he is total. Define the length of agreement between @fand @: as follows:

[(e,s) = .{ :VY < x[@,B(d[s1-1=@,c(Y)[S14h m ( e , s) = max{l(e, t ) : t < s}. Say that stage s is expansionary if s = 0 or [ ( e ,s) > m ( e ,s). Our strategy is to preserve computations up to the greatest length of agreement between @: and a:. Since C has a cappable degree, we can utilize the gap-cogap argument to preserve the computations. That is, we will define a partial computable function p , such that either N,-requirement is satisfied or p e witnesses that C has a promptly simple degree, which is impossible by our assumption on C. In the latter case, p , satisfies the following requirements: Se,i:Wi infinite

+

( 3 ~ ) ( 3 ~ )E [ aWi,a+, : ,& C, 1%# Cpe(,)1x1.

The whole construction is partitioned into infinitely many intervals which are referred to as gaps and cogaps alternatively (as defined later), and we only allow B to change at those stages inside a gap. Thus, inside a gap, we allow B to change and see whether C has a change on small numbers. If C does have a change on some small numbers inside a gap, then some computation @:(y) may change, and at the next expansionary

451

stage, both @F(y)and @s(y) converge to a new value, making +,,i(y) incorrect. However, such C-changes provide us opportunities to satisfy the &+-requirement if we define p,(s) properly (as the stage at which the gap is closed) and we can start to attack a new S-requirement. On the other hand, if C has no such changes during a gap, then at the stage we close the gap (another expansionary stage), we will set up a restraint on B to preserve the B-side computations. Thus, if @: = @: = he is total, then by our assumption that C has a cappable degree, there is some (least) i such that Se,i is not satisfied. In this case, Se,i will define +)e,itotally. As described above, inside the gaps, the C-side computations don’t change and inside of the cogaps, the B-side computations are preserved. Therefore, &?,i computes he correctly. Now we define gaps and cogaps formally. Let s be any expansionary stage. If there is some i such that

(01) Se,i is not satisfied; (02) x enters Wi at stage s; ( 0 3 ) 3Y[Y < q e , s) @ e , i ( Y ) [ S ] t & x

> max{cp(Cs; el Y’,3)

: Y’

I Yll.

Then let i be the least one and open a gap for Se,i as follows:

(1) For those y‘ _< y, where y is as in (03), if ?Jle,i(y’)[s]f, then define @e,i(Y’)= @?(Y’)[S]; (2) Set the restraint r ( e ,i, s) = 0, and initialize all strategies Se,j with j

> i.

Let v be the next expansionary stage and close the gap as follows: (Cl) Define p e ( s ) = v . (C2) Set r ( e ,i, v ) = v . During a gap, if C has a change below x,then by p e ( S ) = v , C, tx # Cpe(,)7 x, Se,i is satisfied. In this case, we say that the gap is closed successfully. If there is no such C-change, then the gap is closed unsuccessfully. Suppose that @: = @: = he is total. Since C has a cappable degree, there is a least i such that Se,icannot be satisfied. Then Se,iopens infinitely many gaps, and each one is closed unsuccessfully. Let so

< . . . < s,


< ...

be the stages at which Se,i opens and closes gaps alternatively. We prove below that I / . J ~computes ,~ he correctly.

452

Fix y and let $ ~ ~ , i ( ybe) defined at stage s,. at stage s,. That is,

Then we open an &+-gap

(1) sj is an expansionary stage, (2) some z enters Wi at stage s,,

and there is some y with (3) Y < t ( e , s n ) ,$ e , i ( ~ ) [ ~ Tand n] 2 > (~(Cs,;e,~,sn), (4) q!~~,i(y)is defined as +F(y)[s,] at the end of stage s,.

Then at stage w,, we close this gap by defining p e ( s , ) = w,, restraining numbers less than w, from entering B till stage s,+1. Since C has no change below cp(CSn ; e, y, s,) inside this gap (otherwise, Se,i will be satisfied), @F(y)[s,] = @F(y)[wn], and hence $e,i(Y)

= @ f ( y > [ ~ n= ]

+.S(Y>[S,I = +F(Y)[v,I = +?(Y>["~I.

Now numbers less than w, are restrained from entering B between stages w, and s,+1, numbers less than w, are restrained from entering B , and as a result, the computation +:(y)[w,] is preserved and hence +e,i(Y)

= + f ( ~ > [ w n I= + f ( ~ ) [ ~ n + l= I +?(y)[~n+lI.

By induction, we have for all m 2 n, $e,i(Y)

= @ f ( ~ ) [ ~ r n=I +?(y)[~mI = +?(~)[wrnI = + f ( ~ > [ w r n ] .

Since both @(y) and +F(y) converge, we have $e,i(Y)

= +:(Y)

= +?(Y> = h e ( Y ) .

Let a be any N-strategy on the tree. Then rs works to satisfy requirement. Define

Ne(,)-

l ( o , s )= {z : VY < "[@$,)(Y)[sl-1=+~,)(Y)"}; m(a,s) = max{l(a, t ) : t < s and t is a-stage}. Say that a stage s is a-expansionary if s = 0 or s is an a-stage and qrs, s) > m(a,s). rs has infinitely many substrategies, each of which works on an Se(u),irequirements. In the following, we write S,,i for Se(,,),i,$,,i for $e(u),i for convenience. During the construction, S,,i may open (and hence close) gaps at expansionary stages, and whenever S,,i opens a gap, S,,i will extend the definition of qm,i. Say that S,,i requires attention at an a-expansionary stage s if one of the following holds:

(1) S,,i is inside a gap. (2) S,,i is inside a cogap. There are two subcases:

(2A) There is some y E dom($,,i) such that C, cp,(C; y)[v] # C, cp,(C; y)[v], where v is the last a-expansionary stage. (2B) &,i is ready to open a gap.

r

In case (2), (2A) has higher priority than (2B). It may happen that (2A) prevents S,,i from opening a gap (2B) for almost all times. In this case, dom(&,i) is finite, and there is some y E dom($,,i) with @F(g)T. Sg,i has two outcomes g
WYH. Say that S,,i receives attention at an a-expansionary stage s as follows if Sa,irequires attention at this stage:

Case I: (1)happens. Then close the gap, define p,(v) = s, and initialize all nodes with lower priority. Stop stage s. If C has a change below x (x is defined in (02) at stage w , where w is the stage at which the gap is opened) then we say the gap is closed successfully, and declare that S,,i is satisfied. Otherwise. The gap is closed unsuccessfully.

Case 2 (2A) happens. Then S,,i has outcome d. $,,i

Case 3: (2B) happens. Then S,,i opens a gap, extends the definition of according to (03). S,,i has outcome g.

In the construction, we don’t put S strategies on the priority tree. We just attach the outcomes of S to a. Thus, a has outcomes go
. . .
gi < L di
. ..
which are described as follows:

f. f denotes the case in which there are only finitely many

u-

expansionary stages (and hence, u is satisfied trivially). d . d denotes the case in which there are infinitely many aexpansionary stages, and a’s substrategies can require attention only finitely many times (if so,then is not total because (03) fails for almost all times and hence there is some z such that @ : ( z ) t , (a: is not total.)

454

gi. gi denotes the case in which the substrategy Su,i opens (and closes) gaps infinitely often. As described above, Gu,i is totally defined. di. di denotes the case in which Sg,ican open gaps only finitely often and there is some y E dom($,,i) such that @z(y) diverges. 2.6. A n U - s t r a t e g y

An %?,-strategy works to satisfy '&-requirement. Define l ( e , s ) = max{z < s : (Vy < z)(@:@D(y)[sI &=We,s(y))}, m(e, s ) = max{O,l(e, t ) : t < s} Say that stage s is expansionary, if s = 0 or l ( e ,s ) > m(e,s). The basic isolation strategy works as follows. At expansionary stage s > 0, for any y < t ( e , s ) , if Af(y)[s] t, then define Af(y) = W , , s ( y ) with 6,(y)[s] = s. Suppose that 6,(y) is defined at stage s. During the construction, numbers enumerated into D ,z say, may injure the current computation of @:@D(y). Such an enumeration may lift the use (pFeD(y), but with Af(y) unchanged. This provides chances for We t o change at y , and if so, A, becomes incorrect at y. Suppose that y enters We at stage s' > s. At the next expansionary stage s" 2 s', by taking numbers, z mentioned above, out of D ,we recover the computation @:eD(y) to @:@D(y)[s]. This creates an inequality because

By preserving this inequality, due to the c.e.-ness of W e ,y remains in W e , and therefore R, is satisfied. We refer to this method as the disagreement strategy. On the other hand, if is total and = W e ,then we will ensure that A: is total and computes W, correctly. Let J be any R-strategy on the tree. Instead of using a,(<), We(<) explicitly, we use at, W
t(t,s ) = max{a: < s : (VY < z)(@PeD(Y)[SI-1= m(J, s) = max(O,l(J, t ) : t

Wg,s(?/))},

< s and t is a J-stage}.

Say that stage s is (-expansionary, if s = 0 or s is a J-stage and l ( Js) , > m(t7 s). Similar to the PE-strategy, J needs to cooperate with the G-strategy. Set k ( J ) as a fresh number. k ( J ) will act as a threshold for the enumeration of y-markers and whenever K changes below k(J), reset t. Again, since k ( J ) is a fixed number, we can assume that after stage so,K has no change below k(J) and hence J cannot be reset afterwards.

455

Without loss of generality, suppose that at a (-expansionary stage s1 > E defines AF(y) = W C , ~ ~with ( ~ )use S,(y) = s1, and that at a (expansionary stage s 2 > s1, 6 finds that A? has a wrong guess of W,(y) (i.e., AF(y) = W C , ~ ~=( 0~ #) 1 = W€,sz(y)),then 5: will perform the following actions: SO,

(1) initialize all strategies with Iower priority to prevent these strategies from injuring the associated computation; ( 2 ) enumerate y(k(())[s2] into D to lift y(z) with z 2 k(() to prevent the G-strategy from injuring the associated computation. Again, we say that y(k(J))[s2] requests that C have a change below it to perform the disagreement strategy. Note that the enumeration of y(k(())[s2] may injure the associated computation. However, if r(lc(())[s~]'s request is realized (C ry(k(())[s~]changes) at stage s3 > s2 say, we redefine y(k(J))[s3] as a big number. Particularly, y(k([))[s3] > s3. Now at the next &expansionary stage, s4 2 s3 say, we take the numbers enumerated into D after stage s1, including y(k(c))[s2], out of D ,and thus recover the computation @FBD(y)to @FeD(y)[s1], which equals 0. By preserving this computation, we have BBD

@,BBD(Y)= a<

(Y"l1

= W€,S1(Y)= 0 # 1 = Wr,dY) = W Y ) .

R is satisfied. As in the PE-strategy, for the sake of the consistency between ( and those R-strategies with higher priority, at stage s4, we also put s1 into B , and declare that for all R-strategies E' c and for any y, if 6<1(y) > s1, let AF(y) be undefined. Obviously, the enumeration of s1 does not injure the disagreement created above. Now we describe the (-strategy in detail. runs cycles ( n ) ,n E w , each of which defines a partial computable functional, A<,n.

<

Cycle (n)runs as follows: (1) Wait for a (-expansionary stage. (2) Let s1 be a &expansionary stage. Then, for any y < t(6,sl) with A&(y)[sll t, define A&(Y)[sI] = W E , ~ ~ (with Y ) ~<(Y)[SI] = si. Go back to (1) and simultaneously, wait for W,(y) to change. (3) Let s 2 > s1 be the first (-expansionary stage with Wr,,,(y) = 1 # 0 = W ~ , s l ( ~and ) A&(Y)[S~]-1= A~,(Y)[sI] with use 6<(y)[s2]= s1. Put y(k(())[s2] into D ,and declare that y(k(<))[s2] requests that C have a change below it to perform the disagreement strategy. For those z < y(lc(())[52], if gc(z) t,define gc(z) = C,, ( z ) .

456

+

Start cycle ( n l), and simultaneously, wait for C to change below y ( k ( 5 ) )b 2 1 . (4) Take y ( k ( [ ) ) [ s aout ] of D ,put s1 into B (perform the disagreement strategy f o r 5) and declare that is satisfied via the disagreement at y .

<

( satisfies the R-requirement as follows:

Case 1. There is a cycle waiting forever at (1). (There i s some y such that @FeD(y)T or @FeD(y)$# W c ( y ) . ) Case 2. There is a cycle, ( n )say, going from (2) to (1) infinitely often. = Wc, then A:, is totally defined, and computes Wc (If correctly.) Case 3. There is a cycle reaching (4) via number y.

(Then, @F'D(y)$= 0 # 1 = W c ( y ) . ) Note that the incomputability of C ensures that it cannot be the case that for each n E w , cycle ( n ) is started, because otherwise, each cycle would wait at (3) forever, making gc totally defined, and hence C is computable. Thus, ( has the following outcomes:

( 0 , ~
Remark: Let A & ( y ) be defined at stage s1 with use &,(y) = s1. In the construction, it is possible that an M or 7-strategy below [ ^ ( n , m ) can enumerate a number x < s1 into B , at stage s2 > s1 say, and hence according to the construction, A [ , ( y ) is undefined at stage s2. If z remains in B , for any s > s2, B, 1 s1 # B,, 1 s1, and thus, the definition of A t , ( y ) [ s 1 ] cannot be recovered to that of stage s1. However, it is possible that at a stage s3 > s2, AE,(y) is redefined with use S<,,(y) = s3 and that later, at stage s4 say, z is moved out of B. Then because B r s l is recovered to B,, 1 s1, by the use principle, A[,(y)[s4] is recovered to the one at stage s1 with use &,,(y)[s4] = s1 of course. Also note that the definition of A f , ( y ) [ s 3 ] with use s3 is now undefined automatically because of the extraction of z. Thus, the M , 7-strategies below ( ^ ( n , m) do not make the definition of A?, inconsistent.

457 2.7. Q-strategies and substmtegies

Q,-strategy, then Uc

< say, attempts to construct a c.e. set Uc such that if We = OF,

ST B and for all i E w,Uc # a,”(. Define

k?(<, s) = m d x < s : (tJY < 4(@;(Y)[sl -1= Wc,s(y))}, r n ~ ( < , s=) max{O,lQ(<,t) : t < s & t is a <-stage}. Stage s is <-expansionary if s = 0 or s is a <-stage and &(<, s) > me(<,s). has two outcomes: 0
q,i U<# 07, (2.8) Let x be an q,i-strategy. Then x tries to figure out an inequality point between Uc and a,”( or between We and 0; (the latter is a global win). x proceeds as follows:

(1) Choose z(x)as a fresh number. (2) Wait for a stage s such that n:+(z(x)) $= 0, and W C ,1~ wi,s(z(x)) = 0:: i u i , s ( x ( x ) ) . (If this never happens, then x ( x ) is a witness t o the success of x , i . ) (3) Put z(x)into Uc and B. Protect B 1s from other strategies. W (4) Wait for a stage s‘ such that Oi,;+’ (x(x))$= 1. (If this never happens, then again x(x) is a witness t o the success of q , i . If it happens, then the change in (x(x)) between stages s and s’ can only be brought about by a change in We rwi,,(x(~)), which is irreversible since We is a c.e. set.)

fly

(5) Remove z(x)from B and protect B 1s from other strategies. (Now

is a permanent witness t o the success of x,i because OF rwi,s(x(x)) # We T~i,~(zC(x)). Note that taking x(x) from B leads t o a global win o n Q,. Uc is n o longer needed, and so we don’t need to care about the loss of B-permisssion f o r x(x) (which is left in Uc).) X(X)

1. Note that if x reaches step ( 5 ) , then an inequality between W, and O < ( B )is created, and so gets a global win for 5.

x has one outcome

x

458

3. Construction

Before describing the construction, we define the priority tree, T say, effectively. First define the priority of the requirements as follows:

6 < PE
<

Definition 3.2. (1) Define the root node X as a PE-strategy; (2) The immediate successors of a node are the possible outcomes of the corresponding strategy; (3) For 6 E T , 6 works for the highest priority requirement which is not satisfied at 6. For 6 E T , if 6 is one the PE-strategies, PD-strategies, M-strategies, and S-strategies, then z(6) will be defined. Furthermore, if 6 is a PEstrategy or an R-strategy, then k(6) will be defined. In the construction, if 6 is initialized, then any parameters will be cancelled. If 6 is reset, then any parameters, except k(S), will be cancelled. If 6 < 6' and 6 is reset or initialized, then 6' will be initialized simultaneously and automatically.

459

Construction

Without loss of generality, suppose that K is enumerated at 3 n + l stages, C is enumerated at 3 n + 2 stages. and that exactly one element is enumerated into K and C at each such a stage. Stage 0: Set B = D = E = 0, and initialize all nodes.

Stage s

+ 1:

(I) s _= 0 (mod 3). Let k be the number in K,+1 - K,. For any strategy 6, if k ( S ) > k, reset 6. If r(C,D; k ) [ s ]4,then enumerate y(k) into D. Otherwise, let z be the least y such that r(C,D; y) f. If r(C, D; z) is first defined, then define r ( C , D ;z)[s 11 = K,+l(z) with r(z)[s 11 fresh. Otherwise, let t be the last stage at which r(C,D; z)[t]4.If one of the following holds, then define r(C,D; z)[s 11 = K,+l(z) with y(x)[s 11 fresh.

+

+

+

+

(a) There is some y < k with y(y)[s] > y(k)[tJ; (b) There are some y-markers enumerated into D or removed from D since stage t. (c) C has a change below the largest active requesting number, z say, and z 5 y(k)[t].

If (a)-(c) do not apply then define r(C, D ;x)[s + 11 = 7(3)[tI* In any case, go t o the next stage.

+ 11 = K,+1 (x)with use

Y(Z"

(11) s

= 1 (mod 3).

Let c be the number in Cs+l- C,. If c is less than some active requesting number z = y ( k ( ~ ) ) [ swith ' ] s' < s, then declare that z's request is realized, and if y(k(~))[s]4,then let r(C, D ;k(~))[s 11 be undefined.

+

(111) s _= 2 (mod 3).

+

Say that a strategy 6 is visited at stage s 1, if 6 is eligible to act at a substage t of stage s + 1. First, let A, the root node, be eligible to act at substage 0.

+

Substage t: Let S be eligible to act at substage t. If t = s 1, then define cS+l= 6, initialize all C > gs+l,and go to the next stage. Otherwise, there are 7 cases: Case I. 6 = a is a PE-strategy.

al. If k(a)f, then define k(a)as a fresh number, define Ss+l = a , initialize all nodes with lower priority and go to the next stage.

460

a2. If k(a) J, z ( a ) t, then define .(a) as a fresh number, define 68+1= a , initialize all nodes with lower priority and go to the next stage. a3. If .(a) J and .(a) E E , then let a - ( d ) be eligible to act at the next substage; a4. If a is not satisfied, and a has a requesting number realized between the last a-stage and s + 1, i.e., there is some z with ga(z) # Cs+l(z).Let z be the least such disagreement point, and let s' 5 s be the stage at which ga(z) is defined. Move out all numbers enumerated into D after stage s' (including y ( k ( a ) ) [ s ' ] ) , put .(a) into E and s' into B , and for all y 2 k(a),let r(C,D;y) be undefined. For all $, and n with <^(n,m) a , if b&(m) > s' then let 6!,(m) be undefined. Declare that a is satisfied via z. Define os+l = a and initialize all nodes with lower priority. Go to the next stage. a5. Otherwise, suppose that a is in cycle (n). There are two subcases: Subcase 1. If @ f e D ( z ( a ) )+ [ s11 J= 0, then enumerate y ( k ( a ) ) [ s+ 11 into D, and for y 2 k(a),undefine r(C,D;y)and for z < y ( k ( a ) ) [ swith ] g t ( z ) t , define g t ( z ) = C,+l(z). Declare that y(k(a))[s] requests that C have a change below it to perform the Friedberg-Muchnik strategy. Stop cycle ( n ) and start cycle (n 1). Define o,+1 = and initialize all nodes with lower priority. Go to the next stage. Subcase 2. Otherwise, let a^(n) be eligible to act at the next substage;

+

Case 2. 6 =

is a PD-strategy.

z(P) t, then define z(P) as a fresh number, define &,+I = 0, initialize all nodes with lower priority and go to the next stage. 02. If z(P) J and z(P) E D , then let ,f3^(0) be eligible to act at the next substage; 03. If z(P) J, @;(z(P))[s 11J= D,(z(p)) = 0, then enumerate z(@) into D , define 6,+1 = fi, initialize all nodes with lower priority. Declare that ,B is satisfied and go to the next stage. p4. Otherwise. Let ,f?-(l)be eligible to act at the next substage.

01. If

+

Case 3. 6 = q is an M-strategy.

q l . If z(q) f, then define z(q) as fresh. Define 6, = q, initialize all strategies with lower priority and go to the next stage.

461

172. If ~ ( 1 7 )1,@ r Y ( x ( v ) -1= ) 0 = B*(x(v)), and w7,s t,4Bs;e(17),~(17),S) =

QCt O s ; e ( 1 7 ) , 4 1 7 ) , s ) , c

then enumerate x(q) into B , For all and n with <-(n,co) & a , if 6&(m) > x(q) then let 6&(m) be undefined. Define 6, = 17, initialize all strategies with lower priority and go to the next stage. 173. If x(q) 1, (~(17)) ./.= 1 = Bs(x(7/))and

@FFs

w7,st4Bs-;e(17),417),s-)=

Q?,

ru(BS-;.(17>,.(17),s-),

where s- is the stage at which x(q) in enumerated into B , then take x(q) out of B , define 6, = 17. (Note that by the use principle, those A&(m) undefined by the enumeration of x ( v ) are defined now because of the recovering of B 1 S[,(m).) Declare that 17 is satisfied, initialize all strategies with lower priority. Go to the next stage. 174. If 17 is satisfied, then let ~ ~ ( be0 eligible ) to act at the next substage. 175. Otherwise, let q n ( l ) be eligible to act at the next substage. Case 4.6 = o is an Af-strategy.

+

01. If s 1 is not 0-expansionary, then let un( f) be eligible to act at the next substage. 02. If s 1 is o-expansionary, and no substrategy requires attention, then let u-(d) be eligible to act at the next substage. 03. Otherwise, let i be the least number such that Su,i requires attention, and let Su,i receive attention as follows:

+

5 v, where v is the stage at which the gap is opened, define pg(m) = s 1. Let x be chosen by ( 0 2 ) at stage w. If C has a change below x between stages v and s 1,then declare that the gap is closed successfully and that Su,i is satisfied. Otherwise, declare that the gap is closed unsuccessfully. Define o ~ = + a-(gi), ~ initialize all nodes to the right of ~ , + l , and go to the next stage. Subcase 2. If 0 is inside a cogap and there is some y E dom($,,i) with C,,l %(Y)[V] # CIJ cpu(Y)[vl, where 'u is the last Qexpansionary stage, then let on(&) be eligible to act at the next substage. Subcase 1. If Su,i is inside a gap, then close the gap, and for all m

+

r

+

r

462

Subcase 3. Otherwise, Su,i is ready to open a gap. That is, there is some z entering Wi between stages w and s + 1, where w is the last an(gi)-stage, and there is some y < l ( g , s + l ) with $u,i(y)[s+ 11 t and z > max{u(Cs+l; e ( o ) , y ‘ , s 1) : y‘ 5 y}. Choose y as the least such number and define $u,i(y) = cPF(y)[s 11. Let on(gi) be eligible to act at the next substage.

+

Case 5. S =

+

< is an R-strategy.

s’ then let dF,,(rn) be undefined. Declare that 5 is satisfied via z. Define us+l = and initialize all nodes with lower priority. Go to the next stage. 54. Otherwise, suppose that is in cycle (n). There are three cases:

<

+

<

+

<

Subcase 1. s 1 is not <-expansionary. Then, let En(n, w)be eligible to act at the next substage. Subcase 2. s 1is <-expansionary and A f n is correct. Then, for any y < ~ R ( < , swith ) A ~ ~ ( Y ) [t,s ]define A ~ ~ ( Y + > [11s = ~ t , S + l ( y ) with use & ~ , ~ ( = y )s 1. Let En(n,cm) be eligible t o act at the next substage. Subcase 3. s 1 is J-expansionary and A t n is incorrect at (the least) y. Put y(k(())[s] into D. Declare that y(k([))[s] requests that C have a change below it to perform the disagreement strategy. For y 2 k(<), let r(C,D;y) be undefined and for z < r(k(t))[sI, if g t ( z ) t, define gt(z) = cs+l(z).Stop cycle (n)and start cycle ( n + 1). Define gS+l = and initialize all nodes with lower priority. Go to the next stage.

+

+

+

<

Case 6.S =

< is a Q-strategy.

463

+ 1 is <-expansionary, then let C-(O) be eligible to act at the next substage. C2. Otherwise, let <-(1) be eligible to act at the next substage.
Case 7. S = x is an z,i-strategy.

x1. If z(x) t, then define z(x) as a fresh number, define 6, = initialize all strategies with lower priority, go to the next stage. x2. I f 4 X ) 4,n,W.(z(X))[SI 4= 0 = UX,S(4X>) and wx,s t w x , s ( 4 x ) ) = s:;@

x,

t%MX)),

then enumerate z(x) into B and U,. For all E and n with <-(n,m) a,if S[,(m) > z(v) then let S:,(m) be undefined. Define 6, = x, initialize all strategies with lower priority and go to the next stage. ~ 3 If . z(x) -1, n ~ ( z ( x ) ) [ $= s ] 1 = Ux,,(z(x)),then take z(x) out of B. (Note that b y the use principle, those A$,(m) undefined by the enumeration of ~ ( 7 are ) defined again because of the recovering of B 1G;,(rn).) Define 6, = x, initialize all strategies with lower priority, go to the next stage. x4. Otherwise, let ~ ~ (be1eligible ) to act at the next substage. This completes the construction. 4. The Verification

In this section, we verify that the construction described above satisfies all the requirements. First we have:

Define f = liminf,

63,.

f is the true path of the construction.

464

Lemma 4.2. If C is noncomputable and has a cappable degree, then f o r

6 c f, ( I ) 6 is initialized or reset only finitely often; (2) 6 acts only finitely often. Proof: We prove the lemma by induction. Let 6- be the immediate

predecessor of 6. By the induction hypothesis, there is some (least) stage so such that (a) 6- cannot be initialized or reset afterwards; (b) 6- does not act afterwards. Since 6 is on f , there is some stage s1 2 SO such that for all s 2 sl(6, 2 6). By the choice of so, and the fact that 6 acts only when 6 is accessible, 6 cannot be initialized after s1. If 6 is a PE-strategy or an R-strategy, let k(6) be defined at stage s2 2 s1. Then k(6) cannot be canceled later and 6 can be reset only finitely often. (1) holds.

For (2), there are seven cases: (i) 6 = a is a PE-strategy. Suppose that (2) fails at a. Then a acts infinitely often. Thus, a can never be satisfied, and whenever a acts, a does the same thing: (1) puts the number y ( k ( a ) )into D,(2) extends the definition of ga, (3) starts the next cycle. Hence, ga is defined totally. We show below that ga computes C correctly. Thus, C is computable. A contradiction. Therefore, a can act only finitely often. (2) holds. Suppose not. Then there is a stage s3 > s2 such that some x with ga(x)[s3] .J.=0, and x enters C at this stage (ga becomes incorrect at x). Suppose that ga(x) is defined at stage s. Let s4 2 s3 be the least a-stage. Then by the construction, at stage s4, (Y takes y ( k ( a ) ) [ s ]out of D ,and puts s into B , %(a)into E. Thus,

E ( z ( a ) )= 1 # 0 = @ p ( x ( a ) ) [ S ] = G p D ( z ( a ) ) [ s q= ] @E@D(x(a)). a is satisfied, contradicting our assumption. (ii)

= P is a PD-strategy.

It is a standard Friedberg-Muchnik strategy. If there is no P-stage s > s1 such that @F(z(P))[s].J.=0, then P has no further action after stage s1. (2) holds. In this case, D(x(P)) = 0 # @F(x(p)), p is satisfied. Otherwise, let

465 s3 > s2 be the least ,&stage at which @;(x(p)) $= 0. Then p puts x ( p ) into D and at the same time initializes all strategies with lower priority. By the choice of s1, x(p) remains in D and the computation @;(x(p ))is preserved forever. Therefore,

p is satisfied, and ,6 has no more actions. (2) holds. (iii) 6 = 7 is an M-strategy. Let s3 > s1 be the stage at which z(7) is defined. Without loss of generality, suppose that at stage s4 > s3, 7 observes the following equations: @?(x(rl))[s4] -1= 0 = Bs,(x(7))and l~ , , ~ , ( 4 7 ) )= W,,,, t (P,+.,(x(q)). Then 17 enumerates z(q) into B and initializes all lower prior) ) &, l~,,~,(47)). Suppose ity strategies. Thus, - ( 4 7 ) ) t ~ , , ~ , ( ~ ( r l = that at an 7-stage s5 > s4, @F(x(q))[s5] $= 1 and iJ?& lCp,,,,(x(v)) = W,,,, r(p,,,s4 (~(17)). (If there is n o such stage, then a is satisfied by the first attempt, and 7 has n o more actions. (2) holds.) Then, W , 1 ( P , , ~ ~ ( Z ( ~ ) ) changes between stages s4 and s5, and hence @: l~p,,~,(x(q))must also have a change. The only reason causing such changes is the enumeration of z(7) into B , and x(7) is less than ~ q , , 4 ( ( p q , s 4 ( x Taking ( ~ ) ) . x(7) out of B at stage s 5 recovers the computations Q: l~p,,,~ ( ~ ( 7 )to) those computations at stage s 4 , and so creates a permanent inequality between W, and q:. r] is satisfied and does not act anymore. (2) holds.

q2,

(iv) 6 = CT is an N-strategy. CT

does nothing during the whole construction. (2) follows immediately.

(v) 6 = [ is an R-strategy.

<

Suppose that acts infinitely often. Then since each cycle of acts at most once (otherwise, this cycle will find a disagreement between @ f e D and We, satisfying E, and hence, E does not act anymore, (2) holds), we know that 5 starts infinitely many cycles, and each cycle extends the definition of gc properly. As a consequence, gc is defined totally. We now show that gt computes C correctly. Suppose not. Let y be the least disagreement between gc and C. Assume that g t ( y ) is defined at a stage s4 > s2. That is, there is a (least) z confirmed as an error at stage s 4 and -y(k(<))[q] is enumerated into D and requests that C have a change below it to perform the disagreement strategy. Let sz be the stage at which A?(Z) is defined. By gc(y) # C ( y ) ,-y(k(<))[s4]’srequest is realized later and by moving out all

466

numbers enumerated into D after stage s z , we get a disagreement between @ F e D ( z )and W t ( z )successfully. As a consequence, no more cycles can be started later. A contradiction. Thus, C is computable, contradicting the assumption that C has a cappable degree. (2) holds.

<

(vi) 6 = is a &-strategy. [ does nothing during the whole construction. (2) follows.

(vii) 6 = x is a 7-strategy.

<

Let C x be the Q-strategy for which x is working. Let z(x) be defined at stage s3 > s2. Without loss of generality, suppose that at a X-stage s4 > s3, we have

@p(z(x))[s4l-l= 0 Then x enumerates z(x) into B and i.7, at stage s4, and initializes all lower priority strategies. By the assumption that has infinitary outcome, we know @ p ( z ( x ) )cannot converge t o 1 at any larger X-stage, because otherwise, x will remove z(x) from B , making [-(1) f . Therefore, Uc(z(x)) = 1 # x is satisfied. After stage s4, x does not act 0 anymore. (2) holds.

<

@F(z(x)),

c

Lemma 4.3. If C i s noncomputable and has a cappable degree, then for f. Therefore, I f I = co. any 6 C_ f , there is some 0 such that 6 - 0

Proof: Let 6 C f be any strategy on f . We only need to consider the cases when 6 is a PE-strategy, an N-strategy or an R-strategy. Case I: 6 = a is a PE-strategy. By Lemma 4.2, if C is not computable, then a acts a t most finitely often. Let s be the last stage at which Q acts and suppose that at stage s, a is running cycle (n). There are two subcases: Subcase 1: .(a) is enumerated into E at stage s. By the construction, we know that some y with g a ( y ) $= 0 enters C between SO, the stage at which g a ( y ) is defined, and stage s. Now a puts .(a) into E , and simultaneously puts SO into B , taking r ( k ( a ) ) [ s oout ] of D.The enumeration of .(a) makes E(z(a))= 1, and the removal of y(k(a))[so] recovers the computation @EeD(z(a)) to @ E @ D ( z ( ~ ) )(Note [ s ~ ] that . the enumeration of so into B does n o t change the computation @E@D(z(a))[so] because (p,(z(a))[so]< SO.) By preserving this computation, we have

E(a:(a))= 1 # 0 = @ E e D ( ~ ( ~ ) ) [=~ @ o ] E@D(z(~)).

467

a is satisfied, and any a-stage after stage s is also an a-(d)-stage. a - ( d ) g

f.

Subcase 2: a starts cycle (n + 1). In this case, a puts ~ ( k ( a ) ) [into s ] D. By the choice of s, the compu) ) not converge to 0 at any larger a-stage, because tation @ z @ D ( x ( adoes otherwise, a will act again. Thus, any a-stage after stage s is also an a-(n + 1)-stage, a-(n + 1) C: f . Case 6 = a is an N-strategy. If there are only finitely many a-expansionary stages, then after a stage large enough, every a-stage is an a ^ ( f)-stage, and hence a-(f) C f . If there are infinitely many a-expansionary stages, and after a stage large enough, a has no substrategy requiring attention anymore, then every a-expansionary stage is a u-(d)-stage. a n ( d ) f . Otherwise, there are infinitely many a-expansionary stages, and a's substrategies can require attention infinitely often. We claim that there is some i such that a-(gi) C f or a ^ ( & ) C f . Suppose not. Then for each i, ah(gi) and an(&) can be visited only finitely often. We show below that each S,,i-requirement is satisfied, and hence C has a promptly simple degree. Contradicting our assumption that C has a cappable degree. Fix i. Then we can assume that after stage SO large enough, no substrategy with higher priority can require attention anymore. Then, after stage S O , whenever S,,i requires attention, Su,i can receive attention. Without loss of generality, assume that Wi is infinite. By our assumption that a-(gi) is not on f , So,i can open gaps finitely often. Thus we can assume that after stage s1 2 SO, So,i opens no gap. Then, dom(+,,i) = dom($~,,i[s~]) is finite. Moreover, for each x E dorn($Jg,i),a:(.) converges (otherwise, Sm,i will require attention infinitely often, making a^(&) g f ) . Let t = max{cp,(y) : y E dorn(&,i)} and let s2 2 s1 be the stage with C, 1z = C z. We claim that at stage s2, S,,i is satisfied or inside a gap, because otherwise, since Wi is infinite, there will be an a-expansionary stage s3 > s2 at which S,,i requires attention to open a gap, which is impossible by the choice of s1. In the first case, we are done. In the second case, since the gap cannot be canceled, the gap will be closed at the next a-expansionary stage s4 > s2, and furthermore, So,iis satisfied by stage s4. Case 3: 6 = 6 is an R-strategy. The argument in the proof of Lemma 4.2 shows that 5 can start only finitely many cycles. Let cycle ( n ) be the largest one being started in the

c

r

468

whole construction. Suppose that cycle (n) is started at stage s1. Then, after stage s1, for m < n, no ["(m, -) can be visited again. There are two subcases:

Subcase 1: There are only finitely many J-expansionary stages. If there is some (least) y such that g&) J. and gt(y) # C(y), where gt(y) is defined by cycle (m) 5 ( n ) at stage s2, then by the construction, we will take y(k(())[s2], together with other numbers, out of D to execute the disagreement strategy. E is satisfied and hence, any J-stage larger than s2 is a <"(d)-stage. (-(d) g f . Otherwise, let s3 > s1 be the last J-expansionary stage. Then any J-stage s > s3 is also a E-(n, w)-stage. <"(n,w) g f . Subcase 2: There are infinitely many &expansionary stages. Then A:n will be defined infinitely often, and for any y, if A:,(y)[s] is defined, then A f , ( y ) [ s ] = lV~,~(y),because otherwise, cycle ( n )would start cycle (n+l),contradicting our choice of n. Thus, each <-expansionary stage larger than s1 is a ["(n, co)-stage, (-(n, co) g f . 0 Lemma 4.4. I f C is noncomputable and has a cappable degree, t h e n for any 6 c f ,

(1) I f (2) I f (3) I f (4) I f (5) I f (6) I f

6 is a P-strategy, t h e n P6 i s satisfied. 6 = q i s a n M - s t r a t e g y , t h e n M , i s satisfied. 6 = u is a n N-strategy, t h e n Nu is satisfied. 6 = E is a n R-strategy, t h e n R.6 is satisfied. 6 = is a Q-strategy, t h e n Qc is satisfied. 6 = x is a 7-strategy, t h e n Tx is satisfied.

Proof: (1)By the proof of (i), (ii) in Lemma 4.2 and (i) in Lemma 4.3. (2) By the proof of (iii) in Lemma 4.2. (3) Suppose that = = h, is total. Then there are infinitely many a-expansionary stages, and by Lemma 4.3, there is some i such that un(gi) C f or U-(di) C f . We now prove that a"(di) cannot be on f . Otherwise, dom(+,,i) is finite. Let s1 is the last stage at which &,i opens a gap. Thus, for any u-(di)-stage s > s1,there is some y E dom(l(lo,i)such that the computation @:(y) changes. Since dom($,,i) is finite, there is some (least) y E dom($,,i) such that $F(y)t, and hence h, is not total. A contradiction. Thus, uh(gi) c f , and hence, as described in the N-strategy, 1Clu,i is totally defined, and computes h, correctly. u is satisfied.

469

@FeD

(4) Suppose that = We. Then there are infinitely many [expansionary stages. By Lemma 4.3, we know that there is some (least) i such that ["(i,00) is on f . We now show that if is total, then the p.c. functional A; is totally defined and computes We correctly. First note that if A? is defined, then A? = We, because otherwise, [ will start to perform the disagreement strategy. There are two possibilities. One is that [ starts a new cycle, and the other one is that 0 performs the disagreement strategy at last. Both make [-(i, 00) not accessible anymore. A contradiction. We now show that A t is totally defined. Fix x. Let A f i ( x ) be defined at stage so. Then S,,i(z)[so]= SO. W.l.o.g., suppose that at stage s1 > SO, some strategy T > e-(i,00) enumerates a number z < SO into B and undefines A E i ( x ) . Obviously, T is below ("(i, co). Then at the next [expansionary stage s2, A t i ( x ) is redefined with use Sc,i(z)[s2]= s2. By the construction, all strategies with priority lower than T are initialized at stage s1 and cannot redefine A,'li(x)[s2] again. Since only finitely many nodes between <"(i,co) and [' have been visited before stage s2, and only these strategies' actions can undefine the newly defined A C i ( x ) ,there is a large enough stage s, at which A f i ( x )is defined and this definition cannot be injured afterwards. (Note t h a t if T is a n M or a 7 - s t r a t e g y , t h e n z can be removed f r o m B f o r t h e sake of t h e r-strategy, and if so, t h e n t h e definition of A t i ( x ) will be recovered t o A f i ( z ) [ s o ]by t h e u s e principle. Again, since there are only finitely m a n y strategies between e"(i, 00) and T, such a procedure can happen finiteZy often.) Then $= A,'li(z)[s,]. AEi(z)is defined. (5) Suppose that Wc = O f , then there are infinitely many Iexpansionary stages and so I-(O) C f . Uc is constructed by C's substrategies 'Fi, i € w,which are arranged below C"(0) by the construction of T . First, we show that Uc ST B. In the construction, when z(x) is enumerated into Uc, by x at stage SO say, z ( x ) is also enumerated into B. Note that x(x) can only be taken out by x , at stage s2 say, and such an extraction action creates an inequality

Remember that x's action initializes all strategies with lower priority, particularly, those _> Sn(l). Let s3 > s2 be any I-stage, then by the choice of s2, s3 is not <-expansionary, and so Cn(l) is visited at stage s3. This is why x cannot be initialized later, and hence the computation O f ( x ( x ) ) [ s 2=] 0

e

470

is preserved forever. <-(1) c f . A contradiction. ( 6 ) By the proof of (vii) in Lemma 4.2.

0

Lemma 4.5. F(C,D) = K .

Proof: By Lemma 4.1, r(C,D ) is a p.c. functional. By actions during 3n 1 stages, if r(C,D) is total, then r(C, D ) = K . Fix k . Let 6 = f [ k . Then 6 can only be visited after stage k . Since 6 is on the true path, by Lemma 4.2, there is some (least) stage sg such that 6 cannot be initialized or reset afterwards. Let s1 2 sg be the stage at which k ( 6 ) is defined. Then k ( 6 ) > k and k ( 6 ) cannot be canceled later. Let sz 2 s1 be the least stage such that K 1( k ( 6 ) 1) = Ks,t ( k ( 6 ) 1). Let s3 > sz be the stage at which r(C, D ; k ( 6 ) ) is defined. Then for any 1 < k ( 6 ) , y(Z)[s3] < y(k(6))[s3],and D has no change below y(k(6))[s3] afterwards.

+

+

+

D Ty(k(6))[~3I= Dss ~ Y ( ~ ( S ) ) [ S Q I . Furthermore, since C is noncomputable, there are only finitely many stages wo,v1,... ,w, such that y(k(d))[vi],i 5 n , can request C have a change below them (i.e., y ( k ( b ) ) [ v i ]are enumerated into D to lift y(k(6))). Let s4 2 v, be the least stage after which y(k(6)) does not request anymore. Then either (T is satisfied at stage s4 (one of the y(k(6))’srequests is realized in this case) or C will have no change below y(k(G))[vi] for any i 5 n. In both cases, if r(C, D; k ( 6 ) ) is defined at stage s5 2 s4, then for all s 2 s5, y(k(S))[s] = y(k(d))[s4] by the G-strategy. Therefore, r(C,D; k ( 6 ) ) 4,and hence r(C, D ; k ) 4. 0 Acknowledgement: This project is supported by New Zealand FRST Post-Doctoral Fellowship. References 1. K. Ambos-Spies, C. G. Jockusch, Jr., R. A. Shore and R. I. Soare, An algebraic decomposition of the recursively enumerable degrees and the coincidence of several degree classes with the promptly simple degrees, Trans. Amer. Math. SOC.281 (1984), 109-128. 2. M. M. Arslanov, Structural properties of the degrees below 0’, Dokl. Akad, Nauk SSSR(N. S.) 283 (1985), 270-273. 3. M. M. Arslanov, S. Lempp and R. A. Shore, O n isolating r.e. and isolated d.r. e. degrees, in “Computability, Enumerability, Unsolvability” (Cooper, Slaman, Wainer, eds), 1996, 61-80.

471 4. S. B. Cooper, Degrees of Unsolvability, Ph. D. thesis, Leicester University, Leicester, England. 5. S. B. Cooper, L. Harrington, A. H. Lachlan, S. Lempp and R. I. Soare, T h e d.r.e. degrees are n o t dense, Ann. Pure Appl. Logic 55 (1991), 125-151. 6. S. B. Cooper, S. Lempp and P. Watson, Weak density and cupping in t h e d-r.e. degrees, Israel J. Math. 67 (1989), 137 -152. 7. S. B. Cooper and X. Yi, Isolated d.r.e. degrees, University of Leeds, Dept. of Pure Math., 1995, Preprint series, No. 17, 25pp. 8. D. Ding and L. Qian, Isolated d.r.e. degrees are dense in r.e. degree structure, Arch. Math. Logic 36 (1996), 1-10, 9. D. Ding and L. Qian, Lattice embedding into d-r.e. degrees preserving 0 and 1, in “Proceedings of the Sixth Asian Logic Conference” (C. T. Chong, Q. Feng, D. Ding, Q. Huang and M. Yasugi, eds) (1998), 67-81. 10. R. G. Downey, D.r.e. degrees and the nondiamond theorem, Bull. London Math. SOC.21 (1989), 43-50. 11. R. G. Downey, A. Li and G. Wu, Every cappable c.e. degree i s complemented in the d.c.e. degrees, in preparation. 12. S. Ishmukhametov, D.r.e. sets, their degrees and index sets, Thesis, Novosibirsk, Russia, 1986. 13. S. Ishmukhametov and G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 (2002), 259-266. 14. A. H. Lachlan, Lower bounds for pairs of recursively enumerable degrees, Proc. London math. SOC.16 (1966), 537-569. 15. G. LaForte, T h e isolated d.r.e. degrees are dense in the r.e. degrees, Math. Logic Quart. 42 (1996), 83-103. 16. A. Li and X. Yi, Cupping the recursively enumerable degrees by d.r.e. degrees, Proc. London Math. SOC.78 (1999), 1-21. 17. R. I. Soare, Recursively Enumerable Set s and Degrees, SpringerVerlag, Berlin, 1987. 18. G. Wu, Nonisolated degrees and the j u m p operator, Ann. Pure Appl. Logic, 117 (2002), 211-223. 19. G. Wu, Isolation and diamond embeddings, J. Symbolic Logic 67 (2002), 1055-1064. 20. G. Wu, O n the density of the pseudo-isolated degrees, Victoria University of Wellington, School of Mathematical and Computing Sciences, 2002, Research Report, No. 02-10, 16pp. 21. G. Wu, Structural properties of the d.c.e. degrees and presentations of c.e. reals, Ph.D. Thesis, Victoria University of Wellington, 2002. 22. G. Wu, Embedding s8 into the d.c.e. degrees preserving 0 and 1, in preparation.