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

  • $\begingroup$ By $\Delta_1$ formula, do you mean a pair of $\Sigma_1$ formulas that define complementary sets, or a pair of $\Sigma_1$ formulas that are proved to define complementary sets by some theory (e.g., PA)? (I'm pretty sure the answer is no in both cases.) $\endgroup$ – Trevor Wilson Aug 11 '12 at 16:11
  • $\begingroup$ I'm happy to work with either of those definitions. $\endgroup$ – neophyte neologican Aug 11 '12 at 16:46

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


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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