[proofplan]
We first represent the computably enumerable set $A$ as the domain of one partial computable function. Then the [s-m-n theorem](/theorems/5398) produces, uniformly in $x$, an index for a program that ignores its own input and simulates that fixed partial computable function at $x$. Evaluating this produced index on itself converts membership in $A$ into membership in the diagonal halting set $K$. Finally, we note that $K$ itself is computably enumerable, so the reduction property makes it many-one complete among c.e. sets.
[/proofplan]
[step:Choose an index whose domain is the given computably enumerable set]
Let $A \subseteq \mathbb N$ be computably enumerable. By the definition of computable enumerability, there exists an index $a \in \mathbb N$ such that
\begin{align*}
A = \operatorname{dom}(\varphi_a) = \{x \in \mathbb N : \varphi_a(x)\downarrow\}.
\end{align*}
Here $\varphi_a: \mathbb N \rightharpoonup \mathbb N$ is the partial computable function with index $a$ in the fixed acceptable enumeration.
[/step]
[step:Use the s-m-n theorem to build constant-input programs uniformly in $x$]
For each $x \in \mathbb N$, define the partial function
\begin{align*}
\psi_x: \mathbb N &\rightharpoonup \mathbb N
\end{align*}
by declaring that, for every $y \in \mathbb N$, the computation $\psi_x(y)$ simulates $\varphi_a(x)$ and returns the same value if that computation halts. Thus
\begin{align*}
\psi_x(y)\downarrow \iff \varphi_a(x)\downarrow.
\end{align*}
By the s-m-n theorem (citing a result not yet in the wiki: s-m-n theorem), applied to the two-variable partial computable procedure $(x,y) \mapsto \varphi_a(x)$, there exists a total computable function
\begin{align*}
f: \mathbb N &\to \mathbb N
\end{align*}
such that, for all $x,y \in \mathbb N$,
\begin{align*}
\varphi_{f(x)}(y) \simeq \psi_x(y),
\end{align*}
where $\simeq$ means equality of partial computations: both sides halt with the same value, or both sides diverge.
[guided]
The goal is to turn the question “does $\varphi_a(x)$ halt?” into the diagonal question “does some program halt on its own index?” To do this, we want a program whose behavior is completely determined by the fixed input $x$ and not by the input later fed to that program.
For each $x \in \mathbb N$, define a partial function
\begin{align*}
\psi_x: \mathbb N &\rightharpoonup \mathbb N
\end{align*}
as follows: on input $y \in \mathbb N$, the computation $\psi_x(y)$ ignores $y$, simulates $\varphi_a(x)$, and returns the value of $\varphi_a(x)$ if that computation halts. Therefore, for every $y \in \mathbb N$,
\begin{align*}
\psi_x(y)\downarrow \iff \varphi_a(x)\downarrow.
\end{align*}
The required uniformity is exactly what the s-m-n theorem provides. Apply the s-m-n theorem (citing a result not yet in the wiki: s-m-n theorem) to the two-variable partial computable procedure
\begin{align*}
(x,y) \mapsto \varphi_a(x).
\end{align*}
This procedure is partial computable because $a$ is a fixed index and the second input $y$ is ignored. The theorem gives a total computable function
\begin{align*}
f: \mathbb N &\to \mathbb N
\end{align*}
such that $f(x)$ is an index for the one-variable partial computable function $y \mapsto \varphi_a(x)$. Equivalently, for all $x,y \in \mathbb N$,
\begin{align*}
\varphi_{f(x)}(y) \simeq \psi_x(y),
\end{align*}
where $\simeq$ denotes equality as partial computations. The word “total” is essential here: $f$ must be defined for every $x \in \mathbb N$ in order to be a many-one reduction.
[/guided]
[/step]
[step:Verify that the computable map reduces $A$ to $K$]
Fix $x \in \mathbb N$. Since $K = \{e \in \mathbb N : \varphi_e(e)\downarrow\}$, we have
\begin{align*}
f(x) \in K
&\iff \varphi_{f(x)}(f(x))\downarrow \\
&\iff \psi_x(f(x))\downarrow \\
&\iff \varphi_a(x)\downarrow \\
&\iff x \in \operatorname{dom}(\varphi_a) \\
&\iff x \in A.
\end{align*}
The first equivalence is the definition of $K$. The second uses the index property of $f(x)$ from the s-m-n theorem. The third uses the definition of $\psi_x$, which ignores its input. The final two equivalences use $A=\operatorname{dom}(\varphi_a)$.
Thus the total computable function $f: \mathbb N \to \mathbb N$ satisfies
\begin{align*}
x \in A \iff f(x) \in K
\end{align*}
for every $x \in \mathbb N$, so $A \le_m K$.
[/step]
[step:Show that the diagonal halting set is itself computably enumerable]
Define a partial computable function
\begin{align*}
\theta: \mathbb N &\rightharpoonup \mathbb N
\end{align*}
by the following computation: on input $e \in \mathbb N$, simulate $\varphi_e(e)$, and if that simulation halts, output $0$. Then
\begin{align*}
\operatorname{dom}(\theta)
&= \{e \in \mathbb N : \theta(e)\downarrow\} \\
&= \{e \in \mathbb N : \varphi_e(e)\downarrow\} \\
&= K.
\end{align*}
Therefore $K$ is computably enumerable.
[/step]
[step:Conclude many-one completeness among computably enumerable sets]
We have shown that every computably enumerable set $A \subseteq \mathbb N$ satisfies $A \le_m K$. We have also shown that $K$ is computably enumerable. Hence $K$ is many-one complete for the computably enumerable subsets of $\mathbb N$.
[/step]
