7
$\begingroup$

Inspired by this question, I've been trying to figure out for myself the basic properties of definable class well-orderings in transitive models $M$ of ZFC: What is $\omega_1^{CK}(\mathsf{Ord})$?

There were a couple things I couldn't figure out.

  1. Is it necessarily the case that $M$ is correct about well-orderings? I.e., if $M \models ``\varphi(\cdot, \cdot)$ is a total ordering of $Ord" \wedge \forall x(x=\emptyset \vee \exists y \in x(\forall z \in x(\varphi(y, z)))),$ then $\varphi$ truly (in $V$) defines a well-ordering of $Ord^M?$
  2. If $\varphi_1$ and $\varphi_2$ define in $M$ isomorphic well-orderings of $Ord^M,$ is there necessarily a definable isomorphism $\psi(\cdot, \cdot)$ between them? E.g., if $\alpha$ is the first ordinal to exceed a proper class of ordinals under $\varphi_1$ and $\beta$ is the first such ordinal under $\varphi_2,$ then we would have $\psi(\alpha, \beta).$

(1) is easy to prove in the case $Ord^M$ has uncountable cofinality in $V,$ but it isn't obvious to me whether it can fail in models of countable cofinality height. (2) seems unlikely, since I don't really see how to extend transfinite recursion past the ordinals (especially in light of potential failures of (1)), but I have trouble imagining what a counterexample would like.

$\endgroup$

2 Answers 2

3
$\begingroup$

The answer to the second question is also no. Let $Ω = Ord^M$. There are two $(Δ^V_2)^M$ well-orderings of length $Ω^ω$ that are not isomorphic by an $M$ formula with parameters. $Ω^ω$ is the smallest such ordinal as comparability of well-orderings $<Ω^n$ can be defined by recursion on $n$.

The proof is analogous to that of existence of non-arithmetically isomorphic computable well-orderings of length $ω^ω$. Each point will encode a first-order formula with ordinal parameters in such a way that an isomorphism to $Ω^ω$ would give the truth predicate for $M$ with ordinal parameters (which is not definable in $M$ from parameters).

We set up a well-ordering such that by induction on the complexity of the formulas, the interval corresponding to a $Σ^V_{n+1}$ or $Π^V_{n+1}$ formula (or in ZF, $Σ^V_n(P)$ or $Π^V_n(P)$ where $P$ is power set) has length $Ω^n$ if the formula is true and $<Ω^n$ otherwise. In ZF an arbitrary formula is equivalent to a formula of the form $∃α_1 ∀β_1 ∃α_2 ∀β_2 ... φ$ for a $Δ^V_1(P)$ $φ$ monotonic in $α_i$ and anti-monotonic in $β_i$. For this, we can replace $∃s \, ψ(s)$ with $∃α ∃s∈V_α ψ(s)$ and note that using replacement $∃s∈V_α$ can be moved inside an anti-monotonic $∀β$, and we analogously handle $∀s \, ψ(s)$. Our well-ordering for $∃α_1 ∀β_1 ∃α_2 ∀β_2 ... φ$ will be the class of $(α_1,β_1,α_2,β_2,...)$ (under lexicographic order) satisfying $φ$. By the monotonicity and the anti-monotinicty, the induction works. Finally, we can combine the constructions for all first-order formulas with ordinal parameters into a well-ordering embeddable (in $M$) into $Ω^ω$, using fillers such that the constructions do not interfere with each other.

I suspect that in GBC (aka NBG; this includes global choice), for a class well-ordering $S$, comparability of suborderings of $Ord^S$ (ordinal exponentiation) is equivalent to elementary transfinite recursion on $S$ (note: each level of transfinite recursion can be a proper class). Fix a global well-ordering, and for every limit $s∈S$, fix $s_α$ cofinal in $s$ of length $≤Ord$. For transfinite recursion, at a limit step $s$, it suffices to handle $∀α \, φ_{s_α}$. For this, we replace $φ_{s_α}$ with $∀β≤α \, φ_{s_β}$, and handle all $β$ in parallel to shortcircuit the expansion once some $φ_{s_β}$ fails, but I did not confirm that it works (it does for $s=ω$). Next, we may have $∃x∈X \, ∀α \, φ_{s_α}(x)$, which we can handle by enumerating all $x$ (or sequences of $x$ if we are tracking multiple possibilities), and (if needed to prevent overflows) for each $x$ repeat the encoding of $∀α \, φ_{s_α}(x)$ $Ord$ times.

In GBC, comparability of all proper class well-orderings is implied by elementary transfinite recursion along proper class well-orderings, which in turn is equivalent to determinacy of clopen proper class games. See Open determinacy for class games by Gitman and Hamkins. Also note a parallel with $\text{ATR}_0$.

To Hamkins answer for the first question, I will add that the least $δ$ with $L_δ⊨\text{ZFC}$ is a Gandy ordinal, that is there is a $δ$-recursive ill-founded linear order without a $δ$-hyperarithmetic (i.e. $L_{δ^{+,\mathrm{CK}}}$) infinite descending sequence. We can even arrange here for that order to be on $δ^{<ω}$ with comparison between $s$ and $t$ in $δ^{<ω}$ computable from the ordering of the ordinals in $s$ and $t$. The construction is based on a tree searching for an $ω$ model of KP + $∃δ \, L_δ⊨\text{ZFC}$ with the model ordinals $<δ$ using actual ordinals $<δ$.

$\endgroup$
9
$\begingroup$

The answer to question 1 is that no, a transitive model $M$ can be wrong about whether a definable class relation is a well-order.

To see this, consider a transitive model $M$, and let me assume that there is no worldly cardinal in $M$. For example, perhaps we have cut off the universe at the smallest worldly cardinal.

By the reflection theorem, we know that for any given $n$, there are many ordinals $\theta$ in $M$ with $V_\theta^M\prec_{\Sigma_n} M$. In particular, we can make an increasingly elementary chain $$V_{\theta_0}^M\prec_{\Sigma_1} V_{\theta_1}^M\prec_{\Sigma_2}\cdots\prec_{\Sigma_n} V_{\theta_n}^M\prec_{\Sigma_{n+1}}\cdots$$ that unions up to $M$.

Let $T$ be the tree of all finite sequences that obey this increasingly elementary substructure relation with one another, and where also the $n^{th}$ element in the sequence also models the $\Sigma_n$ fragment of ZFC. It follows from our observation above that there are a proper class of such instances in $M$, and so $T$ is a proper class. Elements of $T$ amount to finite sequences of ordinals, which can be coded by single ordinals, and so we may view $T$ as a partial order relation on $\text{Ord}$, if you like.

We order this tree growing downward, and I claim it is well-founded in $M$. That is, $M$ has no $\omega$-sequence that is a descending sequence in this tree, because the union of that chain would be a $V_\theta$ that models ZFC, and so $\theta$ would be worldly, but we assumed there are none in $M$.

So $M$ thinks this tree order is well-founded, and therefore it thinks the Kleene-Brouwer order on the tree is a well-order. But $M$ is wrong about both of these things, since we have already observed that $M$ is the union of an increasingly elementary chain, and this is exactly a descending sequence in the tree order and hence a descending sequence in the Kleene-Brouer order.

So $M$ thinks the relation was a well-order, but it was mistaken.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .