5
$\begingroup$

Consider the progression of larger and larger countable ordinals ($\omega$, $\omega^{\omega}$, $\epsilon_0$, the Veblen hierarchy, etc., described nicely here).

On the one, hand, it seems clear that the smaller countable ordinals (e.g. $\omega$, $\omega 2$, $\omega^2$) will exist in any $\omega$-model of $\mathsf{ZF}$. On the other hand, I would assume that (depending on what specific model you're working in) if you continue this progression far enough, eventually you may hit countable ordinals that don't exist in every such model.

Hence the question (with respect to $\omega$-models of $\mathsf{ZF}$): Where exactly is the "boundary" between the countable ordinals that exist in every model and the "extra large" (so to speak) countable ordinals that exist in some models but not others?

$\endgroup$

1 Answer 1

5
$\begingroup$

The ordinals that are standard in every $\omega$-model of $\text{ZF}$ are precisely the elements of $\omega_1^{CK}$, the Church-Kleene ordinal.

What is $\omega_1^{CK}$?

$\omega_1^{CK}$ is defined as the supremum of all computable ordinals, where a computable ordinal is an ordinal whose ordering relation is isomorphic to a computable ordering on a computable subset of $\mathbb{N}$. Since there are only countably many computable subsets of $\mathbb{N}$ and only countably many computable orderings on each of them, $\omega_1^{CK}$ is a countable ordinal. The ordinal $\omega_1^{CK}$ is larger than every ordinal mentioned in the article you linked; in other words, every ordinal mentioned in that article is computable. In fact, every ordinal that is the proof-theoretic ordinal of some theory is computable. So, $\omega_1^{CK}$ is, in a sense, larger than any ordinal we can describe by "arithmetic means."

Why are the elements of $\omega_1^{CK}$ standard in every $\omega$-model of $\text{ZF}$?

The elements of $\omega_1^{CK}$ are precisely the computable ordinals. So, we have to prove that every computable ordinal is standard in every $\omega$-model of $\text{ZF}$. In fact, we can prove that every computable ordinal is standard in any $\omega$-model of $\text{KP}+ \text{Inf}$ (a theory weaker than $\text{ZF}$). This fact is proved as Corollary 5.3 in these course notes, and its proof relies on the fact that the sets of natural numbers in $L_{\omega_1^{CK}}$ are precisely the hyperarithmetic ones. This is important because the hyperarithmetic sets are the ones that can be "built up" from the natural numbers in a certain constructive way.

Is this bound sharp?

In other words, is there an $\omega$-model of $\text{ZF}$ in which $\omega^{CK}_1$ is non-standard? Well, the existence of any model of $\text{ZF}$ is independent from $\text{ZF}$ by Gödel's Incompleteness Theorem. However, if we assume that $\text{ZF}$ does have an $\omega$-model, then, yes, there does exist such an $\omega$-model.

The course notes that I linked above only treat $\omega$-models of $\text{KP}+ \text{Inf}$, but a version of the argument used there can be applied to the case of $\text{ZF}$ or $\text{ZFC}$. The proof relies on the Gandy basis theorem (Theorem 3.1 in the linked course notes), which says that every nonempty $\Sigma^1_1$ set has a hyperlow element. If you don't know what $\Sigma^1_1$ and hyperlow mean, just know that every $\Sigma^1_1$ set has a sufficiently simple description and that the hyperlow sets are those that cannot compute any ordinals beyond $\omega_1^{CK}$.

It turns out that the set of countable $\omega$-models of $\text{KP}+ \text{Inf}$ (or $\text{ZF}$ or $\text{ZFC}$) forms a $\Sigma^1_1$ set. If we assume that this set is non-empty, then there exists a hyperlow $\omega$-model of $\text{KP}+ \text{Inf}$ (or $\text{ZF}$ or $\text{ZFC}$). It follows that this model cannot compute any ordinals beyond $\omega_1^{CK}$.

$\endgroup$
7
  • 1
    $\begingroup$ In the paragraph about the bound being sharp, note that the consistency of "there exists an $\omega$-model of ZF" is higher than simply "there exists a model". $\endgroup$
    – Asaf Karagila
    Jul 11, 2023 at 9:38
  • $\begingroup$ @AsafKaragila My mistake! Just fixed it. $\endgroup$ Jul 11, 2023 at 11:29
  • $\begingroup$ This “standardness” of ordinals seems(?) to mean something different than “standardness” of a model (the latter meaning that the model’s membership relation is the “true” $\in$ of the universe). But from the notes you linked to, it appears(?) that the concepts of “standard” vs “non-standard” ordinals and “standard” vs “non-standard” parts of a model are somehow related to well-foundedness of the model. If the model is well-founded, are all its ordinals “standard”? If so, how does the answer change if one narrows the original question to focus only on well-founded models? $\endgroup$
    – NikS
    Jul 12, 2023 at 7:22
  • $\begingroup$ @NikS Let $(M,E)$ be a model of $\text{ZF}$ (or some other similar theory). We say that $(M,E)$ is well-founded iff $E$ is a well-founded relation. We say that $(M,E)$ is standard iff $E$ agrees with $\in$ on $M$. We say that $(M,E)$ is transitive iff $(M,E)$ is standard and $M$ is a transitive set. We say that an ordinal $\alpha \in M$ is standard iff $E$ restricted to $\alpha$ is a well-founded relation. Every standard model is well-founded, and every ordinal in a well-founded model is standard. $\endgroup$ Jul 12, 2023 at 14:50
  • $\begingroup$ So, given that all ordinals of a well-founded model are standard, does the preceding imply that there exists a well-founded model of $\mathsf{ZF}$ in which all the ordinals are elements of $\omega_{1}^{CK}$? If not, how does the answer to the original question change if the question is narrowed to pertain only to well-founded models of $\mathsf{ZF}$? $\endgroup$
    – NikS
    Jul 13, 2023 at 1:28

You must log in to answer this question.

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