Complexity and (un)decidability of fragments of $⟨{\omega }^{{\omega }^{\lambda }};\times ⟩$

Abstract

We specify the frontier of decidability for fragments of the first-order theory of ordinal multiplication. We give a NEXPTIME lower bound for the complexity of the existential fragment of $⟨{\omega }^{{\omega }^{\lambda }};\times ,\omega ,\omega +1,{\omega }^2+1⟩$ for every ordinal $\lambda$. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the ${\exists }^{\ast }{\forall }^6$-fragment of $⟨{\omega }^{{\omega }^{\lambda }};\times ⟩$ is undecidable for every ordinal $\lambda$.