×

A field guide to equational logic. (English) Zbl 0781.03011

The title of this paper really says all; this is a brief introduction to the important results in five areas of equational logic. The section headings are “Decidability of theories axiomatized by equations”, “Finite axiomatizability”, “Lattices of equational theories”, “Undecidable properties of finite sets of equations” and “Doing mathematics via equations”. There is also a very helpful glossary and a useful list of references.
This paper should both serve to whet the appetite of those not already acquainted with this subject and be an important reference for those already working in the field.

MSC:

03C05 Equational classes, universal algebra in model theory
08B05 Equational logic, Mal’tsev conditions
03-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
08-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to general algebraic systems
03B25 Decidability of theories and sets of sentences
68Q42 Grammars and rewriting systems
68W30 Symbolic computation and algebraic computation
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Addison, J. W., On some points of the theory of recursive functions, (Ph. D. Thesis (1954), University of Wisconsin: University of Wisconsin Madison) · Zbl 1056.03019
[2] Adjan, S. I., On algorithmic problems in effectively complete classes of groups, Doklady Akad. Nauk SSSR, 23, 13-16 (1958), (Russian) · Zbl 0090.01102
[3] Baker, K., Finite equational bases for finite algebras in congruence distributive varieties, Advances in Mathematics, 24, 207-243 (1977) · Zbl 0356.08006
[4] Baker, K.; McNulty, G.; Werner, H., The finitely based varieties of graph algebras, Acta Scient. Math. (Szeged), 51, 3-15 (1987) · Zbl 0629.08003
[5] Baker, K.; McNulty, G.; Werner, H., Shift-automorphism methods for inherently nonfinitely based varieties of algebras, Czech. Math. J, 39, 53-69 (1989) · Zbl 0677.08005
[6] Bauer, G.; Otto, F., Finite complete rewriting systems and the complexity of the word problem, Acta Informatica, 21, 521-540 (1984) · Zbl 0535.68019
[7] Birkhoff, Garrett, Universal algebra, (Proceedings of the First Canadian Mathematical Conference (1946), University of Toronto Press: University of Toronto Press Toronto), 310-326 · Zbl 0060.06802
[8] Bol’bot, A. D., Varieties of Ω-algebras, Algebra and Logic, 9, 244-248 (1970), (English translation) · Zbl 0228.08006
[9] Book, R., Thue systems as rewriting systems, ((1987)), 39-68, in Jouannaud. [1987] · Zbl 0638.68091
[10] Boone, W., Certain simple unsolvable problems in group theory, II, Indag. Math, 16, 492-497 (1954) · Zbl 0057.01701
[11] Boone, W., Certain simple unsolvable problems in group theory, IV, Indag. Math, 17, 571-577 (1955) · Zbl 0067.25706
[12] Boone, W., Certain simple unsolvable problems in group theory, VI, Indag. Math, 19, 227-232 (1957) · Zbl 0067.25706
[13] Boone, W., The word problem, Annals of Math, 70, 207-265 (1959) · Zbl 0102.00902
[14] Bryant, R., The laws of finite pointed groups, Bull. London Math. Soc, 14, 119-123 (1982) · Zbl 0451.08006
[15] Buchberger, B., History and basic features of the critical-pair/completion procedure, ((1987)), 3-38, in Jouannaud. [1987] · Zbl 0645.68094
[16] Burris, S.; Nelson, E., Embedding the dual of \(Π_m\) in the lattice of equational classes of commulative semigroups, (Proc. Amer. Math. Soc, 30 (1971)), 37-39
[17] Burris, S.; Nelson, E., Embedding the dual of \(Π_∞\) in the lattice of equational classes of semigroups, Algebra Universalis, 1, 248-253 (1971) · Zbl 0227.08006
[18] Burris, S.; Sankappanavar, H. P., A Course in Universal Algebra (1981), Springer-Verlag: Springer-Verlag New York · Zbl 0478.08001
[19] Cohn, P. M., Universal Algebra (1965), Harper & Row: Harper & Row New York · Zbl 0141.01002
[20] Cohn, P. M., Universal Algebra (1981), D. Reidel: D. Reidel Dordrecht, Holland · Zbl 0141.01002
[21] Day, A., A characterization of modularity of congruence lattices of algebras, Canad. Math. Bull, 12, 167-173 (1969) · Zbl 0181.02302
[22] Dedekind, R., Über die von drei Moduln erzeugte Dualgruppe, Math. Ann, 53, 371-403 (1900) · JFM 31.0211.01
[23] Dehn, M., Über unendlicher diskontinuierliche Gruppen, Math. Ann, 71, 116-144 (1911) · JFM 42.0508.03
[24] Dershowitz, N., Termination of rewriting, ((1987)), 69-116, in Jouannaud. [1987] · Zbl 0637.68035
[25] Dershowitz, N., Rewriting Techniques and Applications, (Lecture Notes in Computer Science, 355 (1989), Springer-Verlag: Springer-Verlag Berlin)
[26] Dershowitz, N.; Jouannaud, J.-P., Rewrite systems, ((1990)), 243-320, Chapter 6, in van Leeuwem [1990] · Zbl 0900.68283
[27] Evans, T., Some connections between residual finiteness, finite embeddability and the word problem, J. London Math. Soc, 1, 399-403 (1969) · Zbl 0184.03502
[28] Evans, T., Word problems, Bull. Amer. Math. Soc, 84, 789-802 (1978) · Zbl 0389.03018
[29] Feeney, W. J., Certain Unsolvable Problems in the Theory of Cancellation Semigroups, (Ph. D. Thesis (1954), Catholic University of America)
[30] Freese, R., Free modular lattices, Trans. Amer. Math. Soc, 26, 181-191 (1980)
[31] (Freese, R.; Garcia, O., Universal Algebra and Lattice Theory, Proceedings. Universal Algebra and Lattice Theory, Proceedings, Puebla 1982. Universal Algebra and Lattice Theory, Proceedings. Universal Algebra and Lattice Theory, Proceedings, Puebla 1982, Lecture Note in Mathematics, 1004 (1983), Springer-Verlag: Springer-Verlag Berlin) · Zbl 0509.00004
[32] Freese, R.; McKenzie, R., Residually small varieties with modular congruence lattices, Trans. Amer. Math. Soc, 264, 419-430 (1981) · Zbl 0472.08008
[33] Freese, R.; McKenzie, R., Commutator Theory for Congruence Modular Varieties, (London Mathematical Society Lecture Note Series, 125 (1987), Cambridge University Press: Cambridge University Press Cambridge, England) · Zbl 0636.08001
[34] Freese, R.; McKenzie, R.; McNulty, G.; Taylor, W., (Algebras, Lattices, Varieties, Volume II (1991), Wadsworth & Brook/Cole: Wadsworth & Brook/Cole Monterey, CA), To appear
[35] Grätzer, G., Universal Algebra, (University Series in Higher Mathematics (1968), D. Van Nostrand Company: D. Van Nostrand Company New York) · Zbl 0182.34201
[36] Grätzer, G., Universal Algebra, ((1979), Springer-Verlag: Springer-Verlag New York), 581, [1968] · Zbl 0182.34201
[37] Gurevič, R., Equational theory of positive numbers with exponentiation is not finitely axiomatizable, Annals of Pure and Applied Logic, 49, 1-30 (1990) · Zbl 0707.03023
[38] Henkin, L., The logic of equality, Amer. Math. Monthly, 84, 597-612 (1977) · Zbl 0376.02017
[39] Herrmann, C., On the word problem for the modular lattice with four free generators, Math. Ann, 256, 513-527 (1983) · Zbl 0506.06004
[40] Hobby, D.; McKenzie, R., The Structure of Finite Algebras (Tame Congruence Theory), (Contemporary Mathematics, 76 (1988), American Mathematical Society: American Mathematical Society Providence, RI)
[41] Huet, G.; Lankford, D., On the uniform halting problem for term rewriting systems, (Rapport Laboria 283 (1978), Institut de Recherche en Informatique et en Automatique: Institut de Recherche en Informatique et en Automatique Le Chesnay, France)
[42] Isaev, I. M., Essentially infinitely based varieties of algebras, Sibirian Math. J, 892-894 (1989), English translation · Zbl 0725.17002
[43] Jacobs, E.; Schwabauer, R., The lattice of equational classes of algebras with one unary operation, Amer. Math. Monthly, 71, 151-155 (1964) · Zbl 0117.26003
[44] Ježek, J., Primitive classes of algebras with unary and nullary operations, (Colloq. Math, 20 (1969)), 159-179 · Zbl 0188.04801
[45] Ježek, J., Intervals in the lattice of varieties, Algebra Universalis, 6, 147-158 (1976) · Zbl 0354.08007
[46] Ježek, J., The lattice of equational theories, part I: modular elements, Czechoslovak Math. J, 31, 127-152 (1981) · Zbl 0477.08006
[47] Ježek, J., The lattice of equational theories part II: the lattice of full sets of terms, Czechoslovak Math. J, 31, 573-603 (1981) · Zbl 0486.08009
[48] Ježek, J., The lattice of equational theories part III: definability and automorphisms, Czechoslovak Math. J, 32, 129-164 (1982) · Zbl 0499.08005
[49] Ježek, J., Nonfinitely based three-element groupoids, Algebra Universalis, 20, 292-301 (1985) · Zbl 0574.08004
[50] Ježek, J., The lattice of equational theories part IV: equational theories of finite algebras, Czechoslovak Math. J, 36, 331-341 (1986) · Zbl 0605.08005
[51] Jónsson, B., Algebras whose congruence lattices are distributive, Math. Scand, 21, 110-121 (1967) · Zbl 0167.28401
[52] Jónsson, B., Congruence varieties, Algebra Universalis, 10, 355-394 (1980) · Zbl 0438.08003
[53] (Jouannaud, J.-P., Rewriting Techniques and Applications (1987), Academic Press: Academic Press New York)
[54] Kalfa, C., Decision problems concerning properties of finite sets of equations, J. Symbolic Logic, 51, 79-87 (1986) · Zbl 0589.08006
[55] Kalicki, J., On comparison of finite algebras, (Proc. Amer. Math. Soc, 3 (1952)), 36-40 · Zbl 0046.03102
[56] Kalicki, J., The number of equationally complete classes of equations, Indag. Math, 58, 660-662 (1955) · Zbl 0073.24601
[57] Kiss, E.; Prőhle, P., Problems and results in tame congruence theory, Algebra Universalis, 29, 151-171 (1992) · Zbl 0759.08003
[58] Kruse, R., Identities satisfied by a finite ring, J. Algebra, 26, 298-318 (1973) · Zbl 0276.16014
[59] Lampe, W., A property of lattices of equational theories, Algebra Universalis, 24 (1987)
[60] L’vov, I. V., Varieties of associative rings, II, Algebra i Logika, 12, 735 (1973) · Zbl 0288.16009
[61] Lyndon, R., Identities in two-valued calculi, Trans. Amer. Math. Soc, 71, 457-465 (1951) · Zbl 0044.00201
[62] Lyndon, R., Identities in finite algebras, (Proc. Amer. Math. Soc, 5 (1954)), 8-9 · Zbl 0055.02705
[63] Macintyre, A., The word problem for division rings, J. Symbolic Logic, 38, 428-436 (1973) · Zbl 0286.02046
[64] Maltsev, A. I., Amer. Math. Soc. Transl, 119, 67-79 (1958)
[65] Maltsev, A. I., Amer. Math. Soc. Transl, 82, 225-235 (1969), Chapter 29 in Maltsev [1971] · Zbl 0205.31004
[66] Maltsev, A. I., Amer. Math. Soc. Transl, 70, 89-100 (1968), Chapter 34 in Maltsev [1971]
[67] Maltsev, A. I., The Metamathematics of Algebraic Systems: A selection of Maltsev’s papers, (Wells, B. F. (1971), North-Holland Publishing Company: North-Holland Publishing Company Amsterdam)
[68] Maltsev, A. I., Algebraic Systems (1973), Akademie-Verlag: Akademie-Verlag Berlin
[69] Markov, A., On the impossibility of certain algorithms in the theory of associative systems, Doklady Akad. Nauk SSSR, 55, 587-590 (1947)
[70] Markov, A., Impossibility of certain algorithms in the theory of associative systems, Doklady Akad. Nauk SSSR, 77, 953-956 (1951) · Zbl 0043.01102
[71] Martin, C., The Equational Theories of Natural Numbers and Transfinite Ordinals, (Ph. D. Thesis (1973), University of California: University of California Berkeley, CA)
[72] McKenzie, R., Equational bases for lattice theories, Math. Scand, 27, 24-38 (1970) · Zbl 0307.08001
[73] McKenzie, R., Definability in lattices of equational theories, Ann. Math. Logic, 3, 197-237 (1971) · Zbl 0328.02038
[74] McKenzie, R., On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model, J. Symbolic Logic, 40, 186-196 (1975) · Zbl 0316.02052
[75] McKenzie, R., A new product of algebras and a type reduction theorem, Algebra Universalis, 18, 29-69 (1984) · Zbl 0543.08005
[76] McKenzie, R., Finite equational bases for congruence modular algebras, Algebra Universalis, 24, 224-250 (1987) · Zbl 0648.08006
[77] McKenzie, R.; McNulty, G.; Taylor, W., (Algebras, Lattices, Varieties, Volume I (1987), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Monterey, CA)
[78] McKenzie, R.; Valeriorte, M., The Structure of Dedicable Locally Finite Varieties (1989), Birkhäuser Verlag: Birkhäuser Verlag Boston, MA, To appear
[79] McKinsey, J. C.C., The decision problem for some classes of sentences without quantifiers, J Symbolic Logic, 8, 61-76 (1943) · Zbl 0063.03864
[80] McNulty, G., The decision problem for equational bases of algebras, Ann. Math. Logic, 11, 193-259 (1976) · Zbl 0376.08005
[81] McNulty, G., Undecidable properties of finite sets of equations, J. Symbolic Logic, 41, 589-604 (1976) · Zbl 0375.02040
[82] McNulty, G., Structural diversity in the lattice of equational theories, Algebra Universalis, 13, 271-292 (1981) · Zbl 0485.08007
[83] McNulty, G., (Szabó; Szendrei, Fifteen possible previews in equational logic (1986)), 307-331, [1986]
[84] McNulty, G., (Dershowitz, N., An Equational logic sampler (1989)), 234-262, [1989] · Zbl 1503.03035
[85] McNulty, G.; Shallon, C., (Freese; Garcia, Inherently nonfinitely based finite algebras (1983)), 205-231, [1983]
[86] Mekler, A.; Nelson, E.; Shelah, S., A variety with solvable, but not uniformly solvable, word problem (1991), To appear · Zbl 0796.08006
[87] Murskiǐ, V. L., The existence in three-value logic of a closed class without a finite complete system of identities, Doklady Akad. Nauk SSSR, 163, 815-818 (1965) · Zbl 0154.25506
[88] Murskiǐ, V. L., Examples of varieties of semigroups, Mat. Zametki, 3, 663-670 (1968) · Zbl 0181.01401
[89] Murskiǐ, V. L., Nondiscernible properties of finite systems of identity relations, Doklady Akad. Nauk SSSR, 196, 520-522 (1971) · Zbl 0238.02039
[90] Murskiǐ, V. L., The existence of a finite basis and some other properties of “almost all” finite algebras, Problemy Kibernet, 30, 43-56 (1975) · Zbl 0415.08005
[91] Murskiǐ, V. L., Concerning the number of \(k\)-element algebras with one binary operation which have no finite basis of identities, Problemy Kibernet, 35, 5-27 (1979) · Zbl 0464.08002
[92] Novikov, P. S., On the algorithmic unsolvability of the word problem in group theory, Trudy Mat. Inst. Steklov, 44, 1-143 (1955), (in Russian)
[93] Oates, S.; Powell, M. B., Identical relations in finite groups, J. Algebra, 1, 11-39 (1965) · Zbl 0121.27202
[94] Oates-Williams, S.; Vaughan-Lee, M., Varieties that make one Cross, J. Austral. Math. Soc. (A), 26, 368-382 (1978) · Zbl 0393.17001
[95] O’Dúnlaing, C., Undecidable questions of Thue systems, Theoret. Comp. Sci, 23, 339-345 (1983) · Zbl 0512.03019
[96] Perkins, P., Decision Problems for Equatorial Theories of Semigroups and General Algebras, (Ph. D. Thesis (1966), University of California: University of California Berkeley, CA)
[97] Perkins, P., Unsolvable problems for equatorial theories, Notre Dame J. of Formal Logic, 8, 175-185 (1967) · Zbl 0197.28201
[98] Perkins, P., Bases for equatorial theories of semigroups, J. Algebra, 11, 293-314 (1968)
[99] Perkins, P., Basis questions for general algebra, Algebra Universalis, 19, 16-23 (1984) · Zbl 0545.08008
[100] Peirce, C. S., On the algebra of logic, Amer. J. Math, 3, 15-57 (1880) · JFM 12.0041.01
[101] Pierce, R. S., Introduction to the Theory of Abstract Algebras (1968), Holt, Rinehart and Winston: Holt, Rinehart and Winston New York
[102] Pigozzi, D., Base-undecidable properties of universal varieties, Algebra Universalis, 6, 193-223 (1976) · Zbl 0356.08005
[103] Pigozzi, D.; Tardos, G., The representation of certain abstract lattices as lattices of subvarieties (1991), To appear
[104] Plaisted, D., The undecidability of self embedding for term rewriting systems, (Inf. Proc. Lett, 20 (1985)), 61-64 · Zbl 0571.68025
[105] Polin, S. V., On the identities of finite algebras, Sib. Mat. J, 17, 1356-1366 (1976)
[106] Post, E., The Two-valued Iterative Systems of Mathematical Logic, (Annals of Math. Studies, No. 5 (1941), Princeton University Press: Princeton University Press Princeton, NJ) · Zbl 0063.06326
[107] Post, E., Recursive unsolvability of a problem of Thue, J. Symbolic Logic, 12, 1-11 (1947) · Zbl 1263.03030
[108] Rabin, M., Recursive unsolvability of group theoretic problems, Ann. of Math, 67, 172-194 (1958) · Zbl 0079.24802
[109] Sapir, M., Math. USSR Izvestiya, 30, 295-314 (1987), English translation · Zbl 0646.20047
[110] Sapir, M., Math. USSR Sbornik, 61, 155-166 (1988), English translation · Zbl 0655.20045
[111] Schröder, E., (Müller, E.; Teubner, B. G., Vorlesungen über die Algebra der Logik (exacte Logik) (1966), Chelsea Publ. Co.,: Chelsea Publ. Co., New York), published in four volumes, Leipzig. Second edition in three volumes · JFM 22.0073.02
[112] (Schütte, K., Contributions to Mathematical Logic (1968), North-Holland Publishing Co.,: North-Holland Publishing Co., Amsterdam)
[113] Scott, D., Equationally complete extensions of finite algebras, Indag. Math, 5, 935-938 (1956)
[114] Shallon, C., Nonfinitely Based Binary Algebra Derived for Lattices, (Ph. D. Thesis (1979), University of California: University of California Los Angeles, CA)
[115] Shevrin, L. N.; Volkov, M. V., Identities of semigroups, Izvestiya VUZ Mat, 29, 3-47 (1985) · Zbl 0629.20029
[116] Smith, D., Non-recursiveness of the set of finite sets of equations whose theories are one based, Notre Dame J. Formal Logic, 13, 135-138 (1972) · Zbl 0197.28202
[117] (Szabó, L.; Szendrei, A., Lectures in Universal Algebra. Lectures in Universal Algebra, Colloquia Mathematica Societas János Bolyai, 43 (1986), North-Holland: North-Holland Amsterdam) · Zbl 0588.00012
[118] Szendrei, A., Clones in Universal Algebra, (Séminaire de Mathématiques Supérieures, 99 (1986), Les Presses de l’Université de Montréal: Les Presses de l’Université de Montréal Montréal, Canada) · Zbl 0603.08004
[119] Szmielew, W., Elementary properties of Abelian groups, Fund. Math, 41, 203-271 (1954) · Zbl 0064.00803
[120] Tarski, A., On the calculus of relations, J. Symbolic Logic, 6, 73-89 (1941) · JFM 67.0973.02
[121] Tarski, A., Arithmetical classes and types of Boolean Algebras (preliminary report), Bull. Amer. Math. Soc, 55, 64 (1949)
[122] Tarski, A., Undecidability of the theories of lattices and projective geometries, J. Symbolic Logic, 14, 77-78 (1949)
[123] Tarski, A., A formalization of set theory without variables (abstract), J. Symbolic Logic, 18, 189 (1953)
[124] Tarski, A., Equational logic, ((1968)), 275-288, in Schütte · Zbl 0209.01402
[125] Tarski, A.; Givant, S., A Formalization of Set Theory Without Variables, (Colloquium Publications, 41 (1987), Amer. Math. Soc.,: Amer. Math. Soc., Providence, RI) · Zbl 0654.03036
[126] Taylor, W., Equational logic, Houston J. Math. (Survey Issue) (1979) · Zbl 0421.08004
[127] Taylor, W., The Clone of a Topological Space, (Research and Exposition in Mathematics, 13 (1986), Heldermann Verlag: Heldermann Verlag Berlin) · Zbl 0615.54013
[128] Vaughan-Lee, M., Laws in finite loops, Algebra Universalis, 9, 269-280 (1979) · Zbl 0436.20046
[129] Vaughan-Lee, M., Nilpotence in permutable varieties, ((1983)), 293-308, in Freese and Garcia [1983] · Zbl 0525.08008
[130] (van Leeuwen, J., Handbook of Theoretical Computer Science, B: Formal Methods and Semantics (1990), North Holland: North Holland Amsterdam) · Zbl 0714.68001
[131] Wells, B., Pseudorecursive Varieties and Their Word Problems, (Ph. D. Thesis (1982), University of California: University of California Berkeley, CA)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.