Infinite games in the Cantor space and subsystems of second order arithmetic

✍ Scribed by Takako Nemoto; MedYahya Ould MedSalem; Kazuyuki Tanaka

• Publisher: John Wiley and Sons
• Year: 2007
• Tongue: English
• Weight: 202 KB
• Volume: 53
• Category: Article
• ISSN: 0044-3050
• DOI: 10.1002/malq.200610041

✦ Synopsis

Abstract

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)