Projects per year

## 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 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.

Original language | English |
---|---|

Title of host publication | How the World Computes |

Subtitle of host publication | Turing Centenary Conference and 8th Conference on Computability in Europe, CiE 2012, Cambridge, UK, June 18-23, 2012. Proceedings |

Editors | S.Barry Cooper, Anuj Dawar, Benedikt Löwe |

Publisher | Springer-Verlag GmbH |

Pages | 1-10 |

Number of pages | 10 |

ISBN (Electronic) | 978-3-642-30870-3 |

ISBN (Print) | 978-3-642-30869-7 |

DOIs | |

Publication status | Published - 2012 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Berlin / Heidelberg |

Volume | 7318 |

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.## Projects

- 1 Finished