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

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?

• The second paragraph seems false. The subsets of $\omega$ in $L_{\omega_1^{CK}}$ are precisely the hyperarithmetic sets. Famously, Harrison showed that there are pseudowellorderings: recursive orderings of $\omega$ that are not wellfounded but have no hyperarithmetic descending sequences. – François G. Dorais Apr 12 '16 at 23:09
• I was unaware of Harrison's result. This is great to know. Thanks! – Kameryn Williams Apr 13 '16 at 17:04

## 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_{ 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.

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.
• By "$R$ is well-founded" I mean that every nonempty subset of the domain of $R$ has a minimal element. As you explained, the rank function characterization of well-foundedness doesn't have a hope of always working in every $L_\alpha$. I've edited my question to more accurately reflect what I'm asking, in light of your and François's comments about the Harrison order. – Kameryn Williams Apr 13 '16 at 17:20
• Ah, that makes a lot of sense. Thanks! On a minor note, I think your side note in the edit is incorrect. Well-foundedness is absolute for transitive models of ZFC, since it is a $\Delta_1$ property for models of ZFC. – Kameryn Williams Apr 14 '16 at 19:43