Premium
Infinite games in the Cantor space and subsystems of second order arithmetic
Author(s) -
Nemoto Takako,
Ould MedSalem MedYahya,
Tanaka Kazuyuki
Publication year - 2007
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200610041
Subject(s) - mathematics , sigma , determinacy , order (exchange) , space (punctuation) , combinatorics , operator (biology) , discrete mathematics , arithmetic , mathematical analysis , physics , linguistics , philosophy , biochemistry , chemistry , finance , repressor , quantum mechanics , transcription factor , economics , gene
In this paper we study the determinacy strength of infinite games in the Cantor space and compare them with their counterparts in the Baire space. We show the following theorems: 1. RCA 0 ⊢ $ \Delta^0_1 $ ‐Det* ↔ $ \Sigma^0_1 $ ‐Det* ↔ WKL 0 . 2. RCA 0 ⊢ ( $ \Sigma^0_1 $ )2‐Det* ↔ ACA 0 . 3. RCA 0 ⊢ $ \Delta^0_2 $ ‐Det* ↔ $ \Sigma^0_2 $ ‐Det* ↔ $ \Delta^0_1 $ ‐Det ↔ $ \Sigma^0_1 $ ‐Det ↔ ATR 0 . 4. For 1 < k < ω , RCA 0 ⊢ ( $ \Sigma^0_2 $ ) k ‐Det* ↔ ( $ \Sigma^0_2 $ ) k –1 ‐Det. 5. RCA 0 ⊢ $ \Delta^0_3 $ ‐Det* ↔ $ \Delta^0_3 $ ‐Det. Here, Det* (respectively Det) stands for the determinacy of infinite games in the Cantor space (respectively the Baire space), and ( $ \Sigma^0_n $ ) k is the collection of formulas built from $ \Sigma^0_n $ formulas by applying the difference operator k – 1 times. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)