Expressibility of Peano arithmetic and the Arithmetical Hierarchy

Question

First-order Peano arithmetic has no non-logical symbols other than S, +, *, < and variables. One allows finite quantification over predicates such as: $\forall k<n: \phi(k)$ where $\phi(k)$ is a logical formula containing some non-logical symbol such as A_k. This is because it is understood as a shorthand for $\phi(1)\land \phi(2)...\land \phi(n)$. That way the A_k-s are nothing but n different variables. For example:

$(A_0=1) \land \forall k<3: (A_{k+1} = A_k*(k+1))$

is actually:

$(A_0=1) \land (A_1 = A_0*1)\land (A_2 = A_1*2)$.

This way we can deal with primitive recursive functions.

However, situation is different when moving up in the arithmetical hierarchy. For example, in $\Sigma_1^0$ it is no longer possible to make the above substitution, because the number of variables will now depend on a non-fixed variable on which we quantify in a non-bounded way. Taking the above example, we now have:

$\exists n: (A_0=1) \land \forall k<n: (A_{k+1} = A_k*(k+1))$

which we obviously cannot turn into a formula with no new non-logical symbols.

So my question is: Do we actually allow other non-logical symbols in first-order Peano arithmetic in certain conditions? or do the arithmetical hierarchy formulas actually not belong to first-order Peano arithmetic? or am I missing something?

Answer 1

It turns out that https://en.wikipedia.org/wiki/Course-of-values_recursion is the way to make this possible.

More elaborately, for any quantifier-free formula $\varphi$ one has to create the Goedel number of the formula:

$a_0 = C \land \forall n: a_{n+1} = \varphi(n, a_n)$

where C is some constant (e.g. C could be 1).

Then it can be shown that there is a number and some (other) first-order formula $\psi$ such that:

$\psi(G, 0, C)$

and:

$\psi(G,n,m)$ if and only if, in first order arithmetic to which we add the predicate $a_n$, the recursion formula defined by $\varphi$ implies: $a_n = m$. Thus in proper first order arithmetic (without addition of new predicates) the recursion can be "recreated" by G and $\psi$.

One way to do that is with Goedel's beta function: https://en.wikipedia.org/wiki/G%C3%B6del%27s_%CE%B2_function.

Answer 2

You are misinterpreting bounded quantifiers.

"$\forall x<y(\varphi)$" is shorhand for "$\forall x(x<y\rightarrow \varphi).$"

Similarly, "$\exists x<y(\varphi)$" is shorthand for "$\exists x(x<y\wedge\varphi)$."

This can be generalized greatly: in any language, for any definable binary relation $R$, we write "$\forall x Ry(\varphi)$" as shorthand for "$\forall x(xRy\rightarrow \varphi)$," etc. For example, expressions of the form "$\forall x\in y$" are common in set theory, and there's a corresponding version of the arithmetical hierarchy in which such expressions are "for free" (similarly to bounded quantification in arithmetic).

---

Note that the "substitution" interpretation you give breaks down immediately if the model under study is something other than the classical $\mathbb{N}$. Suppose $M$ is a nonstandard model of $PA$, and $c\in M$ is an infinite element. Then how would you interpret "$\forall x<c(\varphi(x))$"?