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?

  • 5
    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
up vote 5 down vote accepted

I think it depends what the OP means by "thinks is well-founded." If $L_\alpha$ is admissible and $W\in L_\alpha$ is a linear order, then $W$ is (genuinely) well-founded iff in $L_\alpha$ there is an order-preserving bijection between $W$ and some ordinal; that is true.

If this is the sense in which you mean "thinks is well-founded," then the answer to your question is yes, non-admissible levels can be wrong about well-foundedness. Let $W$ be a well-ordered computable relation on $\omega$ with ordertype, say, $\epsilon_0$; then no ranking function exists for $W$ in $L_\gamma$ for $\gamma<\epsilon_0$, simply because there aren't enough ordinals in such $L_\gamma$, but a copy of $W$ appears already in $L_{\omega+1}$! (Proof: computable = $\Delta^0_1$ $\subseteq$ arithmetic.) In general, the appearance of long well-orderings is "sudden," in contrast with the corresponding ranking functions (which at least have to wait until there are enough ordinals).

In fact, without too much effort this argument shows that for any nonadmissible $\alpha$, $L_\alpha$ is not correct about well-foundedness in the above sense. EDIT: Specifically, we can show that if $\alpha$ is admissible, then for every $\gamma<\alpha^+$ (the next admissible above $\alpha$) there is a well-ordering of order-type $\gamma$ which is in $L_{\alpha+1}$.

On the other hand, there are $W$ where no such rank function exists, yet $L_\alpha$ doesn't see a descending sequence in $W$, such as the Harrison order. So if "thinks is well-founded" you mean "sees no descending sequence through," then even admissible $L_\alpha$ are not correct about well-foundedness.


EDIT: The answer to your modified question is still yes, for basically the same reason I mentioned above. Let $\xi$ be such that $L_\xi$ is correct about well-foundedness. Then in $L_{\xi+1}$ there is a Harrison-type ordering - that is, a non-well-founded ordering which does not have any infinite descending sequences in $L_{\xi^+}$. So $L_{\xi+1}$ is not correct about well-foundedness. Actually, any successor level of $L$ will not be correct about well-foundedness.

  • 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
  • @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. – Noah Schweber Apr 13 '16 at 17:27
  • 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
  • @KamerynWilliams Quite right, fixed (I was thinking about nonstandard models :P) – Noah Schweber Apr 14 '16 at 19:56

Your Answer

 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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