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?
Best Answer
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.