Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

Ordinal analysis and the … - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

Ordinal analysis and the infinite Ramsey theorem

Paper i proceeding
Författare Bahareh Afshari
Michael Rathjen
Publicerad i Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN 03029743
Publiceringsår 2012
Publicerad vid
Språk en
Ämneskategorier Matematisk logik

Sammanfattning

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.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?