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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
