5
$\begingroup$

The proof that all formulas of second-order arithmetic are $\Pi^1_n$ for some $n$ (i.e. can be written with a bloc of second-order quantifiers followed by an arithmetical formula) uses the axiom of countable choice, which is independent of $Z_2$. Does comprehension for formulas with all the second-order quantifiers in front imply comprehension for all formulas anyway?

More generally, does this hold level-by-level of the analytical hierarchy? More precisely, say that a formula is weakly $\Pi^1_n$ if it can be written with $n-1$ second-order quantifier alternations starting with $\forall$, but also allowing arithmetical quantifiers interspersed between the second-order quantifiers (i.e. the formulas that countable choice implies are $\Pi^1_n$). Does $\Pi^1_n-CA_0$ imply comprehension for weakly $\Pi^1_n$ formulas?

$\endgroup$
1
  • 3
    $\begingroup$ Yes for the first question: you can simulate a number quantifier by a set quantifier with a clause ensuring the set is a singleton. It is easy to see that if you rewrite the formula like this, all the set quantifiers can be moved to the front. $\endgroup$ Jun 25, 2018 at 7:44

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.