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
-
0In 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$. – 2012-02-26
-
0Could 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? – 2012-02-26
-
0@HenningMakholm Good to see I'm not the only one who hasn't seen this notation. – 2012-02-26
-
0So $\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 – 2012-02-26
-
0@Leon In this case, you need to use parentheses to make the statement clearer. – 2012-02-26
-
0@Leon Are there any sets you already know to be $\Sigma_1^0$ or $\Pi_2^0$-complete? – 2012-02-26
-
0@AlexBecker I know that $Tot$, the set of Godel numbers for total recursive functions is $\Pi^0_2$-complete. You are suggesting then to show that $Tot\leq_m A$? – 2012-02-26
-
0@Leon That would certainly work, and would slightly shorten my proof below, which 1-reduces any $\Pi_2^0$ set to $A$. – 2012-02-26
-
0@Leon Have your questions been resolved? – 2012-02-26
-
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 example 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