Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T17:18:35.793Z Has data issue: false hasContentIssue false

On countable chains having decidable monadic theory

Published online by Cambridge University Press:  12 March 2014

Alexis Bés
Affiliation:
University of Paris-Est Créteil, Laboratoire d'Algorithmique, Complexité et Logique, Faculté des Sciences et Technologie, 61 Avenue du Général de Gaulle, 94010 Créteil, France, E-mail: bes@u-pec.fr
Alexander Rabinovich
Affiliation:
The Blavatnik School of Computer Science, Sackler Faculty of Exact Sciences, Tel Aviv University, Ramat Aviv 69978, Tel Aviv, Israel, E-mail: rabinoa@post.tau.ac.il

Abstract

Rationals and countable ordinals are important examples of structures with decidable monadic second-order theories. A chain is an expansion of a linear order by monadic predicates. We 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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2012

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable