# Is there an algorithm for extending a complete set theory to one with classes?

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.$

• 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$ ... May 18, 2018 at 4:18
• @NoahSchweber Do you happen to know a reference for that? May 2, 2021 at 13:54
• @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." May 2, 2021 at 16:45
• @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... May 2, 2021 at 16:50
• @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}$. May 2, 2021 at 16:53

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)$$.