Random graphs in the monadic theory of order

&
Archive for Mathematical Logic 38 (4-5):273-312 (1999)
  Copy   BIBTEX

Abstract

We continue the works of Gurevich-Shelah and Lifsches-Shelah by showing that it is consistent with ZFC that the first-order theory of random graphs is not interpretable in the monadic theory of all chains. It is provable from ZFC that the theory of random graphs is not interpretable in the monadic second order theory of short chains (hence, in the monadic theory of the real line)

Categories

Keywords

Reprint years

DOI

10.1007/s001530050129

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,386

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

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.
Modest theory of short chains. II.Yuri Gurevich & Saharon Shelah - 1979 - Journal of Symbolic Logic 44 (4):491-502.
The monadic theory of (ω 2, <) may be complicated.Shmuel Lifsches & Saharon Shelah - 1992 - Archive for Mathematical Logic 31 (3):207-213.
Regular Subgraphs in Graphs and Rooted Graphs and Definability in Monadic Second‐Order Logic.Iain A. Stewart - 1997 - Mathematical Logic Quarterly 43 (1):1-21.
On the strength of the interpretation method.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (2):305-323.
Interpreting second-order logic in the monadic theory of order.Yuri Gurevich & Saharon Shelah - 1983 - Journal of Symbolic Logic 48 (3):816-828.
On countable chains having decidable monadic theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
Reachability is harder for directed than for undirected finite graphs.Miklos Ajtai & Ronald Fagin - 1990 - Journal of Symbolic Logic 55 (1):113-150.
Graph structure and monadic second-order logic: a language-theoretic approach.B. Courcelle - 2012 - New York: Cambridge University Press. Edited by Joost Engelfriet.
The monadic second order theory of all countable ordinals.J. Richard Büchi - 1973 - New York,: Springer. Edited by Dirk Siefkes.
Monadic theory of order and topology in ZFC.Yuri Gurevich & Saharon Shelah - 1982 - Annals of Mathematical Logic 23 (2-3):179-198.
Uniformization, choice functions and well orders in the class of trees.Shmuel Lifsches & Saharon Shelah - 1996 - Journal of Symbolic Logic 61 (4):1206-1227.

Analytics

Added to PP
2013-12-01

Downloads
36 (#434,037)

6 months
2 (#1,240,909)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The full binary tree cannot be interpreted in a chain.Alexander Rabinovich - 2010 - Journal of Symbolic Logic 75 (4):1489-1498.

Add more citations

References found in this work

On the strength of the interpretation method.Yuri Gurevich & Saharon Shelah - 1989 - Journal of Symbolic Logic 54 (2):305-323.

Add more references