The strength of Ramsey Theorem for coloring relatively large sets
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2012
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911750650068992 |
|---|---|
| author | Carlucci, Lorenzo Zdanowski, Konrad |
| author_facet | Carlucci, Lorenzo Zdanowski, Konrad |
| contents | We characterize the computational content and the proof-theoretic strength of a Ramsey-type theorem for bi-colorings of so-called {\em exactly large} sets. An {\it exactly large} set is a set $X\subset\Nat$ such that $\card(X)=\min(X)+1$. The theorem we analyze is as follows. For every infinite subset $M$ of $\Nat$, for every coloring $C$ of the exactly large subsets of $M$ in two colors, there exists and infinite subset $L$ of $M$ such that $C$ is constant on all exactly large subsets of $L$. This theorem is essentially due to Pudlàk and Rödl and independently to Farmaki. We prove that --- over Computable Mathematics --- this theorem is equivalent to closure under the $ω$ Turing jump (i.e., under arithmetical truth). Natural combinatorial theorems at this level of complexity are rare. Our results give a complete characterization of the theorem from the point of view of Computable Mathematics and of the Proof Theory of Arithmetic. This nicely extends the current knowledge about the strength of Ramsey Theorem. We also show that analogous results hold for a related principle based on the Regressive Ramsey Theorem. In addition we give a further characterization in terms of truth predicates over Peano Arithmetic. We conjecture that analogous results hold for larger ordinals. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1204_1134 |
| institution | arXiv |
| publishDate | 2012 |
| record_format | arxiv |
| spellingShingle | The strength of Ramsey Theorem for coloring relatively large sets Carlucci, Lorenzo Zdanowski, Konrad Logic Logic in Computer Science Combinatorics 03D25, 05D10 We characterize the computational content and the proof-theoretic strength of a Ramsey-type theorem for bi-colorings of so-called {\em exactly large} sets. An {\it exactly large} set is a set $X\subset\Nat$ such that $\card(X)=\min(X)+1$. The theorem we analyze is as follows. For every infinite subset $M$ of $\Nat$, for every coloring $C$ of the exactly large subsets of $M$ in two colors, there exists and infinite subset $L$ of $M$ such that $C$ is constant on all exactly large subsets of $L$. This theorem is essentially due to Pudlàk and Rödl and independently to Farmaki. We prove that --- over Computable Mathematics --- this theorem is equivalent to closure under the $ω$ Turing jump (i.e., under arithmetical truth). Natural combinatorial theorems at this level of complexity are rare. Our results give a complete characterization of the theorem from the point of view of Computable Mathematics and of the Proof Theory of Arithmetic. This nicely extends the current knowledge about the strength of Ramsey Theorem. We also show that analogous results hold for a related principle based on the Regressive Ramsey Theorem. In addition we give a further characterization in terms of truth predicates over Peano Arithmetic. We conjecture that analogous results hold for larger ordinals. |
| title | The strength of Ramsey Theorem for coloring relatively large sets |
| topic | Logic Logic in Computer Science Combinatorics 03D25, 05D10 |
| url | https://arxiv.org/abs/1204.1134 |