Изменения

Заметим, что если <tex> f </tex> {{---}} <tex> n </tex>-местная примитивно рекурсивная функция, то она определена на всем множестве <tex> \mathbb {N}^{n} </tex>, так как <tex> f </tex> получается путем правил преобразования из всюду определенных функций, и правила преобразование не портят всюду определенность. Говоря неформальным языком, рекурсивные функции напоминают программы, у которых при любых входных данных все циклы и рекурсий завершатся за конечное время.

*В правиле подстановки можно использовать функции с разным числом аргументов. Например, подстановка <tex> F(x,y) = f(g(y),h(x,x,y)) </tex> эквивалентна <tex> F(x,y,z) = f(g(P_{2,2}(x,y)),h(P_{2,1}(x,y),P_{2,1}(x,y),P_{2,2}(x,y)) </tex>, но если <tex> F </tex> не константная функция то все подставляемые функции должны иметь хотя бы один аргумент.

*В рекурсии не обязательно вести индукцию по последнему аргументу. Следует из того что мы можем с помощью проекторов поставить требуемый аргумент на последнее место.