1

Soare's Recursively Enumerable Sets and Degrees (1987) shows that $Rec = \left\{ e : W_e \text{ is recursive} \right\}$ is $\Sigma^0_3$-complete via its relationship to other index sets, namely $Cof$ and $Cpl$, as discussed in this previous question on MSE. I assume there is a simple direct argument exhibiting a recursive function $f$ which reduces $K = \left\{ e : \varphi_e(e)\downarrow \right\}$ to $Rec$, but I'm having trouble coming up with it.

One thought I had was that each finite initial segment of $K$ is a recursive set and hence has a pair of indices in $Rec$, and that one could then some how use $Rec$ to take the union of these approximations, but I can't quite see how to make it work. Any help people could offer would be appreciated; I'm sure I'm just missing something obvious.

Community
  • 1
Benedict Eastaugh
  • 2,883

1 Answers1

1

Consider the recursive function $\psi$ such that : $$\psi(e,x)=\mbox{Compute $\phi_e(e)$ on $x$ steps. If it halts in less than x steps then 1 else }\phi_x(x)$$

By smn, there is a recursive function $f$ such that $$\phi_{f(e)}(x)=\psi(e,x)$$

Then $K\le Rec$ by $f$ :

  1. If $e\in K$ then $W_{f(e)}$ is cofinite and $f(e)\in Rec$
  2. If $e\notin K$ then $W_{f(e)}=K$ and $f(e)\notin Rec$

Note that $f$ is obtained by smn, and thus can be made injective and increasing. Hence $K\le_1 Rec$

Xoff
  • 10,310
  • Thanks, very nice. A comment to flesh out the post for future readers: $Cof \subseteq Rec$ since all finite sets are recursive and the class of recursive sets is closed under complementation, hence why your (1) shows that $f(e) \in Rec$. – Benedict Eastaugh Feb 27 '14 at 23:08