Existential characterizations of monadic NIP
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912886091153408 |
|---|---|
| author | Braunfeld, Samuel Laskowski, Michael C. |
| author_facet | Braunfeld, Samuel Laskowski, Michael C. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_05120 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Existential characterizations of monadic NIP Braunfeld, Samuel Laskowski, Michael C. Logic Combinatorics 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. |
| title | Existential characterizations of monadic NIP |
| topic | Logic Combinatorics |
| url | https://arxiv.org/abs/2209.05120 |