The monadic theory of order

Abstract

We deal with the monadic (second-order) theory of order. We prove all known results in a unified way, show a general way of reduction, prove more results and show the limitation on extending them. We prove (CH) that the monadic theory of the real order is undecidable. Our methods are model-theoretic, and we do not use automaton theory. This is a slightly corrected version of a very old work.

Cited by in corpus (10)

• Spectra of monadic second order sentences
• Recognisable languages over monads
• Languages recognised by finite semigroups, and their generalisations to objects such as trees and graphs, with an emphasis on definability in monadic second-order logic
• On factorisation forests
• Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
• Compositionality of the MSO+U Logic
• First-Order logic and its Infinitary Quantifier Extensions over Countable Words
• When Do You Start Counting? Revisiting Counting and Pnueli Modalities in Timed Logics
• Spectra of Monadic Second-Order Formulas with One Unary Function
• The Pseudofinite Monadic Second Order Theory of Linear Order