Finite basis theorems for relatively congruence-distributive quasivarieties
HTML articles powered by AMS MathViewer
- by Don Pigozzi PDF
- Trans. Amer. Math. Soc. 310 (1988), 499-533 Request permission
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
- Kirby A. Baker, Primitive satisfaction and equational problems for lattices and other algebras, Trans. Amer. Math. Soc. 190 (1974), 125–150. MR 349532, DOI 10.1090/S0002-9947-1974-0349532-4
- 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 447074, DOI 10.1016/0001-8708(77)90056-1
- 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
- V. P. Belkin, Quasi-identities of finite rings and lattices, Algebra i Logika 17 (1978), no. 3, 247–259, 357 (Russian). MR 538294
- Garrett Birkhoff, Subdirect unions in universal algebra, Bull. Amer. Math. Soc. 50 (1944), 764–768. MR 10542, DOI 10.1090/S0002-9904-1944-08235-9
- Garrett Birkhoff and John D. Lipson, Heterogeneous algebras, J. Combinatorial Theory 8 (1970), 115–133. MR 250887
- 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, DOI 10.2307/2273660
- W. J. Blok and Don Pigozzi, A finite basis theorem for quasivarieties, Algebra Universalis 22 (1986), no. 1, 1–13. MR 855723, DOI 10.1007/BF01190734
- W. J. Blok and Don Pigozzi, Protoalgebraic logics, Studia Logica 45 (1986), no. 4, 337–369. MR 884144, DOI 10.1007/BF00370269
- 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
- Janusz Czelakowski, Matrices, primitive satisfaction and finitely based logics, Studia Logica 42 (1983), no. 1, 89–104. MR 764552, DOI 10.1007/BF01418762
- 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, DOI 10.1007/BF01190258
- 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 552646
- 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, DOI 10.1007/BF00403339 —, Finitely generated congruence distributive quasivarieties of algebras, Preprint.
- J. A. Goguen and J. Meseguer, Completeness of many-sorted equational logic, Houston J. Math. 11 (1985), no. 3, 307–334. MR 808649 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.
- Philip J. Higgins, Algebras with a scheme of operators, Math. Nachr. 27 (1963), 115–132. MR 163940, DOI 10.1002/mana.19630270108
- Bjarni Jónsson, Algebras whose congruence lattices are distributive, Math. Scand. 21 (1967), 110–121 (1968). MR 237402, DOI 10.7146/math.scand.a-10850
- Peter Köhler, Brouwerian semilattices, Trans. Amer. Math. Soc. 268 (1981), no. 1, 103–126. MR 628448, DOI 10.1090/S0002-9947-1981-0628448-3 J. Lukasiewicz and A. Tarski, Investigations into the sentential calculus, A. Tarski, Logic, Semantics, and Metamathematics, 2nd ed., Hackett, Indianapolis, Indiana, 1983.
- Ralph McKenzie, A finite algebra $\b A$ with $\textrm {SP}(\b A)$ not elementary, Algebra Universalis 8 (1977), no. 1, 5–7. MR 491409, DOI 10.1007/BF02485363 —, Finite equational bases for congruence modular algebras, Preprint.
- 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, DOI 10.1007/BFb0063439
- 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
- William C. Nemitz, Implicative semi-lattices, Trans. Amer. Math. Soc. 117 (1965), 128–142. MR 176944, DOI 10.1090/S0002-9947-1965-0176944-9
- Michael J. O’Donnell, Equational logic as a programming language, Foundations of Computing Series, MIT Press, Cambridge, MA, 1985. MR 804235
- A. Ju. Ol′šanskiĭ, Varieties of finitely approximable groups, Izv. Akad. Nauk SSSR Ser. Mat. 33 (1969), 915–927 (Russian). MR 0258927
- Don Pigozzi, Minimal, locally-finite varieties that are not finitely axiomatizable, Algebra Universalis 9 (1979), no. 3, 374–390. MR 544861, DOI 10.1007/BF02488049 —, Equality-test and if-then-else algebras: Axiomatization and specification, Preprint.
- V. V. Rybakov, Bases of quasi-identities of finite modal algebras, Algebra i Logika 21 (1982), no. 2, 219–227 (Russian). MR 700994
- M. V. Sapir, On the quasivarieties generated by finite semigroups, Semigroup Forum 20 (1980), no. 1, 73–88. MR 572536, DOI 10.1007/BF02572670 A. Tarski, Fundamental concepts of the methodology of the deductive sciences, Logic, Semantics, and Metamathematics, 2nd ed., Hackett, Indianapolis, Indiana, 1983.
- 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
- V. I. Tumanov, Finite lattices with no independent basis of quasi-identities, Mat. Zametki 36 (1984), no. 5, 625–634, 797 (Russian). MR 773799 M. Wajsberg, Beiträge sum Metaaussagenkalkül I, Monatsh. Math. Phys. 42 (1935), 221-242.
- Ryszard Wójcicki, Lectures on propositional calculi, Ossolineum Publishing Co., Wrocław, 1984. MR 756633 —, Theory of logical calculi. An introduction, Manuscript.
- 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
Additional Information
- © Copyright 1988 American Mathematical Society
- 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