Skip to main content
Elaborated answer
Source Link
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. 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.)

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

Source Link
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.