Understanding second axiom of Primitive recursion

Question

I read about Primitive recursion and was able to understand most of it.

However I am finding it very difficult to understand the second axiom of primitive recursion.

I can make out that it helps in defining definitions in a recursive manner. I am also able to write the primitive recursive definitions of some trivial functions myself. But am still not very clear about what the axiom actually says.

Could someone give an explanation or point to a good resource for reading the same ?

---

I meant the second axiom in this (taken from Wikipedia) :

Answer 1

Let us maybe try a few examples.

Addition, written in prefix form as $+(y,x_1)$, is primitive recursive since $+(0,x_1)=x$ and $+(y+1,x_1)=S(+(y,x_1))$. We can make the argument fully explicit by exhibiting $f,g$ as in the Wikipedia link:

• $f$ is the identity function, noted $P^1_1$ in your link,
• $g(y,x,x_1)=S(P_2^3(y,x,x_1))$, which is primitive recursive by composition of the basic successor and projection functions.

Multiplication $\times(y,x_1)$ can be similarly defined by $\times(0,x_2)=0$ and $\times(y+1,x_1)=\times(y,x_1)+y$:

• $f$ is the constant function $0$,
• $g(y,x,x_1)=+(P^3_1(y,x,x_1),P^3_2(y,x,x_1))$ is primitive recursive by composition of the addition and projection functions.

Answer 2

Let's first try this with just $n=0$. Recall that $S(x)$ is interpreted as $x+1$ in this context, which may also ease up on reading this axiom.

In this case, $f$ is a $0$-ary function, so it's really just a constant function. So we have

So we have that if $g$ is a $2$-ary function, so $g(x,y)$ is some function taking input of integers, whose output is an integer, then there is a function $h(x)$ which satisfies the two following properties:

1. $h(0)=f$, which is a constant as we know.
2. $h(n+1)=g(n,h(n))$.

So, for example, if $g(x,y)=x+y$ and $f=1$, then we have that $h(0)=1$ and $h(1)=g(0,h(0))=g(0,1)=0+1=1$ and $h(2)=g(1,h(1))=2$ and $h(3)=g(2,h(2))=4$ and $h(4)=g(3,h(3))=7$ and so on.

So what does it mean? Well, it means that given a function $g(x,y)$ and an initial constant $f$, we can define a sequence whose initial value is $f$, and the "bootstrap function" is $g$, so $h(n+1)=g(n,h(n))$, where $n$ is the index of the sequence.

But we don't want to limit ourselves to a constant starting condition. Instead, we want a wide variety of options which may include parameters. And these parameters are the $x_1,\ldots,x_k$.

So the axiom states that if you have $f(x_1,\ldots,x_k)$ which is the function for the "initial value (up to parameters)" and you have a "bootstrap function" $g$ which also takes these parameters and two extra variables, then you can define a sequence by induction which takes the parameters and an index.

And formally, this means that $f$ is a $k$-ary function and $g$ is a $(k+2)$-ary function, and the recursion schema says that there exists a function $h$ which is $(k+1)$-ary and it satisfies:

1. $h(0,x_1,\ldots,x_k)=f(x_1,\ldots,x_k)$. Our initial value depends only on the parameters.
2. $h(n+1,x_1,\ldots,x_k)=g(n,h(n,x_1,\ldots,x_k),x_1,\ldots,x_k)$. Our "next value" depends on the index, the previous value, and our parameters.

Answer 3

An simple example with a familiar algebraic example may serve to illuminate the conceptual thrust underlying the axiom. Let us consider a linear function in general form:

$$h(x) = ax + c$$

where $a$ is the coefficient of the independent variable $x$ and $c$ is the constant term that gives the value of $h$ when $x = 0$; $a$ and $c$ are the parameters to be set for a particular application of the function.

We can express the function $h$ in the form given by the axiom as $h(x, a, c)$.

A function $f(a, c)$ sets the parameters at the initial value we have specified which is represented by $x = 0$:

$$h(0, a, c) = f(a, c)$$

Subsequently, a function $g$ calculates the successive values of $h$:

$$h(x+1) = g(x, h(x))$$

Hence, in the precise notation given by the axiom:

$$h(S(x), a, c) = g(x, h(x, a, c), a, c)$$