Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-16T23:15:26.901Z Has data issue: false hasContentIssue false
  • English
  • Français

Effective versions of Ramsey's Theorem: Avoiding the cone above 0′

Published online by Cambridge University Press:  12 March 2014

Tamara Lakins Hummel
Tamara Lakins Hummel*
Affiliation:
Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, Illinois 61801
*
Department of Mathematics, Dartmouth College, Hanover, New Hampshire 03755, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Ramsey's Theorem states that if P is a partition of [ω]k into finitely many partition classes, then there exists an infinite set of natural numbers which is homogeneous for P. We consider the degrees of unsolvability and arithmetical definability properties of infinite homogeneous sets for recursive partitions. We give Jockusch's proof of Seetapun's recent theorem that for all recursive partitions of [ω]2 into finitely many pieces, there exists an infinite homogeneous set A such that ∅′ ≰TA. Two technical extensions of this result are given, establishing arithmetical bounds for such a set A. Applications to reverse mathematics and introreducible sets are discussed.

Keywords

Ramsey's Theoremreverse mathematicsintroreducible sets
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 59 , Issue 4 , December 1994 , pp. 1301 - 1325
Copyright
Copyright © Association for Symbolic Logic 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Friedman, H., Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, 1974), Vol. 1, Canadian Mathematical Congress, Montréal, 1975, pp. 235–242.Google Scholar
[2]Friedman, H., Systems of second order arithmetic with restricted induction, I, II, this Journal, vol. 41 (1976), pp. 557–559, (abstracts).Google Scholar
[3]Hirst, J., Combinatorics in subsystems of second order arithmetic, Ph.D. thesis, The Pennsylvania State University, University Park, Pennsylvania, 1987.Google Scholar
[4]Hummel, T., Effective versions of Ramsey's Theorem, Ph.D. thesis, University of Illinois at Urbana-Champaign, Urbana, Illinois, 1993.Google Scholar
[5]Jockusch, C. G. Jr., Uniformly introreducible sets, this Journal, vol. 33 (1968), pp. 521–536.Google Scholar
[6]Jockusch, C. G. Jr., Ramsey's theorem and recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[7]Jockusch, C. G. Jr., Private communication (1992).Google Scholar
[8]Jockusch, C. G. Jr., and Shore, R. A., REA operators, R.E. degrees and minimal coverings, Recursion theory, Proceedings of Symposia in Pure Mathematics, vol. 42, American Mathematical Society, Providence, Rhode Island, pp. 3–11.CrossRefGoogle Scholar
[9]Jockusch, C. G. Jr., and Soare, R. I., classes and degrees of theories, Transactions of the American Mathematical Society, vol. 173 (1972), pp. 33–56.Google Scholar
[10]Jockusch, C. G. Jr., and Stephan, F., A cohesive set which is not high, Mathematical Logic Quarterly, vol. 39 (1993), pp. 515–530.CrossRefGoogle Scholar
[11]Kirby, L. A. S. and Paris, J. B., Initial segments of models of Peano's axioms, Set Theory and Hierarchy Theory V (Bierutowice, 1976), Lecture Notes in Mathematics, vol. 619, Springer-Verlag, Berlin, 1977, pp. 211–226.CrossRefGoogle Scholar
[12]Ramsey, F. P., On a problem informal logic, Proceedings of the London Mathematical Society, ser. 2, vol. 30 (1930), pp. 264–286.CrossRefGoogle Scholar
[13]Seetapun, D. and Slaman, T., On Ramsey's Theorem for Pairs, unpublished.Google Scholar
[14]Simpson, S. G., Subsystems of second order arithmetic, Springer-Verlag, Berlin (to appear).Google Scholar
[15]Soare, R. I., Recursively enumerable sets and degrees, Springer-Verlag, Berlin, 1987.CrossRefGoogle Scholar
[16]Specker, E., Ramsey's theorem does not hold in recursive set theory, Logic Colloquium '69, North-Holland, Amsterdam, 1971, pp. 439–442.CrossRefGoogle Scholar