Recently, I've been studying what the definable subsets of the countable ordinals "look like" from the perspective of bare-bones first order logic (not set theory) equipped with various ways to "access" the structure of the ordinals.


For example, we may have a signature consisting only of a 2-arity relational symbol $S$ which we interpret in a structure $\mathcal{A}$ with underlying set $\omega\_1$ as the set of $(\alpha,\beta)$ such that $\beta$ is the successor of $\alpha$. We can then ask questions about which subsets of $\mathcal{A}$ are definable by first-order logic sentences with this signature, where a subset $S\subset\mathcal{A}$ is considered definable if there is a first order logic sentence $\phi(x)$ for which the set of satisfying assignments of $x$ is $S$. In our example, we can define the set of all countable successor ordinals via the formula $\exists y:S(y,x)$.


We can also ask questions like "what is the smallest ordinal $\alpha$ such that $\alpha$ is undefinable in the sense that $\{\alpha\}$ is undefinable" and such. In the example above, it's clear to see that in fact no ordinal is definable, so the smallest undefinable ordinal is zero. I am particularly interested in how the smallest undefinable ordinal grows as we have stronger and stronger signatures. For example, I have been able to convince myself that with the signature $\{<\}$ with the obvious interpretation in $\omega\_1$ as the "less than relation", the smallest undefinable ordinal is $\omega^\omega$ (though I haven't written my argument out formally yet).


My question is: has anyone studied questions like these? Is it known what the smallest definable ordinal is for various other signatures, like $\{ADD(x,y,z)\}$ which is true on all $x,y,z$ so that $x+y=z$, or even other signatures with multiplication, exponentiation, veblen functions, or more? Are there any known generalizations of these ideas? Any help or related literature would be appreciated.



Definability of ordinals in various signatures
I do not have enough reputation to add a comment. The following paper may be useful for you. It contains results extending the work of Tarski, Mostowski, and Doner, as well as some very nice historical overview and references.


[Buchi, Siefkes - The Complete Extensions of the Monadic Second Order Theory of Countable Ordinals.](https://link.springer.com/chapter/10.1007/978-1-4613-8928-6_27)


Weak monadic second order logic appears already in Ehrenfeucht's original work. Even if you are exclusively interested in first order results, (weak) monadic second order logic can play a role.


For example the first order theory of ordinal addition coincides with the first order theory of ordinal addition inside $\omega^{\omega^{\omega}}$ (by Ehrenfeuct), while $(\omega^{\omega^{\omega}},+)$ is a reduct of a generalised power of $(\omega,+)$ with 'exponent' being the weak monadic second order version of $(\omega^{\omega},<)$ (the Feferman-Vaught theorem is the correct tool to understand this). For more details there is [Thomas - Ehrenfeucht, Vaught, and the decidability of the weak monadic theory of successor](https://dl.acm.org/doi/abs/10.1145/3183645.3183647), the details here are all correct but I think the conclusions have some issues.


There is also more recent work on the automata side such as [Cachat - Tree Automata Make Ordinal Theory Easy.](https://link.springer.com/chapter/10.1007/11944836_27) I know nothing about the content of this but if you want a comprehensive overview of the area, this is maybe a starting point.


