Show that the existence of a semirecursive set that is not recursive implies that any consistent, axiomatizable extension of $\mathbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence.
If we have a semirecursive set $S$, then there is some recursive relation $R$ such that
\begin{align*}
\forall x (Sx \leftrightarrow \exists y Rxy) \\
\end{align*}
Every recursive function $R$ is arithmetically definable by some $\exists$-rudimentary formula. $\exists$-rudimentary formulas are closed over existential quantification so for any rudimentary $F_1$ we have rudimentary $F_2$ such that $\exists b \exists c F_1 xbc \leftrightarrow \exists d F_2 xd$. And every $\exists$-rudimentary formula is correct or true in the standard interpretation if and only if it is a theorem of the minimal theory of arithmetic $\mathbf{Q}$. Combining that, for any recursive $R$ we have some rudimentary $F$ such that:
\begin{align*}
\exists y Rxy \; \text{if and only if} \; (\vdash_{\mathbf{Q}} \exists z F(a,z)) \\
\end{align*}
I'm not sure how I go from here to proving that any consistent, axiomatizable extension of $\mathbf{Q}$ fails to prove some correct $\forall$-rudimentary sentence.
The first, and possibly most important example of a correct but unprovable $\forall$-rudimentary sentence is the consistency sentence:
\begin{align*}
\lnot \text{Prv}_T(\ulcorner \mathbf{0} = \mathbf{1} \urcorner) \\
\end{align*}
Clearly, in a consistent theory, the consistency sentence is correct, or true in the standard interpretation, but it can't be proven.
How do I use a semirecursive set to demonstrate this?
Can someone give me a hint on how to solve the problem. I'm somewhat stuck on what to try.
Best Answer
The point is that if $T$ were a consistent axiomatizable extension of $\mathsf{Q}$ which proved all $\forall$-rudimentary sentences, then the complement of each semirecursive set must also be recursive - hence every semirecursive set is recursive, which we know isn't true. This is because the set of things an axiomatizable theory proves is semirecursive.
In more detail, suppose $\varphi(x,y)$ is $\exists$-rudimentary such that the semirecursive set $$S=\{n: \exists y(\varphi(n,y))\}$$ is not recursive and $T$ is a consistent axiomatizable extension of $\mathsf{Q}$. Let $$X_T=\{n: T\vdash\forall y(\neg\varphi(\underline{n},y))\}.$$ Since $\varphi$ is $\exists$-rudimentary, $T\supseteq\mathsf{Q}$, and $T$ is consistent, we must have $X_T\cap S=\emptyset$; if $T$ were to prove all true $\forall$-rudimentary sentences, we would have $X_T\cup S=\mathbb{N}$ and so $X_T=\mathbb{N}\setminus S$. But since $T$ is axiomatizable the set $X_T$ is itself semidecidable! So this would mean that $S$ is co-semidecidable as well as decidable, hence decidable - which we know it isn't.