Existential characterizations of monadic NIP

2022/09/12 by Braunfeld, Samuel, Laskowski, Michael C. · 3 citations
#Combinatorics (math.CO) #FOS: Mathematics #Logic (math.LO)

paper · doi:10.48550/arxiv.2209.05120

Abstract

We show that if a universal theory is not monadically NIP, then this is witnessed by a canonical configuration defined by an existential formula. As a consequence, we show that a hereditary class of relational structures is NIP (resp. stable) if and only if it is monadically NIP (resp. monadically stable). As another consequence, we show that if such a class is not monadically NIP, then it has superexponential growth rate.

Cited by

• Labelled growth rates of ω-categorical structures and applications in choiceless set theory
• Modeling FO-limits for monadically stable sequences
• Flipping and Forking

Related

• Characterizations of monadic NIP
• Indiscernibles in monadically NIP theories
• Monadic NIP in monotone classes of relational structures
• Externally definable sets and dependent pairs II
• Classification theory for theories with NIP - a modest beginning