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.

2more comments