{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,3]],"date-time":"2026-06-03T14:36:35Z","timestamp":1780497395499,"version":"3.54.1"},"reference-count":34,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2014,3,12]],"date-time":"2014-03-12T00:00:00Z","timestamp":1394582400000},"content-version":"unspecified","delay-in-days":4759,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. symb. log."],"published-print":{"date-parts":[[2001,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We study the proof\u2013theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT<jats:sub arrange=\"stack\"><jats:italic>k<\/jats:italic><\/jats:sub><jats:sup arrange=\"stack\"><jats:italic>n<\/jats:italic><\/jats:sup>denote Ramsey's theorem for<jats:italic>k<\/jats:italic>\u2013colorings of<jats:italic>n<\/jats:italic>\u2013element sets, and let RT<jats:sub arrange=\"stack\">&lt;\u221e<\/jats:sub><jats:sup arrange=\"stack\"><jats:italic>n<\/jats:italic><\/jats:sup>denote (\u2200<jats:italic>k<\/jats:italic>)RT<jats:sub arrange=\"stack\"><jats:italic>k<\/jats:italic><\/jats:sub><jats:sup arrange=\"stack\"><jats:italic>n<\/jats:italic><\/jats:sup>. Our main result on computability is: For any<jats:italic>n<\/jats:italic>\u2265 2 and any computable (recursive)<jats:italic>k<\/jats:italic>\u2013coloring of the<jats:italic>n<\/jats:italic>\u2013element sets of natural numbers, there is an infinite homogeneous set<jats:italic>X<\/jats:italic>with<jats:italic>X<\/jats:italic>\u2033 \u2264<jats:sub><jats:italic>T<\/jats:italic><\/jats:sub>0<jats:sup>(<jats:italic>n<\/jats:italic>)<\/jats:sup>. Let<jats:italic>I<\/jats:italic>\u03a3<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>and<jats:italic>B<\/jats:italic>\u03a3<jats:sub><jats:italic>n<\/jats:italic><\/jats:sub>denote the \u03a3<jats:sub>n<\/jats:sub>induction and bounding schemes, respectively. Adapting the case<jats:italic>n<\/jats:italic>= 2 of the above result (where<jats:italic>X<\/jats:italic>is low<jats:sub>2<\/jats:sub>) to models of arithmetic enables us to show that RCA<jats:sub>0<\/jats:sub>+<jats:italic>I<\/jats:italic>\u03a3<jats:sub>2<\/jats:sub>+ RT<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">2<\/jats:sup>is conservative over RCA<jats:sub>0<\/jats:sub>+<jats:italic>I<\/jats:italic>\u03a3<jats:sub>2<\/jats:sub>for \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup>statements and that RCA<jats:sub>0<\/jats:sub>+<jats:italic>I<\/jats:italic>\u03a3<jats:sub>3<\/jats:sub>+ RT<jats:sub arrange=\"stack\">&lt;\u221e<\/jats:sub><jats:sup arrange=\"stack\">2<\/jats:sup>is \u03a0<jats:sub arrange=\"stack\">1<\/jats:sub><jats:sup arrange=\"stack\">1<\/jats:sup>-conservative over RCA<jats:sub>0<\/jats:sub>+<jats:italic>I<\/jats:italic>\u03a3<jats:sub>3<\/jats:sub>. It follows that RCA<jats:sub>0<\/jats:sub>+ RT<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">2<\/jats:sup>does not imply<jats:italic>B<\/jats:italic>\u03a3<jats:sub>3<\/jats:sub>. In contrast, J. Hirst showed that RCA<jats:sub>0<\/jats:sub>+ RT<jats:sub arrange=\"stack\">&lt;\u221e<\/jats:sub><jats:sup arrange=\"stack\">2<\/jats:sup>does imply<jats:italic>B<\/jats:italic>\u03a3<jats:sub>3<\/jats:sub>, and we include a proof of a slightly strengthened version of this result. It follows that RT<jats:sub arrange=\"stack\">&lt;\u221e<\/jats:sub><jats:sup arrange=\"stack\">2<\/jats:sup>is strictly stronger than RT<jats:sub arrange=\"stack\">2<\/jats:sub><jats:sup arrange=\"stack\">2<\/jats:sup>over<jats:italic>RCA<\/jats:italic><jats:sub>0<\/jats:sub>.<\/jats:p>","DOI":"10.2307\/2694910","type":"journal-article","created":{"date-parts":[[2006,5,6]],"date-time":"2006-05-06T18:03:53Z","timestamp":1146938633000},"page":"1-55","source":"Crossref","is-referenced-by-count":111,"title":["On the strength of Ramsey's theorem for pairs"],"prefix":"10.1017","volume":"66","author":[{"given":"Peter A.","family":"Cholak","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Carl G.","family":"Jockusch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Theodore A.","family":"Slaman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2014,3,12]]},"reference":[{"key":"S0022481200011208_ref033","doi-asserted-by":"publisher","DOI":"10.2307\/1969604"},{"key":"S0022481200011208_ref020","doi-asserted-by":"publisher","DOI":"10.1007\/BF01117472"},{"key":"S0022481200011208_ref030","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59971-2"},{"key":"S0022481200011208_ref034","volume-title":"Proof theory","volume":"81","author":"Takeuti","year":"1987"},{"key":"S0022481200011208_ref011","first-page":"1301","volume":"59","author":"Hummel","year":"1994","journal-title":"Effective versions of Ramsey's theorem: Avoiding the cone above 0\u2032"},{"key":"S0022481200011208_ref017","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19930390153"},{"key":"S0022481200011208_ref025","first-page":"714","volume":"46","author":"Posner","year":"1981","journal-title":"Degrees joining to 0\u2032"},{"key":"S0022481200011208_ref015","doi-asserted-by":"publisher","DOI":"10.1007\/BF02787575"},{"key":"S0022481200011208_ref007","first-page":"185","volume-title":"Arithmetic, proof theory, and computational complexity (Prague, 1991)","author":"H\u00e1jek","year":"1993"},{"key":"S0022481200011208_ref014","first-page":"268","volume":"37","author":"Jockusch","year":"1972","journal-title":"Ramsey's theorem and recursion theory"},{"key":"S0022481200011208_ref002","unstructured":"Downey R. , Hirschfeldt Denis R. , Lempp S. , and Solomon R. , [to appear], A \u03942 0 set withno infinite low set in either it or its complement, this Journal."},{"key":"S0022481200011208_ref032","first-page":"439","volume-title":"Logic Colloquium; 1969 Manchester","author":"Specker","year":"1971"},{"key":"S0022481200011208_ref001","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(96)00003-6"},{"key":"S0022481200011208_ref018","doi-asserted-by":"publisher","DOI":"10.1002\/malq.19970430412"},{"key":"S0022481200011208_ref027","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/005\/0141595"},{"key":"S0022481200011208_ref005","first-page":"557","volume":"41","author":"Friedman","year":"1976","journal-title":"Systems of second order arithmetic with restricted induction, I, II (abstracts)"},{"key":"S0022481200011208_ref008","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22156-3"},{"key":"S0022481200011208_ref012","first-page":"489","volume":"64","author":"Hummel","year":"1999","journal-title":"Generalized cohesiveness"},{"key":"S0022481200011208_ref004","first-page":"235","volume-title":"Proceedings of the international congress of mathematicians (Vancouver, B.C., 1974), vol. 1","author":"Friedman","year":"1975"},{"key":"S0022481200011208_ref021","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511629167.011"},{"key":"S0022481200011208_ref003","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(98)80018-9"},{"key":"S0022481200011208_ref016","first-page":"33","article-title":"\u03a010 classes and degrees of theories","volume":"173","author":"Jockusch","year":"1972","journal-title":"Transactions of the American Mathematical Society"},{"key":"S0022481200011208_ref019","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198532132.001.0001","volume-title":"Models of Peano arithmetic","volume":"15","author":"Kaye","year":"1991"},{"key":"S0022481200011208_ref026","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-30.1.264"},{"key":"S0022481200011208_ref028","doi-asserted-by":"crossref","first-page":"570","DOI":"10.1305\/ndjfl\/1040136917","article-title":"On the strength of Ramsey's theorem","volume":"36","author":"Seetapun","year":"1995","journal-title":"Notre Dame Journal of Formal Logic"},{"key":"S0022481200011208_ref029","first-page":"1133","volume-title":"Handbook of mathematical logic","author":"Simpson","year":"1977"},{"key":"S0022481200011208_ref010","unstructured":"Hirst Jeffry L. , [1987], Combinatorics in Subsystems of Second Order Arithmetic, Ph.D. thesis , The Pennsylvania State University."},{"key":"S0022481200011208_ref023","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0090171"},{"key":"S0022481200011208_ref013","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1968-0220595-7"},{"key":"S0022481200011208_ref024","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)70771-7"},{"key":"S0022481200011208_ref009","unstructured":"Herrmann E. , [to appear], Infinite chains and antichains in recursive partial orderings, this Journal."},{"key":"S0022481200011208_ref022","volume-title":"Classical recursion theory (volume I)","author":"Odifreddi","year":"1989"},{"key":"S0022481200011208_ref031","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-02460-7"},{"key":"S0022481200011208_ref006","volume-title":"Ramsey theory","author":"Graham","year":"1990"}],"container-title":["Journal of Symbolic Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0022481200011208","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,4]],"date-time":"2024-02-04T07:20:19Z","timestamp":1707031219000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0022481200011208\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,3]]},"references-count":34,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2001,3]]}},"alternative-id":["S0022481200011208"],"URL":"https:\/\/doi.org\/10.2307\/2694910","relation":{},"ISSN":["0022-4812","1943-5886"],"issn-type":[{"value":"0022-4812","type":"print"},{"value":"1943-5886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2001,3]]}}}