On countable chains having decidable monadic theory

DOI10.2178/JSL/1333566639MaRDI QIDQ2892678zbMATH OpenOpenAlexFDO

Authors Alexis Bès, Alexander Rabinovich

Publication date 19 June 2012

Published in The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://projecteuclid.org/euclid.jsl/1333566639

zbMATH Keywords

countable chainmaximal decidable structuremonadic second-order logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Model theory of denumerable and separable structures (03C15) Second- and higher-order model theory (03C85) Total orders (06A05)

Review text

This is a contribution to a still open problem raised by \textit{C. C. Elgot} and \textit{M. O. Rabin} in [J. Symb. Log. 31, 169--181 (1966; Zbl 0144.24501)] -- asking whether there exist maximal decidable structures, i.e., structures \({\mathfrak M}\) with a decidable first-order (FO) theory and such that the FO-theory of any expansion of \({\mathfrak M}\) by a non-definable predicate is undecidable -- in the framework of monadic second-order logic. The authors 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 theory (a chain is here an expansion of a linear order by monadic predicates).

Recommendations

• scientific article; zbMATH DE number 4087623
• On monadic theories of monadic predicates
• Weakly maximal decidable structures
• Nonmaximal decidable structures

Cites work

• Algorithmic uses of the Feferman-Vaught theorem
• DETERMINISTIC AUTOMATA AND THE MONADIC THEORY OF ORDINALS < ω2
• scientific article; zbMATH DE number 3767656 (Why is no real title available?)
• Interpreting second-order logic in the monadic theory of order
• Modest theory of short chains. I
• Nonmaximal decidable structures
• The monadic theory of ω₂
• The monadic theory of order
• Weakly maximal decidable structures

Cited in

(7)

• Distributive lattices with a decidable monadic second order theory.
• On infinite transition graphs having a decidable monadic theory
• The full binary tree cannot be interpreted in a chain
• It is decidable whether a monadic thue system is canonical over a regular set
• Weakly maximal decidable structures
• scientific article; zbMATH DE number 4087623 (Why is no real title available?)
• Nonmaximal decidable structures

This page was built for publication: On countable chains having decidable monadic theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2892678)