5
$\begingroup$

For any model of $M$ of ZFC, we can extend it to a model $M_{ew}$ with an "externally well-founded" predicate $ew$. For $x \in M$, We say that $M_{ew} \vDash ew(x)$ when there is no infinite sequence $y_n \in M$ such that $\dots \in_M y_2 \in_M y_1 \in_M y_0 \in_M x$.

My question is how to axiomatize the following theory:

$$T = \{\phi : \forall M. \text{$M$ is a computably saturated model of ZFC implies $M_{ew} \vDash \phi$} \}$$

Every theorem of $T$ without the $ew$ predicate is true in every computably saturated model of ZFC, and therefore in every model of ZFC (since every model is elementarily equivalent to a computably saturated one). Thus by Gödel's completeness theorem, the theorem is true in ZFC, and thus $T$ is conservative over ZFC.

However, $T$ is more the same as ZFC. For example, "there is a natural number greater than every externally well-founded natural number" is a theorem.

(Note ironically that there are models of $T$ with elements that satisfy $\text{ew}$ but aren't actually externally well-founded, of course.)

To make the question more precise, here's what would constitute an "acceptable" axiomatization. It should consist of a finite number of "axiom schema", where each axiom schema is generated from a formula with class variables. Axioms are generated by replacing the class variables with definable classes and then taking the universal closure. Each class variable may have restrictions on what symbols are allowed in the definition of the class that get substituted for them. (ZFC is acceptably axiomatized in this sense.)

$\endgroup$
20
  • 5
    $\begingroup$ $ew(x)$ iff $x$ is in $V_n$ for some standard $n\in\omega$, right? So the theory is definitionally equivalent to the, perhaps simpler, theory where you add a predicate for standard natural numbers instead of ew. $\endgroup$ Commented May 30 at 17:45
  • 3
    $\begingroup$ I only now read the last paragraph. The theory is certainly not axiomatizable by finitely many schemata, as it is not recursively axiomatizable: it includes true arithmetic (interpreted by restriction of the usual operations on $\omega$ to the new predicate). $\endgroup$ Commented May 30 at 19:59
  • 2
    $\begingroup$ Emil, perhaps you might post an answer, since that observation shows that there can be no easy characterization of this theory. Can we show that the theory exceeds $0^{(\omega)}$ in complexity? Or perhaps equivalent. $\endgroup$ Commented May 30 at 23:02
  • 2
    $\begingroup$ @JoelDavidHamkins In any case, if the observation "the theory is not recursive axiomatizable as it includes true arithmetic" were the whole answer, this would not be a research-level question, and the appropriate course of action would be to vote to close it, not to post an answer. $\endgroup$ Commented May 31 at 5:54
  • 3
    $\begingroup$ @EmilJeřábek Since countable computably saturated models $M$ of ZF are precisely those countable models of ZF that are (1) $\omega$-nonstandard and (2) have an expansion to a satisfaction class $S$ such that $(M,S)$ satisfies Tarski's clauses for each standard formula, and (M,S) satisfies replacement in the extended language, it appears that the theory asked about can be obtained as the set-theoretical consequences of the modification of the theory you formulated (using the $\omega$-rule), by changing ZFC to ZFC + S is a satisfaction class (as a scheme). $\endgroup$
    – Ali Enayat
    Commented May 31 at 11:23

1 Answer 1

6
$\begingroup$

Observe that if $M\models\def\zfc{\mathrm{ZFC}}\zfc$ has nonstandard $\omega$, then $x\in M$ is externally well founded iff its rank $\rho(x)$ is a standard natural number: this follows easily by iterating the observation that if $\rho(x)=\sup\{\rho(y)+1:y\in x\}$ is infinite or nonstandard, then $\rho(y)$ is infinite or nonstandard for some $y\in x$ as well. Thus, $T$ is definitionally equivalent with a similarly defined theory where we have a predicate $\def\N{\mathbb N}\N(x)$ for standard natural numbers in place of ew. I will henceforth assume $T$ is formulated in this way.

Assuming ZFC is consistent, the theory $T$ cannot be axiomatized by finitely many schemata, as it is not recursively axiomatizable. In fact, it is $\Pi^1_1$-complete. On the one hand, given a $\Pi^1_1$ sentence of the form $\forall X\,\phi(X)$ where $\phi$ is arithmetical, we have $$\N\models\forall X\,\phi(X)\iff T\vdash\forall X\subseteq\omega\,\phi^\N(X),$$ where $\phi^\mathbb N$ denotes the relativization of all quantifiers in $\phi$ to the $\N$ predicate (in particular, this means that the formula can only query $x\in X$ for $x\in\N$, thus the quantifier over $X\subseteq\omega$ really quantifies over subsets of $\N$ coded in the model). For the left-to-right implication, if $M$ is any model of ZFC, and $X\in M$, then $M\models\phi^\N(X)$ iff $\N\models\phi(X\cap\N)$ (identifying standard natural numbers with the corresponding elements of $M$); thus, if $\N\models\forall X\,\phi(X)$, then also $M\models\forall X\subseteq\omega\,\phi^\N(X)$. For right-to-left, if $\N\not\models\phi(X)$ for some $X\subseteq\N$, then using compactness and the consistency of ZFC, there is a recursively saturated $M\models\zfc$ that contains an $X'$ such that $X'\cap\N=X$, thus $M\models T\land\neg\phi^\N(X')$.

On the other hand, $T$ is complete wrt models $(M,\N)$ where $M$ is a countable recursively saturated model of ZFC. Such a model $M$ and its satisfaction predicate can be encoded by a subset $S\subseteq\N$, and it is easy to see that the property “$S$ is a satisfaction predicate of a recursively saturated model $M$ of ZFC that $(M,\N)\models\phi$” is arithmetical. Thus, $T$ is $\Pi^1_1$.

Nevertheless we can describe $T$ in some nontrivial ways. First, by the usual completeness theorem for $\omega$-logic, the theory of models $(M,\N)$ where $M\models\zfc$ can be axiomatized by $\let\ob\overline\zfc+\{\N(\ob n):n\in\N\}+{}$the $\omega$-rule $$\dfrac{\phi(\ob0),\phi(\ob1),\phi(\ob2),\dots}{\forall x\,(\N(x)\to\phi(x))},$$ where $\ob n$ denotes the numeral for $n$ (the usual definition of $n$ in the language of ZFC).

In order to generalize this to $T$, we can use the idea from a comment by Ali Enayat: let $\zfc^U$ denote the extension of $\zfc$ in a language with a new predicate $U(x)$, and axioms ensuring that $U$ is an unbounded class of ordinals $\alpha$ such that $(V_\alpha,{\in})$ is an elementary substructure of the universe w.r.t. all standard formulas. (The replacement schema is not extended to the new language.) Then $M\models\zfc$ is recursively saturated iff it has nonstandard $\omega$ and it expands to a model of $\zfc^U$: on the one hand, for any ordinal $\beta\in M$, the existence of $\alpha>\beta$ such that $V_\alpha^M\prec M$ follows from recursive saturation, hence we can take for $U$ the set of all such $\alpha$. On the other hand, a recursive type can be coded in a model with nonstandard $\omega$ by some $p\in M$, $p\subseteq\omega$ using overspill; if $\alpha\in U$ is such that all parameters of the type belong to $V_\alpha$, the type is finitely satisfiable in $V_\alpha$, hence using overspill again, a nonstandardly finite part of $p$ is satisfiable, hence the original type is satisfied in $V_\alpha$, and a fortiori in $V$.

Then $T$ consists of all $U$-free sentences provable in $\zfc^U+\{\N(\ob n):n\in\N\}+\exists x\in\omega\,\neg\N(x)+{}$the $\omega$-rule.

$\endgroup$
8
  • $\begingroup$ "let $\def\zfc{\mathrm{ZFC}}\zfc^U$ denote the extension of $\zfc$ in a language with a new predicate $U(x)$, and axioms ensuring that $\omega$ is nonstandard" Does $\zfc^U$'s language also include the $\mathbb N(n)$ predicate? If not, what are the axioms ensuring $\omega$ is nonstandard? $\endgroup$ Commented May 31 at 15:53
  • $\begingroup$ No, it does not yet include $\mathbb N$. But you are right, I can’t do that. I’ll fix it. $\endgroup$ Commented May 31 at 15:56
  • $\begingroup$ Hmm, doesn't the characterization using the $\omega$-rule imply that the theory's complexity is $\Sigma_1^1$ (and thus can't be $\Pi_1^1$-complete)? $\phi$ is a theorem of $T$ with the $\omega$-rule iff there exists a well-ordered countable set and a set of sentences indexed by that set such that each sentence is an axiom of $T$ or follows from previous sentences by the rules of inference and such that $\phi$ is one of those sentences. $\endgroup$ Commented May 31 at 16:12
  • 1
    $\begingroup$ You have hidden an extra universal SO quantifier in “well-ordered”, thus your description is only $\Sigma^1_2$, not $\Sigma^1_1$. You can make it $\Pi^1_1$ if you express it as “$\phi$ belongs to every deductively closed set of formulas closed under the $\omega$-rule”. $\endgroup$ Commented May 31 at 16:16
  • $\begingroup$ A tiny comment: in the theory $T$, we don't need to insist that the replacement scheme is extended (in contrast to the the sibling theory that has a satisfaction predicate) since by using the ZF reflection theorem plus recursive saturation one can bypass the appeal to resplendence to get an expansion to $T$ in the absence of replacement in the extended language (and indeed there is no need for countablity either). I learned this argument from the following 1980 paper of John Schlipf: ams.org/journals/proc/1980-080-01/S0002-9939-1980-0574523-6 $\endgroup$
    – Ali Enayat
    Commented May 31 at 18:50

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