Let $T$ be a complete extension of ZF. Is there an algorithm for extending $T$ to a complete extension of NBG? E.g., if $T$ is the complete theory of some $M \models ZF,$ is the complete theory of $\text{Def}(M)$ Turing reducible to $T?$ I think this is impossible by some sort of undefinability of truth argument, yet I can't come up with anything that can be done in $\text{Def}(M)$ which clearly cannot be simulated in $M.$

  • 2
    $\begingroup$ A trivial comment: it's crucial that we talk about extensions, since the Turing degrees of completions of ZF are exactly the Turing degrees of completions of NBG - that is, every completion $T_0$ of ZF computes a completion $T_1$ of NBG, and this is even uniformly true. Of course, this all turns into nonsense once we demand $T_0\subseteq T_1$ ... $\endgroup$ May 18, 2018 at 4:18
  • $\begingroup$ @NoahSchweber Do you happen to know a reference for that? $\endgroup$
    – Farmer S
    May 2, 2021 at 13:54
  • $\begingroup$ @FarmerS This is just the general fact that any completion of $\mathsf{ZF}$ (or even $\mathsf{PA}$, or $\mathsf{I\Sigma_1}$, or ...) computes completions of every computably axiomatizable theory. See "PA degree." $\endgroup$ May 2, 2021 at 16:45
  • $\begingroup$ @NoahSchweber Oh, thanks - I realize now I think I didn't read your comment properly - I was imagining it was saying that for every completion $T_0$ of ZF, there is some completion $T_1$ of NBG which is Turing equivalent to it... $\endgroup$
    – Farmer S
    May 2, 2021 at 16:50
  • $\begingroup$ @FarmerS I believe that's true too, and again has nothing to do with the specific theories involved: that for every computably axiomatizable consistent theory $T$ interpreting $\mathsf{PA}$, the degrees of completions of $T$ are precisely the degrees of completions of $\mathsf{PA}$. $\endgroup$ May 2, 2021 at 16:53

1 Answer 1


Work with enough background theory that we have compactness. Then there is no such algorithm, in the strong sense, that if $T^+$ is any complete consistent extension of NBG and $T\subseteq T^+$ its ZF part, then $T^+$ is not Turing reducible to $T$, and in fact, the set of $\Sigma_1^2$ sentences in $T^+$ is not Turing reducible to $T$ (I'm not sure on the standard notation, but by $\Sigma^2_1$ I mean formulas of form $\exists C_1,\ldots,C_n\varphi(C_1,\ldots,C_n)$ where the $C_i$'s are class variables and $\varphi$ is any formula without class quantifiers). For otherwise there is indeed an undefinability of truth argument, as you suspected: Suppose there is such a Turing reduction, given by the $e$th Turing program in oracle $T$. Fix a recursive enumeration $\left<\varphi_k\right>_{k<\omega}$ of all ZF sentences. We formally consider the oracle $T$ as its characteristic function $\chi^T:\omega\to\{0,1\}$ with respect to this enumeration. Given whatever set $S$ of ZF sentences, let $\chi^S$ be its characteristic function with respect to this enumeration also. If the program $e$ in oracle $\chi^S$ run on input $x$ only queries the oracle regarding sentences of complexity at most $\Sigma_n$, say that the run has support $\leq n$. Also fix a recursive enumeration $\left<\Phi_n(v)\right>_{n<\omega}$ of all $\Pi^2_1$ NBG formulas in a single free set-variable $v$, and no free class variables.

Now fix a model $M^+$ of $T^+$, and let $M$ be its universe of sets (note $M$ might be illfounded; in particular $\omega^M$ might be illfounded). Then note there is a $\Sigma_1^2$ formula $\Psi$ such that $M^+\models\Phi_n(k)$ iff $M^+\models\Psi(n,k)$, for each $n,k<\omega$ (where $\omega$ denotes the true $\omega$, and we take $\omega\subseteq\omega^M$ as usual). (That is, $\Psi(n,k)$ basically says "there is some integer $i$ and a $\Sigma_i$-satisfaction relation $T_i$ (for first order truth over $M$) such that the $e$th Turing program with oracle $(\chi^{T_i})^M$, run on input (the code for) $\neg\Phi_n(k)$, converges with support $\leq i$, with the output that $\Phi_n(k)$ is true". Note here that this is all stated in the sense of $M,M^+$, so the "integer" $i$ is ostensibly illfounded and $(\chi^{T_i})^M:\omega^{M}\to\{0,1\}$ uses $M$'s natural version $\left<\varphi^M_k\right>_{k<^M\omega^M}$ of the enumeration of $\left<\varphi_k\right>_{k<\omega}$, etc, but of course these things agree with what is computed outside when restricted to standard integers. Note that (for $n,k<\omega$) it doesn't matter whether the witness $i$ is standard or non-standard, since the computation actually only has support $\leq$ some standard integer.)

But now we can do the usual diagonalization: Let $\Phi(v)$ be the formula $\neg\Psi(v,v)$ (a $\Pi^2_1$ formula), and let $d<\omega$ be such that $\Phi_d(v)=\Phi(v)$. Then $M^+\models\Phi_d(d)$ iff $M^+\models\neg\Psi(d,d)$ iff $M^+\models\neg\Phi_d(d)$.


You must log in to answer this question.

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