Partition theorems and computability theory

Bulletin of Symbolic Logic 11 (3):411-427 (2005)
  Copy   BIBTEX


The connections between mathematical logic and combinatorics have a rich history. This paper focuses on one aspect of this relationship: understanding the strength, measured using the tools of computability theory and reverse mathematics, of various partition theorems. To set the stage, recall two of the most fundamental combinatorial principles, König's Lemma and Ramsey's Theorem. We denote the set of natural numbers by ω and the set of finite sequences of natural numbers by ω<ω. We also identify each n ∈ ω with its set of predecessors, so n = {0, 1, 2, …, n − 1}.



    Upload a copy of this work     Papers currently archived: 92,261

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

50 (#319,955)

6 months
11 (#244,932)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

The polarized Ramsey’s theorem.Damir D. Dzhafarov & Jeffry L. Hirst - 2009 - Archive for Mathematical Logic 48 (2):141-157.
Automorphisms of models of arithmetic: a unified view.Ali Enayat - 2007 - Annals of Pure and Applied Logic 145 (1):16-36.
Degrees bounding principles and universal instances in reverse mathematics.Ludovic Patey - 2015 - Annals of Pure and Applied Logic 166 (11):1165-1185.
Dominating the Erdős–Moser theorem in reverse mathematics.Ludovic Patey - 2017 - Annals of Pure and Applied Logic 168 (6):1172-1209.

View all 7 citations / Add more citations

References found in this work

The Higher Infinite.Akihiro Kanamori - 2000 - Studia Logica 65 (3):443-446.
A mathematical incompleteness in Peano arithmetic.Jeff Paris & Leo Harrington - 1977 - In Jon Barwise (ed.), Handbook of mathematical logic. New York: North-Holland. pp. 90--1133.
On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
Ramsey's theorem and recursion theory.Carl G. Jockusch - 1972 - Journal of Symbolic Logic 37 (2):268-280.

View all 12 references / Add more references