10. Сохранение свойства всюду определенности функций,
т.е если 
и 
всюду определенные функции, то 
тоже будет всюду определенная функция,
где f=R(g,h).
Доказательство. Берем произвольный набор 
и докажем, что на этом наборе функция f определена. Доказательство проводим методом математической индукции по y.
1 шаг. Пусть y=0. Тогда по определению операции ПР получаем, что 
Так как функция g всюду определенная функция по условию, то функция f определена на наборе 
.
2 шаг. Предположим, что функция f определена на наборе
3 шаг. Доказываем что функции f определена на наборе 
.
По определению операции ПР получаем, что
.
А функция h обладает свойством всюду определенности по условию. Следовательно, функция f определена на наборе . Так как функция f является арифметической функцией, то метод математической индукции позволяет сделать вывод, что она всюду определена.
20. Сохранение алгоритмической вычислимости функций, т.е.,
если 
и являются алгоритмически вычислимыми функциями, то $ алгоритм 
, вычисляющий функцию , гдe
: 
.
