Is $I\Delta_0+\Omega_1$ globally interpretable in Q?

73 Views Asked by At

Alex Wilkie found a single formula $J(x)$ for an inductive cut of the natural numbers such that the axioms of Robinson arithmetic are sufficient to prove every instance of the induction scheme $\phi(0)\rightarrow(\forall n\in J\!: \phi(n)\rightarrow\phi(n+1))\rightarrow\forall n\in J\!:\phi(n)$ where $\phi(x)\in\Delta_0$ and all of its quantifiers are additionally relativized by $J(x)$. This is theorem 2.7 in Pudlák's Some prime elements in the lattice of interpretability types and it's mentioned in many other places.

$\Omega_1$ is the axiom asserting that $\omega_2(x)=x^{\lfloor\log_2 x\rfloor}$ (or sometimes an inequivalent function with a similar growth rate) is total. It is known that given any finite list of $\Delta_0$ formulas which include the $\omega_2$ function, it is possible to find a cut $J'$ which is closed under $\omega_2$ and within which the induction schemes for those specific formulas can be proven. But if you need any other instances of the induction scheme, you have to find a different cut.

Thus $I\Delta_0$ (from the first paragraph) is globally interpretable in Robinson arithmetic, whereas $I\Delta_0+\Omega_1$ (second paragraph) is only locally interpetable.

My question is whether $I\Delta_0+\Omega_1$ is globally interpretable in Robinson arithmetic after all, or if it is provably not globally interpretable, or if the question is still unresolved.

1

There are 1 best solutions below

0
On BEST ANSWER

The answer is in the positive; see Theorem 5.7 (chapter V) of the book Metamathematics of First Order Arithmetic by Petr Hájek and Pavel Pudlák. A free copy of all the chapters of the book can be found on this link.

As the above theorem shows, something stronger is true: for each $n$ there is a global interpretation of $\mathrm{I}\Delta_0 + \Omega_n$ in $\mathsf{Q}$.

Another great source is the paper Interpretability in Robinson's Q by Fernando Ferreira and Gilda Ferreira, published in the Bulletin of Symbolic Logic (2013), a free preprint can be found here (see p.12, Proposition 3).