6
$\begingroup$

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 2

5

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.

  • 0
    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.2013-01-02
5

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$.)

  • 0
    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.2013-01-01