ON COUNTABLE CHAINS HAVING DECIDABLE MONADIC THEORY

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. §1. Introduction. The study of decidability of logical theories is a well-established research topic with numerous applications in Computer Science, in particular in the field of verification. Many techniques have been developed to build larger and larger classes of structures with a decidable theory. For an overview of recent related results in the framework of monadic second order (shortly: MSO) theorie