2
$\begingroup$

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 where $e$ is a code of length 2 such that $\varphi_{(e)_0} = \varphi_{(e)_1}$. The problem is that $t$ is not necessarily a coding of a pair, and so cannot serve as my desired function. I am unsure of what other directions to take, and any indications or hints would be very useful. Also, any discussion on strategies on proving problems of this kind in general are greatly appreciated. Thank you.

  • 0
    One 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 2

1

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.

  • 0
    Thank you for this answer, I think this is an illustrative e$x$ample of how to tackle these kinds of problems.2012-02-26
2

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

  • 0
    I really like this answer too and think its a nice alternative proof. Thank you very much!!2012-02-26