# Showing a set $\Sigma^0_n$ subset of $\mathbb{N}$ is $\Sigma^0_n$-complete

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<x\exists l \hspace{3pt}S(n, k, l)$$ 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.

-
In my experience, convention varies a fair amount in computability theory. Can you explain the convention you are using a little? Specifically, what are the functions seq and lh, what does $\wedge$ denote, and what are $(e)_0,(e)_1$? Edit: I assume that $e$ is interpreted as coding for two natural numbers using the standard pairing function and that $(e)_i$ is the $i^{th}$ number coded for by $e$. – Alex Becker Feb 26 '12 at 5:18
Could you define the notations "seq" and "lh", please? Also, I'm used to $\varphi_i$ denoting some enumeration of the computable partial functions, but what does the superscript in $\varphi^1_i$ do for you? Is $S$ a defined concept for you or just a random dummy variable? – Henning Makholm Feb 26 '12 at 5:21
@HenningMakholm Good to see I'm not the only one who hasn't seen this notation. – Alex Becker Feb 26 '12 at 5:23
So $\wedge$ denotes regular old "and". Also, $seq$ is not a function, but a unary predicate, where $seq(x)$ holds if and only if $x$ is the code for a sequence, and lh(x) is the function which outputs the length of a code (it outputs 0 when $x$ is not a code for a sequence). By $(x)_i$, I mean the $i$th coordinate in the sequence that $x$ codes, provided of course $i$ is less than the length of $x$. The 1 in the notation $\varphi^1_i$ only indicates that $\varphi_i$ is to be a unary partial recursive function. $S$ is meant to be any recursive predicate which witnesses $B$ being a $\Pi^0_2$ set – student555 Feb 26 '12 at 5:25
@Leon In this case, you need to use parentheses to make the statement clearer. – Alex Becker Feb 26 '12 at 5:28

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