This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
is normal; (3) for all i, l
-
179
LENGTHS OF FORMULAS
is an abridged version of q / y . Let z be the sequence of variables of y not ... $ i - l . Then for some Boolean constants el, c2 the formula occurring in c1 +cz.qi/z is an abridged version of q / z . xi*oibeing an abridged version of ( p i , the formula xi/z*wi/z is an abridged version of q i / z . Therefore, for some operation *', the formula
xi/z*' o i / z is an abridged version of q / z . By assumption, there is no x such that q / x is of the type T,' ; hence, the formulas xi/z and m,/z have less than q distinct variables in common. The number of distinct variables of m inot occurring in $1...$i-Ixi is at least 2 * 4 P - ' - ' . q - q , i.e. at least 4P-'-'.q. If xi contains variables occurring in $l.. . i j i - , , let u be a sequence containing exactly the following variables: all the variables occurring in $' ... $ i - ; all the variables of mi not occurring in xi. Defining $ i as xi/u, q i + las wi/u,conditions (1)-(5) still hold. If xi contains no variable of $' ... $i- let u be a sequence containing exactly the following variables : ... - ; exactly one variable of xi ; all the all the variables occurring in variables of oi not occurring in $l ...$ i - l .xi.Defining again $i as xi/u and qi+' as o i / u , conditions (1)-(5) still hold. are defined; q p ..., Assume that the sequences ( q l ,..., q,), contains at least q variables. If q pcontains variables occurring in $; ...$ p - l , let x be a sequence containing the variables of $1 ... $,-'. If q pcontains no variable of $; . . . let x be a sequence containing all the variables of $; ... $,-1and exactly one variable of q,. Define $ p as q p / x in both cases. Conditions (1)-(5) hold; the formula
',
~,,*($,*..-(*,-,*~,>...) is an abridged version of q / x , i.e. q / x is of type
7;.
7. LEMMA 2. If the sequence ($1, ..., $,J is normal, if no variable occurs in more than k of the formulas t,h1 ,..., $ n and if n ( k + 1)" then there exist an integer p and distinct integers k,,..., k , such that the following holds: (1) x k l occurs in (2) if (xl,. . ., x,) is the sequence obtained from ($l,. . ., $,,) by substituting
180
L. HODES
and E. SPECKER
0 for all the variables except xk,, .. ., x k pand then deleting the formulas containing no variables then ( 4 mdq, (b) for all j , 1d jd m, the formula xi contains exactly one variable, say Xi,'
(c) the sequence (il, ..., i,) (defined in (b)) is a sequence without alternations. (The sequence ( i l , ..., i,) is said t o be without alternations iff for all jl,j,,j3the following holds: If 1 djl <j, <j, <m and ij, =ij3, then ij,= i j 2 . The sequence (9, 9, 7, 8, 8, 8, 1) is without alternations, (9, 9, 7, 8, 8, 9, 1) is not.) Proof. Let xk, be the variable occurring in $,. If m= 1 then p = 1 and k , satisfies the thesis. For the inductive step two cases are distinguished. (a) x k , occurs in none of the formulas t,hj, 2<j<(k+l)"-'+l. Putting r = ( k l),1, the sequence (G2,. .., $,.) is normal and each variable occurs in at most k of the formulas t,hj, 2 < j < r , k,, ..., k , being indices according t o the inductive hypothesis, the sequence ( k , , .. ., k p ) satisfies the thesis. (b) Assume that xk, occurs in some formula $ j , 2 < j d ( k l)m-l 1 and let h be the smallest such numberj. Furthermore, let V be the set of variables different from xk, and occurring in $; ...$h - 1 . Substitute 0 for all the variables of Y in the formulas $ h , $h+ ..., $, and delete the formulas containing no more variables. Let the resulting sequence be (ol, ..., or).The length of the sequence ($1, $h, $ h + l , ..., tjn)is at least n - ( k + l ) " - l + l . There are less than ( k + l),-' distinct variables in $, ... $ h - l , each one occurring in at most ( k - 1) of the formulas t,hl, $ h , . . ., $,. Therefore,
+
+
+
+
,,
+ l),-' + 1 - ( k - 1) ( k + l),-', r 2 ( k + 1)m-1 + 1 . r 3 n - (k
i.e.
The sequence (o,, ..., or)is normal and its length is at least ( k + l)m-l.xkl occurs in w , ; if ( k l , ...,k p ) is a sequence of incides according to the induc..., or), the same sequence satisfies the thesis of the tive hypothesis for (o,, lemma for ..., $,). 8. LEMMA 3. If q is a formula of type T;, if no variable occurs more than k times in cp and ifg > ( k then there exist m distinct variables xk,, .. ., Xkn, of cp such that is equivalent to some formula o satisfying the following condition: There exists a sequence (ao,..., o m of ) formulas such that
+
181
LENGTHS OF FORMULAS
(1) no variable occurs more than ( k - 1) times in 0,; (2) for allj, 1 < j d m , there exist Boolean constants a j , b,, cj such that o j is equivalent to aj ( b j cj.xkj)*wj-l for some operation *; (3) o is the formula w,. Proof. cp being of type zf, there exists a normal sequence ($i,..., $ p ) such that some formula
+ +
*1*(*2*.
..**,I
is an abridged version of cp. Each variable occurs in at most k of the formulas t j i , . . ., $ p . By Lemma 2, there exists a sequence x of variables of cp such that the sequence obtained from the sequence
( X I 7
(*llX,
...
9
x,>
.*.)*,lx>
by deleting the formulas containing no variables has the following properties : (1) k . m < q , (2) for allj, 1 <j < k - m ,the formula xi contains exactly one variable, say xij, (3) the sequence (il, ..., ik.m)is a sequence without alternations. A variable occurs in at most k of the formulas xi, 1 <j
n
rj + 1< i < r j
ofy; (c) for all h, j , 1< h <j < m the variables of y occurring in
]II
rh+l
$,and
n
rj+iSi
$iaredistinct.
We may assume that the variable of y occurring in 1 <j<m. Defining wo as
fl
rj+iSi
t+hi iS xkj,
$r,lY***.*$plY and for all j , 1<j < m , defining the constants aj, bj, c j and the formulas w j such that I + l*...*($rj- ,*mi-1 ) ...)/Y $rj+I*(~rj+
182
L. HODES
is equivalent to Uj
for some operation
and E.
SPECKER
+ ( b j + Cjxkj)*Oj-l
* , the conditions are verified.
9. Definition of the notion of “basic formula”: A formula cp is basic in <xi,, x i l ,..., x i , ) of type ( a l , ..., a,) iff the following conditions hold: (1) ( x i o ,..., xi,) is a sequence of distinct variables; ( 2 ) ( a 1 , . , . ,x,,) is a sequence of operations, xi, l
if
Ekf1
+(bk+l
is sum;
+Ck+lXk+l)+(Pk
+ck+,x~+l)‘cpkifak+lisproduct
VniSq.
A formula q basic in ( x i o ,...,x i , ) is of the form qn*(qn-
1*...*(’~1*(~0)
>
...
2
where q j contains the variable xi, and no other.
If rp is basic in
(.yi0, ..., s i n )of
type (a,, ..., a,) and 1
xi, 1s
/o .
equivalent to a formula basic in (sin, ..., \, .. ., si,,) of type (a,,. .., \, ..., 2,).
LEMMA 4. If cp is basic in (xi,, ..., xi,) of type ( x , , ..., cln) and n36m, m> 1, then there exist rn distinct numbers k,, ..., k,, among il, ..., i, and Boolean constants do, d l , d, such that the formula cp/xioxkl... xk, is equivalent either to m
do
or to
+ (dl + d 2 x i 0 , ) * j fl (l -k x k , ) = 1 do
+
m dlXio
i. d,
j= 1
xk,.
Proof. We assume ij=j, O<j
LENGTHS OF FORMULAS
equivalent to some formula do
+ dlx, +
183
2 111 j = 1
ejxij.
There are m distinct integers j and a Boolean constant d2 such that e j = d 2 . Therefore, there exist distinct k , , .. ., k,,, such that (p/xoxk,. ..xk,, is equivalent to do
m
+ d l x O + d2
j= I
xkJ.
Assume therefore nl < 2m; then a, is the operation product for at least 4m distinct indices k . If there exist m distinct numbers k , , ..., k, among 1 , ..., iz such that ckJ=O, 1 <j < m , then the formula cp/xoxk,...x,_ is equivalent to d,+d,x, for some constants do, d,. Assume therefore that there exist 3m distinct indices k such that a, is the operation product and c,= 1. Letting x be the sequence of the corresponding 3m variables, replacing cp/x by cp and changing notation it suffices to prove the following: If n23m, q, is b ,
for all k , O d k < n - I , (Pkfl
is
ak+l
+ coxo;
+(bk+l + Xk+l)'(Pk; (PniS cp,
then there exist distinct integers k , , .. ., k, such that cp/xoxk,. ..xk, is equivalent to some formula m
do
+ (dl + 4 x 0 ) . JIT (1 + Xk,). =l
If there exists an index k such that b, = 0 and m + 1 d k, then the formula cp/xox,...x, is equivalent to a constant. Assume therefore b,#O for all k , m + l < k , substitute 0 for xl, ..., x, and change again notation: n 2 2 m ; cpo is b ,
for all k , O < k d n - l , (Pktl
is u k + l
+ coxo;
+ (l f xk+l)*'Pk;
CpniSCP.
If all the constants a,, I d k < n - I , are 0, then 63 is equivalent to n
an
+ (b, + c , x ~ k>=
and the thesis of the lemma holds.
1
(1 + xk)
I . HODES and E. SPECKER
184
Otherwise, let i,, . .., ip-, be the indices i such that ui= 1 and 1 < i
-
i , < i2 c .. < i,
-
,.
Define a sequence ($,, ..., $ p ) as follows
Ij/h+l is $pis
ih < i Q ih + I
fl
ip-I
(1 < h
(1 + x i )
< p-2)
(1 +xi).
Then q is equivalent to the formula $ cp
+(
4 1 + *3(1
+ * 2 ( 1 + *I>>>...).
+,,
For all h , j such that 1
(c = c p ; s = [+(P - 1>1>.
Substituting 0 in $ for all the variables occurring in one of the formulas $ 2 j + l , j = 1, 2, ..., and also for the variables xi, i= 1, ..., i, (occurring in we obtain a formula x2 equivalent to c
+
$2
... $2(1 + bo + coxn)
( t = [+PI)-
Among the variables x , , ..., x,, n > 2m, there exist either m occurring in ..., t j 2 s + l or M occurring in one of the formulas one of the formulas $2, ...,tl/2t. In both cases, there exist distinct numbers kl, ..., k , such that q / x o x , ,.,x k , is equivalent to some formula
+
(l + x k j )
(dl
+ d2xO)'
10. MAINLEMMA.Let F be the primitive recursive function defined as follows F ( m , 0) = m F ( ~k ), = 4 ( k + 1 ) 6 ' * ~ F ( m . k - ' ) F ( F ( m , k - l ) , k - 1 ) . If n 2 F(m, k ) and p is a formula in the variables x,, .. ., x , none of which occurs more than k times in cp, then there exist distinct integers k,, ..., k, ( l < k j < n , 1 < j < i n ) and Boolean constants Cg, c,, c2 such that q / x k , .
185
LENGTHS OF FORMULAS
is equivalent to co
+ c1 fl (1 + X k j ) + c2 c Xk,. rn
m
j = 1
j= 1
Moreover, if cp is a p-formula then c2 =O. Proof. The proof is by induction on k , the case k=O being trivial. Putting p = ( k + 1)6’k’m, q= F(F(n2, k - l ) , k - 1) and applying Lemma 1, there exists a sequence x of variables xi(1 Q i < n) such that cp/x is either of type 7; or of type 7;. (1) If cp/x is of type T ; there exist formulas i,h2 and an operation * such that rf/l*$2 is an abridged version of q / x and such that there exist at least q distinct variables xil,..., xi, occurring both in $1 and in ij2.The variables xil,..., xi, therefore occur at most ( k - 1 ) times in t j j ( j = l , 2). Substituting 0 for all the other variables in yields a formula $;*$;. Applying the inductive hypothesis to ,;)I there exist F(m, k - 1) variables xjl, ..., xjr (r=F(un, k - 1 ) ) such that, putting y = ( x j , , ..., xj,), the formula $ ; / y is equivalent to some formula co
+ cln + c2n,
where n =
n (xj,+
l), G =
C xi,.
Applying the inductive hypothesis to $Jy, there exist m distinct variables xkl,. .., xk, among the variables xjl, ..., xj, such that, putting z = (xkl, . .., xk,), the formula $Jz is equivalent to some formula cb
+ c;n’ + c ; d ,
where .n’
= j = 1
(1
+ xkj),
G’ =
C
j= 1
xk, .
The formula $l/z is equivalent to CO
+
C1.n’
+ czn’ ,
the formula ($l*$2)/z therefore to some formula d o + dln’ + d , d . The formula ($1*$2)/z is equivalent to cp/z. (2) Assume on the other hand that cp/x is of type ~ fPuttings= . 6F(m, k - 1) and applying Lemma 3, there exist s distinct indices i,, . .., is and formulas wo,..., o,such that, putting y = (xil,..., xis), the formula w, is equivalent to cply (being the same as cp/x/y) and the sequence (coo,. . ., 0,)satisfies the following conditions : (1) no variable occurs more than (k - 1) times in 0,;
L. HODES and E. SPECKER
186
(2) for all'j, l<j<s, the formula oj is equivalent to some formula aj
+ ( b j+ cixij).wj-l
or ( b j
+ c j x i j )+
Define a sequence (I),, ..., $J of formulas as follows:
For allj, 1 dj<s, the formula aj
is equivalent to
$j
+ (bj+ cjxij)*$j-l
according to the relation of w j to
..., x i , ) ; furthermore,
or to (bi
+ c j x i j )+
The formula
$,y
$j-l
is basic in (so,x i , ,
xo is equivalent to w,. Putting t=F(m, k - l), we
$s L
O
have s> 6t. Applying Lemma 4, there exist distinct integersj,, ...,.itsuch that, putting z = ( x i , , . .., xjt), the formula $ J z is equivalent to some formula t
do
+ (d1 + dzxo) iH (1 + X j J , = 1
+ d l x , + d, 1 x j i . t
do
i= 1
The formula cp/z is therefore equivalent to some formula do
+ (d1 + d,oo/z)*H(1 + x j z ) , do
+ dloo/z+ d 2 C x j i .
We have t = F(m, k - 1); applying the inductive hypothesis to o o / z , we obtain m distinct integers k,, ..., k, such that, putting u= (xk,,.. ., xkm),the formula o o / u is equivalent to some formula co
+ cln +
C,C,
where
n=
I1(1 + x,,),
CJ =
Cxkj.
Because of n.o=O, the formula cp/z itself is equivalent to some formula
e,
+ e,?i + e 2 0 .
If cp is a p-formula, we may assume e2 = 0. 11. THEOREM. If /2>2-F(nz,2 . c ) ( F being the function defined in 10) and if cp is a formula in the variables x, ,. . ., x, of length less than c. n, then there exist integers k,, .. ., k , (1 d k , < ... < k, = it) and Boolean constants c,, cl, c,
187
LENGTHS OF FORMULAS
such that
$x?!k/,
... x k , , ,
is equivalent to m
m
Moreover, if cp is a p-formula then c,=O. Proof. Let n , be the number of variables x , , 1 n, .2c. Therefore, n,>F(m, 2c). Let x j , , ..., x J n 2 be distinct variables occurring at most 2c times in cp. Define x = ( x ) , ,..., x , , , ) and let $ be the formula cp/x. The thesis of the theorem 2 follows by applying the Main Lemma to the formula $. THEOREM (1). For every integer c there exist a formula cp such that for every p-formula $ equivalent to cp the following inequality holds : length I/J 2 c .length cp .
,
Proof. Assume IZ = 21;(2,2-c) and let cp be the formula C:= x,.If II/ is a p-formula in the variables xl, ..., x, of length less than c - n , there exist integers h, i and Boolean constants do, d, such that 1 < h < i< n and that $/x,,,x, is equivalent to do +d,(l +xh) (1 + x L ) .The formula ( p / x h , x , is equivalent to x, +x,, the formulas q, $ are therefore not equivalent. THEOREM (2). For every integer c there exists a formula Q, of the second order propositional calculus (based on the connectives conjunction and negation) such that for every formula (of the first order propositional calculus) equivalent to Q, the following inequality holds length$ 2 c-lengthQ,.
Proof. Assume n= 2 * F ( 3 ,150. c) and define formulas cpk, 1 < k < n, as follows : cp, is ( x l + .,).(I x1 + u l ) . (1 + w,), q k + l is
+
+ .k + x k + l ' k
+ x k + l w k + . k + l ) ' ( I + uk + x h + l u k + x k + l u h + O k + l ) ' f X k + l w k + xk+luk + w k + l ) .
*(I+ w k
'p, .u, is 18n - 12. There exists The length of the formula cp' defined by a p-formula cp equivalent to q' of a length which is at most 4.(18n - 12). Let Q, be the formula
188
L. HODES
and E.
SPECKER
The length of @ is less than 75.n. If (cl, ..., c,) is a sequence of Boolean constants then @/ “ l ” ’ ” ’ ’ has the c1.. .c,
value 1 iff the number of indices i such that 1< i < n and ci= 1 is congruent to 0 modulo 3. (“uk”, “tlk”, “wk” say that the number of constants among cl, ..., ck having the value 1 are respectively congruent to 0, 1, 2 modulo 3.) Let$ beaformulaoflengthless thanco(75.n). Becauseofn=2.F(3, 15O*c), there exist indices h, i, j and Boolean constants do, d,, d2 such that 1
+ d I ( 1 + xh)’(l + xi)’(1 + x j ) + dz(xh + xi + x i ) .
If (cl, ..., c,) is the sequence defined by ch = 1 and ck =0 for k # h (1
I
xl”.xfl
do + d 2 . On the other hand, @
+
I ... xl*’*xfl
c1
c,
is 0,
and t,b are therefore not equivalent.
@/z:‘*‘xy...c,
is 1; the formulas @
References 1. L. HODESand E. SPECKER, Elimination of quantifiers and the length of formulae, Notices Am. Math. SOC.12 (1965) 242. 2. L. HODESand E. SPECKER, Elimination von Quantoren und Lange von Formeln, Abstract J. Symb. Logic. 3. 8. I. NEEIPORUK, A Boolean function, Dokl. Akad. Nauk SSSR 169 (1966) 765-766, Engl. transl.: Soviet Math. Dokl. 7 (1966) 999-1000.
A DECISION PROCEDURE FOR THE WEAK SECOND ORDER THEORY OF LINEAR ORDER H. LAUCHLI Zurich “Linear order” refers to the general theory of the axioms (a) u < u A u < w+ +u<w, (b) U < U A U < U - U = U , (c) u < u v u < u . “Weak second order” (WS) theory (better : “Monadic weak second order theory”) means, roughly speaking, first-order theory extended by the concept “finite set of individuals”. Thus, the order type o of the natural numbers can be characterized by a WS-sentence as follows: “There is no greatest natural number and for every natural number, n, there exists a finite set, X , of natural numbers such that k E X iff k
190
n. LAUCHLI
KO-categorical, finitely axiomatizable. Let C‘, FA’ denote the corresponding classes for WS theory. Then C c (FA n M ) c M and M = F A f c C’, where c denotes proper inclusion. M is too small for strong second order theory: o1for instance, the least non-denumerable ordinal, is not strong second order equivalent to any denumerable order type. Then there are many strong-second-order-discernible kinds of non-denumerable “shufflings” (see section 2) of a given finite set of order types.
1. A decidability criterion We consider the first-order language, L, of a finite number of predicate letters. The set At, of atomic formulae with variables among ul, ..., uk is finite. Let P ( X ) denote the power set of X . The sets T,,,, defined by TOk= P(At,) and c+l,k=f‘(Tfl,k+l) are hereditarily finite. Be A a relational system of the similarity type of L, x = ( x l , ..., xk) a sequence of elements x , ~ l A lA, the empty set (sequence). We define
.>
tO,(A,x) fn+l,k(4
=
{4: 4 E At, and A k 4 [XI],
= P,,,k+l(A
x*Y>:YEIAI)
(where x * y denotes adjunction of term y to sequence x),
h(A>= h O ( 4
4.
tnk(A, x), “the nk-type of A , x”, is an element of Tnk.&(A) is called the n-type of A . Be Cl a class of relational systems of the similarity type of L. We write t;O. for ( [ , , ( A ) AGO.). : CRITERION. The $rst-order theory of C is decidable if the sets ttC efectively depend on n. Since the sets t f K are hereditarily finite, there is no question about the meaning of “effective dependence”. Note that since T,, (= Tfl0)effectively depends on n and t E T,,, (*) ttCl effectively depends on n iff the predicate ‘ ‘ s G t t K “ is decidable. The criterion is based on results by FrajissC [4]. We sketch a proof: Let t be an nk-type, 4 a formula. We define the predicate sat(t, 4) by: (i) If 4 is , if 4 is 41A 42(41v 42,i41),then sat (t, 4) atomic, then sat(t, 4) iff 4 ~ t(ii) iff sat(t, q51) and sat(t, q5J (sat(t, q51) or sat(t, 4& not sat(t, qb,)), (iii) if 4 is 3u4, (Vu4*) then sat(t, 4) iff sat(s, 4J for some s E r (all s ~ t )The . predicate “sat(t, 4)” is decidable, since t is hereditarily finite.
191
WEAK SECOND ORDER THEORY
Let A be a relational system, x an Idl-sequence of length k, 4 a prenex formula with free variables among u l , ..., uk and with a prefix Q l U k + l Q 2 U k + 2 ... Qnuk+“ (Qi are quantifiers). A straight forward induction shows that
A In particular, if
4 [XI
iff sat(t,,(A, x),
4).
4 is a sentence, A k4
iff sat ( t n ( A ) ,4 ) .
If E is a class of relational systems, (1)
K k 4 iff sat($,+) for aII s ~ t ; E .
On the other hand : Given S E A and x (of length k ) ,
mk,a formula dScan be found such that for all
A k 4, [x]
iff
t,, ( A , x) = s .
Therefore, if SET,, (2)
s~t;O.
iff not
Ek i qbs.
The criterion follows from (l), (2) and (*).
2. The WS theory of linear order The WS theory is viewed as the first-order theory of a special class Gt (the “standard models”) of relational systems. The similarity type is given by a unary predicate E and two binary predicates S, 0. A relational system A = ( / A1, EA, S,, 0,) belongs to Gt iff there is a linearly ordered system ( U , <), Uf A , such that (i) IAl= F ( U ) , the set of all finite subsets of U , (ii) EA(x)holds iff x = A , (iii) xS,y iff x s y ,(iv) x0,y iff, for every U E X - ~there is V E Y - xsuch that u < v . The set U= U IAl will be denoted by d. The singletons in I A Jcan be characterized in terms of s,. Furthermore, U < U iff > .{ O,{U>, and U E X iff { u } S,X. Thus the first-order theory of A = (IAI, EA, S,, 0,) is of the same strength as the WS theory of (d, <>.The choice of the primitive constants E, S and 0 is motivated by technical reasons. The isomorphism type of A is uniquely determined by the order type of (2, <), and vice versa. A will denote the order type of (d, <), and W S ( a ) , the “WS theory of the order type a”, will denote the set of all formulae 4 such that whenever A E G and ~ K = E , then A 14. Two order types a, p are said to be WS equivalent if WS(a)=WS(/?).The Skolem-Lowenheim
192
H. LAUCHLI
theorem holds for WS theory (even for a stronger theory, see [6]): Every order type is WS equivalent to some countable order type. Let R be the set of rationals. The shuffling aF of a finite set F of order types is defined by a F = x { a , : ~ E R(the ) summands c(, arrangedin the natural order), where ~ , E F for all r and { r : @,=a} is dense in R for all ~ E FaF . does not depend on the particular partition o f R into dense subsets. Let M be the least class of order types which contains the order type 1 and is closed under the operations a+/?, a * o , a * o * , OF ( F finite). Let ‘93 denote the corresponding subclass of Gt. THEOREM 1. t;W effectively depends on n. THEOREM 2. t :Gt = t $Ul. By the decidability criterion of section 1 : COROLLARY. The WS theory of linear order is decidable. 3. Proof of Theorem 1
We show that to each of the operations a+/?, a v o , a-w*, oF corresponds an effective operation on the n-types. Notation: P ( X ) is the power set of X,F ( X ) the set of all finite subsets of X , X x Y the Cartesian product of X and Y, f o g the composition of the functions f and g ; we write f ” X f o r {f ( x ) : X E X } ,x * y denotes adjunction of term y to the sequence x, ( y ) is the one-element sequence with term y . The elements o f the set At, are the formulae Eui, viSuj, uiOuj, where 1< i , j < k. At, = A . n-types are invariant under isomorphisms. t,(a) will denote the n-type of the systems AEGt with A=a.
3.1. LEMMA 1. t,(l) efectively depends on n. The proof is immediate since 1 is a finite order type. By way of example: {a), then If
a=
t,,(A, ( { a } , A ) >= {Eu,, ulSul, UZSUZ, U&I,
UIOUI, V Z O ~UZZ ~O U I )
and
b ( l ) = f2(A)
= {{t02(’%
3.2. The binary operation t+,,s
< AA>)?t o z ( A ( A , {.}>>>, {t02(A, <{.>, A>>,fez(‘% ({.>, {.>)>>> *
+,,
on T,,is defined thus: and i , j < k } , t ’ ~ t and S ’ E S } .
= ( t n s ) u {“uiOuj”: “uj0ui”$s
t + n + l , k= ~ {t’
+
193
WEAK SECOND ORDER THEORY
n
The order-sum A+B, where A , BEG;^, is defined in a natural way ( A +B= (dx (0)) u (B x { l})). Let x be a k-sequence of elements of IA +BI, xlA = ( x l l A, ..., xk l A ) the restriction of x to A (if ~ E I A + B I then x l A = {u:
(U,O)EX)).
LEMMA 2. tnk(A+B, x)=t,k(A, xlA)+nktnk(B, X l B ) . Proof. We have i EA(xilA) and EB(xilB>, a) E A + B ~ iff xiSA+BXj iff (XilA) S ~ ( x j l A ) and (XiIB) s B ( x j l B ) , x~OA+BX~ iff either (xilA) O , ( x j [ A ) and OB(xjlB>, Or not ( x j l B ) OB(xilB)* b) The function defined by f ( x ) = ( x l A , x l B ) maps IA+BI one-one onto IAI x PI. The lemma for n=O follows from a), the induction step n, k + l+n+ 1, k from b).
COROLLARY 2.1. t,(a+fi)= t,(a)+n,t,(/3). 3.3. The functions fin!, finn:T,+l+Tn+l are defined by: fin: (t) = t , fin!"(t)=fin;(t)u { r + , , s : rEfinf:(t) and s ~ t } , fin,(t) = finr(t), where m = ,uh(fin;+'(t) = fin!(t)).
(m exists since fin!(t)cfin(t)!+' E T,, =finite.) fin;+'(t )=fin!(t) implies finh,"((t)=finh,+'(t). Therefore, fin,(t)= (fin!(f):/z<m}. That is,
u
+
LEMMA 3. fin,(t) is the set of alljnite sums s1 ,'sZ to the left) with s , ~ t .
+ nl.. . +
(associated
3.4. Let n be a permutation of (1, 2, ..., k } . Let Subst"(4) denote the formula obtained from 4 under substitution of variables ui+uni, i= 1, 2, ..., k . Let n+denote the extension of 17 to (1, ..., k + l } leaving k + 1 fixed. G: : Tnk+Tnkis defined by G & ( t ) = {$: Subst"(d)€t},
Gf+1 ,k (t , = GEk++I . Let 17x=<x,,,
..., xnk).
LEMMA 4. tnk(A, nX)=G$(t,k(A, x)). The proof is straight forward.
194
H. LAUCHLI
3.5. The functions FA:Tnk-+Tn,k+l and Fn;: FOfk(t) = t
i
U { “ E U k + 1”) U ( “ U i s U j ” :
u {“ui0uj”: i
=
k
+1
=k
or
TZ,kfl+Tnk
+1
Or
“ E u ~ ” Et ,
are defined by:
“EUi”E
t,
and j < k + I} and j < k 11,
+
FO;k(t)=t- {formulae involving u,+,>, 1,k
(1)= (G$+
FflQl,k(t)
2 OFnfk+
= (FnTk+
oCEkf2)“t
Let x be of length k and LEMMA tnk ( A>
x).
5.
F,f,(titk(A,
I
where ll is the transposition k
+1
c*
k
+2.
IAl.
X))=fn,k+l(A,x*A),
and
Fni(tn,k+l(A,X*y))=
In particular, F f l i ( t f l l ( A(,y ) ) ) = t n ( A ) . The proof of the lemma is straight forward.
WEAK SECOND ORDER THEORY
hypothesis give
c
195
0
t,l(
'%,) = G
i=h+l
( % ( W f l + 1 ( 4 ) ) ) ~
Therefore, by Lemma 3, tn+l(a.w>= ~ , + l ( t , + l ( ~ > ) .
3.8. altf:, altn:Tn+,x Tnl+T,,+lare defined by alt; (s, t ) = { t ) , alt;+'(s, t ) = altf:(s, t)u ( r +,,s' + , , t : rEaltf:(s, t ) and S ' E S } , alt,(s, t ) = altr(s, t ) , where m = ph(alt;+'(s, t ) = altf:(s, t ) ) . (Note that T,+, = Tn+l,o,while Tfll= T,,,.) LEMMA 8. alt,(s, t ) is theset ofalljinite alternating sums t+,,s1 f n l t + , , . . .
... + n l ~ h + , l l twith h a 0 atzd s i ~ all s i
1( r ) =
altfl(U r , G ( o f l ( f C r N* )
LEMMA 9. I f F is ajinite set of order types then t,(aF)=o,(t:F). Proof analogous to the proof of Lemma 7. 3.10. R!,R, are the following subsets of T,:
fc
R;"
=
{ t f l ( l > >>
= R f : u{s +,ot:
s, t E R ; }
u { ~ , , ( t )t:E R i ) u (an*( t ) : t E Rh,) u {a,(r): r E R f : } , R , = R r , where rn=ph(Rf:+'=Rf:). LEMMA 10. t t M = R,. Proof by Corollary 2.1, Lemmas 7 and 9. Since all operations introduced above are effective, this completes the proof of Theorem 1. 4. Proof of Theorem 2
Essentially, the proof can be found in [ 5 ] . pp. 111, 114, 11.5. We reformulate the necessary lemmas in the present notation and point out if neces-
196
H . LAUCHLI
sary how the proofs have to be modified. The numbering of the lemmas corresponds to the numbering in [ 5 ] . LEMMA 2‘. T, isfinite for each n. Let A , E G t for Z E I Given . a linear order relation A , is defined in a natural way.
< on I, the order-sum
XI
LEMMA 3’. Zft,(A,)=t,(B,), all ~ € 1then , t,(xIA , ) = t , ( x , B,). We prove the following generalization: Let x, y be k-sequences with x i ~ I C A l yi€ICB,l. l, Then (*)
if
tnk(A,,xlA,)
then
= tnk(B,,
ylB,),
=tnk(x
tnk(x
B,?Y ) .
(The lemma is the special case k=O, x = y = A . ) Proof. For n=O, (*) follows from t o k ( C A,, x) = { t O k ( A lxlA,):z~Z}u , {“uiOui)’: there is ~ ~such € that 1 “UjOui”$tOk(A,,,, xlA,,) and “ t @ j ” E t O k x x (A,, xlA,) for all z 2 l o } , which is an easy consequence of the definitions involved and the fact that the sets x i are finite. Induction step. Let t n + l , k ~ x ( A , , x l A , ) = t , + l , k ( B , , ylB,), all ZEZ. Then for all I and for every a , ~ l A , l there is b,EIB,I such that
n
(I)
tn,k+ 1
*
=
tn,k+ 1
(Bi,(ylBi) * b i )
Using the fact that “E” is one of our primitive predicates, an induction shows that in (l), either both or none of a,, b, are empty. Therefore, if a,=alA,, all z, for some a ~ l C A , [ ,and the b,’s are chosen to satisfy (l), then there is aJinite set b such that b,=blB,, all z. Therefore, for every a ~ l x A , I there is b E l x B,I such that for all ZEZ, tn,k+l(A,,(xlA,)*(aIA,))
= tn,k+l
( B ~ 3
(YIBc)*(blB1)).
Hence, by induction hypothesis, for every a ~ l A,I x there is b ~ l B,I x such that t n , k + l ( x A c ) X * a ) = t n , k + l ( C B , , y * b ) . Therefore t n + l , k ( C A t , X ) = t n + l , k X x
Proof by Lemma 3‘.
LEMMA 8‘. If the order type of every bounded segment of a given denumerable ordered set A is good, then the order type of A is good.
WEAK SECOND ORDER THEORY
197
LEMMA 9’. Every order type is good. Up to an obvious change of notation, the proofs are verbally the same as in [5]. (The Skolem-Lowenheim theorem is available in WS theory and, if WS(a)=WS(P)then t,(a)=f,,(P). The occurrences of IAl in [5] have to be replaced by d.) Lemma 9‘ establishes Theorem 2. References 1. J. R. BUCHI,Transfinite automata recursions and weak second order theory of ordinals, in: Logic, Methodology and Philosophy of Science, ed. Y . Bar-Hillel (North-Holland Publ. Co., Amsterdam, 1965) pp. 3-23. 2. J. E. DONER, Decidability of the weak second-order theory of two successors, Am. Math. SOC. Notices, November 1965, 65T-468. 3. A. EHRENFEUCHT, Decidability of the theory of the linear ordering relation, Am. Math. SOC.Notices 6, No. 3 (1959). 4. R. F R A ~ SEtude S ~ , de certain opkrateurs dans les classes de relations, difinis a partir d’isomorphismes restreints, Z. Math. Logik und Grundl. Math. 2 (1956) 59-75. 5. H. LAUCHLI and J. LEONARD, On the elementary theory of linear order, Fund. Math. 59 (1966) 109-116. 6. A. TARSKI, Some model-theoretical results concerning weak second order logic, Am. Math. SOC.Notices 5 (1959) 550-556.
STRUKTURZAHLEN IN ENDLICHEN RELATIONSSYSTEMEN W. OBERSCHELP Hannover 1. Einleitung Uber einer endlichen, nichtleeren Punktmenge, die 0.B.d.A. als N = { 1, ...,n } gewahlt werden kann, werden wie in [ 131 Relationssysteme ‘31= ( N , RY’, ..., Rlt’, ..., RY’,..., RE’) betrachtet. Dabei habe die Relation RY) die Stellenzahl i, wahrend j als Unterscheidungsindex dient. z = [ p l , ..., p,,,] sei der Typ von ‘31. ‘31 und %’ rnit gleichem Individuenbereich N und gleichem Typ z heiljen isomorph, wenn eine Permutation n €Gnexistiert, welche jedes RY’ in das entsprechende RY’ uberfuhrt. Gesucht sind asymptotisch auswertbare Formeln fur die Anzahl S(n, z) der nicht-isomorphen Relationssysteme uber n-elementigem Bereich N rnit dem Typ z. Dieses Strukturzahlproblem ist bereits von Carnap [4](S. 124) aufgeworfen worden, aber nur fur den Fall rn = 1 behandelt worden. Es soll hier gelost werden fur sog. reine Relationssysteme, d.h. fur Systeme rnit Relationen nur einer Stellenzahl c. Ein solcher Typ z = [O, ..., 0, p,, 0,..., 01 soll abkiirzend rnit z = (c, p,) bezeichnet werden. Die Carnapsche Problemstellung ist von Davis [5] aufgegriffen worden rnit dem Resultat einer (asymptotisch nicht direkt auswertbaren) Strukturzahlformel Fur S(n, ( B , 1)). Harary [8] erkannte, daB dieses Resultat als Spezialfall der allgemeinen Abzahlungstheorie von Polya [ l l ] zu deuten ist, einer Theorie, die in letzter Zeit insbesondere von De Bruijn [l, 21 fortentwickelt worden ist. Harary [9] gab ohne !. zur Beweis die asymptotische Beziehung S(n, (2, 1)) ~ 2 ” ~ / nMethoden genaueren Abschatzung finden sich bei Oberschelp [lo] (5 4). Als Ergebnis sei z.B. genannt n!
1 (2n2 - 2n)
1 (32n4 - 170 3n3 -t + 24n -
+ 288n2 - 149 3n) + 0 199
(2n’ 1) Tn
.
200
W. OBERSCHELP
In dieser Arbeit sollen unter Benutzung der erwahnten Theorie von Polya asymptotische Anzahlformeln fur S(n, (a, pL,)) bei beliebigem a und po gegeben werden. Dabei werden die Ergebnisse interpretiert als Aussagen uber die mittlere Gr4J3e der Automorphismengruppe reiner Relationssysteme %. Fur Stellenzahlen 0 > 1 erweisen sich fast alle solche Relationssysteme als starr, d.h. sie besitzen nur die triviale (einelementige) Automorphismengruppe. Sei Z(n, z) die Zahl der Relationssysteme uber N vom Typ z ohne Identifikation isomorpher Systeme. Z ( n , z) ist gleich der Zahl der Zustandsbeschreibungen (state descriptions) von Carnap (z.B. in [4], ff IBA). Trivialerweise gilt die Formel
n,
1 Smnm Z ( n , z) = 2O=‘ , wenn s = [pl,. . . , , u r n ] .
Fur die durchschnittliche Zahl s(n, z) zueinander isomorpher Relations-
Die Automorphismengruppe 9%von %, eine Untergruppe der symmetrischen Gruppe 6,mit der Ordnung g , zerlegt die 6,in n ! / g Nebenklassen. Alle zueinander isomorphen verschiedenen Relationssysteme entstehen aus einem durch Ausubung je einer Permutation a m genau einer Nebenklasse auf dieses eine Relationssystem. Mithin gilt fur die “mittlere Ordnung” g(n, z) von 9%die Formel g(n, z ) = n ! / s ( n , 7). Da l,
(n,z) < S ( n , S) ,< Z ( n , 7).
Die oben erwahnte Starrheit fast aller Relationssysteme im Falle n> 1 zeigt man, indem man nachweist, dalj hier fur n+ co die asymptotische Beziehung g(n, z)-1, also S(n, z ) - Z ( n , T ) / n ! gilt. Es sei noch erwahnt, dalj unsere Uberlegungen aufgefaljt werden konnen als eine quantitativ-finite Variante von Bestrebungen der modernen MetaMathematik, welche sich das Auffinden von Modellen mit grol3er Automorphismengruppe zum Ziel gesetzt haben *.
2. Anwendung des Polyaschen Satzes auf das Anzahlproblem Man kann ein reines Relationssystem % vom Typ z= (a, p) uber N vollstandig beschreiben durch ein Diagramtn in Form einer p-zeiligen und nu-
* Man vergleiche z.B. [ 6 ] .
201
STRUKTURZAHLEN
spaltigen Inzidenzmatrix in den Zahlen 0 und 1 . Die Zeilen entsprechen den o-stelligen Relationen R,,..., R, aus %, die Spalten den o-Tupeln xl, ..., x,, von Zahlen aus N in irgendeiner festen lexikographischen Anordnung. uik= 1 bedeute, dafi die Relation Riauf das k-te o-Tupel zutrifft, entsprechend bedeute 0 das Nicht-Zutreffen. Bei dieser Darstellung erscheint ein reines Relationssystem als eine Folge von sog. Elementarkonjigurationen, in diesem Falle von Spalten. Unter der Sturke einer Spalte sei die Komponentensumme verstanden, under der Starke eines Relationssystems die Summe der Starken aller Spalten. x , ...x,, Rl
3
RP
Das Efementarpolynom ist eine (formal bis Unendlich erstreckbare) Potenzm reihe E(z) = evzy,
1
v=o
deren Koeffizienten e , die Anzahl der Moglichkeiten angeben, eine Elementarkonfiguration (Spalte) der Starke v herzustellen. Da dies offenbar auf (t) Weisen geht, gilt
c (3 m
E(2) =
zv = (1
+ z)".
v=o
Da sich jedes reine Relationssystem aus nu solcher Spalten bestimmt, wiirde sich ohne Rucksicht auf Isomorphie-Identifikationen ein Polynom A n , , ( z )= E(z)"O -- (1
+
c m
=
Z)@
v=o
u,zv
mit
a, =
re">
ergeben, wobei a, die Zahl der verschiedenen Relationssysteme der Starke v angibt. Wir interessieren uns hier jedoch fur die Zahl der Isomorphie-Klassen der Starke v, d.h. fur das Polynom m
wobei S,(n, T) die Zahl der nichtisomorphen Relationssysteme uber N vom Typ z mit der Starke v angibt. Allerdings sol1 hier das asymptotische Verhalten dieser Zahlen selbst nicht untersucht werden *, sondern nur die Ge-
*
Vgl. hierzu irn Falle r = (2, l > in [lo], § 5.
202
W. OBERSCHELP
samtzahlen
c S,(n,
Bna
S ( n , 7 ) = &(1)
=
v=o
z)
sind Gegenstand dieser Untersuchung. Durch ubergang zu einem isomorphen Relationssystem vermoge einer Permutation ~ € 6 erfolgt , ein Austausch gewisser Spalten von '21, also eine Permutation II uber einer Menge von nu Elementen. Diese Permutationen IZ bilden die sog. a-Tupelgruppe, bezeichnet mit Gz, offenbar wie die 6, eine Permutationsgruppe der Ordnung n!. Zur Anwendung der Polyaschen Theorie hat man den sog. Zykelindex der 6:zu betrachten. Unter dem Zykelindex Z ( 9 ) einer Permutationsgruppe 9 der Ordnung g iiber n Elementen versteht man ein formales Polynom in n Variablenf,, ...,f, Z ( 9 ) :=
1
-
9
1
f P ' ...f,"".
R
€9
Dabei ist p i die Zahl der Zykeln von n mit der Lange i. Fur die der Permutation 71 zugeordnete Partition der Zahl n, geschrieben als p (n): = (pi, ..., p n ) gilt also ipi=n. Fur das gesuchte Polynom B,,,(z) liefert nun die Polyasche Theorie im Fall reiner Relationssysteme den
xr=,
SATZ1: Bn,
( z ) = Z (G:)
If,/'
(~'11
Die in eckigen Klammern angedeutete sog. Polyasche Einsetzung ist dabei so zu verstehen, da13 fur jedes Vorkommen vonfi im Zykelindex Z(G:)der a-Tupel-Gruppe das Polynom E(z') einzusetzen ist. Damit steht auf der rechten Seite tatsachlich ein Polynom in z. Da E ( z) durch die angedeutete triviale Elementar-Kombinatorik soeben explizit angegeben worden ist, steht und fallt die Auswertung der in Satz 1 gegebenen Formel mit der numerischen Berechnung von Z(6:). Beim Beweis von Harary [7] fur Satz 1 wird die Polyasche Kombinatorik fur solche Problemkreise wie den vorliegenden aufgeschlossen. Fur die Gesamtzahl der Strukturen (ohne Rucksicht auf Starke) gilt das KOROLLAR :
203
STRUKTURZAHLEN
Es ist namlich S(n, (a, , U ) ) = B ~ , ( ~ , ~und > ( ~E(Ir)=2". ), Das Schema Q (17) :=(Pl, ...,P,,) zu 176 G:, also das Schema der Exponenten im Zykelindex 2(63 entsteht aus p(n)= ( p l , ..., p,) in leicht ubersehbarer Weise, die bei Oberschelp [lo] (9 2) genau beschrieben worden ist.
3. Auswertung der Polya-Formel fur reine Relationssysteme rnit a > 1 Es sol1 jetzt das asymptotische Verhalten von S(n, 2 ) fur n+ co untersucht werden. Dabei fuhren die Falle a = 1 und a > 1 zu wesentlich verschiedenen Ergebnissen. Es sol1 zunachst der weniger triviale Fall a > 1 behandelt werden. Die grol3tmogliche Ordnung einer Automorphismengruppe von % ist r ( n , z ) = n ! , unabhangig von 2. Z.B. hat ein Relationssystem, welches nur aus Allrelationen besteht, die volle 6, der Ordnung n! als Automorphismengruppe. Andererseits gibt es stets Relationssysteme rnit der trivialen Automorphismengruppe (sog. starre Systeme), fur die also die kleinstmogliche Ordnung y(n, z)= 1 ist. Beispiele hierfur liefern z.B. Relationen vom Typ einer Ordnung im Sinne von < uber N . Fur die mittlere Ordnung der Automorphismengruppe kann man also zunachst nur 1
(n - 2)"
+ +(nu - (n - 2)") = $(nu + (n - 2)")
= nu
- a n a - l + a ( 0 - 1) n"-z(l
+ (c - 2 ) O(t)).
204
W. OBERSCHELP
Insgesamt ist also der Anteil der Transpositionen
Hierbei hat O(l/n) die Form
__ -
2 +-.,-----a-3 2(Cr-3)(0-4) --++ ( C r - 3 ) ( o - 4 ) ( a - 5 ) 3n 3n2 1 5n3 6!
c) Sei ZK,, derjenige Teil der Summe im Korollar, Abschnitt 2, der zu allen 17 gehort, welche von n induziert werden mit p 1 (n)=n - K (0 < K
1) Die Anzahl der n mit p (n)= (n - K, p 2 , ...,p,) ist bekanntlich* (12
- K)!
n! n! <2 p z p 2 !... nPnp,! ( n - K ) ! '
2) Die Anzahl der Partitionen der Zahl n in der Form p = (n - K , p 2 , . ..,p,) ist kleiner oder gleich 2". Denn alle diese Partitionen miissen einer Partition p = (0, p 2 , ..., p,) der Zahl K entsprechen, und davon gibt es bekanntlich weniger als 2". 3) Fur die Summe der Exponenten gilt nu
~ P i , < P+l ~ ( 2 ~ 2 + 3 ~ , + . . . + n " p , , ) + =+ ~ (1n " - P 1 ) = + ( n " - f - P , ) . 1
Nun ist aber PI = (n - ICY,denn wie in b) sind diejenigen o-Tupel, welche bei 17 unverandert bleiben, genau diejenigen ( n - icy Stuck, welche nur die n - IC bei n nicht permutierten Elemente aus N enthalten. Also ist
*
Vgl. [12], S.67 (1).
205
STRUKTURZAHLEN
Aus I), 2) und 3) folgt
Demnach ist
) --_
2n
K
21rn"
- n!
(2n)" 2+KWnb-'(l+0(l))
wobei die o-Konstante noch u.a. von K abhangt. Wir benotigen aber noch eine gleichmaI3ige Abschatzung in K . Der Exponent im Nenner lautet anders geschrieben ICya- l ) ( c - 2 ) 1-KfJ- I
,yp 2
-
(
n
-~
2
+ -5n
3!
Die Klammer, deren Wert mit K bezeichnet werde, hat die Form
Es sol1 gezeigt werden, daI3 K groI3er ist als eine von positive Konstante, namlich 1/20. x ) 1st 0 < IC < n/a, so wird 1a - 1 K>l-----.. 0
2
1 (a - 1) (a - 2) a2
____
2-3
IC
und n unabhangige
1 (a - 1) (a - 2) (c - 3)
... >
2-3.4 1 1 1 1 1 I--+---- ...--~ > o . 2 2 ~ 4 8 20
a3
p) Sei K >n/a. Zunachst ist wegen n/lc 2 1 : K > (1 - (1 - k-/n)")/o.Nach der Formel (1 - ~ / y<)e-r~ fur y 2 x 2 0 gilt wegen n > K > 0 :(1 - Ic/n)"<e - K ,also (1 - ~ / n ) " = ( l --~/n)"~'~n<e-uK'n. Also ist K>(1 -e-uK/n)/a. Da x/n> l/o, so ist e-uK'"<e-l, also 1 -e-uK'n> 1 -e-'. Damit konnen wir die obige Ungleichungskette fortsetzen : K > (1 - e- ')/a > 1/2a, denn es gilt e-' <+. Damit ist K > 1/2a allgemein bewiesen. Insgesamt gilt, daI3 der Exponent im Nenner der Abschatzung fur ,ZK,n groDer oder gleich $p"-ist fur alle IC mit 0 < IC
'
206
W. OBERSCHELP
Damit steht die Abhangigkeit der Abschatzung von K "ganz auDen". Um nun die Restsumme aller ZK,nfur rc>3 abzuschatzen, teilen wir sie (unter der Annahme, daB bereits n > 4a ist) in zwei Teile:
Fur n >,N o (a, p) ist wegen a > 1 dann 2n/2*""-- <4, so daB der hintere Ted gleichmaDig in K durch die geometrische Reihe abgeschatzt werden kann :
Dieser hintere Teil ist also von kleinerer GroBenordnung als der Term nach b). Die endlich vielen Glieder der vorderen Summe sind einzeln ebenfalls von geringerer GroDenordnung als der Term nach b). Denn nach der Anfangsabschatzung fur ,ZK,nist 2"nU (2nY ZK , l l < - ! 2 t w o n = - i( 1 +o<;>, ' wobei die 0-Konstante von K (und a) abhangt. Da ~ 3 3 so, ist dies aber von kleinerer GroBenordnung als der Term 28nU n ( n - 1) 2pu(0- l ) n ' - 2 ( l + ( o - 2 ) o ( l / n ) )
-.-
-
n!
2
.
2pun"-
1
nach b). Insgesamt gilt also SATZ
2.
n ( n - 1) ~
mit
0
(:) -
=-
2 -
3n
2~u(u-1)"~-2(l+(b-2)0(l/n))
--
-
2pan=-
1
a---
0-3
+ -->- + (a - 4) 0 3n
Im Sonderfall a = 2 ergibt sich damit SATZ3.
~
-
C 3 )
.
207
STRUKTURZAHLEN
1 2 2 2 2 10 8 10 3 104 8.5333 x 10' 1.0133 X 4 3044 2.7307 X lo3 2.9867 x 5 291 968 2.7962 x lo5 2.9054 X 6 96928 992 9.5450 X lo7 9.6848 x 7 112282908928 1.1170 x 10l1 1.1227 x 8 458297 100061728 4.5751 X lOI4 4.5829 X 9 6.6666 x 10l8 6.6630 x 10l8 6.6666 x 10 3.4939 x 1023 3.4933 x 1023 3.4939 x 11 6.6603 x loz8 6.6600 x loz8 6.6603 x 12 4.6557 x 1034 4.6557 x 4.6557 X
lo2 lo3 lo5 lo7 loll
l0ls 1023 loz8
z o , n -t Z 2 , n
I2
ZO.
1 2 3 4 5
4 4 4 136 128 136 44224 4.3691 X lo4 4.42027 x lo4 179228736 1.7896 x lo8 1.79219 x lo8 9383939974144 9.3825 x 1012 9.38393 x 10l2
I 2 3 4 5
8 2080 22386 176 11728 394650624 3 14824619 911 446 167552
1 2 2 136 3 22377984 4 768614354122719232 5 354460798875983 863 749270670915141 632
ld
8 2048 2.23696 x lo7 1.172812 X 1013 3.1482443 x 102"
2 128
1 0.8000 0.8205 0.8970 0.9577 0.9847 0.9948 0.9983 0.99946 0.99983 0.99995 1.Ooooo
1 1 0.9743 0.9812 0.9951 0.99916 0.99991 0.99998 1.ooooo 1.OOoOo 1 .m 1 .m
ZO.n
S
1 0.9412 0.9879 0.9985 0.9998
1 1 0.9995 0.9999 1.moo
8 2080 2.238601 x lo7 1.17283924 x I O l 3 3.1482461984 x lozo
2 136 2.23696 x lo7 2.237781 x 107 7.686143364 X 1017 7.6861435358 x 1017 3.544607988759775x 3.544607988759838626x
208
W. OBERSCHELP
1 2 3 4
4 32896 3 002 399 885 885440 14 178431955039 103827 204 744901 417 762 8 16
1
2 32 896 402975273205975947935744
2 3
4 32 768
3.002399751 x 1015 1.4178431955039102644x lo3’
32 32768 4.02975273204876 x loz3
Naturlich ist es leicht moglich, diese Abschatzungen weiter zu verscharfen, indem man z.B. Z3,n noch explizit berucksichtigt und die Restabschatzung erst bei ~ = beginnen 4 lafit. Aber auch die hier entwickelte Approximation ist schon enorm genau. Zahlenbeispiele. Die exakten Zahlen S(n, z) sind mit Hilfe der Zykelindices Z(G3 errechnet, welche bei Oberschelp ([lo], 3 3) angegeben wurden. Die relativen Fehler I - Z,,/S bzw. 1 +Z2,J/S sind schon bei kleinen Argumenten sehr gering. Im Falle 0 = 3 , p=2, n = 4 z.B. unterscheidet sich schon die erste Approximation erst in der 17. Stelle vom wahren Wert. Die Aussage, welche die Satze 2 und 3 fur die mittlere GroBe der Automorphismengruppe machen, ist klar : Die triviale Abschatzung 1
4.
209
STRUKTURZAHLEN
’
Demnach gilt die asymptotische Gleichheit S(n, (1, p)) -nZW- /(2”- l)!. Satz 4 ergibt sich auch in der hier entwickelten Theorie, da (3; = 6, ist und da bekanntlich” Z(G,,) [ f , / t ] = ( t ( t +1 )...(t+n- l))/n! ist. Fur t=2” erhalt man das Carnapsche Ergebnis. Fur die mittlere GroBe der Ordnung der Automorphismengruppe gilt also
Die grofitmogliche Ordnung ist nach wie vor r ( n , ~ ) = n ! und , diese wird z.B. angenommen fur diejenigen Carnap-Systeme, welche aus lauter AllPradikaten bestehen. Hingegen gibt es fur hinreichend groBe n keine CarnapSysteme mit der trivialen Automorphismengruppe. Vielmehr kann man fur die kleinstmogliche Gruppenordnung 1: (n, z) die folgende asymptotische Abschatzung geben : SATZ5 .
Beweis. Die Automorphismengruppen von Carnap-Systemen sind direkte Produkte von symmetrischen Gruppen, die uber den sog. Q-Pradikaten PI,..., P2,. operieren, welche durch die Pradikate R,,..., R, induziert werden: Ein Q-Pradikat ist dabei definiert durch eine Konjunktion P j : = (1) R, A ... A (1) R,, wobei die 2’ Moglichkeiten, die durch Klammern angedeuteten Negationen zu setzen oder nicht zu setzen, gerade zu den 2” QPradikaten fuhren. Jede Zahl aus N liegt in genau einem Q-Pradikat. Haben die Q-Pradikate die Kardinalzahlen q l , ..., q2*, so hat die Automorphismengruppe $9 die Ordnung g = ql !...q2W!, und diese Zahl fallt minimal aus, wenn alle q j moglichst gleich groB sind. g ist ein sog. OrdnungsmaB (degree of order) im Sinne Carnaps ([3], S. 1-2). 1st n=r 2”+s mit O<s<2”, so gilt fur die kleinste Gruppenordnung der HILFSSATZ. y(n, T ) = ( r ! ) 2 W - s ( ( r + l)!y=(r!)2W(r+ l y . Denn die “gleichmaBigste” Verteilung der n Individuen auf die 2” Basismengen besteht darin, 2” -s Basismengen jeweils r Individuen, den restlichen s Basismengen aber r + 1 Individuen zuzuteilen. Nach der Stirlingschen Formel ergibt sich aber bei festem p fur n+ co (und
*
Vgl. [12], S. 71 (8).
210
W. OBERSCHELP
damit auch fur r+co) aus dem obigen Hilfssatz
’ da s beschrankt ist, Denn (1 -s/n>. strebt gegen e-’, und (1 - ~ / n ) ~ ” -strebt, gegen 1. Hiermit ergibt sich nun, daB bei der Abschatzung y ( n , z)
< g(n, z) < r(n,4 = n !
die Zahl g(n, 2) stets echt zwischen den beiden Randschranken liegt. Genauer, die Quotienten g/y und r/g gehen gegen Unendlich, allerdings der erste wesentlich langsamer als der zweite. Man rechnet leicht aus, daB
r ~
9
N
(2’- I)!
2’”
n2a-1 ~
2””
-b’-- n 2 P -
1
=:PpF(n,p).
Durch Logarithmierung ergibt sich 1 0 g g = 1 0 g c t g + + ( 2 ~ -I ) l o g n + o ( l ) = O ( l o g n ) , dagegen
Y
r
log. = logp, 9
12 1.44 x 104 1.32 x 1013 2.41 x 1050 9.25 x 8.71 x (1 ;500) 1.05 x logs5 (1;1000) 1.49 x 1OZz6* (1 ;5)
(i;io) (1;20) (1 ;50) (1 ; 100) (1;200)
+ p(log2) n - (2” - 1) log n + o(1) = O ( n ) .
22.5 3.90 x 104 4.87 x 1013 1.38 x 7.44 x 10129 9.87 x 10316 1.87 x 1 0 9 8 6 3.76 x 1 0 2 2 6 9
120 3.63 x 106 2.43 x 10’8 3.04 x 1 0 6 4 9.33 x 10157 7.89 x 1.22 x 4.02 x 102567
1.88 2.71 3.70 5.73 8.04 11.3 17.9 25.3
1.78 2.52 3.57 5.64 7.98 11.3 17.8 25.2
95.1 92.8 96.5 98.5 99.3 99.6 99.8 99.9
lo8 1036 10100 10257 10837 101970
6.56 990 3.92 x 109 5.62 x 1038 1.03 x 10103 4.20 X 2.40 x 10840 5.88 x 1O1o73
120 3.63 x 2.43 x 3.04 x 9.33 x 7.89 x 1.22 x 4.02 x
1 4 2.07 x 104 3.54 x 1024 7.91 x 1073 3.35 x 10201 1.52 x 10691 1.58 x 101674
2.90 65.9 1.87 X lo6 5.63 x 1027 1.19 x 1078 5.54 x 10206 5.70 X 6.67 X 101681
120 3.63 x lo6 2.43 x 3.04 x 1 0 6 4 9.33 x 7.89 x 10374 1.22 x 4.02 x 102567
2 144 2.07 X 8.89 x 5.79 x 8.56 x 1.26 x 1.09 x
lo6
l0l8
1064 10157 10374 101134
3.28 6.87 18.9 63.2 1.77 x lo2 4.90 x lo2 1.91 x 103 5.38 x 103
1.89 5.35 15.2 59.9 1.69 x lo2 4.79 x 102 1.89 X lo3 5.35 x 103
2.90 16.5 90.4 1.59 x 103 1.51 x lo4 1.66 x 105 3.76 x 106 4.23 x 107
0.365 4.13 46.8 1.16 x 103 1.31 x 104 1.48 x 105 3.65 x lo6 4.13 x 107
-~-
~
~
1
1 16
4.51 x 1013 1.25 x 1 0 4 9 6.26 x 10147 4.58 x 2.30 x 101382
1 1 1 2.62 x 105 2.04 x 1027 1.57 x 1098 6.46 x 10411 2.10 x 101097
9 -
r ( n , t)
9(",T)
~
__
~-
-
V
Y ~
1.77 10.8 6.55 x 103 3.93 x 1018 8.66 x loS5 5.32 x 10156 3.15 x 10560 2.63 x
120 3.63 x 2.43 x 3.04 x 9.33 x 7.89 x 1.22 x 4.02 x
1.35 3.61 149 5.35 x 10'1 3.15 x 1037 2.03 x loll2 4.86 x 5.66 x
120 3.63 x 106 2 43 x 10'8 3.04 x 1064 9.33 x 7.89 x 1.22 x 4.02 x
106 1Ol8 1064 10374 102567
~
1.77 10.8 4.09 x lo2 8.70 x 104 6.92 x lo6 8.49 x 10s 6.87 x 10l1 1.15 X lOI4
5.92 x 1.07 x 1.94 x 1.87 x 3.39 x 6.14 x 5.92 x 1.07 x
10-4 10-1 10' 104 106 108 10l1
1.35 3.61 1.49 x lo2 2.04 x lo6 1.55 x 10'" 1.30 x 1014 7.52 x 1019 2.70 x 1 0 2 4
4.26 x 1.98 x 9.15 x 1.35 x 6.25 x 2.90 x 4.26 x 1.98 x
10-14
1014
10-9 10-5 lo4 lo8 1013 10l9 1024
STRUKTURZAHLEN
213
Natiirlich ist ebenfalls log (r/y) = O(n). Demnach liegt g tatsachlich wesentlich naher bei y, als r bei y liegt. Diese Tatsache kann man als einen schwachen Ersatz fur das starke Ergebnis im Falle Q > I ansehen, nach dem dann g exakt in der Nahe von y liegt. Zahlenbeispiele: Die Zahlen
sowie r ( n , T)=n! und die Vergleichsfunktion a,,f (n, p) sind fur einige Zahlenwerte bis zu p = 5 und n=1000 berechnet worden. Das Verhaltnis a,,f(n, p ) / ( g / y ) geht hier wesentlich langsamer gegen 1 als bei den Zahlenbeispielen Q > I , wo schon Zahlenwerte urn n = 10 sehr genau waren. Literatur 1. N. G. DE BRUIJN,Generalization of Polya’s fundamental theorem in enumerative combinatorial analysis, Indag. Math. 21 (1959) 59-69. 2. N. G. DE BRUIJN,Polya’s theory of counting, in: Applied combinatorial mathematics, ed. Beckenbach (New York-London-Sydney, Wiley, 1964) S. 144-184. The concept of degree of order (1952) vervielfaltigtes Manuskript. 3. R. CARNAP, Logical foundations of probability (Chicago, Univ. Chicago Press, 1950). 4. R. CARNAP, 5 . R. L. DAVIS,The number of structures of finite relations, Proc. Am. Math. SOC.4 (1953) 486495. und A. MOSTOWSKI, Models of axiomatic theories admitting auto6. A. EHRENFEUCHT morphisms, Fund. Math. 43 (1956) 50-68. The number of linear, directed, rooted and connected graphs, Trans. Am. 7. F. HARARY, Math. SOC.78 (1955) 445463. Note on an enumeration theorem of Davis and Slepian, Mich. J. Math. 8. F. HARARY, 3 (1955/56) 149-153. Note on Carnap’s relational asymptotic relative frequencies, J. Symb. 9. F. HARARY, Logic 23 (1958) 257-260. Kombinatorische Anzahlbestimmungen in Relationen, Math. An10. W. OBERSCHELP, nalen 174 (1967) 53-78. 11. G. POLYA,Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937) 145-254. 12. J. RIORDAN,An introduction to combinatorial analysis (New York, Wiley, 1958). Contributions to the theory of models I, Indag. Math. 16 (1954) 572-581. 13. A. TARSKI,
A SURVEY OF SOME CONNECTIONS BETWEEN CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC D. PRAWITZ and P.-E. MALMNAS] The University of Stockholm
1. Preliminaries As logical constants we use &, v , 2 , V, 3 and A (for absurdity). In case of modal logic, we add N (for necessity) to this list. The formulas are built in the usual way. The letters A , B, C, ... are used as syntactical variables ranging over formulas. The letters P and x are used as syntactical variables ranging over the predicate symbols and the individual variables, respectively. The predicate symbols are to be given in some alphabetic order. A = B is an abbreviation for ( ( A = , B ) & ( B 2 A ) ) and - A stands as an abbreviation for ( A = , A). (That absurdity instead of negation is taken as primitive is only a matter of convenience.) By a part of a formula A , we always mean a formula that forms a part of A. (The subformulas of A form a somewhat wider class than the parts of A, since if, e.g., VxB is a subformula of A , then so are all formulas obtained from B by substituting for all free occurrences of x a term that is free for x in B.) We assume that the reader is familiar with what it means for a formula, A , to be derivable from a set, r, of formulas within classical (intuitionistic, minimal) first order predicate logic; for brevity we say that A is derivable from r within C and write Tt,A. In case of intuitionistic logic and minimal logic we use the letters I and M respectively. The logic that arises by adding the modal rules of S4 to any one of these logics we denote by writing S4 as subscript; we thus speak of Cs4,etc. 1 The proof of Theorem D is based on a seminar essay by the second author (submitted in partial fulfilment of the requirements for the fil.kand. degree). He has influenced other parts of the essay as well.
21 5
216
D. PRAWITZ
and
P.-E. MALMNAS
2. Interpretability
The results of the next section will be concerned with interpreting logical systems within each other. Such an interpretation of a logical system s, into a logical system S, will be given by exhibiting a function or translation 9 that maps formulas of S, into formulas of S, in such a way that for each formula A of S, ks, A if and only if k s 2 F ( A ) . (1)
S, is then said to be interpretable in S, by 9. Consider also the condition: For each set T U { A } of formulas in S,
r Is, A if and only if S ( r )t s 2 F ( A ) ,
(2)
where F(r)is the set that results from replacing each member B of r by 9 ( B ) . If 9satisfies (2), we will say that s, is also interpretable in s, by 9 with respect to derivability. The existence of a translation F that satisfies condition (1) is of course trivial, and the interest of the interpretation will depend on the fact that 9preserves interesting structural similarities. Sometinies 9 is defined by schemata, and we then say that S, is schemaThis means that there are a number of tically interpretable in S, by 9. schemata, one defining the value of F for atomic formulas, and one for each logical constant c defining 9inductively for formulas that have as principal sign the constant c. For instance, there is to be a schema 4 ( F , G), i.e. an expression that is like a formula in S, except for containing the two letters F and G in the position of atomic formulas, such that for each formula A and B in S, .F(A & B ) = f$( F ( A ) ,F ( B ) ) , where $ ( F ( A ) , F ( B ) ) is the result of replacing the letters F and G in @(F, G) by F ( A ) and F ( B ) respectively. There are however interesting interpretations that cannot be defined schematically in this way. Sometimes, the schema consists simply of schematic letters combined with the logical constant in question, as when
9 ( A & B) = F ( A )& 9 ( B ) for each A and B. We will then say that the logical constant in question is literally translated by 9. REMARK.One may ask how schematic interpretations of one logical system in another are related to the notion of interpretability between non-
CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC
217
logical theories considered by Tarski, Mostowski and Robinson [ll]. Given two theories T, and T, containing no common descriptive constant, TI is there said to be interpretable in T, if there is a recursive set A of possible definitions in T, of the descriptive constants in TI, such that if
t,,A,
then
AI-T,sA,
(3)
where T i is obtained from T, by adding to the descriptive constants of T, those of T,. To consider this question, let us take the logical systems c and I as an example, and let us suppose that they are formulated in different symbolisms. Let I‘ be the extension of I obtained by extending only the language through the addition of the symbols of C. We then consider possible schematic definitions in 1 of the symbols of C. Let e.g. A be a binary sentential connective in C. By a possible schematic definition of A in 1, we then mean a schema
F
A
G
= 4 ( F , G),
where 4 (F, G) is a schema containing only the schematic letters F and G and symbols of I. Following Tarski et al., C may then be said to be interpretable in I if there is a set of possible schematic definitions in I of the symbols of C in such a way that if r is the set of substitution instances in 1’ of these schematic definitions. then for each formula A of c : I-, A
if and only if
r I-,
A.
(4)
Clearly, we want “if and only if” in (4) and not only “only if” as in (3); when dealing with logical systems of first order, we are considering open formulas that have no closed equivalents, and hence, non-provability must also reflect the meaning of the logical constants. By defining the notions involved more precisely, it can be shown that in all cases considered here, schematic interpretability as required by (1) is equivalent to interpretability as required by (4).2 To show this equivalence 2 A somewhat analogous situation pertains to the two notions of definability considered in Prawitz [lo]. It can be seen that the two notions are equivalent. Indeed, suppose that y is weakly definable in S using the transformation *. This means that t s A holds if and only if t-sA*. Hence, for all systems in which t s A * = A * , we also have t-s(A* = A * ) * . The last fact can be written ks(A =A*)*, and consequently we also have t s A = A * , which is what is required for strong definability. It would thus have been sufficient to show that the logical constants in I and M are not strongly definable, which would have slightly simplified the proofs. Cf. footnote 10.
218
D. PRAWITZ
and
P.-E. MALMNAS
in the example considered above, one has to show that if A is a formula of I and is derivable from f (where f is as above) in I', then A is provable in I ; this fact can be shown by using e.g. the theorems about normal deductions in Prawitz [lo]. 3. Theorems
THEOREM A.3 Let A"" be the result obtained from A by inserting two negation signs in front of each part of A , and let f - "be the result obtained from r by carrying out this transformation on each member of f . Then: Also
f k C A if and only if
Tt,A
f " "I-, A " " .
f""t,A"".
i fa ndonlyi f
COROLLARY 1.4 Classical logic is interpretable (also interpretable with respect to derivability) in intuitionistic and minimal logic by the translation * defined schematically as follows: (1) (Ptlr2 . . . t n ) * = --Pt,t,...t,. (2) ( A v B ) * = - ( - A * & - B * ) . (3) (3xA)*= -Vx-A*. (4) Translation of absurdity, conjunctions, implications and universal formulas : Literal.
-
2.5 Let f be the set of the non-logical axioms of a classical COROLLARY theory T. Under the condition that all members of r"" (or r*)are valid in an intuitionistic theory U, it holds: If U is consistent, then so is T.
COROLLARY 3.6 If the intuitionistic natural number theory is consistent, then so is the classical one.
--
3 A theorem of this kind was proved by Kolmogoroff [71, who showed that the fragment - transforof C containing only the logical constants 3 and is interpretable by the mation in the corresponding fragment of M; see also Church [l] p. 208, 38.12. Corollary 1 is due to Gentzen [3] and by Bernays (see Gentzen [2] p. 532) seemingly independent of Kolmogoroff; cf. also footnote 6 . A corollary of this kind was also drawn by Kolmogoroff [7], but f had then to contain also logical axioms. This corollary was not explicitly drawn by Kolinogoroff but the result was independently found by Godel [4],using a transformation similar to the * in Cor. 1 except that the transformation of implication was not literal, and that the transformation of atomic formulas was literal.
-
CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC
219
THEOREM B.7 Let A' be the result obtained from A by simultaneously replacing each part B of A by B v A , and let r' be the result obtained from r by carrying out this transformation on each member of I'. Then:
r t ,A
if and only if
r' t, A ' .
COROLLARY 1. Intuitionistic logic is interpretable in minimal logic by the translation " defined schematically as follows : (1) ( A z J B ) "= A x x ( B " v A). (2) (VXA)" =Vx(A" v A). (3) Literal translation in other cases. THEOREM C. Minimal logic is interpretable in intuitionistic logic by the translation " where A" is the formula obtained from A by replacing every occurrence of A by P, where P is the alphabetically first 0-place predicate symbol that does not occur in A . THEOREM D. Let AN be the result obtained from A by inserting N in front of each part of A , and let TN be the result obtained from r by carrying out this transformation on each member of r. Then:
r t,A
if and only if
TNt,,,AN.
COROLLARY 1.8 Intuitionistic predicate logic is interpretable (also interpretable with respect to derivability) in classical predicate logic extended with S4 by the schematic translation defined as follows: (1) (Pt,t, ...t,)"=NPt,t, ...t,. ( 2 ) ( A B)" = N(A" 2 B"). (3) (VxA)"= NVxA". (4) Translation of absurdity, conjunctions, disjunction, and existential formulas : Literal. O
COROLLARY 2.9 Intuitionistic predicate logic is interpretable in classical predicate logic extended with S4 by the translation defined schematically as follows: (1) ( A V B ) + = N A +V N B + +
7 The search for a translation that interpretes I in M was stimulated by a question by docent Jan Berg. 8 This result was proved for sentential logic by McKinsey and Tarski [9], using topological methods. A proof (still only for sentential logic) using Gentzen-type technique was recently given by Hacking [6]. 9 This result was conjectured to hold for sentential logic by GodeI [S] and was proved for sentential logic by McKinsey and Tarski [9].
220
D . PRAWITZ
and P.-E.
MALMNAS
(2) ( A 3 B)' = NA + 3 N B +. (3) (3xA)+=3xNA+. (4) Translation of atomic formulas, conjunctions, and universal formulas: Literal. 4. Discussion
A. From an intuitionistic point of view, the difference between classical and intuitionistic logic may be said to be that classical logic fails to make any distinction between the following two states of affairs : (i) A does not imply a contradiction (i.e. the assumption that A implies a contradiction implies a contradiction ; cf. the definition of negation) and (ii) A is provable. It is therefore very natural to expect that a classical argument can be understood intuitionistically, if the formulas are interpreted throughout in the weak sense (ii), i.e. that classical logic can be interpreted in intuitionistic logic by a translation which successively replaces classical formulas by their double negation as is expressed in Theorem A. Indeed, one finds, in agreement with our remark above, that classical logic may be obtained from intuitionistic logic by adding a rule that annihilates the intuitionistic distinction between (i) and (ii), i.e. by adding a rule for elimination of double negation allowing the inference of A from A. This formulation of classical logic, which was first given by Gentzen [3] (see also Prawitz [lo]), is very suitable for the present purpose. By observing, first, that the rule for eliminating double negation is intuitionistically valid when the conclusion is a negation, and, second, that every intuitionistic inference rule continues to be intuitionistically valid after the --transformation, one immediately obtains a proof of Theorem A. Corollary 1 is then obtained by observing that molecular formulas preceded by a double negation can be replaced with intuitionistically equivalent formulas, e.g. - ( A v B ) is intuitionistically equivalent to - ( - A & -B). Corollary 1 gives a somewhat different perspective to the relation between classical and intuitionistic logic. Except for predicate symbols, the difference between the two systems now appears to be that intuitionistic logic contains in addition to the constants of classical logic, a primitive connective v and a primitive quantifier 3 (both of which are known not be defineable in terms of the other logical constants, see Prawitz [lo] p. 59, Corollary 9). Instead of Corollary 2 one may perhaps expect a somewhat stronger result. To add a rule for elimination of double negation, which amounts to
--
-
-
CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC
22 1
allowing the inference of A when it is known that A does not imply a contradiction, may appear to be a very safe step in the sense that it does not lead to contradictions. Therefore, one may perhaps be inclined to think that no contradiction can be obtained in an axiom system by classical reasoning, if it is not already obtainable by intuitionistic reasoning. This does not hold, however, since A is classically but not intuitionistically derivable from e.g. -Vx(Px v -Px) (see Kleene [8]). (These considerations show incidentally that A k, A“ * does not hold in general, although A I-, A . ) But a classical theory is of course consistent, if the intuitionistic translations (as defined in Theorem A or Corollary 1) of the axioms are valid in an intuitionistically consistent theory.
-
N
B. Note that the translation defined in Corollary B 1 is not an interpretation with respect to derivability. C. The translation defined in Theorem C is not schematically defined10, and it seems likely that there is no schematic interpretation of minimal logic in intuitionistic logic. Similarly, we conjecture that there is no schematic interpretation of intuitionistic predicate logic in classical predicate logic. (For sentential logic, it is known that there is no such schematic interpretation, but the proof for that fact can not, it seems, be generalized to predicate logic; see Kleene [8] p. 495.) D. From a classical point of view, the difference between intuitionistic and classical logic may be said to be that intuitionistic logic fails to make any distinction between asserting only that a formula holds and asserting the provability of the formula; intuitionistic logic can make only the stronger of the two assertions. Hence, one may expect that by adding a modal operator N to classical logic, where NA may be read “it is provable that A”, and by adding rules that correspond to this meaning of N, it will be possible to understand an intuitionistic argument classically, interpreting the formulas overall as asserting provability ; i.e. one may expect that intuitionistic logic is interpretable in some form of classical modal logic by a translation which successively transforms the intuitionistic formulas by writing “N” in front of them as expressed in Theorem D. To prove Corollary 1, we can then observe that for certain molecular 10 The translation defined in Theorem C was wrongly used in Prawitz [lo] in a remark stating that A was weakly definable in I. Since the P that is to replace A according to this translation depends o n the context, the translation does not meet the requirements on weak definability. In fact, A is not weakly definable in M, cf. footnote 2.
222
D. PRAWITZ
and P.-E.
MALMNAS
formulas, if th{ atomic parts are preceded by N and if also the whole formula is preceded by N, then the formula is equivalent to the formula that results from striking this first occurrence of N. Corollary 1 is thus obtained when one tries to transform a formula AN to an equivalent formula by striking as many occurrences of N as possible except for those in front of the atomic parts, going outwards from the smaller parts to the larger parts. Corollary 2 is obtained, when one tries to transform a formula AN to an equivalent formula by striking as many occurrences of N as possible except the one in front of the whole formula, going inwards from larger parts to smaller parts. By completing the latter process, one obtains a formula NB such that kCS,ANif and only if k,,,NB. Since kcs4NBif and only if k,,,B, one can finally remove also the initial occurrence of N. It is to be noted that the interpretation obtained in that way is not a n interpretation with respect to derivability. A counterexample is obtained by observing that but not
P, P Pf, ( P 2
since not
2
Qt-iQ
Q>+t-cSbQ+
P,NP 2 NQ tc,,Q. 5. Proofs
In the proofs of the theorems above, we will assume acquaintance with Prawitz [lo]. At some places, we will make essential use of the fact that the deductions in the systems involved can be written in a certain normal form as described in [lo]. For convenience, theorems about normal deductions are provided in [lo] for c’,a reduced form of c where v and 3 are omitted. In this context, we need similar results for C. However, if ’ stands for a transformation by which disjunctions and existential formulas are replaced by equivalent formulas with and & or and V respectively, it can be seen that a normal deduction in C’ (or C;,) of A’ from r‘ goes over to a normal deduction in C (or Cs4)of A from r by an obvious transformation. N
-
PROOFOF THEOREM A. As pointed out in the discussion above, the theorem can be proved by showing that each classical inference rule goes over to an intuitionistically valid inference after the -transformation of both premises and conclusion. Instead of considering all inference rules in this way, one may however obtain the theorem directly from the following two lemmata : N N
CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC
223
LEMMA1. T t , A if and only i f r - " t,A"". LEMMA2. (a) r""t,A"" if and only if r"" t,A"". (b) r-" k,A"" if and only if r"" t,A"". The only part of the lemmata that is not trivial is the implication from left to right in Lemma 2. It suffices to prove this implication in Lemma 2 (b), i.e. to show that applications of the A-rule in deductions of A"" from r"" are superfluous. To this end let 17 be a normal deduction in c of A"" from r" " with a conclusion B of an application of the A-rule. It may be assumed that no conclusion of an application of the A-rule in Il has the form of an implication ([lo] p. 39, Th. 1). We first assume that B is not minor premiss of an application of the v E- or 3E-rule. Then Il has the form shown to the left below. [- BI [- BI __
c
__
A
(A)
c
That Il has this form follows from the following three facts. (1) B must be the minor premiss of an application of the I> E-rule because (i) B cannot be a major premiss of an application of an E- or A-rule, since Il is normal, and (ii) B, which by assumption does not have the form of a negation, cannot be premiss of an application of an I-rule, since the conclusion of such an application cannot be subformula of a --transformed formula as required by the Subformula Principle ([lo] p. 42). (2) By the same argument (i.e. the Subformula Principle), the major premiss of this application of the 3 E-rule must have the form B. (3) This premiss B must be an assumption; it can be a conclusion neither of an I-rule, since Il is normal, nor of an E- or A rule, since it would then stand below a formula that could not be a subformula of the required kind. An application of the A-rule of the kind above is clearly superfluous. It can be removed simply by transforming the deduction as shown to the right above. The situation is similar when B is minor premiss of an application of the v E- or 3E-rule. By the same arguments, it is then seen that the segment to which B belongs is minor premiss of an application of the 2E-rule, whose
-
-
-
224
D. PRAWITZ
and P.-E.
MALMNAS
-
major premiss is an assumption of the form B. This case can then easily be reduced to the first case by moving the application of the 2 E-rule upwards. PROOFOF COROLLARY A I . The corollary is obtained by proving that
t A“”
Ez
A*
holds for both intuitionistic and minimal logic. This fact is proved by induction over the degree of A . The base is trivial. For the induction step, it suffices to show that for both I and M: (a) t-A= -A, (b) F - ( A ” ” & B ” ” ) s A “ “ &B““, (c) t- - ( A v B)= - ( - A & W B ) , (d) I- - ( A “ “ ~ B ” “ ) ~ A ” ” ~ B “ “ , (e) t- - V x A “ ” = V x A “ “ , (f) I- - 3 x A - - v x - A . To prove (b), it is convenient to show I- - - ( A & B ) = -A&--B and then apply (a). Similar remarks holds for (d) and (e).
-- -
N
N
--
-
--
PROOFOF COROLLARY A 2. If T is inconsistent, then r k C A and hence A (or r*I-, A). Since I-, A = A , we have that r““(or r*) is inconsistent also by intuitionistic reasoning and that hence U is inconsistent.
r““tl
PROOFOF COROLLARY A 3. The axioms for classical and intuitionistic natural number theory are the same. Let r be the set of these axioms. Now, if A is an induction axiom, then so is A*, and if A is some other axiom, then A* = A . Hence, each member of r* is valid in intuitionistic natural number theory, and Corollary 2 then applies. PROOFOF THEOREM B. Clearly, t - , A - A ’ . Hence, if r’t-,A’, then Tt-,A. The converse is easily shown, using the fact that A t,A’. PROOFOF COROLLARY B 1. One may show by induction over the degree of the formulas that I-,A’=(A v A). Now, suppose that t , A . By the theorem, t-,,,A’.Hence, t , A x v A . It follows that either I-,A” or I-,,, A ([lo], p. 55, Corollary 6), but the last alternative k,., A is false. PROOFOF THEOREM C . Given a proof in M of A , we replace each occurrence of A with P. Since no inference rule in M involves A in an essential way, we then obtain a proof of A“ in M and hence also in I. For the converse, we note that since A does not occur in A“, it follows from the separation theorem ([lo], p. 54) that F,A” implies I-,A”. Of course the substitution of
225
CLASSICAL, INTWITIONISTIC AND MINIMAL LOGIC
A for P in the proof of A" does not change the validity of the proof, and since P does not occur in A , this substitution transforms A" to A. PROOF OF THEOREM D. The theorem follows from the following two lemmata (and the converse of Lemma 2), which may be of som eindependent interest : LEMMA 1. T t , A if and only ifrNkIS4AN. LEMMA 2. If TNtCS4AN, then TNtlS4AN. Lemma 1 is easily proved by induction over the length of the deductions. In the direction from right to left, it holds also for classical logic. In the direction from left to right, it is a peculiarity for intuitionistic logic (e.g., k C A v -A but not t,,,N(NAvN-NA)). Lemma 2 is the crucial step, and is proved by essential use of the theorem on normal deductions for modal logic. Let ( n , 9 )be a normal deduction with pure parameters in C,, of A N from TN.We assume that (l7,F)contains some application a of the A-rule by which an assumption B is discharged, where B is not an implication ([lo], p. 39, Th. I). The assumption B must be major premiss of an application of the 2 E-rule. Clearly, it can not be premiss of an application of the NI-rule, since that would break the restrictions on that rule. Other possibilities are ruled out because they would involve formulas that can not be subformulas of N-transformed formulas, contradicting the Subformula Principle. Hence, 17 has the form shown to the left below
-
-
c
B
-B
c
a is to be chosen so that there is no other application of the Ac-rule above a that discharges an assumption (applications that d o not discharge assumptions, are also applications of the A,-rule). We will show that a can be re-
moved, and assume for induction that this holds true for every application of this kind having a lower number of formula occurrences above its conclusion.
226
-
D. PRAWITZ and P.-E. MALMNAS
The assumption B that we are considering is to be chosen so that there is no other assumption of this form discharged by a that (i) stands in C or (ii) stands above the major premiss of an application of the v E- or 3E-rule, the minor premiss of which stands in C, below B.
-
Main case: There is no assumption in C that is discharged in .XI at the minor premiss of an application of the v E- or 3E-rule. We will show that in this case there is no assumption in C that is discharged in C, which shows that a is superfluous; we can simplify Ll as shown to the right above (and .F accordingly). (Note that applications of the NI-rule in 17, cannot be disturbed by removing Cl,because formulas in C, that stand below C, depend on -B, and can then not satisfy clause 1 in the restrictions on the NI-rule (POI P. 791.) Indeed, assume that there were an assumption C in C discharged in C,. It would then have to be discharged by an application of the 3 I-rule having a conclusion C I D (the A ,-rule is excluded because of the way a was chosen). But this is impossible. The segment c to which C I D belongs cannot be a major premiss of an E-rule, since the deduction is normal. Nor can c be premiss of an application of the NI-rule, because according to the restrictions on this rule ([lo] p. 79), there should then be an essentially modal formula between B and C x D that depends only on assumptions on which C x D depends (note that B and C 2 D is not essentially modal). But every formula between - B and C x D depends on C, which C I D does not depend on. Finally, c can not be premiss of an application of some other I-rule or minor premiss of an application of an E-rule, because that would again involve formulas that can not be subformulas of N-transformed formulas, contradicting the Subformula Principle; note that c cannot be minor premiss of an application of the 3 E-rule, where the major premiss is an assumption discharged by an application of the Ac-rule, since we have assumed that such assumptions do not have the form of implications.
-
-
Special case: There is some assumption in C that is discharged in Z,at the minor premiss of an application of the v E- or 3E-rule. In this case, Ll has one of the forms shown below and we will choose an application p of the v E or 3E-rule in C, and move it down to 17,.
CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC
We want to transform
227
n in respective case to ,z
z
~
B
-B
A
B
-B
A
However, this transformation can cause certain disturbances. Among other things, it is necessary (1) that C , v C2 or 3xC does not depend in (n,S ) on some assumption that is discharged by an application of the vE- or 3E-rule at some place in Z5, and (2) that C, or C, or C,X (where a is the proper parameter in question) does not contain some proper parameter of an application of the 3E-rule in Z5. fl will be chosen so that it satisfies (1) and (2). Let p, be an application of the v E - or 3E-rule as provided by the special case we are considering. If p, satisfies (1) and (2), we set /3 = p,. Otherwise, we consider an application p2 of the v E- or 3E-rule that makes (1) or (2) to fail for PI. If p 2 satisfies (1) and (2) we set p = p2 ; otherwise we consider a p3 that makes (1) or (2) to fail for p 2 and so on. By this process, we obtain finally a p, which satisfies (1) and (2), and we then set p=p,. Having chosen p in this way, it can be seen that the deduction obtained
228
D. PRAWITZ
and
P.-E. MALMNAS
by the transformation described above (where F is to be modified accordingly in the obvious way) is a correct deduction (of AN from I").To realize this, one has to check the following facts : (a) C , v C , or 3xC does not depend on any assumption discharged by an application of the 21- or Ac-rule in C, ; (b) C, or C , or C,X (where a is the proper parameter in question) does not contain the proper parameter of an application of the VI-rule in C, ; (c) no application of the NI-rule in Z12 is disturbed by the transformation. The arguments involved to prove these facts are similar to those in the main case, though we have also to utilize clause 2 in the restriction on the NI-rule ([lo] p. 79) and the (full) lemma on parameters ([lo] p. 29). By the transformation, IX is replaced by some other applications of the A ,-rule, but to all those applications, the induction assumption applies, and they can thus be removed.
PROOFOF COROLLARY D 1. We observe that each part B of A" that has the form of a conjunction, disjunction, or existential formula is essentially modal as defined in [lo] (p. 77). Hence, if B is a part of Ao,kCS4B-NB([lo] p. 77, Lemma), which gives the corollary. (One may also observe that the proof of Theorem D goes through without change when the formulas are "-transformed instead of N-transformed.) PROOF OF COROLLARY D 2. One proves easily that kcs4AN=NA+ using l-
cs4N (NA
& NB)
= N ( A& B )
and
kcs4 NVxNA
= NVxA
and then applies the remark in the discussion. References 1. CHURCH,Introduction to mathematical logic (Princeton, 1956). 2. GENTZEN, Uber das Verhaltnis zwischen intuitionistischen und klassischen Arithmetik, Manuscript set in type by Mathematische Annalen but not published (eingegangen am 15.3.1933). 3. GENTZEN, Untersuchungen uber das logische Schliessen, Math. Z . 39 (1934) 176-210. 4. GODEL,Zur intuitionistischen Arithmetik und Zahlentheorie, Ergeb. math. Kolloquiurn, Heft 4 (1932-33) 34-38. 5. GODEL,Eine Interpretation des intuitionistischen Aussagenkalkuls, Ergeb. math. Kolloquium, Heft 4 (1932-33) 3940. 6. HACKING, What is strict implication? J. Symb. Logic 28 (1963) 51-71. 7. KOLMOGOROFF, 0 principk tertium non datur (Sur le principe de tertium non datur), Mat. Sb. (Recueil mathkrnatique de la SociCt6 MathCmatique de Moscou) 32 (1925) 646-667.
CLASSICAL, INTUITIONISTIC AND MINIMAL LOGIC
229
8. S. C. KLEENE, Introduction to metamathematics (Amsterdam, North-Holland Publ. Co., 1952). 9. MCKINSEY and A. TARSKI, Some theorems about the sentential calculi of Lewis and Heyting, J. Symb. Logic 13 (1948) 1-15. 10. D. PRAWITZ, Natural deduction, A proof theoretical study (Stockholm, 1965). 11. A. TARSKI, A. MOSTOWSKI and A. ROBINSON, Undecidable theories (Amsterdam, North-Holland Publ. Co., 1953).
ZUR SEMANTIK DER INTUITIONISTISCHEN AUSSAGENLOGIK K. SCHUTTE Universitat Miinchen Als Grundzeichen zur Bildung von Formeln der intuitionistischen Aussagenlogik verwenden wir Aussagenvariablen, das Symbol A (fur die falsche Aussage) und die Junktoren A , v und +. Wahrheitswerte bezeichnen wir mit w (wahr) und f (falsch). Nach S. A. Kripke" hat man folgenden Modellbegriff fur die intuitionistische Aussagenlogik. Ein Modell ( M , R, W ) ist gegeben durch eine nichtleere Menge M , eine reflexive und transitive binare Relation R auf M und eine Zuordnung W von je einem Wahrheitswert W(v, a) zu jeder Aussagenvariablen v und jedem Element a g M mit der Eigenschaft
, = w. W ( v , a) = W, aRP* W ( V p) In einem derartigen Modell ordnet man jeder Formal F fur jedes Element EM nach der folgenden induktiven Definition einen Wahrheitswert W(F,a) zu: 1. W(u,a) ist fur jede Aussagenvariable v durch das Modell gegeben; 2. W ( h ,a ) = f; 3. W ( AA B, u) = w genau dann, wenn W ( A , a ) = w und W( B , u) = w ist; 4. W ( A v B, a ) =w genau dann, wenn W ( A ,a) = w oder W ( B ,a) = w ist; 5. W(A+B, a)=w genau dann, wenn fur jedes P E M , fur das aRp gilt, W ( A ,p)=f oder W ( B ,p)=w ist. Eine Formel F heiJ3e giiltig im Modell ( M , R, W ) , wenn W(F,a)=w fur alle a E M gilt. Eine Formel heiBe intuitionistisch allgemeingiiltig, wenn sie in jedem Modell ( M , R, W ) gultig ist. Durch Herleitungsinduktion beweist man :
KONSISTENZSATZ. Jede herleitbare Formel der intuitionistischen Aussagenlogik ist intuitionistisch allgemeingultig. * S. A. Kripke: Semantical analysis of intuitionistic Iogik I, in: Formal systems and recursive functions, eds. J. N. Crossley and M. A. E. Dummett (Amsterdam, NorthHolland Publ. Co., 1965) Seite 92-129. 231
232
K. SCHUTTE
Das Ziel dieser Note ist ein einfacher Beweis fur die Umkehrung: VOLLSTANDIGKEITSSATZ. Jede intuitionistisch allgemeingultige Formel der Aussagenlogik ist intuitionistisch herleitbar. Zum Beweis dieses Satzes verwenden wir folgende Bezeichnungen : Kleine griechische Buchstaben bezeichnen endliche (eventuell leere) Mengen aussagenlogischer Formeln. a-+B bezeichne die Formel A,
A
... A A,-+B,
... v B,,,
wenn @ = ( A ,,..., A,,,) und P={B, ,..., B,) ist, El v ... v En, wenn a leer und fi= { E l ,..., B,,} ist, A,A...AA,+A, wenn a={A,, ..., A,} undpleer ist, v
A,
wenn a und
p leer sind.
Hierbei sol1 es nicht auf eine Reihenfolge der Formeln in den Mengen a und B ankommen. Im folgenden sei F eine festgehaltene aussagenlogische Formel. T ( F ) sei die endliche Menge aller Teilformeln von F. Ein geordnetes Paar (s(, p) von Teilmengen a,p der Menge T ( F ) heiBe konsistent, wenn die Formel a+B nicht intuitionistisch herleitbar ist. Offenbar ist dann a n /3 leer. Das Paar (a, p) heil3e F-vollstandig, wenn a u fi = T ( F ) ist. Ein Mengenpaar (a*, p*) heilje eine Erweiterung von (a, p), wenn a ~ a "und B ~ f l *ist. Fur jede Formel C gilt:
1. 1st (cx,p) konsistent, so ist auch ( a u { C ) , p) oder ( a , p u { C ) ) LEMMA konsistent. Beweis. Sind (a, fiu{C}) und ( a u { C } ,p) inkonsistent, so sind die Formeln a-t p u{C> und C-+(a+P) intuitionistisch herleitbar. Dann ist auch a-+p intuitionistisch herleitbar, also (a, p) inkonsistent. Aus Lemma 1 folgt: 2. Jedes konsistente Paar (a,p) von Teilmengen a,p der Menge LEMMA T ( F ) 1aBt sich zu einem F-vollstandigen konsistenten Mengenpaar erweitern. Eine Teilmenge a der Menge T ( F ) heil3e F-ausgezeichnet, wenn das F-vollstandige Mengenpaar (a,T ( F )- a) konsistent ist. U ( F ) sei die Menge aller F-ausgezeichneten Teilmengen von T ( F ) .
LEMMA 3. U ( F ) ist nicht leer. Beweis. Das Mengenpaar (0,0) ist konsistent, da die Formel A nicht intuitionistisch herleitbar ist. Mit Lemma 2 folgt, da13 es ein F-vollstandiges konsistentes Mengenpaar (a,p) gibt. Hiermit hat man ein a~ U ( F ) .
233
INTUITIONISTISCHE AUSSAGENLOGIK
Anmerkung. Es kann sein, daD U ( F ) = (8) ist. Z.B. ist T ( A )= { A } und (8, A) das einzige A-vollstandige konsistente Mengenpaar, also U ( A )= (8).
LEMMA^. Eine Formel C E T ( F ) gehort genau dann zu einer Menge die Formel a+ C intuitionistisch herleitbar ist. Beweis. Fur jede Formel C E ist ~ trivialerweise a+ C intuitionistisch herleitbar. 1st C$LY, so ist C € T ( F ) - a und, da (a,T ( F ) - a ) konsistent ist, auch ( a , ( C } )konsistent, also a+C nicht intuitionistisch herleitbar. Definition des ausgezeichneten Modells ( U ( F ) ,G , W ) :Fur jede Aussagenvariable v und jedes Element C I EU ( F ) sei CIEU ( F ) , wenn
w ( u , a) =
w, wenn v E a ist, f, wenn v $ a ist.
Hiermit ist ein Modell gegeben, da U ( F ) nicht leer, transitive Relation auf U ( F ) ist und definitionsgemafi
c eine reflexive und
W ( v ,a) = w , a G p=. W ( v , p) = w gilt. Wir werden sehen, daD die Formel F in diesem Modell ungultig ist, falls sie nicht intuitionistisch herleitbar ist. Hierzu beweisen wir, daD das ausgezeichnete Modell ( U ( F ) ,c , W ) folgende Eigenschaft hat:
LEMMA 5. Fur C E T ( F )und
C&a ist.
M E U ( F ) gilt
W ( C , a) = w genau dann, wenn
Beweis durch Induktion nach der Lange der Formel C. 1 . C sei eine Aussagenvariable. Dann gilt die Behauptung nach der Definition des ausgezeichneten Modells. 2. C sei die Formel A. Dann ist ({ C),8) inkonsistent, folglich C$a und definitionsgemafl W(C,a)= f. 3. C sei eine Formel A A B. Dann hat man W ( AA B, a ) = w-W(A, a) = w und W ( B ,LY) =w ~ A E und M B E U(nach Induktionsvoraussetzung) o a - t A und a+B intuitionistisch herleitbar (nach Lemma 4) -a+A A B intuitionistisch herleitbar o A A B E E(nach Lemma 4). 4. C sei eine Formel A v B. Dann hat man W ( Av B, a) = w e W ( A , a ) = w oder W(B, a ) = w o A E M oder B E N(nach Induktionsvoraussetzung) o a + A oder a+B intuitionistisch herleitbar (nach Lemma 4) =a+A v B intuitionistisch herleitbar e A v BE^ (nach Lemma 4).
234
K. SCHUTTE
Umgekehrt gilt: 1st a-+A v B intuitionistisch herleitbar, so ist (a, { A , B } ) inkonsistent. Da { A , B } E T ( F ) ist, folgt dann A E X oder B E E . Hiermit ergibt sich W ( Av B, a)= w-A v BE&. 5. C sei eine Formel A+B. Dann hat man
A + B $ ~ ~ D L - + ( A -nicht + B ) intuitionistisch herleitbar (nach Lemma 4) o ( a u { A } ,( B } )konsistent ~ A E und P B $ p fur ein BE U ( F )mit a EP (nach Lemma 2) e W ( A , p) = w und W ( B , p) =f fur ein PE U ( F ) mit a E p (nach Induktionsvoraussetzung) *W(A+B, a)=$ Beweis des Vollstandigkeitssatzes. Die aussagenlogische Formel F sei nicht intuitionistisch herleitbar. Dann ist (0, { F } ) ein konsistentes Mengenpaar. Mit Lemma 2 folgt, daB es ein F-vollstandiges konsistentes Mengenpaar (DL, p) mit FED gibt. Hierfiir gilt cieU(F) und F$a, also nach Lemma 5 W(F, a) = f . Somit ist F nicht intuitionistisch allgerneingultig. Anmerkung. Mit diesem Beweis ergibt sich auch ein Entsclieidungsvevfahren fur die intuitionistische Aussagenlogik. Der Vollstandigkeitssatz IaBt sich in folgender Weise auf beliebige (auch unendliche) Formelmengen verallgemeinern. Ein Paar (a, p) von Formelmengen a, p heifie konsisterzt, wenn es keine endlichen Teilmengen U,ECY und p 0 c p gibt, 5 0 da13 die Formel ao+Po intuitionistisch herleitbar ist. Das Mengenpaar (a, p) heipe interpretierbar, wenn es ein Model1 ( M , R, W ) und ein EM gibt mit
W ( A , 5 ) = w fur alle A E ~ , W ( B , 5) = f fur alie B E @ . Aus dem Konsistenzsatz folgt: Jedes interpretierbare Paar (a,p) ist konsistent. Umgekehrt gilt auch: VERALLGEMEINERTER VOLLSTANDIGKEITSSATZ. Jedes konsistente Paar (a, p) ist interpretierbar. Dieser Satz 1aDt sich folgendermafien beweisen. Entsprechend wie Lemma 1 beweist man fur beliebige Formelmengen M , fl und fur jede Formel C :
LEMMA 1". 1st (a, p) konsistent, so ist auch ( a u { C } , p) oder (u, pu{C}) konsistent. Ein Paar (a, p) heifie maximal-konsistent, wenn es konsistent ist und DL v ,l? die Menge aller Formeln ist. Aus Lemma I * folgt:
INTUITIONISTISCHE AUSSAGENLOGIK
235
LEMMA 2". Jedes konsistente Paar (a,/) 1aDt sich zu einem maximalkonsistenten Mengenpaar erweitern. (ao, Po) sei ein gegebenes konsistentes Paar. (al, PI) sei eine maximalkonsistente Erweiterung von (ao, Po). Wir konstruieren eine Menge M von Formelmengen mit folgenden Eigenschaften : 1. U I E M . 2. Fur jedes N E Mist (a,E ) konsistent. ( E sei die Komplementarmenge von a.) 3. Zu jedem EM und zu je zwei Formeln A , B, fur die das Paar ( a u { A } ,( B } )konsistent ist, gibt es P E M mit a c P , A E P und BCP. Ein Modell ( M , E,W ) wird dann so definiert, daD fur jede Aussagenvariable v und jedes a ~ A genau 4 dann W(v,a ) = w ist, wenn V E E ist. Entsprechend wie Lemma 5 beweist man: Fur jede Formel C und jedes @ E Mgilt W(C, a)= w genau dann, wenn C E ist. ~ . Es folgt W ( A ,a,)= w fur alle A € a Ound W(B,a,)=f fur alle B E P ~Hiermit ist der verallgemeinerte Vollstandigkeitssatz bewiesen. Eine Folgerung ist der KOMPAKTHEITSSATZ. 1st (ao, Po) fur alle endlichen Teilmengen a. so ist (a,P) interpretierbar.
Po cP interpretierbar,
c a und
RECURSION THEORY AND THE THEOREM OF RAMSEY IN ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC D. SIEFKES Mathematisches Institut der Universitat Heidelberg
In his paper [l] Buchi gives a decision method for a system of arithmetic which has the successor function as only operation, but is built up in the strong logical frame of second order one-place predicate calculus. This system is a very suitable tool in examining the behaviour of finite automata (sequential machines, cf. e.g. Rabin and Scott [7]). From its decidability follows the solvability of the automata decision problem for this language (cf. Church [ 2 ] ) .On the other hand, Buchi uses a good part of the theory of automata for his decision procedure. In view of this close connection he calls the system sequential calculus (SC). Buchi can use the means of the theory of automata, since he sets up semantically both the system SC and the decision procedure. If one wants to have a formal approach, one has to analyze the decision procedure - as already Buchi suggests - to get a complete axiom system for SC. To do so, we eliminate in [6] the theory of automata from the decision procedure and show that a certain kind of formulae works as finite automata within the system. To this end we set up an axiom system for second order one-place predicate calculus, and from these axioms and the Peano axioms for the successor function we build up primitive recursion theory as far as it is expressible in the language of SC. With the help of recursion theory we further derive theorem A of Ramsey [8] which was used by Buchi as a second help from outside and which he proposed to be the most interesting candidate for an axiom schema for SC. A careful examination shows that the remaining steps of the decision procedure are derivable; thus this very simple axiom system is complete. In fact it is the idea of Church (cf. e.g. [2]) to handle automata problems by recursion ; for this purpose he uses open recursive theories (quantifiers are excluded, but the introduction of new predicates by recursion equivalences is allowed). Therefore recursion theory suggests itself as a compen237
238
D. SIEFKES
sation of automata theory; but it is surprising that the whole theory of primitive recursion does not exceed the power of SC. - In the sequel we shall speak simply of “recursion”, omitting the word “primitive”. In this paper we shall give the derivation of the theorem of Ramsey within the system SC. Since Ramsey uses metamathematical recursion which is not available in SC, the translation of the original proof into the formal language is one of the central points in establishing the completeness of SC. Thus this topic seems to be worth a separate treatment. - In Section 1 we state the language and the axioms of SC; in Section 2 we derive recursion theory and from this in Section 3 the Ramsey theorem. A presentation of our version of the decision procedure and of the connections between SC and the theory of automata will be given in full detail in [6]. - I wish to thank Prof. G. H. Miiller for his kind criticism and helpful remarks in writing down the paper. 1. The system SC
Since we want to derive the theorem of Ramsey within the system SC, we describe the language and the logical frame before giving the non-logical axioms. Object language: As individual variables we use small Latin letters, a, b, c,... as free, t , x,y , z as bound variables. Analogous A , B, C,... resp. P,Q, R,S as free resp. bound one-place predicate variables. The quantifiers V, 3 serve for both types of variables. Further we use sentential connectives, T and F for the truth values “true” and “false”, brackets and dots for bracketing of formulae (dots extend over brackets). As only non-logical signs we have the individual constant 0 to denote the zero-element and the one-place function symbol ‘ for the successor function. Metalanguage: Formulae we denote by German capitals, natural numbers (for indices etc.) by small German letters. As for the rest we use the signs of the object language in the metalanguage. Logical axioms: We use freely rules of propositional calculus without mentioning. The other axioms and rules we state by pairs (respectively for individual and predicate variables). It is to be understood that one has to avoid collision of variables. 1) Substitution rule:
(a term).
(8 formula with one marked free individual variable).
239
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
2) Changing of bound variables:
( Q quantifier). 3) Axioms for quantifiers:
(AQI1) (Vx) % (x) + % ( a ) (AQ12) %((a) + (3x1 %(x)
(AQPl) (VP) % ( P ) + % ( A ) (AQP2) % ( A ) + ( 3 P ) % ( P )
4) Rules for quantifiers: (RQIl)
B +%(a) 23 4 (VX) % (x) ~~~~
2l(a) + B (RQ12) (3x) %(x) + B
(RQPl)
(RQP2)
B +%(A) B + (VP) % ( P ) % ( A )+ B ( 3 P )% ( P )+ B
( A not in 23). (a not in 23). We call this logical frame P'K(2): second order predicate calculus with one-place predicate variables. Evidently the axiom system is not independent. It is wellknown that within this frame equality is definable by a = b H~~(VP) T P ( a ) -+ P ( b ) l
.
Further a special form of the replacement theorem is derivable which we call principle of extensionality: (EXTI
(vX) r A (x)
B (x)i.+. 3 ( A )+a ( B ).
The derivation is by induction over the length of the formula % and does not use (SP). By the same method we get the generalization
(vX) r A (x) -8 (x)i.+. % ( A )+ q ~ ) . With the help of this formula we show that the substitution rule (SP) is equivalent to the principle of comprehension : (COMP)
( 3 ~(VX) ) rP(x) -%(x)l
( P not in
a).
This shows that P'K(2) may be considered as a fragment of set theory (cf. Robinson [9], Hasenjaeger [3], McNaughton [ 5 ] ) . In most derivations we will use (COMP) instead of (SP) and it is in fact this highly impredicative comprehension rule which gives together with the induction axiom the strongness of SC.
240
D. SlEFKES
Non-logical axioms: The three Peano axioms for successor are sufficient. We need no schema in view of (SP):
a' = b' -+ a = b , a' # 0 , A (0) A (vt) rA ( t ) + A ( t ' ) ~-,(vt) A ( t ) .
(All ('42) (1)
The system built up in P'K(2) by these non-logical axioms is called sequential calculus SC. First of all we get from (I) by (SP) the induction schema
'u(o)
(1s)
A
(vt)
r'u ( t i -,'u( t ' ) ~
-+
(vt) 'u ( t )
.
Further it is known (cf. Hilbert and Bernays [4], p. 490-491) that order is definable by U
< b ++df(3P) [ P ( a ) A
(vt)
rP(t')
-+
p(t)l
A 1P ( b ) ] .
We use the following abbreviations (cf. Buchi [l]): 1)
2) 3) 4) 5)
( I t ) : % ( t ) ++df(3t)r U < t < b A %(t)l , (vt): % ( t ) ++df(v't)ra < t < b 'u(t)l , (3"t) Hdr(vx)( 3 t ) < t A 301, (V'"t> % ( t ) Hdf(3X) ( V t ) Tx < t + %(t>l , (3P)"'U(P)++df(3P) r ( 3 v ~ ( t A) ~ P ) . I
rx
-+
1) and 2 ) are the familiar restrictions of quantifiers; sometimes we use also (3t), % ( t ) and (Vt), %(I), if there is only a lower bound. 3) is to be read as "there are infinitely many t", 4) as "for ultimately all t", 5 ) as "there is an infinite P". Remark that l ( 3 " t ) 'u(t)++(V"t) 1% ( t ) is derivable. For recursion theory we need still another abbreviation: Let %(a, E ( t ) ; t < a ) mean that in the formula 'u the predicate variable E is contained only with bound arguments restricted by a. For such a formula '%(a, E ) we have a restricted form of (EXT):
(REXT)
(vX);;rA(x)oB(x)i.-+.%(a,
B).
2. Recursion theory
In his paper [2] Church considers "wider restricted recursive arithmetic", a numbertheoretic system similar to SC, which has no quantifiers, but allows
241
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
the introduction of predicates by a certain recursion rule. A simple instance of this recursion schema would be
--
A (0) A (a’)
3 [ B ,(O), .. ., B,, (011
9
23 [ B ,(a), ..., B” (a), A (a)] .
In fact Church considers multiple recursion with any (fixed) number (not only 1) as step distance, but we want to generalize it slightly in another direction : For the whole section let B(a7E ( t ) ;?
(R)
defines a predicate in SC, that means that the existence of such a predicate is derivable. Clearly this cannot be done by (COMP) alone, since E is contained in 23, too. So we have to do a little more.* Note that by our definition of restriction 2330, E ( t ) ; t < O ) is equivalent to a formula 0. not containing E at all. Thus we have by (COMP) ( 3 P ) (V‘t) rP(t)-0.1 and therefore ( 3 P ) rP(O)Ct0.1, which ensures us the existence of a predicate starting as we want it. (Of course we could have stated the whole problem with an extra initial condition.) First of all we derive the uniqueness of recursive definition:
LEMMA1. (vz)gbt~~(z)t,~ ( zE)I , A(vz>; rD(z)ttqz, D)I
+piz):
A
b
rE(z)-D(z)i.
Proof. By induction over b : The beginning b=O is trivial. From the premise for b‘ follows the premise for b and thus by induction hypothesis the conclusion for b : (Vz)gb r E ( z ) c t D ( z ) l . From this we get by (REXT) B(b, E)-% (b, 0)and therefore E(b)-D(b), which gives the conclusion for b‘. Next we derive the existence of any initial part of a recursively defined predicate:
LEMMA2. (3s)(vz); r,qZ)- qZ7 s)i. Proof. Induction over b : The beginning is trivial (see above). For the
* Of course, the proof of this “recursion theorem” follows the known pattern of the proof of the recursion theorem e.g. in set theory.
242
D. SIEFKES
and therefore
In other words:
B*( b , B ) A
(vz);
ro
++
B ( z ) ~A
By quantification we get ~ * ( bB,) A (IS) [(vz);
ro (b’) 23 (b’, B)I + -,B*( b , D ) A ro (6’) -23
rs(z)-B(z)i
c-)
A
rS(b’)-%(b’,
(v,D)I
~)1]+
+ (IS) 23*
.
(b’, S) .
From this follows by (1)
B*(b, B ) + (3s)23*(b’, S ) , which leads to the wanted conclusion
(3s)23* ( b , S) --t (IS) 23* (b’, S ) . Now we are able to prove our wanted theorem:
RECURSION THEOREM. For any formula
derivable in SC: Proof. Let
%(a, E ( t ) ; t < a) the following
(3s)(vZ)rs(z)++23(z, s)i .
B* be defined as in the proof of Lemma 2. By (COMP) we have (3s) (vz)
[s(Z)
+R)
rB*(Z, R ) A ~ ( z ) l ] .
Let us abbreviate this formula by
(1)
is
(3s) 3 ( S )
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
243
It is easy to see that with the help of Lemma 1 we have especially
~ * ( bc) ,
D(D).+.(v~); r c ( t ) - D ( t ) i ,
B * ( b , C)
A
%(D).-+.C(b)*D(b).
By (REXT) we have
rC(t)++D(t)l.+.B(b, C ) H B ( b , D)
(Vt);
and by definition of Together we get
B* B*(b, C).+.C(b)++B((h, C).
B*(b, C)
A
D(D).+.D(b)++B(b,D).
Quantification gives us step by step (3R)B*(b, R) A D ( D ) . - + . D ( b ) w B ( b , D ) , (vz) ( ~ R ) B * ( R ~ ), A D(D).+.W) rD(z)ttB(z, 011 , (vz) ( I R ) B * ( ~ ,R ) A (3s)D(s).-+.(~s)(vz) rs(z)HB(z,s)l . With the help of Lemma 2 and (1) we have our theorem. Three remarks to conclude: 1) It is clear that the recursion theorem holds for ordinary recursion, say
For (1) can be transformed into the form (R), e.g. ~ ( a ) + + a=
o v ( j Z ) : rz' =
A
B ( E ( ~ )A , , (z), ..., A,,(~))I.
If we have F instead of T in the first equivalence, we drop the disjunct a = 0. 2) The recursion theorem holds as well for simultaneous recursion of two or more predicates Ei(u) -Bi(a, E l ( t ) ,..., E,(t); t < a), i
=
I , ..., n .
One may prove this fact either by the completeness of SC or by generalizing the proof of the recursion theorem. 3) It follows very easily from the decision procedure of Biichi that every in SC definable predicate is ultimately periodic. Phase and period of the defined predicate can even be computed effectively from the defining formula. Every ultimately periodic predicate is explicitly definable in SC. We conclude
244
D. SIEFKES
that every in SC definable predicate is explicitly in SC definable. This seems to make redundant our recursion theorem: If every definition of the form
(R)
E(a)++B((a,E ( t ) ; t < a )
can be converted into an explicit one
(2)
E ( a ) ++%(a) ( E not in %),
then the existence of a predicate defined by (R) seems to be derivable in SC with the help of (COMP) alone. But this is not true, since we need the completeness of our axiom system to derive in SC that the predicates defined by (R) and (2) respectively are the same, i.e. to derive
3. The theorem of Ramsey For any natural number n>O and any set M let n,(M) be the set of all n-element subsets of M . Then Theorem A of Ramsey [8] reads as follows: THEOREM1 (Ramsey). Let N be a set, let n, m be natural numbers, let Ll, ..., L, be a partition of n,(N). Then there exists a number lj, 1< f j < m , and an infinite subset M of N such that q ( M )c L,. To prove this theorem in SC means first that we choose as N the set N of natural numbers. For the beginning we will further restrict us to the case n = 2 and m = 2 (we will treat the general case at the end of the section). Since we have a wellordered domain, we may speak of sequences instead of subsets and of “ascending” pairs (a, b) (i.e. a
245
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
u i € { c ; , c:, ...} for f < j , we have (af, ai)eL, for every pair €<j. Thus the set {uo, a,, ...} fulfills our theorem in this case.
As for the other case let us assume that the above construction breaks down at step f. Thus for each j we have (cf, c f ) ~ Lfor , at most finitely many i, therefore (c:, c f ) € L Zfor ultimately all i. Let us denote c: by b, and the infinitely many c: with (bo,C:)E L , by dy < d: < .... Now we may continue the above selecting process for L, at infinity, because for every j the sets {bi,d i , d\, ...} are contained in {c:, c:, ...} and therefore ( d i , d / ) E L , for ultimately all i. Thus in this case, too, we get the wanted conclusion using the set {b,, bl, ...}. To formulate Theorem 1 in the language of SC we have to express sets by predicates. Since SC has only one-place predicate variables, we cannot write down the theorem for arbitrary, but only for definable partition sets. So let -4$(a,b) be an SC-formula which may contain other individual- and predicate variables. Then we may translate the Ramsey theorem into the language of SC by the following formula (it is just this formula for special formulae -4$ (a, b) Biichi suggested as axiom schema for SCj :
THEOREM 2. (3Q)". (VY) (vx)'o
rQ (XI
A
Q ( Y ) @ (x,~ 1 v1 +
v (VY) (vx>i
rQ (XI
A
Q (v)
+
-I
@ (x, y)l .
The first step in formalizing the proof given above consists in replacing sets by predicates: We want t o define recursively a predicate E determined just by the sequence a,, a,, .. . . Thus E(ai) holds if and only if there exists an infinite predicate Ci with
ci-
(ai>
A
r(vx) ci(x>-,ai < x A @(ai,
x)
A
ci- (X)I .
We have seen in Section 2 that we are able to introduce in SC a predicate by recursion over the arguments, but is impossible to introduce a sequence of predicates by recursion over the indices. Thus we avoid the explicit construction of the sequence C, C, ... ; we use only the existence of such a predicate Cifor every i, O < i < i . Let us abbreviate the condition A ( b )+ a < b
A
@ ( a , b)
by 8 ' ( A , a, bj and the formula ( g u t ) ~ ( t A) ~ ( a A) (vx) [rA(x)
+
B ( ~ ) IA @ + ( B , b, x)]
246
D. SIEFKES
by D+( A , B, b, a). If we replace in these formulae A and B by Ci and Ci respectively, then we have the conditions upon Ci and Ci of the last paragraph. Thus we may express the above considerations by the following formula : (1)
~ ( a-VQY ) [(vx) Q + (Q, a ,
A
(w: my) -+
+
For the following proofs we abbreviate this by
(W D+(Q, P , Y , all 1.
E ( a ) -FQ) 23 (E,Q, 0). As for the second case we introduce analogous a predicate H determined by the sequence b,, b,, ... . Again we avoid the predicates Di which are determined by the sets { d i , d i , ...}. Let 6- and 9- be the same formulae as 8 ' and 3 ' with 7 s ) instead of s). Then we formalize the second case by
(2) H ( a ) -(vt),
1E ( t ) A A
A
PQ)"[@XI
8-(Q, a , x)
A
(w'or - w ( ] P I a+(Q, P , y, a ) i (wy,rH( Y ) .+ ( 3 ~ID) - (Q, P , Y , a ) i I . --f
A
As abbreviations for the right side of the equivalence we use (Vt), 1E ( t ) A
(3Q) @ ( E ,ff, Q, a )
or even shorter C(E,H , a). Since the recursions (1) and (2) are of type (R) in Section 2, we have at once the existence of E and H : LEMMA 1.
Further it is very easy to see that the recursions (1) and (2) are good for our purpose: if E or H are infinite, then we get an infinite Ramsey set as wanted in Theorem 2. We show this in the following Lemmata 3 and 4. The whole difficulty is reduced to show: if E is finite, then H must be infinite; this will be done in the main Lemma 5. For the convenience of the reader we give now a short informal version of the proof of this lemma; then later on one has to check only the formalization step by step. So let E be finite and let a be the smallest number such that ( V t ) , i E ( t ) . We want to show: for every number b there exists a number c, b
247
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
we have to pay for avoiding the predicates Ci and Di.Let a, be the predecessor of u ( i t . a, is the greatest number with ,?(a,)). We choose a predicate C , as on p. 245 with minimal first element 0, and show H(bo). To this end we prove: 1) ultimately all elements of C, may serve as elements for Do (p. 249, 2. case, (a)), and 2) H ( e ) does not hold for any number e smaller than b, (p. 249, 2. case, (b)). - The induction step is similar: If we have H(b,), we use 6 , and a minimal f), instead of at and C, to show that H(b,+ holds for the first element bt+l of D,.- It is possible to introduce the predicate H by a recursion which corresponds exactly to these three cases and thus goes closer along the lines of the informal proof. But then both the recursion and the proof are even more complicated. Now we come to the formal proofs. First of all we have to show that E and H do what we want them t o do: LEMMA 2. Ascending pairs of elements of E satisfy (Vz) rE(z)+-+(3P)B(E, Q,
z)l
A
5:
E ( a ) A E ( b ) A b < a - - $ $ ( b ,a ) .
Proof. From (1) follows by the premises
(3P)" P ( a ) A (Vx) rP(x) -+ b < x
A
5 ( b , x)?
and therefore $$ (b, a). From Lemma 2 follows directly that the existence of an infinite predicate E ensures us the existence of an infinite Ramsey set for 5: 3. LEMMA (3S)"'(Vz)
rS(z)c-*(3Q) % ( S , Q, z)l +
-+
(3QY ( V Y ) (vx)Y,
rQ(x) A Q (4')
+
$5(x, ~ ) . l
The same remarks hold for H , thus we have LEMMA 4.
(3R)"'(Vz) r R ( z ) c * E ( E , R , z)l -+
-+
rQ
(3Q)"(v~)(vx>Y, (XI A
Q (1'1
+
7
5(x, Y ) I .
Lemmata 1 , 3 , 4 together with the following main lemma give the assertion of Theorem 2. LEMMA 5. If E is finite, then H must be infinite: (Vz)
[ r E ( 4 w ( 3 Q ) 23 ( E , Q, 211 A
A
l H ( z ) + + % ( E , H , z)1]
A
(V"?)i E(t)-+(3"t) H ( t ) .
248
D. SIEFKES
Proof. To make better reading we will not follow the rules of our formalism as close as we did in Section 2; but there will be no difficulty to translate the following considerations into a strictly formal proof. So let E and H satisfy the premises of Lemma 5, let the number a be fixed for the whole proof such that ( V t ) , i E ( t )A (Vt); (3x),E(x) (thus a= 0, if ( V t ) i E(t), and a= c', if E(c) A V t ) = ,E(t)). i We assert (Vy) (3x),H(x) and to prove this we show by induction over b (3x),H(x). 1) Induction beginning: b = 0. 1. case: a = 0. Thus we have ( V t ) i E(t), especially i E(O), therefore by (1) (VQ).(Vx) Q'(Q, 0, x>+(v"t>lQ(t>. This implies
(VQ) . (Vx) from which follows (VQ). (Vx)
rQ (x) +-+x= 0 v 1 5(0, x)l
rQ (x) -0
<x
A i
5(0, x)l
(V'"t)
-+
+(
Q ( t ),
Y t ) Q(t)
.
By (COMP) holds (3Q).(Vx) rQ(x)++O < x
A 1&(O,
x)l ,
this gives together (3Q).(Vx) rQ(x)C-'O < x
A i &(O,
x)l
A
(3"t) Q(t)
and therefore (3Q)" (vx) 8-(Q, 0, x). According to (2), this is equivalent to H(0). 2. case: O
E(c) implies (3Q)B (E, Q, c), which implies by (1) ( 3 x ) V Q ) . B ( E , Q, c)
A
Q(x>.
From this follows by the minimum principle ( 3 4 : ( 3 ~ rB(E, ) Q , c)
Q ( ~ NA (Vy).(3Q) r B ( E , Q, c)
A
A
A
Q ( Y ) +~x
Let d be this least element: ( 3 ~ rB ) ( E , Q, c)
A
Q (d)l
A
(vy). ( 3 ~ rB ) ( E , P , c)
A
P ( ~ )+ I dGy.
249
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
Further let B be a predicate satisfying (3Q): % ( E , B , c ) ~ B ( d ) n ( t l y ) . ( 3 P )r % ( E , P , c ) A P ( y ) l - , d d y .
From (1) and the definition of d and B follows c < d A i E ( d ) A (Vy); i B ( y ) . (3) At last we write down the formula %(I?, B, c) without abbreviation
(4) (3"t) B ( t ) A (vx) rB c < X A 5( c , x)l A (vy); [ E ( y > - + ( w ) " { P ( ~ ) A (vx) [rB(x)--fP(x)l A r p ( x ) - + --f
--f
Y <x
A
--f
B(L.7 X I 1
I}].
We assert that H ( d ) follows from (1)-(4). Proof. We define a predicate C (by (COMP) follows the existence) as (vt)
rc(t)++d < t
B(t) A
A
5 ( d , t)l .
1
a) Assume (3"t). B ( t )A i C(t). Then (3"t). B(t) A B(d, t ) . Thus, if we define c by (vt)
rc(t)-d < t
A
~ ( t A) ~ ( dt>l , ,
we get (39) C(t). We want to show
(vy): m
(5)
y ) -+ ( 3 ~D+ )
(c,P , y, 4 1 .
So let e be a number with 0 Q e < c A E(e); then there exists by (4) a predicate D with (6)
(3"t) D ( t )
A
(VX) r B ( x ) -+ D(x)l
A
rD(x) -+ e < x
A
$ ( e , x>l .
By (6) follows D(d) from B ( d ) and (Vx) rc(x)-+D(x)l from (Vx) rz'(x) - - f B ( x ) l .Therefore we may replace in (6) B by and c by d and get ( 3 P ) D + ( e P , , e, d). Thus we have shown
(vy); rE ( y )
-+
( 3 ~D)
+
(cP , y , d)i .
Since further D + ( c ,B, c, d ) and (Vt),.iE(t), we have derived (5). By definition of c follows %(I?, c, d ) and thus E(d), in contradiction to (3). b) Therefore we have (VV rB ( t ) + c (ti1
250
D. SIEFKES
and thus by (4) and by definition of C
(39) C ( t ) A (Vx) 6- (C, d, x).
(7) As in a) one shows (VA;
(8)
r w y ) -,( 3 ~D+ ) (c,P , y , d ) i
.
Assume now that there is a number e with e < dr\ H(e). Then c < e by (2), and from this and E(c) and from the defining formula for H(e) follows (9) ( 3 ~ ) " A
We define
re@)A (vx) Q + (Q, c, x)l
(w; CEW
-+
me)
(3~)-
by
wX) <
A
A (vX)
-+
A
5( y ,
I}.
rB"(t)-B(t) v t = e l
(vt)
and get from (4) and the first line of (9)
(3'"t) B ( t ) A (VX) 6'
(B, C, X)
and from (4) and the second line of (9)
(w;[ E ( y ) -,( I P , w CP(c)
A
R (e) --+
A
r B (x) -,
(vx)
p(X)l
A
Q f ( P , y , X)
A
6' ( R , .Y,
X)]}].
If we put this together, we get by the help of (COMP) (1"t) B"(t) A
(VX)
But this yields
8' (g, C,
X) A
B ( E , B", c)
(Vy): rE(y) -+ ( 3 P ) D f (B, P, J',C)]
A
B(e)
A
.
e
which is a contradiction to the choice of d. We conclude (Vy);i H ( y ) , which gives together with (7) and (8) E ( E , H , C, d ) and thus H ( d ) . To indicate the formalization of this step consider the formula (vz)
B(E, Q, z ) i A r m z ) - w , H , z ) i A A B(z) A i $ ( d , Z)1] A E ( c ) A (vf),,l E ( t ) A A B ( E , B, z ) A B ( d ) A (vy) [(IP) rB ( E , P , c> A P ( ~ ) I, --+ d < y ] -, % ( E , H , C , d ) .
rrE(z)o(w) A
rc(Z)t,d < z
This is in essence what we have proved in this paragraph. By existential quantification over C , B and d we get proved premises and the wanted conclusion (3x) H ( x ) .
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
251
2 ) Induction step: Let ( ~ x ) ~ H (be x )proved, show (3x),.H(x). If from the induction hypothesis follows H(c) for c > b, we are ready. So we may assume H(b) and therefore (3Q) C(E,H , Q, b). Choose as on p. 249 B as a predicate satisfying (3Q) and d as an element of B in an optimal way, i.e.
Especially we have ( V y ) d , i B ( y ) b~ < d .
As in 1) we want to show H ( d ) . Essentially the proof is the same: Let C be defined as there. The assumption (3"t) B(t) A i C ( t )yields E ( d ) as there, is therefore contradictory. Thus one gets (3"t) C ( t ) A (Vx) F ( C , d, x)
A
(Vy)d, rE(y)
(3'D'(C, ) P, y , d)l
.
we may change this into
Assume that there is a number e with b<e
Define B by ( V t ) m ( t ) c t B ( t )v t = e l . Then we have by definition of B and by the first line of (10) (3"t) B ( t ) A (VX) 8-(B", b, X),
252
D. SIEFKES
and therefore the contradiction @(E,H , B, b) A B(e) A e < d .
Thus we have shown (Vy)$i H ( y ) , from which follows (Vy)$ r H ( y )-+ (3P) ID- (C,P, y , d ) l and thus E(E, H , C, d), which gives H ( d ) . This completes the proof of Lemma 5 and therefore of Theorem 2. Now we extend Theorem 2 to the case of arbitrary many partition sets. At the same time we drop the condition of Theorem 1 that the sets of the covering are disjoint. It is easily seen that both versions of Theorem 1 are of equal strength, and the new one is much more easy to write down formally.
Proof. By induction over m we get easily the proof of Theorem 3 from Theorem 2 : The assertion is trivial for m = 1, for m = 2 it follows from Theorem 2, applied to since the premises of Theorem 3 give i fil (a, b) -+ S2(a,b). So let be m 2 3 : Define formulae 53, as bi for j = I , ..., m-2 and Rm-l as $m-l vBm. By induction hypothesis there is an index j, 1 d j < m - I , with ( ~ Q > " ( V Y >(V'X)~ ~ Q ( x >A
If i < m - 1, we are ready. So let (3"O D ( t )
A
(VY) (VxX
Q (Y>
+
fii(X,
Y)]
*
i =m - 1, let ff be a predicate with
(XI A D ( Y )
-+
Ssm-
(x, Y ) v
B,,,(x, 4'11 .
ONE-PLACE SECOND ORDER SUCCESSOR ARITHMETIC
253
Similar restrict the recursion for H and the proofs to the predicate D.Then Lemmata 1-5 hold as before and one gets as Theorem 2
rQ(x) A Q ( Y ) D (XI A D ( Y ) A $L-(x, ~ 1 v1 v ( V Y ) (VxX rQ(x> A Q ( Y ) D (XI A D ( Y ) A 1ti,,-(x,~ 1 .1
(I€!)".( V Y ) (VxX
-+
1
-+
we get the desired formula
At last we extend Theorem 2 to the case of arbitrary n-tuples.
THEOREM 4. n-
1
m
-+(3Q)". V (Vx, ,..., x,) i=1
m
1
(vx,, ..., xn) ri= A xi <
-+
v 4si(xl, ..., xn)i
-+
i=1
rA
n- I j= 1
xi<xi+lA
n
111
i= 1
i= 1
A Q ( x i > d V 5i(xl,...,xn)1.
We may get a proof of this theorem by trivial changing of some points in the proof of Theorem 3. Or we use the completeness of SC announced in the introduction (shown with the help of Theorem 3 only) and get Theorem 4 by Theorem 1. We conclude with a consequence of the decidability of SC: If we drop the quantifier (3Q) in Theorem 3 and replace the variable Q by A , we get a formula %(A) which is satisfiable if and only if Theorem 3 is true. Now it follows very easily from a result of Biichi [I] that, if a formula % ( A ) is satisfiable at all, then by an ultimately periodic predicate. This shows that the Ramsey set M in Theorem 1 can always be chosen as ultimately periodic if we start with sets L, definable in SC.
254
D. SIEFKES
References 1. J. R. BUCHI,On a decision method in restricted second order arithmetic, in: Logic, Methodology and Philosophy of Science, Proc. of the 1960 Intern. Congr. (Stanford, 1962) 1-11. 2. A. CHURCH, Logic, arithmetic and automata, Proc. Intern. Congr. Math. 1962, 23-35. 3. G. HASENJAEGER, Uber o-Unvollstandigkeit in der Peano-Arithmetik, J. Symb. Logic 17 (1952) 81-97. 4. D. HILBERT and P. BERNAYS, Grundlagen der Mathematik I1 (Berlin, 1939). 5. R. MCNAUGHTON, Some formal relative consistency pioofs, J. Symb. Logic 18 (1953) 136-144. 6. G. H. MULLER and D. SIEFKES, Decidability and completeness in restricted second order arithmetic, to appear. 7. M. 0.RABINand D. SCOTT,Finite automata and their decision problems, IBM J. Res. Develop. 3 (1959) 114-125. 8. E. P. RAMSEY, On a problem of formal logic, Proc. London Math. Soc. 30 (f929-30) 264-286. 9. R. M. ROBINSON, Restricted set-theoretical definitions in arithmetic, Proc. Am. Math. SOC.9 (1958) 238-242.
REFLECTION PRINCIPLES OF SUBSYSTEMS OF ANALYSIS *
Dedicated to Professor S. Iyanaga for his 60th birthday G . TAKEUTI lnstitute for Advanced Study, Princeton, New Jersey
and
M. YASUGI University of Bristol Let 6 be one of the subsystems of analysis, SINN and the system with extended inductive definition (called SEID in this article) (cf. [7]). SINN is second order Peano arithmetic with full induction and the II: comprehension axioms. SEID is an extension of SINN, which is obtained by adding to SINN some inductive definitions. Let rD be the system of ordinal diagrams which is used in proving the consistency of 6 and let ‘Ip be first order Peano arithmetic with second order parameters. Then we can prove the following reflection principles.**
THEOREM 1. Ind,(
a),Prov, (‘Vx3yR (a, x,y)’)
--f
V x l y R (a, x,y )
is p-provable, where R ( N ,x,y ) is elementary in a, i.e., all quantifiers in R(a, x, y ) are numerical and bounded, and Ind,(D) is the schema which allows transfinite induction along 3 with respect to Z y formulas (without second order parameters).
THEOREM 2.
Ind,( %), Prov,(‘A (a)’)
-+
A (a)
is p-provable, where A (a) is an arithmetical formula with a parameter a and
*
Part of this work was supported by NSF GP-4616.
** The results here can also apply to the extended system footnote 2 of [71.
255
SIN”
of
SINN
defined in the
256
G . TAKEUTI
and
M. YASUGI
Ind,(%) is the schema which allows transfinite induction along % with respect to the formulas of ’p. By modifying the proofs of Theorems 1 and 2 we can prove the uniform reflection principles (cf. Introduction of [3]), that is the following two theorems are p-provable.
THEOREM 1’. Ind,
(a)+ V i n (ProvG(‘Vx3yR (x, y , a, n (m)>.)b Vx3yR (x,y , LY, i n ) ) ,
where n ( m ) denotes the “m-th numeral” and R(a, b, a, c) is elementary in LY.
THEOREM 2’. Ind, (9) -+ Vm (Prov, (‘A (a, n (m))’) F A (a, m)) , where A (a, m) is arithmetical in LY. We can also prove another form of the uniform reflection principle.
THEOREM 3. I n d ’ ( 3)
--f
Vm (Prov, ( V + A (4, n (m)).)t VdA (4, m))
is 6-provable, where A(a, a) is arithmetical in a and Ind’ is applied to Z: formulas with a second order parameter. For the meanings and consequences of the reflection principles, the reader should refer to [3] in which a list of references concerning those problems is also found. We are concerned with special cases only. Throughout this article, acquaintance with [7] is presupposed. Both authors started their study of logic in Professor S. Iyanaga’s seminar. We should like to take this opportunity to express our thanks to him. Chapter I In this chapter we shall prove Theorem 1 (which has been stated in the introduction) and its corollary.
1. DeJinition of the systems and elementary predicates. Let 6 be one of the systems SINN, G,, GI, SJNN and the system with extended inductive definition (denoted SEID) and let % be the system of ordinal diagrams that is used in proving the consistency of G(% is denoted by S in [7]). Those systems are defined in [l] and are also to be found in 1 of Chapter 2 , 7 of Chapter 3, at the beginning of Section 2 in Chapter 3, at the beginning of Chapter 3, and in 1 of Chapter 4, respectively. Although 6, and 6,are not to be considered after 2 of Chapter I in this article, we have introduced
SUBSYSTEMS OF ANALYSIS
251
them in order to prove Proposition 1 for SJNN. For the elementary notions and the notations, refer to Chapter 1 of [7]. 1.1. We shall restrict the non-logical constants of 6 to the following. Individual constants; 0, 1. Function constants; +, .. Predicate constants; =, < . 1.2. A formula of 6, R(bl,..., b,, pl,. . ., PI), whose only free variables are b,, ..., b,, pl, ..., (including the cases m=O and/or l=O) and which has no quantifiers on f-variable is called elementary iri pl, ..., pl if all quantifiers appearing in R are bounded. 1.3. The beginning sequences of the system 6 are all those of the forms D-tD and s= t, A ( s ) + A ( t ) , where D and A ( a ) are arbitrary formulas, and mathematical beginning sequences. We may restrict the mathematical beginning sequences to the well known quantifier free axioms concerning the constants given in 1.1. 1.4. All other definitions of 6 in [7] are effective here. We shall use the logical symbols v , k and 3, as well as 1,A and V, although they are not formally defined in 6. Remark. The class of the predicates which are elementary in some free f-variables (cf. 1.2) is smaller than the class of the predicates which are primitive recursive in some freef-variables. This does not weaken our result, however, since the classes of the predicates of the form VxR(a,x , a) and 3xR(cc,x, a) with R elementary in a respectively cover the predicates I7: in a and those Zy in a (cf. Theorem 1). 1.5. A cut is called essential if its cut formula is not of the forms= t o r s< t. 2. PROPOSITION 1. Let R(a, &, ..., 0), be a formula of 6 which is elementary in PI,..., p, and assume that +3xR(x, P1,..., P,) is 6-provable. Then there exists a proof-figure of 6 to the above sequence which does not contain any essential cut or any induction. Moreover, this can be proved with the system of o.d.’s 9, i.e., we can prove the above statement by transfinite induction on the o.d.’s of 9 which are assigned to the prooffigures. The treatment of SJNN is slightly different from the other cases. Proof. For simplicity, we shall prove the proposition only for the case m = 1 and denote the formula R(a, cx). Let us first consider certain conditions on the sequences of 6. Let S be a sequence A , ,..., A j - + A j + l,..., A , of 6. S is said to have the property P if it satisfies the following. P.l. S has no free t-variable.
258
G. TAKEUTI
and M. YASUGI
P.2. Each formula which is in the left side of S, i.e. one of A,, ..., A j , is elementary in a. (This implies that none of A,, ...,A contains unbounded quantifiers.) P.3. Each formula which is in the right side of S, i.e., one of A j + l , ..., A,, is either elementary in ct or 3xR’(x, a),R’(0, a) being elementary in 3.
LEMMA. If a sequence S of 6 which has the property P is 6-provable, then it is provable without essential cut or induction, except for the case 6 is SJNN. Obviously the proposition is a trivial corollary of this lemma, except when G is SJNN. The case where 6 is SJNN shall be treated separately. Proof of Lemma. Suppose a proof-figure P to S is given. The proof is carried out with several steps following the consistency proofs of G (cf. [7]). We shall see that, at each reduction step, the end sequence of the resulting proof-figure still satisfies the property P. 2.1. G is SINN. 1) 2 through 8.2 in Chapter 2 of [7] are effective here. 2) We add the following inference schema “bounded-quantification” (abbreviated to bq) to our system.
where Vy‘y
259
SUBSYSTEMS OF ANALYSIS
3) Reduction in case P contains an explicit logical inference or an induction in the end piece. We shall treat several cases according to the bottommost such inference. If the last such inference is a logical inference, then the reductions are done as those in 6.1 of Chapter 3, [7], except the case an V right on a t-variable. If it is an induction, then the reduction is done as 8.3 of Chapter 2, [7]. For the case where the last inference which satisfies the above condition is an V right on a t-variable, let P have the following form.
..
rAA,b
T + A , VY < tRO(Y, a>
..
r';
d l , VY < sRb(y, a),A , ,
where b< tkRo(b,a) is elementary in a, t is closed and Rb(x, a) and s are obtained from R,(x, a ) and t respectively by term replacements. Assume t = n for some numeral n. If n=O, then P is reduced to
..
r'4 k < n k R b ( k , a), A,,
Vy
< s R ' ( y , a), A , ,
where ( k )means the substitution of k for b in the indicated part of the prooffigure, k
_
_
~
r'+A', (0 < n k R ' (__0 , a)) A ... A ((n - 1) < nkRd(iz - 1, m)) t>q-r'+A', V y < n R b ( y , a ) ~
~~
~
~-
~~
I"
+
~~~
-
~
~-
-~~
A 1%VY < sRb ( Y , a), A , ,
where A' is A , , V y < s R & ( y ,a), A , .
~
~
-~
G. TAKEUTI and M. YASUGI
260
4) Reduction in case there is no explicit logical inference or induction in the end piece. We can follow the proofs in 8.4 through 10 of Chapter 2, [7]. We shall only mention the cases where some extra considerations are needed. 4.1) The end piece of P contains a beginning sequence of the form D-tD. Let P be of the form
D-D
..
r-; A , B r, n
.. B, n-;A ~ b,, A , A, A,,
.. 3+@.
b, A ,
up to term-replacements, the reduction in 8.5.1 in If 6 is identical with Chapter 2, [7], works. If not, then b is of the form
and fi is of the form Vy < tS‘(y), where s= n and t = n for some numeral n, so=O, ..., ~ , , - ~ = =1n, -and S’(0) is either S(0) itself or obtained from S(0) by some term replacements, since there is no explicit logical inference or induction in the end piece. Hence P is reduced to the following proof-figure. I
4.2) Elimination of weakenings in the end place of P (cf. 8.6 of Chapter 2, [7]). If the last inference of the proof-figure Q is a bq, say
A , (0 < kl- S(0)) A r -+ A , Vy < k S ( y )
then the proof goes as follows.
... A ( k - 1 < k t S ( k - 1)) ~
SUBSYSTEMS OF ANALYSIS
261
..
If Q: is T * A A * , then Q* is Q:. If Q: is
..
then
r*
is
Q:
r*+ A * , V y < k S ( y )
5) In the following we assume that the end piece does not contain any logical inference, induction, beginning sequence other than mathematical beginning sequences or weakening, while it may contain some bq inferences. We may also assume that the proof-figure is different from its end piece, for if the entire proof-figure is the end piece, then the end sequence is provable from the mathematical beginning sequences by bq, exchanges, contractions and non-essential cuts, and bq can be eliminated without a use of essential cut and induction (cf. the remark in 2). 5.1) The existence of an essential cut. Since the principal formula of a bq is always explicit, the proof in 9 in Chapter 9, [7], goes through. 5.2) Essential reduction. Note that no principal formula of a bq is implicit. The rest of the proof goes like 10 in Chapter 2, [9]. Thus we have completed the proof in case 6 is SINN. 2.2. 6 is 6,. We can prove this case by following the proof of Theorem 2 in Chapter 3 of [7]. 2.3. 6 is 6,. In this case the proposition is proved along the proof of Theorem 3 in Chapter 3 of [7]. 2.4 6is SEID. In thiscase the lemma is proved following the proof of the case where 6is SINN (cf. 2.1) and the consistency proof of SEID (cf. Chapter 4 of [7]). (We should remark that in this case we might need a finite number of primitive recursive functions (or predicates) in addition to the constants of the system and also a finite number of mathematical beginning sequences besides those in the system, so that Z(a) and a<*b can be defined and exactly one from each pair: {I(n)+ ; -Z(n)) for any numeral n and {n <*m+ ; + n < * m >for any pair n and m of numerals, is provable in 6 without using any essential cut or induction. Indeed these modifications of the system do not cause any problem later in the proof of our theorem.) Inductive definitions can be eliminated as in the consistency proof of SEID, since all A iare implicit (cf. 9 in Chapter 4 of [7]). 2.5. 6 is SJNN. Here we prove the theorem in the original form (i.e. not in the extended form).
262
G . TAKEUTI
and M. YASUGI
1) Set e(a):V4(4 [O] A V y ( 4 [ y ] k 4 [ y + l ] ) t 4 [a])and A : Vxe(x). + 3 x R ( x ,
u ) is 6-provable if and only if A + 3 x R ( x , E) is G1-provable (cf. 10.1 of Section 3 in Chapter 3, [7]). Hence A + 3 x R ( x , a) is G1-provable from the
assumption. 2) From l), T o , Ae+(3xR(x, a)>”is G1-provable, where T o is the set of formulas e(O), V x ( e ( x )k e(x’)) and 3xe(x),and A“ is the restriction of A by e (cf. 10.1 of Section 3 in Chapter 3, [7]). 3) All formulas of T o and A“ are 6,-provable (cf. 10.1 of Section 3 in Chapter 3, [7]). Remark. It is easy to show that Proposition 1 can be extended to the following. Let R ( a , p1,..., p,, y1 ,..., y l ) be a formula of 6 which is elementary in bl, ..., p,, yl, ..., y l and assume that +V41, ..., Vb,, 3 x R ( x , 41,..., @,,, yl, ..., y J is 6-provable. Then there exists a proof-figure of 6 to the above sequence which does not contain any essential cut or induction. For our purpose, however, the present form of the proposition is sufficient. In the following of this chapter we shall consider only SJNN, SINN and SEID as 6.The rest of Chapter I is devoted to proving the reflection principles of those systems.
3. Let $3 be the system of Peano arithmetic with freef-variables as parameters. It is well known that all notions in G (cf. [ 7 ] , particularly Chapter 1) can be arithmetized in 9 using Godel numbering. We shall denote the Godel number of an object A of 6 by ‘A’ and express the notions “P is a proof-figure of 6 ” , “P is a proof-figure of 6 to a sequence S” and “a sequence S is 6-provable” by Pf,(‘P’), Prov, TP’, ‘S’) and Prov, TS’) respectively. Pf * G (.P’), Provz TP’, ‘S’) and Provg TS’) denote the corresponding notions to Pf, r P 7 ) ,Prov, (‘P’, rS1) and Prov, CS’) respectively with the additional condition that “P has no essential cut or induction”. If S is of the form + A , then we may use the simplified notations ProvG(‘A’) and Provg(‘A’) etc. Ind,(T>) is the schema which allows transfinite induction along the ordinals less than 1 9 1 with respect to the Zy formulas (without second order parameters), where 1531 denotes the order type of 3. We should remark that the system of mathematical beginning sequences is finitely axiomatizable. LEMMA1. Ind, (ID), Prov, (‘3xR (x, R)’)
--+
is 9-provable, where R is elementary in a.
ProvG(‘3xR (x, my)
263
SUBSYSTEMS OF ANALYSlS
ProoJ This is proved by formalizing the proof of Proposition 1. We shall give only the outline of the proof that Ind, (D)is adequate. First let us introduce several notations. Assume that p denotes the Godel number of a proof-figure P of 6. ends(p) is the Godel number of the end sequence of P. Q ( p ) is true if and only if the end sequence of P has the property P (cf. the proof of Theorem 1). C ( p ) is true if and only if P is a proof-figure which has no essential cut or induction. 6 ( p ) is defined by 6 ( p ) = o ( p ) # p , where o ( p ) is the 0.d. of P. Note that 6 ( p ) is an 0.d. of D and all those predicates and the functions are primitive recursive. Now from the proof of Proposition 1, we can define a primitive recursive function r as follows. Let p be the Godel number of a proof-figure P. If C ( p )v i Q ( p ) , then define r ( p ) = p . If 1C ( ~ ) A Q ( p ) , then r ( p ) is defined to be the Godel number of the resulting proof-figure of the reduction of P.r is primitive recursive and satisfies the following. 1)
C ( ~ ( P ) ) < ~ ( P )if
* Q(P>.
1C ( P >
2) 5 ( r ( p ) )= 6 ( p ) if C ( p ) . Define r(u, 6) by r(0, p ) = p ; r ( d , p ) =r(r(n, p ) ) . r(u, 6 ) is primitive recursive. Finally define p < . q++O”(p)
itive recursive and the order type of <-is that of D.Then the induction applies on the ordering <. and the induction formula is Q ( p )k 3nC(r(n, p)), or equivalently, 3 n ( Q ( p ) I- C(r(n,p ) ) ) . Remark. In fact, we can prove Lemma 1 in a generalized form: Ind, (a), ProvG(‘Vq53xR(q5, x,a)’)+ProvZ(“Vq53xR(4, x,a).). This is proved from the present form of Lemma 1 and the fact that and
ProvG(‘Vq53xR (4, x,a)’) -ProvG(ElxR ProvZ ( ‘ v ~ ~ x(4, R x,
~1)’)
(8, x, a)’)
c-.Provz ( ‘ 3 x ~(8, x,a)’)
are !&provable, 4. A formula of 6 is said to have the property Q, if it has no quantifiers onf-variables (and no Aj’s in case 6 is SEID) and no free t-variables, but possibly has some free $variables.
264
G . TAKEUTI
and
M. YASUGI
DEFINITION. Let A be a formula of 6 having the property Q. We define A-subformulas as follows : A is an A-subformula; if B A Cis an A-subformula, so are B and C; if i C is an A-subformula, then so is C ; if VxC(x) is an Asubformula, then C(n) is an A-subformula for every numeral n. Notice that every A-subformula has the same property Q and contains only freef-variables in A. Let PA(a) denote the following statement: a is (the Godel number of) a sequence whose formulas are only A-subformulas. We can give the truth definition TA,for A-subformulas, and consequently for the sequences which satisfy PA.It is well known that TA is defined by an arithmetical formula with second order parameters (cf. e.g. 131).
LEMMA2. Let A be a formula having the property Q. The following are 5$-provable: 1 .O
TA (‘VxB(x)’)
w VbTA( r B ( n (b))’),
where V x B ( x ) is an arbitrary A-subformula, and n(b) denotes the b-th numeral.
1.1.
TA (‘B v C’)
tf
TA (rB’) v TA (rC’),
where B and C are any A-subformulas. 1.2.
TA (‘B’)1++ ITA CB’) ,
where B is an arbitrary A-subformula. 2.
T’.CB(n(b,), ..., n(bk)Y)-B(bl, ..., b k ) ,
where B(0, ..., 0) is an arbitrary A-subformula. 3.
PA(a), ProvZ ( a ) + T A ( a ) .
Proof of 3. For simplicity, we shall denote TA by T. Assume PA(a) and Provz (a). Let P be a proof-figure such that Provz CP’, a). Let r (b,, ..., bk)+ + A (b,, ..., bk), where all the free t-variables containing it are fully indicated, be an arbitrary sequence contained in P . We can prove by induction on the number of inferences in the proof-figure to r ( b , , ..., bk)+A(bl, ..., bk) that r (n(c,), ..., n (ck))-+A (n(c,), .. ., n (ck))is provable in 6,where c,, ..., ck range over all the k-tuples of natural numbers; and moreover, by arithmetizing the above proof and using the properties 1 and 2, we can prove
T r ( n ( c l ) , . . . , n ( C k ) ) - - t A ( n ( c , ) , ..., n ( 4 Y ) in ’Q. This proves 3.
265
SUBSYSTEMS OF ANALYSIS
5. THEOREM 1 (REFLECTION PRINCIPLE). Let R(a, b, a ) be a formula of 6 which is elementary in a and contains no free t-variable other than a and b. Then Ind, ProvG(‘Vx3yR(x, y, a).) -+ V x 3 y R ( x , y , a)
(a),
is 9-provable. Proof. Let Vx3yR(x,y , x ) be the A in 4 and define T, as in 4 Prov, (‘Vx3yR (x, y , a).)
(1)
is provable in (2)
Ind,
+ Va
Prov, (‘3yR ( n (a), y , a)’)
9.
(a), ProvG(‘3yR ( n (a), y , a)’) -+
Provg (‘3yR ( n (a), y , a)’)
is 9-provable by Lemma 1 for any free t-variable a. Provz (‘3yR ( n (a), y , a)’)
(3)
--f
T (‘3yR
(12
(a), y , a)’)
is !&provable by 3 of Lemma 2, since PA(r3yR(n(a),y , a)’) is 9-provable.
VaT(‘3yR ( n (a), y , a)’)
(4)
-+
T (‘Vx3yR (x, y , a)’)
is 9-provable by 1.0 of Lemma 2. T (‘Vx3yR (x,y , a)’) -+ Vx3yR (x,
(5)
J’,
a)
by 2 of Lemma 2. From (1)-(5) we have that Ind, (a),ProvG(‘Vx3yR (x, y , a).)
-+
V x 3 y R (x, y , a )
is ‘@-provable. Remark As we remarked in the introduction, we can prove the uniform reflection principle by modifying the proof of Theorem 1. THEOREM 1’. 1ndl (a),Vrn (Prov, (‘Vx3yR (x, y , a,n (m)).) -+ V x 3 y R (x, y , a, m ) ) . LEMMA 1’. Ind,
(a),Prov,
(5IxR’(x, a,I I On)>.)-+ Provg (‘3xR’(x, a, n (m))’) .
This lemma is provable from Lemma 1 by replacing ‘3xR(x,a). by ‘3xR‘(x, a, n(m))’. Then by taking VzVx3yR‘(x,y , a, z ) as A in 4, (1)-(5) in the proof of Theorem 1 are provable for ‘Vx3yR‘(x,y , x , n(m))’ instead of ‘Vx3yR ( x ,y , a)’. 6. Let
9‘be the system obtained
from
by adding second order pure
266
G . TAKEUTI
and M. YASUGI
logic, where mathematical induction is restricted to apply only to the formulas of ‘p. Then from Theorem 1 we have the following COROLLARY. Let R(P, a, b, a) be a formula of 6which is elementary in P and x . Then Ind,
(D), Prov,
(‘V4Vx3yR
( 4 , x,Y , a).) -,V4Vx3yR (4, x , Y , a )
is p-provable. Chapter I1 7. In this chapter we shall consider the systems SINN and SEID and call each of them G. Let 33 denote the system of o.d.’s which is used in proving the consistency of 6 (cf. 1 of this article). is the system which has been defined in 3. Let B(a) be an arbitrary formula of 9 of the form
(*I
3 x , v y , ... 3x,VynBo(a,
~
1
...) , x,, Y n ) ,
where B0(a, a,, b,, ..., a,, b,) is a quantifier free formula whose only free variables are CI, a,, b, ..., a,, b,. B(a)-subformulas are defined as in 4 of Chapter 1. LEMMA 3. Given B(a) which satisfies (*), we can define the truth definition TB(cI) for B(a)-subformulas in ‘p with a Z : , formula having the second order parameter CI.It is obvious that TB(a)can be extended to the sequences of which formulas are B(a)-subformulas. 8. Let B(a) be a formula satisfying (*). We define the condition SB(@) as follows: Let ‘S’ denote the Godel number of a sequence S. By “ we mean that the quoted sentence is actually an arithmetized formula. S, (B(a); ‘S’): “Each formula of S is a B(a)-subformula”. S , ( ‘ S ): “Each formula in the left side of S is quantifier-free”. S,(B(a); T ) : 1TB(a)(rSl). SB(a)(rS1):S , ( B ( a ) ; ‘ S ~ ) A S , C S ~ )SA3 ( B ( a ) ;‘Sl). From now throughout this chapter, B(a) shall be arbitrary but fixed so that it satisfies (*). For simplicity we shall abbreviate TB(a)and S,(,, to T and S respectively. ”
PROPOSITION 2. Ind, ( D),Prov, ( p , ‘ B (a).), is p-provable, where
i T
(‘B (a>.) -,3q
<*p (Pf * ( 4 )
A
S (ends ( 4 ) ) )
<. is the well ordering of o defined in 3 of Chapter I
SUBSYSTEMS OF ANALYSIS
267
and Ind, (a)is the schema which allows transfinite induction along the order with respect to Z:,+ formulas. The proposition is a trivial consequence of i
d
LEMMA 4.
is p-provable. 8.1. The lemma is proved by applying Ind,
(a)to the following formula:
Since T and S are in Z& and I& respectively, the induction formula is in with the parameter tl. It is now obvious that in order to prove (1) it suffices to show
Z:,,+
if Pf* ( p ) , then we may take p itself as q in (1). 8.2. Assume S(ends(p)) A PfG(p)A i P f g ( p ) and find a q which satisfies (2). This is done like the consistency proofs in [7], although, strictly speaking, the whole argument is developed in the arithmetized language. Let P be the proof-figure with the Godel number p . 1) Preparations for reduction, which is seen in 2 through 8.2 except 7 in Chapter 2 of [7], are applicable. 2) If there is an explicit logical inference or an induction in the end piece of P, then the proof is carried out according to the bottommost such inference. 2.1) The last such inference is an 3 right on a t-variable. Let P be of the form ..
Notice that ti is a closed term and primitive recursive. Therefore ti can be computed and is equal to a numeral mi. P is reduced to the following.
268
G . TAKEUTI
and M.
YASUGI
269
SUBSYSTEMS OF ANALYSIS
2.3) All other cases of logical inferences are proved easily. In virtue of S, (ends(p)) and S,(ends(p)), there is no V left on a t-variable and no 3 left on a t-variable. 2.4) The last inference which satisfies the condition is an induction. This case is proved as in [7]. 3) Now we may assume that there is no explicit logical inference or induction in the end piece of P . Hereafter we can follow exactly the consistency proofs of [7]. Thus we have proved Lemma 4.
9. PROPOSITION 3. Ind, (D), ProvG(rB(a)’), i T(‘B(a)’)-+ is p-provable, where B(a) satisfies (*). Proof. From the definition of T, Provz(q)-+T(ends(q)),which contradicts S , (ends(q)). Thus the proposition follows from Proposition 2. 10. THEOREM 2.
Ind,
(D), Prov,
(‘A (a)’)
-+
A (u)
is p-provable for an arbitrary arithmetical sentence A ( u ) with a second order parameter a, where Ind,(D) applies to the formulas of V, that is to the formulas arithmetical in some second order parameters. Proof. It is well-known that A (a) tf B (4
(1)
is !&provable for some B(u) which satisfies (*). Ind, (ID), Prov, (rB(~)7) 4 TB(a) (‘B (a)’)
(2)
and (3)
TB(a)
(rB (‘>’)
are p-provable from Proposition 3 and Lemma 3 respectively. It is also known that ProvG(‘A (a)’)
(4)
tf
Prov, (‘B
(MY)
is p-provable. (1)-(4) yield the theorem. Remark. Here again we can prove the uniform reflection principle.
THEOREM 2‘. Ind, (ID)
-+
Vrn (ProvG(‘A (a, n (m)>.)k A (a, m ) ),
where Ind2(ID) applies to the formulas of
13.
270
G . TAKEUTI
and
M. YASUGI
This is proved with the similar modifications that have been carried out in the proof of Theorem 1’. Namely first apply Lemma 4 to ‘B(a, n(m)). in place of ‘B(a)’. Then take VzB(a, z ) as B(a) and define the truth definition for B(a). The rest of the proof of Theorem 2 goes through after this alteration. 11. Let ‘p’ be the system defined in 6 . Then from Theorem 2 we have the following
COROLLARY. Let A ( @ ) be an arithmetical sentence with a second order parameter a. Then Ind,
(a),Prov, (rv4A (4)’)
-+
V 4 A( 4 )
is p’-provable, where Ind,(lD) applies to the formulas of
p.
12. Now we are going to present another formulation of the reflection principle for the formulas V 4 A (+), where A (a) is arithmetical in a. We shall state it in the form of the uniform reflection principle. THEOREM 3. Let A(a, a) be arithmetical in free variables of A . Then (1)
Ind’ (ID), Prov, (‘VW
c(
(4, n (a))’)
and let a and a be the only
--f
V 4 A (4, a )
is 6-provable, where Ind’(D) applies to Zi formulas with a second order parameter. Proof. 12.1. First there exists a quantifier free formula R(a, b, c, a) for which (2)
V4A (4, a ) - V 4 3 x V y R
(4, x, y , a>
is 6-provable. (2) implies (3)
Prov, (‘V4A (4, n (a)>.) -Prov,
(‘Vq53xVyR (4, x, y , n (a)>.)
is (3-provable. (2) and (3) guarantee that, in order to prove (l), we only have to prove (4)
in
Ind’(ID), Prov, (‘3xVj’R (a, x, y , n (a)>.) + 3xVyR (a, x, y , a )
(3.
12.2. (4) follows from (5)
Ind’( ID), ProvG(‘3xVyR (a, x, y , n (a)).), i T (‘3xVyR (a, x, y , n (a))’)
+
,
271
SUBSYSTEMS OF ANALYSIS
which is proved like Proposition 3. Notice that T is the truth definition for 3xVyR(a, x,y , a) so that we may assume it is a Z x formula with the parameter a, which implies that Ind'(53) is applies to Z: formulas with the parameter a. 13. Remark. Kreisel has suggested* the following argument to show: We cannot prove (1)
Prov, P ' 4 3 x V y R (4, x, y)'> + V 4 3 x V y R (4, x, Y >
by adding to G all true 1;sentences as axioms. (The idea of the proof is that we cannot obtain a new provable well-ordering by this addition by a result of [ 2 ] ; on the other hand, (I) provides a new provable well-ordering whose order-type is the supremum of all the provable well-ordering in G.) This implies that we cannot prove Prov, ( W A (4)')
-+
V#A (4)
2
where A ( a ) is arithmetical in a, by adding to G Ind(53) which applies to arithmetical formulas without second order parameters. 14. Appendix Here we wish to state an application of the proof of the theorem in Chapter 5 of [7] (also cf. [6]), although this has no direct bearing on the reflection principles :
THEOREM. Let 6 be SINN or
(which may contain recursive functions as functional constants) and 33 the system of ordinal diagrams used to prove the consistency of (5;and let Q ( a ) be a recursive predicate (containing no logical symbols) and a < .b a recursive linear ordering of the set Q (= {a[Q (u)}). Then, if <. is a provable recursive well-ordering in 6, there exists a ZZ: orderpreserving one-one map (T from Q into 33. Proof. We can arithmetize notions concerning TJ-proof-figures with respect to 6 as usual: Let P(u, b) express that "a is the Godel number of a TJ-proof-figure whose end-number is b". By the value of a TJ-proof-figure P we understand o(P)#O("), where o ( P ) denotes the value of P in the sense of [6] (i.e. the 0.d. assigned to P ) , a is the Godel number of P and O@) is defined by O(")=O and O(i+l)=O(i)#O. (By this modification of the value no two TJproof-figures have the same value unless they are identical.) Let a 4 b be the arithmetization of the well-ordering of 53 and u(a) the function expressing SEID
* Several remarks were communicated privately to the first author. We are grateful to Piofessor G. Kreisel for his valuable comments.
272
G. TAKEUTI
and
M. YASUGI
the Godel number of the value of a TJ-proof-figure with the Godel number
a. These notions concerning arithmetization can be chosen to be primitive recursive. Let o(a) be defined by
b = a ( a ) o P ( b , a ) ~ V ~ ( P ( x , a ) - + o ( b ) < ov( o~ ()x ) = o ( b ) ) . dfn
If b = a (s), then b is (the Godel number of) a critical proof-figure (for, otherwise, b would be reduced to a TJ-proof-figure with the same end-number s). a is order-preserving: i.e. if s<. t , then o(o(s))
15. Additional remark (added on Feb. 22, 1967) We say “transfinite induction on 4.’’ is introduced by a rule, when we admit a formula VxA (x) to be provable, if it is provable under the hypothesis
vx ( V y ( y
<-x t- A ( y ) ) t- A (x))
.
This rule is called the transfinite induction rule on A ( x ) . It should be remarked that T + A , VxA(x) is not considered to be provable even if it is provable under the hypothesis VX
(VY(Y
<*X 1’4 ( Y ) ) t- A ( x ) ) .
Therefore the rule is weaker than the ordinary induction schema. We can apply the rule repeatedly. For example, we can prove VxB(x) by using
Vx (Vy (y <-x t- B ( y ) ) t- B (x))
and VxA (x) after we prove VxA (x) .
In this paper transfinite induction along the ordering <*of ID is introduced as a schema. However in the proof of Theorems 1,2, l’, 2’ and 3, the schema can be replaced by the rule described above. More precisely we apply the rule only once in each case. For example, in Theorem 1, we can replace Ind, (ID) by the transfinite induction rule on a C(: formula (without second order parameter). Kreisel pointed out that this result is best possible i.e. we cannot replace .Z: transfinite induction rule by lZ(: transfinite induction rule, here. Suppose that lI(:transfinite induction rule is sufficient to prove the reflection principle in Theorem 1. Then, since V x A (x) is I7: if A (x) is IZ:, the reflection principle in Theorem 1 can be proved in @ with true f l y sentences. We can show that
SUBSYSTEMS OF ANALYSIS
273
the reflection principle in Theorem 1 cannot be proved by adding to even 6 any true I l y sentences. For the reflection principle in Theorem 1 provides an enumeration of the provably recursive functions of 6 and addition of true Ily sentences does not increase the class of provably recursive functions (cf. Section 5 of Kreisel, J. Symb. Logic 23 (1958)). He also pointed out that VI,bVx3yR($, x,y ) is equivalent to Vx3yR, (x,y ) for some primitive recursive R , using his theorem in Note 111 of British Journal for Philosophy of Science 4 (1953). Therefore the presence of CI in Theorem 1 is not essential. References 1 . A. KINO,On ordinal diagrams, J. Math. Soc. Japan 13 (1961) 346-356. 2. G. KREISEL, Status of the first &-numberin first order arithmetic, J. Symb. Logic 25 (1960) 390. 3. G. KREISEL and A. Levy, Reflection principles and their use for establishing the complexity of axiomatic systems, to appear. 4. G. TAKEUTI, Ordinal diagrams, J. Math. Soc. Japan 9 (1957) 386-394. 5 . G. TAKEUTI, Ordinal diagrams 11, J. Math. Soc. Japan 12 (1960) 385-391. A remark on Gentzen’s paper “Beweisbarkeit und Unbeweisbarkeit von 6. G. TAKEUTI, Anfangsfallen der transfiniten Induktion in der reinen Zahlentheorie”, I, 11, Proc. Japan Acad. 39 (1963) 263-269. 7. G. TAKEUTI, Consistency proofs of subsystems of classical analysis, Ann. of Math. 86 (1967) 299-348.
E Q U A T I O N A L LOGIC A N D E Q U A T I O N A L T H E O R I E S OF ALGEBRAS
A. T A R S K I * University of California, Berkeley, USA In this paper we shall introduce various metalogical notions referring to equational theories of algebras and, more generally, to equational logic. The purpose of the paper is to give a short survey of the results obtained and open problems concerning these notions. Some of the results announced in the paper appear in print for the first time. 1. Algebras and their equational theories
By an algebra we understand here a system 'u= ( A , 0,, ..., 0,) formed by a non-empty set A and a finite sequence of finitary operations O,, ..., 0, from and to elements of A ; A is the universe (or the carrier) and 0,, ..., 0, are the fundamental operations of the algebra a. The sequence of ranks of O,, . .., 0, is called the (similarity) type of 'u; two algebras of the same type are said to be similar. In particular, algebras ( A , 0) of type ( 2 ) are frequently referred to as groupoids. A fundamental operation of rank 0 is usually identified with the unique element constituting the range of this operation; such an element is called a distinguished element of the algebra. All classes of algebras discussed here are assumed to consist of similar algebras. Many basic properties of algebras are expressed by means of equations, i.e., formulas of the type o = z where a and z are terms in the first-order theory of the algebra discussed. Thus, o and z are formed from variables ranging over elements of the universe and from symbols denoting fundamental operations of the algebra. To avoid the use of parentheses we always put
*
This is an outline of a n address given by the author to the Colloquium on Logic and Foundations of Mathematics, Hannover 1966. The paper was prepared for publication when the author was working on a research project in the foundations of mathematics sponsored by the National Science Foundation, Grant Number GP-6232X. The proofs of new results announced in this paper will be published elsewhere. 275
276
A. TARSKI
an operation symbol in front of the variables to which it refers. A symbol denoting a distinguished element, i.e., an operation of rank 0, is often called a constant or an individual constant. The part of predicate logic in which equations are the only admitted formulas can be construed as a separate formal system and called equational logic. In this logic equations a = z with variables xl,. ..,x, are treated as if they were sentences
vx, ...x,(a
= T)
where V is the universal quantifier. We assume it will be understood what is respectively meant by the statements that an equation (T = T is a consequence of, or is derivable from, a set C of equations. The first of these two notions is defined semantically in terms of models or satisfaction; the second is defined proof-theoretically in terms of operations (rules) of direct injierence. Three such operations are used in equational logic: the operation of including the tautology x=x in every set of derivable equations, the operation of substitution, and that of replacing equals by equals. The notions of consequence and derivability are equivalent by virtue of the completeness theorem for equational logic, first proved by Birkhoff [l]. Two systems of equational logic differ only in operation symbols; each system is determined by a finite sequence (without repeating terms) a = (a1,..., a,) of all operation symbols occurring in it. To discuss algebras ( A , 0,, ..., 0,) of a given similarity type we choose the sequence a in such a way that, for each L=l, ..., v, the symbol a, has the same rank as the corresponding operation 0,. By the equational theory of an algebra 'LI, or a class K of algebras, we understand the set of all equations, in the system of logic determined by a, which are identically satisfied in the algebra 'LI, or in all algebras of K. We denote this theory by O,'u or @,K; usually we need not specify the sequence of operation symbols, and we can denote the equational theory simply by 02,or OK, without causing any misunderstandings. I t is known that for every class K of algebras there is an algebra 'LI such that @%=OK. K is said to be an equational class of algebras or a variety if it consists of all models of some set C of equations (or, equivalently, of the set OK). A well-known theorem of Birkhoff [l] provides a set of conditions, of a purely algebraic nature, which is necessary and sufficient for a class K to be equational. Two theories 0 and with two different sequences a and 5 may of course have the same class of models; the equations of one theory can then be obtained from those of the other simply by exchanging the corresponding operation symbols a, and 0,. We refer to two such theories as isomorphic.
EQUATIONAL LOGIC
277
A set 0 of equations is called an (equational) theory if 0 =@?Ifor some algebra % or, equivalently, if 0 consists of all equations derivable from a set C of equations. Such a set Z is called a base for 0 ; 0 is said to be generated by C and is denoted by O[C]. By a base (or equational base) for an algebra 3,or a class K, we mean any set C which is a base for @?I,or OK, respectively. Let 0 and 0‘ be two equational theories. If 0 is included in 0‘ (and hence, in particular, all the operation symbols of 0 are among the operation symbols of Of),we say that 0 is a subtheory of 0’and that 0’is an extension of 0. When speaking of subtheories of a given theory we always mean here subtheories with the same sequence of operation symbols; on the other hand, we shall sometimes consider extensions of a theory with additional operation symbols. Given a theory 0, an operation symbol 0 of rank, say, v, not occurring in 0, a sequence of v distinct variables xl, ..., x,, and a term z of 0, assume that the following condition is satisfied: either no variable different from xl, ..., x, occurs in z or, if such a variable y does occur, and z‘ is any term obtained from z by replacing some occurrences of y by occurrences of another variable, say, z, then the equation z=z’ belongs to 0. Under this assumption, the equation Oxl . . . x v = z
(orO=zincase v = O )
is called a possible definition of 0 in 0. Let 0’ be an extension of 0 and let O,, ..., 0, be all the distinct operation symbols occurring in 0‘but not in 0. We call 0’ a dejinitional extension of 0 if there is a set C of possible definitions of the symbols O,, ..., 0, in 0, one definition for each symbol, such that 0’ is generated by 0 UC (the union of 0 and Z). We say that two theories 0 and 0‘are directly dejinitionally equivalent if they have a common definitional extension, and that they are dejinitionally equivalent if any two theories 0 and 8’which are respectively isomorphic with 0 and 0’and have no common operation symbols are directly definitionally equivalent. If K and K’ are two equational classes of algebras, and their theories OK and OK’ are definitionally equivalent, then K and K’ are also called dejinitionally equivalent. 2. Finitely based theories
A theory 0 is said to befinitely based if it has some finite base; similarly for an algebra ?I or a class K. It is known that every base C of a finitely based theory 0 has a finite subset which is also a base for 0.
278
A. TARSKI
For various classes K of algebras, and in particular of finite algebras (i.e., algebras with finite universes), the problem of determining which algebras in K are finitely based was frequently raised and studied. Obviously, every one-element algebra is finitely based and has the single equation x = y as a base. Lyndon [2] proved that every two-element algebra is finitely based. In Lyndon [3] he exhibited a seven-element groupoid which is not finitely based. More recently Murskii [4] presented a three-element groupoid with the same property. Oates and Powell [5] proved that all finite groups are finitely based. Perkins [ 6 ] obtained an analogous result for all three-element semigroups (groupoids which satisfy the associative law), but he also constructed a six-element semigroup which is not finitely based; for semigroups with four and five elements the problem is open. An outstanding open problem is whether every infinite group is finitely based. The problem has been solved affirmatively(by B. H. Neumann, Lyndon, and others) for various special classes of groups, such as Abelian, metabelian, and nilpotent groups; an account of the results obtained so far can be found in Neumann [7], page 22. Perkins [6] has shown that every commutative semigroup is finitely based and has extended this result to some classes of non-commutative semigroups.
3. One-based theories If an equational theory 0 is finitely based, we may wish to determine the least number of equations a base of 0 can contain, and in particular to answer the question whether 0 has a base consisting of just one equation. If the answer is affirmative, 0 is said to be one-based; similarly for algebras and classes of algebras. While every one-element algebra is one-based, simple examples of algebras which are not one-based can be found among two-element groupoids. All the two-element groupoids can be divided into seven classes such that any two groupoids in the same class are isomorphic or dual-isomorphic. D. H. Potts has shown that the algebras in two of these classes are not one-based; as representatives of these classes we can take any two algebras ( A , 0) and ( A , Q ) where A consists of two distinct elements, a and b, and where Oaa =a = Qab while Oxy = b and Qxy =b otherwise. Concerning the algebra ( A , 0) see Potts’ note [8]. The algebras in the remaining five classes are known to be one-based. The problem of determining which classes of algebras are one-based has been studied exhaustively for groups and rings. Groups are usually treated as algebras 8 = (G, C, I ) of type (2, l), with
EQUATIONAL LOGIC
279
the binary operation C , group composition or multiplication, and the unary operation Z, formation of inverses. They can also be treated in many other ways, e.g., as groupoids (G, D ) where D is the left-hand division (with Dxy standing for x.y-'), or as algebras (G, C, 0)of type (2,2), etc. In all these cases the unit element E can be included in the definition of a group; groups then become algebras (G, C, Z,E ) of type (2, 1,0), or (G, D , E ) of type (2,0), etc. The class of all groups under each of these treatments is equational, and any two classes corresponding to two different treatments are definitionally equivalent. (Groups can also be treated as groupoids (G, C ) with the group composition C as the only fundamental operation. The class of groups so treated is not equational and is not definitionally equivalent with any of the classes previously mentioned.) It was shown in Tarski [9] that the class of Abelian groups treated as groupoids (G, D ) is one-based. Higman and Neumann [lo] obtained a much stronger result by showing that every finitely based class of groups (G, D ) is one-based. The author has established a still more general theorem, which implies the result of Higman and Neumann as a particular case and permits extending it to several other treatments of groups:
.
THEOREM 1. Let 0 be a jinitely based equational theory with a binary operation symbol D and at most one additional operation symbol 0 of an arbitrary rank, say, v. Assume that 0 contains the equation (i)
DDDvvDx~DDuux= y
and also, in case 0 actually occurs in 0 , the equation (ii)
O(Duu)'
= Duu
(or 0 = Duu if v = 0).
Under these assumptions 0 is one based. In (ii) we use (Duu)" as an abbreviation for the expression obtained by repeating Duu v times. A closely related result is THEOREM 2. Theorem 1 remains valid if equation (i) is replaced by two equations: DyDyx = x and D x x = Dyy . From Theorem 1 we conclude directly that every finitely based class of groups treated as algebras (G, D ) , (G, D, E ) , ( G , D, I ) , or ( G , C , D ) is
280
A. TARSKI
one-based; by means of a simple additional argument we extend this result to groups (G, C, Z). It seems, therefore, interesting that the result cannot be extended to groups treated as algebras (G, C, I,E ) , (G, C, D,E ) , or (G, D,I, E ) : it was shown by Thomas Green and the author that under none of these treatments is a class of groups one-based unless it consists exclusively of one-element groups. Each such class, however, if it is finitely based, has a base consisting of two equations. The notion of a one-based equational class of algebras, i.e., a class consisting of all models of a single equation, is a model-theoretical notion; we may be interested in providing a simple and purely mathematical characterization for this notion, just as it has been done for other related notions (such as equational class, finitely based equational class, elementary class, universal class, etc.). The problem is still open, but the results obtained for groups throw some interesting light on it. To fix the ideas, let K be the class of all groups (G, C , I,E ) and K* the class of all groups (G, D,E ) . K and K* are definitionally equivalent; as a consequence, we can establish a natural oneone correspondence between the members of these two classes which preserves all the properties of groups and classes of groups expressed in such terms as subalgebra, isomorphism, homomorphism, direct product, ultraproduct, etc. Nevertheless, as we have seen, K* is one-based while K is not. The conclusion is that a mathematical characterization of one-based equational classes cannot be given exclusively in terms of subalgebra, isomorphism, etc. (although these notions proved to be adequate for all analogous purposes in the past). The results for groups have been extended to rings. Rings can be treated, e.g., as algebras ( R , C, I,M ) of type (2, 1, 2), with ring addition C, the formation of negatives (additive inverses) I,and ring multiplication M , or as algebras ( R , D,M ) of type (2,2) with ring subtraction D and ring multiplication M. Similarly, rings with unit 1 can be treated as algebras (R,C, I, M , 1) of type ( 2 , 1,2,0), or as algebras (R, D,M , 1) of type ( 2 , 2, 0). A direct consequence of Theorem 1 (or 2) is that every finitely based class of rings ( R , D,M ) is one-based. On the other hand, the author has shown that the class K’ of all rings (R,C, I, M ) is not one-based; the same applies to all finitely based equational subclasses of K containing a ring, with more than one element, in which the product of any two elements is zero. However, each such subclass of K has a base with two equations. Green has proved that all other equational subclasses of K are one-based. The solution of analogous problems for rings with unit is based upon the following general theorem:
EQUATIONAL LOGIC
281
THEOREM 3. Let 0 be ajinitely based equational theory with two binary operation symbols, D and M , an individual constant, 1, and arbitrarily many other operation symbols of arbitrary ranks. Assume that 0 contains equation (i) of Theorem 1, or both equations of Theorem 2, and moreover any three of the following four equations: MXDUU= DUU, MDUUX= DUU, Mxl = x, M l x = x.
Under these assumptions 0 is one-based.
This theorem was established by the author with the help of Theorems 1 and 2. A somewhat weaker, though essentially the same, result was obtained by McKenzie using a different method and was announced in an abstract of Gratzer and McKenzie [ll]. It is easily seen that every equational theory which has a one-based definitional extension is itself one-based. This simple observation leads to a useful improvement of Theorem 3 :
THEOREM 4. I f an equational theory 0 satisjies all the assumptions of Theorem 3, then every equational theory 0’ which is dejinitionally equivalent with 0 is one-based. As a direct consequence of this theorem, every finitely based class of rings (R, D, M , 1) or (R, C , I , M , 1) is one-based, and the same applies to classes of rings with unit under any other definitionally equivalent treatment. In particular, Boolean algebras can be treated as Boolean rings with unit, i.e., as rings ( B , D, M , 1) satisfying identically the equation M x x = x . Several other treatments of Boolean algebras are known which are definitionally equivalent with the one just described. Thus, for instance, Boolean algebras can be treated as algebras ( B , J , M , K ) of type (2,2, l), with two binary operations, the formation of joins J (Boolean addition) and the formation of meets M (Boolean multiplication, coinciding with ring multiplication under the first treatment), and one unary operation, the formation of complements K ; they can also be treated as algebras ( B , J , K ) of type (2, 1) (where J and K are the same operations as before) or, finally, as groupoids ( B , E ) , with the operation E of exclusion (Sheffer’s stroke operation). Theorem 4 implies that the class of Boolean algebras under any one of these treatments is one-based.
282
A. TARSKI
It is well known that the equational theory of any single Boolean algebra
23, say, % = ( B , J, M , K ) , with more than one element coincides with the theory of the class of all Boolean algebras; hence, 23 is one-based. In case the
Boolean algebra %4 has just two elements, it is a primal algebra in the following sense: if B’is any algebra obtained from B by adjoining new fundamental operations (from and to elements of B), then 0%’ is a definitional extension of 0%.Clearly, every primal algebra is finite. An easy consequence of Theorem 4 is that every primal algebra is one-based. This last result was obtained independently by Gratzer (even before Theorem 4 was known) and was stated in Gratzer and McKenzie [ll]. 4. Independent bases
A set Z of equations is called independent (or irredundant) if no equation in this set is derivable from the remaining equations. Given a theory O we shall denote by V O the set of all cardinals v such that O has an independent base C with cardinality v ; similarly we define V%, V K . For any given 0 we may be interested in determining the set VO. The discussion of this problem has been simplified by the following result of the author : THEOREM 5. Let 0 be an equational theory. If K , 1, and p are threeJinite cardinals such that r c < l < p , and K , p E VO, then I E V O . In a more general form this result applies, not specifically to equational logic, but to a wide class of formal systems with finitary operations of direct inference. The latter, treated as operations from formulas to formulas or to sets of formulas, may be of different ranks; e.g., substitution is of rank 1, while the replacement of equals by equals and modus ponens are of rank 2. The result holds for all formal systems in which the ranks of all operations of direct inference do not exceed 2. Actually, the result can be given a still more abstract form, and in this form it can be applied, outside of metamathematics, in the general theory of algebras (and of arbitrary relational structures). Let, for instance, % be any algebra, even with infinitely many fundamental operations, in which, however, no fundamental operation is of rank greater than 2. Let K , I , and p be again three finite cardinals such that K
EQUATIONAL LOGIC
283
THEOREM 6. Let 0 be an equational theory. r f 0 consists exclusively of tautologies z= z,then
vo = ( 0 ) .
(i)
r f 0 is finitely based, but does not consist exclusively of tautologies, then VO is either a bounded or an unbounded interval of non-zero finite cardinals; i.e., either
(ii) for some (iii) for some
vo = [ K , p] = ( A : K < A < p} K,
p with 0
VO = [ K , w ) = (A:K K
with O < K < W .
IA finally, 0 is not finitely based, then either
(iv) or else (v)
VO = O
vo = { w ) ,
(i.e., VO is empty).
An essential supplement to Theorem 6 is
THEOREM 7. For each of the formulas (i)-(v) of Theorem 6 there are equational theories 0 satisfying this formula; formula (ii) can be satisfied for any given cardinals K , p (O< K < ~ < w )and , formula (iii) for any given cardinal K (O
284 YY:
6,:
A. TARSKI
o v + ~ y x l x... z x,y = ov+'yx, ... xvx1y, 0'yx1x, ... x , = o v + ~ y x l x... z x, oyy,
for v = 1,2, 3, ... . The set V 0 has been determined for various theories 0 of the form 0 = 0 [C] where C is a set consisting of some of the equations E ~ - E ~ y,, , and 6,. If, e.g., C = { E ~ } ,then V 0 = [ 1 , 0). If C is one of the sets { E ' , E ~ or } { E ~ E, ~ or } { E ~ E, ~ E, ~ } ,then V 0 = [ 2 , w). (It was pointed out by Potts [8] that 1 $ V 0 and 2 ~ V in0 case ~ = O [ { EE,,, ,E ~ } ] . )If C= { E ~ } then , V 0 = { 1 , 2 } = [ 1 , 2 ] . If Z = { y , : O < v < o } , then V O = { o } ; if C = { y , : O < v < o > u {6,:O
THEOREM 8. Let 0 be an equational theory with arbitrary operation symbols. Let x be a variable, and z be a term in 0 with at least two occurrences of x; assume that the equation z=x belongs to 0.If 0 < K < I < w and K E V O , then 1EV0. Some improvements of this result are also known. By comparing Theorem 8 with various results stated in section 3, we arrive at the following conclusion: if 0 is a finitely based theory of a class of groups or rings (under any treatment of these notions discussed in section 3), then either V 0 = [l , o)or V 0 = [ 2 , o),dependent on whether or not 0 is one-based. This solves a problem raised by Higman and Neumann [lo] for theories of groups ( G , D}. Let 0 be a finitely based theory of a class of lattices, treated as algebras ( L , J, M ) of type ( 2 , 2 ) with the operations of forming joins and meets. It has been announced by Padmanabhan [12] that 2 ~ V 0 Hence, . by Theorem 8, V 0 2 [2, 0).McKenzie has recently proved that 1 $ V 0 if and only if there is a lattice which is not model of 0 and there is a lattice with more than one element which is a model of 0. The following question arises in a natural way: Let r be a finite independent set of K equations belonging to a theory 0 but not forming a base for 0; let K c 1 < w and I E V O . Can we always extend r to an independent set A of A equations which is a base for 0?In general the answer to this question is negative. For instance, let 0 be a finitely based theory of a class of lattices; let r be an independent base for the theory of all lattices, but not for 0, and let K be the cardinality of r. As was mentioned above, we have AEVO for every A such that K<,?
EQUATIONAL LOGIC
285
theory of all distributive lattices. If we ask the same question taking for 0 any finitely based theory of a class of groups and for r an independent base for the theory of all groups, the answer is still unknown. However, the answer proves to be affirmative for theories 0 of various special classes of groups, e.g., the class of Abelian groups or the class of all groups in which the order of every element divides a given positive integer v ; r is assumed here to consist of just one equation. Turning to theories 0 without finite bases, we recall that, by Theorems 6 and 7, they can be divided into two non-empty classes characterized respectively by the formulas v @ = { ~and } V 0 = 0 . We do not know any natural and mathematically interesting examples of algebras without independent bases. In particular, we do not know whether there are groups Q with VQ =O; nor do we know whether there are groups 8 with VQ = { w } . If V ~ = { O } , then, as is easily seen, 0 has 2" subtheories (while V 0 = 0 seems to imply only that 0 has infinitely many subtheories). More generally, if V 0 = { w } and 0' is a finitely based subtheory of 0 , then there are 2" equational theories which include 0' and are included in 0. Hence, in particular, if there is a group Q with V@={O}, then there are 2" varieties of groups. 5. Consistent and complete theories ;the lattice of equational theories An equational theory 0 is called consistent if it does not contain all equations (with given operation symbols) or, equivalently, if it does not contain the equation x = y ; 0 is called complete if there is no consistent theory which properly includes 0.An algebra 2, or a class K, is (equationally) complete if and only if 02,or OK, is complete. The well-known theorem of Lindenbaum (originally established for the sentential calculus), stating that for every consistent theory 0 there is a consistent and complete theory which includes 0, extends to equational theories; its proof depends merely on the facts that all the operations of direct inference are finitary and that inconsistent theories are finitely based. In contrast to the predicate logic, a sharper form of this theorem, to the effect that every theory is the intersection of all complete theories which include it, does not apply to equational theories. Actually many incomplete theories are known which can be extended to just one consistent and complete theory. For some important classes of algebras all equationally complete members of these classes have been fully determined. Thus, Kalicki and Scott [13] have shown that the only semigroups ( A , C ) which are complete are first the
286
A. TARSKI
"trivial" semigroups satisfying one of the three equations Cxy = Cuv, Cxy = x, Cuv = v, then the semilattices, and finally those Abelian groups in which all non-unit elements are of a given prime order. By a result in Tarski [14], a ring 3,with or without unit, is complete if and only if it is commutative, and there is a prime number n such that (i) every non-zero element of the ring is of order in the additive group of 3,and (ii) either the product of any two elements is zero or else every element equals its n-th power. The variety of complete equational theories appears to be rather sparse. Nevertheless Kalicki [15] was able to show that there are 2'" complete theories with, say, one binary operation symbol. The set T of all equational theories, with a fixed sequence 0 of operation symbols, is lattice-ordered by the inclusion relation. If we define the meet of two theories 0 , O ' E T as the intersection 0 n O', and the join as the theory generated by the union 0 v O', then T together with these two operations forms a lattice QU. The meet and join of an arbitrary subset S of T are defined analogously. The lattice is complete; the inconsistent theory, i.e., the set of all equations, is the unit element, and the theory consisting of all tautologies is the zero element of the lattice. The complete and consistent theories are the maximal non-unit elements of the lattice; thus, every non-unit element is included in a maximal non-unit element. On the contrary, it is easily seen that the lattice has no minimal non-zero elements (disregarding the trivial case when all operation symbols are of rank 0). The finitely based theories coincide with the compact elements of the lattice, i.e., the elements x characterized by the following condition: if x is included in the join of any subset S of T, then it is included in a join of finitely many elements of S. The unit element is compact, and every element is the join of all compact elements included in it. It would be interesting to provide a full intrinsic characterization of the lattice & and all its isomorphic images, using exclusively lattice-theoretical terms. The characterization may, of course, depend essentially on the ranks of operation symbols occurring in the theories. In fact, McKenzie has recently shown that two lattices 2uand f$, are isomorphic just if, for every p <w, the sequences CJ and 0'contain the same number of operation symbols of rank p. The problem of characterizing intrinsically some special sublattices of the lattice may also deserve attention. In particular we have here in mind sublattices formed by all extensions of some important equational theories such as the theory of groups, rings, or lattices. Instead of the lattice of equational theories we can, of course, discuss the dual-isomorphic lattice formed by all equational classes of algebras of a given type.
EQUATIONAL LOGIC
287
6. Decision problems
Various notions, problems, and results discussed so far in this paper suggest in a natural way corresponding decision problems. These are problems of the type: is a given set of equations, or of finite sets of equations, or of finite algebras, recursive? The meaning of the term “recursive” in these contexts is clear; finite algebras can be regarded as algebras whose universe consists of finitely many integers. The conceptually simplest decision problems concern the decidability of individual theories. A theory is called decidable simply if it is recursive. Most familiar equational theories prove to be decidable. The theory of any finite algebra is of course decidable. Also, as in the predicate logic, every complete theory with a finite (or, more generally, a recursive) base is decidable. The proof uses again the fact that inconsistent theories are finitely based. There are finitely based undecidable theories. Probably the first example was given in Tarski [16]. It is the theory of relation algebras, which may be treated as algebras of type (2, 1 , 2, l), (2, 1,2) or even (2,2). Perkins [6] gives an example of a theory of groupoids with the same properties. Closely related to decidability problems are the famous ~ w r problems. d Given a theory 0 , we enrich its language with a finite set Q of individual constants. In the enriched language we construct a finite set C of equations containing no variables and we denote by [O, Q, C]the theory generated by 0 u C. The word problem for 0 is the problem of determining whether in each such theory [0,Q, Z] the set of all equations containing no variables is recursive. If we restrict ourselves here to those theories [0,Q, C] in which Q is arbitrary but C is empty, then the resulting problem is simply the decidability problem for 0. It may be noticed that, in formulating the word problem, we may take for 0 , not necessarily an equational theory, but e.g. any firstorder theory, and that the problem may then be formulated more simply in terms of so-called conditional equations (universal Horn sentences) of the original theory 0, without considering any extensions [0,Q, C]. The farreaching results obtained during the last years in the study of word problems are well known. We turn to decision problems of a different type concerning finite sets C of equations. Let S,, v = 1 , ..., 6, be the set of all such sets C satisfying respectively one of the following conditions: (cl) Z is a base for a given finite algebra 3,; (c2) there is a finite algebra ‘u for which C is a base; (cj) K,EV@[Z] for a given positive integer K,; (c,) O[Z] is consistent; (c5) 0 [C] is complete; (c6)0 [C] is decidable. The decision problems for S2,S4,S5,
288
A. TARSKI
S, were discussed and solved negatively by Perkins [6]. The negative solution for S, implies automatically the negative solution for S,, with a one-element algebra taken for go.It seems likely that a negative solution of this problem for some other finite algebras, and in particular for any Boolean algebra, can be obtained by appropriately modifying the proof of an analogous result for sentential calculus announced by Linial and Post [ 171; a detailed proof of the latter result is given by Yntema [18]. (There is much affinity between the formalisms of sentential calculus and equational logic; as a consequence, various metalogical results established for sentential calculus can frequently be carried over to equational logic with appropriate changes in formulations and proofs.) The decision problem for S,, with any particular integer, e.g., 1, taken for K ~ remains , open. We can replace everywhere in (c1)-(c6) the sets ,Z by the singletons { E } where E ranges over arbitrary equations, and denote by S: the resulting sets of equations E . The decision problems for S;-SA seem to be open. So are the decision problems for the sets K,, v = 1,2, 3, of all finite algebras 'u satisfying one of the following conditions: (el) 'u is finitely based; (e2) K ~ E V ( Ufor a given cardinal K~ (0 < K~ < w ) ; (e,) 'u is equationally complete. The problems for K, and K, were raised by Perkins [6]. Many other related decision problems for finite sets of equations and finite algebras are known.
References G. BIRKHOFF, Proc. Cambridge Phil. SOC.31 (1935) 433-454. R.C. LYNDON, Trans. Am. Math. SOC.71 (1951) 457465. R.C. LYNDON, Proc. Am. Math. Soc. 5 (1954) 8-9. V.L. MURSKII,Soviet Math. 6 (1965) 1020-1024. S. OATES and M. POWELL, J. Algebra 1 (1964) 11-39. P. PERKINS, Decision problems for equational theories of semigroups andgeneralalgebras, doctoral dissertation, University of California, Berkeley (1966). 7. H. NEUMANN, Varieties ofgroups (New York, 1967). 8. D.H. POTTS,Can. Math. Bull. 8 (1965) p. 519. 9. A. TARSKI, Fund. Math. 30 (1938) 253-256. 10. G . HIGMAN and B.H. NEUMANN, Publ. Math. 2 (1951-52) 215-221. 11. G . GRATZER and R. MCKENZIE, Am. Math. SOC.Notices 14 (1967) p. 697 [abstract]. 12. R. PADMANABHAN, Am. Math. SOC.Notices 14 (1967) p. 697 [abstract]. 13. J. KALICKI and D. SCOTT,Indag. Math. 17 (1955) 650-659. 14. A. TARSKI, Indag. Math. 18 (1956) 39-46. 15. J. KALICKI, Indag. Math. 17 (1955) 660-662. 16. A. TARSKI, J. Symbolic Logic 18 (1953) 188-189 [abstracts]. 17. S. LINIALand E.L. POST,Bull. Am. Math. SOC.55 (1949) p. 50 [abstract]. 18. M.K. YNTEMA, Notre Dame J. Formal Logic 5 (1964) 37-50. 1. 2. 3. 4. 5. 6.
THE USE OF “BROUWER’S PRINCIPLE” IN INTUITIONISTIC TOPOLOGY A. S. TROELSTRA Mathematical Institute, University of Amsterdam
The purpose of this paper is to demonstrate the strong consequences of the intuitionistic continuity postulate (called “Brouwer’s principle” by Kleene and Vesley in their monograph [2]) in an important domain of mathematics. The first section lists notations and conventions, the second one treats technical matters with the purpose of simplifying the applications, and in the third section a number of theorems is proved in order to show the consequences of Brouwer’s principle and the way it can be applied. Some of the theorems mentioned were already proved in [4]; their proofs are not repeated here; for Theorem 2 for which a proof was given in [4], a new version (more “topological”) of the proof is presented. The other theorems of Section 3 were already proved in another context in [5]; in this paper the presentation of the proofs is simplified. Our proofs are not carried out in any definite formal system, but the possibility of easy formalization was kept in mind. 1. Notations and conventions Instead of the intuitionistic notion “species” we speak of sets. For typically intuitionistic notions not defined in this paper see [l]. For the various topological notions used in this paper we can take those classical definitions which start from “open set” as basic notion. Full details are given in [5]. Now we list a few specific conventions and notations. a) i, j , k , I , m, n, s, t are used for natural numbers; N denotes the set of natural numbers (not including zero). b) tl, p, y always denote denumerably infinite sequences (functions defined on N ) . c) 6, E stand for positive real numbers. 289
A. S. TROELSTRA
50, $I, x,f are used for functions in general. cr, T are always reserved for finite sequences. * denotes concatenation of finite sequences. Sequences ( p 1 , p 2 ,p 3 , ...) are also written as ( P , ) , " , ~ =(p,>,. c( = ( a ( l ) , @(2),. . .) = (a(n)),. i?(n)=(a(l), ..., a(n)>. If a is a convergent sequence, e.g. a sequence of points in a metric space, we write limfl+ma(n)=lima. A , B, C, R , T denote predicates or relations. 0 is always used for a spread law, 9 for a complementary law ([I], 3.1.2); S = ( 0 , 9) denotes a spread. 0, is the set of all finite sequences of natural numbers. D ( O ) = ( 0 , 9) with 9 the identity. 9a=(9i?(n)),. Logical symbols: v , &, 1, -+,V, 3, 3! (there exists exactly one). Set theoretical symbols as usual: n, u,E, c etc.; denotes complementation, i.e. for a subset V of a topological space A : YC=d- V= (p:p€Ll &p$ Y } . r always denotes a complete, separable metric space, r' a complete metric space, r" a separable metric space, I"" a metric space. U(E,p ) = ( q : p ( p , q ) < ~in) spaces r'"with metric p . Likewise with rlinstead of r. m) p x A(x) denotes the smallest x such that A (x).
2. A few technicalities
In this paragraph we always suppose a, p, y ~ D ( 0 , ) ,if not stated otherwise; A is a predicate containing number- and function variables. We start with a summing-up of the various forms of the intuitionistic continuity postulate which will be used. Kreisel introduced ([3], p. 23, D9) a rather weak form of the continuity postulate, which is very manageable ([2], 7.7, p. 79): (1)
V d n A ( a , n ) - + V a 3 m 3 n V p ( ~ ( m=) jI(m)-+A(p,n ) ) .
Without essentially strengthening (I) we may suppose m a n , i.e.
(IA)
Va3nA(a, n)+Va3m3nVp((ii(m) = P ( m ) - + A ( p , n ) ) & m 2 n ) .
Kleene and Vesley introduce in their monograph ([2], p. 73) a much
29 1
“BROUWER’S PRINCIPLE”
stronger form, which they call Brouwer’s principle (for numbers):
(IT) VdnA(cc, n ) + 3 $ V a { 3 ! m $(ti(m)) > 1 &($(Cl(m)) > 1 + +
A (a?$ (i( m ) )- 1))) *
$ is a function defined on finite sequences of natural numbers. (Therefore the requirement that A does not contain $ free is superfluous here, since A contains variables for functions from N into N only.) A weak consequence of (11) is the enumeration principle: (111)
Va3nA(a, n ) -+ 3y(Va3nA(a, y ( n ) )&Vn3crA(cc, y ( n ) ) ) .
The strongest form of an intuitionistic continuity postulate we shall use is Brouwer’s principle for functions ( [ 2 ] ,p. 73)
(IV) Va3PA(a,P)-+3$Va(Vm3!n$(m,a(n)) > I & & VP [ V m h $ ( m , E ( n ) ) = P ( m ) + 1
A ( a , B11).
-+
Without essentially strengthening (1V) we can impose the following condition on the II/ in (IV):
(*I
VrnVn3k($(nz,&(n))< l & $ ( r n + l , E ( k ) ) > l - + n < I c ) .
The form of IV with (*) included is denoted by (IVA). In (IV) and (IVA) a mapping $ is defined for pairs ( m , a), mEN, CEO,. The principles (I)-(IVA) remain valid if the range of the variables a,p is restricted t o D(0). These restricted forms we denote by (I*)-(IVA*). Further we need the axiom of choice in the following form (a not necessarily in D(0,)).
Vn3xB(n, x)
(V)
-+
3aVnB(n, a ( n ) ) .
DEFINITION 1. A set X i s said to be represented by (0, 9, -) if a) (0, 9) is a spread, S, b) S*, the set of equivalence classes of S with respect to can be mapped bi-uniquely onto X . DEFINITION 2. We define a mapping (the standard mapping) x from D(0,) onto D(0),as follows:
-
-
E ( n )E 0 + xa ( n ) = i ( n ) ,
E(n)+O
-+
-
x a ( n >= x a ( n - I > * ( p , ( G ( n - I>*( m >E 0 ) ) .
292
A. S. TROELSTRA
DEFINITION 3. A spread ( 0 ,9) is called homogeneous, if
~atl/?trm (92 (m)
= 9p(m)
--f
37 ( E ( m )= ?; ( m )& 9/? = $7))
.
THEOREM 1. If ( 0 , 9 ) is homogeneous, then
k ’ a ~ D ( 03nA(9a, ) n ) + V a E D ( @ ) 3 m 3 n ’ d P ~ D ( @ ) ( Q ~= ( m9p(m)--t ) A (SB, a ) ) . +
Proof straightforward. Standard construction. (x,), is a given sequence. Let X be the set of finite sequences of elements of (x,),, and let R be a relation defined for pairs ( a , x), O E X ,XE(X,),. A sequence a=(y,, ..., y,) is called admissible if R(O,y , ) & R ( ( y , ) , y 2 ) &...&R((YI,..., Y n - I ) , Y 3 . A sequence a is called admissible if E(n) is admissible for every n. If { x : R ( a ,x)} is enumerable for every g, then a spread (0,,, 9) can be constructed which contains all admissible sequences and which is homogeneous. This is done as follows: Let (a,), be an enumeration of X , g1=O. We suppose (x: R(o,, x)} to be enumerated as ( x ( n , m)),. If to every sequence (mi,. .., m,) of length t a number y2 has been determined such that
9 ( m , , ..., In,) then we put for every m.
= 6,
9(ml,..., m,,m) =a,*(x(n,m))
3. Applications In intuitionistic mathematics all applications of Brouwer’s principle were hitherto in fact applications of the fan theorem, which is a combination of the bar theorem and Brouwer’s principle for a special case, the case of finitary spreads ( [ 2 ] , p. 59). The following examples show that the general form of Brouwer’s principle has strong consequences too. THEOREM 2 . I c N , Wi subsets of a space r.
U {Wi: i ~
l3}T - t
U {Interior Wi: ie1) 3 T
([4], Theorem 6).
ProoJ In this as well as in the other applications treated, the essential idea of the proof is always the construction of a suitable spread to which Brouwer’s principle can be applied.
293
"BROUWER'S PRINCIPLE"
r is separable, therefore we may suppose (p,,),, to be a sequence dense in the space. p is a metric for r. We put Ui,j=U(i-l, p j ) and we define a relation T on ordered pairs
<2-k),
Vn'dmV'k(lP(Pn7 P,,) - q ( n , m , k)l
T(Uk,J,U ; , j ) + + I t ( k - ' > i-'
+ Cp(j,
1, t )
+ 2-f),
and to every pair ( k , I) a pair ( i , j ) can be found such that T ( U k , , ,Ui,j). Therefore, if we put for IJ = ( U k , , l l..., , Uk&) R(a,
ui,j>
=
ui,j> 7
(ukt,lt?
we can carry out the standard construction of a spread S = ( B o ,9) such that YES-VnT(Y(n), r ( n
+ 1)).
In the sequel of this proof we suppose a, PES. If diameter a(n)<2n-', then diameter a(n 1) d 2(n + 1)-'. Hence .(a) contains exactly one point of r for every M E SIf. we define by
+
nn
-
a-P-naan)= n
nm n
then ( B o ,9, -) represents r, hence
The following property holds for S, as is readily verified: (2)
v a v p ~ r v n ( p ~ . ( n ) - , 3 ~ ( c l= ( ~p)( n ) & n p ( n ) = { p } ) ) n
We introduce a predicate A by (3)
Then (4)
V d n A(M, n ) ,
294
A. S. TROELSTRA
Applying Theorem 1, we obtain
Va3m3nVP(E(m)= $ ( m ) -+ A (p, n ) ) .
(5)
Take a p E r , construct an M according to (I), n, m according to (5) and we obtain
(6)
v p @ ( m ) = $(IN)
-+
A (AH I ) .
We apply (2) with respect to a, m:
(7)
v w ( q E 4 4 - , 3 ~ ( ~ ( m= ) c l ( m ) w x w = (4))). n
if qEa(m), and
p is chosen according to (7), we obtain
n,
P ( n ) c W,, so q~ W,. This holds for Therefore (by (6)) A @ , n), hence every qEa(m), therefore a ( m ) c W,, hence p~ct(m)cInteriorW,. THEOREM 3. Iff is a mapping from a space r into a space I-", then f is continuous. Proof ([5], 3.2.23). Let ( p , ) , be a sequence dense in r".We put Wn,i= = ( q : q M & p ( f q , p , ) < 2-"}. ( W,, Ji covers r for every n, therefore (Interior W,Ji is also a covering for every H . Take a q E r , H E N .Then q ~ l nW,,, t for a certain m, so Vr(rEInterior W,,,+p(fr,p,)<2-"), hence Vr(rE1nterior W,,,~p(fr,fq)<2-""). This proves continuity. Example. Let A be a topological space. We consider the properties (A) and (B): (A) For every r"and every mapping f from A into r"f is continuous. (B) = the conclusion of Theorem 2. (A) and (B) are not of the same strength; [Ol] u [1,2] (with the topology induced by the real line) satisfies (A) without satisfying (B). For Interior [0,1]= [0,1), Interior [1,2]=(1,2]; ([0,1], [1,2]} is a covering, but ([0,1), (1,2]} is not. DEFINITION 4. v, rifi.
w~
I/ C '
W + + V ~ Er"'3E(U ( E , p ) n I/ = 0 v U ( E ,p )
v w-
c
W ).
THEOREM 4. v,W C r. c vcu r. Proof([5],3.2.24). The implication from the left to the right is trivial; in the other direction it is proved thus. ( V", W } covers r hence by Theorem 2 (Interior v",Interior W } covers r. Therefore VpEr(pG1nterior V' vpEInterior W ) ,so for everyp there exists an E such that U ( E p, ) c V"v U ( E ,p) c W.
w=
"BROUWER'S PRINCIPLE"
295
DEFINITION 5. A mappingffrom a space r;l,into a space r"'(with metric
p ) is called sequentially continuous if for every converging sequence
with limit x ( x E f ; ' , (x,),cr;') we have
(x,),
Vk3mV'n(n 2 m - + p ( f x , , f x ) < 2 - k ) .
THEOREM 5. Iff is a mapping from r' into r",thenfis sequentially continuous. Proof. See [4],Theorem 1. THEOREM 6. Iff is a sequentially continuous mapping from I"' into r'", then f is continuous. Proof. See [4], Theorem 2. Remark 1 . By combination of Theorems 5 and 6 we obtain another proof of Theorem 3. DEFINITION 6. A pointset V c r is called located, if V p E T V s ( 3 q d ' ( q d ( e , p ) n V ) v 3 6 ( U ( 6 , p ) n V = 0)).
Classically, every pointset is located. THEOREM 7 . Let V , W c r, V located. Then
GW. I.'-cInteriorW-V (Compare [ 5 ] , 3.3.7.) Proof. Only the implication from the left to the right needs proof. If V is located, then V - is located too; for if q E U ( E p, ) n V , then also q~ U(e, p ) n V - , and if U(6, p ) n V=O, then U(2-'6, p ) n V - =O. V G W t , V - G W , for if U ( E , p ) n V=Ov U ( s , p ) c W, then U ( 2 - ' e , p ) n V - = O v v U(2-'e, p ) c W. Hence we may suppose V to be closed in our proof without losing generality. be a sequence Suppose V c Interior W, V located. Let p E r , and let (4.). of points, and (k(n)), a sequence of natural numbers such that V n (q,E
I/ n ~ ( 2 - ~ ( "p' ), v
U(2-k'"', p ) n v = 0).
We may suppose Vn(k(n)>n). If U ( 2 - k ( 1 )p,) n V = @ ,there are no difficulties. Suppose therefore q1E U ( 2 - k ( 1 )p, ) n V . We define a spread S, = (@,$) as follows <0), < I ) € @ ( t l )...)t , , , t ) E O W ( t ,,..., t , ) E O & ( t = t , v ( t = t , + 1& &(m>l+t,,=t,-, + 1)&q,+lEU(2-k(m+1),P))). $(tl,
..., t,>
=
( q c , , ..., 4 r J .
296
A. S . TROELSTRA
If aeSp, then V n ( a ( n ) ~ V )and , since V is closed, limaE V. We have VqE V 3 l ~ ( U ( 2 -q~), c W ) ,and we define for a e D ( O ) :
A ( a , k ) ~ U ( 2 - lim9a) ~, c W.
We see that
Applying (IA*) we obtain
(I)
V ~ E D ( O3kA(cc, ) k).
vaED(0)3n3mVBED(O)((01(m)=B(m)--tA(P,II))&nZ>12).
We define a special a * e D ( O ) :
a*(n)=a*(n+ I ) t t ~ ( 2 - ~ ( " + ' ) , p ) n ~ = P ) . We apply (1) and find n, m for a* such that
(2)
V ~ E D ( O ) ( C I * ( ~ ) = B ( ~ ) - ,nA) )(& Bm , >n.
We remark that (3)
Vt3P E D (0)( t
> m & qt E u (2-k(t),p ) n v
--t
01" ( m ) = = p(m)&Iim$P = q t ) .
+
If a* (m)= a* (m- l), then U ( 2 - k ( m )p, ) n V= 0 ;if a* (m)= a* (m- 1) 1, then q , ~ U ( 2 - ~ ( ~ ) , pV.) nIn the second case we can take a P E D ( O ) such that E*(m)=P(m),and lim9p=ym (an application of (3)); then A ( p , n) holds i.e. U(2-", lim9p) = U(2-", )4, c W , p ( p , 4,) < 2-k(m)+2-k(rn) - p ( p , 4,) = 6 > 0. We remark that k ( m )2 m>n, hence 2-" 3 2-k(m).Therefore U ( 2 - k ( m )9,") , c W, hence U ( 6 ,p ) c W. So we have proved for an arbitrary p : ~E(U(p E ), n V = 0 v U ( E ,p ) c W )
and this proves V C W. THEOREM 8. Every open covering of a space r contains an enumerable sub-covering. (Compare [ 5 ] , 2.2.6.) Proof. Let (O,, 9, ) be the representation of r as described in the proof of Theorem 2, and let { W,: X E X )be an open covering of r ; ( p , ) , is a sequence, dense in r. We introduce a predicate :
-
A(a, k, m ) t , 3 p E r 3 x E X ( n a ( n ) We see that
=
{ p } & p ~ U ( 2 -p,) ~ , c W,).
fl
Va3k3mA (a,k , m ) .
291
“BROUWER’S PRINCIPLE”
From (111) we can derive (using the well-known pairing functions for natural numbers) (a, P, y ~ D ( 0 , ) ) 3P3Y (Va3nA(a, P (n), Y ( H I )
V’n3aA(a, P ( n ) , y (n”
We remark that ( U(2-p(”’,p , ( , , ) ) , covers r ; further we have Vn3x(U(2-P(”),P,(,,)c W,).
Applying (V) we obtain therefore a sequence ( Wxcn,>,which covers r. Remark 2. More generally, this theorem can be proved for topological spaces which can be represented by a spread. THEOREM 9. Let V be a set of sequences of elements of (x,),, and let be an equivalence relation defined for pairs of elements of V ; the corresponding set of equivalence classes is denoted by V*. We suppose V* to be represented by (0, 9, -); (0, 9)=Sc V. Let T be a predicate such that v a E V l p E v ( ( a - P&T(P)).
-
-
Then there exists a representation (O,, 9’, ), (O,, 9‘) = S,, such that v a E s, (T(a)). Proof. Let x be the standard mapping from D ( 0 , ) onto D ( 0 ) according to Definition 2. For a, PED(O,) we introduce a predicate A We see that
A (a, PI + + ~ X N
-
<Xp(n))n
& T ((Xpcn)),)
*
VO1VA(a, P)
Hence we can apply (IVA”), and obtain a function II/ as required there. We define a finite sequence of natural numbers ~ r n l , m z , , , , , r nfor n every (ml,..., mn)EOo,such that
298
A. S . TROELSTRA
Let Y E V . Then 3 a ~ D ( 0 , )( 9 p - y j . We can find a
Y
N
~ X N
N
(X~cn,)m
T ((x,
p such that
A ( a , p) i.e.
*
This proves our theorem. A useful topological application of this theorem is the following theorem (cf [ 5 ] , 3.2.20). 10. Let ( W,), be a sequence of closed pointsets of r, and let r THEOREM be represented by ( 0 , 9, -), ( 0 , 9) = S , such that Va E SVn ( a ( n ) E
< V n > m & 3~ E r ( { P } = na (n>>>.
nL
I1
If to every sequence (W,ci,)i, W n C i , = { p >a, sequence (Wn,(i,)i can be found such that F n ( i ) = { pVi(Wm(,+l) }, C W , , i J then there exists a representation (O,, 9’, -), (0,, 9’)=S’, such that V a ~ S ’ V m ( a ( m +1) Ca(m)j. Proof. lmmediate by an application of Theorem 9.
ni
References 1. A. HEYTINC,Intuitionism, an introduction (second revised edition, Amsterdam, NorthHolland Publ. Co., 1966). 2. S. C . KLEENEand R. VESLEY,The foundations of intuitionistic mathematics (Amsterdam, North-Holland Publ. Co., 1965). 3. G. KREISEL,Reports of the seminar on Foundations of Analysis, Stanford University, Summer 1963 (Mimeographed), Section IV: Theory of free choice sequences of natural numbers. 4. A. S. TROELSTRA, Intuitionistic continuity, Nieuw Archief voor Wiskunde (3), 15 (1967) 2-6. 5. A. S. TROELSTRA, Intuitionistic general topology, Thesis, Amsterdam 1966.