- 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
Monadic second order definable relations on the binary tree
Journal of Symbolic Logic 52 (1):219-226 (1987)
Abstract
Let S2S [WS2S] espectively be the storn [weak] monadic second order theory of the binary tree T in the language of two successor functions. An S2S-formula whose free variables are just individual variables defines a relation on T (rather than on the power set of T). We show that S2S and WS2S define the same relations on T, and we give a simple characterization of these relationsLinks
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 Equivalence of Tree Adjoining Grammars and Monadic Linear Context-free Tree Grammars.Stephan Kepser & Jim Rogers - 2011 - Journal of Logic, Language and Information 20 (3):361-384.
On spectra of sentences of monadic second order logic with counting.E. Fischer & J. A. Makowsky - 2004 - Journal of Symbolic Logic 69 (3):617-640.
Uniformization, choice functions and well orders in the class of trees.Shmuel Lifsches & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (4):1206-1227.
Characterizing Definability of Second-Order Generalized Quantifiers.Juha Kontinen & Jakub Szymanik - 2011 - In L. Beklemishev & R. de Queiroz (eds.), Proceedings of the 18th Workshop on Logic, Language, Information and Computation, Lecture Notes in Artificial Intelligence 6642. Springer.
Relations in monadic third-order logic.A. P. Hazen - 1997 - Journal of Philosophical Logic 26 (6):619-628.
Monadic binary relations and the monad systems at near-standard points.Nader Vakil - 1987 - Journal of Symbolic Logic 52 (3):689-697.
On the consistency of the definable tree property on ℵ.Amir Leshem - 2000 - Journal of Symbolic Logic 65 (3):1204 - 1214.
Rabin's uniformization problem.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (4):1105-1119.
Analytics
Added to PP
2009-01-28
Downloads
22 (#692,982)
6 months
2 (#1,240,909)
2009-01-28
Downloads
22 (#692,982)
6 months
2 (#1,240,909)
Historical graph of downloads
Citations of this work
To know or not to know: epistemic approaches to security protocol verification.Francien Dechesne & Yanjing Wang - 2010 - Synthese 177 (S1):51-76.
References found in this work
On the bounded monadic theory of well-ordered structures.Wolfgang Thomas - 1980 - Journal of Symbolic Logic 45 (2):334-338.
Logical Complexity of Some Classes of Tree Languages Generated by Multiple‐Tree‐Automata.Wojciech Buszkowski - 1980 - Mathematical Logic Quarterly 26 (1‐6):41-49.
Logical Complexity of Some Classes of Tree Languages Generated by Multiple‐Tree‐Automata.Wojciech Buszkowski - 1980 - Mathematical Logic Quarterly 26 (1-6):41-49.
Restricted Set-Theoretical Definitions in Arithmetic.Raphael M. Robinson - 1966 - Journal of Symbolic Logic 31 (4):659-660.
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-7c76586df8-4c2ch uwo