{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T08:06:46Z","timestamp":1775808406623,"version":"3.50.1"},"reference-count":20,"publisher":"Cambridge University Press (CUP)","issue":"2","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":14164,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1975,6]]},"abstract":"<jats:p>An algorithm has been described by S. Burris [3] which decides if a finite set of identities, whose function symbols are of rank at most 1, has a finite, nontrivial model. (By \u201cnontrivial\u201d it is meant that the universe of the model has at least two elements.) As a consequence of some results announced in the abstracts [2] and [8], it is clear that if the restriction on the ranks of function symbols is relaxed somewhat, then this finite model problem is no longer solvable by an algorithm, or at least not by a \u201crecursive algorithm\u201d as the term is used today.<\/jats:p><jats:p>In this paper we prove a sharp form of this negative result; showing, by the way, that Burris' result is in a sense the best possible result in the positive direction. Our main result is that in a first order language whose only function or relation symbol is a 2-place function symbol <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200053743_inline1\"\/> (the language of groupoids), the set of identities <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200053743_inline2\"\/> that have no nontrivial model, is recursively inseparable from the set of identities <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200053743_inline2\"\/> such that the sentence <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200053743_inline3\"\/><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0022481200053743_inline4\"\/> has a finite model. As a corollary, we have that each of the following problems, restricted to sentences defined in the language of groupoids, is algorithmically unsolvable: (1) to decide if an identity has a finite nontrivial model; (2) to decide if an identity has a nontrivial model; (3) to decide if a universal sentence has a finite model; (4) to decide if a universal sentence has a model. We note that the undecidability of (2) was proved earlier by McNulty [13, Theorem 3.6(i)], improving results obtained by Murski\u01d0 [14] and by Perkins [17]. The other parts of the corollary seem to be new.<\/jats:p>","DOI":"10.2307\/2271899","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T21:35:13Z","timestamp":1146951313000},"page":"186-196","source":"Crossref","is-referenced-by-count":45,"title":["On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model"],"prefix":"10.1017","volume":"40","author":[{"given":"Ralph","family":"Mckenzie","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200053743_ref019","volume-title":"Theory of recursive functions and effective comput ability","author":"Rogers","year":"1967"},{"key":"S0022481200053743_ref016","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1973-0325498-2"},{"key":"S0022481200053743_ref015","volume-title":"Publicationes Mathematicae (Debrecen)","author":"Neumann"},{"key":"S0022481200053743_ref014","first-page":"520","article-title":"Nondiscernible properties of finite systems of identity relations","volume":"196","author":"Murski\u01d0","year":"1971","journal-title":"Doklady Academii Nauk SSSR"},{"key":"S0022481200053743_ref013","unstructured":"McNulty G. , The decision problem for equational bases of algebras, Thesis, University of California, Berkeley, 1971."},{"key":"S0022481200053743_ref011","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10984"},{"key":"S0022481200053743_ref009","volume-title":"Cylindric algebras: I","author":"Henkin","year":"1971"},{"key":"S0022481200053743_ref007","doi-asserted-by":"publisher","DOI":"10.2307\/2035450"},{"key":"S0022481200053743_ref005","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19670131304"},{"key":"S0022481200053743_ref002","first-page":"264","volume":"30","author":"Bennett","year":"1965","journal-title":"Equational spectra"},{"key":"S0022481200053743_ref017","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093956081"},{"key":"S0022481200053743_ref010","first-page":"5","article-title":"Effective inseparability of the sets of identically true formulae and finitely refutable formulae for certain elementary theories","volume":"1","author":"Lavrov","year":"1963","journal-title":"Algebra i Logika (2)"},{"key":"S0022481200053743_ref020","first-page":"275","volume-title":"Contributions to mathematical logic","author":"Tarski","year":"1968"},{"key":"S0022481200053743_ref006","volume-title":"Universal algebra","author":"Gr\u00e4tzer","year":"1968"},{"key":"S0022481200053743_ref012","first-page":"A","article-title":"Simple undecidable problems about finite groupoids","volume":"20","author":"McKenzie","year":"1973","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200053743_ref004","doi-asserted-by":"publisher","DOI":"10.1070\/RM1965v020n04ABEH001188"},{"key":"S0022481200053743_ref008","first-page":"697","article-title":"Equational spectra and reduction of identities","volume":"14","author":"Gr\u00e4tzer","year":"1967","journal-title":"Notices of the American Mathematical Society"},{"key":"S0022481200053743_ref018","doi-asserted-by":"publisher","DOI":"10.1007\/BF01578706"},{"key":"S0022481200053743_ref003","doi-asserted-by":"publisher","DOI":"10.1007\/BF02944998"},{"key":"S0022481200053743_ref001","volume-title":"Models and ultraproducts: An introduction","author":"Bell","year":"1969"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200053743","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T19:40:49Z","timestamp":1559158849000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200053743\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1975,6]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1975,6]]}},"alternative-id":["S0022481200053743"],"URL":"https:\/\/doi.org\/10.2307\/2271899","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1975,6]]}}}