Skip to main content
1 of 2
Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331

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.

Noah Schweber
  • 20.5k
  • 10
  • 110
  • 331