10

The property of well-orderability is upward absolute for transitive models of ZF: by Replacement in the smaller class, specifically Mostowski collapse, this is equivalent to the upward absoluteness of von Neumann ordinals, which holds, by Foundation in the larger class, since the property of being a von Neumann ordinal is captured by the $\Delta_0$ condition "transitive and linearly ordered by membership".

Note that Foundation is already necessary for the corresponding absoluteness result concerning finiteness Is $\omega$ absolute in set theory without foundation?:

Is upward absoluteness true or, perhaps more interestingly, independent in the absence of Replacement?

Adam Epstein
  • 2,440
  • 8
    Upwards absoluteness of WO's fails for transitive models of KP (so Pairing, Union, Inf., Found, with Delta_1-Sep. and Sigma_1-Rep.). This is witnessed by an illfounded ordering in the least transitive KP model: L_{omega_1}^{ck}. But if Sigma_1 Rep. is enhanced to Sigma_2-Rep, then the transitive models here are "beta-models": \Pi^1_1 statements, including thus Wellordering, are absolute between them and V. – Philip Welch Jun 07 '18 at 09:43
  • 1
    @PhilipWelch Could you elaborate on the illfounded ordering of $L_{\omega_1^{ck}}$? I'm not sure where it comes from. – Stefan Mesken Jun 07 '18 at 12:52
  • 1
    I like this question. On first sight, it seems like the answer is "obviously yeah", but then you realize that moving to a larger model, one might have added a new set which witnesses the ill-foundedness. Nice! – Asaf Karagila Jun 07 '18 at 14:38
  • @AsafKaragila Thank you so much! This came to mind several months ago when I was mentally verifying some assertion in whatever I was reading at the time (I think a paper of Joel's). I felt I'd really learned something. – Adam Epstein Jun 07 '18 at 15:02
  • 1
    @StefanMesken: there is an r.e. linear ordering, $R$, of $\omega$, which is thus in $M= L_{\omega_1^{ck}}$, but there are no infinite descending chains through $R$ in $M$. (The wellordered part of $R$ has order type ${\omega_1^{ck}}$ but there is an illfounded part beyond it.). This is exactly as Asaf puts it: we move beyond $M$ and can then find a set which witnesses the illfoundedness of $R$. (The existence of such an $R$: R.O. Gandy: A proof of Mostowski's Conjecture (1960).) – Philip Welch Jun 07 '18 at 19:35
  • And very much like Boffa's example discussed here https://mathoverflow.net/questions/85941/is-omega-absolute-in-set-theory-without-foundation – Adam Epstein Jun 07 '18 at 20:12
  • 1
    Related: https://mathoverflow.net/questions/236041/must-l-alpha-be-correct-about-well-foundedness/236056#236056 – Noah Schweber Oct 19 '22 at 16:17
  • Ah that explains why this argument seemed so familiar to me! – Kameryn Williams Oct 20 '22 at 14:19

1 Answers1

9

Upward absoluteness of well-foundedness fails for transitive models of Zermelo set theory (i.e. with full Separation but no Replacement). That is, you can find $M \subseteq N$ both transitive models of Zermelo so that there's a linear order $L \in M$ which $M$ thinks is a well-order but $N$ sees is ill-founded.

This follows from Theorem 2.2 of Harvey Friedman's 1973 paper "Countable models of set theories" (https://doi.org/10.1007/BFb0066789). Let me state an instance of the theorem suitable for this question.

Let $\alpha$ be a countable admissible ordinal and let $T$ be a theory in the language of set theory which extends KP so that $T$ has a transitive model with $\alpha$ as an element. Then there is an ill-founded model of $T$ whose well-founded part has height exactly $\alpha$.

(Briefly: You can prove this using the Barwise compactness theorem. Doing it for $T$ being ZFC: Let $U$ be a countable model of ZFC with $\alpha \in U$ admissible. Then $A = \mathrm L_\alpha$ is an admissible set. You can cook up a theory $E$ in the infinitary language $\mathcal L_A$ whose models must be end-extensions of $A$ whose well-founded parts have height $\alpha$. (Here, $Y \supseteq X$ is an end-extension if for any $a \in X$ if $Y \models b \in a$ then $b \in X$.) Then $U$ witnesses that $A$-finite fragments of $E$ + ZFC are consistent, and so by Barwise compactness $E$ + ZFC has a model.)

Let $\bar M$ be a model of ZFC obtained from this theorem for countable admissible $\alpha > \omega$. ZFC proves that $\mathrm V_{\omega + \omega}$ is a model of Zermelo set theory, and set $M = {\mathrm V_{\omega+\omega}}^{\bar M}$. In Zermelo, well-foundedness is a $\Pi_1$-property. These are downward absolute among end-extensions. (That's really the same fact that $\Pi_1$-properties are downward absolute among transitive models.) So everything in $M$ which $\bar M$ thinks is well-founded is also thought to be well-founded by $M$. In particular, everything $\bar M$ thinks is a countable ordinal is isomorphic to a linear order on $\omega$ in $M$, which $M$ thinks is a well-order. Fix such a linear order $L$, isomorphic to an "ordinal" $\lambda$ in the ill-founded part of $\bar M$.

Now observe that $M$ is well-founded—because $M$ has height $\omega+\omega < \alpha$ and $\bar M$ is well-founded below $\alpha$. So $M$ is a transitive model of Zermelo which thinks $L$ is a well-order. But $N = \mathrm V_{\omega+\omega}$ sees that actually $L$ is ill-founded. This is because $N$ contains every real and so has a witness to the ill-foundedness of $L$. Thus the desired pair $M \subseteq N$.

  • Is the Friedman Lemma being applied to ZFC? Wouldn't this mean you are assuming the existence of a transitive model of ZFC? – Adam Epstein Jul 12 '23 at 08:09
  • 1
    @AdamEpstein My argument assumed a model of ZFC whose well-founded part contains an admissible ordinal $>\omega$, which is epsilon below having a transitive model. But that was just for convenience. It only takes a finite fragment of ZFC to prove that $V_{\omega+\omega}$ satisfies Z. You can run the same argument with a model $\bar M$ of KP + that finite fragment, and that's good enough to conclude that well-foundedness is not upward absolute for transitive models of Z. And of course ZFC proves the consistence of KP + that finite fragment, so we don't need to go beyond ZFC in consistency. – Kameryn Williams Jul 14 '23 at 16:28