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!
0 and each i s 2, (91, X6)6<,,and therefore (%',Xg),,, is a model of -qm+"+'l q"+"l x,, = 0. It follows thatxi, +$, X i , = X i 2 .Therefore h preserves That h preserves P , Q , and each C , , , Qf'l,f' . -Qrfi+'I, and Qf"Y. -Qm+l,4' * D is proved similarly. 0
-
- +
-
-
+.
1 ,
We can now give a characterization (up to isomorphism) of set algebra^.^ LEMMA6.6: 91 i s isomorphic to u set ulgebra if und only if 91 is u model of VEpq,-QI is un atom, and 91 is reachable. Pro08 One implication being obvious, assume that 91 is a model of VE pq, -- Q2 is an atom, and 91 is reachable. Let B be the set of those X E A for which there is some m < o such that X s -Qrn+'X. By 6.5, there is a set algebra 91' and a 1-1 mapping h with dom h = B and run h C A?I such that h preserves 69, ., P , Q , and each C,, -Qm+',l, and Q"'1. -Q'"+'X. D. Then also some algebra 91' of all subsets of some 'W and some mapping h satisfy these conditions. Since 91' is complete, there is a function ho with dom hQ= A such that h b ( X ) = Cm<w:'lp h(-Q"'+W- X ) for each X E A. Now consider any X , Y E A . Since '21 is reachable, X = C , , , - Q m + ' X * X and Y = C r n < , , - Q m + W Y. . If X # Y, then there is some
+,
em/.
4As the proofs of 6.1 and 6.6 show, for other languages ILI one can often characterize set algebtas similarly, using instead of Epqa set of equalities complete for I LI.
86
m
ALGEBRAS OF S E T S A N D ALGEBRAS OF THEORIES
[CH.
6
such that Q J r J-Q1rJ+lI /. . X # Q"'4.-Qrtt+lJ'.Y, hence such that h ( Q I I I J . - Q I N + l ~ . X ) # h (QtJJJ . -Q"+lJ' . y ),
and hence such that /I?
( X )=
xllt<w!>l, h(-Q"'+'4. X ) #
h(-Q"+K. Y ) =
(Y).
~r,,J<wy
Also
xnr<w!,l h(-Q""'Z.
(X.Y)) -
-
Cnt<w:q' h(-Q"+'X. Erncw!j1, h (-Q"+W.
X ) . h(-Qni+l1 * Y ) X' , Crncwy1. h(-Qm+'J'* Y )
since h preserves * and since 91' is complete, respectively. Hence, 111 ( X . Y ) = /A ( X ) . hQ( Y ) . Likewise, since h preserves and 0, hQ preserves and @.Since 3' is reachable and h preserves each QV'.-QiiJ+lJ',h4 preserves X . It follows that h' preserves -. Since is reachable and h preserves each Q V ' . -Q"+lI . D , h' preserves D. Since h preserves -,Q , and each -Qfl+'X. Q " ? ,one has
+
+
+,
!?I'
Q.,. h (-Q"'+'J'.X )
while
. h ( X ))cp
=
Q.1, (-Q"+'X
-
(-Qr"+'2'.Q h ( X ))\!I, = h (-Q"+'J'
h (-QX
*
Q X ),
. Q X ) = h (0)= Qv,,.
Hence ~ m < w ~ l , Q : ~ I , h ( - Q " ' t 1 4 . X ) = ~ . , , , s ~ h (e- Q x") +=' hQ ~.(OX).
Also, Q.1,
hs ( X ) = QYIl, xJ,n<w!yh(-Q"+W.X ) = Cm<wy,,Q!,I,h(-Qm+lJ'. X)
since, by 6.4(b), Q!lI.is completely additive. Hence hb preserves Q . That h1 preserves P and each C , is proved similarly, using complete additivity and the derivability from Epqof p(-qmAl x) = -qml * px and c,(-q"J+'l * x) = -q"'+'l * cIx, respectively. Thus, hb is a monomorphism of 91 into %', and hence an isomorphism of 2l onto a set algebra. 0
-
T o obtain a second characterization of set algebras, which like the one just given is based on the work of Howard [ 161, we turn for a while
CH.
61
A L G E B R A S OF S E T S A N D A L G E B R A S OF T H E O R I E S
87
+,
to purely algebraic considerations. Let Y l = (A, ., -, X , D , P , Q, C,,,C , , ...) be any algebra. A congruence relation of Yl is any R C *A which is reflexive, symmetric and transitive on A , and is such that, for any X , X ' , Y , Y' in A , ( X , X ' ) E R and ( Y , Y ' ) E R imply ( X + Y , X ' Y ' ) E R , and such that with respect to ., -, P , Q , Co,C,, ... analogous conditions are satisfied. Clearly, the identity relation { ( X , X ) : X E A } is a congruence relation of ?l. Also, the intersection of any set {Ra:(Y < p } of congruence relations of Y l is itself a congruence relation of %.If for each such { R a :a < p } not containing the identity relation the intersection differs from the identity relation then 91 is subdirectly irreducible. It follows that ?I is subdirectly irreducible if and only if 91 has a congruence relation which differs from the identity relation and which is included in any other such congruence relation. Let ?)I = ( A , +, ., -, X , D , P , Q , Cl,, C,,...) be any algebra and R any congruence relation of ?l. For each X E A , we let X / R = {A": ( X , X ' ) E R } . T h e quotient algebra ?1/R shall be the algebra
+
23
= ( A % ,ftt,
c,,,,
.$\,-,,/I,. D,. P,, Q.8. c,,....)
such that A , = { X / R :X E A } , such that, for each XIR and Y / R E A , X / R +sY / R = (X+:I, Y ) / R , and such that . -$:, JC,, D\l,, P,, Q,, C,,, C , > f... i satisfy analogous conditions. As is well-known, the function h whose domain is A such that h ( X ) = X / R for each X E A is a homomorphism of 91 onto ?IL/R.It shall be the natural homomorphism of 91 onto % / R . A such that Let ?I be any model of VEpq.An ideal of ?l is any J J # @, such that X E A , X s Y , and Y E J imply X E J , and such Q, P , and each Ci.Clearly A is an ideal of ?l. that J is closed under For each S C A , we let [ S ] , the ideulgeneruted b y S , be the intersection of all ideals J of ?such i that S J . (One verifies easily that [ S ] is an ideal.) For X E A we let [ X I = [ { X } ] .For each S C A , we let S - = { Y : Y . X = 0 for each X E S } . We let cgr be the function whose domain is the set of ideals of % such that for each ideal J of Yl, cgrJ={(X,Y): (X.-Y)+(Y.-X) E J } . In view of the lemma that follows we sometimes let ?l/J = %/cgrJ. Reference to 91 or to A will be taken as understood.
+,
LEMMA6.7: Assume that % is a model of VEpq.Then cgr is 1-1 and the domain of its inverse cgr-' is the set of congruence relations of ?I.
sx
A L G E B R A S OF S E T S A N D A I - G E B R A S OF T H E O R I E S
[CH.
6
Moreover,for any congruence relation R of 91, cgr-' R = { X : ( X , @) E R}. f'roofi This follows from the fact that, for each model % of VE,,, ( A , ., -,X) is a Boolean algebra, Q @= @andQ ( X + Y) = Q X + QY for any X , Y in A , and P and each C , satisfy analogous conditions. 0
+,
LEMMA6.8: Assume that 91 is a model of VEpqand J is an ideal of \!I. Then J - i s un ideal of\![ and J .J - = { @}.s Proof': Let 91 and J be as stated. Evidently, J * J - = { @ } , J -is closed and Z s Y and Y E J imply Z E J - . Now let Y E J - and under consider any X E J. Since J is an ideal, Q X E J. Hence Y Q X = @. By the conjugacy of P and Q, PY . X = 0.Hence PY E J - . Similarly J - is closed under Q and, by the self-conjugacy of C,, under Ci, i <w.0
+,
1
LEMMA 6.9: Let ?I be any model of VE,, and let X E A . (a) [ - Q ? . X I = { Y : Y S Z,,,,,, Q " ( - Q X * X ) for some m < w } = { Y : Y s XIIcff1- Q"+?V.Q"Xjbr some m < w } . (b) [ - Q ~ . X ] . [ - Q ~ . - X ] = { @ } . (c) [-Q2] = { Y : Y s -Q"l+'kfor some m < w } . Proc$ Let 91 be any model of VEpq. let X E A , and let S = {Y: Y d Z,,sf,,Q"(-Q/u. X ) for some m < w } . One easily verifies that C , Q f ' ( - Q 2 . X ) = Q " ( - Q X . X ) . Hence if Y s Z,,, Q"(-Q,I'.X), then C,Y S Z,,, Qrl(-Ql * X) . Hence S is closed under each Ci. Also, if Y ~ - Q / u . X , t h e n P Y = @ d - Q k . X a n d i f Y S Q " + ' ( - Q X . X ) , then PY d Q n ( - Q , I ' . X ) . From P ( Z + Z ' ) = PZ+PZ' it follows that S is closed under P. That S = [- QS . X I then follows easily. For each n, Q'l(-QA.) = Q?4'-Q,l+W. Hence, Q " ( - Q X - X ) =-Q"+'X. Q.X. This proves (a). From C,,,,, Q r Y .-Q"+'Z= -QJJJ+?U we conclude Q " - X imply that (c). Now Y s - Q n + ' X . Q"X and Y d -Q"+X Y s -Q"+'Y. Q " ( X . -X) and hence that Y s 0.This proves (b). 0 LEMMA6.10: Assume that 91 is a model of VE,,, that -QX# @, and that 91 is subdirectly irreducible. Then (a) -QX is an atom and (b) 91 is reachable. Proofi Assume that 91 is a model of VEPq and that -Qf # @. (a) Suppose that -QS is not an atom of a. Then, for some X, - Q X . X # @ and - Q X - -X # @.By 6.9(b), [-QJ'. X I * -XI
[-ex.
"his lemmaand its proof were pointed out to me by R. Arthur Knoebel.
CH.
61
ALGEBRAS OF S E T S A N D ALGEBRAS OF THEORIES
89
{@}. Hence, by 6.7, cgr [ - Q X . XI and cgr [-QX. -XI are congruence relations which differ from the identity relation but whose intersection is the identity relation. Hence ?l is not subdirectly irreducible. (b) Suppose that ?I is not reachable. Then there is some X E A such that X # X and such that -QJ’l+?t s X for each m < w. Then --X E [-QI]- # {@}. Applying 6.8 and 6.7 to cgr[-QI]- and cgr [-QX], one sees that ?I is not subdirectly irreducible. 0
=
LEMMA6.11: Assume that ?I is a model of VEpq.-QZ is an atom, and ?l is reachable. Then ?I is subdirectly irreducible. Pro05 Let ?I be as stated. Consider any ideal J # {@}of ?I. Then J contains some X # 9. Since ?l is reachable, X = C,,,,, (-QJ’I+’X. X ) . Hence, for some m , Q”‘(-QX) . X = QfJY * -Q”’”X . X # 0. By the conjugacy of Q and P, - Q X . P”IX # 9. Since - Q I is an atom, -QX d PJJJX. Hence - Q I E J , and thus ( 9 ) # [-Q.U] C J . By Lemma 6.7, ?l is subdirectly irreducible. 0 We now summarize 6.6, 6.10 and 6. I 1. Note that the only nonelementary notion in 6.12(iii) is one from universal algebra.
T H E O R E6.12: M Thefollowing are equivalent: (i) ?I is isomorphic to a set algebra. (ii)?I is a model of VE,,,-QIis an atom, and L‘! is reachable. (iii) ?I is a model of VE,,, -QX # 9, and ?I is subdirectly irreducible. Consider any algebra ?l, and any subset B of A = A % ) ,We . call B Iw-closed if and only if, for every X E A , if -QJJJ+ ‘X. X E B for each m < w, then X E B. We let c l , , B , the Iw-closure of B , be the intersection of the set {B’: B B’ and B’ is Iw-closed}. When X . X = X for each X E A , and hence in particular when ?I is a model of V E pq, then one can easily show that cl,, B = B { X E A : -Q’JJ+lI’ .X E B for each m < w } . Then cl,, B and B contain the same elements - Q ” ’ + ’ X . X . Evidently, cl,, B is Jw-closed, B C c l , , B, c/,, c / , ,B C cl,, B,and B,,C B,implies cl,, B,,C c/,, B,. The proof of the next lemma is straightforward.
+
LEMMA6.13: Assume that \21 is a model of V E p qand that J is an ideal of ?t. (a) cl,, J is an ideal of 91. (b) cl,, [@I = [-QII-and hence [-QX]cl,, J .
90
A L O t B R A S OF S E l S A N D ALGEBRAS OF T H E O R I E S
[CH.
6
Consider any model Y l of VE,,, any subset B of A = A?,.and any m < w . We let rnk,,, B = { X E B : X Q f t f I-.Q f l t + If lXI } E.rnk,,,A or if B r n k J , then X or B respectively shall be c$runk m (in ?I). Thus, rnk,,, B is the set of those X E B which are of rank m in YL. Consider any model \!I of VE,,, any subset B of A = A!!,.and any m < w . If B # A , then B shall be proper. If rnk,,, B f mk,,, A , then B shall be m-proper. If B is closed under and if X E B whenever X s Y and Y E B . then B shall be a Boolean ideal (of Yi). Evidently, if B is an ideal. then B is a Boolean ideal. Also, if B is a Boolean ideal. then rnk,,, B is a Boolean ideal. If B is a proper ideal and if there is no proper ideal B’ such that B B’ and B # B ’ , then B shall be maximal umong the proper ideals. With respect to other sets, the notion of maximality will be used similarly. To illustrate. let ?)I be a set algebra. Then every ideal different from (8) includes [ - Q J ] . I t follows that every B which is maximal among the proper ideals includes [-QJ’]. I n contrast, the only B maximal among the proper Iw-closed ideals is {8}. Parts (a) and (b) of the next theorem, together with 6.13(a), give a 1 - I correspondence between the Iw-closed ideals and the Boolean ideals of rank 0. According to parts (c) and (d), those that are maximal among the proper ideals of the first kind thus correspond to those that are maximal among the 0-proper ideals of the second kind.
+
c
THEOREM 6.14: Assume that ’!I is a model of VE,,. (a) IfJ is an lo-closed ideal, then c l l , [ m k oJl = J . (b) I f B is u Booleun ideul of rank 0, then m k , , (cl,,,,[ B ] )= B . (c) I f J is muximril umong the lo-closed proper ideals. then rnk,,J i s maximal umong the 0-proper Booleun ideals of rank 0 . (d) If B is mmximul among the 0-proper Booleun ideah of rank 0 , then cl,,,,[ B ]is maximtil among the Iw-closedproper ideals. Proof: (a) Assume that J is an Iw-closed ideal. Since mk,,J C J , it follows that [rnk,,J] J and hence that cl,, [rnk,)J ] C J . Now n . Since J is an ideal, Q?X consider any X E J . n < w , .and m . - Q”‘+’k . X E J and hence P”’(Q”’X. - Q”’+’k . X ) E J . rnk,,A QI,lPIII(Q))P.- Q , , l + l J ’ . X ) Q”<J’.-Q”+IJ’. C,,... = mk,, J . ‘ Then C,,,-,X E [ m k oJ ] and hence Q”’X * - Q n r + l I . X E [rnk,,J l . Since this holds for any m s n , therefore -Qnt’2 * X = ( - Q l X . Q ‘ W . X ) + ... + ( - Q ” + I X . Q’!/‘. X ) E [rnk,)J ] . Since this holds for any n < w, therefore X E cl,,,,[ m k oJ ] . Hence J C cl,, [rnk,,J l .
c
2
CH.
61
91
ALGEBRAS OF SETS A N D ALGEBRAS OF THEORIES
(b) Assume that B is a Boolean ideal of rank 0. Since B is of rank 0, an argument similar to the proof of 6.9(a) shows that [ B ] = {Y: for some Xo, ..., X,-l in B and some m < w, Y c Ck<mQkXxo+... C k < m Q k X n _ , } . Since B is a Boolean ideal, it follows that rnk,, [ B ] = B . Evidently, rnk, (el,,,,[ B l ) = rnk, [ B l . (c) By part (b) and 6.13(a). (4BYpart (a).0
+
T he next theorem, in conjunction with 6.6 and 6.14, yields up to isomorphism, for any model % of VE pq, a 1- 1 correspondence between the homomorphic images that are set algebras and those B that are maximal among the 0-proper Boolean ideals of rank 0. Part (a) strengthens a result by Howard to the effect that whenever 2I is a model of VEpqthen %/[-QX]- is reachable. In conjunction with 6.14, it yields up to isomorphism, for any model Y i of VEw, a 1-1 correspondence between the homomorphic images that are reachable and the Boolean ideals of rank 0.
THEOREM 6.15: Assume that % is a model of VEpqand that J is an ideal. (a) % / J is reachable ifand only ifJ is lo-closed. (b) (-QX)/J is an atom of % / J if and only if rnk, J is maximal among the 0-proper Boolean ideals of rank 0. Proof. For any model I8 of VEpq,!-I? is reachable if and only if [-Qx]& = {&}. This is easily shown, using, e.g., the proof of 6.1O(b). Now let !-I? = % / J . First assume that J is Iw-closed. Consider any Y E I8 such that Y # 0%.Then Y = X / J for some X E A such that X 4 J . Since J is Iw-closed, there is some m < w such that -Q"&+lX.X 4 J and hence ( - Q m " 1 - X ) # 0%. Now ( - Q " + ? U . X ) / J is in [ (-Ql') /JIB. Hence Y 4 [ ( - Q J ) /./la. Therefore [ ( - Q X ) ={ and I8 = %/ J is reachable. Now assume that J is not lo-closed. Then there is some X E A such that X 4 J but -Qm+'Y.X E J for each m < w. Let Y = X / J . Then Y # OB but ( - Q m + l X . Y)@= ( - Q m + ? Y . X ) / J = 0%. Hence 2' 3 = % / J is not reachable. This proves (a). T h e proof of (b) is routine. 0
/Jls alt}
LEMMA6.16: Assume that % is a model of VEpgand that ?I is reachable. Let J = { J : J is maximal among the Iw-closed proper ideals} and let I I J = { X E A : X E Jfor each J E J } . Then rU = {@}. Proof If A = { O } , then J = @ and H J = { O } . If -QX is an atom, then
92
4 1 C r E B R 4 S OF SETS A N D A L G E B R A S OF T H E O R I E S
[CH.
6
= { {Q}} and i l J = { @ } . Now assume that A # { @ }and that -QA’ is not an atom. Consider any X E A such that X # 0.Since Y l is reachable, there is some m < w such that Q’V. -Q”l+’,I’. X # @.Then Prll( QV”-Qrr1+’A’.X ) = - Q X . P”X # Q. Then -QX . -P”X # -QX. Since - Q I is not an atom. therefore -QX . -P”’X belongs to some B which is maximal among the 0-proper Boolean ideals of rank 0. Since B is 0-proper, therefore - Q X . P”’X @ B . Hence Q V -Qrn+W. . X @ [ B ] ,since otherwise -QA“ P”‘X would be in rnk,, [ B ] and hence, by the proof of 6.14(b), in B . Then Q’5i” -Q”“ ‘2‘.X , and therefore X , is not in c l l w [BI. Now cll,B E J . by 6.13(a) and by 6.14. Hence X 6! IIJ.HenceagainIIJ={@}.O
J
Consider any y and any set {\.)la: /3 < y } of algebras !)Ia. The direct product of { ? I f i : /3 < y } shall be the algebra Y( such that (i) A is the set of functions f whose domain is y and whose value fa is in A!,4,for each p < y . and (ii) the operation satisfies for each f , g E A and /3 < y the condition ( f+.,,q)fi =fa +!jIBsaand the operations t ! , , .D!,,. P?,, Q!,l. C,,,,.C,!i,,... satisfy analogous conditions. If y = 0, then A = { @ } . A subdirect product of {?la: p < y } shall be a subalgebra % of the direct product of {?la: /3 < y } such that for each /3 < y the set { fp: f E A*\} is A:lln. An algebra is representable if and only if it is isomorphic to a subdirect product of some set of set algebras. The next lemma. also from Howard, is an immediate consequence of the definitions involved.
+.,
LEMMA6.17: (a) Each direct product of reachable models of VEpq is reachable. (b)Each subriigebra of a reachable model of VE,, is reachable. (c) Each subdirect product of reachable models of VE,, is reachable.
We now characterize the representable algebras. The equivalence of (i) and (ii) is analogous to one in Howard[ 161. THEOREM 6.18: The f o l l o ~ i n gare equivalent. (i) 91 is representable. (ii) ?I is a model of VE,, and Y l is reachable. (iii) \!I is a model of VE,, and YJ is isomorphic to a subdirect product of { \.)1/clI,[B]: B is maximal among the 0-proper Boolean ideals of rank O } .
CH.
61
A L G E B R A S OF SETS A N D A1,GEBRAS OF THEORIES
93
Proofi By 6.13(a), 6.14, and 6.15, if $1 is a model of WEPqand if B is maximal among the 0-proper Boolean ideals of rank 0, then Y I / d W [B] is reachable and -QZ/cll,[B] is an atom of Yl/c/,,[B]. By 6.6, (iii) implies (i). By 6.17(c), (i) implies (ii). Now assume (ii). Let B = (B:B is maximal among the 0-proper Boolean ideals of rank 0}, and let S = {Yl/cll, [BI:B E B } . If A = {@}, then B = 0, hence S = @, and ?I is the algebra which is a subdirect product of S . If -QZ is an atom of ?I, then B = ( (@}}.hence S = (?I/ { O } } , and ?I is isomorphic to the subdirect product ?(/(@} of S . Now assume that A # { @ }and that -QXis not an atom. Let h be the function whose domain is A such that, for each X E A , h ( X ) is that function f with domain B such that fil = X / c / , , [BI for each B E B . Now the natural mapping from ?)I onto Y ~ / C / ~ is , Ba homomorphism for each B E B . Hence h is a homomorphism of $1 onto a subdirect product of S. By 6.16, h is 1-1. (Cf. Theorem 9, p. 92, of Birkhoff [3].) Hence (ii) implies (iii). In the preceding portions of ch. 6, we largely followed Howard [ 161, except for introducing Iw-closed ideals and relating them to reachability. In the remaining portions, we shall take up topics that were not investigated in 1161. Consider any algebra 91 and any n < w. We let Q(,,X = Q X when n = 0 and Q(,J = C , l ( D ( t t - l .) ,Q(,-,J) l otherwise. We let P,,J = P X when n = 0 and P,,,X = P ( , - l ) ( D ( , , - l )* nC , X ) otherwise. When X,, ...,XnPlare of rank 1 in ?l, then the Cartesian product of X o , ..., X n P l (in 91) shall be QoQ(l)n-lXo. Q l Q ( l ) n - 2 X... . Qn-lQ,I,"X,-l.If Y is a Cartesian product of rank n in ?I and if i < n, then P(l,iPn-i-lYshall be the i-th component of Y (in 91). A function (in 2l) shall be any X E A such that Q*X QX . Q(,,X s D. If either n = 0 and Y = -QZ # 0 or else n # 0 and Y is the Cartesian product of functions X,, ...,Xn-l of rank 1 in ?l each of which differs from 0, then Y shall be an n-singleton (in ?1). A singleton (in 3 ) shall be any Y which is an n-singleton for some n < w. Note that if Y is an n-singleton isla subalgebra of 93 then Y is an n-singleton in 23. We let ?I in 2l and ? be n-singletonic if and only if, whenever 0 # X s Q n X . - Q n i l X , then there is some n-singleton Y in 2l such that Y s X . We let ?be I singletonic if and only if, whenever 0 # X E A , then there is some singleton Y in '.21 such that Y s X . These definitions can be motivated by considering a set algebra ?I
94
A L G E B R A S OF SETS A N D A L G E B R A S OF T H E O R I E S
[CH.
6
with base U . Then Q ( , , ) X ={ f - ( u ) - g : f E " U , u E U , f-g E X} and P,,,,X = {f-g: f E "U and f-(u)-g E X for some M E U } . If = { ( A , , ..., fL1) XI,,..., X,,-, are of rank 1 in 91, then Q'Q(l)n--I-lX, E " U :J, E X,}, the Cartesian product of XI,,..., X,,_, in YI, is their usual set-theoretic Cartesian product {(A,, ...,filPl): fi E X , for i < n } , and its i-th component in ?I is X I . Now consider any X E A such that for any g E there is at most one LI E U such that ( u ) ^ g E X. Consider any ( u , w ) - g E Q2X. Then from ( u , w)-g E QX and ( u , n')-g E Q , , , X it follows that ( w ) - g E X and (u)-g E X , hence that u = N-,and therefore that ( u , \t')-g E D. Thus X is a function in Yl. Conversely, as one sees easily, if X is a function in ?I, then X E A and for any g E '"U there is at most one N E U such that (u)-g E X. It follows that X is a 1-singleton in ?1 if and only if X E A and X = { ( 1 1 ) ) for some u E U . More generally, X is an n-singleton in 91 if and only if X E A and X = {f} for some f E " U . It follows that each singleton in ?I is an atom in ?l. Also, ?I is singletonic if and only if each atom in YI is a singleton in ?l and ?I is atomic (i.e., whenever Q # X E A , then there is some atom Y in Y1 such that Y s X).
LEMMA6.19: Assume thut Yl is a model of WEppand that -@'is un atom. (a) Any singleton is un atom. (b) if Y i3 the Cartrsiun product of elements X,,, ..., X,,-, of rank 1 in 91 and i f i < n , then the i-th component of Y is X , . (c) If ?I is I-singletonic, then 3 is n-singletonic for each n < w. Proofi (a) and (b). By the preceding discussion and by 6.5. (c) Since the hypothesis of 6.5 is satisfied, there is an h and an 3' satisfying its conclusion. Let Q = Q., , P = P , , .... Given any n 2 1, assume as inductive hypothesis that 9" is n-singletonic. Consider any X # Q of rank n+ I in ?Ir. Then PX # @ and PX is of rank n in 3 ' . By the inductive hypothesis there is some singleton Y of rank n in 3' such that Y d PX. Then Y = {f}for somef E " U , where U is the base of ?I'. Clearly QY - X = { ( u ) - f i u E U } * X # 9 and hence P,,,"-'(QY. X) # 9. Since 3 and hence 3' is 1-singletonic, there is some singleton { ( u ) } of rank 1 in 91' such that { ( M ) } s P(l)n-'(QY* X ) . Now for each i < n , the i-th component {(fi)} of {(fo, ...,fn-l>} is a I-singleton in 91'. Hence { ( u , & ...,fn)} is an ( n + 1)-singleton in ?If. Also { ( M ,fo, ...,fn)} s Q Y - X s X . Therefore 8' is ( n + 1)singletonic. Since 91' is n-singletonic for n s 1, it follows by induction
CH.
61
ALGEBRAS OF SETS A N D ALGEBRAS OF THEORIES
95
that %' is n-singletonic for each n < W. Since '$1' and h satisfy the conclusion of 6.5,'u is n-singletonic for each n < w . 0 If 'u is a set algebra, U is its base, and {f} E A for eachf E I"U, then 'u shall be singletonic in a set-theoretic sense. THEOREM 6.20: Thefollowing are equivalent. (i) 'u is isomorphic to a set algebra which is singletonic in a settheoretic sense. (ii) 'u is a model ofVEPq,-QX # 9, and 91 is singletonic. (iii) 'u is a model of VEpq.?l is reachable, -QX is an atom, and 91 is 1-singletonic. Proof: Clearly, (i) implies (ii). Now assume (ii). If X is of rank n and Y S X then Y is of rank n. Hence 91 is I-singletonic. Likewise, 'u is 0-singletonic. Since -QX is the only singleton of rank 0, therefore -QX is an atom. Furthermore, since ?1 is singletonic, therefore [-QXl-= {@}and hence ?l/[-QI]- is isomorphic to ?I. By 6.13(b) and 6.15(a), % is reachable. Hence (ii) implies (iii). Henceforth assume (iii). Let g be the function whose domain is the set of singletons in 91 such that g(-QA') = @ and such that, if n # 0, Y is an n-singleton, and Y i is the i-th component of Y in ?l,'i < n , then g ( Y ) = ( Y o ,..., Y , - l ) . Let h be the function with domainA which, for each X E A , yields the value h ( X ) = { g ( Y ) : Y is a singleton and Y c X}. Let U be the set of 1-singletons in 9,so that, by 6.19(b), each g ( Y ) is in I"U and hence each h ( X ) is a subset of I"U. Finally let 23 be the subalgebra of the algebra of all subsets of '"U which is generated by ran h. By 6.19(b), g is 1-1 and rang = I"U. By 6.19(a), each singleton in '21 is an atom in 3.By 6.19(c) and the reachability of '21, each atom in 91 is a singleton in 'u and 91 is atomic. I; now follows easily that h is 1- 1 and preserves +v,,.\!L,-\!I, lrl. Now consider any X E A , any n 3 1, and any Y 1 ,..., Y, in U . Then the following conditions are equivalent by the definition of Psi*, the definition of h, the proof of 6.19(c), and the definition of h respectively: ( Y , , ..., Y,) E P s ( h ( X ) ) ;there is some Yo E U such that ( Y o ,Y , , ...,Y , ) E h ( X ) ; there is some Yo E U such that if Y is the Cartesian product in ?l of Yo, Y,, ..., Y,,, then Y s X ; if 2 is the Cartesian product in 'u of Y 1 ,..., Y,, then Z s P,,X; ( Y , , ..., Y,,) E h ( P , X ) . One can likewise show that 9 E Ps ( h ( X ) ) if and only if @ E h(PGY). Thus h preserves P,!,. Similarly, h preserves Q9,,
96
ALGEBRAS OF SETS A N D ALGEBRAS OF THEORIES
[CH.
6
C,\V.and D\I,.It follows that A, = run h and that h is an isomorphism of \'I onto 58. Finally, consider any f E '"U. There is some singleton Y in $ such !I thatf= g ( Y ) and hence { f } = h ( Y ) E As. Hence B is singletonic in a set-theoretic sense. Hence (iii) implies (i). 0
The set of algebras characterized in Theorem 6.12, 6.18, o r 6.20 respectively cannot be characterized by a set of first-order sentences. This follows from the compactness theorem for such sentences, and was pointed out to me by Ralph McKenzie. As after 3.16, let E be the set {q"'l x = x: 0 s m < w } . Then for each finite F C E there is some (?I, X 8 ) 8 < , such that \!I is a set algebra which is singletonic in a set-theoretic sense and such that (?I, X 8 ) , < , is a model of F { 'Ix = O}. Yet there is no ( a [ , X6)6i, such that 91 is representable and such x=O}. that ('!(,X6)6iaisamodelofE+{ i We now return to sets of equalities, always letting E, E', ... be sets of this kind. We begin with a completeness result for VEPqr6.21(a) below, which supplements that of ch. 5. In 6.21(b) we obtain as a qli = l} VE,,. corollary of 6.21(a) a completeness result for { Both may also be compared with 6.2 or 6.1.
+
+
THEOREM 6.21: (a) Let T = T' be any bounded equality. Then T = 7' ifund only ifVEpq E T = 7'. (b) Let 0 be formed f r o m negations of equalities by means of A and V. Then 0 if und only i f { i ql = l} VE,, 0. Proofi (a) One implication being obvious, let T = 7'be any bounded equality and assume that (?(, X 8 ) 8 < , is a model of VE,, E + { 'IT = T'}. For convenience, also assume that. in ( ? ( , X 8 ) 8 < v T, denotes XI, and T' denotes XI. Let h be the natural homomorphism of Y I onto Y(/[-Ql'-. Then, in ( ? ( / [ - Q l ] - , hX,),,,, 7 denotes AX,, and T' denotes h X , . Now from hX,, = h X , it would follow that (XI).-XI ) + (XI . -XI,) E [-Q4 and hence that - Q m + ' X . X0 = -Qm+'X . X , for each m < w. This is impossible, since (PI, X8)*<, is a model of { i T = T'} and since T = T' is a bounded equality. Hence hX, f h X , . It follows that ('?l/[-QI]-, hX,),,, is a model of VEpq E + { 'IT = 7 ' ) . Moreover, by 6.13(b), 6.15(a), and 6.18, Y I / [ - - Q I l ~ is representable. Thus there is an isomorphism g of ?I/[-QJ]- onto a subdirect product 58 of some {?Iu: p < S } such that each 'Au is a set algebra. Now for any p and u, (!V/[-Ql']-, hX,),,, is a model of p = u if E
+
+
+
+
CH.
61
97
ALGEBRAS OF S E T S A N D A L G E B R A S OF THEORIES
and only if, for each p < 5, (?I@, ( g ( h X 8 ) ) o ) 8
---
+
-TI.,)
A theory, we recall, is a nonempty set E which is closed under b, i.e., which contains each u = T such that E k u = 7 . Evidently, the set of those u = T which are (w-valid is a theory, and is included in every other theory. It shall be the null theory. By the completeness of Epq.the null theory can also be characterized syntactically as the set of those u = T such that VE,, l- u = T. There is also a theory which includes all others, namely the set of all u = T. A theory shall be proper if and only if it does not contain every u = T. Thus, a theory is proper if and only if it has at least one Iw-model. A theory E shall be maximal among the proper theories if and only if E is a proper theory and there is no proper theory E’ such that E C E‘ and E z E’. Part (a) of the next theorem states that a theory is uniquely determined by the equalities -ql p = 0 it contains. Hence it is also uniquely determined by the equalities -ql * p = -ql it contains. Parts (a) and (c) follow from Theorem 3.15, and part (b) is obvious.
-
THEOREM 6.22: Assume that E and E‘ are theories. (a) E = E’ if and only if E and E’ contain the same equalities -ql * p = 0. (b) E is proper ifand only if-ql = 0 is not in E. (c) E is maximal among the proper theories i f and only if E i s proper and, for each p , either -ql * p = 0 is in E or -ql p = -ql is in E.
-
T h e next lemma follows from the compactness of I L,, I (Theorem 3.16) with the aid of the axiom of choice (in the form of principle (AC3) of p. 42 of [3]).
, ~
98
ALCiEBRAS OF S E T S A N D A L G E B R A S O F 'THEORIES
[CH.
6
LEMMA6.23: For every proper theory E there i s some E' such E' and such that E' is maximal among the proper theories. that E The next theorem relates a theory to those of its extensions which are maximal among the proper theories. It follows easily from 6.23.
THEOREM 6.24: E i s ( I theory if and only if E is the intersection of E' und E' i s maximal among the proper theories}.
{ E':E
We now define two syntactical closure conditions on a set E. For any E', we let E be closed under VE' if and only if E contains each u = 7 such that E + VE' u = 7 . We let E be closed under the Iw-rule if and only if E contains each u = 7 such that -qm+'l u = -qmf' 7 is in E for every m < w. The next theorem characterizes theories syntactically.
t-
-
THEOREM 6.25: E is a theory i f and only if E is nonempty and closed under VE, and under the lo-rule. Proof: Assume that E is closed under VE, t- and the lo-rule. Suppose that E u = 7 . Consider any m < o.Then E k -qm+'l * u = -q"+'l . 7 . By 6.21(a), E + VE, -qm+'l * u = -qm+'l 7 . Since E is closed under VE, F, -qm+'l * u = - q m + ' l - 7 is in E. Since this holds for each m < o and since E is closed under the Iw-rule, u = 7 is in E. T h e converse follows from the fact that each equality in E, is Iw-valid. 0
+
We now return to algebras. First, we introduce a particular algebra = A , +shall be the set of terms of L,. Its element d shall be the term 1, and its element D the term d. The value of its function for any given argument ( 7 , T'), shall be the term (T+T'). Its functions *, -, P , Q , Co, C1, ... shall be defined analogously. 7 ) : u = 7 E E} is a congruence relation For any E such that {(a, on VIt, we let % t / E = %t/{(u,7): u = 7 E E} and T/E = {a: u =7 E E}. T h e next two lemmas from universal algebra are well known and easily proved.
VIt, the algebra of terms. Its set A
+,
LEMMA6.26: Assume that E is nonempty and closed under VE' (a) E is a congruence relation of VIt. (b) % t / Ei s a model ofVE'. (c) u = 7 E E ifand only ifu = 7 is true in (VIt/E, xg/E)*<,,.
k.
CH.
61
ALGEBRAS OF SETS A N D ALGEBRAS OF T H E O R I E S
99
LEMMA6.27: Let (91,X6)6<,, be any algebra with designuted elements, and let E be the set of equalities true in (91, X6)6
THEOREM 6.28: (a) Assume that E is u theory. Then ?1T/E is a model of VEpqand 3 t / E is reachable. (b) Assume that \u is u model of VEw and YI is reachable. Let E be the set of equalities true in (91, Xs)6<,,, where { X 6 : 6 < q } generates 91. Then E is a theory and ?I is isomorphic to YItlE. Proof: (a) Since E is closed under VE,,, and by 6.26(b), Vlt/E is a model of VEm. That 9lt/E is reachable follows from the closedness of E under the lo-rule by a proof similar to the first part of the proof of 6.15(a), except that in place of X E J one uses T = 0 E E. (b) By 6.27(b), \u is isomorphic to \ut/E. Since Y I is a model of VEw, E is closed under VE,,. Since 91 is reachable, E is closed under the Iw-rule. By 6.25, E is a theory. 0 The next theorem and Theorem 6.12 supplement each other.
THEOREM 6.29: Thefollowing are equivalent. (i) For some E which is maximal among the proper theories, 91 is isomorphic to %t/E. (ii) 3 is isomorphic to a set algebra. Proof: By 6.28(a), 6.22(c), and 6.6, (i) implies (ii). By 6.28(b) and 6.22(c), (ii) implies (i). 0 Some theorems of ch. 6 make it plausible that for most purposes the basic model-theoretic relation for ILp, I can be replaced by, or analyzed into, a relative product of four relations, the first of which is syntactical while the others are algebraic. More precisely, it is plausible that for most purposes one may, in place of the relation which holds between a set E’ of equalities of Lm and an Iw-structure ( U , X6)6
I00
A l ( 1 1 B R A S OF S t T S A N D ALGEBRAS OF I H E O R I E S
[CH.
6
E' which is closed under VEpqF and the Iw-rule; (ii) between any theory E and (31t/E, x ~ / E ) ~ (iii)< between ~; any (Y(,X6)8,, such that "1 is generated by { X 6 : 6 < q}. 91 is a model of VIEPq.and ?I is reachable and those homomorphic images (%, Y8)8
CHAPTER 7
SECOND ALGEBRAIZATION
In our first method of algebraization we used the mapping U V P . which assigns to each F of a relational type the Iw-operation U U P F = & {SF: s < w } . In our second method of algebraization, which will now be presented, we shall use the mapping 3 of ch. 3, which assigns to each F of a relational type the w-operation dF. This mapping also commutes with substitutions. From theoperations icpiin /L,i,dleadstothesetTj" = {Gjcpj: icpi E [L,:}. which in turn gives rise to clG* :L,:, the closure of '*w 'j L, i under substitutions. We shall give two sets of generators for cl d*'i L, i. T h e first of these Y,D , Ci, Q, P : 0 d i < w } of w-operations, will be the set {+, *,-, where each operation in the set is defined as the corresponding Iwoperation was defined in ch. 2 except that in place o f t = '"U one now uses Y = '"U.The second set will be described presently. The correspondence between the function symbols of L,, and the operations in the first generating set induces a mapping of the set of terms of L, onto the set clD" / L, i. We let \Lp4\ be L,, together with this induced mapping and \ T\ the w-operation into which 7 is thus mapped. For the effective mapping tm of the formulas of L, into terms of L,, which was defined in ch. 2 we shall show that\rmcp\= &:pi. Hence, if icpi = i+[, then \tmcp\=\tm+\. T h e converse does not always hold since 3 is not 1- 1, nor even practically 1- 1. However, the weaker assertion holds that if F and G .are of the same relational type then GF = 3 C implies F = C . Thus, if cp and JI are of the same relational type, then\rmcp\=\rm+\if and only if icpi = i+i. Thus the mapping tm is an interpretation of i L,i in\ LPq\which is not fully faithful, but faithful enough to reduce problems of validity for i L,: to problems of validity for \ Lw\. For the second set of generators for c/G*i L, we shall define a mapping with similar properties. I
I
,
,
101
102
S t C O N D ALGEBRAIZATION
[CH.
7
We shall also characterize cI5;"i L a / more directly as Gr: red* ; L a ; , the set of w-successors of Iw-operations which are reducible to some icp i. Compactness and definability will be discussed briefly. We conclude ch. 7 by giving two sets of generators for IL,I which are closely related to the second set of generators for \ Lpq\. For any set I, a trunsformation (on I) shall be any function a such that dom a = I and ran a G I . Composition, or product formation, involving transformations will henceforth be often denoted by juxtaposition, although at times the product ( a ( p ( i ) ) :i E I ) = { ( a ( p ( i ) )i): , i E I } of the transformations a and p will also be crop. Thus, if f = (J;,,fr ,...) is in "U and a = ( a ( O ) , a ( ] ),...) - ( a o ,a I, ...) and p = ( p (0) ,p( 1 ) , ...) are transformations on w, thenfashall be(f,,,,,, f ( ~ ,andapshall ~ . . - )b e ( a ( P ( O ) ) , a ( P ( l ) ) , ...) = (am).a B ( 1 ) .
...>.
We let a be an ciirnost constunt s h i f , or a E Acs, if and only if a is a transformation on w and there is some k in w such that a ( k + n ) = a ( & ) n for every n in w . Let a be any transformation on w . We now introduce two l-ary w-operations. Of these, (Sa)has been investigated by Halmos [ 131, while ( T a ) is induced by the converse of the relation { ( f , f a ):f E X} which induces (Sa).H e r e 1 = " U and X C R:
+
( S a ) X = { f E &fa E X } . (Ta)X={ f a : f X ~ } = { g : g = f a f o r s o m e f E X}. The second set which will be shown to generate cl'Tj*iL,i is the , 9 = Acs. set {+, ., -,$, (Sa),( T a ) :a E Y } where We now proceed to give details. As in ch. 3, we let Z F = Ti tre F whenever n s w and F is of a relational type. It follows that for any F of type (rOis,,, one can characterize "wF as that rn-ary o-operation which for any argument ( X i )Isism satisfies: (13) For any h E " U , 'W
*
(('TjF)(Xi)lsis,,l)wh = F("U .X;h),~i~,,t.
Now let F and G be of the same type Consider any argu. any h E "U and, for 1 s i s rn, let X i = Yi h ment ( Y i ) , s i s m Take = { g - h : g E Y , } . Then YJ . X i - h = Y i , 1 d i s rn. Hence, for any g E ' " U , g-h E ( Z j F ) ( X i ) l s i s m if and only if g E F ( Y J l S i s m ; similarly for C. Thus we have shown: I
CH.
71
103
SECOND ALCEBRAIZATION
LEMMA 7.1: If F and G are of the same relutional type and if F = G.
TjF = "OG,then
T h e condition that F and G are of the same relational type cannot be omitted from 7.1. For example, if F if any of the operations C.,1 ,+I+!-' then & F is the w-operation Ci. Also, for each r < w, if F is t r , . t r , or r , then ZF is the w-operation ., or - respectively. We now let 12 be the n-ary w-operation satisfying for each argument (Xj)lcjsn the condition I>(Xj)lsjsn = X k and, for any S C " U , we let K.;!' be the n-ary w-operation satisfying for each argument (Xj)jsn the condition K,k!l(Xj)lsjsn = S . Note that if R G ' U is taken as a 0-ary operation of type ( r ) , then GR = {g-h: g E R and h E " U } . For w-operations and sets of these we define cl and related notions by making the obvious changes in the definitions given in ch. 1. T h e proof of part (a) of the following analogue of 2.2 and of 3.2 is similar to the proofs for these. The other parts are obvious.
+
+,
I
LEMMA7.2: Let F be of type (ri)ism,for 1 < i < m let G i be of " U , ..., Y,, G " U . Then: type (Ti, s,, ...,s,) = (ri)-f, and let Y , (a) ( " w ( F ( G i ( X j ) , s , , , ) , s i s , n : X jC "'Ufor 1 <.j d n))(Yj),sjs,e = (&F) ( G G i ) ( Y j )1s j s n ) I s i s m (b) For any s,, und R E "'U, sjKY( = dK::,., = K:it. (c) F o r uny k , 0 < k 6 n, GI:. = G I ; = I;.".
c
T h e condition that F , G I , ..., G,,, are of suitable relational type cannot be omitted from 7.2. For example, let F be tre-rr, and let G = G, be tre-rr+t. Then Z F and "OG are the w-operation -, so that ( G F ) { ( G G ) ( Y ) )= Yforeach Y C " U . O n t h e o t h e r h a n d . F ( G ( X ) ) - F(-,r+i("+'U . X ) ) = - t r ( " U . ("'U .-A')) = - t r @ = "U for '"U))(Y) = "U for each each X C '"U, so that ( G ( F ( G ( X ) ) : X Y "U. For w-operations we now define w-quusiterm, the m-ary and v-ary w-operation \ 6 \ denoted by an w-quasiterm 6 ,etc. as these notions were defined in ch. 2 for lo-operations and for operations of relational similarity types. Then a proof similar to that of 2.4, except that no analogue of 2.l(c) is needed and that 6 may be a quasivariable, yields the following theorem.
c
THEOREM 7.3: Let 6 be a quasiterm of a relational type and let 6'
104
[CH.
SECOND ALCEBRAIZATION
7
be the w-qircisiterm M?hichresirlts from 6 when euch occurrence of any G cfu relationul type is repluced byZG. Then\b'\ = Gj19 i.
Unless noted otherwise. we now let +, -,-,A', D , C j ,Q , P , D j j , and Si be those w-operations which are defined as the corresponding lo-operations were defined in ch. 2, except that k = "U is now used instead o f Y = '"U.
THEOREM 7.4: The set {+, .,-,4', D , Cj,P , Q : 0 d i < w } of woperations grnerutes cIG*: L 3i. Proo$ We already observed that .,-, C j are GF where for some r < W , F is + i r , . i r , - f r , or C,,iZ+l+,, respectively. One also observes that D is GD,),P is&P'tl, and Q is G Q [ o . Also,Y= - D + D. Hence, by 1.3, cl {+, .,--,A', D , C ; ,Q , P : i < W } is included in cl G*' La:. The other inclusion follows from these observations, from 7 . 3 , a n d f r o m 6 D j = Q'D, (GC,,,, ) X = X f o r i a r, ( G Q ' , r ) X = S ; - l . . . S: S,l)Q X . and ( G P ' , ) X = P S',' S,: ... S;:-I C,.X for r > 0 . 0 ~
+,
Next, we turn to the set Acs, which will be used for defining the second generating set. For any index set I and any i and j in I , we let (ilj), the rc~plticrmentof i by j, be that transformation on I which satisfies ( i / j ) n = n i f n # iand ( i / j ) n = j i f n = i.Wealsolet ( i , j ) i = j , ( i , j ) j = i , and ( i , j )n = n if i # n # j . The I concerned will often be taken as understood. We let (+ I ) be that transformation on w which satisfies ( + l ) n = n+ 1 for each n in o.We let (-1) be that transformation on w which satisfies (- 1) n = n - 1 if n > 0 and 1) n = 0 if n = 0. We let (0; 1 ) = I ) , and for any r in o we let ( r + 1 ; 1 ) betheproduct ( r ; - l ) ~ ( r + l / r + 2 ) . T h e n ( r ; - l ) n = n i f n s rand 1 ) = ~ n - 1 if I Z > r. Finally for any I , any transformation a on (r; 1. and any t in w we let a" = a and at' I = a' a. In the next lemma. cl is closure under composition. 0
LEMMA 7.5: Acs = ci { ( + I ) , (L I ) , (i/j) : i < w , j < w } . Pro($ Clearly, ( + l ) , ( L 1 ) . and all (ilj), where i < w and j < w, are in Acs. Now consider any a in Acs. There is some k < w such that a k t,, = ak++nfor every n < w and such that, in addition, if k' < k, then ak' < ak. Let t 2 ak and let p = (t/ao) ( ( t l ) / a , )0 ( ( t+k . . .) ) o (+ 1 1'. Then P = (Po,PI, . . . ,Pk-,)^(Pk, = ( a o ,a I , .. . , a ~ - ~ ) - ( k + t k , + t + 1 , . . .). Hence a is a product of transformations (+ I), 1) and (ilj),since a = ( a k - 1; l)k+r-akoB. 0 0
+
A
a e . 0
CH.
71
SECOND ALGEBRAIZATION
I05
THEOREM 7.6: The set (+, *, - , X , (Sa), ( T a ): a E Acs} generates clZ* /La;. Proof: Consider any X C W. If i # j then ( S ( i / j ) ) X= C,(D,,. X ) and ( T ( i / j ) ) X= D,, * C,X, and if i = j then ( S ( i / j ) ) X= ( T ( i / j ) ) X =X.Also, ( S ( + I ) ) X = Q X a n d (T(+l))X=PX.Further,(S(-1))X = P(D . X) and ( T ( - 1 ) ) X= D . QX. Finally ( S a p ) X = (Sa)( S p ) X and ( T a p ) X = ( T p )( T a ) X . It follows from 7.5 that c l { + , .,-,A’, (Sa),( T a ) :a E Acs} is included in c l { + , D , C , , Q, P : i < a}. For the other inclusion we observe that D = (T(0/1)) ( S ( O / l ) ) d , C,X = ( S ( i / i + 1 ) ) ( T ( i / i + 1))X and again that QX = ( S ( + I ) ) X and PX = ( T ( + 1 ) ) X. T h e theorem then follows from 7 . 4 . 0 a,-,,?,
The proof also shows that another set of generators for c 1Z*;L, is (Sa),(Ta):a E cl{(+I),(i/i+i):i<w}}. Using the generating set of 7.4 we define for each term T of L, an m-ary and q-ary o-operation \ T \ in the same manner in which the generating set of 2.5 was used to define 171. We let \LpA be L,, together with the interpretation\^\ of its terms. Often we let \LPq\ be simply the set of these operations \T\. Using the generating set of 7.6, we construct a language LACS, and then define \T\and\L,,A analogously. We define the notions of o-model, W-vulidity, and w-consequence as the corresponding lo-notions were defined in ch. 2. We let E k= 0 or l=0 if 0 is an w-consequence of E or w-valid respectively. When we deal with L,, then either we let tm be defined as inch. 2 or we let tm cp result from the tm cp defined there by making the simplifications made possible by QX = X: When we deal with LA,\then we define tm analogously but more simply since LA,, contains a symbol for (Sa) which allows us to define tm (x8(va(,,), ..., v ~ ( ~ - ~without ))) the detour of standard forms. T h e proof of part (a) of the next theorem is then similar to that of 2.6(a). For part (b) one also uses 7.1.
{+;,-,A:
THEOREM 7.7: Let tm be one of the two mappings just described.
(a)\tm+\=G j+/. (b) lf cp and are of the same relational type, then\ tm cp\ =\tm +\ if and only if icp / = / i.
+
+
Part (b) of 7.7 allows us to reduce problems of validity for / L a / to problems of validity for\L,,\ or for \L4c5\.Neither for the language of
I Oh
SECOND ALCEBRAlZATlON
ICH.
7
w-dimensional cylindric algebras nor for the slightly more expressive language obtained from it by adding symbols for each (Sa)such that a has finite support (see [ 151 and [ 131) do we know of a similar reduction. In particular, the mapping of formulas in standard form which one is first inclined to use will not work. For example, x(v,,) would be but not mapped into x, and 3,,x(v0) into cIx.Now ix(vll)/= /3,,x(vo)~ \x\= \ c,x\. We now turn to the task of characterizing \ L,\ = \ L.4rs\ more directly. First, one can verify that for any Jw-operationF , Ej commutes as follows with substitution of variables for variables. LEMMA7.8: Let F be any m-ary Iw-operation and let Y , Y,, C " U . Then ( Z { F ( / [(
G '"Ufor I
~ i ) l s j s , , ) , ~ j ~ , J , : ~ j
G
=
THEOREM 7.9: Let S be
(I
j
G
n))(YJ)lsjs-n
( G F )( ( G I : , 1 ( Y j ) l s . i < n ) ~ s i c , r i .
set of operations of relational similarity
types. (a) 1fS contains @, then G* cl tre" S el G'j' S . (b) If S contriins each H such tlwt ire H = 33 f o r some s
c
G E S , then c l Z " S Proof:
u U , ...,
c Z'!' cl tre'"S .
< w and
(a) Assume that S contains 4. Consider any F € cltre" S . Then F = 16") for some lo-quasiterm 6"such that each lw-operation occurring in 6"is tre H for some H € s. Now suppose there is a subquasi, , , for term (tre H ) ^ 6 , - ... -6,,,of 8"such that N is of type ( T ~ ) ~ ~while some i, 1 d i d in, 6; begins with some tre G , where 15is of a type ( s ~ ) ~such ~ , , that ri # so. Then replacement in 6"of this occurrence of bjby @ = tre @ yields an Iw-quasiterm which also denotes F . Repeating this process one can obtain an lo-quasiterm 6 such that 161 = F and such that, for some quasiterm A of a relational type in which each G belongs to S, A yields 8 by the replacement of each G by tre G. Let 8' be the w-quasiterm which results from 6 when each t r e G is replaced by G C . Then \6'\ belongs to (.I G:::S. By 7.3, \8'\=W-i A = Z ( t r e / A : ) . By the analogue for tre of 2.3, tre / A : = 161. Hence \a'\ = GI61 = G F . Therefore G*:cltre4: S C c1G:;:S. (b) Assume that S contains each H such that tre H =SG for some s < w and G E S. First, consider any w-quasiterm 6' such that no
CH.
71
I07
SECOND ALGEBRAIZATION
quasivariable occurs in 6'more than once and such that each w-operation occurring in 6'is 3H for some H E S. By 3.l(b), 3H = d(3H) for each H E S and s < w . By induction one shows that to each occurrence of any GH in 6'one can assign an s < w such that, given any occurrence of a subquasiterm (DH)-b,^... -6, in a', if H is of type 1 S i S m,ai begins with TjG, G is of a type (s~)~~?,, r has been assigned to the occurrence of 3H being considered, and s has been assigned to the occurrence of G being considered, then s,, s = ri r. Let 6 be the Iw-quasiterm which results from 6'by replacing each particular occurrence of any G H by 3H, where s is the number that has been assigned to this occurrelice of &H. Since no quasivariable occurs in 6 more than once, there is a quasiterm A of a relational type such that A yields 6 by the replacement of each G by tre G. Then GI61 = G ( t r e / A j ) = \ 6 ' \ by the analogue for tre of 2.3, and by 7.3 and 3.l(b), respectively. By the assumption on S, each 2H in 6 is tre G for some G E S, so that 161 E cl ?re* S. Now consider any n-ary F E clZ*S. Then there is some w-quasiterm 6' of the kind just considered and there are Zi,, 1 i < m , such that F ( Yj)lsjsn = \6'\(Z~~~(Yj)lSjsn)lsism for each Y, C " U , ..., Y , C " U . If 6 is obtained from 6'as above, then
+
+
F(Y J ) ] <= J ~(Ol6l) ~ ((a]:) (yj)1SJS,)1s2s7rl
=(&(l8l(fz (Xj)lSJsn)lstsm:XJ c I"Ufor 1
4j G
n))(Y,),,,,,
by 7 . 2 ( c ) ,and 7.8, respectively. Since cf tre* S is closed under substitutions and since 161 is in cl tre* S , so is (ISl(l;( X j ) l s , s n ) l s t s , n : X, I"U for 1 s j C n). Hence F is in G* cl ?re* S . Therefore cl o'*S c G* cl tre* S . 0 Since /L3/is closed under substitutions, 7.9 and 3.8, together with 7.4 and 7.6, yield:
THEOREM 7.10: \Lw\ =\ LAC\\ = cf o'* i La i = G* red* :La[ Turning briefly to compactness, we should like to mention that Ralph McKenzie, in a work not yet published, has used ultraproducts to show that, if every finite subset of a set E of equalities has an wmodel, then E has an w-model. In contrast, the w-consequence relation E b T = T ' is not of finite character. For example, let E be the set
I ox
SECOND A1 CnEBRAIZATION
[Ch.7
q’d: 0 S i < w}. Then E ‘F qx = cox. but there is no finite subset E’ of E such that E’ ‘F qx = c,,x. Next. we shall give an example where one has an implicit definition but no explicit definability. Let any U # @ be given. The constcrnt functions shall be those j E “U such that J; =f, for each i < j < w. We let
{x
Q
11$ = { ( r i ) - j J’ E and eitherjis constant and 11 =A, o r j ’ i s not constant and II =A+, for the least i such that
./; + t ; I I *
‘
Then D$ may be regarded as a characteristic function of the set of constant functions., By 7.10. each \ T\ is G ( r 1 F ) for some F and Y < w . Hence. if U contains at least two objects, then there is no T which explicitly defines D$ in the sense that \T\ has D$ as its only value. Let E d + consist of the following five equalities: ( I ) c , , x = 1, (2) qx * c , ( d * qx) C d. ( 3 ) d * x Q qd * qx. ( 4 ) -qd - x c,(d qd), and ( 5 ) qd * x * cl(-d * qx) = 0. Let ( U , X 6 ) 6 , , be any w-structure. One verifies that if X,,= DS, then ( U , X 6 ) 6 c r )is an w-model of E d $ . Now assume that ( U ,X 8 ) 6 , , is an w-model of Ed*.Let X = XI).We shall show that X = D$ and hence that Ed+implicitly defines D$. Consider any .f E “ U . Suppose ( r r ) - f E X and (~i,)-fE X . Then ( i t , , u)-f E Q X . Also ( i t - , i t . ) - j E D . Q X and therefore (M*,rr>-f E C, ( D . Q X ) . By (21, i.e., since ( U , X6)s
CH.
71
I09
S E C O N D ALGEBRAIZATION
now the case where J;, # u. Iffo f fi, then, by (4), u =f, and hence u =A+1 for the least i such that A # Now assume as inductive hypothesis that if the least j such that gj # gj+lis i , then ( w ) ^ g E X if and only if w = gi+l.Suppose that the least j such that f, # f,+, is i + l . Then f o = f l and hence ( u ) ^ f E Q D . X . Let g = (fi,h,...). If ( w ) - g were in X and w # 11, then (11, w)^g would be in - D * QX, and hence ( u ) - f = (u,J;,)^g in C , ( - D * Q X ) , which is impossible by (5). Hence, by ( 1 ) , ( u ) ^ g E X. Hence, by the inductive hypothesis, u = gi+l
=A+2.
For the rest of ch. 7 we return to I LJ. Let Acs
t
=Acs
*
{a:a ( j ) 2 a ( i ) wheneverj 2 i } .
F o r each a in Acs t andfin I"U, the set { i : a ( i ) E d o m f } is an initial segment of w and hencefa is in IWU.Thus for each a in Acs t one can define lo-operations ('Sa)and ('Ta) as (Sa)and ( T a ) were defined at the beginning of ch. 7 , except that one now lets,= /' IWU. T h e next theorem gives a set of generators for I L,I, which is closely related to the set of generators for\ L,\ that was given in 7.6. The Boolean operations involved are, of course, lo-operations.
THEOREM 7.11: ILwI=cl{+,.,-,X, ( ' S a ) , ('Ta): a E A c s ? } ., -,I,('Sa), ( ' T a ) : a E { (+ 1) } + { ( i / i+ 1 ) : i E w } } . Proof. Note that f E ( ' S y ) ('Ty) X if and only if, for some h E X, dom f . r m y = dom h .run y and f ( j )= h ( j ) for every j in d o m f . run y. It follows that
= cl{+,
( ' S ( i / i + l ) ) ( ' T ( i / i +I ) ) k U = kU ifk $Z { i , i + 1 ) . ( ' S ( i / i + l ) ) ( ' T ( i / i +l ) ) k U = iCJ+i+lUifk E { i , i + I } .
Now let i < w and let Ci, P, Q, Djk be as in ch. 2. One verifies that ('T(i+ l / i + 2 ) ) ( ' T ( i / i +l))4'= ( D i ( i + lD) .( i + l H i + 2Ii+'U, ))+ ('S(i+ l / i + 2 ) ) ( ' T ( i + l / i + 2))((Di(i+1) . D(i+l)(i+2))+ "+'U) = Di(iC2) "+'U,
+
( ' S ( i / i + l))('T(i/i+1))(Di(i+2)+ li+lU) = - 1 i + 3 U + 1 i + 2= U -i+zU,
( ' T ( + 1 ) ) ( ' T ( + 1 ) ) (i+")
= 'U.
I10
Also,
SECOND ALGEBRAIZATION
[CH.
7
+
C,X = ('U . X ) (--IU. ( ' S ( i / i + 1 ) ) ( ' T ( i / i +l ) ) X ) , Q X = - " U . ('S(+l))X, . PX= ('T(+l))(-('U.X),
D =-"U. ('T(O/l))X. Hence the third set of the theorem includes the first. By 3. I I , the first \et includes the second. (A more direct proof can be given by showing, with methods similar to those in the proof of 7.5, thatAc.7 t = (.I{(+ l ) , (A I ) , ( i / i + I ) , ( i + l / i ) :0 d i < w } . ) Evidently, the second set of the theorem includes the third. 0 Unfortunately, an axiomatic approach to ILpqlwhich takes the operations ('Sa)and ( ' T a ) , a E Acs T , as primitive does not look promising. Mainly. ( ' S a ) ( Ta)( ' 'Sp)('T p ) and ('Sp)('T p ) (' S t y ) ( ' T a ) often differ. For example, if i > 0 then ( ' S ( i - l / i ) ) ( ' T ( i - l / i ) ) ( ' S ( i / i + 1 ) ) ( ' T ( i / i +l ) ) ' + ' U is ?-'I!) + ' U +'+'U whereas ( ' S ( i / i + 1 ) ) ( ' T ( i / i + 1 ) ) ( ' S ( i - I / i ) ) ( ' T ( i - l/i))I+'U is IU+'+'U. This failure of commutativity is caused by sequences f and g in IWUforwhichfo( i / i + I ) = g o ( i / i + l ) a n d y e t d o m f = { O , . . . , i - I } # (0, ..., i - I , i } = dorn g . This suggests that, given a transformation a in Acs, we restrict ourselves to certainfa. T h e restriction will be carried out by choosing a certain number t h r a , the threshold for a, and letting & be the function which satisfies (i) d o m & = C { " U : n 2 t h r a } , a n d (ii) if f E d o m n , then &( f ) =fa = ( ( 1 4 , i): a ( i ) E dom f and f ( a ( i ) )= 1 4 ) . It is desirable to choose the values thr a so as to satisfy the following four conditions: (iii) run & 1 " ~ ; (iv) if & ( f ) = & ( g ) ,then dom f = dqm g ; (v) iff E dorn & and & ( f ) E dom @, thenf E dom ap; (vi) i f f E dom & and if i # j but a ( i ) = a ( j ) ,then a ( ; ) E dom f a n d h e n c e i E d o m & ( f )a n d j E d o m & ( f ) . To carry out the proof of 8.6 below, we also want rhr a to satisfy: = (&( f))-h = (fa)^h for any (vii) if f E dorn &, then &vAh) h E IWU. Also, we should like h t o have the largest domain compatible with
CH.
71
Ill
SECOND ALGEBRAIZATION
these conditions. For any a in Acs we therefore pick the least k which satisfies both (i)' a ( k + m ) = a ( k ) + m f o r e v e r y m < wand (ii)' a ( k ' ) < a ( k ) for every k' < k, and then let thr a = a ( k ) . One can verify that k satisfies (iii), ..., (vii). For any a in Acs we now introduce the following two lo-operations, distinguishing them from the corresponding o-operations of 7.6, which will be used much more often, by means of context: (Sa)X=
{fi&(f) E X } = { f E C { " U : n 2
rhra}:fa E X } ,
( T a ) X = { & ( f ) : f ~ X } = { f i E C { W : a ( m )2 t h r a } : f E X } .
To illustrate, let a = (+ 1 ) . Then thr a = 1, dom (x = C n b 1) = Q x a n d i f n 2 1 a n d f = (fo,fi, ...,f n - l ) i s i n " U t h e n & ( f ) = (fi, ..., f,-,).Then (Sa)is the lo-operation Q and ( T a ) the lo-operation P . Now let a = ( j / i ) where j # i. Then t h r a = mrtx(i,j) 1 , dom & = Qmfrsci~j'+l,K (Sa)is the lo-operation Sf, and (Ta).Y is the lo-operation Dji. Assigning the above lo-operations (Sa)and ( T a ) to ( s a ) and (ta) respectively, we obtain in the now familiar way for each term 7 of LACS an lo-operation 171. We let I LACS/ be LA,, together with this interpretation of its terms. Often, IL,,,I will be simply the set of these is the set of lo-operations lo-operations 171. I n the latter sense, lLAcSl which is generated by {+, *, -,X,(Sa),( T a ): a E Acs}.
+
THEOREM 7.12. I LAC,/= I L, I. Proofi One can verify that C , , X = - Q X . X + Q P X and C,+,X = --Q'+'X*X+ ( S ( i / i - 1 ) ) ( T ( i / i - -1 ) ) X . It follows from the illustra= cl{+, .,--,A', (Sa),( T a ) : a E Acs} tions given above that lLAcSl includes I L, I. T h e other inclusion follows from 3.1 I. 0 An axiomatization of lLAcSlusing the primitives suggested by the preceding discussion has not been undertaken but may be worthwhile. In applications, it would have the advantage over E,, that translations from L, would be simpler. Also, by 8.6 and 9.18 below, it would yield a subtheory, evidently proper, of the theory yielded by the axiom set TBACsof ch. 9, and thus might add to our understanding of it.
CHAPTER 8
AUGMENTED CYLINDRIC THEORY FOR SETS OF a-SEQUENCES
In this chapter we shall give an axiomatic basis for the set of those equalities of L which are w-valid. In fact, we shall show that a basis for the o-valid equalities is obtained by adding to any basis for the lo-valid equalities the two further equalities q l = 1 and -co- d * qx =-C,,-d.x. We begin by relating cId':S to cluce" S, where S is any set of operations of relational types which satisfies certain weak conditions. In particular.\L,\ will thus be related to.lL,,I. The definitions involved and 3.1(b) yield: 8. I : Let F be uniformfrom r on. Then LEMMA G(r1 F ) = Z ( ( r + s )
1
F) =G(
3 ( ( r + s ) 1 F : s < 0)).
THEOREM 8.2: Let 6 be any lo-quasiterm such that each Iw-operation occurring in 6 is some uve G , let 6' be the w-quasiterm which results from 6 when each occurrence of uny u v e G is replaced b y GG, andlet 161 be uniformfrom r o n . T h e n d ( r 1 161) =\a'\. Proof: Let 6 , 6', and r be as stated. If 6 is a quasivariable o r some uue G , then G ( r 1 161) =\a'\. Now let 6 be (uve C ) ^ S , - . . . and assume as inductive hypothesis that d ( r i 1 !?yi1)= \a:\ where 6: is uniform from ri results from 6,as 6'results from 6 and where on, I S i d m . Let G be of type ( s ~ and ) ~let ~r = ~ max ( r l , ..., r m ) . Then, by 3.4, 161 is uniform from t = s,,+ r on. By 8.1, it therefore Consider any g E ' U , h E "CJ, suffices to show that G ( r 1 161) = 6'1. and such that X 6 C "U for each 6 < 71. Now 6'= ( G C ) 6;... -6;= ( G ( i G ) ) - 6 ; - ... -6;.Hence
-
(x&),<,
la'\( x 6 ) 6 < 1 = (T'o(3G))( \ 6 ~ \ ( x 6 ) 6 < V l ) l = Z i s m Now the following four conditions are equivalent by the definition of -, the inductive hypothesis and 8.1, and (9) of ch. 3, respectively: 112
CH.
81
113
C Y L I N D R I C T H E O R Y FOR S E T S OF W-SEQUENCES
g E ( 7 C ) ( ‘ + ” U .( Z ( ( r + s i ) 1 1 6 i l ) ( ~ ~ ) ~ < ~ ) c h ) ~ ~ j s ~ ~ ~ .
Also
g E (33)(r-iFLU . I6jl(Xs-h)s
(?G)
(r+3c
U . I6iI(Ys)sfi
... -67nl(ys)*
-
=
Iw)-61-
=
((r+s0)1 I(uueG)-6,-... 6ml)(Yds
=
t t l l@I)~Y*)6
Hence the following three conditions are equivalent: g E (TG)(rfslU .16jI(Xs-h)s
Thus g-h E \6’\(Xs)6
THEOREM 8.3: Let S be a set of operations of relationul similarity types which satisfies the conditions of 3.9. Then el &*’ S = G*’ cl me*:S . Proof: Assume that S satisfies the conditions of 3.9. By 7.9(b) and the proof of 3.9, cl d* S C 3* el tre* S C G* el uue* S. Now consider any F € cl w e * s. Then there is some 6 satisfying the hypothesis of 8.2 such that F = 161. Let 6’ result from 6 as in 8.2. By 3.5and8.1,thereissomersuchthatG7=3( E ( ( r + s ) 1 F : s < w ) ) = \S’\ and hence is in el&* S . By 3.9, 3.8, and 7.9(a), for each s < r there is some G, E cl&*:S such that iA(s 1 F) = G,. Now ‘oF = c{s’(s 1 F ) : s < w} = 2{G,: s 6 r } . Since the o-operation is in cl d* S and each G, is in ~ 1 3 :S:, :we therefore see that SF is in cl 3”S. Hence G* cl w e * S C cl G:’:S. 0
+
Since satisfies the conditions of 3.9, lLwl = cf w e * : ; L a : ,and \Lm\ = cl w * La:, 8.3 yields: I
THEOREM 8.4:\L,\
,
=iA*lL,I.
We now turn to the relationship of w-validity to (w-validity. As a corollary of 8.2, one obtains:
I14
CYLINDRIC THEORY FOR SETS OF W-SEQUENCES
[CH.
8
THEOREM 8.5: For j 1, let 6,and 6:be U S in 8.2, and assume that IS(,l= I6,I.I'hen\61,\ =\Sj\. We now relate validity for \L,\ to validity for lL,l. It turns out that for\ LArF\and I L a similar relationship holds.
THEOREM 8.6. Let r O= r , be any equality of L,, or of LA,,. I f lo-valid, then T ( ,= r 1is also w-vulid. Proof. First, let T , and ~ T, be terms of LA,,.Consider any a such that (sa) or (ta) occurs in r(,or 7 , . There is a unique k such that a ( k ) = thr a. Since & ( f - h ) = ( f a ) - h for every f E dom & and h E '"17, therefore the lo-operation (Sa)is uve G for some G of type ( a ( k ) ,k ) . Similarly, the lo-operation ( T a ) is u v e H for some H of type (k, a ( k )). Moreover, "OG is the w-operation (Sa)and 8 H is the o-operation ( T a ) . Furthermore, by 3.5, there is some Y such that 1ro1 and lrlI are uniform from r on. Then by 8.5, given any U f 0,if lrO1 = 17, I then\ro\= \rl\. Now let T(,and T~ be terms of L w . In this case one cannot apply 8.5 directly, because no primitive operation C , of lLwl is uve G for any G , even though each primitive operation of \ L w \ is 3 for some p.' For j s 1, we therefore consider an m-development a,of T.,. Then the denotation of u,(although not in general that of 7,) remains unaffected if we associate with each c, the lo-operation uveC,,r,+l, rather than C,,and with each other functioa symbol the same lo-operation as in ch. 2. Now assume that t= ro= r l ,hence that k u n = ul,and therefore that luol= lull for the given U . Then, by 8 . 5 , \ ~ , \ = \ ~ l \ . Since U is arbitrary, F u,, = uIand therefore b 7 0 = r1.2 0 To show for L, that there are, so to speak, not many more ovalidities than lo-validities, we first prove a lemma related to 3.l(d) and to 7.1. Note that when U is a singleton { u } ,F is the lo-operation Q, and G X = X for each X c_ '"U, then Z ( r 1 F) = i % ( r l G ) but r l F # r l G.
r0= 7 , is
'Choosing Ci rather than ULV Ci.1i + l as primitive for lLwl has the advantage that one deals with an operation which is induced by an equivalence relation on '"U and which has fairly simple algebraic properties. Also, the relationship to the theory of cylindric algebras becomes closer. Note, incidentally, that each primitive operation of \Lw\ is 0% for the corresponding primitive operation F of I L,(. YAlternatively,using the completeness of E, for Iwvalidity, one can prove 8.6 for I., by verifying that 'F 7,)= I,for each equality in E,.
CH.
81
I15
CYLINDRIC THEORY FOR SETS OF W-SEQUENCES
LEMMA8.7: Assume that U contains at least tbtw objects. Consider any r , 0 s r < w , and any Jw-operationsF and G . Then G ( r 1 F ) = & ( r 1 G ) implies that r 1 F = r 1 G . Proof: Let i40 and i d 1 be distinct objects in U , a r d let h = (h,),h l , ...) E "U be such that h, = uo and h,,, = 11, for each i < w . If g is a proper initial segment of g' E 1"U, then the last occurrence of 14, in g-h is earlier than the last occurrence of 110 in g'-h and hence g-h f g'-h. Hence for any g and g' in '"U, if g-h = g'-h then g = g'. Now con'"U and any g E I"U. Then g E (X'h)-h if and only sider any X if g-h E X'h if and only if, for some g' E X , g'-h = g-h and hence if and only if g E X . Hence (X'h) ' h = X . Now let F and G be m-ary Jw-operationsand consider any g E ' U and X I C '"U,..., X,,, C I"U. Then g E ( r l F)(X,),,,,,,, = ( r l F ) ( (X,"h) vh)l,,,,n if and only if g-h E ( 3 ( r 1 F ) )(XtAh)lsl,T,L. Likewise g E ( r l G)(X,),,,,,, if and only if g-h E ( d ( r 1 G))(X,'h)ls,s,,. Hence?h(r 1 F ) = G ( r 1 G ) implies that r 1 F = r 1 G . 0 LEMMA8.8: (a) I f the m-developments of T and of T' exist, m 2 2 , rind b co- d T = cn- d T', then c0- d q"'1 * T = co- d q"'1 * 7 ' . (b) I f T and T' contain neither p nor q and if !F -cO- d * pk7 = - c ~, d p%', then -co - d * q21 pk7 = -cO - d * q21 * p%'. Proof: (a) Assume the hypothesis of the lemma. First consider any U which contains exactly one object. Then Id( = Q'k: hence (co-dJ = Q'X, and therefore Ic0-d.q"l -71 = @ = IclI-d.q7'~l-7'1. Now consider any U which contains at least two objects. Let r 2 m. By 8.2 and the device usedforproving 8 . 6 , 3 ( r 1 171) = \ T \ a n d & ( r 1 17'1) =\TI\. Since ' ~ c ~ - d . ~ = c ~ - d\T\=\T'\. . ~ ' , Hence, by 8.7, r l J ~ l = r17' l 1. Hence Iq'l.-q'+'l.TJ= l q ' l . - q ' + ' l . ~ ' I , r 2 m. Hence ( q " l - ~= l ( q " l - ~ ' and ( therefore ( c , - d - q ' n l - ~ l= ( c o - d q"X.7'1. Since this holds for any U # @, b c o - d - q n t l - T = c o - d q"1 * 7 ' . (b) Assume the hypothesis of the lemma. First consider any U which contains at least two objects. Then Jco-dl = X and hence ) - q - d - q Z 1 . p k T 1 = @ = I-q-d.qZ1.pkT'I. Now consider any U which contains exactly one object. Consider any m 3 2 and X , '"U, 6 < 7. For each 6 < 77 let Y , = 0 if k+7nU X , = 0 and let
-
-
-
-
-
-
I16
CYLINDRIC THEORY FOR SETS O F W-SEQUENCES
[CH.
8
Y, = "U if h + f ' i UX,. # 0 and hence k+fnU* X - k+ffrU. By induction, if u contains neither p nor q, then h + r t l UI .U I ( X ~ ) ~is <0~ or k+f"U according to whether \u\(Y 6 ) , , , is @ o r " U . Hence "IU . ( p A r l ( X g ) g < o is 0 or f f l Uaccording to whether \ phr\(Y 6 ) 6 < nis @ or " U . Similarly for phr'. Since \ph7\ = \pkr'\, therefore Iqtfil -q"'+'l * pkrl = Iq"'1 * -qff1+Il pkr'I. Since this holds for any m 3 2, )q21 p"r1 = 19'1 * pkr'l and therefore I -co - d q'l pkrI = I - co- d $1 * p'r' I. Since this holds for any U # 0, -c,, - d q21 pkr = -co - d q21 * p h d 0 fi
-
-
-
-
-
-
THEOREM 8.9: Thefollowing two conditions ure equivulent: (i) b 7 = 7'. (ii) There is u j n i t e sequence ( T , ~..., . r t ) of terms of L, such thut r0is r , rt is T' und,for erich i < t , either ( 1 ) I= r, or ( 2 ) r, yields T , + ~b y the replacement of (in occurrence of q l by one of 1 or vice versa, or ( 3 ) f o rsome p , r, yields T,,, by the replacement of un occurrence o f -co - d * qp by one of -co - d p or vice versa. Proof: That (ii) implies (i) follows from b q l = 1, b -co- d qx = -co - d x, and 8.6. To show that (i) implies (ii), we first consider a special case. Assume that k -co - d r = -co- d 7'. T h e same procedure which is used for finding the normal transform of a term, except that further use may be made of k x = pqx, yields some k < w and terms pkp and pkp' such that I= r = pkp, k r' = pkp', and p and p' are normal and d o not contain p. Let u result from p by replacement, for each i # 0, of each quasiatomic occurrence of any q'xg o r q'd by -co - d q'xg o r -co - d * q'd respectively, and let uA result from u by replacement, for each i # 0, of each quasiatomic occurrence of any q'G or q'd by xg or d respectively. Let u' result from p ' and u ' A from uf similarly. One verifies that -co - d pkp = -co - d * pk(-co - d * p) and that k- c,)- d p = - co- d u. Hence, (a) - cO- d r = - co- d * pku, and thus 'F -q, - d r = -c, - d pku and therefore also b -q, - d r - -c,,-d pAue. Likewise, ( p ) k -c,)-d r' = - co- d pku', and therefore also k - c,,- d 7'= - cO- d * pkufA. Hence also k -qI - d p k d = -q, - d pku'A. From 8.8(b) it follows that ( y ) k -c, - d q21 pkuA= - c,- d q21 - p k d o . From (a), ( p ) and ( y ) it follows that there is a desired sequence from -c, - d * r to
-
-
-
-
-
-
-
-
+
-
-
-
-
-
-
-
-
-
-
CH.
81
- cI,- d - T ' , i.e.. a sequence -c0-d
I I7
C Y L I N D R I C T H E O R Y FOR SETS OF w-SEQUENCES
.. .
( T ~ ~ , , T ~ such )
that T~~is - cl, - d
- 7'.and one of( I ) , ( 2 ) ,(3) holds for each i < t .
-
T ,T,
is
We now turn to the general case where 'i=T = 7 ' .Since b -ell - d * 7 = co- d r', there is a desired sequence from -cIl - d * T to -co - d 7 ' . Also, since 'F cl)- d T = cl)- d T', there is, by 8.8(a). some rn 2 2 and some desired sequence from c0- d q"l r to clI - d q"'1 * 7 ' . Since a = -ell - d a + c, - d a , the two sequences yield a desired sequence from T to 7 ' .0
-
-
-
-
-
One can now utilize the completeness results of ch. 5. If one adds - d x to E,, and then uses BP to make certain obvious simplifications, one obtains a set E',, consisting of the equalities in the Boolean part BP of E,, and of the following equalities:
-
q l = 1 and -ell - d qx = -co
-
1. (a) c,O = 0.
(b) X - C , X = X . (c) c,(x c,y) = c,x c,y. (d) c,cJx = c,c,x.
-
-
2. (b) q(x+y) = qx+qy. (c)' q - x = -qx. (d) qctx = ct t 1 qx. (f)' qpx = cox. (g) Pqx = x.
3. (a)' c,d = 1, for i < 2. (b) c,d = d, for i 2 2. (c) d,, c,(d,, x) = d,, x, for i # j and -2 (d)' -cI)- d qx = -co-d x.
-
-
-
S
i-j
i2.
The completeness of Eiq for Lpqwith respect to w-validity which is contained in the following theorem therefore follows from 8.9, 5.9, and facts about Boolean algebras. The soundness of E;, asserted by the theorem can be verified. This soundness would not have been affected if in the definition of w-validity we had allowed U to be empty, since U = Q implies that "U =Q and hence that X = Y for a n y X C " U , Y " U . (We recall from ch. 4 that for EMand Iw-validity the situation is different since "4 # 0.)
THEOREM 8.10: 'F r = T' ifandonly ifEA
7
= 7'.
1IX
C Y L I N D R I C T H E O R Y FOR S E T S OF w - S E Q U E N C E S
[CH.
8
Let Eq reshlt from Eh by the removal of 2(g) and by the replacement of 2(fY by 2(f), qx = c,,qx. Observe that the sequences ( T o , ..., r t ) constructed in the proof of 8.9 consist entirely of terms of L, whenever 7 , )and 7, are terms of L,. From this observation, 5.8, and l= qx = c,qx it follows that E’q is in the following sense sound and nearly complete for L, with respect to w-validity :
THEOREM 8.11: If T and T ‘ are terms of L,, then ’F qJ”T= q”’T’. onlv ifthere is some m such thut E;
T = T’
if and
We conclude with another model-theoretic result which, however, in view of 8.10, also has a proof-theoretic and an algebraic content. It contrasts with the failure, described in ch. 7, of the analogue of Beth’s theorem.
THEOREM 8.12: If \= p C T , then there is some u such that any uariable occurring in u occurs both in p and in T und such that ~ p < u a i n d ~ c r < r . Proof: By the first part of the proof of 5.9, it is sufficient to consider the case where p and T are m-normal, m 2 2. Assume that ’F p 5 T . Then, by 8.8(a), I= ql- d qml (p T ) = c, - d q”1- p and hence k co- d * q”‘1 p co- d q”‘l T . By 3.19, and earlier results about normal transforms, there is some k and some term u’of L, such that any variable occurring in u’occurs both in p and in T and such that, using an obvious convention, l= c0- d qnl p 6 qnl * p k a ’ < co- d q“l T for each n 3 m. Moreover, for n large enough one can choose u’such that, for each U # 9 , the denotation lqnl p k u ’ I of qnl pko’ remains unchanged if with each ci in p‘u’ we associate uveC,.r,+l rather than C , . Then, by 8.5, F ’ c O - d . q n l - p < qnl . p ” u ‘ 6 c,-d * q”l T , and hence ! F c,)- d p < pku’ < c,- d 7 . Using ’F -c,, - d * qx = -co - d x, k -c0 d px = -cod * x, 8.8(b), and 3.19, one can also show that there is some term a’’of L, such that any variable occurring in a’’occurs both in p and in T and such that ’F - co- d p g u ” < - c , ) - d - ~ . T h e n ’ ~ p< u “ + p k u ’ C 7 . 0
-
-
-
-
-
- -
-
-
-
-
-
- -
-
-
-
-
CHAPTER 9
A THEORY OF TRANSFORMATIONAL AND OF BOOLEAN OPERATIONS
In a large part of this chapter we shall consider an arbitrary index set I, which shall be kept fixed. It should be clear what is meant by an (m-ary) I-operation, I-validity, etc. Simple changes in earlier definitions of certain o-operations then yield the following I-operations, wherea E '1,J C 1 , M C 21,andA/=IU. (Sa)X={fE/Y:fa E X } .
( T a ) X = {fa:fE X } = {g: g =fa somef E X}. (CJ)X = {f E /y: for some g E X , g ( i ) = f ( i ) for each i fZ, J } .
( D M ) = {f E / V : f ( i ) = f ( k ) foreach ( i ,k ) E M ) . ( E M ) X = { f E X : f ( i ) =f(k) foreach ( i , k ) E M } . In a large part of this chapter we shall also consider a set Y of transformations (on 1 ) which is closed under composition, but otherwise arbitrary. Again, unless stated otherwise, ,Y shall remain fixed. it is natural to consider the union { (Sa):a E 9} Given 9, { ( T a ): a E 9}, and then the closure of this union under composition. T h e operations in this closure shall be the trunsformutional operations (resultingf r o m 9). From the transformational operations (resulting from Y ) and the Boolean I-operations one is led to their union and then to the closure of this union under substitutions. According to 9. I below, this closure includes the operations ( C - r u n a ) and ( D a - a ) where a is in .Y. Thus, a theory based on a language for the operations in this closure will have similarities with an algebraic theory of logic.'
+
'The systematic use of ( T a ) . in addition to (Sa)and the Boolean operations. was initiated by Howard[l6]. This was partly done on our suggestion, which in turn was partly caused by his use of some operations ( T a ) in an earlier draft of[16]. Howard's operations are on certain sets X C Z { ' U ; J I } and include the 0-ary operation {@}, i.e.. the set consisting of the empty sequence. In general. { @ } is not definable by the other primitive operations of his language. I19
I20
I RANSFORMATIONAL A N D BOOLEAN OPERATIONS
[CH.
9
We shall investigate a set TBv of I-valid equalities of this language. From a certain subset TB, of TB, we shall derive enough consequences to show that the theory, adjusted to Y ,of polyadic algebras with diagonal elements can be developed from it. (The definitional equivalence of the two theories will be proved in[9].> O n our way, we shall give an easy completeness proof with respect to that fragment of the language which corresponds to the quantifier-free part of firstorder logic with equality. Also, we shall consider a question of independence. In the last part of this chapter we shall turn to the special case where .Y is the set Acs, introduced in ch. 7, of almost constant shifts. We shall show that T B I , , is complete in the sense that each equality of L 1 , , which is I-valid can be derived from TB.,,,. It follows that problems of validity in first-order logic with equality can also be reduced to problems of derivability from T B 4 c s . One uses the mapping t m , given just before 7.7, of formulas of L 3 into terms of LA,,. Henceforth, we usually let i , j , X , ... be elements of I. Also, J, K , J', ... shall be subsets of I, while M , N, M ' , ... shall be subsets of 'I = I X I, and a , p , y , ... shall be transformations on I. We let id be the identity transformation. The relative product, and hence in particular composition, will be indicated by juxtaposition. For example, MN shall be { ( i , k): there is some j such that ( i , j ) E M and ( j ,X ) E N}, and (Sa)( T p ) shall be ( (Sa)( ( T p )X ) : X C 1).At the same time, our earlier convention for indicating values of functions for arguments shall remain in force. For example, ( i / j ) i will be j and ( T p ) X will be a subset o f 1 . Which of these two uses of juxtaposition is involved should be clear from the context. We let M - be the converse of M . It follows that a'a is the equivalence relation { ( i , k) : a ( i ) = a (k) } . We let a i J = { a ( i ) : iE J } , a * M = a M a - = { ( a ( i ) , a ( X ) )( i:, k ) E M } ,
a-'J
=
{i:a(i) E J } ,
a-'M=a'Ma=
{ ( i , k ) : ( a ( i ) , a ( k )E ) M}.
We let -J = { i : i 6! J}.The intersection, and hence the least, of those N which are equivalence relations on I and include M shall be eqv M.
CH.
91
IZI
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
If M = eqv M and if for each i there is exactly one j E K such that ( i , j ) E M , then K shall be a cross-section of M. We let M f J = ( M * 2J)+id and call it the conjinement of M to J. Note that M = eqv M implies that M r J = eqv ( M r J) . The identities in the following lemma will play a basic, although essentially heuristic and somewhat hidden, r6le. They follow from the definitions involved. LEMMA9.1 : Let a be any trunsformution. {a) ( C - r u n a ) = (Sa)(Ta). (b) ( E a - a ) = (Ta) (Sa). (c) (Da-a) = ( 7 - a ) X .
We now introduce a language for the transformational and Boolean operations and for the operations which they generate by substitution. More precisely, we let L, be an algebraic language whose function 1, symbols having 2, 2, 1, 0, 1, 1 places respectively are +. where a E Y. To these we assign, respectively, the (sa), (ta), appropriate Boolean operation, (Sol), and (Ta). By induction there is thus assigned to each term 7 of L.? an I-operation \T\. We let \Ly\ be L Ytogether with this assignment. Often,\LY\ will be simply the set of operations \71 Conventions used earlier for other languages shall henceforth apply to L, or \L,\respectively. For example, u s 7 and 7 3 u shall be the equality u 7 = 7. For convenience, we shall henceforth assume that (O/I) is in .4p (and hence that 0 and 1 are in I ). For any a in 5’ we let be the term - ( s a ) ( t a ) - (ta)l of Ly.We 1etJdbe the termJ&,,l). We now present nine sets of equalities. Here a, p, y shall be arbitrary elements of 9.
-.-.
+
T BI. TB2. TB3. TB4. TBS. TB6. TB7. TB8. TB9.
(sa)- X = - ( s ~ ) x .
+
a
+
(sa)(x y) = (sa)x ( s c u ) ~ . (ta)(x+y)= (ta)x+(ta)y. (sa)(ta)x 3 x. (ta)(sa)x s x. (sa)(sp)x= (saP)x. (sa)(ta)(sp)(tp)x = (sp)(tP)(sa)(ta)x. (sa)(tp)l s (ty)l, provided y - y = eqv (sa)(Jd-x) = x.
a*(p-p).
122
[CH.
T R A N S F O R M A T I O N A L A N D BOOLEAN OPERATIONS
9
Among the above, TB3 was suggested by TB2, TB5 by TB4, and TB9 partly by Theorem 1.3.19 of [ 151 and partly by 3(d)' of ch. 8. The others have been taken or adapted from the literature. Specifically, T B 1, TB2 and T B 6 are from p. 1 1 1 of [ 131. By 9.1(a), TB4 and T B 7 correspond to (C,) and (C,) respectively of § l . l of[151, and also to l(b) and I(d) of our chs. 4 or 8. Also, by 9. I(c), TB8 corresponds to one half of (D 1) of p. 260 of [2O]. We let T B = T B , be the union of the sets TBO, T B I , ..., TB9 where TBO is the set BP of ch. 4, i.e.. a set of equational axioms for the theory of Boolean algebras such that -,-, 1 but no other function symbols are used. We let TB- = T B r be the union of the sets TBO, T B I , ..., TB8. We let be derivability from TBO ... TB5. Also, we let TB, k and T R ,t be derivability from TB; or T B ,, respectively. Furthermore, for example, we let 6 , s k be derivability from TBO ... +TBS TB6 TB8. Here. as in chs. 4 and 8, T = T' shall be derivable from a set E of equalities if and only if there is a finite sequence (T",..., T ~ ) of terms of L , such that 7,, is T, T~ is 7'and, for each r < t . substitution of terms for variables throughout some equality in E yields an equality a = a' such that replacement of some occurrence of u by one of a' changes either T,-, to T, or T, to T , - ~ . Using 9.1, one can verify that T B , is sound with respect to t validity, i.e.. that each T = T' in TB, and hence each T = 7' derivable from T B , is I-valid. Indeed, T B , also lends itself to certain other interpretations of which we shall now give an example. Assume, for a moment, t h a t x i s Z { ' U : J E f}, instead of'(/. For eachf E A', let f a be the element { ( I ! , i): ( I ! , a ( i ) ) E f } of 1. Assume that (Sa), ( T a ), and the Boolean operations are defined accordingly, so that ( T a ) X = { f E A': CY CY f ' J ' + ' ( - d o m f ) } . Then all equalities in 0, which with TBO, TBO. ..., TB8 hold as well as the equality T B 1 , TB2 implies those in TB9. The equalities in T B , also lend themselves to an interpretation which includes the one mainly intended as a special case and which has been suggested by Halmos [ 131, pp. 102- 104, 2 18-220. Let B be the set of elements of a Boolean algebra %, and let X and Y be B valued functions on ' U , i.e., functions whose domain is 'I/ and whose range is included in B. Let X + Y . X . Y , - X , a n d X b e those B-valued functions on ' U which for each argument f satisfy respectively
+,
+ +
+
+
+
a=
cn. 91
I23
T R A N S F O R M A T I O N A L A N D B O O L E A N OPERATIONS
( X + Y ) ( f ) = X ( f ) + J ( f )( X . V ) ( f ) = X ( f ) . a Y ( f ) , (-XI ( f ) = - s ( X ( f ) ) , (X)( f ) =A&. Also, let ( S a ) X be the B-valued function on ' U which for each argument f satisfies ( ( S a ) X )( f ) = X ( f a ). Finally, assuming that for each f E iU the subset S,= { X ( g ) : g E ' U , and f = ga} of B has a least upper bound C s S , in 93, let ( T a ) X be the B-valued function on 'U which for each argument ,f satisfies ((Ta)X)(f) = C , { X ( g ) : g E 'U and f = g a } . Then ( T a ) I is the B-valued function on ' U which for any argument f yields the value A8if a-a ,f'-f' and @$+otherwise. Now let A be a set of B valued functions on 'U such that X E A , a n d f E ' U , the set { X ( g ) : g E ' U (i) for each a E 9, andf= g a } has a least upper bound in '23, and (ii) A is closed with respect to the above -,A', (Sa)and ( T a ) , a E 9. Then for each of the sets TBO, ..., TB9 one can verify that the universal closure of any equality in the set is true for ( A , ., -, ( S a ), ( T O I ) ) , ~(For ~ . TB2 ,..., T B 8 and ( A , X, ( S a ) , ( T C X ) it) ~ ~ ~ suffices to assume that '23 is an upper semilattice with a greatest element, and to weaken (ii) accordingly.) We now turn to derivability from certain subsets of TBO, ..., TB9. One of our aims is to bring out different levels of generality in algebraic logic. First, we turn to derivability from TBO .-. TB5. 9
+,
a,
+,
+ +
LEMMA9.2: Let a be in 9. (a)ffFu 6 .r,then t- ( s a ) a 6 ( s a ) ~ . ( b ) f f I - a s .r,then F ( t a l a C ( t a ) 7 . ( c ) t- (sa)O= 0. (d) ( s a )1= 1. (el F (sa)( x Y) = ( s a )x ( s a )Y. (f) F ( t a ) O = O . (g) t- ( s a )( t a ) ( s a ) x = ( s a ) x . (h) I- ( t a ) (sa) ( t a ) x = ( t a ) x . (i) F (sa)( t a ) O = 0. (j) I- ( s ~ ~ ) ( t a ) - ( s a ) ( t a ) x = - ( s ~ ) ( t c u ) x . (k) f f I- a 6 7,then F ( s a )( t a ) a s ( s a )( t a ) T . Proofi We shall often use TBO tacitly. (a) By TB2. (b) By TB3.
-
-
+,
I24
I R A N S F O R M A I IONAL A N D B O O L E A N O P E R A T I O N S
[CH.
9
(c), (d). (e) By T B 1 and TB2. ( f ) By part (d) and T B 5 , respectively, k (ta)O= ( t a )( s a ) O C 0. (g) By TB4. k ( s a ) ( t a )( s a ) 2~ ( s ~ ) xBy. T B 5 , E X 3 ( t a )( s ~ ) x , which, with part (a). yields k ( s a ) x 2 ( s a ) ( t a )(sa)x. (h) By T B 5 , k ( t a )(sa)( t a ) x C ( t a ) x . By T B 4 , E X s ( s a )( t a ) x , which, with part (b), yields F ( t a ) x s ( t a )( s a )( t a ) x . ( i ) By parts ( f ) and (c). ( j ) By (c).TBO, (e),(g), and T B 1 , respectively,
EO=
(sa)O= (Sa)((ta)X'-(ta)X) = (sa)( t a ) x (sa)- ( t a ) x
= ( s a )( t a ) x- ( s a )( t a )(sa)- ( t a ) x
= ( s a ) ( t a ) x* ( s a )( t a )- (SOL) ( t a ) x . Hence. by TBO,
k (sa)( t a )- ( s a ) ( t a ) x d - (sa)( t a ) x .
By T B 4 ,
k-
( s a )( t a ) x C ( s a ) ( t a )- ( s a ) ( t a ) x .
( k ) By parts (a) and (b). 0 Part (e) of the following lemma corresponds t o (CJ of $ 1 . 1 of [ I S ] , and also to scheme I(c) of our chs. 4 and 8 (while 9.2(i) corresponds to (C,) and l(a)). Part (f) mirrors the natural definition of ( E a - u )in terms o f . and ( T a ) Y = ( D a - a ) .
LEMMA9.3:Let a E .V. (a) ff E u C ( s ~ ) Tthen , k ( t a ) us T . ( b ) / f k ( t a ) u .r,then C ( s ~ ) T (C)
E(
.
t a ) u ' T = o ~ U n ~ o ~ f (yS L~Y )~T =Uo .'
-
(d) k ( t a ) ( x ( s a ) y )= ( t a ) x* y . (e) k (sa)( t a ) ( x* ( s a )( t a ) y )= ( s a )( t a ) x ( S O L ) ( t a ) y . ( f ) E ( t a )( S d Y = ( t a ) l - y . ( 8 ) t- ( t a )(sa)(x* ( t a )W Y ) = ( t a )( s a ) x* ( t a )( S 4 Y . (h) k ( s a )( t a ) ( x +( s a ) ( t a ) y )= (SOL)( t a ) x + ( s a ) (ta)y. (i) F - ( s a ) ( t a ) - ( x * y ) = - ( s a ) ( t a ) - x - - ( w ) ( t a ) - y . Proof: (a) If u s ( w ) T , then by 9 . 2 ( b ) , and TB5, respectively,
-
1( t a ) u
(ta)(S(Y)7
7.
cn. 31
125
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
(b) If
bT
3
( t a ) u , then by 9.2(a), and TB4, respectively, l-(sa)7
( s a )( t a ) u
3
3 u.
(c) By TBO, parts (a) and (b), T B I , and TBO, respectively, the following are equivalent to each other: F (ta) u 7 = 0; (ta)u s - 7 ;
s
-
(S(Y)-T;~(T~-(Sa)7;~U'(S(Y)T=o.
-
Note that one can similarly prove, for example, that 6F(ta) u 7 = 0 if and only if 6 u ( s a )=~ 0. (d) Using first TBO, 9.2(b), and TB5, then TBO and 9.2(b), and then TBO we get respectively:
-
I-
t-
-I
( t a ) ( x . (sa)y) s ( t a ) ( s a ) y s Y. (ta)(x (sa)y) s (ta)x,
-
(ta)x y.
(tar) ( x * ( w ) y )
Using first TB4 and then TBO, T B 1, and TB2 we obtain
1x
k ) Y s
-
(SOL)
(ta)(x * (sa)Y),
x * (sa) (y - ( ta ) (x * ( s(y ) y)) = 0.
By part ( c )and TBO, respectively, we then have:
t-
- .- (ta)(x
(ta)x (y
1 (ta)x * y s (ta)(x
*
*
(sa)y)) = 0,
(sc.)y).
(e) By part (d), and 9.2(e), respectively,
i- ( s a )(ta)(x *
(SOL)
(ta)y) = (sa)((ta)x * (ta)y)
= ( s a )(ta)x * ( s a )(ta)y.
(f) By TBO, and part (d), respectively,
t (tcu) (scr)Y
= (tcu)(l* h ) Y ) = ( f c y ) 1 * y.
(g) By part (f) and TBO.
(h) By TB3, TB2, and 9.2(g). (i) By TBO, TB2, and T B 3 . 0 We now turn to derivability from TBO+...+TB6 . Parts (d) and
(g) of the following lemma are related to the axiom scheme of substitutivity on pp. 2 15-2 16 of Halmos [ 133. And part (k) corresponds
I26
[CH.
TRANSFORMATIONAI A N D BOOLEAN OPERATIONS
9
to scheme (P,) on p. 1 1 1 of [ 13 ] since, when J = run y, then a y = By if and only if a and p rrgrre o n ./ in the sense that a ( ; )= p ( i ) for each i E J.
L E M M A9 . 4 : L r t c x . a ’ , p , p ’ , y h c ~ i n . Y . ( a ) 6 k ( t p ) ( t a ) x = (tcupb. ( b ) 6 k ( t p ’ )( s ( Y ’ ) x C ( s a )( t P ) x , p r o v i d e d p ’ a = a’P. (c) 6 k (sp) ( t p ) ( s a ) x 6 ( s a ) ( s y ) ( t y ) x , p r o v i d r d p a = a y . (d)6 k ( t y ) l * ($)X (scw)x,p~o~idrdj3a- y-y. (e) 6 k ( s u ) ( t a ) ( ( t a ) l- x ) = (sa)x,providedcycu= a. ( f ) 6 t- ( t a )1 * ( s a )( t a ) x = ( t n ) x , p r o v i d r d aa = a. (g) 6 k ( t a )1 * x 6 ( s a )x, provided acy = a. (h)6 k (sa)(ta)(ta)l=l,providedaa=cr. (i) 6 t- (ta)((tcy)le x ) = ( t a ) l - x , p r - o v i d r d a a = a. (j)6 1 * x) = x , p r o v i d e d a a = a. ( k ) 6 f (sa)( s y ) ( t y ) x = ( s P )( s y )( t y ) x , provideday = PY.
(scy)(Ba Ha*
ProoJ
(a) T h e first assertion in the following sequence holds by TB4, and the others then follow by TBO, the proof of 9.3(c), TB1, TB6, the proof of 9.3(c), and TBO, respectively: 6 6
/-
(tcy)x x
*
C
(SLY)
( s p ) ( t p ) ( t a ) x ; 6 t-(ta)x.-(sp)(tP)(ta)x=O;
6 E x . (saP)-(@)(t(~)x=O; 6 6
F (taP)x
t- x - ( ~ a(sP) ) - ( t P ) ( t a ) x = 0; k (t@)x.-(tP)(ta)x=O;
- (sP)(tp)( t a ) x = 0; 6 (tp) (ta)x.
The first assertion in the next sequence holds again by TB4, and the others then follow by TBO, T B 1, TB6, the proof of 9.3(c), the proof of 9.3(c), and TB3, respectively: 6 Fx.-(sap)(tolp)x=o; 6 I- x (sap) - (tCyp)x = 0; 6 k x * (SQI) (sp) ( t @ ) x = 0;
6 k x 6 (sap)(taP)x;
-
-
6 f (tcy)x * (sp) - ( t a p ) x = 0;
6
I- (tP) ( t a ) x 6
6
F (tp) ( t a ) x
a-
( t o l p ) x = 0;
(t(YP)X.
From TBO it follows that 6
(tp) (ta)x= (tab)x.
(b) The first assertion in the following sequence holds by TB5 and
CH.
91
T R A N S F O R M A T I O N A L A N D BOOLEAN OPERATIONS
I27
9.2(b), and the others then follow by TBO, 9.4(a), P ‘ a = a’P, 9.3(f), the proof of 9.3(c), T B 1, and TBO, respectively:
F (tP)(ta’)(sa’)x.-(tP)X=O; 6 k ( t a ’ P ) ( ~ a ’ ) ~ * - ( t P ) x = O6; I- ( t p ‘ a ) ( ~ a ’ ) ~ ‘ - ( t P ) X = O ; 6 ( t a ) ( t P ’ ) ( ~ a ’ ) ~ . - ( t P ) x 6= O I-;( t p ’ ) ( s a ’ ) x *( s a ) - ( t P ) X = O ;
6 F ( t @ ) ( t c ~ ’ ) ( s a ’ )sx (tP)x; 6
6 /- (tp‘) ( s ~ ’ ) x. - ( ~ a )(tP)x.= 0;
6
(tp‘) ( s a ’ ) C ~ ( s a )(tP)X.
(c) Assume that pa = ay. By part (b), 6
t- (tP) (sa)x
( s o )(tY)X.
Then by 9.2(a), TB6, pa = a y , and TB6, respectively, 6
I- ( s p ) (tP) ( s a ) x
(sP) (SOL)(ty)x =
(ty)x = ( s a y )( t y ) x = ( s a )( S Y ) (ty)x. y-y. Consider any j . Then ( P ( j ) , a ( j ) ) (d) Assume that p a E pa - C y-y. Hence y P ( j ) = y a ( j ) . Therefore yp = y a . Hence by 9.3(f), TB6, -yP = y a , TB6, and TBS, respectively,
6
I-- (ty) 1 -
(sP)x = (ty) (SY) (sP)x = (ty) ( s r P ) x = (ty) ( s y a ) x = (ty)( s y )( S U ) X s ( s a ) x .
(e) By 9.2(g), aa = a and part (a), and 9.3(f ), respectively, 6
( s a ) x = ( s a )(ta) ( s a ) x = ( s a )( t a ) ( t a ) ( s a ) ~
= ( s a )( t a ) ( ( t a ) l SX). ( f ) By 9.2(h), aa = a and TB6, and 9.3(f), respectively, 6
I-
( t a ) x = ( t a ) (SOL)( t a ) x = (ta)( s a )( s a )( t a ) x = ( t a ) 1 * (sa)( t a )x.
(g) By part (e) and TB4. (h) By part (a) and a01= a, and by TB4. (i) By 9.3(f), part (a), aa 5 a, and part (a), respectively, 6 E ( t a ) ( ( t a ) l - x ) = (ta)(ta)(sa)x= (taa)(sa)x = (ta)(sa)x= (ta)l.x.
(j) The definition of J& will be used tacitly. Assume that aa = a.
128
[CH.
T R A N S F O R M A T I O N A L A N D BOOLEAN O P t R A T l O N S
9
By TB4 and TBO, 9.4(i), and TB4 and TBO, respectively, 6
(ta)(@,-x)=
(ta)((ta)l*@,.X)=
(ta)l.fl,.x=@,.x.
Then, by TBO, the proof of 9.3(c), and T B 1 and TBO, respectively, 6
1 (ta)(@, - x) --(@, - X) = 0.
6 ~ J & * x *(sa)-(JZf,~x)=O,
6
1JZf, - x
- x).
aG (sa)(JZf,
By 9.2(e) and T B I , and by part (g) and TBO. 6
k ( t a ) l - x . (sa)(-x*
(ta)x)= ( t a ) l - x . - ( S a ) X ' ( S a ) ( t a ) X = O .
Hence, by TBO, Then
6
F x .( s ~ ) ( - x * ( t a ) x )
6 k ( t a ) x * - ~ = (ta)x. (ta)x.-X= d (ta) - ( t a l l
<-(ta)l.
(ta)(X'(sa)((ta)x*-X))
< (sa)( t a ) ( t a ) - ( t a ) l = (sa)( t a )
-(ta)l
by TBO, 9.3(d), 9.2(b) and the inequality just derived, TB4, and part x. By TBO, (a) and aa = a, respectively. By TBO, 6 kJ&-(ta)x the proof of 9.3(c), and substitution of -x for x followed by TBO we obtain, respectively:
1 (ta)x (fla*-x) 6 1 x - ( s a ) ( J z f , a-x) 6
6
*
l-
(m)(J& * x)
(sa)(d.
x.
= 0, = 0,
-
x, it suffices by To conclude the proof that 6 ( s a ) ( @ , * x) < This follows from the last x) TBO to show that 6 1 x, TBO, and 9.2(a). inequality derived by substitution of (k) By T B 6 . 0 TB6, we Before considering further consequences of TBO now introduce some further notions. We let a be idempotent if and only if aa = a. Thus a is idempotent if and only if a ( j ) =j for each j E run a. Also, if M = eqv M and K is a cross-section of M, then there is exactly one idempotent a such that ran a = K and a -a = M. If ap = id, then p shall be a right inverse of a,and a a left inverse of p. Thus p is 1-1 if and only if p is a right inverse (of some a E ' I ) , and run a = I if and only if a is a left inverse (of some p E 'I).
+ +
CH.
91
T R A N S F O R M A T I O N A L A N D BOOLEAN OPERATIONS
119
We call J a support of p if and only if p ( i ) = i for each i tZ J. We let llJll be the cardinality of J. For each infinite cardinal K we let 9-K= {a E 'I: for some J , J is a support of a and llJll < K } . In is the set of those transformations a such that a has particular, FW (some) finite support. We now list conditions on .Y. Of these, SO, S6 and S7 will not be used until ch. 10. 1f.Y satisfies S I , then .Y shall be regiciur (cf. 151).
+
c
SO. Y cl ( { a E Y :aa = a } { a E 9: Pa = id for some p E ,Y} +{a E Y:aP=idforsomep E Y } ) . S 1. For every a in .Y there is some y in tY such that aya = a. S2. For every a and p in .Y there is some y in .Y such that y - y =equa*(p-p). S3. For every a and p in ,Ysuch that run a . run p # 0 there is some y in
c
LEMMA9.5: Assume that .Y is Acs or c l { ( i / j ): i E I , j E I } or Y Kwhere , K is an infinite cardinal. Then .Y satisfies SO, ... , S7. Proofi To verify that c f { ( i l j ): i E I , j E I } satisfies SO, ..., S7, show that it is the set { i d } {a E J-": run a # I}. When I is finite or K = w, then 9-Kis { b y : p E y E .FK, y y = y , and pa = id = ap for some a in T K as } ,can be easily seen (cf. [ 131, p. 164). When I is infinite and K > w, then Y Kis { B y : p E Y Ky, E K K p'p , = id for some p' E 3-Kand yy' = id for some y' E X,}, as is also not hard to show. Hence in either case, 9-Ksatisfies SO. 0
+
c ~ - K ,
Parts (a), ...,(d) of the following lemma are well-known (cf. [ 5 ] ) . T h e converses of (a) and of (b) hold for any .Y. For regular .Y this furnishes a condition which is necessary and sufficient for p-p C a a or for run a run b, respectively, and which involves only composition.
I30
TRANSFORMATIONAL AND BOOLEAN OPERATIONS
LEMMA9.6: Let
(x
(CH.
9
trnd p hc in ,Y rind. except.for purts (g) and (h),
ussriine thut .Y is rogirlrrr. . there is some y in ,Y such that y p = a. ( a ) 1 j p - p & ~ Y ' C Ythen ( b )l j r a n a C run /3. then thrre i s some y in .Ysuch thut By = a. (c) Therc is sonir y in sY sirch thut y i s idrmpotent und y - y = /3;(3. ( d ) Thew is somo y in .YSLICII thut y is idempotent trnd run y = run p. (el If'run p i s ( I cross-section o j a - a , then the idcmpotrnt y satisfying y ' y = - a rind rrin y = run p i s in .Y . ( f ) 1.f ../ sritisfics S2. then id is in ,Y. (g) I j y - y = oyc (r"(p-p),then ( y a ) - ( y a )= e q v ( a - a + p ' p ) . Hrncr if . / srrtisfirs S2. thcn there is some 6 in .!/ srrch thrrt 6'6 = eyu ( a ' a
+ p -p,. in
( h ) If' . / sritisfios S3 rind ij' run a . rrin p # 0. then there is some 6 srrch thut run 6 = run a . run p.
( i ) I f ' . / sutisfios S3 rind S4 and if run tx . run p = 0 ,fiw some a and p in .Y. thrn j i ) r c ~ c i c lJi f I tlierr is some 6 in .Y s i ~ c . hthut run 6 = J . Proof-
( a ) There is some 6 in ../ such thatp6p = p. Assume that p - p C a - a . Let y = tr6. Since . / is a semigroup. y is in ,./. Consider any i . Since p6/3(i) = p ( i ) , therefore ( S p ( i ) , i ) E p'p C a - a and hence y P ( i ) = tr6p(i) = a ( ; ) .Hence y/3 = a. ( h ) There is some 6 in such that p6p = p. Assume that run a C r u n p. Let y = 6 ( y . Consider any i. There is some li such that a ( ; ) = / 3 ( X ) . Then p y ( i ) = pSa(i) = PSpCli) = p ( l i ) = a ( ; ) . Hence p y - (1.
( c ) There is some 6 in ./ such that p6p = p. Let y = Sp. Then y y Hence y is idempotent. Clearly p - p C (68)' (Sp) = y - y . Now let ( i , X ) E y - y . Then Sp(i) = S p ( X ) and hence p ( i ) = p S p ( i ) = pSp(X) = p ( X ) . Hence ( i , X ) E p - p . Thus y - y C p'p. ( d ) There is some 6 in .Y such that p6p = p. Let y = p6. Then y y = pSp6 = p6 = y . Hence y is idempotent. Clearly, run y = ran p6 C run p. N o w let i E run p. Then i = p ( k ) for some li. Then i = P ( k ) =/36p(li) = p S ( i ) = y ( i ) . H e n c e i E rciny.Thusrun/3 & r u n y . ( e ) There is some 6 in .Y such that ( a p ) 6 ( a p )= ap. Since ran p is a cross-section of u - a , one has run a C run (ap) and (ap)' ( a p ) C p'p. N o w consider any i. Since ran a C ran ( a p ) ,there is s o m e j such that a ( ; ) = a P ( j ) . Hence apSa(i)= ap6ap(j) = a p ( j ) = a ( i ) . Hence a ( p 6 ) a= a . By the proof of part ( c ) , (pSa)-(pSa)= a-a. = Sp6/3 = S/3 = y .
CH.
91
'TRANSFORMATIONAL A N D B O O L E A N O P E R A T I O N S
131
Again consider any i. Since ( (ap)6 (ap)) ( i ) = ap ( i ) , therefore ( S a p ( i ) ,i) E (cup)-(ap) p'p, and hence pSap(i) = p ( i ) .Therefore p(Sa)p = p. By the proof of part (d), p6a is idempotent and rut? (pan) = run p. Hence y = p6a has the desired properties. ( f ) There is some y in .Y such that y - y = rqv a':(a-cw)= id. Then y is one-to-one. Also, there is some 6 in .i/ such that y6y = y . Then
c
6y = id.
(g) Assume that y ' y
p-p
= cyv
a* ( p - p ) .Then
c
a-up-pa-a c
=
a - ( r q z ? a ' : ( p - p ) ) a =a - y - y a = (ya)-(ya).
a-(eqv
(ap p a - ) ) a
Also, a -a C ( y a ) ( y a ). Hence c.4~( a - a + p - p )
c eqv ((ya)"(yaj)= ( Y C U ) - ( Y C W ) .
c
Now note that a ' M a rqv ( a - a t p - p ) holds when M is id and that, if it holds for M , then also a ' ( a p ' P a ' M ) a = a-aP-p(a-Ma)
C By induction, Hence
a-ap-p(eqv ( a - a + p ' p
c rqv ( a
a-(rqv (ap-pa-))a
(p-p))a = a'(rqv (ap-pa ) ) a c c q v ( a - a + p - P ) .
( y a )-(?a) = a - y - y a = a-(4yva*
Therefore ( y a ) -( y a ) = eqv ( a - a + p - p ) . (h) Assume that run a * run p # (8. There is some y in .i/ such that y is idempotent, ran y = run p, and run ( y a ) run a. Then run ( y a ) = run a . run p. (i) Assume that run a . run p = (8 for some a and p in 9. Now let any J # 0 be given. There is some k E J. By S4, there are a' and p' in Y such that run a' = {k) +run a and run p' = {k} +run p. By part (h), there is some y in Y such that run y = {k}. Then, by S4, there is some 6 in Y such that run 6 = J . 0
c
We now return to derivability from T B O + * * * + T B 6 .Part (d) of the following :emma supplements TB8.
I32
[CH. 9
T R A N S F O R M A r l O N A L A N D BOOLEAN OPERATIONS
LEMMA9.7: Let C Yp, . y he in Y .Assnme th(rt Y is regular and, f o r part (f 1, that 9' satisjes S5. (a) 6 (sa) ( t a ) x (sp) (tP)x,providedran /3 run a. (b)6 ( t a )( s a ) x C (tp) (sp)x,providedP'P a-a. (c) 6 k ( t a )1 s ( t P )1,providedP'P a'a. (d)6 k- ( s a ) ( t P ) l 3 ( t y ) l , p r o v i d e d P ' P C (ya)'(ya). ( e )6 (sa) (tcu) ( t p )1 = 1,provided ran a is a cross-section of P'p. ( f ) 6 k - ( s P )( t p ) - ( t y )1 6 ,l$,,k), provided i @ ran p and y ( i )
c
=y(h).
Proofi (a) Assume that ran p C_ ran a. By 9.6(b) and the regularity of Y, there is some y in ,Y such that a y = p. Then by a y = P , by TB6 and 9.4(a),and by TB4 and 9.2(a), respectively,
6
k ($3)
( t P ) x= ( s a y )( t a y ) x = ( s a )( s y )( t y )( t a ) x 3
(SOL) b
)x.
(b) Assume that p-p a - a . By 9.6(a) and the regularity of S", there is some y in .Y such that yp = a. Then by a = yP, by TB6 and 9.4(a),and by TB5 and 9.2(b), respectively, 6
1 ( t a )( s a ) s = (trP)( s r P ) x = ( t P )( t y ) ( s y ) ( $ 3 ~ ( t P ) ( s P ) x .
(c) By part (b) and 9.2(d). (d) Assume that p'p C (ya)'(ya).By 9.6(a) and the regularity of , Y , there is some S in .Y such that Sp = y a . Then by 9.2(d) and 9.4(b), respectively, 6
k (ty)l=
( t y )( s S ) 1
( s a )(tP11.
( e ) By 9.6(e), the idempotent y is in 9 which satisfies ran y = ran a and y ' y = p-p. Then by parts (a) and (c), by 9.4(a) and yy = y , and by TB4 and TBO, respectively, 6 k ( s a )( t a )( t P ) l = ( s y )( t y )( t y ) l = ( s y )( t y ) l = 1. (f) By part (c), 6 k (ty) 1 C ( t ( i / k ) )1 and hence 6 F-(t(i/k))l 6 -(ty)l. By 9.2(b) and 9.2(a),
6
b- ( s ( i / k ) )( t ( i / k ) )- ( t ( i / k ) ) l 6 ( s ( i / k ) )( t ( i l k ) )- ( t y ) l .
BY Part (4, 6
k ( s ( i / k )1 (t(i/k)) - ( t y ) l
(sP)( t P ) - ( t y )1.
CH.
91
T R A N S F O R M A T I O N A L A N D BOOLEAN OPERATIONS
I33
It follows, by TBO and the definition o f a , that 6
k-
( t P ) - ( t y )1
+ +
+
0
J&ih-).
Derivability from TBO ... TB6 TB8 will be considered next. Part (a) of the following lemma expresses the reflexivity of equality and corresponds to an axiom on p. 216 of Halmos[l3], and also to axiom (C,) of [15]. T o axioms (P,) and (PJ on p. I l l of [I31 there correspond equalities in part (b). Part (c) strengthens TB8 and corresponds to axiom scheme ( D l ) on p. 260 of Lucas[2r)l (which generalizes another axiom scheme on pp. 215-216 of [13]). T h e $-half of part (e) corresponds to scheme (D4) on p. 260 of [20].
LEMMA 9.8: Let a, p, y be in 9. Except for parts (a)and (b) assume thut Y' is rrgrrlur. A l s o , for parts (a) und (b) ussrrrne thut id is in ,/. und forpart (e) assume that 9satisjies S2. (a)8 F ( t i d ) l = l . (b)6,8 b x = ( s i d ) x = ( t i d ) x = ( s i d ) ( t i d ) x . (c) 6,8 k ( s a ) ( t p ) l = ( t y ) l , p r o v i d e d y ' y = e q v a * ( p ' p ) . (46,8 k (SLY)( t P )(sP)x = ( t y )( s y ) ( s a ) x , provided Y'Y =eqva*(p-p). (e) 6,8 k ( t a ) l ( t p ) l = ( t y ) l , p r o v i d e d y - y= eqv ( a - a + p - p ) . (f) 6,8 1 (sa)( t a )( t p ) l = ( t p ) l .provided ( p u p )f'(rcrn a ) = p-p. (g)6,8 F ( w ) ( t a ) - ( t p ) l = - ( t p ) l , provided (p'p)f'(rana)
-
=
p"p.
(h) 6,8 k- ( S L Y ) (ta) (tp) ( s p ) x = ( t p ) (sp) ( s a )( t a ) x ,provided
( p - p ) r ( r a na ) = p'p.
Proofi (a) By TB4, and TB8, respectively,
8 k1 s ( s i d ) ( t i d ) l s ( t i d ) l . And,byTBO, -l ( t i d ) l s 1. (b) By 9.2(g), 9.4(a), 9.3(f), part (a), and TBO, respectively 6,8
F ( s i d ) x = ( s i d ) ( t i d ) ( s i d ) x= ( s i d ) ( t i d ) ( t i d ) ( s i d ) x
-
-
= ( s i d ) (t i d ) ( ( t id)1 x ) = (s id) ( t id)(1 x ) = ( s id) ( t i d ) x .
Similarly, 6,8k ( t i d ) x = ( s i d ) ( t i d ) x by 9.2(h), TB6, 9.3(f), part (a), and TBO, respectively. Hence,
I34
6,8
[CH.
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
9
( s i d ) x = ( t i d ) x . Itfollowsthat
6,8
I- (s id)x = (s id) (s id)x = (s id) (t id)x
3x
by TB4. But also by TB5, 6.8
( s i d ) x = ( s i d ) ( s i d ) x = ( t i d ) ( s i d ) x C x.
(c) Assume that y y
= eqv
8
t-
a* ( p ' p ) . By TB8,
(sa)(tp)1
(tr)1.
By 9.6(g), (ycu)-(ya)= eqc ( a - a + p ' p ) and h e n c e p - p BY 9.7(d), 6 F ( s a )(tP)1 a ( t y ) l .
C
(-ya)-( y a ) .
(d) Assume that y - y = equ a* ( p - p ) .Then by 9.3(f), 9.2(e), 9.8(c), and 9.3(f), respectively, 678
I- ( s a ) (tp)(sP)x= (sa)((tp)l ex)
= ( s a )( t D ) l - ( s a ) x
= (tr) 1 * ( w ) x = (ty) ( s y )( W ) X .
(e) Assume that y - y = e4v ( a ' a + p - p ) and that .i/ satisfies S2. There is some 6 in .Y such that 6-6 = eqv a'(p-p). By 9.6(g), ( 6 a ) -( 6 a ) = equ ( a - a - t p - p )= y - y .
Then by 9.3(f), part (c), 9.4(a), and 9.7(c), respectively, 6-8 k ( t a ) l . ( t / 3 ) I = ( t a ) ( s a ) ( t D ) I = (ta)(t6)1= ( t 6 a ) l = ( t y ) l .
( f ) Assume that ( p ' p ) r ( r u n a) = pup. By 9.6(d) and the regularity of . f ,there is some idempotent y in .Y such that run y = run a. Then e q v y * ( ( p y ) - (pr))= e4v = eqv
(Y(PY)-(PY)Y)=e w ( Y Y - P - ~ ~ Y )
( p -p . (ran y ) ) = ( p -p)r ( r a n y ) = p-p.
Then by 9.7(a), by 9.4(a), and by part (c) and eqvy*((py)'(py))
= pup,respectively,
6,8
k ( s a )(ta)(tP) 1 = (sy) (ty) (tP)1 = ( S Y ) (Wr)1 = (to) 1 .
( 8 ) By part ( f ) and 9.2(j).
(h) Assume that (p'p)f'(van a) = pup.Then
CH.
91
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
135
by 9.3(f 1. part (f ),9.3(e), part (f), and 9.3(f ), respectively. 0 A {+, -, 1, s, d}-term shall be a term of L, in which any occurrence of any (ta) is an occurrence within ( t a ) l . It follows that if p is a {+, 1, s, d}-term, then\p\is local in the sense of 171. Roughly speaking, the restriction of \ L y \ to such terms corresponds to the quantifier-free part of a language, adjusted to I and ,Y, for first-order logic with equality. Using well-known methods, we now prove, for many , Y , the completeness of TBO ... TB6 TB8 with respect to equalities between such terms. a ,
..-,
+ +
+
THEOREM 9.9: Assume that ,Yis regular and satis3es S2. Let p and u be any {+, -,-, 1, s, d}-terms. If 'F p = u,then 6,s k p = u. Proof: By TBO, we can assume that u is 0. Moreover, by 9.6(f),
the first part of 9.8(b), and by 9.8(a), we can assume that any occurrence in p of any xg or of 1 is an occurrence within some (sa)xg or some (ty) 1 , respectively. By TB I , TB2, and TB6, we can also assume that any occurrence in p of any ( s a ) is an occurrence within some (sa)xE or some ( s a )( t y ) l . Moreover, by 9.8(c) and S2, we can assume that (sa) does not occur within any ( s a )(ty) 1. Applying in the usual way, first, deMorgan's laws and then disp,. tributivity one obtains terms po,...,p,. such that k p = po and such that each pk has the above properties of p, contains no and contains - only within some -(sa)xg or - ( t y ) l . Clearly, for showing that I=p = 0 implies 6,s k p = 0 it suffices to show that, for each k s r , 'F pk = 0 implies 6,s P k = 0. Consider any S r. Then pk is some T,, *.. T ~ .By 9.6(f) and , T ~ } Moreover, . 9.8(a), we can assume that some ( t y ) l is in { T ~..., we can assume that by 9.8(e) and by 9.6(g), S2 and the regularity of Y, there is no S # y such that (tS) 1 is in {T",...,T ~ } . Now assume that not 6,s k T~ * ... T , = 0. There is some U satisfying llUll d 11/ 1 1 and some f E X = ' U such that f:f'= y ' y . For any 5 < 7 ,let X , = { f a : (sa)xs is in { T ~..., , T ~ } } .
+ .-.+
- -
-
+,
I36
TRANSFORMATIONAL. A N D BOOLEAN OPERATIONS
[CH.
9
Consider any T , , , 171 4. If T, is a term (t6) 1 , then 6 = y and f E ( T 6 M . If T,, is a term ( s a ) x , , then .fa E X , and hence f E \T,\X, = ( S a ) X c . Now suppose that T, is a term - (tS)1. Then not 6,8 1 ( t y ) l . - ( t 6 ) l = 0. From TBO, S2, the regularity of 9, and 9.8(e), it follows that 6‘6 $ y - y = f - J Hence f @ ( T S ) d and therefore f E - ( T 6 ) 1 . Finally, suppose that T ~ , ,is a term -(sp)x,. Consider any a such that fa E X,. Then ( s a ) x , is in { T ~..., , T ~ } Since . not , -( s p ) x , = 0, it follows from 9.4(d) that 6,8 f (ty)l ( s c u ) ~ ap 4 y2y. Hence there is some i such that ( a ( i ) ,p ( i ) ) is not in y - y = J If: Thenfa(i) # fp(i),and hencefa # .fp. Since this holds for any fa E X,,fis not in ( S p ) X , . Hencef E \ T ~ \ X , = - ( S p ) X , . It follows thatf E \ T,) ... T,\(X,),<~,and hence that not b P k = 0.
-
- -
In passing, we note an ‘internal’ set of axioms for those equalities *, -, 1, s,d}-terms. The proof just given shows that, if .4r satisfies the hypotheses of 9.9, then any such p = u is derivable from the following: TBO, the first equality in 9.8(b), TB6, T B I , TB2, 9.8(a), 9.8(c), 9.8(e), and 9.4(d). By 7.3 of [20], = can be replaced in 9.8(e) by <. Moreover, 9.4(d) can be replaced by 9.4(g). For, as indicated on p. 2 15 of[ 131, given any idempotent y in .Y, from TBO, T B 1, and 9.4(g) one can derive ( s y ) x . (ty)l *-x < ( s y ) x . ( s y ) - x = ( s y ) x . - ( s y ) x = 0 and hence (ty) 1 ( s y )x = (ty) 1 * x. Now consider any a, p, y in .Y such that pa - C y - y . By 9.8(e), and by 9.6(c) and the regularity of . Y , one can assume that y is idempotent. Then by substituting (sp)x for x and (sa)x for x into the last equality one can derive p = u of L that are /-valid and whose terms p and u are {+,
-
-
(tr)l ( s P ) x = ( t y ) l *( s y ) ( s P ) x = ( t y ) l *( s y P ) x = ( t y ) l - (sy0l)x = ( t y ) l * ( s y )( s a ) x = ( t y ) l * ( s a ) x .
+ +
+
We conclude our discussion of TBO ... T B 6 TB8 with an example, Let .4p be the set A c s ? defined just prior to 7.1 1, and for Ly define lo-validity in the obvious way, assigning (‘Sa)to (sa)and ( ’ T a ) to (tcy). Then one can verify that each equality of one of the forms TBO, ..., TB6, TB8, 9.8(e) is lo-valid. Since ,ip is regular, it follows that each equality of one of the forms of 9.8 is also lo-valid. In contrast, as was shown after the proof of 7. I 1 , many equalities of the form TB7 are not lo-valid. We now turn to consequences of TB; = T B O t - - - + T B 8 . If a ( i )
CH.
9)
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
I37
i and k are in J and i # A , then a shall be I - 1 o n J . Parts (b) and (c) of the following lemma correspond to Halmos’ axioms (P4)and (Pd. # a ( k ) whenever
LEMMA9.10: Let a , P , y be in Y . Assume thut 9 is regular. For p u t s (b) und (c) ussidme thut .YsatisJrs S 3 und S4, u n d j h r pcirt (e) thut .Ysutisfies S 5 . (a) T B i ( s a ) ( t p ) x = ( t p ) ( s a ) x , provi&d a rind ,!3 urc idempotent, run (pa) run a , run (a@)c run p. and - r u n a . -rut? @ = @. (b) TB7 ( w )( t a ) (sp) ( t p ) x = ( s y )( t y ) x , provided run y = run a * run p. (c) T Bu (sp)( t p ) (sa)x = ( s a )( s y )(ty)x, providd r ~ t 1y = a-’ (run p) and a is 1- 1 on - run y . (d) 6,7 k ( s a )( t a ) (sp) (tp) - ( t y ) l = (sp) ( t p ) - (ty) 1, provided ran a and ran p are cross-sections of y - y . provided i # X und i’ f k ’ . (e) T B F = Proof: (a) Assume that a and p satisfy the stated provisos. Consider any distinct i and j such that p ( i ) = p ( j ) . If i fZ run p. then i E run a since -run a *-run p = @.Now suppose that i E run p. Since p is idempotent, p ( i ) = i a n d j fZ ran p. H e n c e j E run a, so t h a t j = a ( X ) for some k. Then again i = p a ( k ) E ran ( p a ) C ran a . Thus ( p ’ p ) f (ran a ) = pup.Similarly, ( a - a ) f(ran p ) = a-a. It follows that
JZf(,,,\)
TBV I- ( s a )(tP)x = (sa)( t a ) (SOL) (tp) csp, ctp)x = ( s a )( t a ) ( t a ) ( s a )( t P ) (sp) (sp) (tP)x = (tP) ( S P ) ( s a )( t a ) ( t a )( s a )(sp) (tp) x = (tP) ( S P ) ( S P ) (tP) (sa)( t a ) ( t a ) (sa)x = (tP) ( S P ) (tP) ( s a )( t a ) ( s a )x = (tp) ( s a )x by 9.2(g) and 9.2(h), by a = aa, p = pp, 9.4(a), and TB6, by 9.3(f) and 9.8(h), by 9.8(h) and TB7, by TB6,9.4(a), pp = p, and aa = a, and by 9.2(h) and 9.2(g), respectively. (b) Assume that ran y = ran a ran p. Consider first the case where -ran a . -ran p = @.Since ran a ran p = ran y z 9, since Y satisfies S3, and by 9.7(a), we can assume without loss of generality that p is idempotent and ran ( p a ) ran a. It follows that ran ( p a ) = ran a * run p = run y . We can likewise assume that a is idempotent and
-
ITx
TRANS) O R M A T I O N A I A N D BOO1 E A N O P E K A r l O N S
[CH.
9
CH.
91
TRANSFORMATIONAL A N D B O O L E A N O P E R A T I O N S
I39
(d) We adapt the proof of Theorem I .3. I8 (ii) of [ I S ] . Assume that y o n a and nin P are cross-sections of y ' y . By TBO, by 9.7(e). and by two uses of 9.3(e) and TBO one has 6
-I
(SP)
(tP) - (ty) 1 =
(SP)
(tP) (1 * - (ty) 1)
=
(SP)
(tP)((sP)(tP)(tr)l - - ( t r ) l )
= ($3) (tP)((ty) 1
-
(SP)
(tP) - ( t y ) 1).
By 9.6(e). the idempotent 6 is in ,Y which satisfies t x t i 6 = run 01 and 6-6 = y - y . Hence, by 9.7(a) and 9.7(c), by 9.4(e), by TBO and TB I ,
by 9.4(e),and by 9.7(a) and 9.7(c),respectively. 6
k (SOL) ( t a ) ( ( t y ) l
-
x) = (s6) (t6)((t6)1 x)
= (s8)x = - (s6) - x = - (s6) (t6)( (t6) 1 .-x) = - ( s a ) (ta)((ty)l *-XI.
Then, by the first equality previously derived, TB7. and the second equality previously derived, by TBO and 9.2(k), by TB4, TBO, and 9.2(k), and by 9.2(g), respectively, 677
F ( s a )(ta) ( S P ) (tP) - (ty) 1 = ( S P ) (tP) - (SOL) (ta) ((ty) 1 * - ( S P ) (tP) - (ty) 1 )
s s
- (SOL) (ta) - ( S P ) (tP) - (ty) 1 ( S P ) (tP) ( S P ) (tP) - (ty) 1 = ( S P ) (tP) - (ty) 1.
(SP)
(tP)
The lemma then follows by TB4. (e) Since ,Ysatisfies S5, the transformations ( i / j ), ( . j / i ) ,... are in .Y. We adapt parts of the proof of Theorem 1.3. I8 (iii) of [IS]. First, we assume that k' = k and prove the lemma for this special case. Since the lemma is then trivial when i' = i, let us assume that i' # i and, for convenience, l e t j = i f .Then 6,8 F - ( t ( j / k ) ) l = - ( s ( i / j ) ) ( t ( i / k ) ) l = ( s ( i / j ) ) - ( t ( i / k ) ) l
-
= (s ( i / j )) (t ( d j )) ( (t ( i l j )) 1 - (t ( i / k ) ) 1)
s M i / A ) ( t ( i / A ) - ( t ( d k ) ) l = (s(i/k))(t(i/k))- ( t ( i / X ) ) l by 9.8(c), T B l , 9.4(e), TBO and 9.2(k), and 9.7(a), respectively. I t
I40
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
[CH.
9
follows that
TH
I
t ( s ( . i / k )1 ( t ( . i / k )1 - ( t ( j / k )11 ( s ( . i / X . ) )( t ( , j / L ) () s ( i / k ) ) (t(i/k-)) - ( t ( i / k ) ) l = ( s ( i / k ) 1 ( t ( i / L ) ) ( s ( j / k ) )( t ( . i / k ) )- ( t ( i / k ) ) I C
= ( s ( i / A ) ) ( t ( i / k ) )- ( t ( i / k ) ) l
by the equality just derived and 9.2(k), by TB7, and by 9.8(g) and 9.2(k ) , respectively. By symmetry. TR,
k (s(i/k))(t(i/L))-(t(i/k))l
By TBO. it follows that TH, for 1,' = A . Now 6.7
Fa,
=
(s(,i/L))(t(j/k~)-(t(j/k))l
a
This proves the lemma
t ( s ( i / / , )()t ( i / / , ) ) - ( t ( i / / , ) ) l = (s(A/i))(t(~/i))(s(i/k))(t(i / ~( t) () i / k ) ) l = ( S ( i / X ) ) ( t ( i / A ) )( S ( / < / i ) ) ( t ( k / i ) ) - ( t ( i / k ) ) l
= ( s ( A / i ) ) ( t ( X . / i ) ) - ( t ( i / / , ) )= l (s(k/i))(t(k/i))-(t(k/i))l
by part (d). TB7. part (d). and 9.7(c), respectively. Hence 6,7 k-J&,.) ,). Similarly. 6.7 Hence, by the earlier special case where k ' = A. the lemma also holds for the special case where i' = i. The lemma itself follows from these two special cases. 0
=
a,..
kaj
I t is now fairly easy to show that, if .Y satisfies S1, ..., S S , then TH, yields the theory, adjusted to . Y , of polyadic algebras with diagonal elements. T h e axioms of that theory are obtained by adjusting to . / . in the manner indicated by Lucasl20], the axioms of Halmos [ 131. pp. 2 13-239. Details are given in [9], where it is also shown that this theory yields TH ;. We finally turn to TH,. Parts ( a ) and ( b ) of the following lemma supplement 9 . 7 ( c )and 9.8(g).Parts ( a )and (c) supplement TB9.
c
[ - E M M A 9. I 1 : As.siinir f l i t i t { (i/,j):i E I , j E I } . Y . For-purr (b) rrlso ~ i . s . s i ~ ntil ii r~i t .Y i s r-ogiilrir-. L x t a ririd p hi) it1 . Y . (a) T B , k - ( s t r ) ( t a ) - ( t p ) 1= p( ,pr - ol . i d r d ( / j - p ) r ( r - r l n a )z p-p. (b) TB , (tcr)]. X) = p(-X. (c) T B , ( t t u )
(a.
en. 91
141
TRANSFORMATIONAL A N D BOOLEAN OPERATIONS
Proof: (a) By TB4 and TBO, k0 = @ . - ( s p ) (tp)@. By TB9 and TBO, T B I , 9.2(e), and TB9, respectively, this implies that
9
k 0 = (SP)@.-
(SP!
(tP)@=
(SP)@.
(SP)
- (tP)@
(tP)@. (tp)@ It follows that 9 k @ s (tp)I and hence by
= (sP)(@--
(tP)@) =
@ a -
Hence 9 $@-I TBO, and by TBO and TB9, respectively, that 9
/ - o = @ . - (tP)l= (sa)@.-
(tP)l.
By the proof of 9.3(c), it follows that 9 0 = @. (ta)- (tp)1 and hence by 9.2(c), 9.2(e), and TB9 and TBO, respectively, that 9
t-
0 = ( s a ) O = (m)(@*(ta) - (tP)l)
= ( s a ) @ . ( s a )(ta) - (tp) 1 = @* ( s a )(ta) - (tP) 1.
ByTBO,9 k @ $ - ( ~ a ) ( t a ) - ( t p ) l . Now assume that ( p - p ) r ( r u na) # p’p. Then there are distinct i a n d j such that i E - r u n a and p ( i ) = j 3 ( j ) . By 9.7(c) and 9.2(k) and TBO, 9.7(a) and TBO, and 9. IO(e),respectively,
T B ? 1- ( s a )(ta)- ( t P ) l s - ( s a )(ta)- ( t ( i / j ) ) l s@(?,,,= @. (b) By 9.7(c) and 9.6(c), we can’ assume that a is idempotent. In the case where a is 1- 1, the lemma then holds by 9.8(a) and TBO. In the remaining case, (a-a)r(runa)# a - a and the lemma holds by part (a), TB4, and TBO. (The first part of the proof of part (a) contains another proof.) (c) By the first part of the proof of part (a) one has 9 1@ s (ta)@ Also, by TB9 and TBO one has 9 ( s a ) @ = @. Hence by TB5 also 9 (ta)@= (ta) (m)@ s @ and therefore 9 k (ta)@= @. Also, 9 k @ * x = (sa)(@.x)=
(sa)@- ( s a ) x = @ .
(sa)x
by TB9, 9.2(e), and an equality just derived, respectively. By an equality derived, 9.3(d), and an equality derived, it follows that 9
k (ta)(@. x) = (ta)(@- ( s a ) x ) = (ta)@. x = @-x. 0
Next, we show that in two important cases TB, and TB; are equivalent. Our proof is essentially contained in [ 151.
I41
I RANSFORMAIIONAI
[CH.
A N D ROO1 I AN OPFKAllONS
9
T H t x i R E M 9. 12: Ass~iirrrtlrot .Y
i s ./-, 01' c I { ( i / j ) :i E I , j E I } . TB9 is drrii.(ihlofi.oi?i TB; . /'roc!/': Consider first the special case where there are distinct i,J. .... i,..X such that I' < w and a is the product ( i , J k ) ... ( i , . / k ) . By 9.lO(e), by 9.8(g), 9.3(i), TB7, and TBO, and by 9.1O(b) and 9.8(e), respectively. one has Tlrcir
~ ( i ( , leyricility i iii
TB/
F@=@~~,~,,:J
*
...
= - ( s ( i , l / k ) ) ( t ( i ( , / k... ))
.@(j,.ln.)
( s ( i , . / k ) ) ( t ( i / . / ~ () () -t ( i , l / k ) )... ~ .* ( t ( i , . / k ) ) l ) Then it follows from 9.4(j ) that
TH ,
t-
(sa)
(@a
x) =
(S(Y)
(J&
*
-
x ) = J& x =
=ac1.
JZf. x .
Now consider the more general case where a is idempotent. Since a has finite support, (Y is a product ~ l ~ ... ~ LY, ~ x such , that each is a product ( i , J X ) ... ( i , . i k ) . where i,,, ..., i,., k are distinct. Hence for this (SLY) x) = x. case also T H Consider finally, the case where a is not idempotent. Then there are i and ;, such that a ( i ) = j # a ( j ) . Let p be the product a (jli). Then
(a- a-
0
TB F ( S L Y )(@*X ) = (sa)(JZ(i , i ) I
*
X)
= ( s a )( s ( , ; i i ) ) c J Z ( ; ! i ) * x ) = csp)(J&i).X)=
(sp)(Jd.x)
by 9.1O(e). 9.4(j), TB6, and 9.1O(e), respectively. Now if K is a support of a. then K . - { j } is a support of p. Since n has finite support, repetition of this argument yields some y such that TB; F (sa)(Jd.x ) = ( s y ) ( @ . x ) and such that either y is idempotent or y has support @ and hence is again idempotent. Hence, by the previous case, TB?
F(sa)(Jd-x)=
(sy)(Jd*~)=JZf-x.O
I n order to show that T B 9 is not always redundant, we now introduce some further notions. As usual, an ideul on I is a non-empty class of subsets of I which is closed under finite union and under inclusion. I t is trivial if it is {@}.It is proper if it differs from the class of all subsets of I . An .Y-idml shall be an ideal on I which is closed under each a-' and a*. a E Y . I t shall be pr0perfor.Y if and only if, for some a and p in 5'. {i: a(;)# p ( i ) } is not a member of it. We shall assume that I and U are disjoint. For any ,9 on I , we let = l be the (disjoint) union of the two relations { ( f , h ) E 2 x 2 : { i : f ( i ) # h ( i ) } E f } and { ( c w , ~E) . i " x . Y : { i : a ( i ) # p ( i ) } E 9). Then the
CH.
91
TRANSFORMArlONAL A N D BOOLEAN OPERATIONS
I43
restriction of - / to X X X is an equivalence relation on X , and the Moreover, restriction of = i to'5 X Y is an equivalence relation on 9. if f is closed under each y-l such that y E tY, and hence in particular if Y is an 9-ideal, then they are congruence relations on X or Y respectively. More precisely, closure of ,f under each y - l , y E Y', implies that, for any f,f' in X and p, p' in Y , iff = f f ' and p --- p' thenfp- Yf'p'. It also implies that for any a , a ' , p , p' in 9. if a = a' and p = p ' , then ap = I alp'. The notions of an algebra, set ulgebru, model, ... which were introduced in ch. 6 for I L,, I will be assumed to have been adapted to \ L / \ . In particular, the algehru cgull subsets oj"U shall be the algebra !)I = ( A , + , .,-,l',S,, T,),, + such that A = { X : X ' U } , such that ., .,-, are ,I the ' appropriate Boolean I-operations, and such that S, and T , are the I-operation ( S a )and ( T a ) respectively. a E Y . Let // be an 9-ideal. Let 91 = ( A , + , .,-,X,S,, Ta),,/ be a set algebra based on some U , i.e., a subalgebra of the algebra of all subsets of ' U . For each X E A , let C / X = { f E I : f - h for some h E X } . Assume that A is closed under C , . Let A ' , X ' , + ' ; ' , - ' , SL,Tb, be { C , X : X E A } , X , and the restriction to A ' of +, ., -, S,. Cf T , respectively, a E 9. One sees easily that 1' E A' and that A ' is closed under +', -',-', TL, a E 5'. Moreover, for each a E .i' and X E A , since f is closed under a-I, therefore C / S , X G S , C / X and hence Cf S,C, X S S,C, C,X = S a c JX s C, S , C , X . Hence A' is also closed under each SA.Therefore ( A ' , X ' , -', -', S & , T & ) , ,I is an algebra. It shall be the C, -contraction of !)I.
,
+,
+',
THEOREM 9.13: Assume that // is an .Y-ideal, 31 = ( A , t,.,-,A', S,, T J a E/ is u set ulgebru, A is closed under C f , und % ' is the C , -
contruction of ?'I. Then ?I' is a model of QTB;. Proofi Let !I['= ( A ' , ] ' , + ' , . ' , - ' , S & , T ' J o E / . Since +', .',-',SL are the restrictions of . , - , S , to A ' , therefore !)l' is a model of V ( T B O + T B I +TB2+TB6). Since C a T , ( X + Y ) = Cu(T,X+ T,Y) = C, T,X C , T,Y, since S,Cf T,X 2 S,T,X 2 X , and since Cf T,S,CfX < C J C f X= C f X , therefore 91' is a model of V(TB3 TB4 TB5) .*
+,
+
+
+
'This part of the proof extends an argument on p. 45 of [ 131. and applies to any algebra 91 which is a model of V(TB0 + ... + TB6) and any operation C on A which. for each LY in i/ and each X and Y in A , satisfies C @= @.C X > X , C ( X . C Y ) = C X . CY. and CSJ s S , C X .
I44
I RANSF OKMA I IONAL A N D BOOLF.AN OPEKA I IONS
[CH.
9
Now assume that J’ E S&T&S;TLX.Then for some h E X and for some g . .f;Y = / g a and gp x i hp. Let J = a”{i:f a ( i ) # g a ( i ) } and K = ( x ’ : . { i : g p ( i ) # h p ( i ) } . Since i/ is closed under a:: and @*, therefore J , K . and hence J K are in /. Also, if; E rlin CY . r(iti p*. - ( J + K ) . then f l j ) = g ( j ) = h ( j ) . Now let g ’ ( j ) = . f ( j ) = A ( ; ) if,; E r . t i / i t w . r . r i , i p . - ( J + K ) . let g ’ ( , j ) = . f ’ ( j ) i f j E - r ~ i n ~ ~ ~ r ~ and let , q ‘ ( , j ) = h ( j ) for any other j . Then { i : fD(i) # g ’ p ( i ) ) is included in p - ’ ( J K ) and hence is in Y.Thereforefp =y g ’ p . Also { i: g ’ o l ( i ) # hcx(i) } = @ is in f . Therefore g ’ u = ha. Hence f E SLTijSirT:r{h}.I t follows that SiTiS;TLX C SLTbShT&X. By symmetry. :)I’ is a model of VTB7. Now assume that a,p. y are in .Y. y - y = eqv a : ’ : ( p - p ) .and f E S:,T;Y’ = S,C, TOY. Then f a = i hp for some h. Let J = { k : f & ( k ) # h p ( k ) } and let K = y : : : ( a ’ : J )Then . .I is in 7 and hence K and y - ’ K are in f . For each j E run y . - K select some i such that j = y ( i ) and let g ( , j ) =.f’(i). F o r each j @ r u n y . - K , let g ( j ) be some element of U . Consider any i thus selected. Let a’ = { ( a ( k ) , k ) : k E -J} a n d p ’ = ( ( p ( k ) , k ) : k E -J}.Usingy‘y=eqva:’:(p”p) and the definition of K , one shows by induction on r < w that, for any i’. ( i , i’) E (ap-pa-) ” implies that ( i ,i’) (a‘p’-p‘a‘-)‘. Hence (i.;‘) E y ‘ y = e q v a * ( p - p ) implies that (i ,i ’) E e q u a ’ * ( p ’ - p ’ ) . By induction one also shows that e q v a ” ( p ” p ’ ) f-5 It follows that i f i h a s b e e n s e l e c t e d f o r j a n d i f y ( i ’ ) = j = y ( i ) , t h e n f ( i ’ ) = f ( i ) = g ( j ) = g y ( i ’ ) . It follows that {i’:f(i’) # g y ( i ’ ) }is included in y-IK and hence is in f . Therefore f = g y , and hence f E C,T,X= T;X‘. Therefore !)I’ is a model of VTB8. 0
+
+
We now show that. for some 9, T B 9 is not redundant.
THEOREM 9.14: Assume that each ( i l k ) is in ,Yand that there is a non-triciul .‘/-ideul proper j b r 9. Then VTB, has a model which is not u model of VTB9. Proof: Let 9 be a non-trivial 9-ideal proper for Y .T h e n some { k } is in I.Now each ( j l k ) is in 9 and hence $ is closed under each ( j / k ) - l . Therefore each { j } is in .P. It follows,that a =,p for any a , p i n Y that have finite support. In particular (0/1) = / i d . N o w let IIU(I 2 11\11. let ‘.u be the algebra of all ,subsets of * U ,and let Vl’ be the C, -contraction of ‘.u. Then T:o/l)= C, T,,,,) = C, Tid= Tid is and similarly S;oil,= SId. Hence -.!3~o~,~T~o,l~ - Tlo/,)Z’= X . Since
i t z ~ ,
CH.
91
T R A N S F O R M A T I O N A L A N D BOOLEAN OPERATlONS
145
proper for Y there is some a in Y such that not a ,id. Since I)CIll 3 11111, there is some f E X such thatf( i) f f(j ) for any distinct i and j. Let X = C, {fa}.Then X E A ' . Since f l f a would imply that a f i d , therefore f @ X. Since f E SAX, therefore SkX differs from X. Therefore S&(-S:o/l)T,&l)- T:n/l)X'. X ) = Si (A" . X) differs from -S~'o~l)T~',)~l)T;,)/J' . X = X' . X . Hence 91' is not a model of WTB9. By9.13,?If isamodelofWTB;.O 2-
2-
2-
When .5" is A c s , then { J w: J is finite} is a non-trivial Y-ideal proper for Y . Hence when Y is A c s , then TB9 is independent from TB;. For cases not covered by 9.12 or 9.14, we do not know whether TB9 is independent from TB;. In particular, the case where I is infinite, K > w, and .Y= .TKis not covered, since there are no nontrivial Y-ideals proper for Y = .FK. We now turn to the problem of the completeness of T B , for the special case where Y is Acs. To link up with ch. 7, we define inductively a mapping, or translation, tr which associates with each term p of L,, a term t r p of LACS as follows: t r d is ( t ( O / l ) ) l t, r 1 is 1 , and t r p is p for each variable p ; also, tr ( p p ' ) , tr ( p p ' ) , and tr - p are ( t r p t r p ' ) , ( t r p t r p ' ) . and - tr p respectively; furthermore, fr C , p. t r p p , and t r q p are ( s ( i / i + l ) ) ( t ( i / i +1 ) ) t r p , ( t ( + l ) ) t r p , and ( s ( + l ) ) t r p respectively. It follows from 9.l(a) and 9.l(c) that \tr p\ =\ p\ for each term p of Lw .
+
+
-
-
LEMMA9.15: L e t p be a term of L,, a n d let i # j . (a) TBi., k t r d , J = ( t ( i / j ) ) l . (b) TBG, k t r (cl(dzJ P ) ) = ( S ( i / j ) ) t r p . (c) TBiC, k tr ( d l l . c z p )= ( t ( i l j ) )t r p . Proofi
(a) Assume first that i < j. Let p ( k ) =j for i S k S j and let p ( k ) = k otherwise. Let a ( k ) =j for i < k s j and let a ( k ) = k otherwise. Recall that d, and d,, are the term Cl+l
... C,-l(q'd
By 9.8(c) and induction,
*
q'+'d *
... - qJ-'d).
TB&, l- t r ( q k d )= (t(k/k+ 1))l. Hence, by 9.8(e) and induction, TB,,
-
t r (q'd q'+'d
- - q ,-Id) = ( t p ) 1.
I46
[CH.
TKANSFOKMArlONAL A N D BOOLEAN OPERATIONS
9
By 9.10(b) and induction, TBY,,~ 1 t r ( c i + , ... c j - , p ) = ( s a ) ( t a )t r p . Finally. since pa = p and ( i / , j ) - ( i / j )= eyu a ' : ( P ' P ) , therefore by 9.4(a) and 9.8(c). respectively. T B T ~1 , ~( S L Y ) ( t a )(t/3)1 = ( s a )( t p a ) l = ( t ( i / , j )) 1 . For i > , j the proof is similar. ( b ) By part (a), by run ( i / i + 1 ) = r u n ( i l j ) , 9.7(a), and 9.3(f), by 9.4(a) and the idempotency of ( i / j ) ,and by 9.2(g), respectively,
1'B,,.,<
~ ~ . ( c ; ( d , , -= p )( )s ( i / i + I ) ) ( t ( i / i +I ) ) ( ( t ( i / j ) ) l * t r p )
= ( s ( i / j ) )( t ( i / j ) )( t ( i / j ) )( s ( i / j ) )r r p = ( s ( i / . j ) ) ( t ( i / j ) ) ( s ( i / j )f) r p = ( s ( i / j ) ) t r p . ( c ) By part (a), by 9.3(f), run ( i / i + I ) = r u n ( i l j ) , and 9.7(a), by TB6 and the idempotency of ( i l j ) .and by 9.2(h), respectively,
TB-,,.,<
t r ( d i j * c i p ) = ( t ( i / j ) ) l* ( s ( i / i + I ) ) ( t ( i / i + 1 ) ) t r p
= ( t ( i / j 1 1 (s ( i / j) ) (s ( i l j 1 1 ( t ( i / j1 ) t r p = ( t ( i / j ) ) ( s ( i / j ) ) ( t ( i / j ) ) t r p(=t ( i / j ) ) t r p . 0
L E M M A9.1 6 : For t>rich t e r m r of L.,,.,sthere is u t e r m p of L,, such thtrt T B , , , < r = tr p . Proof: 1-et p be any term of L,,. Then ( s ( + I ) ) t r p is t r q p . and ( t ( + 1 ) ) tt-p is tr Q p . Also
t
TB-(,.,
=
id. 9.4(a).9.7(b). and 9.3(f),respectively.
TH;<.,< t ( s ( l l ) ) x =(tid)(s(-I))x = ( t ( l I ) ( + l ) ) ( s ( ; I))x= ( t ( + I ) ) ( t ( l -
I ) ) ( S ( A
-
I))x
= ( t (+ 1 ) ) ( t ( O / I ) ) ( S ( O / I ) 1 x = ( t (+1 ) ) ( ( t (0/1) ) 1 x).
I n a related manner one shows that
rB;,.,s
k
(t
1 ) x = ( t (0/ 1) (s(0/I ) 1 (s(+ 1 ) ) x = t ( O / l ) l* ( s ( + I ) ) x
' I t follow\ that the transformational operations resulting from Acs = c / { (A I ) . ) . ( i / j ) : i -. O . j < W } also result from the smiiller semigroup .Y = d{(+ I ) . ( i / j ) :i < w..; < w } . Letting u = (Oil) and p = (+I). one sees that the conclusion of 9.6(h) fails foi- . f . I t is therefore probable that the conclusion of 9.7(a)fails for . Y . and
(+I
hence that TB, is not complete.
CH.
91
147
r R A N S F O R M A T l O N A L A N D BOOLFAN O P E R A I IONS
and hence that TB;,.,
-
L (t(-
1 ) ) tr p = tr ( d qp).
Furthermore, if i # j then 9.15(b) and 9.15(c). respectively. yield: TB;I,, TB-4 ('s
k ( s ( i / j ) ) t r p= fr
(ci(dij. P ) ) .
(t(i/j)) t r p = t r ( d i j - c i p ) .
By the definition of tr, and by induction, it follows that the lemma holds for those terms 7 of LACS.which contain no ( s a ) or ( t a ) other than those where a is either ( + I ) or (A 1) or ( i / j ) for some distinct i a n d j . By 7.5, TB6, and 9.4(a), the lemma then holds for every term 7 of LACS. 0 LEMMA9.17: I f p = p' is any equality in the set E i q c f ch. 8 , then TB,4,.,s f r p = tr p ' . Proofi If p = p' is in BP, then t r p = t r p ' is p = p' and is in TBO. If p = p' is in l(a), l(b), l(c), or l(d), then TB;c,s t r p = f r p ' by 9.2(i), TB4, 9.3(e), and TB7, respectively. If p = p' is in 2(b), 2(c)', 2(d), 2(f)', or 2(g), then TBiC, k tr p = tr p' by TB2, T B l , 9.10(c), 9.7(a), and 9.7(b) and 9.8(b), respectively. If p = p' is in 3(a)' or 3(b), then TB,, tr p = tr p' by 9.7(e) or 9.8(f), respectively. If i j , then 9.15(a) and 9.15(b) yield:
t
+
1 t r ( d i j . c , ( d i j . x )= ) (t(i/j))l . ( s ( i / j ) ) x .
TB;., TB&
k tr(d,, - x )
.
= (t(i/j)) 1 x .
Hence, by 9.3(f) and TB6, if p = p' is in 3(c), then TBiC, k p = p ' . By T B 9 and TBO, by 9.2(e), and by TB9, respectively, one has TBAcs t-
@ a
( s ( + 1) )x = (s(+ 1) )@- (s(+ 1) 1x = (s(+l))(@.x)=pl.x.
Hence if p = p' is in 3(d)', then TBAcsk tr p = tr p' . T h e completeness of TBAcsnow follows easily from results already proved. In view of [9], it implies the completeness of the corresponding axioms for polyadic algebras with diagonal elements.
THEOREM 9.18: lf 7 and then TBAcsk 7 = 7'.
7'
are any ternis of L..q,,strnd
if
'F 7
= 7',
I48
rRANSFORMATIONAL A N D BOOLEAN OPERATIONS
[CH.
9
By 9.16, there are terms Proofi Consider any terms T and r' of p and p' of L, such that TB,,, k r = tr p and TB;,, k T' = t r p ' . Now assume that b T = 7'. Since \r\ = \tr p\ =\p\ and since \TI\ =\tr p'\=\p'\, therefore !F p = p ' . By 8.10, p = p' is derivable from E;q. Hence by 9.17 and induction, TBAcs fr p = tr p'. It follows that TBAcst- 7 = 7'. Recall that 8.10, the completeness theorem for E(pq,was proved by using 5.9, the completeness theorem for Epq.Hence our proof of the completeness of TB.,,.,yis twice removed from a direct completeness proof.
CHAPTER 10
THEORY OF TRANSFORMATIONAL RELATIONS
For convenience, it will be assumed throughout this chFpter that 11111 3 3 and that Y satisfies the conditions SO, ..., S7 which precede 9.5. Quite often, as will be evident, some or all of these assumptions are unnecessary. (For another set of assumptions, see I 1 .S.) One purpose of this chapter is to prove the completeness of the set TB? of ch. 9 with respect to those inequalities p s cr which involve only transformational operations. By the equivalence proved in [9], this result applies also to the theory, adjusted to .Y, of polyadic algebras with diagonal elements. Another purpose of the present chapter is to prove the completeness of a certain set T, of equalities when TYis interpreted as describing transformational operations under composition. The set Ty has a closely related second interpretation which seems to be simpler and which we shall now bring out. Let A'= ' U and 2' =Yxd.ForanyM fxf,let
c
=
{(f, h) E
2 x 1
M
c f-11)
= { ( f , h ) E ?I':f(i)=h(k)foreach(i,k) E M } .
Then [ M I ] - = E M - ] . Also, for example, the following hold: uan = { ( f , h ) E
[(.-I]
=
[all-
22:a
c f-h}
={(fa,f):fE
u a a = w, j - ) : j -E
IIPP'yy-Il= { ( f , h ) E 2,f':fand
c
=
{(f,fa):fE 1 ) .
X}.
c m.
h agree on ran p . ran y } .
We let R 2X be a transformational relation (resulting f r o m S") if and only if R is a relative product R,,R, _ _R. , such that each R , is either some [Tan,a E Y ,or some Ba-1, (Y E Y .Thus, the transformational relations form the closure under relative product of I49
IT0
I H L O R Y O F I K A N S I - O K M A I I O N A l KFLATIONS
+
[ C H . 10
{[IcYn: (Y E . I > { ~ ( Y - Ja : E .Y}. They also form the closure, under relative product and under converse. of {[IaII:a E .Y>. Now for each R 2 ?J. let R3' be the 1-ary I-operation which, for each X C 1. satisfies R:!'X = {.fi ( f , h ) E R for some h E X}. Then R:? R':!: implies that R = R'. Also R*'R'*'= (RR')'?. Furthermore, ( S a ) = [IaU:;: and ( T a ) = [Ia-U". It follows that the converse of * is an isomorphism of the semigroup of transformational operations under composition onto the semigroup of transformational relations under relative product. Our set T, will therefore be applicable to either semigroup. T o prove the completeness of TSt,we shall prove the following normal form theorem: For any transformational relation R resulting from 9 one can derive from Tr an equality which expresses that R is a relative product [ [ u- twJII pnUy,,yiy,y;DU6 -81. We conclude this chapter with a few set-theoretical results concerning transformational relations (operations). Some others are given in [lo]. We begin by forming a language I-'> for transformational relations under reiative product, or for transformational operations under composition. T h e (individuul)constants, or 0-place function symbols, shall be those [a] and [a-] such that a E Y . (In ch. 9 we could also have used [a] and [ p ' ] in place of (SLY) and (tp); for a = p - only the former are the same.) The only other function symbol is one which has 2 places. Starting from the constants, we form further terms (of L1;) by inserting the 2-place function symbol between terms already formed and enclosing the resulting expression by a pair of parentheses. Thus all terms of LS are constant terms, i.e., contain no variable. I n this chapter, unless we say so explicitly, p , cr, ... shall be terms of LT. As before, we shall use juxtaposition of names for expressions to indicate juxtaposition of the expressions named. Also, usually we shall tacitly use an axiom scheme of associativity as well as suppress pairs of parentheses associating to the right. Thus, usually we shall give no indication of parentheses. As to the 2-place function symbol, when parentheses are ignored then its occurrences alternate with occurrences of constants. Thus we may, and shall, neglect to indicate its occurrences. Thus, for example, [a][p], [ a ] [ P ] [ y - ] ,... shall be terms. Let U be given. We assign (Sa)to [a] and ( T a ) to [a-I. We also assign Ua1 to [a] and Ua'D to [a'].T o the 2-place function symbol we 1
C H . 101
THEORY OF T R A N S F O R M A T I O N A L RELATIONS
1.51
assign the composition operation and also the operation of relative product. Since a = p- implies that [Ian = Up-1 and (Sa)= ( T p ) , there is thus assigned to each term T of LT, a unique transformational operation \T\ and a unique transformational relation \T\:::.Evidently, (\T\*) * =\A. We shall say that T denotes \T\ and \T\:::. An equality p = u shall be valid, o r 'F p = u,if and only if\p\=\u\ for each U . Hence 'F p = u if and only if\p\,, = \u\:!: for each U . We now introduce a set T, of equalities of La. Let TO be the set of equalities ~ ( u T )= pa)^. Then T, shall be the union of TO and of the following seven sets of equalities, where a , p, y are in .Y.
T 1. [ a ] [ a ' ] [ a=] [ a ] . T2. [ a - ] [ a ] [ a=- ][ a ' ] . T3. T4. T5. T6.
[aI[Pl= rap]. [ p ' J [ a -= ] [p'a-1. [ a ] [ a - ] [ p I [ p - [l = y l [ y - l provided , aa-j3p' [ a - ] [ a ] [ P - ]= [ P[]y - ] [ y provided ], eqv
=yy-.
( a - a p - p )= y - y .
T7. [ a ] [ a - ] [ p - ] = [ p[]p ~ ] [ / 3 l [ a l [ provided a-l. i d + a a - p - p = p-p. We let 1 be derivability from T,. where derivability from a set of equalities is construed as in chs. 4, 8, and 9. One can verify that if u = T is in Ty then k u = T. (It may be helpful to note that aa-p p= y y - is equivalent to ran a . run p = ran y , that eyv (a-cyp'p) = eqv ( ~ y - c y + + ~ p )and , that i d + a a - p - P = p - p is equivalent to ( p - p ) r ( r a n a )= p - p . ) It follows that if U = T then 'F u = 7 . Hence T, is sound for the two intended interpretations. For any p, let the dual p'l of p be the result of first inverting p (considered as a finite sequence of symbols) and then replacing each constant [ a ]by [ a - ]and vice versa and each left parenthesis by a right parenthesis, and vice versa. One can verify that if u = T is in T, , then either some u'= T' or some T' = u' is in T:, such that u' and T' yield udand T~ respectively by uses of TO. Induction then yields the following prooftheoretic duality.
LEMMA10.1: If
k u = T,then k u"= 7''.
For each of the relations [Ia'aJ and [Iaa-pp-J. where a and p are in .Y, we shall now select a term denoting it. Let any a - a be given such that a E Y . I f a - a = id, then the constant [id] = [ a - a ]denotes Ua-aU.
IS7
T H F O R Y OF 1 R A N S F O R M A T I O N A I R E L A T I O N S
[CH.
10
If a - a # id and hence a - a differs from each 6 and each 6', we select some y E .Y such that y - y = adu and let [ a - a ]be the term [ y - l [ y l . which denotes [ a - a l . Now let any aa-pp- be given such that (Y E .Y and p E , Y . If aa-pp- = id,then the constant [id]= [aa-pp-l denotes [Icua-pp-1. Now suppose that id# aa-pp-, and hence (UY-PP-differs from each 6.6.. and 6-6. Suppose first, that aa-pp# @.Then. by 9.6(h). there is some y E ,Ysuch that y y - = aa-pp-. We select one of these y and let [aa-pp-1be the term [ y ] [ y - lwhich , denotes [[(~(v-pp'l]. Suppose now that aa-pp' = @.Then, by 9.6(i), for each k , the thnsformation ( D k ) satisfying (D k ) ( . j ) = k for each j is in .Y . Then we let [au-p p ' ] be the term [ (0/ 1 ) (0/ I 1- I [ ( D 0 ) (D 0)- 1 , which denotes Uau-pp'D. Parts (b) and (c) of the following lemma show that the particular selections made d o not matter.
L>EMMA 10.2: Let a and p be in 9. (a) k [ a u - ]= [a][cu-]. (b) t- [aa-PP-l= [aa-l[PP-l. (c) k [ a - a ]= [ a - ] [ a ] . (4k [ e w ( a - a P - p ) l= [a-al[P-PI. (e) k [aa-I [ P p ' l = [PP'I[aa-l. ( f ) -t [a-a"'PI = [P-PI[a-aI. (g) k [ a a - ] [ p ' p= ] [p'p][aa-],prouided ( p - p ) f ' ( r a na ) = p-p. Proof: Henceforth, TO will be used tacitly. (a) Suppose first that a a - = id and hence [ a a - ]is [id]. Then, by T 3 and T 5 respectively,
-t [id= [idJ[id][id][id]= [al[a-l. Suppose now that a a - # id and hence [aa-1 is [ y ] [ y - lfor some
y E .Y such that y y - = aa- . Then, by T 1 and T 5 respectively,
1 = [ a l b -1. (b) Consider first the case where aa-pp' # 9. Then by 9.6(h), aa-Pp' = y y - for some y E 9'Then . [y"-
1 = [rl[r-""-
k [ a a - I [ p p - l =b l [ a - I [ P l [ P - l =[rl[r-l= [aa-PP'I by part (a), T5 and part (a), respectively. Similarly,
-I
[PP-"a-I
= [aa-PP-I.
CH.
101
153
THEORY O F TRANSFORMATIONAL. RELATIONS
Consider now the case where aa-pp- = 9. By S4, there are an, a I , a;, a2 in 9 such that run a,,= - { 0 } + r u n a , run aI= - { 1) run a , run a6 = - (0, I} +run a, and run ap= (0, I} +run a. By the previous case, I- [aa-I = [a;a;-a?a,l= [a;a;-][a*ai]
+
= [a"c~,aic~il[apa
Similarly, there are Po,pi,p2 in .Y such that run Po = -{O} run P1= -{ 1) +run @ , r u nP2 = (0, I} + r u n P and
+run P,
I- [PP-I = [PoPiI[PIP;I[P2Pil. Since 11/11 2 3, therefore -{O} ---{I} # 0 and hence no two of the a$,Po,PI,P2 are disjoint from each other. Hence by ranges of ao,al,
the commutativity result for the previous case
k [ana~I[aiaiI[a2a; I[PoPiI[PiP;I[P2PiI
= [anaOl[PnPO I[aiai I[PiP; I [ a 2 + i I[P2P2 1.
By 9.6(i), there is some y in Y such thatran y = (0, I}. By the previous case, t- [anaiI[PoPiI = [anai,PoPiI = [(0/1) 1 9
t- [aiaiI[PiP;I = [(1/0)( l / O ) - I , 1 [a2ail[P2PiI = [yy-l.
t- [ ( I N )
(I/O)Y l [ Y Y - l =
[(D 0) (D 0)-
I.
It follows that
I- b - l [ P P - l =
[ ( O / l ) (o/l)- "D 0) (D 0)- 1
(c) Suppose first that a-a = id and hence [a'a] is [id].Then, by T 3 and T6 respectively,
k [id= [idl[idl[idl[idl= [a-][a]. Suppose now that a - a # id and hence [a-a]is [y-][y] for some y E Y such that y ' y = a-a. Then by TI and T6, respectively,
I- [r-l[rl= [Yl[-Yl[y-l[yl= [a-"I.
I54
[CH.
T H E O R Y OF T R A N S F O R M A T I O N A I . REI.ATIONS
(d) By 9.6(g),there is some y in ,Y such that y - y Then by part (c),T6. and part (c), respectively,
= equ
10
(a'ap-P).
k [ a - a I [ P - P l = [ a - l [ a l [ P - I [ P= I [ r - l [ r l= [?-?I. (e) BYpart (b). ( f ) BY part (4 (g) By part (a),part (c). and T 7 . 0 LEMMA10.3: L e t a . p. y . 6 he in .Y. (a) [ p p y y - ] [ a ]= [ a ] [ a - ' ( p p - y y - ) ] .provided a is 1 - 1 on - a- 1 (run /3. run y ) . (b) [ a ' ] [ P P ' y y ' ] = [ a - ' ( p P ' y y - ) ] [ a - ] , provided a is 1 - 1 on -,-I (run P . run y ) . (c) k [(."-PI = [ePa*(p-P)"l. (4k [ p ' p l [ a - l = [ a - l [ e q v a ' ( p - P ) l . (e) k [ a ] [ y y - 6 6 -= ] [p][yy'66-],prouidedayy-66' = Pry-66'. Proc?f: Henceforth 10.2(a), 10.2(c) and, when aa-pP'= 9, 10.2(b) will often be used tacitly. (a) Consider first the case where a - ' ( P D - y y - ) # 9. By 9.6(h), there is some p' in -5' such that run p . ran y = ran p'. Then, by S6, there is some 6 in Y such that 66 = a-'( p ' p ' - ) = a-*(P P ' y y - ) . By using 10.2(a) and making the obvious changes in the proof of 9.10(c) one can then show that k [/"/3"l[aI= [a1[66'1and hence
k [PP-rr'"I=
[al[a-'(PP-rr-)l.
Consider now the case where a - 1 (PP'y-y') = 9. By 9.6(i) if Pp'y-y' 9,and by S4 and 9.6(h) if PP-yy' # 9 , there is some 6 in .Ysuch that ran 6 = ( ( ~ ( 0 ) ) (ran p .ran y ) . Also, there is some 6' in .Y such that ran 6' = -{a(O)}. Since run a . (ran p . ran y ) = 9, it follows that 6'6'-66- = P P - y y - . Then by 10.2(b), the previous case, the previous case, and a-l (pp-y-y' ) = 9, respectively,
=
+
k [ @ ' y y ' ] [ a ] = [6'6'-][66-][a]= [6'6'-][a][(D 0) ( D 071 = [ a l [ ( O / l ) ( O / l ) - l [ ( OD) ( D 01-1 = bl[a-'(PP-rv-)l. (b) By part (a)and 10.1. (c) By S2, there is .some y in Y such that y - y = eqv a* ( p - p ) . B y 9.6(g), (ya)-(ya) = equ (a-ap-p). Also ( y - y ) r ( r a n a )= y - y and
CH.
101
THEORY OF TRANSFORMATIONAL RELATIONS
155
hence id+ a a - y - y = y - y . Then
k raI[P-I[Pl[a-l = r ~ l [ P - 1 [ P 1 r ~ - l r I~ l r ~ -
= r ~ l r ( r ~ ) - l r r ~ l r a~-~l =l ~ ~ - l ~ r - l r r l r ~ l r ~ - l = ~ r " l ~ r l r ~ l ~ ~= - l[Yr -~l rl rrl ~r ~- ll[ ~ - l
by T 2 , T6, T 3 and T4, T7, and T 2 , respectively. Hence by T 1. 10.2(f), the equality derived above, T 1, and 10.2(c), respectively,
t- [a"'PI
= [ ~ l r ~ - l [ ~ I r P - I= r P[ 1~ I r P - I ~ P l r ~ - I [ ~ l = [ r - l ~ r l ~ ~ l [[r-l[rl[al= ~ ~ l ~ ~ l[eqv = a* (P-P)l[al.
(d) By part (c) and 10.1. (e) Consider first the case where yy-66- # 0.Then by 9.6(h), there is some y' in 9 such that y'y" = yy-66". Since ayy-66- = P y y " s s - , therefore ay' = b y ' . Hence by 10.2(a), T3, ay' = P y ' , T3, and 10.2(a). respectively,
t-
ral[yy-88-1= [al[y'l[y'-l = [ar'lrr'-l
= [Pr'l[y'-l= [Plrr'lrr-l = "rr-ss-1. Consider now the case where yy-86' = 0.By S5, ( O / a ( O ) ) is in 9. Then I- [alrrr-ss-l= [a"D 0) ( D o)-lr(o/l)( o / l ) - l = r(O/a(O))Ir(DO)(DO)-Ir(0/1)(0/1)-1
= [ ( O / a ( O ) ) I [ ( 0 / 1 ) ( O / ~ ) - I r ( D O )(D 0)-I = [id][(O/I)(O/ l)-l[(DO)(DO)-l
by 10.2(b), the previous case, 10.2(e), and the previous case. respectively. Similarly, Hence
t- [p][y-ss-l= [idl[(O/l)(O/l)'"D t-
0) (D 0)-1.
ra1rrr-ss-1= [Pl[rr-ss-l. 0
Consider any J and any M such that M = equ M. Recall that K is a cross-section of M if and only if for each i there is exactly one k E K satisfying (i, k) E M. We shall say that a cross-section K of M favors J if and only if, for each k E K , if there is s o m e j E J such that (j,k) E M, then k E J. Also recall that the confinement of M to J is
I56
T H E O R Y O F I KANSFORMATIONAL. RELATIONS
the relation M r J
=
id
[CH.
10
+ ( M . 2 J ) .We let
;(I+ ( M . ' { i : f o r e a c h k , i f ( i , k ) E M.thenk E J } ) be the strict cotzjinotnent of M to J . Evidently. if M' is the strict confinement of M to J . then M'
=
c MFJ = e
eyu M '
4 (~M r J ) .
Again consider any J and any M such that M = equ M . Let M,, MPJ and let M2= M; be the strict confinement of M to -J. Also let M,',be the strict confinement of M t o J and let
=
MI
= id+
( M . - MI,. - M i ) .
TheneqvMi = MIandM=M,\+MI+M;.AlsoM,,= M l \ + ( M I f J ) . Now let KI be any cross-section of M i which favors J , and let
M,
=
M;r ( - J
+ K ; 1.
T h e n M , = e y v M , . Alsoequ ( ( M i f J )+ M I ) = MI. Hence r4u ( M , , + M , )= eqv (M;,+(M;rJ)+M,)
=M;,+ eyu((M,'t'J)+M,)
Therefore ( e q u (M,,+M , ))
=y;+~,'.
+ M, = M:,+ M i + M i = M
We call ( M I , MI, , M , ) a J-decomposition of M . For illustration, let I = o,J = (0, 1,2,3,4}, and M = equ { ( 1 , 2 ) , (2.3), (3, S ) , ( S , 6 ) , (4,7), (8,9)}. Then M,,= M r J = equ { ( 1 , 2 ) , (2.3)}, and thestrictconfinementM,= M;ofMto-.Iisequ{(8,9)}. The strict confinement M,!, of M to J is id and hence Mi = equ { ( 1 , 2 ) , (2.3), ( 3 , s ) .( S , 6 ) ,(4,7)}. Then any cross-section K ; of Mi which favors J contains exactly one of { 1,2,3} but neither 5 nor 6, contains 4 but not 7, and contains every element of -{ 1,2,3,4,5,6,7}. There are three sets K ; satisfying these conditions. For these, the relations M , = M ; r ( - J + K ; ) are equ { ( I , 9 , ( S , 6 ) , (4,7)}, eqv ((2, S ) , ( S , 6 ) , (4,7)} and eyv { ( 3 , 5 ) , ( 5 , 6 ) , (4,7)}. respectively. Observe that for each of these three relations the set - { S , 6,7} is the only crosssection which favorsJ. We now generalize this last observation.
CH.
101
I57
T H E O R Y OF T R A N S F O R M A T I O N A I RE1 A T I O N S
LEMMA10.4: Assume that M = eciv M und that ( M , , ,M I , M,) is ( I J-decomposition of M . Then the only cross-section of M I \c.hic.hfiivor.s J i s J + { i : f o r e r i c h k , i f ( i , k ) E Mthenk E -J}. Proofi Let ( MI,,M I , M,) be a J-decomposition of M = eqv M . Clearly, for each i there is at most one k E J such that ( i , A ) E M I . Hence MI has only one cross-section favoring J, and J is a subset of this cross-section. Also, if i E -J, then i belongs to a cross-section favoring J if and only if k E -J for each k satisfying ( i . k ) E M . 0
LEMMA10.5: Let a und P be in .Y. There uro a,,,a1,a2.P' in .Y such that (a;ull,u p , , a ~ a , )is ( I (run P)-decomposition of C Y - ~ , a 1 is idempotent and run a I is that cross-section of a;tr, \t'hich favors run P , run P' = run p + - run a I , und 1 [PB-I [ t ~ - a I = [~,~,,"Il[p'p'I[..ck!I. Proofi Let a and p be in .Y. By S7 there are a,,,y . a p .in ,Y such that (a,;al,,y ' y , aia,) is a (run P)-decomposition of a'a. By 10.4, the unique cross-section of y - y which favors run P includes run /3, and hence, by S4, is run 6 for some 6 in ,Y. By 9.6(e), the idempotent a l satisfying a;al = y ' y and run a1= run 6 is in 9. By S4, there is some p' in .Ysuch that run P' = run p -run a l . Since run a I includes run P. therefore run a I . run p' = run /3 and hence aIa;/3'p'- = Pp'. Since (a,a,)r(run p ) = aia,, and since run p C run p' and run /3 run a l , therefore (a;a)r(run p ' ) =a;ull and ( a ; u l l ) P ( r u n a I )= a ~ a l l By . 10.4. run /3'= run p+ { i E - r u n p: for some k , (i, k ) E a - a and k E run P } . Hence ( a ; a , ) r ( r u n p ' ) = a;a,. By 10.2(b) and 10.2(d), 10.2(g), and T4 and a l u l = a 1 and T I . respectively, it follows that
+
k [ P p - l [ a - 4 = [ala;l[P'P'- I [ a i ~ o l [ ~ ; ~ I 1 ~ ~ : ! ~ 2 1 = [ ~ , ~ l , l [ ~ , ~ ; l [ P'P'-"2-~21 ~;~ll[ =~
~,~ol~~Il~P'P'-I~~2-~~1.0
LEMMA 10.6: Let a , P. yo, y 1 be in Y . (a) I- [PP-I[a-al[PP-l= [PP-l[(a-a)r(ran P)1. (b) I- [YOYOYIY; I[a -a1 PP - 1 = [YOYOYIYi I[ PP -11 ( a -a )r (run P ) provided (a-a)r- (ran y o . ran y l ) = a - a . (c) F [rlnorlr;l[~-~l[Pl = [rorirlr;l[P1[P-l(a-~)l. provided (a-a)r- (ran y o . ran y l ) = a - a . 1 9
I58
I H t O R Y OF TRANSFORMATIONAI R t L A T l O N S
[CH.
10
Proofi (a) Let ao,al.a2.P’ be as in 10.5. By 9.6(c) and 10.2(c) we can assume that a2 is idempotent. Now a i a , is the strict confinement of a‘a to - r a n P . It follows from 10.4 that (a;a2)f‘(ranal) = a;a2, and from 10.4 and the idempotency of a2 that a 2 ( i )= i for each i E (run P -run a I )= run p’. From a2p‘ = P’ it follows that
+
k [P’P’. I[aia.I[P’P’- 1 = [ P ’ I [ p ’ - ~ 2 1 [ ~ 2 P ’ I [ P1’ = [P’I[P‘-Irp’I[P’-l= [P”’‘]
by T 4 and T3. a$’ implies that
=
P ’ , and T1, respectively. Similarly, a I a l= a 1
Fr ~ l ~ ; l [ ~ ; ~ l l= [ ~[alal-l. l~;1
By 10.2(b)and 10.2(d). 10.2(g)and 10.2(e). the equalities just derived, 10.2(b).and 10.2(g).respectively, it follows that
F [ pp -][a -a”P
-1=
IIP’P’ - I[aOao”
;a II[~2-~2”1~;1[ P’P’ - 1
= [ ~ l ; ~ o I [I[a;all[a,a;l[P’P’ ~I~; - “2az”‘P’-
1
= [ ~ ~ ~ l l ~ [ ~ l ~=; [~( a[ -pa’) pr (’r -~ P)I[PP-I ~n = [ p p -I[
-cy
)r( r f I lpl )I.
{ i : ( i , . j ) E a‘a for s o m e j # i } . By S4, there are P’ and rill1 p’ = run P + - J and run P” = run P + J . Evidently. (CU - C Y ) l-( ~ ( I I Ip‘ ) = ( CY - CY ) r ( r u n p ) . Consider first the case where yoy,;yIyi # 0.By 9.6(h). there is some y in .f such that y y - = YIIyfiylyj. Since ( a - a ) r - ( r u n y ) = a‘a, therefore .I C -run y and hence rlin y run P’. By S4. there is some y ’ in .Y such that r r i n y ’ = r c i n y + ( J . - r u n P ) = r u n y + - r u n p ‘ and hence yoy,iyIyi = y’y’”’P“. Then by 10.2(b), part (a), 10.2(g), and 10.2(b),respectively.
( b ) Let J
=
p” in .Y such that
1[
~
o
Y i~Y ii
CYI[ PP‘ I = [Y’Y”I[P’P” I[a txI[P’P‘’ I[P”P”-1 = [ r ‘ y ’ - ~ [ ~ ’~~[’ (- ~ - ~ ) r (P)I[P”P”-I run
I[ P ” P ” (~a- a 1r (ran P ) 1 = [ ~ o ~ i iyyi iI[PP‘ I[ ( a - a1r (run P ) I.
= [Y”” 1[ P‘ p”
Consider now the case where yoy,;y,y; = YIIYI;YIY;P’P‘- we have
F [Y~YGYIYII
=
0.By
10.2(b)and YoyOylyi
= [yoyiI[~i~iI[P’P’-l.
cn. 101
I59
T H E O R Y OF T R A N S F O R M A T I O N A L RELATIONS
We then proceed as in the previous case. (c) By T 1, part (b) and 10.2(g), and T 1, respectively,
t- [ yo~ o ~ i ~ ; l [a -a I[PI = [roro~lriI[a-aI[PP‘I[PI
= [ Y o Y ~ Y I Y i ~ [ ( a - a ) r ( r aPn ~ I ~ P P - I [ P I = [YOYO ~ i I[ (01-a) ~ i W a n P ) lip].
Now equp* ( p - l ( a - a ) )= equ (Pp-a-app-)= ( a - a ) r ( r a n p ) .
Hence, by 10.3(c),
t- [ ( a - d r ( r a n P ) I [ P=~ [PI[p-’(a-a)l. 0 Certain special kinds of terms of L> will now be introduced. Let u be the term Consider any a,p, yo,y l , 6 in 9.
I(.al[Pl[yoy,;ylY; 1[6 - 61. ~
Then u shall be an ( e , s, c, e)-term (cf. 9.1). Now assume that (6-6) r- (ran yo * ran y l ) = 6‘6. Then u shall be a right-reduced ( e , s, c, e)-term. Now let
N,
=
( (ap)-
1 r (ran yo . ran y11.
Then 6 - 6 + N , = equ (6-6-t N 2 ) . By S7 and by 9.6(g), [N,] and [6-6 N,] are terms of L;. Let T be the term
+
[a-al[Pl[yuy(~ yiyi I[S-S + N21. Then
T
shall be semicanonical. Also, T shall be the right augment o f u .
LEMMA10.7: Let p be any ( e , s, c, e)-term. (a) There is a right-reduced ( e ,s, c, e)-term u such that t-p = u. (b) I f 7 is the right augment ofu, then u = T. Proof: (a) Let p be ~~~61[~l~PoP;P1P;1~a-al. If POP;PIPI = 4,then p is right-reduced. Now assume that P0/3;P1P; # 0. By 9.6(h), there is some P in Y such that PP- = PoPOP1Pi. Let a(,,a],a2,P‘ be as in 10.5. By S2, there is some 6‘ in Y such that 6’-6’ = equ y * ( a o a o ) . Then
t- 16- 6”l[
PP - 1[a- a1 = 16 - 61[rl[a0aol[all[ P ’P’ - “5
a21
= ~~-~l~~’-~’l~Yl[cu,l[P’P’“;a21 = [eqv (8-66’-6’)][ral][P’P’-l[a~nzl
160
T H t O R Y OF TKANSFORMATIONAL RE1 A T l O N S
ICH.
10
by 10.5, 10.3(c), and I0.2(d) and T3, respectively. By 10.4, -runP' {i: for each k , if (i, k ) E M , then k E -ran p } . Since aru, is the strict confinement of u - a to -run p, therefore (o,-n,)r(-run p ' )
=
- Ly2~(YL.
(b) Assume that u , p, yo, y I , 6 are in 9, ( 6 ' 6 ) r - (run y o . run y l ) 6 ' 6 . u i s [ ~ ~ - ~ ~ ] [ p ] [ y , ~ y ~ y and ~ y ; r] [ is 6 ~the 6 1right , augment of cr. If y,,y; y , y ; = @, then 7 is u.Now assume that YoYtiYlYi f 9.By 9.6(h) there is some y in Y such that y y ' = YoyGyIyi. By S7, [((ap)'(ap)) r ( r m y ) ] and [(o- a)l'(run ( b y ) ) ]are terms of L:> Also,
=
hence
((cup)-(ap))r(runy ) = i d - t y y - P - a - a b y y - , ( a m w a n y ) ) = PP- + ~ y y - p - u - a ~ y m
P* ( (
and therefore
eyv p"(((nP)-(ap))r(run y ) ) = (a-UL)l'(run( B y ) ) . Hence by 10.2(d), :0.2(g), 10.3(c),and 10.2(d),respectively
t-
7
= [n-~l[Pl[YY-l[((ap)'(~~))~ (run r)"-61 - ()a P )) r ( r a nY ) l [ Y Y - l [ ~ - ~ l = [a-aI[PI[((aP = [ a - a ~ ~ ( a - a ) r(( Pr c~r )n) I [ ~ I [ ~ = -~I[~
-~I
T h e next theorem yields two sets of generators for the transformational operations (relations) resulting from 9. THEOREM 10.8: Let p be any term of L,;. (a) For some u f o r m e d from constants [ a ] und [ a ' ] such that a is either idempotent or I - I , t- p = u. ( b ) For some Tformed from terms [ Pp' ] and [ p -p] and from constunts [ a ]and [.-] such that a is 1-1, F p = r . Proof: (a) By SO, and by T 3 and T4, we can assume that p is formed from constants [ a ] and [ a ' ] such that either a is idempotent o r a is 1-1 or ap = id for some p in .Ywhich is 1-1. Consider now this last case. By 9.6(c),there is some idempotent y in .Y such that y - y = a-UL. Then
t- [.-I
= [(y-l[idl= [ a - l [ a l [ b l =[ ~ - l [ r l [ P l
by T4, T 3 , and 10.2(c), respectively. By 10.1, it follows that = [P'HY -"I.
[a]
CH.
101
161
THEORY OF TRANSFORMATIONAL RELATIONS
(b) If aa = a, then
1 [ a ]= [a][.-][.]= [ a ] [ a - ] [ a - ] [=a [] a a - ] [ a - a ] by T1, T 4 and aa = a, and 10.2(a) and 10.2(c), respectively. By 10.1, if aa = a, then [ a - ]= [ a - a ] [ a a - ]Part . (b) then follows from part (a). 0
-t
T h e next theorem yields four related normal forms for the transformational operations (relations) resulting from Y .
THEOREM 10.9: Let p be any term of LT, There are uo, ul,u2, u3 such that u,) and the dual ufof u1are right-reduced (e. s, c, e)-terms, such that u2 and the duul of u3 are semicanonical and such that F p = u , , i ~3. Proofi By T 3 and T4, F [ i d ] p = p. Hence, by 10.8(b), we can assume that p is a term [id] or a term id]^, such that T satisfies the conditions of 10.8(b). If p is [ i d ] , then, by T3, F p = u for some (e. s, c, e) -term u. Now let p be [ i d ] T , where T satisfies the conditions of 10.8(b). Then for some p‘ satisfying the conditions of 10.8(b), some A‘, and some X which is 1-1, T is either p ’ [ X ’ - h ’ ]or p ’ [ h ‘ h ’ - ]or p ’ [ h ] or p ’ [ h ‘ ] . Assume as inductive hypothesis that there are a,P, y o ,y l , 6 in .Y such that I-P‘ = ~ ~ - ~ I ~ P l ~ r ” r o r ~ r ; l ~ ~ ‘ ~ l . If p is p ‘ [ h ’ - h ’ ] ,then , by 10.2(d), there is an (e,s,c,e)-term u,such that k-p = u.If p is p ’ [ X ’ h ’ - ]then, , by 10.7(a) and by 10.6(b) and 10.2(b), there is an (e, s, c, e)-term u such that t - p = u.If p is p ’ [ h ] , then, by 10.7(a) and by 10.6(a), 10.3(a), and T3, there is an (e, s, c, e)term u,such that b p = u.Now consider the case where p is p”h-1. Since X‘X = id, therefore YoyGyIyi = h-’(yl,yb-yIy;-)
where yl, = Xyo and yi = hy,. Then, by 10.3(d) and 10.3(b), there are yb, yi, 6’ in Y such that
k p = p‘[A‘l= ~ a ~ a I ~ P I ~ ~ ’ I ~ ~ ~ y ~ , ~ y ~ y ~ ‘ I ~ ~ ’ ~
By the regularity of 9, there is some X” in ,Y such that A“X [A‘]
= [X”h][h‘]= [h”][hh‘]
=
id. Then
162
T H t O K Y OF 1 R A N S F O R M A T I O N A L R E L A T I O N S
[CH.
10
by T 4 , and T3, respectively. By T 3 and 10.2(b),it follows that p = [ a' a ] [~A"][AA' yAy,i-y;y; '][a'- 6'1.
Hence, in this case also. there is an (e,s,c,e)-term u such that k p = u. such that By 10.7(a). there is a right-reduced (e,s,c.e)-term a,, p = a,,. Let u2be the right augment of u,,. Then u,is semicanonical. Bv 10.7(b). uII = u2and hence 1 p = u,.Now let p" be the dual of p. Applying to p" what has just been proved for p , we obtain some 01 and a,;. such that a;is a right-reduced (e, s, c, e)-term, a:,is the right augment of a : . and b p" = u:= a;.Let a1and asbe those respectively., By 10.1, p= terms whose duals are dIand d,, ul = U { . 0 We now introduce a binary analogue of the unary set ( D M ) { f E X : M C_ f If'}. For any M,,,M I ,M , , the diagonal relation determined b y (M,,,M I , M , ) shall be the set =
EM,,. M I , M,ll
=
{ ( f , h ) E , !M,, & f -f,M ,
c j - h , a n d M2 c h-h}.
T h e notion EM,,, M I ,M 2 j slightly generalizes the notion @MI] { ( f , h ) E ld: M f ' h } , since [rMJ = [rid, M , idl] = [I@, M,@ and I since, by parts (b) and (c) of the next lemma, [rM,,,MI, M211= Uoyc M,,llUMIDUrqt.M,ll. T h e more general notion is needed only for those [IM,,,M I .M,D. which differ from each [rMI,,Mi, MJ for which Mi, C_ id+ MIMI' and M i C id+ MI- MI, since otherwise, by parts (c) and (a) of the next lemma,
c
=
UM,,,M I . M,ll
=
[Mi,,MI, M i l = Uid, MIl,i d 1 = [Mill.
LEMMA 10.10: M I , and Mi M,, then UM,,M,,M,II (a)ff MI, M,,, MI C UMb, MI, Mill. ( b ) UM,,,M I ,M2D = [reqv Mo,M I ,eqv M211. (c) UMo, Mi, M J I = [Mo+ M I M ; , Mi + MOMIM2, M2+ M ; M J . (d) UM,. M , .M,n c [ r M , , n [ r ~ , n u w n . (e) Zfid C MI,and id M2,then [ r M o J [ r M I J [ r M= 2 ~[rM,,M1,M211. (f)[rMn[r~n (g) uan[rm = uaMn. Proofi (c) Assume that ( f , h ) E [rM,,MI, M2n.Then Mo C fy,MI f-h,
c
c
c
c cumn.
c
CH.
101
163
THEORY OF TRANSFORMATIONAL RELATIONS
The other inclusion follows from part (a). (d) Assume that ( f , h ) E EM,,, M , , M J . Then there are g and g’ in I,namely g =f and g’ = h, such that MI, C f -g, M I C g ‘ g ‘ . and M, g’-h. (e) Assume that ( f , h ) E UM,,RUM,II[IM,II and that id C MI, and id M , . Then there are g E X+andg’ E I,such that id M,, c f - g , M I C g - g ’ , and id C M 2 C g ‘ - h . Since id f-g, therefore f ( i ) = g ( i ) for each i , and hence f = g. Similarly, g’ = h. Hence ( f , h ) E EM,,, M , , M2D.T h e lemma then follows from part (d). ( f ) Assume that ( f , h ) E [IMIIUNII. Then there is some g E I, such that M C f - g and N g - h . Then M N C f ‘ g g - h C j - h . Hence ( f , h ) E EMNII. (g) Assume that ( f , h ) E EaMT]. Then a M C f h . Let g =fa. Then a C f - f a = f - g , and hence ( f , g ) E [ a ] . Also, M C g - g M = g - f a M C g ‘ f f - h C g‘h, and hence ( g , h ) E [MI]. Hence ( f , h ) E [IaIIUMI].The lemma then follows from part (f). El
c c
c
c
It is natural to consider those triples ( M , , ,M I ,M , ) for which neither IO.IO(b) nor IO.lO(c) leads to a new triple. We let ( M , , ,M , , M 2 ) be cunonicul if and only if it satisfies the following conditions: (i) M,, = eqv M Oand M 2 = eyv M , ; (ii) M , M , M ; M,and M ; M , M , C M 2 ; (iii) M , , M , M , = M , . We let ( M , , M I ,M , ) be precunonical if and only if it satisfies (i) and (ii). We let ( M , , ,M , , M 2 ) be semicanonical if and only if it is precanonical and satisfies the following condition: (iv) M,,M,M2 = M,,M,. M O M , M,M,M,and Note that (i) and (iii) imply M o M , M , = M , hence imply (iv). Also, if M , = eqv M U and if (iv) holds, then M , M , C M , , M , M , = M o M , , while if M , = e q v M , and M , M , C M O M , , then M , M , M , C M o M o M= l M O M I .-Hence (i) implies that (iv) is equivalent to: M I M , C M O M , .Also, (i) implies that (iii) is equivalent to: M O M ,= M I and M I = M , M 2 . Hence (i) and (iii) imply that (ii) is equivalent to: M , M ; C Mo and M ; M , C M , . It also follows that
c
c
I61
I Hf O H Y OF T R A N S F O R M A I I O N A I K k L A r l O N S
[CH.
10
if ( M , , . M I .M , ) is canonical. then M I M ; M l = M I . These, or closely related. facts will sometimes be used tacitly. LEMMA10. I 1 : (21) If' M I ,= c y r M,,. M , = P ~ M,, C titld M , , M , M , = M I . then ( C ~ C I( ~M I , +M I M , ) . M l .c q r ( M , + M ; M l ) ) i . s ~ ) ~ ~ ~ ~ . ( i i i o t l i ~ . ( i l . (b) If ( M I , .M I , M , ) is precanonicctl, then ( M , , . M,,M,M,, M , ) is crrnoniccil. ( c ) If ( M , , . M I . M , ) is semicanonical, then ( M,,, M l l M 1 M , 2 ) is ('(1 nonicril. Proof:
(a) A s s u m e that M,, = e y u M I , ,M , = eyv M,, and M , , M , M , = M I . Then M , , M , = M I . Hence, i f 11 2 1 then ( M , M ; ) " = M , ( M , M ; ) " , where N o = id and N"+' = N N " . It follows that M,,(
E
(M,W
)ti)
=
oc I K W
=
M,,+
M , ( M , M ; )(I+M,(
M l , ( M 1 M ; ) " =M,,+
(wM;)~) (M,M;)".
IS?I
IS II
Hence
z z
ISII<W
( M ~ , ( ~ W ( M , M ; )=) ) c,
(M,(
0s IIl<W
(M,,+
= 0s JII<W
C
(M,M;)~~))J~~ (M,M;)")"'
IQII<W
M(r+
=
z
( I S n<w
~lsItl<w
= M,,+equ
E ( I=n<w z
IEIII<W
(MIM;)n))"'
(M,M;).
NOW let M , i = e y u ( M o + M , M ; ) and M ; = e q u ( M , + M ; M , ) . It follows that M;, = M,+equ ( M , M ; ) . Hence M i M i M l = M;(M,+equ
(M,M;))M,
M i M o M , + M ; (equ ( M I M ; ) ) M , = M i M I + M ; (eqv ( M , M i ) ) M l =
I:
=Mi(
nsn<w
C
(Pzn i w
Similarly, M , M g M 1 -
(MIM;)")M,=
C
(Mi M I ) " = eqv ( M i M , )
MA.
(MiM,)"+'
0s n<w
MI.
CH.
101
I65
T H E O R Y O F T R A N S F O R M A T I O N A I . RELATIONS
(b) Assume that ( M I , M , I , M , ) is precanonical. Let MJ = M,,M,M,. Then
MIMI'
= M,M,M,M, M ; M i = MoMlM2M;Ml,
Similarly, MI' M i
MoMIMz
Ml,Ml,Ml,= MI,.
C M , . Furthermore,
= M,M,M,M,M,
= M o M l M , = MI.
(c) Assume that ( M , , , M , , M , ) is semicanonical. Let MI Then we have
= Ml,MI.
c MOMOM; = M I , , M I ' M I = M ; M i M o M I = MIMOM, c M,, M l , M J M 2= M,M,M,M, c M,Ml,Ml,M, = M O M l= M I . 0 MIMI-
= MoM,M;M;
THEOREM 10.12: (a) For each M,,, M , , M , there are MA, M I , M i which include M , , MI, M , respectively, such that ( M i , M I , M i ) is canonical and such that [ M ; , M i , Mkll = EM,, M i , M J I . (b) Assume that IIUII 2 2 and that ( M , , MI,M , ) and ( M I ; ,M i , M i ) are canonical. T h e n EM,, M , , M z ) C [MI,, M I , Mill if and only if MI, C MI,, MI C M I , and M3_C M 2 . Hence [ M I , . M I , M , ] = [MI:, M i , M i ] if and only $ M I , = M:,, M , = M J,and M , = M ; .
Proof: (a) Let any ( M , , M1,M , ) be given. Then ( e q u M,. (equ M,) M , (equ M,) , equ M , ) satisfy (i) and (iii) of being canonical. Moreover, by lO.lO(b), lO.lO(c), and lO.lO(a), UeqvM,, ( e q u M , , ) M , ( e q v M , ) , eqvMzll = UM,,M,,M,ll. By lO.ll(a), and by lO.lO(b), lO.IO(c), and lO.lO(a), there are M:, MY, M f including equ M,, (equ MO) M I (equ M , ) , equ M , , respectively, such that ( M i ,My, M i ) satisfy (i) and (ii) of being canonical and such that
[MI(, My, Mill
=
Uequ M,, (equ M,) M I (equ M,) ,eqv M A .
By 10.1 l(b), and by lO.lO(c) and IO.lO(a), there are M i , M i , M i including M i , My, M;, respectively, such that ( M i , M i , M i ) is canonical and such that [ M i , M I , M i ] = EM;, M ; , Mill. (b) Assume that I(Ul(2 2 and that ( M , , M , , M , ) and ( N l ) , N l , N , ) are canonical. Suppose that N , M I . Then there are in and i , such
I66
THEORY O F T R A N S F O R M A T I O N A L RELATIONS
[CH.
10
that (i,, il) E N, . -Ml. Let u and v be distinct elements of U . Let f(j)
Let
=
if (i0J M,,, [u otherwise. 11
E
{
II if ( i o , j ) E M1, h ( j ) = u otherwise.
Then f ( i o ) = I i # u = h ( i , ) and hence (i,,, i,) e f ‘ h . Since (i,,, il) E N , , therefore N, f ‘ h and hence (f,h ) 4 [IN,, N , , N J . Next, consider any ( j , k) E M,. If ( i o .j ) $! M,, then ( i o ,k) fZ M,, and hence f ( j ) = u = f ( k ) . If ( i o , j ) E M I , , then ( i , , , k ) E M,, and Hence M o h e n c e f ( j ) = u = f ( k ) . In either case, (j,k ) E N o w consider any ( j ,k) E M , . If ( i 0 , j ) E M I ) ,then ( i o ,k ) E MOM, = M I and hence f ( j ) = ii = h ( k ) . If (i0J @ M , then ( i n , k ) @ M , , since (i,, k) E M, would imply that ( i o , j ) E M I M ; C M,. Hence, if (i0,j) ‘$ M , then f(j) = v = h ( k ) . In either case, ( j ,k) E f ‘ h . Hence M I C f ‘ h . N o w consider any ( j ,k) E M,. If ( i o , j ) E M , , then ( io, k) E M , M , = M I and hence h ( j ) = 14 = h ( k ) . If ( i o , j ) @ M , then (i,, k) fZ M1, since (i,, k) E M, would imply that (i,,j) E M 1 M 2 = M l M 2 = M,. Hence, if ( i 0 J @ M I , then h ( j ) = u = h ( k ) . In either case, ( j , k ) E h u h .Hence M 2 h - h . It follows that (f,h ) E EM,, M I ,M,D and hence that [IMn,Ml, MzIl cf [IN,,,N , , N2D. A similar argument shows that if N o M , o r N 2 M 2 , then [IM,,,M 1 ,M211 $ [IN,,, N,, N2D. Hence UM,, M,, M2D C [IN,, N,, N,Il implies that N o C M,, N, M1,and N, MP. T h e converse follows from 10.10(a). 0
fx
c
fx
c
LEMMA10.13: Let a, p, y o , y , , 6 be in Y . (a) \[a-ai[~i[y,~y,y,y;i[6-61\, = ua-a, P Y ~ ~ O W6-a. ; ~ (b) If [ . - c ~ I [ P l [ ~ o ~ ~ ~ l ~ i ] [is6 - 6a] semicunonical term, then ( a - a ,Pyoyiiyiyi , S - S ) is semicanonica!. Proofi (a) Suppose first that yoy;yly; # 0. T h e n there is some y’ such that IIyoynyoylyiIl is Uy’DUf-Il and Y ~ Y O Y ~ Y ; = Y‘Y’-. Then U y ’ l b ’ -1 = Uy’y’-D. By the definition of \p\*, \[y’l[r’-]\* is Uy’DUy‘-J1. Hence \Crororlr;l\*= [Irorirlr;ll.Suppose now that Y , , Y ~ Y ~ Y=; 0. Then a n argument which is similar but also uses ~ y n y R J 1 ~ y= I y[[y,,-yoyly;ll j~
CH.
101
I67
T H E O R Y OF T R A N S F O R M A T I O N A L R E L A T I O N S
shows that \[yoy;yly,-]\:i:= [Iyoy;yly;Il. T h e lemma then follows by lO.lO(g) and lO.lO(e). (b) Assume that [ a - a ] [ p ] [ y o y o y l y ; ] [ 6 - 6is] semicanonical. Let M,, = a‘a, MI = p yoy;y I y ; , and M, = 6-6. Also let
N, = ((ap)‘(ap))r(ranr,.,rany1). Then, for some 6’, (6”6‘)r-(ran yo .ran y l ) = 6’-6’
and
MZ
= 6”6‘
+ NZ.
Then M,M, = M 1 N 2 . Now consider any (i, k ) E M l N 2 . Then k E ran y o . run y 1 and, for some j~ r a n y , , * r a n y l , i = p ( j ) and + ( j ) = a p ( k ) . Then ( i . p ( k ) ) E a‘a and ( p ( k ) , k ) E MI. Hence (i, k ) E a ’ a M , = M a l . Thus M , M 2 M O M l ,and hence ( M o ,M , , M 2 ) satisfies condition (iv) of semicanonicalness. It follows that
c
MiMZM; = MlMzM,M;= (M1M2) ( M i M z ) ‘
Also,
& (MOM,)( M O M , ) -= MoMIMLM,; & MOM;
= Mo.
MLMOMI= YIY~YOYOP -a-aPyoyiyiyi = (aP)- (aP) - 2 ( r a n y o * r a n ~C1 )N , & M,.O L E M M A10.14: Assume that llUll 3 2 , und that the terms p = [ ~ - ~ l [ P I [ ’ ~ o y ~ y ~ yund i 1 [ ~p’- ~ =1[ a ’ - a ’ l [ P ’ l [ y ~ y , ~ - y ~ y ~ ~ lare [6’-6’] if and only if the following foirr semicanonical. Then \p\* C conditions are satisfied: (i) a”al a-a; (ii) 7;y;- r;r;-G YOYO-YIYI‘; (iii) S’-6’ 6-6; (iv) ij-yAyA-y;y;- = y’y‘-, then ap‘y‘ = spy'. Proof: Assume the hypotheses of the lemma. First assume (i), (ii), (iii) and (iv). Consider the case where y;y;-y;y;‘ # 0. Then yAy;‘y;y;= y ’ y ’ - for some 7’. By (iv), \PI\*
c c
n
ua -anupnurv- = ua-nuapy’nw =
-n
ua-nuapvnw-n = ua-anwnwr’-n.
I68
Also
T H E O R Y OF I R A N S F O R M A 1 I O N A L RELATIONS
u.
-
ammrorirlr;nus -an
c
ua
ICH.
10
- a n u m w-nus-an
by (ii), and -a n u P q u Y ' y
nus -61 c
by (i) and (iii). Hence \p\:$ Then
- a q u p g u y ' y ' -nus'-sg
C \p'\:!:.Suppose now that y,!lyb-y~yi'= 0.
upnur(;r;-r;rjn = UY~:Y;)-Y;Y;n = uP'nur;)r;)-r;r:n.
Then similarly \p\.!: C \p'\*. Now assume that \P\:~ C \p'\:::. Then it follows from 10.13(a), lO.l3(b). 10.1 l(c), lO.lO(a), IO.lO(c).and lO.l2(b), that u"a'
6"6' Since
c a-a, c 6'6,
a' -a'p'yoyi y , y ; i E (ran y:, . run y ; )
c a - apyoyi YlYl'. . - (ran y o . run
would imply that
(P'(4 i> E (a'-a'P'YoYOY,Yl-) 7
*
- (a-aProYir1r;).
it follows that y b y ~ - y ~ y C ; ' yoyOyIy;. Now assume that there is some y' such that y ' y ' - = -y:)-y~)-y;y~and consider any i E run y ' . Then
(p'(i),i)
E a'-a'p'y'y'- = a ' - a ' p ' y I ; y ~ - ~ I ~ ~ -
c a-apyoy,y,y; c a-ap.
H e n c e a ( p ' ( i ) ) = a P ( i ) .I t f o I l o w s t h a t a P ' y ' = apy'.D T h e completeness of T, (under our assumption that ))I)) 3 3 and that satisfies SO, .... S7) can now be proved.
THEOREM 10.15: If p = p ' , then p = p ' . Proof: Assume that k p = p ' . By 10.9. there are a , p, y o , y , , 6, U L 'p', . yb. 7 ; .6' in 9such that the two terms and
u =t ~ ' ~ I t ~ I t Y l ~ Y o Y ~ Y ~ I t ~ - ~ l
u'= [ a ' - a ' ]p'][y;y,!)"y;y; [ -][6'-6']
CH.
101
THEORY OF TRANSFORMATIONAL RELATIONS
I69
are semicanonical and such that k p = u and k p ' = u'.By the soundness of & , k p = u and I=p' = u'.Hence k u = u'.From 10.13(a), 10.13(b)and 10.14, it follows that u'is [a'al[P'l[roro yIyI' 1 [6-6] and that if yl,yl;yly; = y y then ap'y = apy. If yoycylyi = 0, then 1 u = u' by 10.3(e), and hence k p = p ' . Now suppose that yoyOy1y; f 0.Then, by 9.6(h), there is some y in Y such that yoyOyIy;= y y ' . Then '
t-
[ a-a][Pl[rr""I
r
= a -l[al[ P"
-"I = rc.-lr~Prlrr-lr~l =[~-l[~P'rl[r-l[~l =r ~ - l r ~ l [ P ' l ~ = ~ l[a~ al[P'" ~ ' l ~ ~ rl"1
by 10.2(c) and 10.2(a), T3, aPy = ap'y, T3. and 10.2(c) and 10.2(a). respectively. Hence again k u = u'and thus p = p ' . 0 We now return briefly to the language L, and set T B r of ch. 9. An {s, t}-term of L, shall be any term of L, which contains x but no other variable, which contains at least one ( s a ) or (ta), and which contains no function symbols other than (sa) or (ta). a E Y . Under our assumption that 11111 3 3 and that Y satisfies SO, ..., S7, we now show that TB; is complete with respect to those inequalities which involve only transformational operations. For fragments of L other than that of 9.9 and the one immediately below. completeness seems to be an open problem. THEOREM 10.16: Let p and p' be any {s,t}-term;\ of L .such that p' is derivable from TB;. p' is valid. Then p Proofi I n this proof we let p , p ' , cr, u',... be {s, t}-terms of L, and T,T',... terms of LJ. For each term T of Lr. we let rN be that term of L; which results from T by change of parentheses only and which contains all right parentheses to the right of all other symbols. For each {s, t}-term p of L,, we let pT be that term of LT,, which is obtained by first listing the occurrences (from left to right) of the symbols (s a ) and ( t a ) in p , then replacing each (sa)by [a] and each ( t a ) by [a-1,then inserting between two consecutive constants of L; the 2-place function symbol of LT, and finally adding parentheses so as to yield a term r'( of LT,. Clearly, for any I/, p and pT denote the same operation. If pa = id, then TB; ( s a ) x 3 (tp)x, by 9.8(b), 9.4(a), and TB4. If ap = id, then TB; t- ( s a ) x C ( t p ) x , by 9.8(b), 9.4(a), TB5, and 9.2(b). Hence if a = p then TB; F ( s a ) x = (tp)x. It follows that if
p
I70
T H t O R Y OF TRANSFORMATIONAL R t L A T l O N S
pl is P ‘ ~ uT , is u’l, and TB,
p = u,then also TB?
ICH.
10
p‘ = u’. In
the next paragraph we shall use this fact tacitly. Now consider any terms T and T ’ of LT. Let p and p‘ be any terms of L, Fuch that p‘ is and P ’ is~ T ‘ ~ If . T = T‘ is in TO, then T~ is T ’ and hence TB; l- p = p ’ . If T = T’ is in T 1 , T2, T3, T4, T5, T6, or T 7 respectively. then it follows from 9.2(g), 9.2(h), TB6, 9.4(a), 9.10(b), 9.8(e). and 9.8(h). respectively, that T B / k p = p ‘ . By induction, if T = T’ is derivable from T, , then TB; t p = p ’ . Now let p and p’ be {s,t}-terms of L, such that b p = p‘. Then t= pT = P ’ ~ By . 10.15, p’ = pIT is derivable from Ti. Since (pT)‘ IS p r and ( p ‘ l )It is p t Ttherefore . TB; p = p ’ . Thus TB; is complete with respect to equalities between {s, t}-terms of L,. Finally, let p and p’ be {s, t}-terms of L, such that !F p s p ’ . Then by 10.9, 10.14, and t h e soundness of Ti, b pT = T and ’F ptT= T‘ for some 7 = [ ( Y - ~ I [ P I [ Y ~ YI[S-SI, ~Y~Y~
-t
7’=
[ a ” ~ ‘ l [ ~ ’ l [ Y ( l Y ( ;Y~’Yl-l[a’l
such that (Y, P , ... y l , 6’ are in Y , and such that (i), (ii), (iii) and (iv) of 10.14 hold. Consider first the case where -y,:y:lyiyi # 0. By 9.6(h), there are y ’ and y in Y such that y ’ y ‘ - = -y;)yA-yiyi- and y y ” = w o yIyI-.Let u = (ta)(SOL)
(SP)
u’= (ta’)(SOL’)
b y ) (ty) (t6) ( S S ) x,
(SP’)
(sy’) (ty’) (t6‘) (SS’)X.
Then ’F p = u and b p’ = u’.Hence TB, p = cr and TB- 1p’ = u’, by the above completeness of TBp. Using 9.7(a), 9.7(b), and this
completeness, we can now parallel the reasoning in the first part of the proof of 10.14 to show that TB; k u C u’.It follows that TB; p 6 p ‘ . Consider now the case where $%;“y{y,’- = 0.Then TB,
t ( S P ) (sr(J(tr(J (SYJ ( t y p = ( S P ’ ) by;,) (tr;))(syj) (ty;)x,
again by the above completeness of TB;. Then, by an argument similar to that for the previous case, TBd k p C p ‘ . 0 By the soundness of Tp, results of this chapter involving t- have counterparts involving b, which we shall quote by the same number. These counterparts do not depend on T,, and often not on our assumptions about Y . Some of their consequences are worth noting.
~
CH.
lo]
T H E O R Y O F T R A N S F O R M A T I O N A L RELATIONS
171
From 10.9, 10.13, 10.1 1, and 10.12 it follows that for each p there is a unique canonical ( M , , ,M , , M 2 ) such that, for each U , \p\ = UM,, M , , M J . Moreover, our proofs contain directions for constructing this ( M,,, M , , M,) . Hence these proofs contain directions for determining, given any p and p ‘ , whether or not the corresponding canonical ( M , , ,M,, M , ) and ( M b , Mi,M l ) are the same and thus !F p = p ‘ . For certain 9, including any 9 A c s , these directions can be carried out effectively and hence yield a decision method for validity of equalities p = p’. Similar remarks apply to inequalities between {s,t}-terms of L,. The existence of such decision methods can also be inferred from the following consequence of 10.9 and 10.14.
THEOREM 10.17: Let p and p‘ be any { s, t}-terms of L,. Then p p’ is valid if and only if\ p\ +. G \p’\ * f o r some (and hence f o r each) U satisfying 11 UII = 2 . A set-theoretic consequence of 10.9 is the following theorem, which contrasts with Theorem 3.5 of [ 171.
THEOREM 10.18: If I is finite, then the set of transformational relations (operations) resulting from Y is finite. From our assumptions about I and Y it follows that, roughly speaking, formation of relative products yields no new relations [rag. [ra-ajor Baa- 1.
THEOREM 10.19: Assume that I(UlI 2 2. (a) If\p\ * = [Tall,then (Y E 9. (b)Zf\p\. = [ r a - a I ] , t h e n a - a = p - p f o r s o m e p E 5”. (c) If\p\ , = [Taa-g,then aa-= pp- for some p E Y . Proof: Let any term p of L$ be given. By 10.9, 10.13, lO.lO(c), lO.lO(a)and 10.1l(c),therearea’,p’,y~,,y;,6’in.Ysuchthat ( a ’ - a ’a, t - a t p t y ; y ; -y ; y ; - , s’-sl)
is canonical and \p\* = [
(a) Assume that \p\*
~ ~ ~ - ~ ~ , ,si-sin. ~ ~ - ~ ~ p ~ ~ ; ~ ; =
[rag. Evidently, [Tall = [rid,a , a-all and
(id,a,a-a) is canonical. Hence, by 10.12(b), a = a’-a’ p‘ yiyi-yiyi-. This implies that a = p’ E Y .
172
T H E O R Y O F 1 R A N S F O R M A I I O N A L RE1 A 1 IONS
[CH. 10
(b) Assume that \p\* = Ua-aII. Evidently, [la-all = [la-a,a-a, a-all and ( a - a , a - a , a - a ) is canonical. Hence, by l0.12(b), a - a = a“a’ where a’ E .Y’. (c) Assume that \p\:$= [Iaa-I].Evidently [Iaa-Il = Bid, a a - , id1 and ( i d , a a - , i d ) is canonical. Hence, by 10.12(b), aa‘ = a‘- a’p’yhy;,-y;yi-. This implies that a a - = y l \ y l ~ - y ~ y By ; - . 9.6(h), and since a a - # (0, there is some p in Y such that pp = yoy{yIyi = aa-. 0
Finally, we describe the relationship between the diagonal relations (determined by some ( M , , ,M I .M , ) ) and the transformational relations (resulting from 9).
THEOREM 10.20: (a)Each trunsformutional relation is a diagonal relation. (b) I f ,Y = ‘ I , then euch diagonal relation is u transformational relation. PROOF: (a) By 10.9 and 10.13(a). (b) By 10.12(a), each diagonal relation is EM,, M I ,MBll for some canonical (MI,,M I ,M ? ) . Let K be any cross-section of Mo and let N , = M I . ( K X I ) . Consider any ( i , k ) E M I . There is some j E K such that ( j , i ) E MI,. Then ( j , k ) E M , , M , C M I . Since j E K , therefore ( j , k ) E N , . Then ( i t k ) E MI&”. Hence MI C MIIN,. Conversely, M , , N , M , , M , C M I . Hence M , , N , = M I .From lO.IO(c) and 10.10(a) it follows that EM,,,M I .M2D = EM,,,N , , M J . Now suppose that ( i , k ) E N , and ( j , k ) E N , . Then ( i , j ) E N , N ; C M , M ; C MI,. Since i E K and j E K , therefore i = j . It follows that N , N ; C id. Hence there are p, y o , y , in ‘ I such that N , = py,,-y,jy1y;. Also, there are a and 6 in ‘ I such that MI,= a - a and M , = 6-6. From lO.IO(e). lO.lO(g), 10.2(c), 10.2(b), and 10.2(a) it follows that [ I M , ,N , , M,n
=
n
ua- uan
u p m I , nu ~ m y Iuny m - n u a .
Hence EM,,.M I ,M,J is a transformational relation resulting from ‘ I . 0 The assumption that lllll 2 3 is not needed for Theorems 10.17, ..., 10.20, since, when is replaced by ‘F, it is not needed for 10.2(b) and hence not for 10.9.
CHAPTER I 1
SOME CASES OF INCOMPLETENESS
I n this chapter w e shall give some incompleteness results. Most of these are based on unpublished work by Ralph McKenzie (done in 1967). T h e rest follow from a result by Johnson in [ 171. Specifically, for a certain semigroup 9 of transformations of w, it follows from McKenzie's work that the w-valid equalities of L , are not recursively enumerable and that the set T B , of ch. 9 is incomplete. Also, for 3 s 11/11 < K = w and .Y = ' I , it follows from Johnson's result that T B , is incomplete. T h e problzm of completability by other axiom schemes will be T B ,will be shown t o be comdiscussed briefly. Also, for the above 9. plete with respect t o those equalities which involve only transformational operations. Explicitly, McKenzie was concerned with conditionals u = 0 + 7 = 0 where CT and T are terms of Lpq and where, moreover, u and T contain n o variable other than x. H e showed that the w-valid conditionals of this form are not recursively enumerable, and stated that for (w-validity similar methods yield a similar result. To facilitate exposition, we shall make minor changes in McKenzie's is the language whose argument and apply it t o \ L p q . A , . , \ . where Lpq.acs function symbols are those of Lpq and those of LA,,. By 7.4 and 7.6, the sets \ Lpq \ and \ L p q . A c ,\ of w-operations are the same. W e let / = w. A s in ch. 7, we let ( i / j ) n= n if n # i and ( i / j ) i= J . if n > r. and w e let ( r ; - - l ) n = n if n s r and ( r ; - I ) n = n - l Similarly,welet ( r ; + l ) n = n i f n < r a n d ( r ; + l ) n = n+ 1 if12 3 r . i 5 3, one W e let u p be the term uE.,+up2+uF:, where, for 1 = 0 from the corresponding expression below in the usual obtains ub.i way. (1) ~ e - d l ? C do,. (2) ( S ( ~ / ~ ) ) X . - ( S ( I ; + I ) ) (s(O/l)) X' (s(I/~))x.-(s(O;+I))X C do,. (3) ( s (1 ; A I ) ) x C c,,( (s( 1 ; A I ) ) x s-x).
173
I74
S O M E CASES OF INCOMPLETENESS
[CH.
11
LEMMA1 1.1 : Let ( U , X6)6<,,be any w-structure. Then the following a r e equivalent to the condition that ( U ,X6)6<1)is a n w-model of ( 1 ) , ( 2 ) , or ( 3), re.\pccticrIy. ( I ) ' For each h E " U , i f h , , f h , , then { u : (ri)-h E X O } C {h,,). (2)' F o r ericli h E "U, /I { u : ( u ) - ( h,))-h E X o } . - { u : (u)-h E Xo}II 1. (3)' For ctrcIi h E " U . if Il{u: ( u ) - { h O ) - h E X,,}ll 2 1, then l l { r r : {Ii)-(h,,)-h E X , ) }. - { [ A : { u ) ^ h E X,)}ll 2 I . Prooj: Let any h E "U be given. Consider any u and w in { u : { l 4 ) - ( h ( l ) - / l E X } . - { u : ( u ) - h E X } . T h e n {c.1.1-)-hisineachof the sets ( S ( I / 2 ) ) X . - ( S ( l : + I ) ) X , ( S ( O / I ) ) ( S ( 1 / 2 ) ) X and - ( S ( O , + 1 ) ) X . Now assume that ( U , X 6 ) 6 < 1is) an w-model of ( 2 ) and that X,, = X . Then { L', ~ ' ) - his in D,,,and hence u = M'. Since this hold\ for any h E " U , therefore ( 2 ) ' holds. Now assume that ( U , X6)6,, is an w-model of ( 3 ) . Let X = X,, and consider any h E "U for which there is some v E U such that ( v ) -( A,,) -h E X . Then (v)^h E S ( 1 ; L l ) X
c c,)((S(l;Al))x.-x).
Then there is some M I such that ( w ) - h @ X and such that (wi)-h E ( S( 1; 1 ) ) X and hence ( H,)-( hJ-h E X . Hence ( 3 ) ' holds. T h e lemma now follows easily. 0 L E M M A11.2: (a) I f ( U ,Xfi)6,, is rrn w-model of u p c,,-d,), = 0 then, for each / i E " U , ll{u: ( u ) - h E X,,}II < N,,. (b) If I c IJUl)< N,,, then there is some w-model ( U , X 6 ) 6 < sof U~ * c,,- d,,, = 0 c l t 1 d S o t ? l e h E "U .sli(.h t/l(/t { u : (14)-h E XI)}= 0. Pro()$ (a) Assume that 1' = { C J , X f i ) f i , ,is an w-model of ur cO- d,,, = 0. If ?( is an w-model of c,l-d,ll = 0, then I)UII = 1 and the desired conclusion holds. Therefore assume now that 91 is not an w-model of c,l-d,l, = 0. Then ?( is an w-model of c,,-d,,, = 1, and hence an w-model of u p= 0. Consider any h E " U . Suppose first that h is a constant function, i.e., that h i = hj for each i < j < w. Then (h,)-h = h. By (3)' of 1 1 . 1 . 11{u: ( u ) - { h , ) ) - hE X,,}ll < 1 and hence ll{u: ( r r ) - h E Xll}ll = 0. Suppose now that h is not a constant function. Then there is s o m e j such that hi # A,+, and such that hi = hj for each
-
-
1I]
CH.
I75
SOME CASES OF INCOMPLETENESS
i < j . By (1)'of 11.1,
Hence, by (2) ' of 1 1.1, 11{/1:
>
(u)-(ho, ..., hJ,hJ+l,... E
xo}ll c j +
1.
(b) First assume that 11U11 = 1. Then the desired conclusion holds for X , = "U and the unique h E " U . Now assume that U = ( 1 4 0 , i l l , ..., L I ~ , - ~where } n 2 2 and where u, # 11, for i < j < n. Let XI, = { ( ~ ) - fu~l )(- g : g E "U and there is some i, 1 s i c n, such that f E ' { ~ I ~ and ,} II E { i l l , , ..., u - ~ } } . Then ( I ) ' , ( 2 ) ' , (3)'of 11.1 hold.ThenthereareX, C "U,O < 6 < q. such that ( U , XG)fi,, is an w-model of uF= 0 and hence of ub* Co - do1 = 0. Moreover, iff E n { u , } ,then, for any g E " U , { u : (u>-f-(.J-g
E
X"}
=
u. 0
For any r and s and any formula J/ (of L,) of type (r, s ) one can define a formula rlu of type ( r ,s + 1 ) in which one, so to speak, relativizes to the last place of relations of rank s 1. To make this more precise, we need a way of indicating, when several sets are under consideration, which one is to serve as universe. For any I/ # 0,we therefore let / x be the operation x i for the universe V . Recall that, for any Y $+lCJ,
+
c
and
+
/,
P;s,l Y = { ( w " , ..., wsPl): ( w", ..., wsPlru ) E Y for some u } PsY = { u: ( w", ..., w , - ~ ,u ) E Y for some w", ..., w ~ - ~ } ,
where P is regarded as an lo-operation. Then there is an effective method of constructing for any formula Ji of type (r, s) a formula rlu of type (r, s 1) such that, for any U # @, Y s+lUandf E r U ,
+
+
f E rlu + :(.(Y ) if and only if
0 # F','y+, Y C . ( P Y ) andf
E ~ J / ~ p p ' v ( PY). ',s+l
Let x, = x be of rank s. Let a:s)be the result of substituting psx for x throughout uF.Let tm be the mapping of formulas of LBinto terms of which is described just prior to 7.7 so that, by 7.7, L, (or of LACS) \tm (rlu +)\ = 0' j rlu /.
+
I76
SOMk C A S t S OF INCOMPLETENESS
L E M M A1 1.3: Let JI be .symbols other tliun (ire rqiiiculent. dictitr
[CH.
1I
of L3 \z>liichcontuins no prerind x. Then tliefi~llowingtwo conditions
tiriy fbrmulci
(i) j+j, ( Z ) = @ Ji)r c'uc'ry V und Z such thut llVll < H I , and @# z "V. (ii) u;s)* c,,- do, = 0 + t m ( r l u JI) = 0 is w-utilid. Proof: First assume (i). Let ( U , X , ) G < Obe :' - any w-model of u cl,-dd,,,= 0. Let X = X I ) . Consider any f E "U and h E " U . Then j - 1 7 E \ t m ( r l r $)\(A') = (W'irlc J I j ) ( X ) if and only if f E jrIr J / i ( , s + ' UX. - h ) . Let
c
-
V=
,"("+Iu.X-h)
z= f ;
(+,
(S+lU
= c/.
(psX)-h,
.X-h).
Suppose first that V = 0 or Z $ "V. Then f 6! / r / u J / / ( " + I U . X - h ) , by the definition of r / u . Now suppose that V # @ (and hence Z # 0) and that Z " V . By 11.2 (a), and since ( U ,Xs)G
c
c
~ = X ~ , = { g - ( u ) - h ' : gE Z a n d ( v ) - h ' E Y , ) }
c
and. for 0 < 6 < q , let X , " U . Then ( V , X6),,, is an w-model of . c,,-dI,, = 0 and hence an w-model of tin ( f l u J / ) = 0. Now conI. sider a n y f E ' V . Thenf'-h @ \ t m ( r l r J / ) \ ( X )= ( o ' j r l c J / j ) ( X )and ) . the choice of h. f " ( " + ' V . X - h ) hence f @ ~ r I c J / ~ ( " + ' V . X - hBy = V # @. Also f ' , , + , . ( . s + l V . X - h )= Z "V. Hence, f f2 iJIiI.(Z). Therefore iJ/ i, ( Z ) = @.Hence (ii) implies (i).
uLYl
c
I t is well known that. for any s 2 2. those formulas J/ are not recursively enumerable which are oftype (0, s ) and have no model ( V , ZS)6
CH.
111
I77
S O M E CASES OF INCOMPLE-FENESS
denoting the same w-operation. Hence 11.3 yields that part of 11.4 below which pertains to w-validity. For Iw-validity, instead of w-validity, one can give a similar argument, which is somewhat simpler since no special provision is needed for those f that are constant. By 7.1 I , one can use symbols of L Acsf in addition to those of L,,. Instead of the inequalities ( I ) . (2), (3) above, one can then use the following: (4) xe-q'l s do,. ( 5 ) ( s ( I ; 1 ) ) x * - ( s ( I ; + 1 ) ) (s(1; 1 ) )x * ( s ( 0 ; + I ) ) x . - ( s ( O ; ( s ( l ; + l ) ) x c do1.
+
+
+1 ) )
THEOREM 1 1.4: Consider the conditionals u = 0 --* r = 0 such that u and r are terms of L,, containing no variable other than x. Then neither those thut are w-valid nor those that are lo-valid are recursively enumeruble. One task of terms p of L,, is to denote an w-operation. A different task is that of specifying the set of those w-structures which are wmodels of the equality p = 1. One may call these w-structures the wmodels of p. Regarding the second task, but not the first, \[.,A and \L,,\ are equivalent. (This follows from footnote 5 of ch. 5.) With respect to the first task, two terms p and p' serve the same function if and only if (i) b p = p ' . With respect to the second task, two terms p and p' serve the same function if and only if (ii) I=p = 1 p' = 1. For L3 i, in place of \LPq\.the condition corresponding to (ii) as well as the condition corresponding to (i) gives rise to a relation which is recursively enumerable. This may be a cause of our tendency to de-emphasize or overlook the difference between the two tasks. the difference is more difficult to ignore. According to 8.10, For \Lpq\. (i) gives rise to a relation which is recursively enumerable, whereas -(u + r ) = 1 shows that (ii) gives rise a change in 1 I .4 to -u = 1 to a relation which is not recursively enumerable. " U , the condition X # 4) is equivalent to the condition For X (Cw)X = " U . Hence it follows from 11.4 that, if one adds to L,, symbols for the cylindrifications ( C (w * - J ) ) where J is finite, then the w-valid equalities are not recursively enumerable. We shall say that OL E Acv, or that OL has almost constant value, if and only if OL is a transformation on w and there is some k such that
-
-
I78
S O M E CASES OF INCOMPLETENESS
[CH.
1I
I n particular the transformation ( D 0) satisfying i < o is in A C L .Now let .Y = Acs+Ac.v. Then there i s a term T of I ,. for example, the term (s( D O ) ) ( t ( D 0 ) ) (s(O/l))(t(O/l))x, such that \T\= ( C W ) .Hence 11.4 implies the following theorem.
w . - u ‘ { k } is finite. ( 9 0 ) ; = 0 for each
1 1.5: Let 9 = Acs + A m . Then the o-valid equalities THEOREM of L I (ire not recursively enumerable.
One way of specifying a transformation a in Acv is to give that k such that o . - a - ’ { k } is finite together with those pairs ( a ( ; ) ,i ) such that a ( i ) # k . One way of specifying a transformation a in Acs is to give the least set { ( a ( i ) i, ) : i s k } such that a ( j + k ) = a ( j ) + k for each j < w. Now let Y = Acs +Acu and assume that the symbolism of L, uses these two ways of specifying the transformations in A c v or Acs, respectively. Then each of TBO, ..., TB9 is a decidable set of equalities of L,. For TB6 and for TB8 this can be verified. and for the others this is obvious. Hence 1 1.5 yields the following incompleteness theorem.
+
THEOREM 1 1.6: Let 9= Acs Acv. Then some w-valid equalities of L, are not derivable from TB,. One may regard each of the axiom schemes of TB,, and also each of the theorem schemes of ch. 9, as defining a set of equalities of L, by The applying a language 2’about transformation semigroups to 9. syntax of 9does not depend on Y .T h e connection with Y is made by making 9‘the range of the variables for transformations and, if desirone able, by making I the range of the variables for indices. In 9, employs in certain ways (which were not specified) vocabulary for certain set-theoretic operations o r relations to formulate conditions (or ‘provisos’) on transformations and indices. Among the settheoretic notions may be those of image and of pre-image under a mapping, of relative product and of converse, of cross-section and of confinement, of eqv and of C . T h e conditions, if any, employed by a scheme are such that, for each set I and each semigroup Y of transformations on I, the scheme defines a set of equalities of L9 which are I-valid. and one should thereT h e notion of a scbeme thus depends on 9, fore talk about 2 - s c h e m e s . It seems plausible that there are 9 such
111
CH.
S O M E CASES OF INCOMPLETENESS
I79
that each of TBO, ..., TB9 is an 2'-scheme and such that the w-valid equalities of L4r.a+Acr. are not axiomatizable by a set of liP-schemes that is decidable. T h e argument for 11.6 depended on the decidability of the sets such TB6, and TB8, when 9= Acs + A m . There are semigroups 9, (of ch. 9) for non-denumerable K and infinite I, as the semigroups T K where these two sets are not decidable. For these 9, the completeness of TB,, or of axiom sets obtained by adding to TBO,. ..., TB9, finitely many other axiom schemes, is an important open problem. One can also use 11.6 to show that (even when 11111 2 S,,) certain conditions on Y are not sufficient for the completeness of TB,. For Of these, the last three this purpose we now list six conditions on 9. are implied by S7, while the first three will be used in place of S4 but are not implied by it. For example, S4' and S4" fail for5' = Acs.
S4'. For every a in Y such that run a # I there is some y in Y such that run y = -run a. S4". For every a in Y which is not 1- 1 there is some y in Y such that ran y = { i : ( i , j ) E a-a for s o m e j # i } . S4"'. For every a and p in Y there is some y in Y such that run y is a cross-section of a-awhich favors run p. S7'. For every a and p in Y there is some y in Y such that y - y = equ ( p - p . -a-a). S7". For every a and p in Y there is some y in Y such that y - y = (a-a)r(runp). S7"'. For every a and p in Y there is some y in Y such that y - y is the strict confinement of a-ato run p.
LEMMA11.7: If Y = Acs+Acu, then Y satisjies the conditions SO, S1, S2, S3, S4', S4", S4"',S5, S6, S7', S7", S7"'. Proof: Let Y = Acs+Acu. If a E Acu, then ap E Acu and Pa E Acu for every p E 9. Hence Y = c l Y . One can show that each a E Acu is a product py such that y is in Acu and is idempotent and such that p is a permutation of w which has finite support. Hence Y satisfies SO. Since A c s and Acu are regular, so is their union 5".Clearly, {run a:a E .V}is the set of those J # @ where eitherJ or -J is finite. Also, {a-a:a E Y}is the set of those M = equ M such that either M -id or ( I X I) * -A4 is finite. One now verifies easily that Y satisfies the remaining conditions. 0
-
I xo
S O M t CASES O F INCOMI'I E T E N t S S
[CH.
11
I n ch. 10 it was assumed throughout that 11111 B 3 and that Y satisfies SO, .._,S7. We now show that this assumption can be modified. In contrast to 11.6. it follows (using also 11.7 and 10.16) that TB,,.,. ,ct. is complete with respect to those equalities which involve only transformational operations. Thus, further axioms for \L,4,.,v+ would have to involve transformational and Boolean operations.
THEOREM 1 1.8: Throughout ch. 10, the ussumption thut .4p sutisjies SO, ..., S7 cun be replaced b y the ussumption thut Y sutisjies SO, S1,
S2, S3, S4', S4", S4"',SS, S6, S7', S7". S7"'. Proof: In ch. 9, S7 is not used as hypothesis, and S4 is a hypothesis of 9.6(i), 9.10(b) and 9.10(c) only. The proof of 9.10(b) shows that S4' can be used in place of S4. For 9.10(c) one can also use S4' since S4 enters the proof of 9.10(c) only indirectly, namely through the use of 9.10(b). Thus, the only result of ch. 9 whose use in ch. 10 requires modification is 9.6(i). These uses occur in the next to last paragraph before 10.2 and in the proof of 10.2(b) and 10.3(a). Instead, one can use in these places the condition that each ( D k ) is in 9, which follows from SS and S4', and the condition that { r u n a: a E Y } is closed under which follows from S4', 9.6(h), and id E Y. The use of S4 in the proofs of lG.2(b) and 10.3(a) can be avoided similarly. T o prove 10.5 one proceeds as follows. By S7"' and S4', there are a(, and a2 in Y such that a2"a2is the strict confinement of a'a to - r u n p and a,;-a;,the strict confinement of a - a to run p. Then, by S7'. there is some y' in .Ysuch that y ' - y ' = id+ (a-a.-ah-a,!, s-az-az). By S4"', there is some S" in 9'such that run 6" is a cross-section of y " y ' which favors run p. Since { r u n a: a E Y }is closed under+, and by S4', there are 6 and 6' in 9 such that run 6 = run 6" + r a n p and run 6' = run S"+-run p. By S7", there is some y in Y such that y ' y = ( y ' - y ' ) f ' ( r u n S'). Then run 6 is the unique cross-section of y - y which favors run p. Also, by S7", there is some a. in Y such that ao-a,,= ( a - a ) f ' r u n p . By S4' and the closure of { r u n a : a E Y } under there is some p' in Y such that run p' = run p+-run al. The rest of the proof then goes through unchanged. When a is 1-1 and hence a - a = id, then 10.6(b) can be proved easily. When a is not I - I , then, by S 4 , there is some 6 in Y such that run 6 = { i : ( i J ) E a - a for some j # i } . Replacing uses of S4 by uses of S4' and of the fact that { r u n a : a E Y } is closed under+, one can then prove 10.6(b)as before.
+,
+,
CH.
I I]
SOME CASES OF INCOMPLETENESS
1x1
There are no further uses of S4 in ch. 10. T h e only further uses of S7 occur just prior to 10.7 and in the proof of 10.7(b). In both of these places, one may use S7" instead.
In conclusion, we turn to the case where 3 C 11111 < K O and Y = '1. Utilizing ideas of Monk in [211, Johnson obtained in [I71 an incompleteness result for a language which differs from \LJ only in the choice of primitives. His result therefore can also be applied to \Ly\ and implies the incompleteness of TB,. Note that, by 9.5 and 10.16, TB, is complete with respect to those equalities which involve only transformational operations. THEOREM 1 1.9: Assume that 3 c 11111 < K,,and that Y = ' I . Then there is n o finite set E of I-valid ryuulitirs of L, from which each I-valid equality of L,is derivable. Proof: Assume that 3 d ((Ill < K,,and let Y = 'I. Let D1, ..., D7 and PD9 be as described in [9], and let Lhbe a language appropriate for PD,. Note that PD, is a finite set of equalities of L&.Let tr be the mapping of the terms d L$into terms of L, which corresponds to D 1, D2, D3, and let tr' be the mapping of the terms of L,into terms of Lkwhich corresponds to D4, D5, D6, D7. By the part of Theorem 28 of [9] which concerns D1, D2, D3. if p is any term of L;, then from PD, one can derive tr' ( t r p ) = p. Now suppose there were a finite set E of I-valid equalities of L, from which each I-valid equality of I-, were derivable. Let E' = {tr' u = rr' T:u = 7 is in E}. Consider any equality po = p, of L; which is I-valid. Since for each U . t r p , , and p,, denote the same ooperation and t r p , and p1 denote the same o-operation, therefore t r p , = t r p l is I-valid and hence would be derivable from E. Then tr' ( t r p " )= tr' ( t r p , ) would be derivable from E', and hence p,, = pI from PD, + E ' . Hence PD,+E', which is a finite set of I-valid equalities of I-',. would be complete, thus violating Theorem 3.5 of[17]. 0
BIBLIOGRAPHY
[ I ] P. BERNAYS.Uber eine natiirliche Erweiterung des Relationenkalkuls. in: A. Heyting, ed., C'onstruc.tiuit.v in Muthemurics (North-Holland, Amsterdam, 1959) pp. 1-14. 121 E. BETH. On Padoa's method in the theory of definition. Koninkl Ned. Akad. Wetenschap. Proc. Ser. A 56 (Indtrg. Mtrth. 15) (1953) 330-339. 131 G. BIRKHOFF. Lutric.e Theory. Am. Math. Soc. Colloq. Publ. 25 (Am. Math. SOC.. Providence. R. I., 1961) xix+283 pp. [4] G . BOOLE.The mathemuticul unulysis of logic. being an essay toward a calculus of deductive reusoning (London, 1847) 82 pp. (Reprinted in: P. E. B. Jourdain, ed., Geur,ve Roole's Colloctrd Logiccrl Works 1: Open court, Chicago. 1966.) 151 A. H. CLIFFORD and G . B. PRESTON,The Algehrtric Theory of Semigroups 1 (Am. Math. Soc.. Providence.R.1.. 1961)pp. 1-224. [6j W. CRAIG.Three uses of the Herbrand-Gentzen theorem in relating model theory and proof theory, J. Symbolic Logic 22 ( I 957) 269-285. 171 W. C R A I GBoolean , notions extended to higher dimensions, in: J . W. Addison, L. Henkin and A. Tarski. eds., The Theory of Models (North-Holland. Amsterdam, 1965) pp. 55-69. [ 8 ] W. C R A I GT. w o complete algebraic theories of logic. in: B. van Rootselaar and J. F. Staal. eds.. Logic. Methodology trnd Philosoph.v o f Science (North-Holland. Amsterdam. 1968) pp. 23-29. [9] W. CRAIG.Unification and abstraction in algebraic logic. in: A. Daigneault. ed., Studies in Algebruic Logic (Math. Assoc. Am., 1974). [I01 W. CRAIG.Diagonal relations, in: L. Henkin. ed.. Proc. Tarski S y m p . (Assoc. Symbolic Lo,yic. Proridc,ntx,, R . 1.. 1973). [ I I ] R. FRA'ISSL. Applications des y-operateurs au calcul logique du premier echelon, Z. Math. Logik u. tirundl. Math. 2 (1956) 76-92. [ 121 R. FRAISSE,Relafion, formule logiyue, compacitk, comple'rude (Gautiers-Villars, Paris, 1968) xii + 186 pp. [ 131 P. R. HAL.MOS,A/gebruic Logic (Chelsea, New York, 1962) 27 I pp. Cylindric algebras, in: Lattice Theory (Am. Math. [I41 L. H E N K I Nand A. TARSKI, Soc., Providence, R.I., I96 1 ) pp. 83- 1 I 3. 1151 L. H E N K I N D. . MONK and A. TARSKI, Cylindric Algebras I (North-Holland, Amsterdam. 197 1) vi 508 pp. [I61 C. M. HOWARD,An Approach to AIgebraic Logic, Ph.D. thesis, Univ. of California, Berkeley, Calif. (1965). [ 171 J. S. JOHNSON,Nonfinitizability of classes of representable polyadic algebras, J. Symbolic Logic 34 ( I 969) 344-352. [ I S ] B. J ~ N S S Oand N A. TARSKI. Boolean algebras with operators I , A m . J. Marh. 73 (195 I ) 89 1-939.
+
182
BIBLIOGRAPHY
I83
[ 191 S. C. KLEENE, Introduction to Metumtrt/ic,mtiticJ (van Nostrand. North-Holland.
P. Noordhoff Amsterdam and Groningen. New York and Toronto. 1952) 550 pp. [201 TH. LUCAS,Sur I’equivalence des algebres cylindriques et polyadiques. Bull. Soc. Math. Belg. 20 (1968) 236-263. [211 J . D. MONK,Nonfinitizability of cylindric algebras, J . Symbolic Logic 34 (1969) 33 1-343. [22] A. TARSKI. Some notions and methods on the borderline of algebra and metamathematics, in: Proc. Intern. Congr. Math. Cumbrufge. Muss. 1950. vol. l (Am. Math. SOC.,Providence, R.I., 1952) 705-720. On definable sets of real numbers, Logic, Semuntics, Metumuthe1231 A. TARSKI. mutics (Oxford Univ. Press, London, 1956) pp. 110-142. x
+
INDEX OF SYMBOLS
(Symbols are arranged by page of first occurrence. Some descriptions are not wholly accurate.) identical with, 5 E member of, 5 { .s: .. . .s ... } set abstraction, 5 (f'(.s):s E S ) . ( f ( L Y ) ) , e $ functional abstraction, 5 value off'for ,Y, 5 f b ./I .y ) f s ( r .s ) ordered pair, 5 dom R domain of R , 5 r(111 R range of R , 5 K *s image of S under R. 6, 150 set inclusion, 6 0 empty set, also null element, 6 , 8 3 C Y . /3. y . ... ordinals, also transformations, 6, 120 i.,i. X . ... finite ordinals, also elements of index set, 6, 120 least infinite ordinal, 6 U universe (non-empty), 6 'I'U set of functions from T into U , 6 CJ set of sequences with terms in I/ and of length a , 6 u set of sequences with terms in U and of length < a , 6 sequence of length ti. 6 ( ,L . .. . / ; , ~ ~) i sequence of length W , 6 ( f k .A. . ..) sequence of length a , 6 or ( segment of sequence from CY to y , 6 (./;j)
3
c
(tJ
(y
l(1
1
f ; j ) /j<
1 X4
INDEX OF SYMBOLS
t
< =z r)
Pr
rk
L, V(),
... ,V,(, ... ,n < w
&
XI),
... , XS, ... , 6 < r )
x, Y 1 A V
3 v,
cp,
31, x, ...
185
concatenate of a set with a sequence, 6 decatenate of a set with a sequence, 6 set-theoretic or Boolean sum (union) of a class, 6, 83 set-theoretic or Boolean binary sum (union), 6, 27, 80, 83, 104 set-theoretic or Boolean binary product (intersection), 6,27,80, 83,104 complementation, 7, 27, 80, 83, 104, 120 less than, 7 less than or equal to, also Boolean inclusion, 7,83 a fixed infinite limit ordinal, 7 pairing function, 7 rank, 7 language for first order logic with equality, 7 individual variables of L,, 7 equality symbol of L,, 7 predicate symbols of L,, also variables of algebraic language, 7,28 same as x,,, x, respectively, 7 negation symbol, 7,29 conjunction symbol, 7,29 disjunction symbol, 7,29 symbol for existential quantification, 7 expression for implication, 7 expression for equivalence, 7 expression for universal quantification, 7 formulas of L,, 7
I86
INDEX OF SYMBOLS
i La'/
B #
ni Ci. P',
,
5
Q 'I
% .
+i s .I s
-
CI
1-1 llue
tm
s
least r such that i < r for each v, free in Ji, 7 operation of relational type denoted by A, 7, 8, 26 L with interpretation j Ji 1 of its , set 'of operaformulas ~ ialso tions ! Ji [,8 relational, lo-,or o-structure, 8, 22, 103 not a member of, 9 not identical with, 9 restricted (i, i + 1 )-diagonal element, 10 restricted i-th cylindrification, 10 restricted projection on the right, 10 conjugate of restricted projection on the right, 10 restricted set-theoretic sum, 10 restricted set-theoretic product, 10 restricted complementation, 10 theory of valid formulas of L,, 12 identity operation of a relational type, 13 constant operation of a relational type, 13-14 closure under substitutions or compositions, 14, 24, 103, 105 one-to-one 19 uniform virtual extension, 21, 23 mapping of the formulas of L, into terms of algebraic language, 22,30,105 augmented cylindric language, 22, 28 lo-operation denoted by A, 22, 26, 29
,
INDEX OF SYMBOLS
I T / of its terms, also set of operations IT^. 22,29 trivial extension, 22 identity Iw-operation, 24 constant Iw-operation, 24 end of proof, 24, passim quasiterms, Iw-quasiterms, or Wquasiterms, 2 5 , 2 6 , 103 Boolean unit, also set of finite, W-, or /-sequences, 27, 80, 83, 104 i, j-diagonal element, 27, 104 0,l-diagonal element, 27, 80, 104 i-th cylindrification, 27,80, 104 projection, 27,80, 104 conjugate of projection, 27, 80, 104 r-th iterate of Q, 27 set of sequences of length 3 r, also Q”-image of Boolean unit, 27,84 substitution operation, j for i, 27, 104 terms of algebraic language, 28, 121, 150 symbol for Boolean sum, 28, I2 1 symbol for Boolean product, 28, 121 symbol for complementation, 28, 121 symbol for Boolean unit, 28, 121 symbol for 0,l -diagonal element, 28 symbol for i-th cylindrification, 28 symbol for projection, 28 symbol for conjugate of projection, 28 Lpqwith interpretation
trr / ;I K;I
0 6,6 1 9 . .
R Di.; D Ci
P
Q
Q”
Q”Z
Si p , u , 7 , ...
+ 1 d
I87
I88
INDEX OF SYMBOLS
symbol for equality, 29 expression for Boolean inclusion, 29, 121 expression for converse of Boolean inclusion, 29, 121 expression for null element, 29 expression for r-th iterate of Q, 29 expression for i,j-diagonal element, 29 expression for substitution operation,jfor i, 29,60 lo-valid, also (w-consequence, 29 range restriction of F to length Y,
2,
0 g'
4
I
Sl
31
I I ? m ( s , ..
. . , s,,,)
BP E P9 I (a),.. . ,3(c) 1-,
E, 2(f)q
t
operation obtained by summing values, 3 1 operation obtained by summing disjoint values. 32 a set of operations of the above kind, 32 a-successor, also a-successor of trivial extension, 32,33 set of lo-operations reducible to an operation in S , 34 maximum of s , , ... ,s,,,, 35, 52 Boolean part of Epq, 46 axiom set for I L,, 1-46-47 equalities in E,,, 46-47 p-free sublanguage of L,, ,47 adjustment of E,, to L,, 47 E,-substitute for 2(f), 47 derivable, 47, 48, 81, 118, 122, 151 l-p=aand k a = ~ , 4 8 result of driving q inward in p, 50 definition of S ; T , 60 sentence resulting from substitution into cp, 67
INDEX OF SYMBOLS
(Ti,... ,rk-,; m 17)
term mimicking substitution of individual constants, 6 7 , 6 8 term mimicking substitution of individual constants, 68 a fixed sequence of terms, 68 a fixed sequence of sets of terms, 68 universal closure, 79 algebra, 80 algebras, 80 algebra with designated elements, 80 D , ... of algebra ?I,80 formula expressing atomhood, 8 1 set of elements S-equivalent to X , 87,98 quotient algebra of YI over S, 87, 98 ideal generated by S, 87 set of elements disjoint with each element of S, 87 congruence relation corresponding to an idea, 87 Iw-closure, 89 subset of elements of rank m, 90 set-theoretic product (intersection) of a class, 91 n-th projection, 93 conjugate of n-th projection, 93 algebra of terms, 98 w- or I-operation denoted by A, 101, 103,105, 121,151 Lpq with interpretation \7\ of its terms, also set of operations \T\. 101, 105 composition, 102 set of almost constant shifts, 102 o-,lo-,or I-operation of a-substitution, 102, 1 1 1, 119
+,
YIJS
[Sl Scgr
189
190
Acs
thr a
I L.l,.Sl
9
I J, K, J', ... M. N, MI, ...
id X
M'
INDEX O F SYMBOLS
conjugate of (Sa),102, 1 1 1 , 1 19 identity @operation, 103 constant w-operation, 103 replacement of i byj, 104 transposition of i andj, 104 successor transformation, 104 predecessor transformation, 104 predecessor from r on, 104 r-th iterate of a, 104 language L, f0r.Y = A c s , 105,121 L,,., with interpretation \T\ of its terms, also set of operations\T\, 105 o- or I-valid, also w- or I-consequence, 105, 119, 151 set of nondecreasing almost constant shifts, 109 lo-operation of a-substitution, 109 conjugate of ('Sa),109 a-induced partial mapping of finite sequences, 1 10- 1 1 1 threshold for (Y, 1 1 1 Ls,, with interpretation 171 of its terms, also set of operations (71, 111 axiom set for\L,\, 117 equalities in E', , 1 17 adjustment of E', to Lq, 1 18 J-cylindrification, 1 19 M-diagonal element, 1 19 intersection with M-diagonal element, 119 a fixed set of transformations, 119 a fixed index set, 1 19 subsets of /, 120 subsets of I x I, 120 identity transformation on I , 120 Cartesian product, 120 converse of M, 120
INDEX OF SYMBOLS
a* a-' eqv M
so,S l , ..., s7 =f
c,
tr
uMn
*
\T\
19 I
a-image, 120 a-preimage, 120 equivalence relation generated by M , 120 confinement of M to J, 1 2 1 language for transformational operations resulting from .Y and for Boolean operations, 121 L, with interpretation \T\ of its terms, also set of operations\T\, 121 symbol for (Sa),2 1 symbol for ( T a ) ,12 1 term associated with IlUll s 1 , 12 1 a-analogue of@, I 2 1 axiom schemes for transformational and Boolean operations, 121 Boolean part of TB, 122 TBO+ ... +TB9,122 TBO+ .._+TBS, 122 cardinality of J , 129 set of transformations with support of cardinality less than K , 129 conditions on Y , 129 9-congruence, 142 =ib-cylindrification, 143 translation from L,, into LACS, 145 diagonal relation determined by M , 149 symbol for UaD and for ( S a ), 150 symbol for Ua-1and for ( T a ) , 150 language for transformational relaalso tions (resulting from 9, language for transformational operations, 150 transformational relation denoted by T, 151
192
TO,.. . T7
S4',..., S7"
INDEX OF SYMBOLS
axiom schemes for transformational relations (operations), 151 TO+ ... + T 7 , 1 5 1 dual of p, 15 1 term for Ilcr-aD and for ( E a ) , 152 term for Baa -pp'U and for ( C ( r a n a . run p)), 152 transformation having constant value k , 152 diagonal relation determined by (Mo,M i , M Z ) , 162 first infinite cardinal, 173 union of L,, and L , r e , 173 successor from r on, 173 term associated with a finiteness condition, 173 relativization of JI, 175 iy for universe I/, 175 set of transformations having almost constant value, 177 conditions on .Y, 179
INDEX OF NAMES, PHRASES, SUBJECTS
Major references and references to explicit or implied definitions are given in bold face. axiom set E,,. 3.46-47 abstraction, levels of, 12 addition of non-equational agree, 126 axioms, 79, 80 algebra, 80,143 as a set of one-premise rules, 3 Lindenbaum-Tarski, 4 , 7 9 47-48 of all subsets, 84,143 Boolean part, 46 of formulas, 4,79 bounding the length of axioms, of sets, 4,79,84,143 66 of terms, 98 completeness, 46, 47, 48, 67, 76 of a theory, 4,79,99 with designated elements, 80 consequences of atomhood of - Q X , 82,84,94 algebraic language, I , 2 algebraic theory, 2-3 dimensionality of schemes, 66 algebraization, 2, 2 1-26, 35-39, modifications, 66 101-104 redundancies, 66 almost constant shift, 102 soundness, 46,47,48 axiom set E,, 47 almost constant value, 177 consequences, 48-65 analytic, 48 applicability of theorems of logic, consequences not involving 12 axioms for diagonal eleassociativity axioms, 15 1 ments, 48-56 assumptions; see conventions, near-completeness, 48, 67, 76 conditions soundness, 47 atom of an algebra, 83 subset adequate for reduction, atomic, 94 76n2 augmented cylindric theory for axiom set EL, 3,117 sets of finite sequences, 46 completeness, 117 autonvmv. conventions for, 7 soundness. 117 193
I94
I N D E X OF N A M E S . PHRASES, SUBJECTS
axiom set El. 118 near-completeness. 118 axiom set TB,, 3. 120,121-122 additional interpretations, 122I23 cases of irredundancy of TB9, 120,144-145 cases of redundancy of TBY, 142 completeness when Y = Acs, 120, 147 consequences, 123- I42 decidability of members hip, 178, 179 incompleteness for some . Y , 3 , 178,181 levels of generality. 123 relationship to axioms in current use. 122, 124, 125, 126, 133, 137 soundness, 122 axiom set TB,, 120,121-122 case of irredundancy of TB7, I36 cases of equivalence to TB,y. 142 consequences. 123- 140 completeness for transformational operations, 149, 169, 180 completeness, without TB7, for local operations, 120, 135 equivalence to axioms for polyadic algebras with diagonal elements. 120. 140 axiom set T, , 149,151 cases where derivability decidable, 171
completeness, 3-4, 149, 168, 180 duality, 151 interpretations, 151 soundness, 151 base, 79,84 Bernays, P., 3n, 4Xn Beth, E., 43,44, 1 18 Beth’s theorem; see definability , interpolability Birkhoff, G., 93 Boole, G.. I , 12n3 Boolean ideal, 90 Boolean null element, 83 Boolean part of axiom set, 46, 117,122 Boolean unit, 21,83,104 bounded, 41 1 -bounded equality representing a sentential combination, 42 bound for indices of variables free in a formula, 7 canonical. 163 canonical presentation of diagonal relations, 165 cardinality, 129 Cartesian product in an algebra, 93 characterization of algebras of maximal proper theories, 99 algebras of sets, 4n, 7 9 , 8 5 , 8 9 , 96,99 algebras of theories, 99 representable algebras, 4 n , 79, 92,96,99
INDEX OF NAMES, PHRASES, SUBJECTS
characterization of: (cont.) operations in I L,,I, 3 1.39 operations in \Lpq\. 107,113 singletonic set algebras, 95, 96 theories, 98 theories maximal among proper theories, 97 closed under composition, 104, 119 closed under an operation, 83, 149-150 closed under substitutions, 14,24, 103 closed under the Iw-rule, 98 closed under VE’ k, 98 lo-closed, 89 closure under substitutions. 14, 24,103 Iw-closure, 89 commutativity with substitutions, 21,24,35, 101,103 compactness, 3 I , 42,97,107 without finiteness of consequence relation, 43, 108 complementation, 7, 27, 80, 104, 120 restricted, I0 complete algebra, 83 completely additive, 84 completeness: of axiom sets; see axiom set of a theory, 3 for bounded equalities, 80, 82, 8211.96 for negations of equalities, 7980,96 open problems, 169, I79 i-th component in an algebra, 93
195
composition, 102 concatenation, 6 conditions on set Yof transformations, 129, 179 consequences, 130 confinement, 121 confinement, strict, 156 congruence relation, 87 conjugate, 2, 84 of projection, 27,104 of restricted projection on the right, 10 of substitution operation. 102, 109,111,119 consequence of axiom set: see axiom set, derivability lo-consequence, 2 9 , 3 1 w-consequence, 105 consistent (with respect to Eq).68 constant function, 44,108 constant operation of a relational type, 13-14 constant lo-operation, 24 constant o-operation, 103 C, -contraction of an algebra, 143 conventions for or of: autonymy, 7 ch. 10,149,150 chs. 9- 1 1,120 composition, 102,120 indices, 60, 120 iteration, 27,29 juxtaposition, 7,120,150 language L,, ,29 language L,y,121 omitting reference to algebra, 84,87 parentheses, 6,7,29,150
196
INDEX OF NAMES, PHRASES, SUBJECTS
conventions for o r of (cont.) proofs of derivability, 48. 123, 154 converse, 2,120 correspondence between: algebras of sets and algebras of complete theories, 99 algebras of theories and representable algebras, 79, 92,99 lo-closed ideals and Boolean ideals of rank 0.90 congruence relations and ideals, 87-88 operations of type ( ri)isn,and operations of another kind, 19 (w-operationsand sequences of range-restricted Iw-operations, 32 reachable homomorphic images and Boolean ideals of rank 0, 91 lo-structures and relational structures, 40 terms of LP4and sequences of formulas of L,, 40 transformational operations and transformational relations, 150 cross-section of an equivalence relation, 121 cylindric algebra (o-dimensional), 2. 3. 46. 54. 76n3, 106, 114nl cylindrification, 27, 80, 104, 119, I43 restricted, 10
decatenate, 6 decidability of: membership in axiom set TB,. 178,179 identity of transformational operations, 171 J-decomposition of an equivalence relation, 156 deferred predecessor transformation, 104 deferred successor transformation, 173 definability, implicit vs. explicit, 31,43,44, 102,108 definability of primitives, 66, 11911, 121 denotation: abstracted from mode of composition, 12 competing choices, 16-20 not always preserved under replacement, 9 of a first-order formula, 1 , 7, 8 of a quasiterm, 26 of an lo-quasiterm, 26 of an w-quasiterm, 103 of a term in an algebra, 80 of a term of lLpql, 29 of a term of \Lw\, 105 of a term of L ,,121 of a term of LT,, 151 see also operation denotational vs. model-theoretic aspects of a language, 1 , 13, 16, 177 derivability from: a set of equalities, 47, 81, 122, 151
INDEX OF NAMES, PHRASES, SUBJECTS
derivability from: (cont.) axiom set TBO ... TB5, 123-125 axiom set TBO + ... +TB6, 123-128, 131-132 axiom set TBO ... TB6 TB8, 123-128, 131-136 axiom set TB;, 123-128,131140 axiom set TB,, 123-128,131141 derivation, based on a set of equalities, 47 designated elements in an algebra, 80 rn-development, 52 diagonal element, 27, 80, 104, 119 intersection with, 119 restricted, 10 diagonal relation, 162 canonical presentation, 165 direct product, 92 domain, 5 duality, 151 dual of a term. 151
+ +
+ +
+
effectiveness of mapping of formulas into terms, 2, 22, 30, 105 empty set, 6 equality, 3,28-29,12 1 as a one-premise rule, 3,47 symbol for algebraic languages, 29, 121 symbol for first-order logic, 7 equational, I , 2,3,48n equivalence relation, 120 confinement of, 121
197
cross-section of, 121 J-decomposition of, 156 determined by a transformation, 120 generated by the image of an equivalence relation, 12 1, 129, 131 generated by a relation, 120 strict confinement of, 156 eventually uniform, 34 extension: by finite set of axiom schemes, 179 of a function, 21 of a theory, 3 trivial, 21 uniform virtual, 2 I , 23 virtual, 21 faithfulness of interpretation, 2, 4,22,101 favors, 155 first-order logic with equality, I , 7 defect of associated algebras of formulas, 79 deficiency in expressive power, 12,13 imperfect formalization of identity of operations, 5 , 13, 22, 79 operations associated with a formula, 5,743, 16-20 theory Ta, I2 see also language L, , language I
0
formula of language L3, 7 Fraisse, R., 8,25
I98
INDEX OF N A M E S . PHRASES. S U B J K T S
Frege, G., I , 1 I function, 5, 12 functional abstraction, 5 function in an algebra, 93 function symbol, 2, 28, 121, 150, 173 Galloys, J., I generating set. 2, 14. 24, 103, 104 for almost constant shifts, 104 for diagonal relations, 172 for nondecreasing almost constants shifts, 110 for operations in jL, 15 for operations in /Lpq1.22, 28, 1 0 9 , l lI for operations in \ L ~ ~ \1.0 1 , 104, 105 for transformational operations, 120, 146n for transformations in . Y , 129 Giidel, 14, 36
:,
Halmos, P.. 102, 122, 125, 133, 137,140 Henkin, L., 67 Henkin-type construction, 67-75 Henkin-type model, 75 homomorphism, 83 Howard, C., 4n, 17n, 27, 4811, 1 1911, ch6 passim ideal: Boolean, 90 generated by a set, 87 of an algebra, 87 on a set, 142 proper, 142
proper for a set of transformations. 142 trivial, 142 .!/-ideal, 142 idempotent, 128 identity operation of a relational type, 13 identity Iw-operation, 24 identity w-operation, 103 identity transformation, 120 image of a set under a relation, 6,120,150 immediate subquasiterm, 25 incompactness, 18,96 individual constant. 150 individual variable; s e o variable interpolability, 3 1,44, 118 without Beth’s theorem, 3 1,44, 118 isomorphism, 83 iteration, 27,29 Johnson,J. S.. 173, 181 juxtaposition, conventions of, 7, 120,150 Kleene, S. C., 14, 19 Knoebel, R. A., 88n language La, 7 language j L,! . 8 competing choices, 16-20 direct reasons for choice, 16 generating set, 15 model-theoretic equivalence with a variety of languages, 41 other denotation of formulas, 20
INDEX OF N A M E S , PHRASES, SUBJECTS
language L,,, 22,28-29 conventions, 29 language (Lpql, 2,22,29 analysis of model-theoretic relation, 99- 100 axiom set, 46-47,76 Beth’s theorem, restricted analogue, 43-44 characterization of operations, 31,35,39 compactness, 3 1,42,97-98 consequence relation not finite, 31,43 consequence relation denumerable, 43 correspondence between terms and sequences of first-order formulas, 40 definability, implicit vs. explicit, 3 1,43,44 faithful interpretability of !La/, 22,30 genesis from j L,:, 2, 21-22, 28-30 generating set, 28, 109, 111 interpolability, 3 1,44 model-theoretic equivalence to iL,j, 3 1 , 6 4 1 nd recursive enumeration of valid (bi)conditionals,177 redundancy of primitives, 66 validity for IL, reduced, 22, 30 validity implied by validity for bounded Iw-structures, 39 language L,. 47 an equivalence to L,,, 77115, 177 4
8
,
1
199
non-equational axiom set, 76n3 language \LPq\, 2,105 axiom set, 117 characterization of operations, 107,113 compactness, 102, 107 consequence relation not finite, 107-108 definability, implicit vs. explicit, 102, 108-109, 118 equivalence to \LA,.., 104-105 genesis from !La1, 101,104 generating set, 104,105 interpolability, 118 no recursive enumeration of valid (bi)conditionals, 177 operations related to those in ILp4), 2, 113, 114111 validity for j La j reduced, 101 , 105 validity reiated to validity for JLp,I, 114-1 17 105,121 language LACS, language\L,,,\, 2,105,121 axiom set, 12 1, 147 characterization of operations, 107 equivalence to \ L,,\, 104-105 genesis from j La:, 101, 104105 validity implied by validity for ILACSl, 114 language L,, 121 conventions, 121 language \L ./.\,3,121 axiom set for local operations, 136 case of axiomatizability , 147
200
INDEX OF NAMES, PHRASES, SUBJECTS
language \L,\, (cwnt) case of nonaxiomatizability, 3, 178
definability of cylindrifications, 121
definability of diagonal elements, 121 language LT, 150 axiom set, 151, 168 cases of of finiteness, 171 closure properties, 171 decision method, 171 generating set, 149-150,160 interpretations, 150-151 normal forms, 161 2-validity implies validity, 171 least upper bound, 83 left inverse, 128 Leibniz, G. W., 1 length of pprefix, 50 length of sequence, 2,6,27 levels of abstraction, 12 Lindenbaum-Tarski algebra, 4, 79 local operation, 135 Lucas, Th., 133, 140 mapping of formulas into terms, 22,2526,105
maximal among proper ideals, 90 maximal among proper theories, 97
maximal consistency, 67 analogue, 73 maximal proper extensions of a theory, 98 McKenzie, R., 80n, 96, 107, 10811, 173
mode: and abstraction, 12 indicated by a formula of L, , 5 , 10-11
of composition, 9, 10 of determining the value of an operation, 9, 10,47 relationship t o Frege’s sense, 11
relationship to syntactical structure, 10, 1 I , 16,17n, 18,20 small changes, 3,47-48 model of an equality, 80,143 model, relational, 9 lo-model, 29 o-model, 105 o-model of a term, 177 Iwnodels related to models, 81 model-theoretic equivalence: of first-order language and
I J A
1, 4&41
of IL,( and ILqI,77n, 177 of \Lw\ and \Lq\, 77n, 177 with difference in denotative power, 40 model-theoretic vs. denotational aspects of a language, 1, 13, 16, 177 Monk, D., 181 monomorphism, 83 natural homomorphism, 87 nearly complete, 48,53,118 neat embedding theorem, 3,76n3 non-commutativity of operations (‘Sa)(’Ta),I10 nondecreasing almost constant shift, 109
I N D E X OF N A M E S , PHRASES, SUBJECTS
non-equational, 48n, 76113 n-normal. 51 normal form for transformational operations, 150,161 normal term, 50 normal transform, 50,51,76-77 null theory, 97 occurrence in a sequence, 26 one-to-one on a set, 137 operation: denoted by a formula of L,, 7-8 denoted by a quasiterm, 26 elementary, 8 in j ~ ~ / , 8 local, 135 logical of Fra'isse, 8 of a relational (similarity) type, 8 of (similarity) type ( Y ~ ) ~ ~ , , , ,8 transformational, 119 7-ary, of a relational type, 8 lo-operation, 21 denoted by an lo-quasiterm, 26 denoted by a term of L,, , 2 9 in I L p q l , 29 m-ary, 21 q-ary, 22 o-operation, 17,32 denoted by an w-quasiterm, 103 denoted by a term of L,, 105 in \Lpq\, 105 m-ary, 17,32 I-operation, 119 denoted by a term of L,, 12 1 in L,, 121 ordered pair, 5
20 1
order type of sequence; see length of sequence ordinal, 6 pairing function, 7 parentheses, conventions for, 6, 7, 29, 150 partial mapping offinite sequences induced by a transformation, 110 E-path, 47 Peirce, C. S., 1 Pigozzi, D., 20, 76n4 Platonism, avoidability. 12n polyadic algebra with generalized diagonal elements, 2, 3, 106, 120,140,147,149 practically identical, 21, 24-25 practically one-to-one, 22, 24-25 precanonical, 163 predecessor transformation, 104 predicate symbol of L, , 7 pre-image, 120 pprefix, 50 preserves an operation, 83 projection operation, 2,27,104 on the right, restricted, 10 proof theory, 1, 16 proper ideal, 142 proper subset, 90 m-proper subset, proper theory, 97 quantification, infinite, 4 quantifier, 1,7 quantifier-free part of logic, 135 quantifiers and natural languages,
1
202
I N D E X OF N A M E S , PHRASES, SUBJECTS
quasi-atom, 51 quasi-atomic occurrence, 51 quasiterm associated with a formula of L,, 11 quasiterm of a relational similarity type, 25 1 w-quasiterm, 26 w-quasiterm, 103 quasivariable, 25 quotient algebra, 87 range, 5 rank: associated with an ordinal, 7 in an algebra, 90 of a formula, 4,7,79 ofa predicate symbol, 7 of a quasiterm, 25 reachable, 83 reduces, 34,39 reducible, 34 reduction of first-order validity: to validity in an algebraic language, 1 , 2, 22,30, 101,105, 106 to derivability in an equational theory, 1-2, 3, 45-46, 76, 117, 120,147 reflexivity of equality, 133 regular, 129 relational structure, 8 relative product, 120 replacement in a sequence, 26 replacement transformation, 104 representable algebra, 79,92 restriction of (*operation by range, 31 right augment, 159
right inverse, 128 right-reduced, 159 satisfaction, 7,8, 17, 17n scheme, 178 Schroder, E., 1 segment, 6 Seifert, R., 23 semantics, I semicanonical, 163 semicanonical term, 159 semigroup, 119, 1.50, 173 sense, I 1 sentence of L, ,7 sentential combination of equalities of L,, 29 sequence, 2 , 6 set abstraction, 5 set algebra; see algebra of sets set of finite sequences, 6,27 set of sequences of length r, 6,27 set of sequences of length 2 r, 6, 27 set of w-sequences, 6,104 similarity type: of a formula, 8 of an operation, 8 of a quasiterm, 26 singletonic, 93 n-singletonic, 93 sicgletonic in a set theoretic sense, 95 singleton in an algebra, 93 n-singleton in an algebra, 93 sorting and logic, 12n soundness: of axiom sets; see axiom set of a theory, 3
INDEX OF NAMES, PHRASES, SUBJECTS
standard form, 15 strict confinement, 156 structure, algebraic, 1,80 relational, 8 Iw-structure, 22 Iw-structure corresponding to a relational structure, 40 subalgebra, 83 subalgebra generated by a set, 83 subdirectly irreducible, 87 subdirect product, 92 subquasiterm, 25 substitution into an operation, 14, 24,103
substitution of constants mimicked, 68 substitution operation, 2, 27, 102, 104, 109, 11 1,119
substitution schemes, 14, 15, 24, 103
substitutions, commutativity with, 21,24,35, 10 1 , 103 substitutivity, 125- 126 a-successor, 3 1,32-33 reduction of behavior, 32, 33, 102 successor transformation, 104 support, 129 Tarski, A., 8, 17n term: right-reduced, 159 semicanonical, 159 associated with a formula, 22, 2526,105
of a sequence, 6 of language L,, ,28 of language L//, 121
203
of language LT,, 150 {+, *, -, 1, s, d } term, 135 (e, s, c, e)-term, 159 { s, t}-term, 169 theory, 79,97 determined by its 1 -bounded equalities, 97 theory T,, 12 threshold, 110-111 transformation, 102 with support of cardinality less than K, 129 transformational relation, 149 relationship to diagonal relations, 172 transformational operation, 119 normal form, 150,161 translation from L3 into algebraic language, 22,26,105 translation from L,, into LACS, 145 transposition, 104 trivial algebra, 83 trivial ideal, 142 trivial extension, 22-23 true in an algebra, 80
uniform from Y on, 3 1,33-34 uniformity and weak normality, 52
uniform virtual extension, 1, 2 1 , 23,34
reduction of behavior, 23-24 universe, 6,s upper bound, 83 valid, 9, 151 lo-valid, 29 w-valid, 105
2 04
INDEX OF NAMES, PHRASES, SUBJECTS
I-valid, 119 validity and empty universe, 47, 84,117 validity and analyticity, 48 w-validity related to lo-validity, 113-1 14 value of a function for an argurnent, 5
value of a quasiterm, 25 variable, 2,7,28,121 variable-binding operator, 3 , 7, 4811 virtual extension, 21 weakly n-normal, 51