{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T19:22:54Z","timestamp":1698348174727},"reference-count":7,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":12795,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1979,3]]},"abstract":"<jats:p>The elementary calculus of binary relations as developed by Tarski in [5] may be thought of as a certain part of the first-order predicate calculus. Though less expressive, its theory (i.e. the set of its valid sentences) was shown to be undecidable by Tarski in [6]. Translated into algebraic logic this means that the equational theory of the class of relation algebras is undecidable. Similarly it can be proved that the same holds for the (sub-) class of proper relation algebras.<\/jats:p><jats:p>The idea in Tarski's proof is to describe a pairing function by which any quantifier prefix may be contracted. In this note we apply a different method to treat the case of finite structures. We prove the<\/jats:p><jats:p>Theorem. <jats:italic>The equational theory of the class of finite proper relation algebras is undecidable<\/jats:italic>.<\/jats:p><jats:p>This result was announced in [4]. The main tool is representing the graph of primitive recursive functions via the cardinalities in finite simple models of equations.<\/jats:p>","DOI":"10.2307\/2273710","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T17:49:34Z","timestamp":1146937774000},"page":"111-115","source":"Crossref","is-referenced-by-count":10,"title":["An undecidability result for relation algebras"],"prefix":"10.1017","volume":"44","author":[{"given":"Wolfgang","family":"Sch\u00f6nfeld","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200048787_ref007","first-page":"569","volume":"70","year":"1950","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0022481200048787_ref006","first-page":"188","volume":"18","year":"1953","journal-title":"Some metalogical results concerning the calculus of relations"},{"key":"S0022481200048787_ref005","first-page":"73","volume":"6","year":"1941","journal-title":"On the calculus of relations"},{"key":"S0022481200048787_ref001","first-page":"50","volume-title":"Theory of computation","year":"1974"},{"key":"S0022481200048787_ref003","doi-asserted-by":"publisher","DOI":"10.2307\/2372074"},{"key":"S0022481200048787_ref002","first-page":"341","volume":"1","year":"1951","journal-title":"University of California Publications in Mathematics"},{"key":"S0022481200048787_ref004","first-page":"A","volume":"24","year":"1977","journal-title":"Notices of the American Mathematical Society"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200048787","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,26]],"date-time":"2019-05-26T17:56:45Z","timestamp":1558893405000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200048787\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1979,3]]},"references-count":7,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1979,3]]}},"alternative-id":["S0022481200048787"],"URL":"https:\/\/doi.org\/10.2307\/2273710","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1979,3]]}}}