Пусть σ(х,у)=х+у и ρ(х,у)=х·у для любых натуральных х, у. Доказать примитивную рекурсивность функции относительно совокупности функций { σ, ρ, Cnq } для подходящих n и q.

Следует показать, что функция сложения q(x,y)=x+y примитивно-рекурсивная функция.

Действительно, q (x,0) = x + 0 = (x) (функция здесь это базовая примитивно-рекурсивная функция, сопоставляющая упорядоченному множеству из n переменных q-ую по очереди переменную).

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