Кусочное задание функции.

Пусть задана совокупность функций и совокупность предикатов , где и , причем области истинности предикатов попарно не пересекаются.

Введем следующие обозначения: .

Определение. Говорят, что функция задана кусочным образом относительно заданной совокупности функций и предикатов, если она удовлетворяет следующим условиям:

,

Теорема 4. Функция f(x), заданная кусочным образом из совокупности , является ПРФ относительно ψ

Доказательство.Пусть представляющая функция для предиката p_i(x), где . Тогда покажем, что функцию f(x) можно представить следующим образом . (32)

1) Рассмотрим произвольный набор .

Пусть для какого – то предикат , где . Тогда по определению представляющей функции предиката, получаем, что , следовательно

а для всех остальных i¹i₀ , p_i(x₀)=л, отсюда

.

Таким образом, в данном случае, мы получаем, что

.

2) Предположим, что для любого i, , тогда , где . Следовательно, , а

Из пунктов 1–2 следует, что на множестве функция

совпадает с функцией , которая задана кусочным образом из совокупности ψ. Так как операции конечного суммирования и конечного произведения сохраняют свойством примитивно рекурсивности функций, следовательно, рассматриваемая функция является ПРФ относительно ψ. Ч.т.д.

Лемма 1.1. Подстановка примитивно рекурсивной функции в предикат равенства есть примитивно рекурсивный предикат.

Доказательство. Пусть заданы примитивно рекурсивные функции и пусть – предикат равенства.

Рассмотрим предикат вида .

Он является примитивно рекурсивным предикатом. Действительно, для данного предиката представляющей функцией является функция вида ,

которая является ПРФ.