{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T06:53:00Z","timestamp":1760079180384},"reference-count":19,"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":11515,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[1982,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>For every \u03ba \u2208 \u03c9, there is an infinite set <jats:italic>A<\/jats:italic><jats:sub>\u03ba<\/jats:sub> \u2286 \u03c9 and a <jats:italic>d<\/jats:italic>(\u03ba) \u2208 \u03c9 such that for all <jats:italic>Q<\/jats:italic><jats:sub>0<\/jats:sub>, <jats:italic>Q<\/jats:italic><jats:sub>1<\/jats:sub>, \u2286 <jats:italic>A<\/jats:italic><jats:sub>\u03ba<\/jats:sub> where \u2223<jats:italic>Q<\/jats:italic><jats:sub>0<\/jats:sub>\u2223 = \u2223 <jats:italic>Q<\/jats:italic><jats:sub>1<\/jats:sub>\u2223, or <jats:italic>d<\/jats:italic>(\u03ba) &lt; \u2223<jats:italic>Q<\/jats:italic><jats:sub>0<\/jats:sub>\u2223, <jats:italic>Q<\/jats:italic><jats:sub>1<\/jats:sub>\u2223 &lt; \u2135<jats:sub>0<\/jats:sub>, the structures \u2039\u03c9, +, <jats:italic>Q<\/jats:italic><jats:sub>0<\/jats:sub>\u203a and \u2039\u03c9, +, <jats:italic>Q<\/jats:italic><jats:sub>1<\/jats:sub>\u203a are indistinguishable by first-order sentences of quantifier depth \u03ba whose atomic formulas are of the form <jats:italic>u = v, u + v = w<\/jats:italic>, and <jats:italic>Q<\/jats:italic>(<jats:italic>u<\/jats:italic>), where <jats:italic>u, v<\/jats:italic>, and <jats:italic>w<\/jats:italic> are variables.<\/jats:p>","DOI":"10.2307\/2273595","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:00:58Z","timestamp":1146938458000},"page":"659-668","source":"Crossref","is-referenced-by-count":17,"title":["On sets of relations definable by addition"],"prefix":"10.1017","volume":"47","author":[{"given":"James F.","family":"Lynch","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200044029_ref018","doi-asserted-by":"publisher","DOI":"10.1016\/S0003-4843(70)80006-7"},{"key":"S0022481200044029_ref017","first-page":"1","article-title":"Decidability of second-order theories and automata on infinite trees","volume":"141","author":"Rabin","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200044029_ref016","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4684-9452-5"},{"key":"S0022481200044029_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694182"},{"key":"S0022481200044029_ref012","doi-asserted-by":"publisher","DOI":"10.1016\/0003-4843(80)90014-5"},{"key":"S0022481200044029_ref011","first-page":"139","volume":"39","author":"Jones","year":"1974","journal-title":"Turing machines and the spectra of first-order formulas with equality"},{"key":"S0022481200044029_ref009","doi-asserted-by":"publisher","DOI":"10.1007\/BF02759729"},{"key":"S0022481200044029_ref007","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19750210112"},{"key":"S0022481200044029_ref006","first-page":"43","volume-title":"Complexity of computation","author":"Fagin","year":"1974"},{"key":"S0022481200044029_ref005","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"S0022481200044029_ref002","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0022481200044029_ref001","unstructured":"[1] Benda M. , Infinite words as universes (to appear)."},{"key":"S0022481200044029_ref010","unstructured":"[10] Immerman N. , Number of quantifiers is better than number of tape cells, Journal of Computer and Systems Sciences (to appear)."},{"key":"S0022481200044029_ref014","first-page":"131","article-title":"An L\u03c91\u03c9 complete and consistent theory without models","volume":"62","author":"Makkai","year":"1977","journal-title":"Proceedings of the American Mathematical Society"},{"key":"S0022481200044029_ref013","unstructured":"[13] Lynch J. F. , Complexity classes and theories of finite models, Mathematical Systems Theory (to appear)."},{"key":"S0022481200044029_ref003","doi-asserted-by":"publisher","DOI":"10.4064\/fm-43-1-50-68"},{"key":"S0022481200044029_ref004","doi-asserted-by":"publisher","DOI":"10.4064\/fm-49-2-129-141"},{"key":"S0022481200044029_ref019","first-page":"98","volume":"14","author":"Robinson","year":"1949","journal-title":"Definability and decision problems in arithmetics"},{"key":"S0022481200044029_ref008","first-page":"50","volume":"41","author":"Fagin","year":"1976","journal-title":"Probabilities on finite models"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200044029","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T16:47:38Z","timestamp":1558716458000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200044029\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,9]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,9]]}},"alternative-id":["S0022481200044029"],"URL":"https:\/\/doi.org\/10.2307\/2273595","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,9]]}}}