Worst-case expansions of complete theories

DOI10.2140/MT.2022.1.15MaRDI QIDQ6156871zbMATH OpenOpenAlexWikidataFDO

Authors Samuel Braunfeld, M. C. Laskowski

Publication date 19 June 2023

Published in Model Theory (Search for Journal in Brave)

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)

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.

Recommendations

• Characterizations of monadic NIP
• scientific article; zbMATH DE number 4087623
• Generic expansions by a reduct
• Expansions of models of ω-stable theories

Cites work

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

Cited in

(4)

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

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)