Abstract
We prove the equivalence of the determinacy of \(\Sigma^0_3\) (effectively Gδσ) games with the existence of a β-model satisfying the axiom of \(\Pi^2_1\) monotone induction, answering a question of Montalbán [8]. The proof is tripartite, consisting of (i) a direct and natural proof of \(\Sigma^0_3\) determinacy using monotone inductive operators, including an isolation of the minimal complexity of winning strategies; (ii) an analysis of the convergence of such operators in levels of G¨odel’s L, culminating in the result that the nonstandard models isolated by Welch [18] satisfy \(\Pi^2_1\) monotone induction; and (iii) a recasting of Welch’s [17] Friedman-style game to show that this determinacy yields the existence of one of Welch’s nonstandard models. Our analysis in (iii) furnishes a description of the degree of \(\Pi^2_1\)-correctness of the minimal β-model of \(\Pi^2_1\) monotone induction.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
J. Barwise, Admissible Sets and Structures, Perspectives in Mathematical Logic, Springer, Berlin–New York, 1975
M. Davis, Infinite games of perfect information, in Advances in Game Theory, Princeton University Press, Princeton, NJ, 1964, pp. 85–101.
S.-D. Friedman, Parameter-free uniformisation, Proceedings of the American Mathematical Society 136 (2008), 3327–3330.
R. B. Jensen, The fine structure of the constructible hierarchy, Annals of Mathematical Logic 4 (1972), 229–308; erratum, ibid. 4 (1972), 443.
D. A. Martin, Determinacy, unpublished manuscript.
D. A. Martin, \(\Pi^2_1\) monotone inductive definitions, in Cabal Seminar 77–79 (Proc. Caltech-UCLA Logic Sem., 1977–79), Lecture Notes in Mathematics, Vol. 839, Springer, Berlin–New York, 1981, pp. 215–233.
M. O. MedSalem and K. Tanaka, Weak determinacy and iterations of inductive definitions, in Computational Prospects of Infinity. Part II. Presented Talks, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, Vol. 15, World Scientific, Hackensack, NJ, 2008, pp. 333–353.
A. Montalbán, Open questions in reverse mathematics, Bulletin of Symbolic Logic 17 (2011), 431–454.
A. Montalbán and R. A. Shore, The limits of determinacy in second-order arithmetic, Proceedings of the London Mathematical Society 104 (2012), 223–252.
A. Montalbán and R. A. Shore, The limits of determinacy in second order arithmetic: consistency and complexity strength, Israel Journal of Mathematics 204 (2014), 477–508.
Y. N. Moschovakis, Descriptive Set Theory, Mathematical Surveys and Monographs, Vol. 155, American Mathematical Society, Providence, RI, 2009.
G. E. Sacks, Higher Recursion Theory, Perspectives in Mathematical Logic, Springer, Berlin, 1990.
S. G. Simpson, Subsystems of Second Order Arithmetic, Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009.
J. R. Steel, Determinateness and subsystems of analysis, ProQuest LLC, Ann Arbor,MI, 1977, Thesis (Ph.D.)–University of California, Berkeley.
K. Tanaka, Weak axioms of determinacy and subsystems of analysis. I. Δ02 games, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 36 (1990), 481–491.
K. Tanaka, Weak axioms of determinacy and subsystems of analysis. II. Σ02 games, Annals of Pure and Applied Logic 52 (1991), 181–193.
P. D. Welch, Weak systems of determinacy and arithmetical quasi-inductive definitions, Journal of Symbolic Logic 76 (2011), 418–436.
P. D. Welch, Gδσ games, Isaac Newton Institute Preprint Series (2012), 1–10.
K. Yoshii, A survey of determinacy of infinite games in second order arithmetic, Annals of the Japan Association for Philosophy of Science 25 (2017), 35–44.
K. Yoshii and K. Tanaka, Infinite games and transfinite recursion of multiple inductive definitions, in How the World Computes, Lecture Notes in Computer Science, Vol. 7318, Springer, Heidelberg, 2012, pp. 374–383.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Hachtman, S. Determinacy and monotone inductive definitions. Isr. J. Math. 230, 71–96 (2019). https://doi.org/10.1007/s11856-018-1802-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-018-1802-1