7
$\begingroup$

It is well known that Ackermann's function is not primitive recursive. Therefore, the theories of primitive recursive arithmetic (PRA) and of $\Sigma_1$-induction ($I\Sigma_1$) cannot prove the totality of Ackermann's function.

However $\Sigma_2$-induction suffices to prove the totality of Ackermann's function. It also proves the consistency of $I\Sigma_1$.

My question: Is already the totality of Ackermann's function strong enough to prove the consistency of PRA or $I\Sigma_1$?

$\endgroup$
6
$\begingroup$

The answer is apparently yes.

Recall the Grzegorczk hierarchy $\mathcal{E}^n$. This a hierarchy which classifies computable functions based on their growth rate, see Wikipedia: Grzegorczyk hierarchy.

Now on this hierarchy can be extended to ordinal level, see Wikipedia: Fast Growing Hierarchy. Then we have $\mathcal{E}^\omega:= \bigcup_{n<\omega} \mathcal{E}^n$, which is the same as the set of all primitive recursive functions. On the next level $\mathcal{E}^{\omega+1}$ one find then a variant of the Ackermann function.

Now Cleave, Rose formulate in $\mathcal{E}^n$ arithmetic an arithmetical systems $\mathcal{E}^n$ corresponding to the set of functions $\mathcal{E}^n$. Further, they show there that $\mathcal{E}^{n+1}$ proves the consistency of $\mathcal{E}^n$ for $n<\omega$. In $\mathcal{E}^\alpha$ and transfinite induction Rose claims that this result is also true for $n$ being an infinite ordinal. Thus arithmetic with a variant of the Ackermann function proves consistency of PRA (which is the same as consistency of $I\Sigma_1$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.