×

On the strength of Ramsey’s theorem for pairs. (English) Zbl 0977.03033

J. Symb. Log. 66, No. 1, 1-55 (2001); corrigendum ibid. 74, No. 4, 1438-1439 (2009).
The authors use computability theory and proof theory to analyze various forms of Ramsey’s theorem, obtaining especially interesting results about Ramsey’s theorem for pairs. This work is closely related to earlier work of C. Jockusch [J. Symb. Log. 37, 268-280 (1972; Zbl 0262.02042)] and D. Seetapun and T. Slaman [Notre Dame J. Formal Logic 36, 570-582 (1995; Zbl 0843.03034)]. A forcing argument similar to one of C. Jockusch and F. Stephan [Math. Log. Q. 39, 515-530 (1993; Zbl 0799.03048)] proves that for any \(n \geq 2\) and any computable \(k\)-coloring of the \(n\)-element sets of natural numbers, there is an infinite homogeneous set \(X\), with \(X^{\prime \prime} \leq_{\text T} 0^{(n)}\). In particular, every computable \(k\)-coloring of pairs has a low\(_2\) homogeneous set. Additional forcing arguments show that RCA\(_0+\)I\(\Sigma_2 +\)RT\(_2^2\) is \(\Pi^1_1\)-conservative over RCA\(_0+\)I\(\Sigma_2\), leading to a proof that RT\(^2_{<\infty}\) is strictly stronger than RT\(^2_2\) over RCA\(_0\). After an analysis of the strength of statements concerning stable colorings and cohesive sets, the article concludes with a list of open questions and a comprehensive bibliography.

MSC:

03F35 Second- and higher-order arithmetic and fragments
03B30 Foundations of classical theories (including reverse mathematics)
03C62 Models of arithmetic and set theory
03D30 Other degrees and reducibilities in computability and recursion theory
03D80 Applications of computability and recursion theory
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Handbook of mathematical logic pp 1133– (1977)
[2] Generalized cohesiveness 64 pp 489– (1999) · Zbl 0935.03050
[3] Recursive function theory pp 117– (1962)
[4] Proceedings of London Mathematical Society (3) 30 pp 264– (1930)
[5] Degrees joining to 0’ 46 pp 714– (1981) · Zbl 0517.03014
[6] Intuitionism and proof theory (Proceedings of a Conference, Buffalo, N.Y., 1968) pp 459– (1970)
[7] DOI: 10.1007/BFb0090171 · doi:10.1007/BFb0090171
[8] Effective versions of Ramsey’s theorem: Avoiding the cone above 0’ 59 pp 1301– (1994) · Zbl 0815.03028
[9] Classical recursion theory (volume I) (1989)
[10] DOI: 10.1017/CBO9780511629167.011 · doi:10.1017/CBO9780511629167.011
[11] Journal of Soviet Mathematics 1 pp 71– (1973)
[12] Metamathematics of first-order arithmetic (1993) · Zbl 0781.03047
[13] Arithmetic, proof theory, and computational complexity (Prague, 1991) pp 185– (1993)
[14] Ramsey theory (1990)
[15] Systems of second order arithmetic with restricted induction, I, II (abstracts) 41 pp 557– (1976)
[16] Proceedings of the international congress of mathematicians (Vancouver, B.C., 1974), vol. 1 pp 235– (1975)
[17] Proof theory 81 (1987)
[18] Handbook of proof theory 137 (1998) · Zbl 0898.03001
[19] DOI: 10.2307/1969604 · Zbl 0074.01302 · doi:10.2307/1969604
[20] Logic Colloquium; 1969 Manchester pp 439– (1971)
[21] DOI: 10.1016/0168-0072(96)00003-6 · Zbl 0860.03040 · doi:10.1016/0168-0072(96)00003-6
[22] Recursively enumerable sets and degrees (1987)
[23] Subsystems of Second Order Arithmetic pp 445– (1999)
[24] Models of Peano arithmetic 15 (1991) · Zbl 0744.03037
[25] DOI: 10.1002/malq.19970430412 · doi:10.1002/malq.19970430412
[26] DOI: 10.1002/malq.19930390153 · Zbl 0799.03048 · doi:10.1002/malq.19930390153
[27] Transactions of the American Mathematical Society 173 pp 33– (1972) · Zbl 0247.00014
[28] DOI: 10.1007/BF02787575 · Zbl 0279.02024 · doi:10.1007/BF02787575
[29] Ramsey’s theorem and recursion theory 37 pp 268– (1972)
[30] DOI: 10.1090/S0002-9947-1968-0220595-7 · doi:10.1090/S0002-9947-1968-0220595-7
[31] DOI: 10.1305/ndjfl/1040136917 · Zbl 0843.03034 · doi:10.1305/ndjfl/1040136917
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.