Example of a $Δ_1$-formula that is not $Δ_0$ (arithmetical hierarchy).

Question

In the arithmetical hierarchy, the class of $Δ_1$-formulas is defined as the intersection of $Σ_1$- and $Π_1$-formulas. It is obvious that every $Δ_0$-formula is $Δ_1$, but not every $Σ_1$- or every $Π_1$-formula is (for example the Gödelsentence, which is clearly $Π_1$ but not $Σ_1$, cf. Gödel's first theorem). What I am looking for is a $Δ_1$-formula that is not $Δ_0$.

Answer 1

EDIT: it's easy to check that any function which is $\Delta_0$-definable is primitive recursive, so consider the Ackermann function. And in fact there is a primitive recursive function which is not $\Delta_0$-definable; see here.

---

Let $(\varphi_i)_{i\in\mathbb{N}}$ be an effective enumeration of the bounded-quantifier-only (=$\Delta_0$) one-variable formulas, and consider the set $$R_0=\{n: \neg\varphi_n(n)\}$$ (the "$\Delta_0$-Russell set"). The set $R_0$ is clearly computable (since we can computably check whether a bounded-quantifier-only formula holds of a given input) and so is definable by a $\Delta_1$ formula, but by diagonalization $R_0$ can't be defined by any formula using only bounded quantifiers. Now just pick a formula defining $R_0$.

A computability-free argument: we can express satisfaction of a bounded-quantifier-only formula at a given input in a $\Sigma_1$ way (since such satisfaction is witnessed by finitely much data), so this gives a $\Pi_1$ definition of $R_0$; now note that the negation of a bounded-quantifier-only formula is again bounded-quantifier-only, and this gives a $\Sigma_1$ definition of $R_0$.

---

Incidentally, note that "$\Delta_1$-formula" is a slightly abusive term. When we say that a formula $\varphi$ is $\Delta_1$, what we mean is that there are formulas $\psi_1,\psi_2$ which are $\Sigma_1,\Pi_1$ respectively and such that $\varphi$ is equivalent to $\psi_1$ and is equivalent to $\psi_2$. This is an important thing to point out because equivalence of formulas is hard to prove: e.g. we can computably tell whether a formula is $\Sigma_1$ just by putting it into normal form, but we can't computably tell whether a formula is equivalent to a $\Sigma_1$ formula.

In the example above, we've whipped up something quite nice: a formula $\varphi$ which a very weak theory of arithmetic proves is equivalent to both a $\Sigma_1$ formula and a $\Pi_1$ formula. So we've gotten the ideal situation.