Bárány, Vince; Kaiser, Łukasz; Rabinovich, Alexander Expressing cardinality quantifiers in monadic second-order logic over chains. (English) Zbl 1222.03009 J. Symb. Log. 76, No. 2, 603-619 (2011). Summary: We investigate the extension of monadic second-order logic of order with cardinality quantifiers “there exist uncountably many sets such that \(\dots \)” and “there exist continuum many sets such that \(\dots \)”. 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 a Ramsey-like theorem for dense linear orders. Cited in 1 Document MSC: 03B15 Higher-order logic; type theory (MSC2010) 03C10 Quantifier elimination, model completeness, and related topics 03C80 Logic with extra quantifiers and operators Keywords:extension of monadic second-order logic of order; cardinality quantifiers; countable linear orders; chains; ordinals PDF BibTeX XML Cite \textit{V. Bárány} et al., J. Symb. Log. 76, No. 2, 603--619 (2011; Zbl 1222.03009) Full Text: DOI Link References: [1] Model-theoretical logics pp 479– (1985) [2] The monadic theory of {\(\omega\)}2 48 pp 387– (1983) · Zbl 0549.03010 [3] DOI: 10.1007/BF02756489 · Zbl 0359.02061 [4] DOI: 10.1090/S0002-9947-1961-0139530-9 [5] The monadic second order theory of all countable ordinals 328 (1973) · Zbl 0298.02050 [6] Proceedings of the international congress on logic, methodology and philosophy of science 44 pp 1– (1962) [7] DOI: 10.1002/malq.19600060105 · Zbl 0103.24705 [8] Decidability and generalized quantifiers (1980) · Zbl 0442.03011 [9] Fundamenta Informaticae 100 (2010) [10] Siberian Mathematical Journal 13 pp 103– (1962) [11] Rossiĭskaya Akademiya Nauk. Doklady Akademii Nauk. SSSR 140 pp 326– (1961) [12] DOI: 10.2307/1971037 · Zbl 0345.02034 [13] Mathematical Foundations of Computer Science, MFCS’91, Proceedings 520 pp 367– (1991) [14] Fundamenta Mathematicae 44 pp 12– (1957) [15] First-order and counting theories of omega-automatic structures 73 pp 129– (2008) · Zbl 1141.03015 [16] Model theoretic logics pp 123– (1985) [17] Modest theory of short chains II 44 pp 491– (1979) · Zbl 0464.03014 [18] Modest theory of short chains I 44 pp 481– (1979) · Zbl 0464.03013 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.