{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,3]],"date-time":"2022-04-03T07:18:01Z","timestamp":1648970281893},"reference-count":37,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":9963,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1986,12]]},"abstract":"<jats:p>Alfred Tarski identified decidability within various logical formalisms as one of the principal themes for investigation in mathematical logic. This is evident already in the focus of the seminar he organized in Warsaw in 1926. Over the ensuing fifty-five years, Tarski put forth a steady stream of theorems concerning decidability, many with far-reaching consequences. Just as the work of the 1926 seminar reflected Tarski's profound early interest in decidability, so does his last work, <jats:italic><jats:bold>A formalization of set theory without variables<\/jats:bold><\/jats:italic>, a monograph written in collaboration with S. Givant [8\u2212<jats:sup>m<\/jats:sup>]. An account of the Warsaw seminar can be found in Vaught [1986].<\/jats:p><jats:p>Tarski's work on decidability falls into four broad areas: elementary theories which are decidable, elementary theories which are undecidable, the undecidability of theories of various restricted kinds, and what might be called decision problems of the second degree. An account of Tarski's work with decidable elementary theories can be found in Doner and van den Dries [1987] and in Monk [1986] (for Boolean algebras). Vaught [1986] discusses Tarski's contributions to the method of quantifier elimination. Our principal concern here is Tarski's work in the remaining three areas.<\/jats:p><jats:p>We will say that a set of elementary sentences is a <jats:italic>theory<\/jats:italic> provided it is closed with respect to logical consequence and we will say that a theory is <jats:italic>decidable<\/jats:italic> or <jats:italic>undecidable<\/jats:italic> depending on whether it is a recursive or nonrecursive set. The notion of a theory may be restricted in a number of interesting ways. For example, an <jats:italic>equational theory<\/jats:italic> is just the set of all universal sentences, belonging to some elementary theory, whose quantifier-free parts are equations between terms.<\/jats:p>","DOI":"10.2307\/2273902","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:19:27Z","timestamp":1146939567000},"page":"890-898","source":"Crossref","is-referenced-by-count":2,"title":["Alfred Tarski and undecidable theories"],"prefix":"10.1017","volume":"51","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":"S0022481200030371_ref032","first-page":"1","volume":"12","year":"1947","journal-title":"Recursive unsolvability of a problem of Thue"},{"key":"S0022481200030371_ref033","doi-asserted-by":"publisher","DOI":"10.2307\/1969933"},{"key":"S0022481200030371_ref029","first-page":"1113","volume-title":"Handbook of mathematical logic","year":"1977"},{"key":"S0022481200030371_ref028","volume":"44","year":"1955","journal-title":"Trudy Matemati\u010deskogo Instituta imeni V. A. Steklova"},{"key":"S0022481200030371_ref027","first-page":"297","volume":"42","year":"1977","journal-title":"A lattice of interpretability types of theories"},{"key":"S0022481200030371_ref026","first-page":"520","volume":"196","year":"1971","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200030371_ref025","first-page":"899","volume":"51","year":"1986","journal-title":"The contributions of Alfred Tarski to algebraic logic"},{"key":"S0022481200030371_ref023","first-page":"389","volume":"8","year":"1982","journal-title":"Houston Journal of Mathematics"},{"key":"S0022481200030371_ref022","first-page":"186","volume":"40","year":"1975","journal-title":"On spectra, and the negative solution of the decision problem for identities having a finite nontrivial model"},{"key":"S0022481200030371_ref021","first-page":"953","volume":"77","year":"1951","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200030371_ref020","first-page":"19","volume":"77","year":"1951","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200030371_ref019","first-page":"587","volume":"55","year":"1947","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200030371_ref018","volume-title":"The metamathematics of algebraic systems: collected papers 1936\u20131967","year":"1971"},{"key":"S0022481200030371_ref017","first-page":"3","volume":"69","year":"1966","journal-title":"Matemati\u010deski\u01d0 Sbornik"},{"key":"S0022481200030371_ref016","first-page":"311","volume":"45","year":"1980","journal-title":"The equational theory of CA3 is undecidable"},{"key":"S0022481200030371_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02485385"},{"key":"S0022481200030371_ref013","doi-asserted-by":"publisher","DOI":"10.2307\/1969375"},{"key":"S0022481200030371_ref012","first-page":"50","volume":"55","year":"1949","journal-title":"Bulletin of the American Mathematical Society"},{"key":"S0022481200030371_ref011","first-page":"883","volume":"51","year":"1986","journal-title":"The contributions of Alfred Tarski to general algebra"},{"key":"S0022481200030371_ref041","first-page":"20","volume":"17","year":"1978","journal-title":"Algebra i Logika"},{"key":"S0022481200030371_ref040","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093957737"},{"key":"S0022481200030371_ref009","volume-title":"The lattice of interpretability types of varieties","year":"1984"},{"key":"S0022481200030371_ref008","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1980-0576864-X"},{"key":"S0022481200030371_ref007","first-page":"37","volume":"20","year":"1965","journal-title":"Uspehi Matemati\u010deskih Nauk"},{"key":"S0022481200030371_ref039","first-page":"869","volume":"51","year":"1986","journal-title":"Alfred Tarski's work in model theory"},{"key":"S0022481200030371_ref038","first-page":"129","volume-title":"Logic, foundations of mathematics, and computability theory (proceedings, London, Ontario, 1975","year":"1977"},{"key":"S0022481200030371_ref005","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"S0022481200030371_ref037","doi-asserted-by":"publisher","DOI":"10.1305\/ndjfl\/1093893456"},{"key":"S0022481200030371_ref004","first-page":"40","volume":"1","year":"1936","journal-title":"A note on the Entscheidungsproblem"},{"key":"S0022481200030371_ref036","first-page":"87","volume":"1","year":"1936","journal-title":"Extensions of some theorems of G\u00f6del and Church"},{"key":"S0022481200030371_ref003","volume-title":"Decidability and Boolean representations","year":"1981"},{"key":"S0022481200030371_ref010","first-page":"173","volume":"38","year":"1931","journal-title":"Principia Mathematica"},{"key":"S0022481200030371_ref035","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1950-0038912-1"},{"key":"S0022481200030371_ref002","first-page":"231","volume":"16","year":"1954","journal-title":"Indagationes Mathematicae"},{"key":"S0022481200030371_ref034","first-page":"58","volume-title":"Logic, methodology and philosophy of science (proceedings, Jerusalem, 1964","year":"1965"},{"key":"S0022481200030371_ref001","first-page":"13","volume":"123","year":"1958","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200030371_ref031","doi-asserted-by":"publisher","DOI":"10.1007\/BF02485829"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200030371","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T23:09:10Z","timestamp":1558480150000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200030371\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1986,12]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1986,12]]}},"alternative-id":["S0022481200030371"],"URL":"https:\/\/doi.org\/10.2307\/2273902","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1986,12]]}}}