Heights of models

From Cantor's Attic
(Redirected from ZFC-P)
Jump to: navigation, search

The smallest heights of transitive models of theories can often be large ordinals. If the theory is first-order, consistent and has an infinite model, the least such height must be countable by the Lowenheim-Skolem theorem, so here we don't discuss uncountable models of theories. If we have a first-order theory \(T\) that's consistent with \(V=L\), we have $T\not\vdash V\neq L$, so by Godel's completeness theorem there is some model \(M\) of \(T\) that satisfies $V=L$. The model $M$ is then a rank $L_\xi$ of $L$ for some ordinal $\xi$.

The smallest transitive models of theories with larger consistency strength usually have larger heights than the smallest transitive models of weaker (by consistency strength) theories, because every model $M$ of the stronger theory usually contains transitive models of the weaker theory, their height is of course less then $\mathrm{Ord}^M$ (the smallest height countable, i.e. less then $\omega_1^M$) and a transitive model in a transitive model is a transitive model. However, this is not always the case even for "natural" theories, for example the least ordinal $\delta$ such that $L_\delta\vDash\omega-\Pi_3^0\textrm{-DET}$ is less than the height of the minimal model of $Z_2$ even though $Z_2$ is proof-theoretically weaker than $\omega-\Pi_3^0\textrm{-DET}$.<ref>A> Montalbán, R. Shore, The Limits of Determinacy in Second Order Arithmetic: Consistency and Complexity Strength (2013, p.8). Accessed 6 August 2022.</ref>

Ordering these ordinals

In some cases, we want to prove \(T\not\vdash``\exists\alpha(L_\alpha\vDash T)\!"\) for a first-order theory \(T\). Since first-order set theories are sound, from \(\) (expand this).

Also, when comparing the models of first-order theories $T_1$ and $T_2$, we may see if $\forall(\varphi\in T_2)(T_1\vdash\varphi)$, i.e. if $T_1$ proves all of $T_2$'s axioms. Then by Godel's completeness theorem, all models of $T_2$ must satisfy all of $T_1$'s axioms as well. This allows us to translate consistency strengthWrong term? of theories to size of models.

If the theory is first-order and consists of (in Dmytro Taranovsky's words) "arbitrary sufficiently satisfiable axioms", the height of its smallest transitive model must be less than the least stable ordinal (a more precise characterization of such theories is given in [W. Marek, K. Rasmussen, "Spectrum of L"], proposition 0.7.)

KP variants

Heights of models of KP are called admissible. Just considering ranks of $L$, some extensions of KP, such as KP augmented by the Σ1-separation schema, have larger heights of their models. From the logic above, a level $L_\xi$ that's a model of KP+Σ1-sep. is nonprojectible (although the restriction to ranks of $L$ is important here: without $V=L$, there are shorter models of KP+Σ1-sep. https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/abs/locally-countable-models-of-1separation/28D83F60A5B1D067E7726C464BD78A66). We can also consider models of subsystems of $Z_2$.

Here is a list of some conditions that heights of models have (assuming $L_\alpha\vDash\textrm{V=HC}$):

  • $L_\alpha\cap\mathcal P\omega\vDash\Pi_1^1\textrm{-CA}_0$(1.) when $\alpha$ is a limit of admissibles. [1]
  • $L_\alpha\cap\mathcal P\omega\vDash\Delta_2^1\textrm{-CA}_0$(1.) iff $\alpha$ is recursively inaccessible. [2]
  • For $0<n<\omega$, $L_\alpha\vDash\Sigma_n\textrm{-coll.}$ iff "$\alpha$ is $\Pi_{n+1}$-reflecting on $\{\beta\in\alpha:L_\beta\prec_{\Sigma_{n-1}}L_\alpha\}$" [3]
  • For $0<n<\omega$, $L_\alpha\vDash\Sigma_n\textrm{-sep.}$ iff $L_\alpha\cap\mathcal P\omega\vDash\Sigma_{n+1}^1\textrm{-CA}_0$(1.) iff "$\{\beta\in\alpha:L_\beta\prec_{\Sigma_n}L_\alpha\}$ unbounded in $\alpha$" [4]
    • (Note that the analytical hierarchy's $\Sigma^1_{n+1}$ appears connected to the Levy hierarchy's $\Sigma_n$ in this respect - this may be due to interpretations of set theory in arithmetic with similar connections [5]Lemma 8.9)
  • $L_\alpha\vDash\textrm{Full replacement}$ iff $L_\alpha\cap\mathcal P\omega\vDash\textrm{Comprehension schema}$ iff $(L_{\alpha+1}\setminus L_\alpha)\cap\mathcal P\omega=\varnothing$ [6]

ZFC without the powerset axiom

Heights of models of ZFC without the powerset axiom are given in MarekSrebrny73. One of the main results (theorem 2.7) is that $L_\alpha \models \mathrm{ZFC}^- + V=\mathrm{HC}$ iff $\alpha$ starts a gap, i.e. $\alpha$ is a gap ordinal (\((L_{\alpha+1} - L_\alpha) \cap \mathcal{P} (\omega) = \varnothing\)), but $\forall_{\beta \in \alpha} (L_\alpha - L_\beta) \cap \mathcal{P} (\omega) \neq \varnothing$. ($\mathrm{HC}$ is the class of hereditarily countable sets.)

Elementary substructures have some of these model-theoretic properties: if $L_\alpha\prec L_\beta$ and $\alpha\in\beta$, then $L_\alpha\vDash\textrm{ZFC}^-$. [1]Lemma 4.9

The latter result will also hold for these:

ZFC- plus some cardinals

In $L$, $L_{\omega_{\alpha+1}}$ are uncountable transitive models of ZFC-P (or $\mathrm{ZFC^-}$, ZFC without the power-set axiom) plus "$\omega_\alpha$ exists", so applying Lowenheim-Skolem downward, there must be also countable transitive models of such theories. This argument works in models of ZFC-P too, so the smallest height $\beta_1$ of a model of ZFC-P plus "$\omega_{\alpha_1}$ exists" must be countable in $L_{\beta_2}$, the minimal model of ZFC-P plus "$\omega_{\alpha_2}$ exists", for $\alpha_1<\alpha_2$: $\beta_1 < \omega_1^{L_{\beta_2}}$.

Counterintuitively, there's no guarantee that $\omega_1^{(L_\alpha)}=\omega_1^{(L_\beta)}$ implies $\alpha=\beta$. [7]

Cardinals within these models have some properties:

  • Sacks <ref>G. Sacks: Higher Recursion Theory, (p.161).</ref> left as an exercise that \(\alpha\) and \(\beta\) with \(\alpha\) admissible, \(L_\alpha\vDash``\beta\textrm{ is a cardinal} >ω\!"\) implies \(L_\beta\prec_{\Sigma_1}L_\alpha\) (see stable for related substructure conditions).
  • If $(L_{\beta^+}\setminus L_\beta)\cap\mathcal P(\omega)=\varnothing$, then $L_{\beta^+}\vDash``\omega_1\textrm{ exists}\!"$, and in fact $(\omega_1)^{L_{\beta^+}}=\beta$. [8]
    • Localizing this, there can exist $\theta$ such that $L_\beta\vDash\exists\theta\exists p(p=\aleph_1^{L_\theta}\land\theta\textrm{ is not admissible})$. [1 (p.149)].
    • We can restrict $p$ even further: let $E(p)$ be the closure of $p\cup\{p\}$ under a certain extension of primitive recursion functions to transfinite ordinals. Then there can exist $\theta$ such that $L_\beta\vDash\exists\theta\exists p(p=\aleph_1^{L_\theta}\land L_\theta=E(p)\land\theta\textrm{ is not admissible})$. [9]

ZF and ZFC

The height of the minimal model of ZFC is greater than some weakened variants of stability, such as the least (+1)-stable, the least inaccessibly-stable, and the least nonprojectible. However, it's less than the least stable ordinal. [2] Also, the minimal transitive model of ZFC is pointwise definable. <ref>J. D. Hamkins, D. Linetsky, J. Reitz "Pointwise Definable Models of Set Theory" (p.6)</ref>

David and Friedman have given a characterization of $\textrm{ZF}$-spectra, and in the $\kappa=\omega$ case we get countable spectra. The characterization includes cardinals $\beta$ where $L_\alpha\vDash``\beta\textrm{ is regular}\!"$ [10]

Beyond the least stable

Because of how the least stable ordinal is greater than the heights of models of many first-order theories, it's more difficult to go past. One way to pass it would be to use second-order set theories - here, the Lowenheim-Skolem theorem isn't guaranteed to hold, so we may have second-order theories that have no countable models.

We can also impose restrictions on our models, such as looking at heights of $\beta_n$-models of second-order arithmetic, i.e. models $M$ of second-order arithmetic such that $M\prec_{\Sigma_n^1}\mathcal P(\omega)$, to go beyond the least stable ordinal.[1] (This is an extension of the concept of \(\beta\)-model, the latter of which was introduced by Mostowski. (Girard, Part III\[\Pi_2^1\]-Logic, 198?, p.206))

  • (The first ordinal that is not $\Delta^1_n$ is called $\delta_n$.)in section 0
  • $\delta_2$, the least stable ordinal,Theorem 3.1 is not a gap ordinal before Corollary 2.9
  • Any $\beta_2$-model of "second-order arithmetic+arithmetic form of axiom of constructibility" is of the form $L_\alpha\cap\mathcal P(\omega)$ for some stable gap ordinal $\alpha$ (K. Apt, W. Marek, Second-order arithmetic and related topics, p.209, p.216)
  • Τhere is a stable gap ordinal below $\delta_3$Corollary 2.9 and $\delta^L=\bigcup_{n \in \omega} \delta_n^L$ is a stable gap ordinal.Fact 3.5 d
  • If $\alpha$ is a stable gap, then $\alpha$ is the $\alpha$th stable ordinal.Lemma 4.14
  • Existence of a minimal $\beta_3$-model of second-order arithmetic is equiconsistent with existence of a Ramsey cardinal (K. Apt, W. Marek, Second-order arithmetic and related topics, p.219, p.216)

In a step down in strength, the $\beta_0$-models of $Z_2$ are exactly the $\omega$-models of $Z_2$ (W. Marek, Observations concerning elementary extensions of $\omega$-models. II, lemma 1.a), and these are also related to admissible ordinals:


  1. Note: Since ZFC proves all axioms of PA hold in $\omega$[ citation needed ], adding the full second-order induction schema to the theory doesn't change this result since each $L_\alpha\cap\mathcal P\omega$ is an $\omega$-model. So we get $(L_\alpha\cap\mathcal P\omega\vDash\Pi_n^1\textrm{-CA}_0)\rightarrow(L_\alpha\cap\mathcal P\omega\vDash\Pi_n^1\textrm{-CA})$, etc.


  1. Marek, W. Stable sets, a characterization of $\beta_2$-models of full second order arithmetic and some related facts. Fundamenta Mathematicae 82(2):175-189, 1974. www   bibtex
  2. Madore, David. A zoo of ordinals. , 2017. www   bibtex
Main library