Showing that all semirecursive sets are semidefinable

Question

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?

Answer 1

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.

Answer 2

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

1. If $P(n)$ is true, then $\mathbf{Q}\vdash\phi(\mathbf{n})$, so $T\vdash\phi(\mathbf{n})$ since $T$ extends $\mathbf{Q}$.
2. 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$.