Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Need more definition on computability. What does it mean for a graph to be computable? – user86828 Jul 19 '13 at 21:42
Okay, I put up the definition. Thanks – Jmaff Jul 19 '13 at 21:54
I recommend an appeal to the Church-Turing thesis. – Quinn Culver Jul 22 '13 at 21:24
up vote 1 down vote accepted

Here is how you would do it.

  1. 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.

share|cite|improve this answer
This sounds good but I am unsure about how your $f(F,y)$ function works. Let's say $F$ has domain and range, $N^{n} \longrightarrow N$. Now the composed function f(F,y) has domain $N^{n+1}$ and range $\{ 0,1\}$ . Thus I think it is more specifically $f(F(x), I_{n+1}^{n+1} (x,y))$ According to our definition of computability (2) though, I thought that the fist coordinate should be a function with domain $N^{n+1}$ Thus I am wondering if there is a way to get $F(x)$ from the n+1 tuple (x,y). – Jmaff Jul 19 '13 at 22:24
I do not understand your confusion. I do not understand what $I_{n+1}^{n+1}$ means. You can get $F(x)$ from the n+1-tuple $(x,y)$. Apply the projection function to it. $F(x_1,x_2 ...) = x_i$ is the projection function and is recursive. Now, the graph of F is defined to be the set of points (x, y) in $N^n \times N = N^{n+1}$ such that $F(x) =y$ The characteristic function of a set of points in $N^{n+1}$ is the function that returns 1 for a point if it is in the set, and 0 if it is not. – user86828 Jul 21 '13 at 18:11
The function $I_{n+1} ^{n+1}(x_{1},...,x_{n+1}) $ is the projection function to $x_{n+1}$. I was thinking that one could use the projection function but if I want to apply it to the n+1 tuple (x,y) where $ x \in N ^{n}$ then I don't see how to apply projection function to get out an entire n-tuple, namely x. I thought that the projection functions only had single natural numbers as outputs. – Jmaff Jul 21 '13 at 19:50
you can apply the projection function to each part of x. So if $x = (x_1, x_2)...$, and you have the tuple $(x_1, x_2, ... y)$, you can apply one projection function to $x_1$, another to $x_2$, etc. F(x) is really $F(x_1, x_2, x_3...)$. So you compose F with all your projection functions. – user86828 Jul 24 '13 at 18:28
ah, okay I think that makes sense. Thank you. – Jmaff Jul 25 '13 at 1:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.