0
$\begingroup$

I posted this question on math.stackexchange.com with no answers (https://math.stackexchange.com/questions/4337852/an-arithmetic-hierarchy-without-bounded-quantifiers).

Let $\exists_n$ formulas in the language of arithmetic be defined like $\Sigma_n$ formulas, except that bounded quantifiers count toward the number of quantifier alternations. For example, $\exists_1$ formulas are purely existential formulas, those of the form $\exists \bar{y} \phi(\bar{x}, \bar{y})$, where $\phi$ is quantifier-free. For all $n \ge 1$, are all $\Sigma_n$ formulas equivalent to $\exists_n$ formulas, in the sense that if $\phi$ is $\Sigma_n$, then there is a $\exists_n$ formula $\psi$ such that $\mathbb{N} \models \forall \bar{x} (\phi(\bar{x}) \leftrightarrow \psi(\bar{x}))$? I'm also curious whether we can even have $\mathrm{PA} \vdash \forall \bar{x} (\phi(\bar{x}) \leftrightarrow \psi(\bar{x}))$, where $\mathrm{PA}$ is Peano arithmetic.

It's easy to see that the answer is negative for $n = 0$, and for $n=1$ the answer is affirmative by the MRDP theorem.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Every $\Sigma_n$ or $\Pi_n$ formula is equivalent over PA to $n$ alternating quantifiers followed by a bounded formula. Don't you get a positive answer to your question for $n \geq 1$ by using the MRDP theorem to replace the innermost $\Sigma_1$ or $\Pi_1$ formula with an $\exists_1$ or $\forall_1$ formula? $\endgroup$
    – Gabe Goldberg
    Commented Dec 23, 2021 at 19:00
  • 2
    $\begingroup$ One subtlety in @GabeGoldberg's comment is that you need the "internal" MRDP theorem rather than the MRDP theorem as usually stated - that is, you need to check that the proof of MRDP goes through in PA. But it does, so that's fine. $\endgroup$
    – Noah Schweber
    Commented Dec 23, 2021 at 19:09
  • $\begingroup$ @GabeGoldberg Thanks. I forgot bounded quantifiers can be pushed after the unbounded quantifiers. $\endgroup$
    – BPP
    Commented Dec 24, 2021 at 1:52

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .