8
$\begingroup$

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?

| cite | improve this question | | | | |
$\endgroup$
  • 5
    $\begingroup$ 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. $\endgroup$ – François G. Dorais Apr 12 '16 at 23:09
  • $\begingroup$ I was unaware of Harrison's result. This is great to know. Thanks! $\endgroup$ – Kameryn Williams Apr 13 '16 at 17:04
6
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Kameryn Williams Apr 13 '16 at 17:20
  • $\begingroup$ @KamerynWilliams See my edits. The answer is still yes - the key fact being that we can always construct Harrison-type orders "relative" to any admissible set. $\endgroup$ – Noah Schweber Apr 13 '16 at 17:27
  • $\begingroup$ 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. $\endgroup$ – Kameryn Williams Apr 14 '16 at 19:43
  • $\begingroup$ @KamerynWilliams Quite right, fixed (I was thinking about nonstandard models :P) $\endgroup$ – Noah Schweber Apr 14 '16 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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