Published on

15-Jun-2016View

216Download

4

Transcript

Math. Log. Quart. 41 (1995) 190 - 196 Mathematical Logic Quarterly @ Johann Ambrosius Barth 1995 Hybrid Identities and Hybrid Equational Logic Klaus Denecke Institut fur Mathematik, Universitat Potsdam, Am Neuen Palais, D-14415 Potsdam, Germany) Abstract. Hybrid identities are sentences in a special second order language with identity. The model classes of sets of hybrid identities are called hybrid solid varieties. We give a Birkhoff-type-characterization of hybrid solid varieties and develop a hybrid equational logic. Mathematics Subject Classification: 08B05, 03B15, 03C05. Keywords: Hyperidentity, Hybrid identity, Hybrid solid variety, Hybrid equational theory. 1 Introduction An identity t R t of terms of any type T is called a hybr id iden t i t y for a universal algebra A = ( A ; (ft)iE1) if t x t holds identically for every choice of n-ary term op- erations to represent some n-ary operation symbols occuring in t and t. For example, the equation (1) F ( x A Y, 2) M F ( r , 2) A F(Y, Z), where F is a binary operation symbol is a hybrid identity for every distributive lattice. Indeed, any binary term operation of a distributive lattice is induced by one of the following binary terms: 2, y, xAy, x v y . Replacing F in (1) by one of these binary term operations we get an identity in any distributive lattice. An identity t M 2 is called a hyper iden t i t y for A if t M t holds identically in A whenever all operation symbols occuring in t and t are replaced by any term operation of A of the appropriate arity. So, hybrid identities are between identities and hyperidentities. The concept of a hybrid identity was introduced by SCHWEIGERT in [4]. Hyperidentities and hybrid identities may be considered as specific sentences in a second order language with equality. In the sentence (1) the symbol F stands for a binary operation defined on A and we bind the interpretation of F to binary term operations of the algebra A. If V is a variety of algebras of a given type T , then V is called hybr id so l id if each of its identities is a hybrid identity. It turns out that hybrid solid varieties are just model classes of sets of hybrid identities. We give a Birkhoff type characterization of hybrid solid varieties and prove that all hybrid solid varieties of a given type T form a lattice which is a sublattice of the lattice of all varieties of type T. Then we develop a hybrid equational logic (a fragment of second order logic) containing the hybrid substitution rule as an additional rule and prove completeness. l)e-rnail: KdeneckeQhp.rz.uni-potsdam.de Hybrid Identities and Hybrid Equational Logic 191 2 Hybrid substitutions We will give a more precise definition of a hybrid identity using the concept of a hybrid substitution. We fix a type r = {ni I i E I, ni > 0 for all i E I}, and operation symbols {f* I i E I}, where fi is n,-ary. Let W7(X) be the set of all terms of type r over some fixed alphabet X, and let Alg(r) be the class of all algebras of type r. D e f i n i t i o n 2.1. Let I beasubset o f I . Thenan I/-hybridsubstitution o f t y p e r , (for short, an 1-hybrid substitution), is a mapping a : {f, I i E I } - W7(X) which assigns to every n,-ary operation symbol an n;-ary term, (i. e. a term constructed from the variables zl,. . .,I,,,) such that u(fi) = fi(z1,. . . ,zn,) for all i E 1. Clearly, every 1-hybrid substitution can be extended to the terms by the following inductive definition : (i) &[z] := z for any variable in the alphabet X, (ii) e[f,(tl,. . . ,tn,)l := ~I(fi)(eI[tl]~. . .,&I[tn,l) for f , ( t l , . . . , i n , ) E w ~ ( x ) . If t w t is an equation, then we denote by Z:[t x t] the set uI( j , ) = f , ( q , . . . ,zn,) for all i E 11. {b[t] x (i[t] I ul : {f, I i E I} - W T ( X ) and Let A = ( A ; ( f t ) i E i ) be an algebra of type 7. Then we define .[dl := ( A ; (uI(fi)A)iEl), Z:[d] := {u[d] I (TI : {fi 1 i E 1) - W 7 ( X ) and u( f i ) = fi(z1,. . . ,zn,) for all i E 11. For a set C of equations consisting of terms of type r and for a class K of algebras of this type we put Z:[C] = U { Z I [ t x t] I t x 2 E C}, E[K] = U{z:[Jt] I A E K}. P r o p o s i t i o n 2.2. For all sets 0 c I c I , Zz is a closure operator on sets of equations C and on classes of algebras K of type r , i. e., (i) c z:[cI, (i) K g Z:[K], (ii) C g C 3 Z.[C] Z1[C], (ii) K 5 K +- ZII[K] g ZI[K], (iii) 81 [c - I [C]] = Z[C], (iii) Z[S:[K]] = ZI[K]. P r o o f . Note that I-hybrid substitutions are hypersubstitutions in the sense of [l], i . e. mappings u : {fi I i E I} - W 7 ( X ) which assign to every nj-ary operation symbol an ni-ary term. We define the composition of two I-hybrid substitutions by 01 oh u g ( f i ) := &1[ug(fi)] for all i E 1. Further put uid : fi H fi(z1,. . . , z,,). Since b i d is an 1-hybrid substitution, (i) and (1) are clear. The propositions (ii) and (ii) are also obvious. Let A E K and let u, a be I/-hybrid substitutions. Assume that u[u[d]] = (A; ( ~ ( f ~ ) ~ ~ [ ~ ] ) i ~ ~ E Z[EI[Ii]]. Since the composition of 1-hybrid substitutions is again an I/-hybrid substitution, the algebra u[u[d]] is an element of Z:[K], and together with E[K] 5 E[E1[K]] we have (iii). The proof of (iii) is similar and straightforward. 0 192 Klaus Denecke P r o p o s i t i o n 2.3. For sets I' G I" G I , for any set C of equations and for any class K of algebras of type r we have: (i) E"[C] 2 Z'"[C] and (ii) 3"[K] 2 Z:"'[K]. 0 3 1'-hybrid identities Using I/-hybrid substitutions we can give a more precise definition of the 1'-hybrid identities. D e f i n i t i o n 3.1. Let d E Alg(r), let { f, I i E I} be a set of operation symbols, and let I' be a subset of I . Then the identity t w t ' , where t ,t ' are terms of type r , is called an I'-hybrid identity of type T in A if # [ t ] w 6."[t'] are identities for every I/-hybrid substitution cd'. If K is a class of algebras of type r , then the identity t M t' is called an 1'-hybrid identity in K if it is an I/-hybrid identity in every algebra of K. Note that @-hybrid identities are hyperidentities and that I-hybrid identities are ordinary identities. For a class K of algebras of type T and for a set C of identities of this type we fix the following notations: Id K denotes the class of all identities of K , HId'IK denotes the class of all 1'-hybrid identities of K , Mod C denotes {d E Alg(r) 1 A satisfies C} (the variety defined by C), Var K denotes ModId K (the variety generated by K) , HMod'lC denotes {A E Alg(7) I A satisfies every equation from C as an 1'-hybrid identity} (the I/-hybrid equational class defined by C), and HVarI'K denotes HMod"H1d"K (the I/-hybrid equational class of type T defined by H1d"K). By definition every I'-hybrid identity is an identity. Very natural there arises the problem to find algebras or varieties for which every identity is an I/-hybrid identity. D e f i n i t i o n 3.2. Let V be a variety of type r . Then V is called I'-hybrid solid if E"[V] = V. (If I' = 0, then V is called solid variety of type r.) T h e o r e m 3.3. Let K c Alg(r) be a variety. Then the following conditions are equivalent: (i) K i s an I'-hybrid equational class, (ii) K is I/-hybrid solid, (iii) Id K = HId'lK, i . e. every identity of K is an 1'-hybrid identity, (iv) E:"[Id K] = Id K , i. e. Id K i s closed under If-hybrid substitutions. P r o o f . The first step is to prove that for every algebra d E K there holds (2) This is true by definition of Z". The inclusion Z:"[t w t ' ] fact that t M t' is an It-hybrid identity of A, and we have (3) HId'IK = IdZ"[K]. Let C be a set of equations of type r and let A E HMod."C, i. e., every equation of C is an 1'-hybrid identity in A and thus C I d d by definition t w t' E IdZ:"[d] E"[t w t ' ] c I d d . I d d is equivalent to the H1d"A. Then E:"[C] Hybrid Identities and Hybrid Equational Logic 193 of an 1-hybrid identity. This means by (2) C C IdE.[d] and thus A E ModE:[C]. Conversely, A E Mod =[El implies A E HModlC and we have (4) HModIC = ModE:[C]. With C = H1dK from (3) and (4) we obtain: HModH1dK = Mod E[HIdK] = Mod Id Z[K], and therefore (5) HVarlK = Var Z[K]. Now, let K be an I-hybrid equational class, i .e. K = HVarIK. Then by (5) we have = I [K] C Var B[K] = K . Together with the closure property of E we get E[K] = K and K is I/-hybrid solid. Next, let K be 1-hybrid solid. By definition we have =:[K] = K and further Id I{ = Id E[K] = HIdIK by (3). Therefore (iii) is satisfied. From Id K = H1dK by definition of an 1-hybrid identity it follows that Id K is closed under I/-hybrid substitutions. This shows (iv). By definition of an 1-hybrid identity the equation Id K = H1dK implies Id K = HId K and further K = Var K = ModId K = Mod E:[Id K] = Mod E[HIdK] = HModH1dK by (4). This means K = HVarIK and K is an 1-hybrid equational class. 0 Note that the equivalence of (i) and (ii) is a Birkhoff-type-characterization of I/-hybrid equational classes. A variety is an I/-hybrid equational class if and only if it is closed under the operator E. 4 The lattice of all 1-hybrid solid varieties Let C ( t ) be the lattice of d.11 varieties of type t and let S(T) be the set of all 1-hybrid solid varieties of this type. Then we have: T h e o r e m 4.1. S1(7) forms a sublattice o f t h e lattice L(7). P r o o f . Assume that V1, Vz E S( t ) . Then VI A VZ = V1 n V 2 , Z:[V1 ~ V Z ] g =:[Vi] = Vi, ( i = 1,2) , and E1 [Vlnv~] E V l n V z . Therefore, by the closure property of E, we have Z,[V1 n V,] = V1 n VZ. This means, V1 A VZ E S1(7). Let Id V1, Id Vz be the sets of all identities of the I/-hybrid solid varieties V1 and VZ. Then Id V1 n Id VZ E E:[IdV1 n Id VZ] because of the closure property of EI, and from IdV1 nIdV, E IdVi, ( i = 1,2), the monotony of = and Theorem 3.3(iv) it follows =[Id V1 n Id V,] g Id V1 n Id Vz , and therefore we have =:[Id V1 n Id Vz] = IdV1 n IdVz. Thus, V1 V V2 = Mod (IdV1 n Id Vz) = Mod Z[IdV1 n Id Vz] = HMod(IdV1 n IdVz) by (4) in the proof of Theorem 3.3. Since HMod(IdV1 n IdVz) is an 1-hybrid equational class, by Theorem 3.3(ii) it is 1-hybrid solid. 0 194 Klaus Denecke Note that the proofs of Theorem 3.3 and Theorem 4.1 are very similar to the proofs of corresponding propositions on hyperequational classes and solid varieties (see [l]). Indeed, for I = 0 we get this case. P r o p o s i t i o n 4.2. Let {fi I i E I} be a set of operation symbols of type r and I c I c I. Then S(T) forms a sublattice of S(T) (and both are sublattices P r o o f . Let V be I/-hybrid solid. Then Z[V] = V. By Proposition 2.3 we have V = Z:[V] _> Z[V] _> V I m d therefore Z[V] = V. This shows that V is I-hybrid solid. Since S(r) and S ( r ) are sublattices of C ( r ) , the lattice S(r) is asublattice of .qT)) . of s ( T ) . 0 5 Hybrid equational logic Theorem 3.3 contains a slight modification and generalization of BIRKHOFFS char- acterization theorem for equational classes. We are asking for a generalization of the completeness theorem for equational theories. D e f i n i t i o n 5.1. A set C of equations of type T is called an 1-hybrid equational theorie of type r if there is a set K of algebras of type r with C = HIdlK. C o r o l l a r y 5.2. A n equational theory C of type T is an I-hybrid equational theory of type r ~ ~ z : [ c I = C. P r o o f . If C is an equational theory, then there is a class K of algebras of type r with C = Id K , i.e. K is a variety. Assume that =[El = C. Then S[IdK] = IdK for the variety K, and by Theorem 3.3 K is an I/-hybrid equational class. Conversely, assume that C is an I-hybrid equational theory of type r . Therefore by definition there is a variety K with C = HIdIK. By definition of an I-hybrid identity we have C HIdlK if and only if Z[C] c IdK, and from H1dK c HIdIK we get 3[HIdK] C IdK and further Z[Z[HIdK]] c HIdlK by Proposition 2.2 and therefore Z[HIdK] c HIdlK. This means E:[C] C. Together with Proposition U Hybrid equational logic can be done in full analogy to the ordinary equational logic of Universal Algebra. Let C be an I/-hybrid equational theory of type r and let t , t E W T ( X ) . Then we write 2.2 we have Z[C] = C. C kI1 t M t if any algebra A of type r which satisfies every equation from C as an It-hybrid identity also satisfies t M t as an I-hybrid identity. We write C I - I I t R5 t if there is a formal deduction of t M t starting with identities in C and using the following rules of derivation (1) - (6). (1) 0 1 t M t for any term t E w ~ ( x ) ; (2) t M t (3) {t M t,t M ,I/) !-I t x t; t M t ; Hybrid Identities and Hybrid Equational Logic 195 (4) { t j M t j l I 1 5 j 5 nil tI f i ( t 1 , . . . , tn , ) M f i ( t i , . . . , t ~ , ) for every operation symbol fi (i E I ) ; ( 5 ) let t , t, T E W T ( X ) and let t, i? be the terms obtained from t , 2 by replac- ing every occurence of a given variable x E X by r , then t M t t f M ? (substitution rule); (6) t z, t tr a[t] M a[t] for every 1-hybrid substitution or (hybrid substitu- tion rule). We have the following completeness theorem for 1-hybrid equational logic: T h e o r e m 5.3. C k t M 2 P r o o f . Since HModrC is an I/-hybrid equational class and every identity is an 1-hybrid identity, C k t M t is equivalent t o t M t E H1dHModC = Id HModIC. Because of HModC = ModEi[C] (see (4) in the proof of Theorem 3.3) we get t w t E Id Mod Z:[C]. This means by the completeness theorem for equational logic that t M t is derivable from E:[C] by using the derivation rules (1) - (5) for the equational logic. For hypersubstitutions E. G R A C Z Y ~ K A showed in [2] that the rule (6) commutes with the rules (1) - (5) in the sense that (6) always can be performed first. Since I/-hybrid substitutions are hypersubstitutions, the equation t M t is derivable from E:[C] by using of (1) - (5) if and only if t M t is derivable from C as 0 if and only if C I- t M t. an 1-hybrid identity by using of (1) - (6). 6 Anexample Remember that a projection algebra A E Alg(r) is an algebra for which every fun- damental operation is a projection. Let P, be the class of all projection algebras of type T and let RA, be the variety generated by the class P,. The elements of RAT are called rectangular algebras of type r in [3]. We mention the following results on the variety RAT. L e m m a 6.1. (i) Let C! be the set of following equations o f type T , where i , j E I : (IDf,) (ABj,) (Mf.,j,) fi(fj(2119. ..yx1nj),fj(x~1,. ..,x znj),...,fj(xn,li...,xn,n,)) fi(z,. . . , x) w 2, fi(211rx22,.. . , x n , n , ) M fi(fi(xllr...rxn,l),...,fi(Cln,r. . . , x n , n , ) ) , M fj(fi(x11,. ..,x n,1),fi(212,...2n.~)r...,fi(xlnj,...,xn,nj)). Then RAT = Mod E!. product of two-element projection algebras. (ii) Every rectangular algebra of finite t ype r is isomorphic to a subalgebra of a direct 0 Let I 5 I and let k = ( k i ) i c p be a sequence of numbers kj with 1 5 k, 5 n, for all i E 1. Consider the subset PF(k),s P, with the property that for all i 1 the fundamental operation ft of A E P, (k) is the same projection ft = e;;. Let RA,(k) be the variety generated by this set of projection algebras. Every algebra of the variety RA:(k) is called an 1-k -hybrid rectangular algebra. Then we have: (iii) RA, is solid and every solid variety of type r contains RAT. 196 Klaus Denecke T h e o r e m 6.2. (i) Let X:'(k) be the set of the equations (IDJ,), (AB!,) and (Mf, , f j ) of type r , where i , j E I \ I / , and additional the following equations: Then RAf'(k) = ModC','(k). algebra of a direct product of two-element projection algebras f rom P:' (k) . fi(z1,. . . ,zn,) N" 25, for all i E 1'. (ii) Every I / - k -hybrid rectangular algebra of finite type r is isomorphic l o a sub- (iii) RA','(k) is I/-hybrid solid and every I/-hybrid solid variety of t y p e r contaans RA: (q. P r o o f . (ii) is a consequence of Lemma 6.1(ii). T h e other propositions are clear. 0 References [I] DENECKE, K., D. LAU, R. POSCHEL and D. SCHWEIGERT, Hyperidentities, Hyper- equational classes and clone congruences. In: Contributions to General Algebra, Verlag Holder-Pichler-Tempsky, Wien, and Verlag B. G. Teubner, Stuttgart 1991, pp. 97 - 117. [2] GRACZY~SKA, E., On normal and regular identities and hyperidentities. In: Universal and Applied Algebra, Turawa, Poland 3-7 May 1988, World Scientific (1989), 107 - 135. [3] POSCHEL, R., and M. REICHEL, Projection algebras and rectangular algebras. In: General Algebra and Applications, Research and Exposition in Mathematics, Vol. 20, Heldermann-Verlag, Berlin, pp. 180 - 195. [4] SCHWEIGERT, D., Hyperidentities. In: Algebras and Orders, NATO AS1 Series, Serie C: Mathematical and Physikal Sciences, vol. 385, Kluwer Academic Publishers, Dordrecht 1993, pp. 405 - 506. (Received: March 7, 1994; Revised: May 24, 1994)