# Ordinals definable over $L_\kappa$

Suppose $\kappa$ is an uncountable cardinal, with $L_\kappa$ an admissible set (i.e. a model of Kripke–Platek set theory). Let $<_\gamma \subseteq \kappa \times \kappa$ denote a wellordering of $\kappa$ (equivalently, of $L_\kappa$) such that $\mathrm{ot}(<_\gamma) = \gamma$.

What is the least ordinal $\delta$ such that $<_\delta$ is not first order definable (i.e. in $\mathcal{L}_\in$) over $L_\kappa$?

Variations on this question include:

• What is least such ordinal when we consider $L_\alpha$ for any admissible $\alpha$?
• How is the answer affected by restricting definability, e.g. to $\Delta^0_1$, or strengthening it to $\mathcal{L}^2_\in$?
• This is all parameter-free, does allowing parameters substantially change the answer?

I'm afraid I don't know much about $L$ or admissibility so these may be naïve questions, sorry!

## 2 Answers

Eran has answered the main question and (in parentheses) the variation concerning admissible $\alpha$ rather than only uncountable cardinals, but you also asked about a couple of other variations. Restricting to $\Delta^0_1$ definitions makes no difference, once you have a $\Sigma^0_1$ definition, since $\xi<_\gamma\eta$ if and only if $\xi,\eta<\gamma$ and $\eta\not<_\gamma\xi$ and $\xi\neq\eta$; this gives a $\Pi^0_1$ definition of $\xi<_\gamma\eta$ if you plug in a $\Sigma^0_1$ definition of $\eta<_\gamma\xi$.

As far as parameters are concerned, $<_\kappa$ is definable without parameters in $L_\kappa$, and therefore $<_\delta$ will also be definable without parameters in $L_\kappa$ whenever $\delta<\kappa$ and $\delta$ is definable without parameters in $L_\kappa$. On the other hand, if $\delta$ is not definable without parameters, then neither is $<_\delta$. More generally, any parameters that suffice to define $\delta$ also suffice to define $<_\delta$ and vice versa.

• Thanks for this, Andreas. $\Delta_1$ is ambiguous, sorry—I meant $\Delta^0_1$, i.e. recursive. I've amended my question to clarify this. – Benedict Eastaugh Jan 1 '13 at 23:36
• Benedict, the ambiguity is everywhere. The superscripts in my answer and Eran's should also have been 0. I'll edit my answer. – Andreas Blass Jan 1 '13 at 23:53
• Now that I re-read the question, I see that the answers have missed the point. You want to know about definable well-orders of $\kappa$ of order type greater than $\kappa$. I believe that such well-orders exist for order-types up to but not including the next admissible ordinal after $\kappa$, and that this is the case whether you allow arbitrary first-order definitions or restrict to $\Delta^0_1$. – Andreas Blass Jan 2 '13 at 0:00
• Yes, that's right—sorry for asking what seems to have been a rather unclear question. I'm interested in what the equivalent to arithmetical transfinite recursion would be in the admissible setting, hence the question about definable wellorderings. – Benedict Eastaugh Jan 2 '13 at 0:06

A good reference is K. Devlin Constructibilty, Lemma 3.1 and the following discussion, where he proves a $\Sigma^1_1$ well ordering of $L$ (but it can be adapted to admissible $L_k$). So for all $\delta \lt \kappa$ $\lt_\delta$ is definable with parameters in $L_\kappa$ (and this cannot be done for $\delta \gt \kappa$ as $\delta \notin L_\kappa$.)

• Consider $<_\delta \in L_{\kappa + 1}$ such that $\delta > \kappa$. Are any such wellorderings definable, i.e. by a formula $\varphi \in \mathcal{L}_\in$ such that $x <_\delta y \Leftrightarrow \varphi(x, y)$? This would be analogous to the definitions of recursive ordinals in arithmetic. – Benedict Eastaugh Jan 1 '13 at 23:58