The limits of determinacy in second-order arithmetic

Abstract

We establish the precise bounds for the amount of determinacy provable in second-order arithmetic. We show that, for every natural number n, second-order arithmetic can prove that determinacy holds for Boolean combinations of n many Π 3 0 classes, but it cannot prove that all finite Boolean combinations of Π 3 0 classes are determined. More specifically, we prove that Π n + 2 − 1 C A 0 ⊢ n − Π 3 − 0 D E T , but that Δ n + 2 − 1 C A ⊬ n − Π 3 − 0 D E T , where n − Π 3 0 is the nth level in the difference hierarchy of Π 3 0 classes. We also show some conservativity results that imply that reversals for the theorems above are not possible. We prove that, for every true Σ14 sentence T (as, for instance, n − Π 3 − 0 D E T ) and every n ⩾ 2 , Δ n − 1 C A 0 + T + Π ∞ − 1 T I ⊬ n − Π n − 1 C A 0 and Π n − 1 − 1 C A 0 + T + Π ∞ − 1 T I ⊬ Δ n − 1 C A 0 .