I have known that:A function $\Bbb N  \Bbb N$ is recursive if and only if its graph is a recursive subset of $\Bbb N^2$.Now I am considering about the partial functions. Is it the fact that:A partial function $f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive if and only if its graph is a recursively enumerable subset of $\Bbb N^2$.If it is true (or one direction is true), may I please ask for a proof? Or some reference would be also appreciate (I searched it but did not obtain any useful result). Note: It is from a math course (and I have asked in the math site). And I have not learnt about the related things about computer science (for instance, I have not learnt about the Turing machine and I have no skill of coding). So sorry I cannot understand explanations which involves the usage of terms in computer science. May I please ask for a mathematical approch please? Thanks! I have done some search but I cannot find some helpful material. Any reference would be appreciate to. Thanks a lot.
$f:\Bbb N\dashrightarrow\Bbb N$ is partial recursive $\Leftrightarrow$ its graph is a recursively enumerable?
graphs;computability;recursion;enumeration
A $k$-ary relation $R \subseteq \mathbb{N}^k$ is recursively enumerable if its indicator function $f_R$ defined by$$f_R(n_1,\ldots,n_k) = \begin{cases} 1 & \text{if } R(n_1,\ldots,n_k) \\0 & \text{otherwise} \end{cases}$$is a partial recursive function. So if $f: \mathbb{N} \rightarrow \mathbb{N}$ is a partial recursive function, it is easy to see that the graph$$R_f = \{ (m,n) \mid f(m) = n \}$$is a recursively enumerable set. We have $f_{R_f}(m,n) = 1 - \mathrm{sg}(f(m) - n)$, where $\mathrm{sg}(n)$ is the primitive recursive function that is $0$ for $n=0$ and $1$ otherwise. Since we can express the indicator function $I_{R_f}$ of the graph as the composition of partial recursive functions, we therefore conclude that it is also a partical recursive function.Conversely, if $$R_f = \{ (m,n) \mid f(m) = n \}$$is a recursively enumerable set with indicator function $I_{R_f}$, then $$f(m) = \mu n. [ (1 - I_{R_f}(m,n)) = 0 ] $$Here $\mu n.P(n)$ denotes unbounded mineralization over the unary predicate $P(n)$.