Premium
The limits of determinacy in second‐order arithmetic
Author(s) -
Montalbán Antonio,
Shore Richard A.
Publication year - 2012
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/pdr022
Subject(s) - determinacy , mathematics , order (exchange) , combinatorics , discrete mathematics , second order arithmetic , arithmetic , economics , mathematical analysis , finance , peano axioms
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 0classes, but it cannot prove that all finite Boolean combinations ofΠ 3 0classes are determined. More specifically, we prove that Π n + 2 −1C A 0 ⊢ n −Π3 −0D E T , but that Δ n + 2 −1C A ⊬ n −Π3 −0D E T , where n −Π 3 0is the n th level in the difference hierarchy ofΠ 3 0classes. We also show some conservativity results that imply that reversals for the theorems above are not possible. We prove that, for every true Σ 1 4 sentence T (as, for instance, n −Π3 −0D E T ) and every n ⩾ 2 , Δ n −1C A 0 + T + Π ∞ −1T I ⊬ n −Πn −1C A 0and Π n − 1 −1C A 0 + T + Π ∞ −1T I ⊬ Δn −1C A 0 .