= Solution
For the given effective enumeration of partial computable functions, the <diagonal halting set> is
$$
\boxed{K=\{n\in\mathbb N:f_{n,1}(n)\text{ is defined}\}}.
$$
A <many-one reduction> $A\leq_mB$ is a <total computable function> $g:\mathbb N\to\mathbb N$ such that
$$
\boxed{x\in A\Longleftrightarrow g(x)\in B}.
$$
The <S-m-n theorem> states that for every $m,k\geq1$ there is a total computable function $s_k^m$ satisfying
$$
f_{s_k^m(e,x_1,\ldots,x_m),k}(y_1,\ldots,y_k)
=f_{e,m+k}(x_1,\ldots,x_m,y_1,\ldots,y_k)
$$
whenever either side is defined.
Suppose first that $X$ is <recursively enumerable set>[recursively enumerable]. Choose a program that halts exactly on inputs in $X$, and let $e$ index a two-variable program that, on $(x,y)$, ignores $y$ and runs that program on $x$. By the S-m-n theorem,
$$
g(x)=s_1^1(e,x)
$$
is total computable and indexes the unary function
$$
f_{g(x),1}(y)=f_{e,2}(x,y).
$$
Therefore
$$
x\in X
\Longleftrightarrow f_{g(x),1}(g(x))\text{ is defined}
\Longleftrightarrow g(x)\in K.
$$
Thus $X\leq_mK$.
Conversely, suppose $X\leq_mK$ through a total computable $g$. On input $x$, compute $g(x)$ and simulate machine $g(x)$ on its own code. This procedure halts exactly when $g(x)\in K$, equivalently exactly when $x\in X$. Hence $X$ is recursively enumerable. We have proved the <many-one completeness of the halting problem>:
$$
\boxed{X\text{ is recursively enumerable}\Longleftrightarrow X\leq_mK}.
$$
Finally, use the stated fact that $0\notin K$ and define
$$
S=\{0\}\cup\{2n+1:n\in K\}.
$$
Then $0\in S\setminus K$, so $S\ne K$. The total computable map $n\mapsto2n+1$ satisfies
$$
n\in K\Longleftrightarrow2n+1\in S,
$$
and therefore $K\leq_mS$. This is a <distinct representative of the halting many-one degree>.
Back to article page
