Let $L_\alpha$ be some admissible level of the constructible hierarchy and $M \supseteq L_\alpha$ an extension of $L_\alpha$. I am looking for conditions under which $M \simeq L_\beta$. It is not enough to ask that $M$ be an end elementary extension of $L_\alpha$ as $M$ may not be well-founded.

However I suspect that this may be provable when $M$ is an $\mathcal{A}$-elementary end extension of $L_\alpha$ for some fragment $\mathcal{A}$ of infinitary logic $L_{\omega_1 \omega}$. In the general case, well-orderdness is not definable in $L_{\omega_1 \omega}$ but here we also have the structure of $L_\alpha$ to help us.

The idea is to do as follows to show that $M$ is well-founded:

  1. In $M$ we can define ordinals as hereditarly transitive sets and they are well-founded by foundation.
  2. Then we can define by $\Sigma$-recusion (here we need $\alpha$ to be admissible and likely even $L_\alpha$ to be a model for infinitary $KP$) a predicate $L(x, \alpha)$ defined as: \begin{align*} L(x, \alpha+1) &\longleftrightarrow \bigvee_{n \in \omega} \bigvee_{\varphi} \exists p_1, \ldots, p_n \, \forall y \in x (L(y, \alpha) \wedge \varphi(y, p_1, \ldots, p_n)) \\ L(x, \alpha) &\longleftrightarrow \exists \beta \in \alpha \, L(x, \beta) \text{ for } \alpha \text{ limit} \end{align*} With it, we define $L_\alpha = \left\{ x \mid L(x, \alpha) \right\}$.
  3. With this definition, the two following infinitary sentences are true in $L_\alpha$ (observe that the second sentence is not usually true when $L(x, \alpha)$ is defined in the finite setting using rudimentary functions instead of the definibality predicate) : \begin{align*} \begin{cases} \forall x \, \exists \alpha \, x \in L_\alpha \\ \forall \alpha \, (x \in L_\alpha \implies \forall y \in x \, \exists \beta \in\alpha \, y \in L_\beta) \end{cases} \end{align*}
  4. Those two sentences can be reflectd in $M$ by $\mathcal{A}$-elementarity and with those, any infinite decreasing sequence $a_0 \ni^M a_1 \ni^M a_2 \ldots$ would yield an infinite decreasing sequence of ordinals $\alpha_0 \ni^M \alpha_1 \ni^M \alpha_2 \ldots$ which in turn would contradict the fact that ordinals are well-founded w.r.t. $\in^M$.

Now: do we need $L_\alpha$ to be a model for $KP$ for infinitary logic for the definition by recursion? And is there a more direct argument to show this?

  • 1
    $\begingroup$ If $\mathcal A$ is a countable fragment and $\alpha$ is a countable ordinal, then by $\mathbf{\Sigma}^1_1$-boundedness, either there is an illfounded $\mathcal A$-elementary end extension of $L_\alpha$ or the $\beta < \omega_1$ such that $L_\beta$ is an $\mathcal A$-elementary extensions of $L_\alpha$ are bounded below $\omega_1$. So it seems there must be something wrong with your argument (or mine, I guess). I haven't looked closely at your argument though. $\endgroup$ Commented May 18, 2023 at 16:10
  • $\begingroup$ Should the definition of $L(x,\alpha+1)$ instead be something along the lines of $L(x,\alpha+1)\leftrightarrow\bigvee_{n\in\omega}\bigvee_{\varphi}\exists p_1,\ldots,p_n \, \forall y(y\in x\leftrightarrow (L(y,\alpha)\land\varphi(y,p_1,\ldots,p_n)))$, with a $L(p_1,\alpha)\land\ldots\land L(p_n,\alpha)$ restriction and comprehension for $y$? As is currently written, if $L(x,\alpha+1)$ there does not seem to be anything forbidding $L(x',\alpha+1)$ where $x'$ is an arbitrary subset of $x$. $\endgroup$
    – C7X
    Commented Feb 15 at 10:25
  • 1
    $\begingroup$ Yes you're right. Which makes the definition actually $\Sigma_2$ and so we can't use $\Sigma$-recursion. Thanks, that explains the contradiction with Gabe Goldberg comment. $\endgroup$
    – Johan
    Commented Feb 21 at 18:16
  • $\begingroup$ @Johan I was also going to write an answer mentioning that well-foundedness is not expressible in $L_{\omega_1\omega}$ (according to this comment it is not even expressible in $L_{\infty\omega}$) and attempting to produce an $M$ whose ordinals are non-well-founded, however if $\Sigma$-recursion does not apply, is it still worth writing? $\endgroup$
    – C7X
    Commented Mar 4 at 3:13
  • 1
    $\begingroup$ Hi @C7X, sorry I forgot to answer your last comment. I think the error you pointed out plus the theoretical limitation that Gabe Goldbard suggested already builds a good case against what I was trying to do. Maybe you could add their observation in your answer for the sake of completeness? $\endgroup$
    – Johan
    Commented Mar 21 at 10:09

1 Answer 1


(Turning some comments into an answer)

The definition of $L(x,\alpha+1)$ was wrong, instead it should have been $$L(x,\alpha+1)\leftrightarrow\bigvee_{n\in\omega}\bigvee_{\varphi}\exists p_1,\ldots,p_n \, \forall y(y\in x\leftrightarrow (L(y,\alpha)\land\varphi(y,p_1,\ldots,p_n)))$$, and as this is not $\Sigma_1$, $\Sigma$-recursion is not applicable with the corrected definition.

Additionally, from step #1 on, the argument is dependent on stating an axiom of foundation in $\mathcal L_{\omega_1\omega}$ such that $M$ satisfying the axiom means that even just the ordinals of $M$ are externally well-ordered. But Karp ("Finite-Quantifier Equivalence", in The Theory of Models, J. Addison, L. Henkin, and A. Tarski (eds.), 1965) and Lopez-Escobar ("On Defining Well-Orderings, Fundamenta Mathematicae vol. 59, 1966) showed that external well-orderedness is not definable in $\mathcal L_{\omega_1\omega}$ nor in $\mathcal L_{\kappa\omega}$ for any cardinal $\kappa$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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