{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T02:36:50Z","timestamp":1768531010519,"version":"3.49.0"},"reference-count":18,"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":1015,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2011,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the extension of monadic second-order logic of order with cardinality quantifiers \u201cthere exists uncountably many sets such that\u2026\u201d and \u201cthere exists continuum many sets such that \u2026 \u201d. We prove that over the class of countable linear orders the two quantifiers are equivalent and can be effectively and uniformly eliminated. Weaker or partial elimination results are obtained for certain wider classes of chains. In particular, we show that over the class of ordinals the uncountability quantifier can be effectively and uniformly eliminated. Our argument makes use of Shelah's composition method and Ramsey-like theorem for dense linear orders.<\/jats:p>","DOI":"10.2178\/jsl\/1305810766","type":"journal-article","created":{"date-parts":[[2011,5,19]],"date-time":"2011-05-19T13:18:58Z","timestamp":1305811138000},"page":"603-619","source":"Crossref","is-referenced-by-count":1,"title":["Expressing cardinality quantifiers in monadic second-order logic over chains"],"prefix":"10.1017","volume":"76","author":[{"given":"Vince","family":"B\u00e1r\u00e1ny","sequence":"first","affiliation":[]},{"given":"\u0141ukasz","family":"Kaiser","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Rabinovich","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200001869_ref018","first-page":"103","article-title":"Finite automata and the logic of one-place predicates","volume":"13","author":"Trakhtenbrot","year":"1962","journal-title":"Siberian Mathematical Journal"},{"key":"S0022481200001869_ref017","first-page":"326","article-title":"Finite automata and the logic of monadic predicates","volume":"140","author":"Trakhtenbrot","year":"1961","journal-title":"Rossi\u012dskaya Akademiya Nauk. Doklady Akademii Nauk. SSSR"},{"key":"S0022481200001869_ref015","first-page":"367","volume-title":"Mathematical Foundations of Computer Science, MFCS'91, Proceedings","volume":"520","author":"Niwi\u0144ski","year":"1991"},{"key":"S0022481200001869_ref011","first-page":"491","volume":"44","author":"Gurevich","year":"1979","journal-title":"Modest theory of short chains II"},{"key":"S0022481200001869_ref016","doi-asserted-by":"publisher","DOI":"10.2307\/1971037"},{"key":"S0022481200001869_ref010","first-page":"387","volume":"48","author":"Gurevich","year":"1983","journal-title":"The monadic theory of \u03c92"},{"key":"S0022481200001869_ref009","first-page":"479","volume-title":"Model-theoretical logics","author":"Gurevich","year":"1985"},{"key":"S0022481200001869_ref007","doi-asserted-by":"publisher","DOI":"10.1007\/BF02756489"},{"key":"S0022481200001869_ref005","volume-title":"The monadic second order theory of all countable ordinals","volume":"328","author":"B\u00fcchi","year":"1973"},{"key":"S0022481200001869_ref002","volume-title":"Decidability and generalized quantifiers","author":"Baudisch","year":"1980"},{"key":"S0022481200001869_ref001","doi-asserted-by":"crossref","DOI":"10.3233\/FI-2010-260","article-title":"Expressing cardinality quantifiers in monadic second-order logic over trees","volume":"100","author":"B\u00e1r\u00e1ny","year":"2010","journal-title":"Fundamenta Informaticae"},{"key":"S0022481200001869_ref013","first-page":"129","volume":"73","author":"Kuske","year":"2008","journal-title":"First-order and counting theories of omega-automatic structures"},{"key":"S0022481200001869_ref012","first-page":"123","volume-title":"Model theoretic logics","author":"Kaufmann","year":"1985"},{"key":"S0022481200001869_ref004","first-page":"1","volume-title":"Proceedings of the international congress on logic, methodology and philosophy of science","volume":"44","author":"B\u00fcchi","year":"1962"},{"key":"S0022481200001869_ref008","first-page":"481","volume":"44","author":"Gurevich","year":"1979","journal-title":"Modest theory of short chains I"},{"key":"S0022481200001869_ref003","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19600060105"},{"key":"S0022481200001869_ref006","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1961-0139530-9"},{"key":"S0022481200001869_ref014","doi-asserted-by":"publisher","DOI":"10.4064\/fm-44-1-12-36"}],"container-title":["The Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200001869","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,19]],"date-time":"2020-06-19T08:19:45Z","timestamp":1592554785000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200001869\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,6]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2011,6]]}},"alternative-id":["S0022481200001869"],"URL":"https:\/\/doi.org\/10.2178\/jsl\/1305810766","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,6]]}}}