Пример 2

Функция оⁿ: Nⁿ  N, все значения которой равны нулю, примитивно рекурсивна, ибо она является композицией о  Iⁿ₁ простейших функций Iⁿ₁: Nⁿ  N и о: N  N. Рассмотрим при k    1 функцию c_k: Nⁿ  N, все значения которой равны k. Функция c_k равна композиции функций оⁿ: Nⁿ  N и k функций N  N … N, каждая из которых равна s, c_k  =  s^k oⁿ. Стало быть, c_k примитивно рекурсивна.

Пример 3

Функция f: N²  N, заданная как f(x,y)  =  x + y, удовлетворяет соотношениям:

f(x,0)  =  x;

f(x,y + 1) =  (x + y) +1  = f(x,y) + 1  = s(f(x,y)).

Положим: g(x)  =  I¹₁(x)  =  x, h(x,y,z)  =  s(z). Так как f(x,0) = g(x) и f(x,y + 1)  =  h(x,y,f(x,y)), то f  =  R(g,h) = R(I¹₁,s  I³₃). Значит, f – примитивно рекурсивна.