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 (32)

• On what I do not understand (and have something to say), model theory
• Expressiveness of Metric modalities for continuous time
• On the Monadic Second-Order Transduction Hierarchy
• Spectra of monadic second order sentences
• Logics with rigidly guarded data tests
• Satisfiability problems on sums of Kripke frames
• The logical strength of Büchi's decidability theorem
• Recognisable languages over monads
• On the strength of some topological lattices
• Logics of Finite Hankel Rank
• 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
• Trees over Infinite Structures and Path Logics with Synchronization
• Distorted sums of models
• Peano Arithmetic may not be interpretable in the monadic theory of orders
• On factorisation forests
• Register Automata with Extrema Constraints, and an Application to Two-Variable Logic
• A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
• A Strategy for Dynamic Programs: Start over and Muddle through
• Decidable Expansions of Labelled Linear Orderings
• First-Order logic and its Infinitary Quantifier Extensions over Countable Words
• When Do You Start Counting? Revisiting Counting and Pnueli Modalities in Timed Logics
• Compositionality of the MSO+U Logic
• Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
• Toward classifying unstable theories
• Two monads for graphs
• Recursion Schemes, the MSO Logic, and the U quantifier
• Infinite and Bi-infinite Words with Decidable Monadic Theories
• A note on the theory of well orders
• Spectra of Monadic Second-Order Formulas with One Unary Function
• The Pseudofinite Monadic Second Order Theory of Linear Order
• The Church Problem for Countable Ordinals
• Continuous Ramsey theory on Polish spaces and covering the plane by functions