The set of $\Delta_1$ indices

Question

Is the set of Godel numbers of $\Delta_1$ formulae itself $\Delta_1$ definable (i.e., computable)?

Answer 1

The answer is no, in either of the cases Trevor outlined.

For example, for a fixed $e$, consider the formulas $p(x)\equiv$"There is some $n$ such that $\Phi_e(x)[n]\downarrow=1$" and $q(x)\equiv$"There is some $n$ such that $\Phi_e(x)[n]\downarrow=0$." These formulas are both $\Sigma^0_1$, and they define complementary sets if and only if $\Phi_e$ is a total $\lbrace 0, 1\rbrace$-valued function. So if the set of indices for pairs of $\Sigma^0_1$-formulas defining complementary sets was $\Delta^0_1$, we'd have that the set of indices for total $\lbrace 0, 1\rbrace$-valued functions is computable, which is a clear contradiction.

Something similar will work in the other case Trevor described. The basic idea is that the set of indices of pairs of $\Sigma^0_1$-formulas which PA (say) proves are complementary is c.e. (just search through proofs) but not computable. To flesh that out, for $e$ a natural number, consider the $\Sigma^0_1$-formulas $p_e(x)\equiv$"$x\not=x$" (defining $\emptyset$) and $q_e(x)\equiv$"$\exists s(e\in W_{e, s}\vee x=2)$." These formulas are complementary iff $e\in W_e$, and moreover are complementary iff PA proves that they are complementary (I guess I'm assuming soundness of PA here, but that's not a huge assumption to make). But if the indices for PA-provably complementary $\Sigma^0_1$-formulas were $\Delta^0_1$, we could use the above setup to compute the set of $e$ such that $e\in W_e$ - i.e., the Halting Problem. So the answer is again no. (Note that the only properties of PA that are being used here are soundness, and the fact that it is sufficiently strong to express and prove basic facts about c.e. sets.)