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!


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.

  • $\begingroup$ 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. $\endgroup$ – Benedict Eastaugh Jan 1 '13 at 23:36
  • $\begingroup$ Benedict, the ambiguity is everywhere. The superscripts in my answer and Eran's should also have been 0. I'll edit my answer. $\endgroup$ – Andreas Blass Jan 1 '13 at 23:53
  • $\begingroup$ 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$. $\endgroup$ – Andreas Blass Jan 2 '13 at 0:00
  • $\begingroup$ 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. $\endgroup$ – 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$.)

  • $\begingroup$ 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. $\endgroup$ – Benedict Eastaugh Jan 1 '13 at 23:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.