Примитивно-рекурсивные функции. Доказать, что функция примитивно-рекурсивная

если погуглить, то окажется, что функция называется примитивно-рекурсивной, если она может быть задана при помощи такого правила:
{ f(x₁ ... xₙ, 0) = примитивно-рекурсивная функция от x₁ ... xₙ
{ f(x₁ ... xₙ, n+1) = примитивно-рекурсивная функция от x₁ ... xₙ, n и f(x₁ ... xₙ, n)

кроме того, постулируется, что примитивно-рекурсивными являются следующие функции:

• тождественная константа:

O() ≡ 0
т.е., функция, которая всегда выдаёт ноль

• функция следования:

S(n) = n+1
т.е., функция, которая на выход подаёт увеличенный на единицу аргумент

• функция выбора:

I[k](x₁ ... xₙ) = xₖ
т.е., функция, которая возвращает k-й элемент переданного на вход кортежа

• а также суперпозиция примитивно-рекурсивных функций.

из этого сразу получается, что все константы являются примитивно-рекурсивными.
например, константу 3 можно представить в виде: 3() ≡ S(S(S(O())))

сложение двух чисел ⊕(x, y) также является примитивно-рекурсивным:
{ ⊕(x, 0) = x
{ ⊕(x, y+1) = I[3](x, y, S(+(x,y))

используя эти сакральные знания, можно показать, что и f(x) = 3x, то есть, функция, возвращающая утроенный аргумент, тоже является примитивно-рекурсивной:
{ f(0) = O()
{ f(x+1) = I[2]( x, ⊕(3(), f(x)) )
или так, без использовпания функции сложения:
{ f(0) = O()
{ f(x+1) = I[2]( x, S(S(S(f(x)))) )