MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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.) – Trevor Wilson Aug 11 '12 at 16:11
I'm happy to work with either of those definitions. – neophyte neologican Aug 11 '12 at 16:46
up vote 6 down vote accepted

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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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