On the strength of Ramsey's theorem for pairs

Journal of Symbolic Logic 66 (1):1-55 (2001)
We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ n denote the Σ n induction and bounding schemes, respectively. Adapting the case n = 2 of the above result (where X is low 2 ) to models of arithmetic enables us to show that RCA 0 + IΣ 2 + RT 2 2 is conservative over RCA 0 + IΣ 2 for Π 1 1 statements and that $RCA_0 + I\Sigma_3 + RT^2_{ , is Π 1 1 -conservative over RCA 0 + IΣ 3 . It follows that RCA 0 + RT 2 2 does not imply BΣ 3 . In contrast, J. Hirst showed that $RCA_0 + RT^2_{ does imply BΣ 3 , and we include a proof of a slightly strengthened version of this result. It follows that $RT^2_{ is strictly stronger than RT 2 2 over RCA 0
Keywords Ramsey's Theorem   Conservation   Reverse Mathematics   Recursion Theory   Computability Theory
Categories (categorize this paper)
DOI 10.2307/2694910
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 23,316
External links
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
References found in this work BETA

Add more references

Citations of this work BETA
Jeremy Avigad (2004). Forcing in Proof Theory. Bulletin of Symbolic Logic 10 (3):305-333.
Wei Wang (2014). Cohesive Sets and Rainbows. Annals of Pure and Applied Logic 165 (2):389-408.

View all 13 citations / Add more citations

Similar books and articles

Monthly downloads

Added to index


Total downloads

200 ( #18,102 of 1,926,181 )

Recent downloads (6 months)

34 ( #14,063 of 1,926,181 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.