Let F be a function from $N ^{n} \longrightarrow N$. Show that if F is computable then its graph is computable.
According to the definition of computable/recursive I am looking at, a relation is computable if its characteristic function is computable. It is also known that the relation of equality is computable. I want to show that given $ R(a,b) \leftrightarrow F(a)=b$, the relation R is a computable function.
Here is the definition of computability I am using:
The computable functions are the functions $ N ^{n} \longrightarrow N$ obtained inductively by the following rules: (1) $+: N^{2} \longrightarrow N, \cdot: N^{2} \longrightarrow N, \chi _{\leq} : N^{2} \longrightarrow N$ ,and the coordinate functions are computable.
(2) If $ G: N^{m} \longrightarrow$ is computable and $H_{1},...H_{m} : N^{n} \longrightarrow N$ are computable the so is the function $F = G(H_{1},...H_{m}) : N^{n} \longrightarrow N$ defined by$ F(a)=G(H_{1}(a),...,H_{m}(a))$
(3) If $G : N{n+1} \longrightarrow$ is computable ,and for all $a\in N^{n}$ there exists N such that $G(a,x)=0$, then the function( $F: N^{n} \longrightarrow N$) defined by $F(a)= \mu x(G(a,x)=0) $ is computable.
The graph is computable if its characteristic function is computable.
Thanks for any help
Here is how you would do it.
Prove that the function f(x,y) which returns 1 if x=y, and 0 otherwise is recursive.
2.You are done, compose f(x, y) with F, to get f(F, y). Show that this is the characteristic function of the graph of F.