{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T02:54:37Z","timestamp":1777517677236,"version":"3.51.4"},"reference-count":15,"publisher":"SAGE Publications","issue":"2","license":[{"start":{"date-parts":[[2015,7,1]],"date-time":"2015-07-01T00:00:00Z","timestamp":1435708800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["Computability"],"published-print":{"date-parts":[[2015,7,24]]},"abstract":"<jats:p>Abstract<\/jats:p>\n                  <jats:p>Let \u03c3 be a signature and [Formula: see text] a \u03c3-structure with domain [Formula: see text]. Say that a monadic second-order \u03c3-formula is [Formula: see text] iff it has the form [Formula: see text] with [Formula: see text] set variables and \u03c8 containing no set quantifiers. Consider the following properties: for each positive integer n, the set of [Formula: see text]- \u03c3-sentences true in [Formula: see text] is [Formula: see text]-complete; for each positive integer n, if a set of natural numbers is [Formula: see text]-definable (i.e. by a [Formula: see text]-formula) in the standard model of arithmetic and closed under automorphisms of [Formula: see text], then it is [Formula: see text]-definable in [Formula: see text]. We use \u2223 and \u22a5 to denote the divisibility relation and the coprimeness relation respectively. Given a prime p, let [Formula: see text] be the function which maps every pair [Formula: see text] of natural numbers into [Formula: see text]. In this article we prove: [Formula: see text] and all [Formula: see text] have both [Formula: see text] and [Formula: see text]; in effect, even [Formula: see text] has [Formula: see text]. Notice \u2013 these results readily generalise to arbitrary arithmetical expansions of the corresponding structures, provided that the extended signature is finite.<\/jats:p>","DOI":"10.3233\/com-150036","type":"journal-article","created":{"date-parts":[[2015,7,26]],"date-time":"2015-07-26T09:13:12Z","timestamp":1437901992000},"page":"159-174","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":5,"title":["Some new results in monadic second-order arithmetic"],"prefix":"10.1177","volume":"4","author":[{"given":"Stanislav O.","family":"Speranski","sequence":"first","affiliation":[{"name":"Sobolev Institute of Mathematics, Novosibirsk, Russia. ."}]}],"member":"179","published-online":{"date-parts":[[2015,7,1]]},"reference":[{"key":"ref001","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-0072(97)85376-6"},{"key":"ref002","unstructured":"[2]A.\u00a0B\u00e8s, A survey of arithmetical definability, in: A Tribute to Maurice Boffa, M.\u00a0Crabb\u00e9 et al., eds, Soci\u00e9t\u00e9 Math\u00e9matique de Belgique, 2002, pp.\u00a01\u201354."},{"key":"ref003","doi-asserted-by":"publisher","DOI":"10.4064\/fm-156-2-111-129"},{"key":"ref004","doi-asserted-by":"publisher","DOI":"10.2307\/2586837"},{"key":"ref005","unstructured":"[5]J.R.\u00a0B\u00fcchi, On a decision method in restricted second order arithmetic, in: Logic, Methodology and Philosophy of Science, E.\u00a0Nagel, P.\u00a0Suppes and A.\u00a0Tarski, eds, Stanford University Press, 1962, pp.\u00a01\u201311."},{"key":"ref006","doi-asserted-by":"publisher","DOI":"10.1007\/BF02127802"},{"key":"ref007","doi-asserted-by":"publisher","DOI":"10.2307\/2274706"},{"key":"ref008","first-page":"53","volume":"318","author":"Korec I.","year":"1993","journal-title":"Grazer Mathematische Berichte"},{"key":"ref009","unstructured":"[9]I.\u00a0Korec, Elementary theories of structures containing generalized Pascal triangles modulo a prime, in: Discrete Mathematics and Applications, Blagoevgrad\/Predel, 1994, S.\u00a0Shtrakov and I.\u00a0Mirchev, eds, Blagoevgrad, 1995, pp.\u00a091\u2013102."},{"key":"ref010","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00113-4"},{"key":"ref011","doi-asserted-by":"publisher","DOI":"10.2307\/2275735"},{"key":"ref012","first-page":"1","volume":"141","author":"Rabin M.O.","year":"1969","journal-title":"Transactions of the American Mathematical Society"},{"key":"ref013","doi-asserted-by":"publisher","DOI":"10.2307\/2266510"},{"key":"ref014","doi-asserted-by":"publisher","DOI":"10.1007\/s00153-013-0328-9"},{"key":"ref015","unstructured":"[15]S.O.\u00a0Speranski, Quantifying over events in probability logic: an introduction,\n                      Mathematical Structures in Computer Science\n                      (2015), accepted for publication."}],"container-title":["Computability"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-150036","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.3233\/COM-150036","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.3233\/COM-150036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,28]],"date-time":"2026-04-28T16:03:12Z","timestamp":1777392192000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/COM-150036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,7,1]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,7,24]]}},"alternative-id":["10.3233\/COM-150036"],"URL":"https:\/\/doi.org\/10.3233\/com-150036","relation":{},"ISSN":["2211-3568","2211-3576"],"issn-type":[{"value":"2211-3568","type":"print"},{"value":"2211-3576","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,7,1]]}}}