Let $x \in \mathbb{N}$ be fixed. Let $K$ be the set $\{y | \phi_y(y) \downarrow\}$. I need to prove that $K^c \leq_1 \{y | \phi_y = \phi_x\}$. If I understand correctly, we need to find an injection $f$ such that $\phi_{f(x)} = \phi_x$ if and only if $\phi_y(y)$ does not converge. I thought maybe we could use the $smn$-theorem to construct $f$, but can't make it work.
2026-03-27 02:35:21.1774578921
Complement of the halting set one to one reducible to $\{y | \phi_y = \phi_x\}$ for fixed $x$.
79 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
1
The statement is false. I can't find the question again, but I probably copied it wrong or something.
Use the smn theorem to find a computable injection $f$ such that $\phi_{f(y)}(z) \simeq \phi_x(z) + 0 \cdot \phi_y(y)$.
If $y \notin K$, then $\phi_{f(y)} \neq \phi_x$ unless $x$ is an index for the empty function, if $y \in K$, then $\phi_{f(y)} = \phi_x$, so
$f: K \leq_1 \{y \ | \ \phi_y = \phi_x \}$. As $K$ is $1$-complete, that means that $ \{y \ | \ \phi_y = \phi_x \} \equiv_1 K$. But then $\bar{K} \leq_1 \{y \ | \ \phi_y = \phi_x \}$ implies that $\bar{K} \leq_1 K$. Call this one reduction $g$, then $\lambda x. \phi_{g(x)}(g(x))$ converges precisely when $g(x)$ is in $K$, so precisely when $x$ is in $\bar{K}$. That would mean $\bar{K}$ is c.e., so $K$ would be computable which is a contradiction.