I'm trying to show the equivalence of these definitions of a computably enumerable set:
- $A$ is c.e. if there is a computable partial $f:N\to N$ such that $A=\text{dom}f$.
- $A$ is c.e. if there is a computable partial $g:N\to N$ such that $A=\text{im} g$.
One direction: Suppose $A=\text{dom} f$. Consider $f'(x)=c_1\circ f$ where $c_1$ is the constant function with value $1$. Now let $g(x)=xf'(x)$. Then $g$ is defined iff $f'$ is defined iff $f$ is defined, and the range of $g$ is the domain of $f$. All functions that appear above are partial computable, so this proves this direction.
The other direction: Let $T(-,-,-)$ be the Kleene $T$-predicate. $T(p,x,z)$ holds iff program number $p$ halts on input $x$, and $z$ is a witness of this. $T$ is a computable predicate. Given $g$ that is computed by a program number $p$, the idea is to construct a program that computes $f$ as follows:
For all $i=0,1,2,...$ check if $(\exists x < i)(\exists z < i) T(p,x,z)$. If this is the case, then output final($z$) where final "extracts" the value of $g(x)$ from the witness $z$.
How to make this more formal? I'm thinking about something like this:
$$f(i)=g(\text{the least }x < i\text{ such that } (\exists z < i)T(p,x,z)\land x\notin \{f(0),\dots, f(i-1)\})$$ But I see at least one problem: if $i\in A$, $f(i)$ may be undefined, since the witness $z$ of the fact that $g(\text{something})=i$ may be larger than $i$...
So how to either fix this definition of $f$ or make a new one in a way that $A=\text{dom}f$?
I would say $f(x)$ is the smallest $k$ such that $(\exists i<k)(\exists z<k) \, T(p,i,z) \wedge \mathrm{final}(z)=x$.