2

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.

CWcx
  • 608
  • 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 05: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? – hmakholm left over Monica Feb 26 '12 at 05:21
  • @HenningMakholm Good to see I'm not the only one who hasn't seen this notation. – Alex Becker Feb 26 '12 at 05: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 – CWcx Feb 26 '12 at 05:25
  • @Leon In this case, you need to use parentheses to make the statement clearer. – Alex Becker Feb 26 '12 at 05:28
  • @Leon Are there any sets you already know to be $\Sigma_1^0$ or $\Pi_2^0$-complete? – Alex Becker Feb 26 '12 at 05:34
  • @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$? – CWcx Feb 26 '12 at 05:39
  • @Leon That would certainly work, and would slightly shorten my proof below, which 1-reduces any $\Pi_2^0$ set to $A$. – Alex Becker Feb 26 '12 at 05:53
  • @Leon Have your questions been resolved? – Alex Becker Feb 26 '12 at 08:16
  • One of the easiest ways is to reduce $\forall x \ \exists y \ A_{TM}(e,<x,y>)$ 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. – Kaveh Mar 06 '12 at 18:01

2 Answers2

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

Levon Haykazyan
  • 4,876
  • I really like this answer too and think its a nice alternative proof. Thank you very much!! – CWcx Feb 26 '12 at 09:49
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.

Alex Becker
  • 60,569
  • Thank you for this answer, I think this is an illustrative example of how to tackle these kinds of problems. – CWcx Feb 26 '12 at 09:49