Ordinal Analysis and the Infinite Ramsey Theorem

Bahareh Afshari, Michael Rathjen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

The infinite Ramsey theorem is known to be equivalent to the statement ‘for every set X and natural number n, the n-th Turing jump of X exists’, over RCA0 due to results of Jockusch [5]. By subjecting the theory RCA0 augmented by the latter statement to an ordinal analysis, we give a direct proof of the fact that the infinite Ramsey theorem has proof-theoretic strength εω. The upper bound is obtained by means of cut elimination and the lower bound by extending the standard well-ordering proofs for ACA0. There is a proof of this result due to McAloon [6], using model-theoretic and combinatorial techniques. According to [6], another proof appeared in an unpublished paper by Jäger.

Original languageEnglish
Title of host publicationHow the World Computes
Subtitle of host publicationTuring Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings
EditorsS.Barry Cooper, Anuj Dawar, Benedikt Löwe
PublisherSpringer-Verlag GmbH
Pages1-10
Number of pages10
ISBN (Electronic)978-3-642-30870-3
ISBN (Print)978-3-642-30869-7
DOIs
Publication statusPublished - 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin / Heidelberg
Volume7318
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Fingerprint

Dive into the research topics of 'Ordinal Analysis and the Infinite Ramsey Theorem'. Together they form a unique fingerprint.

Cite this