The full binary tree cannot be interpreted in a chain

Journal of Symbolic Logic 75 (4):1489-1498 (2010)
  Copy   BIBTEX

Abstract

We show that for no chain C there is a monadic-second order interpretation of the full binary tree in C

Categories

Keywords

Reprint years

DOI

10.2178/jsl/1286198158

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,369

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Rabin's uniformization problem.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (4):1105-1119.
On countable chains having decidable monadic theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
Monadic second order definable relations on the binary tree.Hans Läuchli & Christian Savioz - 1987 - Journal of Symbolic Logic 52 (1):219-226.
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.
Hindman’s theorem for sums along the full binary tree, $$\Sigma ^0_2$$ Σ 2 0 -induction and the Pigeonhole principle for trees. [REVIEW]Lorenzo Carlucci & Daniele Tavernelli - 2022 - Archive for Mathematical Logic 61 (5):827-839.
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.
On the strength of the interpretation method.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (2):305-323.
An axiomatization of full computation tree logic.M. Reynolds - 2001 - Journal of Symbolic Logic 66 (3):1011-1057.
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.

Analytics

Added to PP
2010-09-12

Downloads
30 (#757,175)

6 months
8 (#605,434)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Linear Orderings.Joseph G. Rosenstein - 1983 - Journal of Symbolic Logic 48 (4):1207-1209.
Random graphs in the monadic theory of order.Shmuel Lifsches & Saharon Shelah - 1999 - Archive for Mathematical Logic 38 (4-5):273-312.

Add more references