Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-29T01:58:29.205Z Has data issue: false hasContentIssue false
  • English
  • Français

A recursion theoretic analysis of the clopen Ramsey theorem

Published online by Cambridge University Press:  12 March 2014

Peter Clote
Peter Clote*
Affiliation:
Université Paris VII Paris, France
Get access Rights & Permissions [Opens in a new window]

Abstract

Solovay has shown that if F: [ω]ω → 2 is a clopen partition with recursive code, then there is an infinite homogeneous hyperarithmetic set for the partition (a basis result). Simpson has shown that for every 0α, where α is a recursive ordinal, there is a clopen partition F: [ω]ω → 2 such that every infinite homogeneous set is Turing above 0α (an anti-basis result). Here we refine these results, by associating the “order type” of a clopen set with the Turing complexity of the infinite homogeneous sets. We also consider the Nash-Williams barrier theorem and its relation to the clopen Ramsey theorem.

Keywords

Ramsey's theoremlimit lemmahyperarithmeticbasis and anti-basis resultsGalvin-Prikry theoremNash-Williams barrier theorem.
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 49 , Issue 2 , June 1984 , pp. 376 - 400
Copyright
Copyright © Association for Symbolic Logic 1984

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]Assous, Marc, Caractérisation du type d'ordre des barrières de Nash-Williams, Publications du Département de Mathématiques, Faculté des Sciences de Lyon, vol. 11 (1974), no. 4, pp. 89–106.Google Scholar
[2]Chen, Keh-Hsun, Recursive well-founded orderirigs, Annals of Mathematical Logic, vol. 13 (1978), pp. 117–147.CrossRefGoogle Scholar
[3]Clote, Peter, Recursion theoretic analysis of the barrier theorem, this Journal, vol. 45 (1980), pp. 387–388.Google Scholar
[4]Clote, Peter, A recursion theoretic analysis of certain generalizations of Ramsey's theorem and of the Gale-Stewart theorem, Ph.D. Thesis, Duke University, Durham, North Carolina, 1979.Google Scholar
[5]Clote, Peter, Anti-basis theorems and their relation to independence results in Peano arithmetic, Model theory and arithmetic (Proceedings of the CNRS conference, Paris, 1979–1980), Lecture Notes in Mathematics, vol. 890, Springer-Verlag, Berlin, 1981, pp. 115–133.Google Scholar
[6]Clote, Peter, A generalization of the limit lemma and clopen games, submitted to this Journal.Google Scholar
[7]Fraïssé, Roland, Relation theory, North-Holland, Amsterdam (to appear).Google Scholar
[8]Friedman, H., McAloon, K. and Simpson, S. G., A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis, Patras Logic Symposion 1980 (Metakides, G., editor), North-Holland, Amsterdam, 1982, pp. 197–230.CrossRefGoogle Scholar
[9]Friedman, Harvey, Systems of second order arithmetic with restricted induction. I, II, this Journal, vol. 41 (1976), pp. 557–558, 558–559.Google Scholar
[10]Friedman, Harvey, Bar induction and Π11-CA, this Journal, vol. 34 (1969), pp. 353–362.Google Scholar
[11]Jockusch, Carl G. Jr., Ramsey's theorem and recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[12]Jockusch, C. G. Jr., and McLaughlin, T. G., Countable retracting functions and Π20 predicates, Pacific Journal of Mathematics, vol. 30 (1969), pp. 67–93.CrossRefGoogle Scholar
[13]Quinsey, J. E., Some problems in logic: applications of Kripke's notion of fulfilment, Ph.D. Thesis, Oxford University, Oxford, 1980.Google Scholar
[14]Rogers, Hartley Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[15]Sacks, Gerald E., Higher recursion theory, M.I.T. course notes written by D. MacQueen, 1971/1972.Google Scholar
[16]Shoenfield, Joseph R., Degrees of unsolvability, North-Holland, Amsterdam, 1971.Google Scholar
[17]Simpson, Stephen G., Sets which do not have subsets of every higher degree, this Journal, vol. 43 (1978), pp. 135–138.Google Scholar
[18]Simpson, Stephen G., Σ11 and transfinite induction, Logic Colloquium '80, North-Holland, Amsterdam, 1982, pp. 239–253.Google Scholar
[19]Simpson, Stephen G., Set theoretic aspects of ATR0, Logic Colloquium '80, North-Holland, Amsterdam, 1982, pp. 255–271.Google Scholar
[20]Solovay, Robert M., Hyperarithmetically encodable sets, Transactions of the American Mathematical Society, vol. 239 (1978), pp. 99–121.CrossRefGoogle Scholar