Abstract
The purpose of this research is to investigate the logical strength of weak determinacy of Gale-Stewart games from the standpoint of reverse mathematics. It is known that the determinacy of \(\Sigma^0_1\) sets (open sets) is equivalent to system ATR0 and that of \(\Sigma^0_2\) corresponds to the axiom of \(\Sigma^1_1\) inductive definitions. Recently, much effort has been made to characterize the determinacy of game classes above \(\Sigma^0_2\) within second order arithmetic. In this paper, we show that for any k ∈ ω, the determinacy of \(\Delta((\Sigma^0_2)_{k+1})\) sets is equivalent to the axiom of transfinite recursion of \(\Sigma^1_1\) inductive definitions with k operators, denote \([\Sigma^1_1]^k\)-IDTR. Here, \((\Sigma^0_2)_{k+1}\) is the difference class of k + 1 \(\Sigma^0_2\) sets and \(\Delta((\Sigma^0_2)_{k+1})\) is the conjunction of \((\Sigma^0_2)_{k+1}\) and co-\((\Sigma^0_2)_{k+1}\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bradfield, J.C.: Fixpoints, games and the difference hierarchy. Theor. Inform. Appl. 37, 1–15 (2003)
Bradfield, J.C.: The modal μ-calculus alternation hierarchy is strict. Theor. Comput. Sci. 195, 133–153 (1998)
Heinatsch, C., Möllerfeld, M.: The determinacy strength of \(\Pi^1_2\)-comprehension. Ann. Pure Appl. Logic 161, 1462–1470 (2010)
Mashiko, K., Tanaka, K., Yoshii, K.: Determinacy of the Infinite Games and Inductive Definition in Second Order Arithmetic. In: RIMS Kokyuroku, vol. 1729, pp. 167–177 (2011)
MedSalem, M.O., Tanaka, K.: \(\Delta^0_3\)-determinacy, comprehension and induction. Journal of Symbolic Logic 72, 452–462 (2007)
MedSalem, M.O., Tanaka, K.: Weak determinacy and iterations of inductive definitions. Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap., vol. 15. World Sci. Publ., Hackensack (2008)
Montalbán, A., Shore, R.A.: The Limits of determinacy in second order arithmetic (preprint)
Montalbán, A.: Open Questions in Reverse Mathematics. Bulletin of Symbolic Logic 17, 431–454 (2011)
Nemoto, T.: Determinacy of Wadge classses and subsystems of second order arithmetic. Math. Log. Quart. 55(2), 154–176 (2009)
Nemoto, T., MedSalem, M.O., Tanaka, K.: Infinite games in the Cantor space and subsystems of second order arithmetic. Math. Log. Quart. 53, 226–236 (2007)
Simpson, S.G.: Subsystems of Second Order Arithmetic. Springer (1999)
Tanaka, K.: Weak axioms of determinacy and subsystems of analysis I (\(\Delta^0_2\) games). Z. Math. Logik Grundlag. Math. 36, 481–491 (1990)
Tanaka, K.: Weak axioms of determinacy and subsystems of analysis II (\(\Sigma^0_2\) games). Ann. Pure Appl. Logic 52, 181–193 (1991)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Yoshii, K., Tanaka, K. (2012). Infinite Games and Transfinite Recursion of Multiple Inductive Definitions. In: Cooper, S.B., Dawar, A., Löwe, B. (eds) How the World Computes. CiE 2012. Lecture Notes in Computer Science, vol 7318. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-30870-3_38
Download citation
DOI: https://doi.org/10.1007/978-3-642-30870-3_38
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-30869-7
Online ISBN: 978-3-642-30870-3
eBook Packages: Computer ScienceComputer Science (R0)