A Generalization of the Limit Lemma and Clopen Games
Clote, Peter
J. Symbolic Logic, Tome 51 (1986) no. 1, p. 273-291 / Harvested from Project Euclid
We give a new characterization of the hyperarithmetic sets: a set $X$ of integers is recursive in $e_\alpha$ if and only if there is a Turing machine which computes $X$ and "halts" in less than or equal to the ordinal number $\omega^\alpha$ 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 $\alpha$ of a well-founded tree corresponding to a clopen game $A \subseteq \omega^\omega$ and the Turing degree of a winning strategy $f$ for one of the players--roughly, $f$ can be chosen to be recursive in $0^\alpha$ and this is the best possible (see $\S 4$ for precise results).
Publié le : 1986-06-14
Classification:  Limit lemma,  clopen games,  hyperarithmetic winning strategy,  trees
@article{1183742093,
     author = {Clote, Peter},
     title = {A Generalization of the Limit Lemma and Clopen Games},
     journal = {J. Symbolic Logic},
     volume = {51},
     number = {1},
     year = {1986},
     pages = { 273-291},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183742093}
}
Clote, Peter. A Generalization of the Limit Lemma and Clopen Games. J. Symbolic Logic, Tome 51 (1986) no. 1, pp.  273-291. http://gdmltest.u-ga.fr/item/1183742093/