Изменения

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