Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-22T15:58:46.675Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite state automata and monadic definability of singular cardinals

Published online by Cambridge University Press:  12 March 2014

Itay Neeman
Itay Neeman*
Affiliation:
Department of Mathematics, University of California Los Angeles, Los Angeles, CA 90095-1555, USA, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We define a class of finite state automata acting on transfinite sequences, and use these automata to prove that no singular cardinal can be defined by a monadic second order formula over the ordinals.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 73 , Issue 2 , June 2008 , pp. 412 - 438
Copyright
Copyright © Association for Symbolic Logic 2008

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üchi, J. Richard, Decision methods in the theory of ordinals, Bulletin of the American Mathematical Society, vol. 71 (1965), pp. 767–770.CrossRefGoogle Scholar
[2]Büchi, J. Richard, The monadic second order theory of ω, The monadic second order theory of all countable ordinals (Decidable theories, II), Lecture Notes in Mathematics, vol. 328, Springer, Berlin, 1973, pp. 1–127.Google Scholar
[3]Büchi, J. Richard and Zaiontz, Charles, Deterministic automata and the monadic theory of ordinals < ω2, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, vol. 29 (1983), no. 4, pp. 313–336.CrossRefGoogle Scholar
[4]Gurevich, Y., Monadic second-order theories, Model-theoretic logics, Perspectives in Mathematical Logic, Springer, New York, 1985, pp. 479–506.Google Scholar
[5]Gurevich, Yuri, Magidor, Menachem, and Shelah, Saharon, The monadic theory of ω2, this Journal, vol. 48 (1983), no. 2, pp. 387–398.Google Scholar
[6]Magidor, Menachem, Reflecting stationary sets, this Journal, vol. 47 (1982), no. 4, pp. 755–771 (1983).Google Scholar
[7]Mcnaughton, Robert, Testing and generating infinite sequences by a finite automaton, Information and Control, vol. 9 (1966), pp. 521–530.CrossRefGoogle Scholar
[8]Shelah, Saharon, The monadic theory of order, Annals of Mathematics. Second Series, vol. 102 (1975), no. 3, pp. 379–419.CrossRefGoogle Scholar
[9]Wojciechowski, Jerzy, Classes of transfinite sequences accepted by nondeterministic finite automata, Roczniki Polskiego Towarzystwa Matematycznego. Seria IV. Fundamenta Informaticae, vol. 7 (1984), no. 2, pp. 191–223.Google Scholar
[10]Wojciechowski, Jerzy, Finite automata on transfinite sequences and regular expressions, Roczniki Polskiego Towarzystwa Matematycznego. Seria IV. Fundamenta Informaticae, vol. 8 (1985), no. 3-4, pp. 379–396.Google Scholar