2020-04-12
264
Над предикатами, заданными на множестве натуральных чисел N будем использовать операции отрицания (), конъюнкции(^), дизъюнкции(
, импликации(→) и эквивалентности, а также ограниченные кванторы:
Например, запись 
означает предикаты «для любого у такого, что y<z и 
».
Теорема. Предикаты, которые можно получить из примитивно рекурсивных(или рекурсивных) с помощью логических операций и ограниченных кванторов также примитивно рекурсивны (соотв. рекурсивны).
Подстановка функции в предикат используется при доказательстве примитивной рекурсивности функций, заданных кусочно.
Определение: функция 
называется кусочно заданной, если она удовлетворяет условиям:
При этом предполагается, что для каждого набора 
значений переменных истинно одно и только одно из высказываний 
.
Теорема. Если функции 
и предикаты 
примитивно рекурсивны (рекурсивны), то функция примитивно рекурсивна (рекурсивна).
