Изменения

: Это правило называется правилом рекурсии,при этом будем говорить что рекурсия запускается по аргументу <tex> y </tex>.

Заметим, что если <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> в правиле подстановки можно подставлять , но если F не константная функция то все подставляемые функции должны иметь хотя бы один аргумент.*В рекурсии не обязательно вести индукцию по последнему аргументу. Следует из того что мы можем с разным числом аргументов и тогда количество переменных от которых зависит результирующая функция будет равно максимальному количеству аргументов среди всех подставляемых функцийпомощью проекторов поставить требуемый аргумент на последнее место.В дальнейшем вместо P_n,k{x_1,\ldots,x_k} будем писать просто, подразумевая требуемое нам <tex> n </tex>.