Let $T$ be a consistent axiomatizable theory extending $\mathbf{Q}$. Let $P^+$ be the set of (code numbers for) sentences provable from $T$; let $P^-$ be the set of (code numbers for) sentences disprovable from $T$. Show that there is no recursive set $R$ such that both $P^+ \subset R$ and $R \cap P^- = \emptyset$.
Hint: suppose otherwise. Since $R$ is recursive there is then a $\exists$-rudimentary formula $F(x)$ that defines $R$ in $\mathbf{Q}$. Try to apply the diagonal lemma.
Let's start with the hint. We have some $\exists$-rudimentary formula $F(x)$ that defines $R$ in $\mathbf{Q}$ such that $a \in R \leftrightarrow \vdash_Q F(a)$.
We will use the diagonal lemma on the negation of $F$ such that there exists some sentence $G$:
\begin{align*}
\vdash_T G \leftrightarrow \lnot F(\ulcorner G \urcorner) \\
\end{align*}
Suppose $G$ is correct. Then $F(\ulcorner G \urcorner)$ is not correct, therefore $\ulcorner G \urcorner \not\in R$, therefore $\ulcorner G \urcorner \not\in P^+$, therefore $G$ is not provable from $T$.
Suppose $G$ is not correct. Then $F(\ulcorner G \urcorner)$ is correct, therefore $\ulcorner G \urcorner \in R$, therefore $\ulcorner G \urcorner \not\in P^-$, therefore $G$ is not disprovable from $T$.
These aren't contradictions. $T$ isn't complete, so $G$ can be correct but not provable or not correct but not disprovable.
$\exists$-rudimentary sentences are correct if and only if they can be proven from $\mathbf{Q}$. If $G$ were $\exists$-rudimentary this would yield the contradiction. But $G$ isn't necessarily $\exists$-rudimentary.
Any hints on what to try next?
BTW, this is the same question as the following. But the top answer seems wrong since I don't think we can assume that $G$ is logically equivalent to some $\exists$-rudimentary sentence.
Best Answer
The definition you are using for "$F(x)$ defines $R$ in $Q$" is wrong. What you want is that if $a\in R,$ then $\vdash_Q F(\mathbf a),$ and if $a\notin R$, then $\vdash_Q\lnot F(\mathbf a).$
Then we can argue as follows:
If $G$ is provable in $T$, then $\ulcorner G\urcorner\in P^+,$ so $\ulcorner G\urcorner\in R.$ Thus, we have $\vdash_Q F(\ulcorner G\urcorner)$ and then $\vdash_T\lnot G,$ so $T$ is inconsistent.
If $G$ is not provable in $T,$ then neither is $\lnot F(\ulcorner G\urcorner),$ and this implies $\lnot F(\ulcorner G\urcorner)$ is not provable in $Q.$ Thus, $\ulcorner G\urcorner\in R,$ and it follows that $\vdash_Q F(\ulcorner G\urcorner)$ and so $\vdash_T \lnot G.$ Thus $\ulcorner G\urcorner\in P^-,$ which is impossible since it is in $R.$
Note, we didn't actually have to use the fact that $F$ was $\exists$-rudimentary here.