Hostname: page-component-cd9895bd7-q99xh Total loading time: 0 Render date: 2024-12-16T21:41:34.280Z Has data issue: false hasContentIssue false
  • English
  • Français

Ramsey's theorem and recursion theory

Published online by Cambridge University Press:  12 March 2014

Carl G. Jockusch Jr.
Carl G. Jockusch Jr.*
Affiliation:
University Of Illinois at Urbana-Champaign, Urbana, Illinois 61801
Get access Rights & Permissions [Opens in a new window]

Extract

Let N be the set of natural numbers. If A ⊆ N, let [A]n denote the class of all n-element subsets of A. If P is a partition of [N]n into finitely many classes C1, …, Cp, let H(P) denote the class of those infinite sets A ⊆ N such that [A]n ⊆ Ci for some i. Ramsey's theorem [8, Theorem A] asserts that H(P) is nonempty for any such partition P. Our purpose here is to study what can be said about H(P) when P is recursive, i.e. each Ci, is recursive under a suitable coding of [N]n. We show that if P is such a recursive partition of [N]n, then H(P) contains a set which is Πn0 in the arithmetical hierarchy. In the other direction we prove that for each n ≥ 2 there is a recursive partition P of [N]n into two classes such that H(P) contains no Σn0 set. These results answer a question raised by Specker [12].

A basic partition is a partition of [N]2 into two classes. In §§2, 3, and 4 we concentrate on basic partitions and in so doing prepare the way for the general results mentioned above. These are proved in §5. Our “positive” results are obtained by effectivizing proofs of Ramsey's theorem which differ from the original proof in [8]. We present these proofs (of which one is a generalization of the other) in §§4 and 5 in order to clarify the motivation of the effective versions.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 37 , Issue 2 , June 1972 , pp. 268 - 280
Copyright
Copyright © Association for Symbolic Logic 1972

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]Friedberg, R. M., Two recursively enumerable sets of incomparable degree of unsolvability (solution of Post's problem 1944), Proceedings of the National Academy of Sciences of the United States of America, vol. 43 (1957), pp. 236–238.CrossRefGoogle ScholarPubMed
[2]Jockusch, C. G., Semirecursive sets and positive reducibility, Transactions of the American Mathematical Society, vol. 131 (1968), pp. 420–436.CrossRefGoogle Scholar
[3]Jockusch, C. G., The degrees of bi-immune sets, Zeitschrift für mathematische Logik and Grundlagen der Mathematik, vol. 15 (1969), pp. 135–140.CrossRefGoogle Scholar
[4]Jockusch, C. G., Ramsey's theorem and recursion theory, Notices of the American Mathematical Society, vol. 17 (1970), pp. 672–673.Google Scholar
[5]Jockusch, C. G. and McLaughlin, T. G., Countable retracing functions and Π20 predicates, Pacific Journal of Mathematics, vol. 30 (1969), pp. 67–93.CrossRefGoogle Scholar
[6]Jockusch, C. G. and Soare, R. I., Π20 classes and degrees of theories (to appear).Google Scholar
[7]McLaughlin, T. G., Splitting and decomposition by regressive sets. II, Canadian Journal of Mathematics, vol. 19 (1967), pp. 291–311.CrossRefGoogle Scholar
[8]Ramsey, F. P., On a problem in formal logic, Proceedings of the London Mathematical Society, vol. 30 (1930), pp. 264–286.CrossRefGoogle Scholar
[9]Rogers, H., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[10]Sacks, G. E., A minimal degree less than O', Bulletin of the American Mathematical Society, vol. 67 (1961), pp. 416–419.CrossRefGoogle Scholar
[11]Shoenfield, J. R., On degrees of unsolvability, Annals of Mathematics, series 2, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[12]Specker, E., Ramsey's theorem does not hold in recursive set theory, Studies in logic and the foundations of mathematics, North-Holland, Amsterdam, 1971.Google Scholar
[13]Yates, C. E. M., Arithmetical sets and retracing functions, Zeitschrift für mathematische Logik and Grundlagen der Mathematik, vol. 13 (1967), pp. 193–204.CrossRefGoogle Scholar
[14]Yates, C. E. M., A note on arithmetical sets of indiscernibles, Studies in logic and the foundations of mathematics, North-Holland, Amsterdam, 1971, pp. 443–451.Google Scholar