Complexity and (Un)decidability of Fragments of 〈 ω ω λ;× 〉

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 \text{,}\omega \text{,}\omega \text{+1,}{\omega }^2+1〉$ for every ordinal λ. Moreover, we prove (by reduction from Hilbert Tenth Problem) that the ∃*∀⁶-fragment of $〈{\omega }^{{\omega }^{\lambda }};\times 〉$ is undecidable for every ordinal λ.