Finite basis theorems for relatively congruence-distributive quasivarieties

Author:
Don Pigozzi

Journal:
Trans. Amer. Math. Soc. **310** (1988), 499-533

MSC:
Primary 08C15; Secondary 03B05, 03C05, 68Q65

DOI:
https://doi.org/10.1090/S0002-9947-1988-0946222-1

MathSciNet review:
946222

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: is any quasivariety. A congruence relation on a member of is a -*congruence* if . The set of all -congruences is closed under arbitrary intersection and hence forms a complete lattice . is *relatively congruence-distributive* if is distributive for every . Relatively congruence-distributive quasivarieties occur naturally in the theory of abstract data types. is *finitely generated* if it is generated by a finite set of finite algebras. The following generalization of Baker's finite basis theorem is proved. Theorem I. *Every finitely generated and relatively congruence-distributive quasivariety is finitely based*. A subquasivariety of an arbitrary quasivariety is called a *relative subvariety of* if it is of the form for some variety , i.e., a base for can be obtained by adjoining only identities to a base for . Theorem II. *Every finitely generated relative subvariety of a relatively congruence-distributive quasivariety is finitely based*. The quasivariety of *generalized equality-test algebras* is defined and the structure of its members studied. This gives rise to a finite algebra whose quasi-identities are finitely based while its identities are not. Connections with logic and the algebraic theory of data types are discussed.

**[1]**K. Baker,*Primitive satisfaction and equational problems for lattices and other algebras*, Trans. Amer. Math. Soc.**190**(1974), 125-150. MR**0349532 (50:2025)****[2]**-,*Finite equational basis for finite algebras in a congruence-distributive equational class*, Adv. in Math.**24**(1977), 207-243. MR**0447074 (56:5389)****[3]**K. Baker, G. McNulty and H. Werner,*The finitely based varieties of graph algebras*, Acta Sci. Math. (Szeged)**51**(1987), 3-15. MR**911554 (88m:08007)****[4]**V. P. Belkin,*Quasi-identities of finite rings and lattices*, Algebra i Logika**17**(1978), 247-259. (Russian) MR**538294 (80g:08015)****[5]**G. Birkhoff,*Subdirect unions in universal algebra*, Bull. Amer. Math. Soc.**50**(1944), 764-768. MR**0010542 (6:33d)****[6]**G. Birkhoff and J. D. Lipson,*Heterogeneous algebras*, J. Combinatorial Theory**8**(1970), 115-133. MR**0250887 (40:4119)****[7]**W. J. Blok and P. Köhler,*Algebraic semantics for quasi-classical modal logics*, J. Symbolic Logic**48**(1983), 941-964. MR**727785 (85f:03014)****[8]**W. J. Blok and D. Pigozzi,*A finite basis theorem for quasivarieties*, Algebra Universalis**22**(1986), 1-13. MR**855723 (87i:08016)****[9]**-,*Protoalgebraic logics*, Studia Logica**45**(1986), 331-363. MR**884144 (88e:03045)****[10]**S. Burris and H. P. Sankappanavar,*A course in universal algebra*, Springer-Verlag, New York, 1981. MR**648287 (83k:08001)****[11]**J. Czelakowski,*Matrices, primitive satisfaction, and finitely based logics*, Studia Logica**42**(1983), 89-104. MR**764552 (86k:03015)****[12]**J. Czelakowski and W. Dziobiak,*Congruence distributive quasivarieties whose finitely subdirectly irreducible members form a universal class*, Preprint. MR**1025840 (91i:08013)****[13]**W. Dzik and R. Suszko,*On distributing of closure systems*, Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic**6**(1977), 64-66. MR**0552646 (58:27681)****[14]**W. Dziobiak,*Concerning axiomatizability of the quasivariety generated by a finite Heyting or topological Boolean algebra*, Studia Logica**41**(1982), 415-428. MR**764764 (86c:08012)****[15]**-,*Finitely generated congruence distributive quasivarieties of algebras*, Preprint.**[16]**J. A. Goguen and J. Meseguer,*Completeness of many-sorted equational logic*, Houston J. Math.**11**(1985), 307-334. MR**808649 (87i:03055)****[17]**J. A. Goguen, J. W. Thatcher, and E. Wagner,*An initial algebra approach to the specification, correctness, and implementation of abstract data types*, Current Trends in Programming Methodology, R. Yeh, ed., Prentice-Hall, 1978, pp. 80-149.**[18]**P. J. Higgins,*Algebras with a scheme of operators*, Math. Nachr.**27**(1963), 115-132. MR**0163940 (29:1239)****[19]**B. Jónsson,*Algebras whose congruence lattices are distributive*, Math. Scand.**21**(1967), 110-121. MR**0237402 (38:5689)****[20]**P. Köhler,*Brouwerian semilattices*, Trans. Amer. Math. Soc.**268**(1981), 103-126. MR**628448 (82i:06005)****[21]**J. Lukasiewicz and A. Tarski,*Investigations into the sentential calculus*, A. Tarski, Logic, Semantics, and Metamathematics, 2nd ed., Hackett, Indianapolis, Indiana, 1983.**[22]**R. McKenzie,*A finite algebra**with**not elementary*, Algebra Universalis**8**(1978), 5-7. MR**0491409 (58:10665)****[23]**-,*Finite equational bases for congruence modular algebras*, Preprint.**[24]**G. F. McNulty and C. Shallon,*Inherently nonfinitely based finite algebras*, Universal Algebra and Lattice Theory, R. Freese and O. Garcia, eds., Lecture Notes in Math., vol. 1004, Springer-Verlag, Berlin, 1983, pp. 206-231. MR**716184 (85h:08011)****[25]**J. Meseguer and J. A. Goguen,*Initiality, induction, and computability*, Algebraic Methods in Semantics, M. Nivat and J. Reynolds, eds., Cambridge Univ. Press, 1985, pp. 459-540. MR**835461 (88a:68073)****[26]**W. Nemitz,*Implicative semi-lattices*, Trans. Amer. Math. Soc.**117**(1965), 128-142. MR**0176944 (31:1212)****[27]**M. J. O'Donnell,*Equational logic as a programming language*, The MIT Press, Cambridge, Mass., 1985. MR**804235 (87j:68002)****[28]**A. J. Ol'šanskiĭ,*Varieties of finitely approximable groups*, Izv. Akad. Nauk SSSR Ser. Mat.**33**(1969), 915-927. MR**0258927 (41:3572)****[29]**D. Pigozzi,*Minimal, locally finite varieties that are not finitely axiomatizable*, Algebra Universalis**9**(1979), 374-390. MR**544861 (81a:08007)****[30]**-,*Equality-test and if-then-else algebras*:*Axiomatization and specification*, Preprint.**[31]**V. V. Rybakov,*Bases of quasivarieties of finite modal algebras*, Algebra i Logica**21**(1982), 219-227. (Russian) MR**700994 (84j:03137)****[32]**M. V. Sapir,*On the quasivarieties generated by finite semigroups*, Semigroup Forum**20**(1980), 73-88. MR**572536 (81g:08016)****[33]**A. Tarski,*Fundamental concepts of the methodology of the deductive sciences*, Logic, Semantics, and Metamathematics, 2nd ed., Hackett, Indianapolis, Indiana, 1983.**[34]**J. W. Thatcher, E. G. Wagner and J. B. Wright,*Data type specification*:*parameterization and the power of specification techniques*, ACM Trans. Program. Lang. Syst.**4**(1982), 711-732. MR**521047 (80d:68028)****[35]**V. I. Tumanov,*On finite lattices not having independent basis of quasi-identities*, Mat. Zametki**36**(1984), 625-634. (Russian) MR**773799 (86e:08010)****[36]**M. Wajsberg,*Beiträge sum Metaaussagenkalkül*I, Monatsh. Math. Phys.**42**(1935), 221-242.**[37]**R. Wójcicki,*Lectures on propositional calculi*, Publ. House Polish Acad. Sci., The Polish Academy of Sciences Institute of Philosophy and Sociology, Ossolineum, Warsaw, 1984. MR**756633 (86h:03002)****[38]**-,*Theory of logical calculi. An introduction*, Manuscript.**[39]**P. Wojtylak,*Strongly finite logics*:*finite axiomatizability and the problem of the supremum*, Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic**8**(1979), 99-111. MR**534281 (80g:03027)**

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
08C15,
03B05,
03C05,
68Q65

Retrieve articles in all journals with MSC: 08C15, 03B05, 03C05, 68Q65

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1988-0946222-1

Keywords:
Quasivariety,
finite basis theorem,
Baker's theorem,
relatively congruence-distributive,
abstract data type

Article copyright:
© Copyright 1988
American Mathematical Society