Hierarchy of Arithmetic Formulas

Let $\mathcal{L}=\{S,<,+,\cdot ,0\}$ be the language of arithmetic.

${\Delta }_0$ Formulas

A formula $\phi$ is a ${\Delta }_0$-formula if

• $\phi$ is atomic
• apply $\neg ,\wedge ,\vee ,\to$, that is $\phi$ is $\neg \psi$ where $\psi$ is ${\Delta }_0$
• bounded quantifiers $\exists x(x<t\wedge \psi )$ where $t$ is a term not containing $x$ and $\psi$ is ${\Delta }_0$
• $\phi$ is $\forall x(x<t\to \psi )$where$t$ is a term not containing $x$ and $\psi$ is ${\Delta }_0$.

Validity for ${\Delta }_0$ Formulas

Suppose $\mathfrak{N}$ is the standard model for arithmetic and $\phi (x_1,\dots ,x_n)$ is a ${\Delta }_0$-formula with free variables $x_1,\dots ,x_n$. Then it is a “mechanical” procedure to check if $\mathfrak{N}\models \phi (a_1,\dots ,a_n)$, where $(a_1,\dots ,a_n)\in {\mathbb{N}}^n$ ($\mathbb{N}$ the universe of $\mathfrak{N}$). In particular, $\{(a_1,\dots ,a_n)\in {\mathbb{N}}^n\mid \mathfrak{N}\models \phi (a_1,\dots ,a_n)\}$ is primitive recursive. If $\mathfrak{A}=⟨A;S,+,\cdot ,,0⟩$ is an end-extension of $\mathfrak{N}$ with $\mathbb{N}\subset A$, then for $(a_1,\dots ,a_n)\in {\mathbb{N}}^n$,} $\mathfrak{N}\models \phi (a_1,\dots ,a_n)\text{iff}\mathfrak{A}\models \phi (a_1,\dots ,a_n).$

${\Sigma }_1/{\Pi }_1$ Formulas

A formula $\phi$ is a ${\Sigma }_1/{\Pi }_1$-formula if it is of the form $\exists x_1\exists x_2...\exists x_n\phi$ or $\forall x_1\forall x_2...\forall x_n\phi$ respectively, where $\phi$ is ${\Delta }_0$