Functions defined at $0$ and undefined at $1$ is not a (co)computably enumerable set

53 Views Asked by At

Let $U$ bet a Godel universal function and consider the set $R=\{p\in N: U(p,0)\downarrow, \ U(p,1)\uparrow\}$. Prove that $R$ is not c.e. (computably enumerable) and not co-c.e (co-computably enumerable).

Is the following sketch of proof correct?

It's enough to show that $K=\{p\in N: U(p,p)\downarrow\}$ can be $m$-reduced to $R$ and $\overline R$ (overline = complement).

  1. $K\leq_m R$:

Define the partial function $V:N\times N\to N$ as follows:

  • if $n\in K$, then $V(n,x)=\frac{x}{x-1}$;
  • if $n\notin K$, then $V(n,x)$ is undefined for all $x$.

This is a computable partial function. Thus there's a total computable $s:N\to N$ such that $V(n,x)=U(s(n),x)$ for all $n,x$. This $s$ $m$-reduces $K$ to $R$.

  1. $K\leq_m \overline R$

Define the partial function $V:N\times N\to N$ as follows:

  • if $n\in K$, then $V(n,x)=\frac{1}{x}$ (or alternatively $V(n,x)=1$ for all $x$);
  • if $n\notin K$, then $V(n,x)$ is undefined for all $x$.

This is a computable partial function. Thus there's a total computable $s:N\to N$ such that $V(n,x)=U(s(n),x)$ for all $n,x$. This $s$ $m$-reduces $K$ to $\overline R$.