Complexity of winning strategies for Δ⁰₂ games

Barua, Rana

doi:10.1090/S0002-9939-1993-1119261-5

Complexity of winning strategies for $\Delta ^ 0_ 2$ games
HTML articles powered by AMS MathViewer

by Rana Barua PDF

Proc. Amer. Math. Soc. 117 (1993), 227-233 Request permission

Abstract:

For a $\Delta _2^0$ game played on $\omega$, we show that the winning player has a winning strategy that is recursive in ${\mathbb {E}_1}$, where ${\mathbb {E}_1}$ is the total type-$2$ object that embodies operation $\mathcal {A}$.

References

P. Aczel, Representability in some systems of second order arithmetic, Israel J. Math. 8 (1970), 309–328. MR 269501, DOI 10.1007/BF02798678

Structure of hyperarithmetical sets of ambiguous Borel classes

Rana Barua, A note on $_2\textrm {sc}(\textbf {E}_1)$, Proc. Amer. Math. Soc. 103 (1988), no. 3, 921–925. MR 947683, DOI 10.1090/S0002-9939-1988-0947683-X

Classical hierarchies from a modern standpoint, Part

sets

115

Part

sets

Peter G. Hinman, Recursion-theoretic hierarchies, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1978. MR 499205, DOI 10.1007/978-3-662-12898-5
Peter G. Hinman, Hierarchies of effective descriptive set theory, Trans. Amer. Math. Soc. 142 (1969), 111–140. MR 265161, DOI 10.1090/S0002-9947-1969-0265161-3
Thomas John, Recursion in Kolmogorov’s $R$-operator and the ordinal $\sigma _3$, J. Symbolic Logic 51 (1986), no. 1, 1–11. MR 830066, DOI 10.2307/2273936
K. Kuratowski, Topology. Vol. I, Academic Press, New York-London; Państwowe Wydawnictwo Naukowe [Polish Scientific Publishers], Warsaw, 1966. New edition, revised and augmented; Translated from the French by J. Jaworowski. MR 0217751
Alain Louveau, A separation theorem for $\Sigma ^{1}_{1}$ sets, Trans. Amer. Math. Soc. 260 (1980), no. 2, 363–378. MR 574785, DOI 10.1090/S0002-9947-1980-0574785-X
Yiannis N. Moschovakis, Descriptive set theory, Studies in Logic and the Foundations of Mathematics, vol. 100, North-Holland Publishing Co., Amsterdam-New York, 1980. MR 561709