Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 4 down vote accepted

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.

share|cite|improve this answer
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$.)

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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