# Definability of ordinals in various signatures

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.

• Ehrenfeucht studied this, perhaps verifying your conjecture on $\omega^\omega$ for order and adding one more $\omega$ to the tower for addition. See Vaught’s overview, link.springer.com/chapter/10.1007/3-540-63246-8_1 Aug 19 '20 at 2:17
• Thanks! Do you think if I extended his results I could publish a paper on it, or does that not seem paper worthy? Aug 19 '20 at 4:41
• The standard for publication is usually saying something new and interesting. It'd be hard to meet that standard with just questions that Ehrenfeuct might have pondered and the now-standard techniques that he developed in the 50's. For publishable results, you'd probably have to build instead on some of the papers published in that vein more recently. Aug 19 '20 at 5:34
• I was given the impression that Ehrenfeucht’s work was all that was done on this area, so extending it would already be saying something new and interesting. Are there more recent papers that you didn’t mention that I’d have to build on? Aug 19 '20 at 9:59
• For the signature $\{<\}$, see mathoverflow.net/questions/35971 , particularly the paper of Doner, Mostowski, and Tarski cited there. Aug 24 '20 at 2:51

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, the details here are all correct but I think the conclusions have some issues.