- 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 relationsOther Versions
No versions found
Links
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
Rabin's uniformization problem.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (4):1105-1119.
Definability in the monadic second-order theory of successor.J. Richard Buchi & Lawrence H. Landweber - 1969 - Journal of Symbolic Logic 34 (2):166-170.
Representation of Functions and Total Antisymmetric Relations in Monadic Third Order Logic.M. Randall Holmes - 2019 - Journal of Philosophical Logic 48 (2):263-278.
The full binary tree cannot be interpreted in a chain.Alexander Rabinovich - 2010 - Journal of Symbolic Logic 75 (4):1489-1498.
Uniformization, choice functions and well orders in the class of trees.Shmuel Lifsches & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (4):1206-1227.
Binary Relations: Finite Characterizations and Computational Complexity. [REVIEW]Vicki Knoblauch - 2008 - Theory and Decision 65 (1):27-44.
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.
Second-order logic on equivalence relations.Georgi Georgiev & Tinko Tinchev - 2008 - Journal of Applied Non-Classical Logics 18 (2-3):229-246.
Uniformization and Skolem Functions in the Class of Trees.Shmuel Lifsches & Saharon Shelah - 1998 - Journal of Symbolic Logic 63 (1):103-127.
On plural reference and elementary set theory.Helen Morris Cartwright - 1993 - Synthese 96 (2):201-254.
Analytics
Added to PP
2009-01-28
Downloads
138 (#318,171)
6 months
24 (#411,685)
2009-01-28
Downloads
138 (#318,171)
6 months
24 (#411,685)
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.
Definability and decidability of binary predicates for time granularity.Massimo Franceschet, Angelo Montanari, Adriano Peron & Guido Sciavicco - 2006 - Journal of Applied Logic 4 (2):168-191.
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.
Restricted Set-Theoretical Definitions in Arithmetic.Raphael M. Robinson - 1966 - Journal of Symbolic Logic 31 (4):659-660.
Try MATCHA Writer if you're interested in citing directly from PhilPapers and certifying your authorship.
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