Суперпозиция частичных функций.

Пусть заданы n частичных функций от одного и того же числа m переменных, определенных на множестве Х со значениями во множестве Y, и пусть на множестве Y определена частичная функция f от n переменных со значениями во множестве Z. Введем частичную функцию g от m переменных на множестве X со значениями во множестве Z, полагая по определению, что выполняется равенство: для произвольных переменных .

Говорят, что функция g получается операцией суперпозиции или подстановки из функций . Оператор подстановки будем далее обозначать символом . В качестве множеств X, Y, Z далее всюду будет браться множество натуральных чисел N.

Например, значение терма не определено, а значение терма , где - символы простейших функций, определенных в предыдущем параграфе.