Must $L_\alpha$ be correct about well-foundedness?

Question

If $R \in L_\alpha$ is a binary relation so that $L_\alpha$ thinks $R$ is well-founded, must $R$ truly be well-founded? (Edit) That is, if $L_\alpha$ thinks that every nonempty subset of the domain of $R$ has a least element, is the same true in $V$?

(Edit) If $L_\alpha$ satisfies a sufficiently strong fragment of $\mathsf{ZFC}$, then the answer is yes because then $L_\alpha$ can build a rank function from $R$ into its ordinals and thus an ill-foundedness in $R$ would give rise to an ill-foundedness in $\mathrm{Ord}$, which is impossible. But if $L_\alpha$ does not have rank functions for all well-founded relations then it only has access to the $\Pi_1$ characterization of well-foundedness. It is conceivable in this case that $L_\alpha$ could be wrong about well-foundedness, that it has a relation which it wrongly believes to be well-founded.

For comparison, Zermelo set theory (= $\mathsf{ZFC}$ minus Replacement and Foundation) has transitive models which are wrong about well-foundedness. The problem with these models is that they fail to have enough ordinals to capture the ordertype of every well-order.

That these bad models exist is an easy consequence of a theorem by Harvey Friedman.

Theorem (H. Friedman, 1973): Fix a countable admissible set $A$. Consider $T$, a theory extending $\mathsf{KP}$ in the infinitary logic $L_A$ which has a model containing $A$ and is $\Sigma_1$-definable over $A$. Then there is an ill-founded $M \models T$ so that the ordinals of the well-founded part of $M$ are exactly the ordinals of $A$ and the well-founded part of $M$ contains $A$.

To build these bad models of Zermelo set theory, consider the theory consisting of $\mathsf{KP}$ plus the assertion that $V_{\omega + \omega}$ exists. This theory has models containing your favorite countable admissible set, which let's say is $L_{\omega_1^{CK}}$. Let $M$ be the model Friedman's theorem produces when applied to this theory and admissible set and consider $N = V_{\omega+\omega}^M$. Then $N$ is transitive, since everything in $N$ has rank far less than $\omega_1^{CK}$, and $N$ agrees with $M$ about well-foundedness. Take any countable "ordinal" from the ill-founded part of $M$ and you can find an isomorphic copy, call it $R$, which is a subset of $\omega^2$ and hence in $N$. Then, $N$ wrongly thinks $R$ is well-founded.

This argument won't answer the question for non-admissible $L_\alpha$s. Any well-order in $L_\alpha$ must have ordertype less than the least admissible $\beta > \alpha$ as otherwise $L_\beta$ would see an isomorphic copy of its ordinals in an initial segment of itself. If we tried to run a variation of the above argument to produce an ill-founded $M$ with $L_\alpha$ in its well-founded part, we would have that the well-orders in $L_\alpha$ have ordertype in the well-founded part of $M$. As such, we cannot by this means produce an $L_\alpha$ which is wrong about well-foundedness.

(Edit) As pointed out by François and Noah, admissibility isn't sufficient to make $L_\alpha$ correct about well-foundedness. The particular case I'm interested in is when $\alpha$ is the successor of an ordinal whose corresponding fragment of $L$ is correct about well-foundedness.

Question: (Edit) Is there $\xi$ so that $L_\xi$ satisfies enough of $\mathsf{ZFC}$ to be correct about well-foundedness but $L_{\xi+1}$ is wrong about well-foundedness?

Answer 1

Coming back to this years later I've just noticed that my original answer was massively flawed; I've corrected it now. The issue is essentially that I took it for granted that all admissible sets look like $L_{\omega_1^{CK}}$ more than they actually do - see e.g. here.

The exact relationship between correctness about well-foundedness and closure properties of ordinals depends what is meant by "thinks is well-founded." (I'll restrict attention to linear orders as opposed to general partial orders for simplicity here.) I'll consider two notions: isomorphisms with ordinals and non-existence of descending sequences.

---

Isomorphisms with ordinals

The most well-behaved interpretation is via ordinals. Classical a linear order is a well-order iff it is isomorphic to an ordinal; so, for what levels of $L$ does this hold as well?

The nice thing about this correctness property - which I'll call weak wf-correctness - is that it can't yield false positives: if $L_\alpha\models R\cong\gamma$, then $R$ really is a well-ordering. The interesting issue is false negatives.

It turns out that every admissible ordinal is weakly wf-correct. This is a neat application of external induction. Suppose $R\in L_\alpha$ is a well-ordering and every proper initial segment of $R$ is isomorphic to some ordinal via an isomorphism in $L_\alpha$. Then for each $x$ in the domain of $R$, there is a unique ordinal $\gamma_x<\alpha$ such that there is an isomorphism between $R_{<x}$ and $\gamma$ in $L_\alpha$; this means that the map $x\mapsto \gamma_x$ is $\Sigma_1$. Since $R\in L_\alpha$ we may apply $\Sigma_1$-replacement to get $\sup\{\gamma_x:x\in dom(R)\}\in L_\alpha$ and so the ordertype of $R$ is some ordinal $\lambda<\alpha$. The set $g=\{\langle x,\gamma_x\rangle: x\in dom(R)\}$ yields an isomorphism $R\cong\lambda$ and is in $L_\alpha$ since it is a $\Delta_1$-over-$L_\alpha$ subset of $dom(R)\times\lambda$.

The converse, interestingly, fails badly: we can have an $\alpha$ such that $L_\alpha$ is weakly wf-correct but is not admissible. The simplest way to see this is to note that there are non-admissible limits of admissibles (e.g. $\sup_{i\in\omega}\omega_i^{CK}$, which is annoyingly sometimes called "$\omega_\omega^{CK}$"). However, there are even stronger examples: e.g. letting $\theta$ be the next admissible above $\omega_1$, we have that $(i)$ for every limit ordinal $\beta<\theta$ the supremum of the ordertypes of the $\beta$-recursive well-orderings is $<\theta$ and $(ii)$ $cf(\theta)=\omega_1$, so combining these facts we can get a weakly wf-correct ordinal strictly between $\omega_1$ and $\theta$ - in particular, this ordinal is not a limit of admissibles either.

---

Non-existence of descending sequences

The other obvious correctness notion here is "sees a descending sequence in:" say that $L_\alpha$ is strongly wf-correct if for each ill-founded linear order $R\in L_\alpha$ there is a descending sequence through $R$ in $L_\alpha$.

Here we get the opposite situation: even admissible ordinals need not be strongly wf-correct! The classic example of this is $\omega_1^{CK}$: there are computable linear order (the Harrison orders) which are ill-founded but have no hyperarithmetic descending sequence. (FWIW, each of these is of the form $\omega_1^{CK}(1+\eta)+\mu$ where $\eta$ is the ordertype of the rationals and $\mu<\omega_1^{CK}$.)

On the other hand, it turns out that any ill-founded linear order in an admissible set $L_\alpha$ does have a descending sequence in the next admissible set since quantifying over initial segment isomorphisms in $L_\alpha$ is bounded at that point. This means that every limit of admissibles is strongly wf-correct, so there are non-admissible strongly wf-correct ordinals.

---

Now what about your final question?

The construction of Harrison orders does relativize to some levels of $L$. Specifically, suppose $L_{\zeta+1}\models$ "$L_\zeta$ is countable." Then there is an ill-founded linear order in $L_{\zeta+1}$ with no descending sequence in $L_\xi$, where $\xi$ is the next admissible above $\zeta$. Extracting an appropriate theory (e.g. a small fragment of KP + "Every set is contained in an admissible set) gives an affirmative answer to your question.

If you're willing to go one level higher, though, things get much cooler. Suppose $L_\alpha$ is pointwise-definable. Then there is a bijection between $L_\alpha$ and $\omega$ in $L_{\alpha+2}$, and so again a la Harrison there is an ill-founded linear order in $L_{\alpha+2}$ with no descending sequence in the next admissible above $L_\alpha$. The point is that pointwise-definable levels of $L$ exist which have very strong theories - e.g. the least level of $L$ satisfying ZFC is pointwise-definable!

I don't know if the above works with merely "$+1$," however.