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

Help me please $f(x)=x+a$, where $a$ is a constant.

share|cite|improve this question
do you want to show that $f(x)$ is primitive recursive? – Ram Jan 14 '13 at 9:28
Yes! Where f(x) is x+a – user58222 Jan 14 '13 at 9:31
Welcome to Math.SE! You could have considered the addition of this link to your question: . In specific the paragraph "Addition" in the page above should answer your question. Is it correct? – Giovanni De Gaetano Jan 14 '13 at 9:37
up vote 1 down vote accepted

First of all I think that your statement is wrong when $a\notin \mathbb{Z}$, and the function you define when $a\notin \mathbb{N}$ should have the domain restricted, because you cannot use the subtraction but only the limited subtraction.

So let us suppose $a\in \mathbb{N}$ for simplicity. If $a=0$ then $f(x)=x$ is the identity function, and this is known to be primitive recursive. Indeed $f(x) = P_1^1(x)$.

Now let us proceed by induction and suppose that $f_n(x)= x+n$ is primitive recursive. By $S$ we denote the successor function $S(k)=k+1$ which is axiomatically primitive recursive. Then $S(f_n(x))= (x+n)+1=f_{n+1}(x)$.

Since the composition of primitive recursive functions is primitive recursive we deduce that $f_{n+1}(x)=x+(n+1)$ is primitive recursive as well. By the induction hypothesis we are done.

Note: This has been brutally copied by Wikipedia: Primitive recursive function.

share|cite|improve this answer
Thank you! And there is my solution: (is it correct ?) $$f(x-a)=x-a+a=x$$ is the identity.....and primitive. $$f(x+1)=x+a+1=f(x)+1=S(f(x))$$ – user58222 Jan 14 '13 at 10:50
You are welcome! The problem with your solution seems to me that $f(x-a)$ could be not well defined. In the sense that a primitive recursive function goes from $\mathbb{N}$ to $\mathbb{N}$ and if $x<a$ then $x-a\notin\mathbb{N}$. Moreover you should observe that the composition of primitive recursive functions is primitive recursive. If you want to be sure to have understood a good exercise could be to write $f_n(x)=x+n$ only in terms of projective and successor functions. Lastly, do you know how to accept an answer? – Giovanni De Gaetano Jan 14 '13 at 11:02
i accepted. did i it right? – user58222 Jan 14 '13 at 12:59
Perfect! ;) For your future participation in Math.SE remember that people do care about how many answers did you accept, so keep going! – Giovanni De Gaetano Jan 14 '13 at 14:41

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.