On the strength of Ramsey’s theorem. (English) Zbl 0843.03034

Seetapun, David; Slaman, Theodore A.

Notre Dame J. Formal Logic 36, No. 4, 570-582 (1995).

Summary: We show that, for every partition \(F\) of the pairs of natural numbers and for every set \(C\), if \(C\) is not recursive in \(F\) then there is an infinite set, \(H\), such that \(H\) is homogeneous for \(F\) and \(C\) is not recursive in \(H\). We conclude that the formal statement of Ramsey’s Theorem for Pairs is not strong enough to prove \(ACA_0\), the comprehension scheme for arithmetical formulas, within the base theory \(RCA_0\), the comprehension scheme for recursive formulas. We also show that Ramsey’s Theorem for Pairs is strong enough to prove some sentences in first order arithmetic which are not provable within \(RCA_0\). In particular, Ramsey’s Theorem for Pairs is not conservative over \(RCA_0\) for \(\Pi^0_4\)-sentences.

MSC:

03F30

First-order arithmetic and fragments

Keywords:

Ramsey’s theorem for pairs; comprehension scheme; first order arithmetic

References:

[1]	Brown, D. K., and S. G. Simpson, “The Baire category theorem in weak subsystems of second-order arithmetic,” The Journal of Symbolic Logic , vol. 58 (1993), pp. 557–578. JSTOR: · Zbl 0794.03085 · doi:10.2307/2275219
[2]	Friedberg, R. M., “A criterion for completeness of degrees of unsolvability,” The Journal of Symbolic Logic , vol. 22 (1957), pp. 159–160. JSTOR: · Zbl 0078.00602 · doi:10.2307/2964177
[3]	Friedman, H., “Some systems of second order arithmetic and their use,” pp. 235–242 in Proceedings of the International Congress of Mathematicians, Canada, 1974 vol. 1, Canadian Mathematical Congress, 1975. · Zbl 0344.02022
[4]	Kaye, R., “The theory of \(\kappa\)-like models of arithmetic,” The University of Birmingham, preprint 94/35, 1994b. · Zbl 0848.03019 · doi:10.1305/ndjfl/1040136915
[5]	Martin, D. A., “ Classes of recursively enumerable sets and degrees of unsolvability,” Zeitschrift für Mathematische Logik und Grundlangen der Mathematik , vol. 12 (1966), pp. 295–310. · Zbl 0181.30504 · doi:10.1002/malq.19660120125
[6]	Mytilinaios, M. E., and T. A. Slaman, “On a question of Brown and Simpson,” preprint, 1994. · Zbl 0835.03026
[7]	Scott, D., “Algebras of sets binumerable in complete extensions of arithmetic,” Recursive Function Theory , # 5, pp. 117–121 in Proceedings of Symposia in Pure Mathematics , American Mathematical Society, Providence, 1962. · Zbl 0199.02601