{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T16:20:49Z","timestamp":1767198049174,"version":"build-2238731810"},"reference-count":25,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":13706,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1976,9]]},"abstract":"<jats:p>Though equations are among the simplest sentences available in a first order language, many of the most familiar notions from algebra can be expressed by sets of equations. It is the task of this paper to expose techniques and theorems that can be used to establish that many collections of finite sets of equations characterized by common algebraic or logical properties fail to be recursive. The following theorem is typical.<\/jats:p>\n                  <jats:p>\n                    Theorem.\n                    <jats:italic>In a language provided with an operation symbol of rank at least two, the collection of finite irredundant sets of equations is not recursive<\/jats:italic>\n                    .\n                  <\/jats:p>\n                  <jats:p>Theorems of this kind are part of a pattern of research into decision problems in equational logic. This pattern finds its origins in the works of Markov [8] and Post [20] and in Tarski's development of the theory of relation algebras; see Chin [1], Chin and Tarski [2], and Tarski [23]. The papers of Mal\u2032cev [7] and Perkins [16] are more directly connected with the present paper, which includes generalization of much of Perkins' work as well as extensions of a theorem of D. Smith [22]. V. L. Murskii [14] contains some of the results below discovered independently. Not all known results concerning undecidable properties of finite sets of equations seem to be susceptible to the methods presented here. R. McKenzie, for example, shows in [9] that for a language with an operation symbol of rank at least two, the collection of finite sets of equations with nontrivial finite models is not recursive. D. Pigozzi has extended and elaborated the techniques of this paper in [17], [18], and [19] to obtain new results concerning undecidable properties, particularly those of algebraic character.<\/jats:p>","DOI":"10.2307\/2272037","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:42:22Z","timestamp":1146937342000},"page":"589-604","source":"Crossref","is-referenced-by-count":21,"title":["Undecidable properties of finite sets of equations"],"prefix":"10.1017","volume":"41","author":[{"given":"George F.","family":"McNulty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200051161_bib013","first-page":"A","article-title":"Undecidable properties of finite sets of equations, II","volume":"22","author":"McNulty","year":"1975","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200051161_bib011","first-page":"657","article-title":"On algebras whose equational theories are essentially base-undecidable","volume":"17","author":"McNulty","year":"1970","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200051161_bib023","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093894637"},{"key":"S0022481200051161_bib003","first-page":"341","article-title":"Distributive and modular laws in the arithmetic of relation algebras","volume":"1","author":"Chin","year":"1951","journal-title":"University of California Publications in Mathematics"},{"key":"S0022481200051161_bib017","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093956081"},{"key":"S0022481200051161_bib012","first-page":"A","article-title":"Undecidable properties of finite sets of equations","volume":"19","author":"McNulty","year":"1972","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200051161_bib025","first-page":"275","volume-title":"Contributions to mathematical logic","author":"Tarski","year":"1968"},{"key":"S0022481200051161_bib015","first-page":"520","article-title":"Nondiscernible properties of finite systems of identity relations, (Russian)","volume":"196","author":"Murski\u01d0","year":"1971","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200051161_bib004","volume-title":"Universal algebra","author":"Gratzer","year":"1968"},{"key":"S0022481200051161_bib009","first-page":"587","article-title":"On the impossibility of certain algorithms in the theory of associative systems","volume":"55","author":"Markov","year":"1947","journal-title":"Doklady Akademii Nauk SSSR, Novaja Serija"},{"key":"S0022481200051161_bib007","first-page":"313","article-title":"Model'nye sootvetstvija","volume":"23","author":"Mal'cev","year":"1959","journal-title":"Izvestija Akademii Nauk SSSR, Serija Matematiceskaja"},{"key":"S0022481200051161_bib008","first-page":"3","article-title":"To\u017edestvennye soolno\u0161enija na mnogoobrazijah kvazigrupp","volume":"69","author":"Mal'cev","year":"1966","journal-title":"Matematiceskii Sbornik, Novaja Serija"},{"key":"S0022481200051161_bib024","first-page":"189","volume":"18","author":"Tarski","year":"1953","journal-title":"An undecidable system of sentential calculus"},{"key":"S0022481200051161_bib018","unstructured":"Pigozzi, D. , The base-undecidability of various algebraic properties of equational theories, (to appear)."},{"key":"S0022481200051161_bib014","unstructured":"McNulty, G. , The decision problem for equational bases of algebras, Annals of Mathematical Logic , to appear."},{"key":"S0022481200051161_bib020","unstructured":"Pigozzi, D. , The universality of the variety of quasigroups, (to appear)."},{"key":"S0022481200051161_bib022","volume-title":"Theory of recursive functions and effective computability","author":"Rogers","year":"1967"},{"key":"S0022481200051161_bib016","unstructured":"Perkins, P. , Decision problems for equational theories of semigroups and general algebras, Ph.D. Thesis, University of California at Berkeley, 1966."},{"key":"S0022481200051161_bib006","volume-title":"The metamathematics of algebraic systems, collected papers: 1936\u20131967","author":"Mal'cev","year":"1971"},{"key":"S0022481200051161_bib010","first-page":"186","volume":"40","author":"McKenzie","year":"1975","journal-title":"On spectra and the negative solution of the decision problem for identities having a finite nontrivial model"},{"key":"S0022481200051161_bib005","volume-title":"Cylindric algebras. Part I","author":"Henkin","year":"1971"},{"key":"S0022481200051161_bib002","unstructured":"Chin, L. , Distributive and modular laws in relation algebras, Ph.D. Thesis, University of California at Berkeley, 1948."},{"key":"S0022481200051161_bib021","first-page":"1","volume":"12","author":"Post","year":"1947","journal-title":"Recursive unsolvability of a problem of Thue"},{"key":"S0022481200051161_bib019","unstructured":"Pigozzi, D. , Universal equational theories and varieties of algebras, (to appear)."},{"key":"S0022481200051161_bib001","volume-title":"Model theory","author":"Chang","year":"1973"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200051161","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,22]],"date-time":"2023-03-22T06:39:33Z","timestamp":1679467173000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200051161\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1976,9]]},"references-count":25,"aliases":["10.1017\/s0022481200051161"],"journal-issue":{"issue":"3","published-print":{"date-parts":[[1976,9]]}},"alternative-id":["S0022481200051161"],"URL":"https:\/\/doi.org\/10.2307\/2272037","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1976,9]]}}}