Showing that all semirecursive sets are semidefinable I'm working on this problem from Boolos' Computability and Logic:

A set $P$ is (positively) semidefinable in a theory $T$ by a formula $\phi(x)$ if for every $n$, $\phi(\mathbf{n})$ is a theorem of $T$ if and only if $n$ is in $P$.  Show that every semirecursive set is (positively) semidefinable in $\mathbf{Q}$ and any $\omega$-consistent extension of $\mathbf{Q}$.

$\mathbf{Q}$ is Boolos' version of Robinson arithmetic.
My intended proof is something like this: let $P$ be a a semirecursive set.  Then there is a recursive relation $R$ such that $P(x)$ iff $\exists y\,R(x,y)$.  Now $R$ is definable in $\mathbf{Q}$ by an $\exists$-rudimentary formula $\psi(x,y)$, and $\exists y\,\psi(x,y)$ is arithmetically equivalent to a $\exists$-rudimentary formula $\phi(x)$.
Does this correctly connect the dots from $P(n)$ to $\phi(\mathbf{n})$, and back again?  If so, where does $\omega$-consistency enter in?
 A: A semirecursive set $P$ is one such that there is a Turing machine $T$ that accepts on input $n$ if and only if $n\in P.$ The expression “T accepts on input $n$” is a $\Sigma_1$ (what the book calls “$\exists$-rudimentary”) formula $\varphi(n)$. The theory about $Q$ and recursive functions implies $Q$ proves every true $\Sigma_1$ sentence, so if $n\in P,$ then $Q\vdash \varphi(\mathbf n).$
Where $\omega$-consistency comes in is in showing the other direction. If $n\notin P$ and nonetheless $T\vdash \varphi(\mathbf n),$ then $T$ proves a false $\Sigma_1$ sentence, i.e. it proves there exists a number satisfying a $\Delta_0$ property when in fact non exists. (I don’t recall the book’s jargon for $\Delta_0$... it’s the one where all quantifiers are bounded.) Since $T$ extends $Q$, it can disprove every false $\Delta_0$ sentence. So $T$ is $\omega$-inconsistent.
A: Let $P$ be a semirecursive one-place relation.  By definition, $P(x)\leftrightarrow \exists x R(x,y)$ for some recursive relation $R$.  Now every recursive relation is definable in $\mathbf{Q}$ by an $\exists$-rudimentary formula (Boolos: Theorem 16.16).  Since $\exists$-rudimentary formulas are preserved under unbounded existential quantification (Boolos: Lemma 16.9), $P$ is arithmetically definable by an $\exists$-rudimentary formula $\phi(x)$.  That is, $P(n)$ iff $\phi(\mathbf{n})$ is true in the standard interpretation of arithmetic.  Since an $\exists$-rudimentary sentence $\phi(\mathbf{n})$ is true (in the standard interpretation of arithmetic) iff it is a theorem of $\mathbf{Q}$, we have $\mathbf{Q}\vdash\phi(\mathbf{n})$ iff $P(n)$, so $P$ is semidefinable in $\mathbf{Q}$.
Now we must expand this result to a theory $T$ which is an extension of $\mathbf{Q}$.  We must show that $T\vdash\phi(\mathbf{n})$ iff $P(n)$.


*

*If $P(n)$ is true, then $\mathbf{Q}\vdash\phi(\mathbf{n})$, so
$T\vdash\phi(\mathbf{n})$ since $T$ extends $\mathbf{Q}$.

*If $T\vdash\phi(\mathbf{n})$ and $\neg P(n)$, then
$\mathbf{Q}\not\vdash\phi(\mathbf{n})$ since
$\mathbf{Q}\vdash\phi(\mathbf{n})$ iff P(n).  But since $\mathbf{Q}$
proves all correct $\exists$-rudimentary sentences, and
$\phi(\mathbf{n})$ is $\exists$-rudimentary, $\phi(\mathbf{n})$ must
be false in the standard interpretation.  Let $\psi(x,y)$ be a
rudimentary formula such that $\phi(x)\leftrightarrow\exists
y\,\psi(x,y)$.  Since $\phi(\mathbf{n})$ is false, and since 
$\psi(x,y)$ is rudimentary, $\mathbf{Q}\vdash\neg\psi(\mathbf{n},\mathbf{m})$ for all $m$, and
hence $T\vdash\neg\psi(\mathbf{n},\mathbf{m})$ for all $m$.  Thus since $T\vdash\neg\psi(\mathbf{n},\mathbf{m})$ for all $m$ and yet $T\vdash\exists y\,\psi(\mathbf{n},y)$, $T$ is $\omega$-inconsistent.


Now 1. and 2., taken together, make $P$ semidefinable in $T$.
