×

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

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
PDF BibTeX XML Cite
Full Text: DOI

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
[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
[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
[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
[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
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.