Automatic Ordinals

Abstract

We prove that the injectively omega-tree-automatic ordinals are the ordinals smaller than ${\omega }^{{\omega }^{\omega }}$. Then we show that the injectively ${\omega }^n$-automatic ordinals, where $n>0$ is an integer, are the ordinals smaller than ${\omega }^{{\omega }^n}$. This strengthens a recent result of Schlicht and Stephan who considered in [Schlicht-Stephan11] the subclasses of finite word ${\omega }^n$-automatic ordinals. As a by-product we obtain that the hierarchy of injectively ${\omega }^n$-automatic structures, n>0, which was considered in [Finkel-Todorcevic12], is strict.

To appear in a Special Issue on New Worlds of Computation 2011 of the International Journal of Unconventional Computing. arXiv admin note: text overlap with arXiv:1111.1504