Show that this set is $\Pi_1^0$-complete?

35 Views Asked by At

Let us call $A:= \{i \in \mathbb{N} \mid \varphi_i \ \text{is partial, computable and strictly increasing} \}$ and we want to show that $A$ is $\Pi_1^0$-complete (for the many-one reduction).

First, let see why $A \in \Pi_1^0$. Let us consider the complement of $A$ : $\overline{A}$.

$i \in \overline A \Leftrightarrow \overbrace{\exists z (\pi_1(z)>\pi_2(z) \ \wedge U(\pi_1(z))\le U(\pi_2(z)))}^{\text{not strictly increasing}} \ \wedge \overbrace{\exists t (T^1[i,\pi_1(z),\pi_1(t)]\wedge T^1[i,\pi_2(z),\pi_2(t)])}^{\text{on these entries the function is defined by being total}} \Leftrightarrow \exists z \exists t \ \Sigma_0^0.$

Indeed, we use the encoding of a pair (which is a primitive recursive operator), the primitive recursive function $U$ of Kleene which gives the result of the computation of $\varphi_i$ on entries $x$ and $y$, the Kleene predicate $T^1$ which is recursive and gives on entries $x$ and $y$ the existence of two histories of computation which makes $\varphi_i$ halt in less than $\pi_i(t)$ steps. The relations $>$ and $\le$ are also recursive. The closure of recursivity by the operator $\wedge$ gives the $\Sigma_0^0$ statement.

Hence $\overline A \in \Sigma_1^0$ and then $A \in \Pi_1^0$.

Now let us show the completeness. We will use the following set $K:= \{i \in \mathbb{N}\mid \varphi(i,i) \downarrow\}$ which is $\Sigma_1^0$-complete.

Let us prove that $\overline K \le_m A$.

We start by building a partial computable function which will be strictly increasing using the induction-scheme :

$\begin{align} g(i,0)&=0 \\ g(i,n+1)&= g(i,n)+1 \end{align}$ where $g(i,n)= \begin{cases} 0 \ \text{if}\ i \in K \\ \uparrow \ \text{else} \end{cases}$.

The function $g$ is partial computable (the definition by case using the halting set $K$ is valid here) hence by the smn theorem it has an index $j$ such that : $g(i,n)= \varphi^2(j,i,n)=\varphi_{s_1^1(j,i)}(n)= \varphi_{\alpha(i)}(n)$ where $\alpha$ is a total computable function.

$\alpha(i)$ is an index of the partial computable function $g$ which is strictly increasing. Hence $i \in \overline K \Leftrightarrow \alpha(i) \in A$ and the reduction is done.

We can conclude that $A$ is $\Pi_1^0$-complete.

I was wondering if this proof was correct ? Especially the part about reduction. Also, maybe there are other approaches more "algorithmic" to see this.

Thanks in advance !