No CrossRef data available.
Article contents
A generalization of the limit lemma and clopen games
Published online by Cambridge University Press: 12 March 2014
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).
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1986
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
[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