Weak systems of determinacy and arithmetical quasi-inductive definitions. (English) Zbl 1225.03082

Welch, P. D.

J. Symb. Log. 76, No. 2, 418-436 (2011).

Summary: We locate winning strategies for various \(\Sigma^0_3\)-games in the \(L\)-hierarchy in order to prove the following:
Theorem 1. \(\text{KP} + \Sigma_2\)-Comprehension \(\vdash \exists \alpha L_\alpha\vDash\text{``}\Sigma_2\text{-KP}+\pmb{\Sigma}^0_3\)-Determinacy”. Alternatively: \(\Pi^1_3\)-CA\(_0\vdash\) “there is a \(\beta\)-model of \(\Delta^1 _3\)-CA\(_0+\pmb{\Sigma}^0_3\)-Determinacy”. The implication is not reversible. (The antecedent here may be replaced with \(\Pi^1 _3 (\Pi^1 _3)\text{-CA}_0\): \(\Pi^1_3\) instances of Comprehension with only \(\Pi^1 _3\)-lightface definable parameters – or even weaker theories.)
Theorem 2. \(\text{KP}+\Delta_2\)-Comprehension \(+\Sigma_2\)-Replacement \(+\text{AQI}\nvdash\Sigma^0_3\)-Determinacy.
(Here AQI is the assertion that every arithmetical quasi-inductive definition converges.) Alternatively: \(\Delta^1_3\text{-CA}_0+\text{AQI}\nvdash\Sigma^0_3\)-Determinacy.
Hence the theories \(\Pi^1_3\text{-CA}_{0}\), \(\Delta^1_3\text{-CA}_{0}+\Sigma^0_3\)-Det, \(\Delta^1_3\text{-CA}_0\)+AQI, and \(\Delta^1_3\text{-CA}_{0}\) are in strictly descending order of strength.

MSC:

03F35	Second- and higher-order arithmetic and fragments
91A80	Applications of game theory

Keywords:

subsystems of second-order arithmetic; \(\Sigma^0_3\)-games; determinacy; comprehension; arithmetical quasi-inductive definition

References:

[1]	Ways of proof theory: Festschrift for W. Pohlers (2010)
[2]	Recursion in Kolmogoroff’s R operator and the ordinal {\(\sigma\)}3 51 pp 1– (1986)
[3]	Eventually Infinite Time Turing degrees: infinite time decidable reals 65 pp 1193– (2000) · Zbl 0959.03025
[4]	DOI: 10.1007/BF00302339 · Zbl 0513.03003
[5]	Foundations of the Formal Sciences V pp 143– (2007)
[6]	Infinite time Turing machines 65 pp 567– (2000)
[7]	DOI: 10.1090/S0002-9939-08-09275-7 · Zbl 1145.03030
[8]	DOI: 10.1023/A:1023027808400 · Zbl 1026.03009
[9]	Constructibility (1984) · Zbl 0542.03029
[10]	Annals of Mathematical Studies 52 pp 85– (1964)
[11]	The truth is never simple 51 pp 663– (1986)
[12]	Admissible sets and structures (1975)
[13]	DOI: 10.1016/0168-0072(91)90045-N · Zbl 0729.03033
[14]	Subsystems of second order arithmetic (1999) · Zbl 0909.03048
[15]	Higher recursion theory (1990) · Zbl 0716.03043
[16]	DOI: 10.1007/s00153-004-0226-2 · Zbl 1068.03046
[17]	DOI: 10.1007/s00153-004-0232-4 · Zbl 1068.03047
[18]	Annual conference of the European Association for Computer Science Logic (CLS) 2471 (2002)
[19]	DOI: 10.1007/BFb0069303
[20]	DOI: 10.1112/S0024609399006657 · Zbl 1016.03040