9
$\begingroup$

The goal of this question is to fill in the gap in this old answer of mine.

For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation used in the linked answer above, but on reflection I like it more, and to the best of my knowledge there is no standard notation):

  • $\mathsf{Def}(M)$ is the supremum of the ordertypes of the well-orderings which are (first-order, with parameters) interpretable in $M$.

  • $\mathsf{Ad}(M)$ is the height of the smallest admissible set with $M$ as an element.

Per the title, each of these can be thought of as a kind of "$\mathsf{Ord}$'s $\omega_1^{CK}$." Classically, $\omega_1^{CK}$ is defined as the smallest ordinal with no computable copy but is also the supremum of the definable well-orderings of $(\mathbb{N};+,\times)$ and the smallest admissible ordinal $>\omega$.

It's not hard to show that $\mathsf{Def}(A)\le\mathsf{Ad}(A)$ for all $A$, and equality does occur for some $A$ (e.g. $\mathsf{Ad}(L_\omega)=\mathsf{Def}(L_\omega)=\omega_1^{CK}$). However, $\mathsf{Def}(A)<\mathsf{Ad}(A)$ is also possible. The above-linked answer shows that we have $\mathsf{Def}(M)<\mathsf{Ad}(M)$ whenever $M\models\mathsf{ZFC}$ and $M^\omega\subseteq M$. My question is whether this closure condition is in fact needed:

Is there any transitive $M\models\mathsf{ZFC}$ with $\mathsf{Def}(M)=\mathsf{Ad}(M)$?

Note that since the definitions of $\mathsf{Def}$ and $\mathsf{Ad}$ are sufficiently simple, it's enough to ask whether there is a countable such $M$.

$\endgroup$

1 Answer 1

3
+200
$\begingroup$

Every ordinal $α$ that is the least ordinal satisfying a given $Σ^1_1$ property (about $α$, equivalently, about $L_α$) is a Gandy ordinal, so $\mathsf{Def}(L_α)=\mathsf{Ad}(L_α)$. This includes the least $L_α$ satisfying ZFC, and even includes the least $L_α$ with $α$ an inaccessible cardinal in $L_{α^{+\text{CK}}}$ (but using $L_{α^{+\text{CK}}+1}$ would fail).

The proof of being Gandy is analogous to the proof of existence of recursive pseudowellorderings. Consider a theory $S$ including $\mathrm{ATR}_0$ and "ordinal $α$ satisfies a given $Σ^1_1$ property", with definable Skolem functions. Let $T$ be the tree of (essentially) finite partial $α$-models (as in $ω$-models) of $S$: A sequence of ordinals $<α$   $x_1,x_2,...,x_n$ is in $T$ iff there is no inconsistency proof shorter than $n$ for "$S$, symbols $x_1,x_2,...,x_n$, ordering of $x_1,x_2,...,x_n$, and $∃y<α \, φ(y) ⇒ φ(x_{⌈φ⌉})$ for the first $n$ one-variable formulas $φ$" ($⌈φ⌉$ is the Gödel number; $x_n$ is not used if $⌈φ⌉≤n$). Then the Kleene–Brouwer order of $T$ has a well-ordered initial segment of length $α^{+\text{CK}}$. The existence of the desired model ensures that the order is ill-founded, while its nonexistence in $L_{α^{+\text{CK}}}$ (since per assumption, $α$ is the least ordinal with the $Σ^1_1$ property, and we use $\mathrm{ATR}_0$) ensures that the well-founded length equals $α^{+\text{CK}}$.
In fact (not needed here), there is a recursive order-invariant linear order $f$ on $ℚ^{<ω}$ such that for all $α$ that are the least ordinal for some $Σ^1_1$ property, the initial well-founded portion of $f↾α^{<ω}$ has length $α^{+\mathrm{CK}}$ (by order invariance it does not matter how $α$ is order-preservingly embedded into $ℚ$). The construction is to interleave separate partial models as above for all variations of the theory $S$, except that we can skip variations at the cost of choosing a higher branch.

A related result is that for every finite $n$, $\mathsf{Def}(L_α)=\mathsf{Ad}(L_α)$ for the minimum $α$ such that $L_α$ satisfies ZFC and is correct about well-foundedness of $\mathbf{Σ}_n^{L_α}$ relations. The proof is as above except that we require that the partial models are correct about $Σ_{n+1}^{L_α}$ properties of the ordinals. This way a resulting model is correct about well-foundedness of relevant relations, and hence cannot be shorter than $α$.

As an aside, the results may seem surprising since working in ZFC or NBG, we can develop a theory of proper class well-orderings, and using replacement, failure of well-foundedness would be witnessed as a set. By diagonalization, increasing descriptive complexity gives strictly longer proper class well-orderings (at least for parameter-free complexity or if $V=HOD$), with 'longer' interpreted using embeddability into proper initial segments (which makes sense even though I think not all first-order definable class well-orderings are comparable using first-order definable classes). And for extensions of ZFC (including the replacement schema) using infinitary logic or constructible hierarchy above $V$, the increase in well-ordering lengths continues transfinitely with even the supremum of $L_\mathrm{Ord}(V)$ well-orderings not reaching the height of $\mathsf{Ad}(V)$ (assuming correctness about well-foundedness). But as soon as replacement (for countable sequences) fails (which presumably it would not for the 'true' $V$), in some cases, the supposed well-orderings may turn out to be an illusion.

$\endgroup$
1
  • $\begingroup$ Your construction of $T$ looks pretty similar to the proof of GIrard's $\beta$-completeness proof, which generates an $\alpha$-preproof of a theory whose infinite branch can be thought as a countable partial $\alpha$-models (a many-sorted model with a type for ordinals, and the ordinal part of the model is a countable subset of $\alpha$.) $\endgroup$
    – Hanul Jeon
    Commented Jun 13 at 7:51

You must log in to answer this question.

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