To the top

Page Manager: Webmaster
Last update: 9/11/2012 3:13 PM

Tell a friend about this page
Print version

Ordinal analysis and the … - University of Gothenburg, Sweden Till startsida
Sitemap
To content Read more about how we use cookies on gu.se

Ordinal analysis and the infinite Ramsey theorem

Conference paper
Authors Bahareh Afshari
Michael Rathjen
Published in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN 03029743
Publication year 2012
Published at
Language en
Subject categories Mathematical logic

Abstract

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 RCA 0 due to results of Jockusch [5]. By subjecting the theory RCA 0 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 ACA 0. 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. © 2012 Springer-Verlag.

Page Manager: Webmaster|Last update: 9/11/2012
Share:

The University of Gothenburg uses cookies to provide you with the best possible user experience. By continuing on this website, you approve of our use of cookies.  What are cookies?