We give a new treatment of the relations between Ramsey's Theorem, ACA 0 and ACA′ 0. First we combine a result by Girard with a colouring used by Loebl and Nešetril for the analysis of the Paris-Harrington principle to obtain a short combinatorial proof of ACA 0 from Ramsey Theorem for triples. We then extend this approach to ACA′ 0 using a characterization of this system in terms of preservation of well-orderings due to Marcone and Montalbán. We finally discuss how to apply this method to ACA 0 + using an extension of Ramsey's Theorem for colouring relatively large sets due to Pudlàk and Rödl and independently to Farmaki. © 2012 Springer-Verlag.

A note on Ramsey theorems and Turing jumps / Carlucci, Lorenzo; Konrad, Zdanowski. - STAMPA. - 7318 LNCS:(2012), pp. 89-95. (Intervento presentato al convegno Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 tenutosi a Cambridge nel 18 June 2012 through 23 June 2012) [10.1007/978-3-642-30870-3_10].

A note on Ramsey theorems and Turing jumps

CARLUCCI, LORENZO;
2012

Abstract

We give a new treatment of the relations between Ramsey's Theorem, ACA 0 and ACA′ 0. First we combine a result by Girard with a colouring used by Loebl and Nešetril for the analysis of the Paris-Harrington principle to obtain a short combinatorial proof of ACA 0 from Ramsey Theorem for triples. We then extend this approach to ACA′ 0 using a characterization of this system in terms of preservation of well-orderings due to Marcone and Montalbán. We finally discuss how to apply this method to ACA 0 + using an extension of Ramsey's Theorem for colouring relatively large sets due to Pudlàk and Rödl and independently to Farmaki. © 2012 Springer-Verlag.
2012
Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012
Ramsey Theorem, Reverse Mathematics, Well-ordering
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
A note on Ramsey theorems and Turing jumps / Carlucci, Lorenzo; Konrad, Zdanowski. - STAMPA. - 7318 LNCS:(2012), pp. 89-95. (Intervento presentato al convegno Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012 tenutosi a Cambridge nel 18 June 2012 through 23 June 2012) [10.1007/978-3-642-30870-3_10].
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/477751
 Attenzione

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

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