10
$\begingroup$

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?

$\endgroup$
8
  • 8
    $\begingroup$ 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. $\endgroup$ Jun 7, 2018 at 9:43
  • 1
    $\begingroup$ @PhilipWelch Could you elaborate on the illfounded ordering of $L_{\omega_1^{ck}}$? I'm not sure where it comes from. $\endgroup$ Jun 7, 2018 at 12:52
  • 1
    $\begingroup$ 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! $\endgroup$
    – Asaf Karagila
    Jun 7, 2018 at 14:38
  • 1
    $\begingroup$ @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).) $\endgroup$ Jun 7, 2018 at 19:35
  • 1
    $\begingroup$ Related: mathoverflow.net/questions/236041/… $\endgroup$ Oct 19, 2022 at 16:17

1 Answer 1

9
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ Is the Friedman Lemma being applied to ZFC? Wouldn't this mean you are assuming the existence of a transitive model of ZFC? $\endgroup$ Jul 12, 2023 at 8:09
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 14, 2023 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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