7
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • $\begingroup$ 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 $\endgroup$
    – user44143
    Commented Aug 19, 2020 at 2:17
  • $\begingroup$ Thanks! Do you think if I extended his results I could publish a paper on it, or does that not seem paper worthy? $\endgroup$
    – exfret
    Commented Aug 19, 2020 at 4:41
  • 1
    $\begingroup$ 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. $\endgroup$
    – user44143
    Commented Aug 19, 2020 at 5:34
  • $\begingroup$ 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? $\endgroup$
    – exfret
    Commented Aug 19, 2020 at 9:59
  • 2
    $\begingroup$ For the signature $\{<\}$, see mathoverflow.net/questions/35971 , particularly the paper of Doner, Mostowski, and Tarski cited there. $\endgroup$
    – Andreas Blass
    Commented Aug 24, 2020 at 2:51

1 Answer 1

Reset to default
6
+50
$\begingroup$

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.

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, 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. I know nothing about the content of this but if you want a comprehensive overview of the area, this is maybe a starting point.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .