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

Question

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

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