Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to write a formula $A(x, y)$ which represents the relation $(y=f(x))$ in True Arithmetic? The formula for $A(x, y)$ can use a formula $B(c, d, i, y)$ that represents the graph of Godel $β$ function $(y=β(c, d, i))$

edit: $f(x)$ is the fibonacci function:

$$f(0) = f(1) = 1$$ $$f(i + 2) = f(i + 1) + f(i)$$

share|improve this question
You can do this by saying that there is a number that codes a sequence of length at least $x$, that $y$ is the $x$-th term of this sequence, that the first two terms of the sequence are $1$, and that each term of the sequence from the second on is the sum of the previous two. The beta function allows you precisely to do this. –  Andres Caicedo Apr 3 at 22:31
See here for the same argument, applied to the case of exponentiation. –  Andres Caicedo Apr 3 at 22:32

Your Answer


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

Browse other questions tagged or ask your own question.