Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-20T02:24:18.834Z Has data issue: false hasContentIssue false
  • English
  • Français

Expressing cardinality quantifiers in monadic second-order logic over chains

Published online by Cambridge University Press:  12 March 2014

Vince Bárány ,
Łukasz Kaiser  and
Alexander Rabinovich
Vince Bárány
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Ox1 3QD, Oxford, UK, E-mail: [email protected]
Łukasz Kaiser
Affiliation:
Laboratoire d'Informatique Algorithmique: Fondements et Applications & CNRS, Université Paris Diderot, 75205 Paris, France, E-mail: [email protected]
Alexander Rabinovich
Affiliation:
Tel Aviv University, The Blavatnik School of Computer Science, Ramat Aviv, Tel Aviv 69978, Israel, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We investigate the extension of monadic second-order logic of order with cardinality quantifiers “there exists uncountably many sets such that…” and “there exists continuum many sets such that … ”. 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.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 76 , Issue 2 , June 2011 , pp. 603 - 619
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Bárány, V., Kaiser, Ł., and Rabinovich, A., Expressing cardinality quantifiers in monadic second-order logic over trees, Fundamenta Informaticae, vol. 100 (2010).CrossRefGoogle Scholar
[2]Baudisch, A., Seese, D., Tuschik, H.-P., and Weese, M., Decidability and generalized quantifiers, Akademie-Verlag, Berlin, 1980.Google Scholar
[3]Büchi, Julius R., Weak second-order arithmetic andfinite automata, Zeitschrift für mathematische Logik und Grundlagen der Mathematik, vol. 6 (1960), pp. 66–92.CrossRefGoogle Scholar
[4]Büchi, Julius R., On decision method in restricted second order arithmetic, Proceedings of the international congress on logic, methodology and philosophy of science (Nagel, E., Suppes, P., and Tarski, A., editors), Studies in Logic and the Foundations of Mathematics, vol. 44, Elsevier, 1962, pp. 1–11.Google Scholar
[5]Büchi, Julius R. and Siefkes, Dirk, The monadic second order theory of all countable ordinals, Lecture Notes in Mathematics, vol. 328, Springer, 1973.Google Scholar
[6]Elgot, Calvin C., Decision problems of finite automata design and related arithmetics, Transactions of the American Mathematical Society, vol. 98 (1961), pp. 21–51.CrossRefGoogle Scholar
[7]Gurevich, Yuri, Monadic theory of order and topology, I, Israel Journal of Mathematics, vol. 27 (1977), pp. 299–319.CrossRefGoogle Scholar
[8]Gurevich, Yuri, Modest theory of short chains I, this Journal, vol. 44 (1979), pp. 481–490.Google Scholar
[9]Gurevich, Yuri, Monadic second-order theories, Model-theoretical logics (Barwise, Jon and Feferman, Solomon, editors), Springer, 1985, pp. 479–506.Google Scholar
[10]Gurevich, Yuri, Magidor, Menachem, and Shelah, Saharon, The monadic theory of ω2, this Journal, vol. 48 (1983), pp. 387–398.Google Scholar
[11]Gurevich, Yuri and Shelah, Saharon, Modest theory of short chains II, this Journal, vol. 44 (1979), pp. 491–502.Google Scholar
[12]Kaufmann, Matt, The quantifier “there exists uncountably many” and some of its relatives, Model theoretic logics (Barwise, J. and Feferman, S., editors), Springer-Verlag, 1985, pp. 123–176.Google Scholar
[13]Kuske, Dietrich and Lohrey, Markus, First-order and counting theories of omega-automatic structures, this Journal, vol. 73 (2008), pp. 129–150.Google Scholar
[14]Mostowski, Andrzej, On a generalization of quantifiers, Fundamenta Mathematicae, vol. 44 (1957), pp. 12–36.CrossRefGoogle Scholar
[15]Niwiński, Damian, On the cardinality of sets of infinite trees recognizable by finite automata. Mathematical Foundations of Computer Science, MFCS'91, Proceedings, Lecture Notes in Computer Science, vol. 520, Springer, 1991, pp. 367–376.Google Scholar
[16]Shelah, Saharon, The monadic theory of order, Annals of Mathematics, vol. 102 (1975), pp. 379–419.CrossRefGoogle Scholar
[17]Trakhtenbrot, Boris A., Finite automata and the logic of monadic predicates, Rossiĭskaya Akademiya Nauk. Doklady Akademii Nauk. SSSR, vol. 140 (1961), pp. 326–329.Google Scholar
[18]Trakhtenbrot, Boris A., Finite automata and the logic of one-place predicates, Siberian Mathematical Journal, vol. 13 (1962), pp. 103–131, in Russian.Google Scholar