Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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: $ \mathcal{Q}$ is any quasivariety. A congruence relation $ \Theta $ on a member $ {\mathbf{A}}$ of $ \mathcal{Q}$ is a $ \mathcal{Q}$-congruence if $ {\mathbf{A}}/\Theta \in \mathcal{Q}$. The set $ Co{n_\mathcal{Q}}{\mathbf{A}}$ of all $ \mathcal{Q}$-congruences is closed under arbitrary intersection and hence forms a complete lattice $ {\mathbf{Co}}{{\mathbf{n}}_\mathcal{Q}}{\mathbf{A}}$. $ \mathcal{Q}$ is relatively congruence-distributive if $ {\mathbf{Co}}{{\mathbf{n}}_\mathcal{Q}}{\mathbf{A}}$ is distributive for every $ {\mathbf{A}} \in \mathcal{Q}$. Relatively congruence-distributive quasivarieties occur naturally in the theory of abstract data types. $ \mathcal{Q}$ 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 $ \mathcal{R}$ of an arbitrary quasivariety $ \mathcal{Q}$ is called a relative subvariety of $ \mathcal{Q}$ if it is of the form $ \mathcal{V} \cap \mathcal{Q}$ for some variety $ \mathcal{V}$, i.e., a base for $ \mathcal{R}$ can be obtained by adjoining only identities to a base for $ \mathcal{Q}$. 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.


References [Enhancements On Off] (What's this?)

  • [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 $ A$ with $ SP(A)$ 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)

Similar Articles

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

American Mathematical Society