We characterize the effective content and the proof-theoretic strength of a Ramsey-type theorem for bi-colorings of so-called exactly large sets. The theorem we analyze is as follows. For every infinite subset M of N, 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 RCA0 —this theorem is equivalent to closure under the ωth Turing jump (i.e., under arithmetical truth). Natural combinatorial theorems at this level of complexity are rare. In terms of Reverse Mathematics we give the first Ramsey-theoretic characterization of ACA0+. Our results give a complete characterization of the theorem from the point of view of Computability Theory and of the Proof Theory of Arithmetic. This nicely extends the current knowledge about the strength of Ramsey’s Theorem. We also show that analogous results hold for a related principle based on the Regressive Ramsey’s Theorem. We conjecture that analogous results hold for larger ordinals.

THE STRENGTH OF RAMSEY’S THEOREM FOR COLORING RELATIVELY LARGE SETS / Carlucci, Lorenzo; Konrad, Zdanowski. - In: THE JOURNAL OF SYMBOLIC LOGIC. - ISSN 0022-4812. - 79:01(2014), pp. 89-102. [10.1017/jsl.2013.27]

THE STRENGTH OF RAMSEY’S THEOREM FOR COLORING RELATIVELY LARGE SETS

CARLUCCI, LORENZO;
2014

Abstract

We characterize the effective content and the proof-theoretic strength of a Ramsey-type theorem for bi-colorings of so-called exactly large sets. The theorem we analyze is as follows. For every infinite subset M of N, 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 RCA0 —this theorem is equivalent to closure under the ωth Turing jump (i.e., under arithmetical truth). Natural combinatorial theorems at this level of complexity are rare. In terms of Reverse Mathematics we give the first Ramsey-theoretic characterization of ACA0+. Our results give a complete characterization of the theorem from the point of view of Computability Theory and of the Proof Theory of Arithmetic. This nicely extends the current knowledge about the strength of Ramsey’s Theorem. We also show that analogous results hold for a related principle based on the Regressive Ramsey’s Theorem. We conjecture that analogous results hold for larger ordinals.
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/563952
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact