Showing a function that behaves like pred to be primitive recursive

Question

Let's define $M$ such that for $x \ge 0$:

$$ M(0)=0 $$

$$ M(x+1)=x $$

Now, I want to show that $M$ is primitive recursive. How should I go about doing this?

Thanks a bunch!

Answer 1

The definition

A function is primitive recursive if it is in the smallest class $\mathcal C$ that contains:

• $\lambda (x_1 ... x_k).0$, $k \geq 0$
• $\lambda x.x+1$
• $\lambda (x_1 ... x_k).x_i$ for all $1 \leq i \leq k$ (projection/identity)

And such that composition and primitive recursion hold:

• For all $m$-ary $g_1, g_k \in \mathcal C$ and $h \in \mathcal C$, the followint function is in $\mathcal C$:

$$ \lambda x_1 ... x_m.h(g_1(x_1, ..., x_m), ..., g_k(x_1, ..., x_m)) $$

• Given the $(k+1)$-ary function $h \in \mathcal C$ and the $(k-1)$-ary function $g \in \mathcal C$, the following $k$-ary function is in $\mathcal C$:

$$\begin{cases} f(0, x_2, ..., x_k) &= g(x_2, ..., x_k) \\ f(x_1 + 1, x_2, ..., x_k) & = h(x_1, f(x_1, ..., x_k), x_2, ..., x_k) \end{cases}$$

EDIT: note I did not use currying in defining the functions, but I listed the arguments in tuples. This is for simplicity and ease of reading.

The application

In your case you have to define the two functions:

• $g = \lambda x.0$ (zero $\in \mathcal C$)
• $h = \lambda (x_1, x_2, x_3).x_1$ (projection $\in \mathcal C$)

Combine them (primitive recursion) to obtain the binary function $f$ such that:

$$\begin{cases} f(0, x) &= g(x) = 0 \\ f(x_1 + 1, x_2) & = h(x_1, f(x_1, x_2), x_2) = x_1 \end{cases}$$

You now have a function $f$ that behaves like pred, but has the wrong arity. To fix this, you can use composition:

• $i = \lambda x . x$ (projection/identity $\in \mathcal C$)
• $\implies \text{pred} = \lambda x . f(i(x), i(x)) \in \mathcal C$