This is both a general and specific question in basic computability theory. Broadly speaking, I am not very comfortable with showing whether or not a subset of $\mathbb{N}$ is $\Sigma^0_n$ (or $\Pi^0_n$) complete. I am struggling with several such questions on my computability homework, I will state here what I believe is the simplest (at least terms of complexity of the set). Consider the set $ A:= \left\{e\mid \left(seq(e)\right)\wedge \left(lh(e)=2\right)\wedge \left[\varphi^1_{(e)_0} = \varphi^1_{(e)_1}\right]\right\}. $ This set is certainly a $\Pi^0_2$ subset of $\mathbb{N}$, but I want to show that it is $\Pi^0_2$-complete. That is, I want to prove that whenever $B\subseteq\mathbb{N}$ is $\Pi^0_2$, then there is a total recursive function $f$ such that $ B(n)\iff A(f(n)) \iff f(n) \text{ is a code of a pair $(a, b)$ such that $\varphi^1_a = \varphi^1_b$}. $ My first reaction is to write $ B(n)\iff \forall k\exists l \hspace{3pt}S(n, k, l) $ where $S$ is a recursive predicate. We can do this as $B$ is a $\Pi^0_2$-set. However, I cannot see how to take this and find my desired $f$. I have tried using the index function theorem to find a function a total recursive function $t$ such that $ \varphi_{t(n)}(x) = e\iff \forall k
Showing a set $\Sigma^0_n$ subset of $\mathbb{N}$ is $\Sigma^0_n$-complete
-
0One of the easiest ways is to reduce $\forall$x$\ \exists y \ A_{TM}(e,
)$ to your problem, where $A_{TM} = \{ (e,z) | \varphi_e(z)=accept \}$. It is easy to show the later is complete. This method generalizes to other levels of the hierarchy. – 2012-03-06
2 Answers
Consider an arbitrary $\Pi_2^0$ set $B$, and let $B(n)$ denote the predicate $n\in B$. Let $S$ be a recursive predicate such that $B(n)\iff (\forall k)(\exists l) S(k,l,n)$ as you suggest. Define the function $f(k,n)$ to be $1$ for all $n,k$, and define the function $g(k,n)$ to be $1$ iff $(\exists l)S(k,l,n)$ and undefined otherwise. Note that $g(k,n)$ is recursive but may not be total. Crucially, we have that $g(k,n)=1=f(k,n)$ for all $k$ iff $B(n)$. By the parameter theorem (or at least that's what I call it) we have one-to-one recursive functions $t(n),s(n)$ such that $f(k,n)=\varphi_{t(n)}(k)$ and $g(k,n)=\varphi_{s(n)}(k)$ for all $k,n$. Then let $h(n)=\langle t(n),s(n)\rangle$ where $\langle\cdot,\cdot\rangle$ denotes the standard pairing function. Note that $h$ is recursive and one-to-one. We have $\begin{eqnarray}B(n)&\iff&f(k,n)=g(k,n)\\ &\iff&\varphi_{t(n)}=\varphi_{s(n)}\\ &\iff& h(n)\in A\end{eqnarray}$ and thus $h$ $1$-reduces $B$ to $A$. Hence $A$ is $\Pi_2^0$-complete.
-
0Thank you for this answer, I think this is an illustrative e$x$ample of how to tackle these kinds of problems. – 2012-02-26
Alex Becker's answer shows directly that $A$ is $\Pi^0_2$-complete. However if you already know some $\Pi^0_2$-complete sets, than it is easier to $m$-reduce such a set to $A$. As you have mentioned in a comment you know that $Tot$ is $\Pi^0_2$ complete. Now let $e$ be a natural number. Define functions $f_1(x) = 0 \cdot f_e(x)$ $f_2(x) = 0$ It can be seen that $e \in Tot$ if and only if $\langle a, b \rangle \in A$, where $a$ is an index of $f_1$ and $b$ is an index of $f_2$.
-
0I really like this answer too and think its a nice alternative proof. Thank you very much!! – 2012-02-26