Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 1 down vote accepted

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.

share|cite|improve this answer
Thank you for this answer, I think this is an illustrative example of how to tackle these kinds of problems. – student555 Feb 26 '12 at 9:49

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

share|cite|improve this answer
I really like this answer too and think its a nice alternative proof. Thank you very much!! – student555 Feb 26 '12 at 9:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.