Second-order quantifiers and the complexity of theories
The study of properties of models which are not first-order expressible and the study of the relative complexity of various theories in an arbitrary logic are combined in the following programme. Consider two theories \(T_ 1\) and \(T_ 2\) formulated in a logic L. To compare their strengths, choose a stronger logic \(L^ 1\). Now think of \(T_ 1\) and \(T_ 2\) as \(L^ 1\)-theories and investigate their properties. The authors classify all theories of the form (T,L) where (T,L) is the collection of L sentences valid on the models of the complete first-order theory T and L is one of the following: second-order logic, permutational logic, or monadic logic. They partition those theories, in which second- order logic cannot be interpreted, into four classes and find a prototype for each class. One of the classes contains unstable theories, the other three are stable. In the unstable case it is shown that the permutational theory of the class interprets second-order logic and that the monadic theory of the class is at least as complicated as the monadic theory of order. All the monadic theories have the same Löwenheim number - that of second-order logic. But the Hanf number of the monadic theory of order is strictly less than the Hanf number of second-order logic. In the other three cases each model of the theory with cardinality \(\lambda\) is associated with a tree of height \(<\aleph_ 1\). The three cases correspond to \(\lambda^{<\aleph_ 1}\), the full tree \(\lambda^{<\omega}\) and well-founded subtrees of \(\lambda^{<\omega}\). The Löwenheim and Hanf numbers of such theories are computed. Much of the paper is devoted to answering the following question: why does research in monadic logic focus on theories of order and trees and why is research in permutational logic concerned entirely with the theory of equality? The paper can be viewed as propaganda for classification theory as the present material demonstrates the importance of the earlier work on classification theory by applying it in a nontrivial context.
- Monadic logic and Löwenheim numbers
- More on monadic logic. Part D: A note on addition of theories
- Notes on monadic logic. Part B: Complexity of linear orders in ZFC
- More on monadic logic. C: Monadically interpreting in stable unsuperstable \(\mathcal T\) and the monadic theory of \(^{\omega}\lambda\)
- The monadic theory of ω2
- Monadic logic and Löwenheim numbers
- Lower bound results on lengths of second-order formulas
- First-order theories of abstract dependence relations
- Trivial pursuit: remarks on the main gap
- A note on the Hanf number of second-order logic
- Notes on monadic logic. A: Monadic theory of the real line
- Monadic \(\Pi _ 1^ 1\)-theories of \(\Pi _ 1^ 1\)-properties
- Ranks and pregeometries in finite diagrams
- Elementary equivalence of infinite-dimensional classical groups
- Toward classifying unstable theories
- Regular partitions of gentle graphs
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Strict superstablity and decidability of certain generic graphs
- A model-theoretic characterisation of clique width
- More on monadic logic. Part D: A note on addition of theories
- Simple monadic theories and indiscernibles
- Simple monadic theories and partition width
- Interpreting second-order logic in the monadic theory of order
- Complete Coinductive Theories. I
- On an interpretation of second order quantification in first order intuitionistic propositional logic
- ℵ0-categorical tree-decomposable structures
- scientific article; zbMATH DE number 1303431 (Why is no real title available?)
- Peano arithmetic may not be interpretable in the monadic theory of linear orders
- scientific article; zbMATH DE number 1163945 (Why is no real title available?)
- Compatibility of Shelah and Stupp's and Muchnik's iteration with fragments of monadic second order logic
- Mutually algebraic structures and expansions by predicates
- Theories with few non-algebraic types over models, and their decompositions
- Characterizations of monadic NIP
- The hierarchy theorem for second order generalized quantifiers
- Locally modular theories of finite rank
- Monadic stability and growth rates of ω$\omega$‐categorical structures
- Worst-case expansions of complete theories
- Stable graphs of bounded twin-width
- Model checking on interpretations of classes of bounded local cliquewidth
- Existential characterizations of monadic NIP
- Triviality, NDOP and stable varieties
- Indiscernibles in monadically NIP theories
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- On first-order transductions of classes of graphs
- Twin-width. VIII: Delineation and win-wins
- Planar graphs with separation are dp-minimal
- Decomposition horizons: from graph sparsity to model-theoretic dividing lines (extended abstract)
- Twin-width. IV: Ordered graphs and matrices
- First-order transductions of graphs (invited talk)
- Extension preservation on dense graph classes
- Twin-width. VIIIa: Delineation
- Separability properties of monadically dependent graph classes
- Forbidden induced subgraphs for bounded shrub-depth and the expressive power of MSO
- Notes on monadic logic. Part B: Complexity of linear orders in ZFC
- More on monadic logic. C: Monadically interpreting in stable unsuperstable \(\mathcal T\) and the monadic theory of \(^{\omega}\lambda\)
- Some coinductive graphs
This page was built for publication: Second-order quantifiers and the complexity of theories
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1078169)
