- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
On countable chains having decidable monadic theory
Journal of Symbolic Logic 77 (2):593-608 (2012)
Abstract
Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We show that if the monadic second-order theory of a countable chain C is decidable then C has a non-trivial expansion with decidable monadic second-order theoryLinks
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
Peano arithmetic may not be interpretable in the monadic theory of linear orders.Shmuel Lifsches & Saharon Shelah - 1997 - Journal of Symbolic Logic 62 (3):848-872.
The monadic second order theory of all countable ordinals.J. Richard Büchi - 1973 - New York,: Springer. Edited by Dirk Siefkes.
Peano Arithmetic May Not be Interpretable in the Monadic Theory of Linear Orders.Shmuel Lifsches & Saharon Shelah - 1997 - Journal of Symbolic Logic 62 (3):848-872.
The complete extensions of the monadic second order theory of countable ordinals.J. Richard Büchi & Dirk Siefkes - 1983 - Mathematical Logic Quarterly 29 (5):289-312.
Logical aspects of Cayley-graphs: the group case.Dietrich Kuske & Markus Lohrey - 2004 - Annals of Pure and Applied Logic 131 (1-3):263-286.
Decidable Theories I. Büchi's Monadic Second Order Successor Arithmetic.Dirk Siefkes - 1976 - Studia Logica 35 (2):203-205.
The structure of the models of decidable monadic theories of graphs.D. Seese - 1991 - Annals of Pure and Applied Logic 53 (2):169-195.
SIEFKES, D. Decidable theories I. Buchi's monadic second order successor arithmetic. [REVIEW]R. Kolodziej - 1976 - Studia Logica 35:203.
Interpreting the weak monadic second order theory of the ordered rationals.John K. Truss - 2022 - Mathematical Logic Quarterly 68 (1):74-78.
The monadic second-order logic of graphs VIII: Orientations.Bruno Courcelle - 1995 - Annals of Pure and Applied Logic 72 (2):103-143.
Analytics
Added to PP
2012-04-05
Downloads
39 (#115,291)
6 months
12 (#1,086,452)
2012-04-05
Downloads
39 (#115,291)
6 months
12 (#1,086,452)
Historical graph of downloads
References found in this work
Decidability and undecidability of extensions of second (first) order theory of (generalized) successor.Calvin C. Elgot & Michael O. Rabin - 1966 - Journal of Symbolic Logic 31 (2):169-181.
Algorithmic uses of the Feferman–Vaught Theorem.J. A. Makowsky - 2004 - Annals of Pure and Applied Logic 126 (1-3):159-213.
Interpreting second-order logic in the monadic theory of order.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (3):816-828.
Deterministic automata and the monadic theory of ordinals < ω2.J. Richard Büchi & Charles Zaiontz - 1983 - Mathematical Logic Quarterly 29 (5):313-336.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-6686886f5-sqlzn uwo