R $\subseteq \omega$ recursive iff $\exists m \in \omega$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$.

61 Views Asked by At

The queston I'm trying to solve is use Kleene's enumeration theorem to show R $\subseteq \omega$ recursive iff $\exists m$ such that $R=\{n \ | \ \bar{\omega} \models \phi[m,n] \}$ for some $m \in \omega$.(In the numerical language $(+ , . ,$ Succ $,1, 0)$). The implication $\rightarrow$ is trivial.However if we suppose $\phi(x,y)$ is given by Kleene's enumeration theorem then $R=\{n \in \omega \ | \ \bar{\omega} \models \phi[m,n]\}$ for some $m \in \omega$ is recursively enumerable since R is $\Sigma_{1}$. Then by employing the negation theorem all that is left to do to show R is recursive is to show the complement of R is recursively enumerable. However I'm unsure how to go about this. I know $R^{c}=\{n \in \omega \ |\ \bar{\omega} \models \neg \phi[m,n] \}$. So in particular $R^{c}$ is $\Pi_{1}$. Any suggestions on how to proceed would be very welcome. I thank you in advance.