Characterizations of monadic NIP

Michael C. Laskowski; Samuel Braunfeld

arxiv: 2104.12989 · v3 · submitted 2021-04-27 · 🧮 math.LO · math.CO

Characterizations of monadic NIP

Samuel Braunfeld , Michael C. Laskowski This is my paper

Pith reviewed 2026-05-24 13:44 UTC · model grok-4.3

classification 🧮 math.LO math.CO

keywords monadic NIPindependence propertyfinite satisfiabilitymodel decompositionsindiscerniblesforbidden configurationhereditary classesquantifier elimination

0 comments

The pith

A complete first-order theory is monadically NIP exactly when every type over a model is finitely satisfiable in a small subset.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Monadic NIP means that expanding the theory by any collection of unary predicates never produces the independence property. The paper proves this property holds for a complete theory T if and only if every complete type over a model is realized inside some small subset of that model. Equivalent conditions are given in terms of model decompositions, the behavior of indiscernible sequences, and the absence of one specific forbidden configuration. The result is then used to show that hereditary classes of finite substructures drawn from models of non-monadically NIP theories that eliminate quantifiers must themselves have the independence property.

Core claim

A complete first-order theory T is monadically NIP if and only if every type over a model is finitely satisfiable in a small subset of the model. This condition is equivalent to the existence of certain decompositions of models, to specific restrictions on the behavior of indiscernibles, and to the absence of a forbidden configuration. The equivalences are applied to obtain non-structure results for hereditary classes of finite substructures of models of non-monadically NIP theories that eliminate quantifiers.

What carries the argument

The finite satisfiability condition on types, which is shown to be equivalent to the property that no expansion by arbitrary unary predicates introduces the independence property.

If this is right

Models of monadically NIP theories admit decompositions with controlled properties.
Indiscernible sequences in such models obey specific behavioral restrictions.
The theory avoids one particular forbidden configuration.
Hereditary classes of finite substructures from non-monadically NIP theories that eliminate quantifiers exhibit the independence property.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The finite-satisfiability test may simplify verification of monadic NIP for specific theories arising in practice.
Similar characterizations could be sought for expansions by predicates of arity greater than one.
The forbidden configuration may correspond to known dividing lines elsewhere in model theory.
The non-structure application limits the possible combinatorial complexity of finite structures embeddable in models without monadic NIP.

Load-bearing premise

The theory T is assumed to be complete and first-order, and the finite satisfiability condition is taken as the load-bearing equivalent definition.

What would settle it

A complete first-order theory in which every type is finitely satisfiable in a small subset, yet some expansion by a unary predicate still has the independence property, would falsify the central characterization.

read the original abstract

We give several characterizations of when a complete first-order theory $T$ is monadically NIP, i.e. when expansions of $T$ by arbitrary unary predicates do not have the independence property. The central characterization is a condition on finite satisfiability of types. Other characterizations include decompositions of models, the behavior of indiscernibles, and a forbidden configuration. As an application, we prove non-structure results for hereditary classes of finite substructures of non-monadically NIP models that eliminate quantifiers.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives clean equivalent conditions for monadic NIP centered on finite satisfiability of types, plus a direct non-structure application to hereditary classes.

read the letter

The main new material is a set of equivalent conditions for a complete theory T to be monadically NIP. The load-bearing one is a finite satisfiability condition on types; the others cover model decompositions, indiscernible behavior, and a forbidden configuration. From these they derive non-structure for hereditary classes of finite substructures of non-monadically NIP models that eliminate quantifiers. These conditions are not in the earlier NIP literature they cite, and the hereditary-class payoff is new as well. The equivalences are stated directly from the definition without obvious circularity or reduction to fitted parameters. The application follows in a straightforward way once the characterizations are in hand. The restriction to quantifier-eliminating models is a minor narrowing rather than a flaw; it fits the setting of finite structures they target. No load-bearing gaps appear in the logical chain from the abstract and stress-test description. This is for model theorists already working on NIP, monadic expansions, or combinatorial classification. A reader who needs tools to check or apply monadic NIP properties will get concrete value. It is worth sending to a serious referee.

Referee Report

0 major / 2 minor

Summary. The paper gives several characterizations of monadic NIP for a complete first-order theory T (i.e., T remains NIP after arbitrary unary predicate expansions). The central characterization is a finite-satisfiability condition on types; equivalent conditions are given via model decompositions, indiscernible behavior, and a forbidden configuration. An application derives non-structure results for hereditary classes of finite substructures of non-monadically NIP models that eliminate quantifiers.

Significance. If the equivalences hold, the work supplies a practical set of tools for recognizing monadic NIP theories and for deriving combinatorial consequences in hereditary classes. The direct derivations from the definition of monadic NIP, without reduction to fitted parameters, strengthen the result. The application to quantifier-eliminating structures links the characterizations to non-structure phenomena in a concrete way.

minor comments (2)

[Introduction] The precise statement of the forbidden configuration (mentioned in the abstract) would benefit from an explicit reference to its definition in the main text, e.g., in the section introducing the characterizations.
Notation for the finite-satisfiability condition on types could be introduced with a displayed definition before its use in the central equivalence.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive report and recommendation to accept the manuscript.

Circularity Check

0 steps flagged

No significant circularity; equivalences are logically derived

full rationale

The paper states multiple characterizations of monadic NIP for complete first-order theories T as logical equivalences, centered on a finite satisfiability condition for types together with model decompositions, indiscernible behavior, and a forbidden configuration. These are presented as derived from the definition (expansions by arbitrary unary predicates lack IP) without any reduction of the central claim to a fitted parameter, self-citation chain, or definitional loop. The hereditary-class application follows directly from the equivalences. No load-bearing step in the provided abstract or description exhibits a construction where an output equals an input by fiat; the derivation chain remains self-contained against external model-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper works inside standard first-order model theory; no free parameters are introduced, no new entities are postulated, and the axioms invoked are the usual background of complete theories and the definition of the independence property.

axioms (2)

domain assumption The theory T is assumed complete and first-order.
Stated in the abstract as the setting for the characterizations.
domain assumption Expansions are formed by adding arbitrary unary predicates.
Central to the definition of monadic NIP given in the abstract.

pith-pipeline@v0.9.0 · 5597 in / 1393 out tokens · 20095 ms · 2026-05-24T13:44:29.824774+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Trace definability I: preservation and characterizations
math.LO 2025-04 unverdicted novelty 6.0

Introduces trace definability for first-order structures and establishes preservation and characterization results for classification-theoretic properties under it.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · cited by 1 Pith paper

[1]

Hans Adler and Isolde Adler, Interpreting nowhere dense graph classes as a classical notion of model theory , European Journal of Combinatorics 36 (2014), 322–330

work page 2014
[2]

3, 229–303

John T Baldwin and Saharon Shelah, Second-order quantiﬁers and the complexity of theories, Notre Dame Journal of Formal Logic 26 (1985), no. 3, 229–303

work page 1985
[3]

4, 409–431

Achim Blumensath, Simple monadic theories and partition width , Mathematical Logic Quarterly 57 (2011), no. 4, 409–431

work page 2011
[4]

´Edouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and St´ ephan Thomass´ e, Twin-width IV: low complexity matrices , arXiv preprint arXiv:2102.03117 (2021)

work page arXiv 2021
[5]

Peter Cameron, Thomas Prellberg, and Dudley Stark, Asymptotics for incidence ma- trix classes , The Electronic Journal of Combinatorics 13 (2006), no. 1

work page 2006
[6]

3, 267–288

Alfred Dolich, John Goodrick, and David Lippel, Dp-minimality: basic facts and ex- amples, Notre Dame Journal of Formal Logic 52 (2011), no. 3, 267–288

work page 2011
[7]

15, 1637–1650

Frank Gurski, Linear layouts measuring neighbourhoods in graphs , Discrete Mathe- matics 306 (2006), no. 15, 1637–1650

work page 2006
[8]

2, 276–286

HD Macpherson, Inﬁnite permutation groups of rapid growth , Journal of the London Mathematical Society 2 (1987), no. 2, 276–286

work page 1987
[9]

15, 1599–1634

, A survey of homogeneous structures , Discrete Mathematics 311 (2011), no. 15, 1599–1634

work page 2011
[10]

2, 514–538

Michael Morley, Categoricity in power , Transactions of the American Mathematical Society 114 (1965), no. 2, 514–538

work page 1965
[11]

Saharon Shelah, Monadic logic: Hanf numbers , Around Classiﬁcation Theory of Mod- els, Springer Lecture Notes in Mathematics #1182, 1986, pp. 203–223. Sh:197, avail- able at shelah.logic.at/files/95757/197.pdf

work page 1986
[12]

, Classiﬁcation theory: and the number of non-isomorphic mod els, Elsevier, 1990

work page 1990
[13]

Pierre Simon, A guide to NIP theories , Cambridge University Press, 2015

work page 2015
[14]

, A note on stability and NIP in one variable , arXiv preprint arXiv:2103.15799 (2021)

work page arXiv 2021
[15]

Pierre Simon and Szymon Toru´ nczyk, Ordered graphs of bounded twin-width , arXiv preprint arXiv:2102.06881 (2021)

work page arXiv 2021

[1] [1]

Hans Adler and Isolde Adler, Interpreting nowhere dense graph classes as a classical notion of model theory , European Journal of Combinatorics 36 (2014), 322–330

work page 2014

[2] [2]

3, 229–303

John T Baldwin and Saharon Shelah, Second-order quantiﬁers and the complexity of theories, Notre Dame Journal of Formal Logic 26 (1985), no. 3, 229–303

work page 1985

[3] [3]

4, 409–431

Achim Blumensath, Simple monadic theories and partition width , Mathematical Logic Quarterly 57 (2011), no. 4, 409–431

work page 2011

[4] [4]

´Edouard Bonnet, Ugo Giocanti, Patrice Ossona de Mendez, and St´ ephan Thomass´ e, Twin-width IV: low complexity matrices , arXiv preprint arXiv:2102.03117 (2021)

work page arXiv 2021

[5] [5]

Peter Cameron, Thomas Prellberg, and Dudley Stark, Asymptotics for incidence ma- trix classes , The Electronic Journal of Combinatorics 13 (2006), no. 1

work page 2006

[6] [6]

3, 267–288

Alfred Dolich, John Goodrick, and David Lippel, Dp-minimality: basic facts and ex- amples, Notre Dame Journal of Formal Logic 52 (2011), no. 3, 267–288

work page 2011

[7] [7]

15, 1637–1650

Frank Gurski, Linear layouts measuring neighbourhoods in graphs , Discrete Mathe- matics 306 (2006), no. 15, 1637–1650

work page 2006

[8] [8]

2, 276–286

HD Macpherson, Inﬁnite permutation groups of rapid growth , Journal of the London Mathematical Society 2 (1987), no. 2, 276–286

work page 1987

[9] [9]

15, 1599–1634

, A survey of homogeneous structures , Discrete Mathematics 311 (2011), no. 15, 1599–1634

work page 2011

[10] [10]

2, 514–538

Michael Morley, Categoricity in power , Transactions of the American Mathematical Society 114 (1965), no. 2, 514–538

work page 1965

[11] [11]

Saharon Shelah, Monadic logic: Hanf numbers , Around Classiﬁcation Theory of Mod- els, Springer Lecture Notes in Mathematics #1182, 1986, pp. 203–223. Sh:197, avail- able at shelah.logic.at/files/95757/197.pdf

work page 1986

[12] [12]

, Classiﬁcation theory: and the number of non-isomorphic mod els, Elsevier, 1990

work page 1990

[13] [13]

Pierre Simon, A guide to NIP theories , Cambridge University Press, 2015

work page 2015

[14] [14]

, A note on stability and NIP in one variable , arXiv preprint arXiv:2103.15799 (2021)

work page arXiv 2021

[15] [15]

Pierre Simon and Szymon Toru´ nczyk, Ordered graphs of bounded twin-width , arXiv preprint arXiv:2102.06881 (2021)

work page arXiv 2021