On n-dependence
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2014
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913371945697280 |
|---|---|
| author | Chernikov, Artem Palacin, Daniel Takeuchi, Kota |
| author_facet | Chernikov, Artem Palacin, Daniel Takeuchi, Kota |
| contents | In this note we develop and clarify some of the basic combinatorial properties of the new notion of $n$-dependence (for $1\leq n < ω$) recently introduced by Shelah. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, $n$-dependence corresponds to the inability to encode a random $(n+1)$-partite $(n+1)$-hypergraph with a definable edge relation. Most importantly, we characterize $n$-dependence by counting $φ$-types over finite sets (generalizing Sauer-Shelah lemma and answering a question of Shelah) and in terms of the collapse of random ordered $(n+1)$-hypergraph indiscernibles down to order-indiscernibles (which implies that the failure of $n$-dependence is always witnessed by a formula in a single free variable). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1411_0120 |
| institution | arXiv |
| publishDate | 2014 |
| record_format | arxiv |
| spellingShingle | On n-dependence Chernikov, Artem Palacin, Daniel Takeuchi, Kota Logic Combinatorics In this note we develop and clarify some of the basic combinatorial properties of the new notion of $n$-dependence (for $1\leq n < ω$) recently introduced by Shelah. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, $n$-dependence corresponds to the inability to encode a random $(n+1)$-partite $(n+1)$-hypergraph with a definable edge relation. Most importantly, we characterize $n$-dependence by counting $φ$-types over finite sets (generalizing Sauer-Shelah lemma and answering a question of Shelah) and in terms of the collapse of random ordered $(n+1)$-hypergraph indiscernibles down to order-indiscernibles (which implies that the failure of $n$-dependence is always witnessed by a formula in a single free variable). |
| title | On n-dependence |
| topic | Logic Combinatorics |
| url | https://arxiv.org/abs/1411.0120 |