Worst-case expansions of complete theories

DOI10.2140/MT.2022.1.15arXiv2107.10920OpenAlexW3186178098WikidataQ114045324 ScholiaQ114045324MaRDI QIDQ6156871FDOQ6156871

Authors: Samuel Braunfeld, M. C. Laskowski 

Publication date: 19 June 2023

Published in: Model Theory (Search for Journal in Brave)

Abstract: Given a complete theory $T$ and a subset $Ysubseteq{X}^k$, we precisely determine the {em worst case complexity}, with respect to further monadic expansions, of an expansion $(M,Y)$ by $Y$ of a model $M$ of $T$ with universe $X$. In particular, although by definition monadically stable/NIP theories are robust under arbitrary monadic expansions, we show that monadically NFCP (equivalently, mutually algebraic) theories are the largest class that is robust under anything beyond monadic expansions. We also exhibit a paradigmatic structure for the failure of each of monadic NFCP/stable/NIP and prove each of these paradigms definably embeds into a monadic expansion of a sufficiently saturated model of any theory without the corresponding property.

Full work available at URL: https://arxiv.org/abs/2107.10920

zbMATH Keywords

mutually algebraicmonadic expansions

Mathematics Subject Classification ID

Classification theory, stability, and related concepts in model theory (03C45)

Cites Work

• A Guide to NIP Theories
• Second-order quantifiers and the complexity of theories
• Monadic logic and Löwenheim numbers
• Some trivial considerations
• The elementary diagram of a trivial, weakly minimal structure is near model complete
• Mutually algebraic structures and expansions by predicates
• Uniformly bounded arrays and mutually algebraic structures
• Mutual algebraicity and cellularity
• Characterizations of monadic NIP

Cited In (4)

• Collapsing and separating completeness notions under average-case and worst-case hypotheses
• The Theory of WSTS: The Case of Complete WSTS
• Exact Worst Case TCAM Rule Expansion
• Undecidable first-order theories of affine geometries

This page was built for publication: Worst-case expansions of complete theories

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6156871)