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 \(\mathbf{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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Afshari, B., Rathjen, M.: Reverse Mathematics and well-ordering principles: a pilot study. Ann. Pure Appl. Log. 160(3), 231–237 (2009)
Carlucci, L., Zdanowski, K.: The strength of Ramsey Theorem for colouring relatively large sets, http://arxiv.org/abs/1204.1134
Farmaki, V., Negrepontis, S.: Schreier Sets in Ramsey Theory. Trans. Am. Math. Soc. 360(2), 849–880 (2008)
Girard, J.-Y.: Proof Theory and Logical Complexity. Biblipolis, Naples (1987)
Harrington, L., Paris, J.: A mathematical incompleteness in Peano Arithmetic. In: Barwise, J. (ed.) Handbook of Mathematical Logic, pp. 1133–1142. North-Holland (1977)
Hirst, J.: Reverse Mathematics and ordinal exponentiation. Ann. Pure App. Log. 66(1), 1–18 (1994)
Jockusch Jr., C.G.: Ramsey’s Theorem and Recursion Theory. J. Symb. Log. 37(2), 268–280 (1972)
Loebl, M., Nešetřil, J.: An unprovable Ramsey-type theorem. Proc. Am. Math. Soc. 116(3), 819–824 (1992)
Marcone, A., Montalbàn, A.: The Veblen function for computability theorists. J. Symb. Log. 76(2), 575–602 (2011)
McAloon, K.: Paris-Harrington incompleteness and transfinite progressions of theories. In: Nerode, A., Shore, R.A. (eds.) Recursion Theory. Proceedings of Symposia in Pure Mathematics, vol. 42, pp. 447–460. American Mathematical Society (1985)
Pudlàk, P., Rödl, V.: Partition theorems for systems of finite subsets of integers. Discret. Math. 39(1), 67–73 (1982)
Simpson, S.G.: Subsystems of Second Order Arithmetic. Springer (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Carlucci, L., Zdanowski, K. (2012). A Note on Ramsey Theorems and Turing Jumps. In: Cooper, S.B., Dawar, A., Löwe, B. (eds) How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30870-3_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-30870-3_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30869-7
Online ISBN: 978-3-642-30870-3
eBook Packages: Computer ScienceComputer Science (R0)