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

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]**Kirby A. Baker,*Primitive satisfaction and equational problems for lattices and other algebras*, Trans. Amer. Math. Soc.**190**(1974), 125–150. MR**0349532**, https://doi.org/10.1090/S0002-9947-1974-0349532-4**[2]**Kirby A. Baker,*Finite equational bases for finite algebras in a congruence-distributive equational class*, Advances in Math.**24**(1977), no. 3, 207–243. MR**0447074**, https://doi.org/10.1016/0001-8708(77)90056-1**[3]**Kirby A. Baker, George F. McNulty, and Heinrich Werner,*The finitely based varieties of graph algebras*, Acta Sci. Math. (Szeged)**51**(1987), no. 1-2, 3–15. MR**911554****[4]**V. P. Belkin,*Quasi-identities of finite rings and lattices*, Algebra i Logika**17**(1978), no. 3, 247–259, 357 (Russian). MR**538294****[5]**Garrett Birkhoff,*Subdirect unions in universal algebra*, Bull. Amer. Math. Soc.**50**(1944), 764–768. MR**0010542**, https://doi.org/10.1090/S0002-9904-1944-08235-9**[6]**Garrett Birkhoff and John D. Lipson,*Heterogeneous algebras*, J. Combinatorial Theory**8**(1970), 115–133. MR**0250887****[7]**W. J. Blok and P. Köhler,*Algebraic semantics for quasiclassical modal logics*, J. Symbolic Logic**48**(1983), no. 4, 941–964 (1984). MR**727785**, https://doi.org/10.2307/2273660**[8]**W. J. Blok and Don Pigozzi,*A finite basis theorem for quasivarieties*, Algebra Universalis**22**(1986), no. 1, 1–13. MR**855723**, https://doi.org/10.1007/BF01190734**[9]**W. J. Blok and Don Pigozzi,*Protoalgebraic logics*, Studia Logica**45**(1986), no. 4, 337–369. MR**884144**, https://doi.org/10.1007/BF00370269**[10]**Stanley Burris and H. P. Sankappanavar,*A course in universal algebra*, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981. MR**648287****[11]**Janusz Czelakowski,*Matrices, primitive satisfaction and finitely based logics*, Studia Logica**42**(1983), no. 1, 89–104. MR**764552**, https://doi.org/10.1007/BF01418762**[12]**Janusz Czelakowski and Wiesław Dziobiak,*Congruence distributive quasivarieties whose finitely subdirectly irreducible members form a universal class*, Algebra Universalis**27**(1990), no. 1, 128–149. MR**1025840**, https://doi.org/10.1007/BF01190258**[13]**Wojciech Dzik and Roman Suszko,*On distributivity of closure systems*, Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic**6**(1977), no. 2, 64–66. MR**0552646****[14]**Wiesław Dziobiak,*Concerning axiomatizability of the quasivariety generated by a finite Heyting or topological Boolean algebra*, Studia Logica**41**(1982), no. 4, 415–428 (1983). MR**764764**, https://doi.org/10.1007/BF00403339**[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), no. 3, 307–334. MR**808649****[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]**Philip J. Higgins,*Algebras with a scheme of operators*, Math. Nachr.**27**(1963), 115–132. MR**0163940**, https://doi.org/10.1002/mana.19630270108**[19]**Bjarni Jónsson,*Algebras whose congruence lattices are distributive*, Math. Scand.**21**(1967), 110–121 (1968). MR**0237402**, https://doi.org/10.7146/math.scand.a-10850**[20]**Peter Köhler,*Brouwerian semilattices*, Trans. Amer. Math. Soc.**268**(1981), no. 1, 103–126. MR**628448**, https://doi.org/10.1090/S0002-9947-1981-0628448-3**[21]**J. Lukasiewicz and A. Tarski,*Investigations into the sentential calculus*, A. Tarski, Logic, Semantics, and Metamathematics, 2nd ed., Hackett, Indianapolis, Indiana, 1983.**[22]**Ralph McKenzie,*A finite algebra 𝐴 with 𝑆𝑃(𝐴) not elementary*, Algebra Universalis**8**(1977), no. 1, 5–7. MR**0491409**, https://doi.org/10.1007/BF02485363**[23]**-,*Finite equational bases for congruence modular algebras*, Preprint.**[24]**George F. McNulty and Caroline R. Shallon,*Inherently nonfinitely based finite algebras*, Universal algebra and lattice theory (Puebla, 1982) Lecture Notes in Math., vol. 1004, Springer, Berlin, 1983, pp. 206–231. MR**716184**, https://doi.org/10.1007/BFb0063439**[25]**José Meseguer and Joseph A. Goguen,*Initiality, induction, and computability*, Algebraic methods in semantics (Fontainebleau, 1982) Cambridge Univ. Press, Cambridge, 1985, pp. 459–541. MR**835461****[26]**William C. Nemitz,*Implicative semi-lattices*, Trans. Amer. Math. Soc.**117**(1965), 128–142. MR**0176944**, https://doi.org/10.1090/S0002-9947-1965-0176944-9**[27]**Michael J. O’Donnell,*Equational logic as a programming language*, Foundations of Computing Series, MIT Press, Cambridge, MA, 1985. MR**804235****[28]**A. Ju. Ol′šanskiĭ,*Varieties of finitely approximable groups*, Izv. Akad. Nauk SSSR Ser. Mat.**33**(1969), 915–927 (Russian). MR**0258927****[29]**Don Pigozzi,*Minimal, locally-finite varieties that are not finitely axiomatizable*, Algebra Universalis**9**(1979), no. 3, 374–390. MR**544861**, https://doi.org/10.1007/BF02488049**[30]**-,*Equality-test and if-then-else algebras*:*Axiomatization and specification*, Preprint.**[31]**V. V. Rybakov,*Bases of quasi-identities of finite modal algebras*, Algebra i Logika**21**(1982), no. 2, 219–227 (Russian). MR**700994****[32]**M. V. Sapir,*On the quasivarieties generated by finite semigroups*, Semigroup Forum**20**(1980), no. 1, 73–88. MR**572536**, https://doi.org/10.1007/BF02572670**[33]**A. Tarski,*Fundamental concepts of the methodology of the deductive sciences*, Logic, Semantics, and Metamathematics, 2nd ed., Hackett, Indianapolis, Indiana, 1983.**[34]**James W. Thatcher, Eric G. Wagner, and Jesse B. Wright,*Data type specification: parameterization and the power of specification techniques*, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, Calif., 1978) ACM, New York, 1978, pp. 119–132. MR**521047****[35]**V. I. Tumanov,*Finite lattices with no independent basis of quasi-identities*, Mat. Zametki**36**(1984), no. 5, 625–634, 797 (Russian). MR**773799****[36]**M. Wajsberg,*Beiträge sum Metaaussagenkalkül*I, Monatsh. Math. Phys.**42**(1935), 221-242.**[37]**Ryszard Wójcicki,*Lectures on propositional calculi*, Ossolineum Publishing Co., Wrocław, 1984. MR**756633****[38]**-,*Theory of logical calculi. An introduction*, Manuscript.**[39]**Piotr Wojtylak,*Strongly finite logics: finite axiomatizability and the problem of supremum*, Polish Acad. Sci. Inst. Philos. Sociol. Bull. Sect. Logic**8**(1979), no. 2, 99–111. MR**534281**

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