2
$\begingroup$

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?

$\endgroup$
6
  • 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

1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .