Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-22T20:51:35.315Z Has data issue: false hasContentIssue false
  • English
  • Français

A generalization of the limit lemma and clopen games

Published online by Cambridge University Press:  12 March 2014

Peter Clote
Peter Clote*
Affiliation:
Computer Science Department, Boston College, Chestnut Hill, Massachusetts 02167
Get access Rights & Permissions [Opens in a new window]

Abstract

We give a new characterization of the hyperarithmetic sets: a set X of integers is recursive in e α if and only if there is a Turing machine which computes X and “halts” in less than or equal to the ordinal number ωα of steps. This result represents a generalization of the well-known “limit lemma” due to J. R. Shoenfield [Sho-1] and later independently by H. Putnam [Pu] and independently by E. M. Gold [Go]. As an application of this result, we give a recursion theoretic analysis of clopen determinacy: there is a correlation given between the height α of a well-founded tree corresponding to a clopen game A ⊆ ωω and the Turing degree of a winning strategy ƒ for one of the players—roughly, ƒ can be chosen to be recursive in 0 α and this is the best possible (see §4 for precise results).

Keywords

Limit lemmaclopen gameshyperarithmetic winning strategytrees.
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 51 , Issue 2 , June 1986 , pp. 273 - 291
Copyright
Copyright © Association for Symbolic Logic 1986

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.)

Footnotes

1

I would like to express my thanks to Professors K. McAloon and J. R. Shoenfield, as well as to Professor C. G. Jockusch, Jr., for some helpful correspondence. I would also like to thank the referee for pointing out an error in an earlier version of the generalized limit lemma (concerning partial functions), for giving a simplification of the successor step in Theorem 2 and for suggesting a possible strengthening of the generalized limit lemma, thus allowing a converse. A weaker version of the generalized limit appeared in [Cl-1].

References

REFERENCES

[AP] Apt, K. R. and Plotkin, G. O., Countable nondeterminism and random assignment, manuscript, 1982 (to appear).CrossRefGoogle Scholar
[B1] Blass, A., Complexity of winning strategies, Discrete Mathematics, vol. 3 (1972), pp. 295–300.CrossRefGoogle Scholar
[Ch] Chen, K. H., Recursive well-founded orderings, Annals of Mathematical Logic, vol. 13 (1978), pp. 117–147.CrossRefGoogle Scholar
[Cl-1] Clote, P., 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
[IC1-2] Clote, P., Anti-basis theorems and their relation to independence results in Peano arithmetic, Model theory and arithmetic, Lecture Notes in Mathematics, vol. 890, Springer-Verlag, Berlin, 1981, pp. 115–133.CrossRefGoogle Scholar
[Cl-3] Clote, P., A recursion theoretic analysis of the clopen Ramsey theorem, this Journal, vol. 49 (1984), pp. 376–400.Google Scholar
[FMS] Friedman, H., McAloon, K. and Simpson, S. G., A finite combinatorial principle which is equivalent to the l-consistency of predicative analysis, Patras Logic Symposion (Patras, 1980), North-Holland, Amsterdam, 1982, pp. 197–230.CrossRefGoogle Scholar
[Go] Gold, E. Mark, Limiting recursion, this Journal, vol. 30 (1965), pp. 28–48.Google Scholar
[Gr] Grimeisen, G., Ein Approximationssatz für Bairesche Funktionen, Mathematische Annalen, vol. 146 (1962), pp. 189–194.CrossRefGoogle Scholar
[Ha] Harel, D., A general result on infinite trees and its applications, Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing, 1984, pp. 418–427.Google Scholar
[Jo] Jockusch, C. G. Jr., Ramsey's theorem and recursion theory, this Journal, vol. 37 (1972), pp. 268–280.Google Scholar
[Pu] Putnam, H., Trial and error predicates and the solution to a problem of Mostowski, this Journal, vol. 30 (1965), pp. 49–57.Google Scholar
[Ro] Rogers, H. Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967.Google Scholar
[Shap] Shapiro, N., Real numbers and functions in the Kleene hierarchy and limits of recursive rational functions, this Journal, vol. 34 (1969), pp. 207–214.Google Scholar
[Sho-1] Shoenfield, J. R., On degrees of unsolvability, Annals of Mathematics, ser. 2, vol. 69 (1959), pp. 644–653.CrossRefGoogle Scholar
[Sho-2] Shoenfield, J. R., Degrees of unsolvability, North-Holland, Amsterdam, 1971.Google Scholar