Математическая логика контрольная
Задание:
Доказать, что следующий предикат является (или не является) (примитивно) рекурсивным:
«х есть геделев номер частного случая схемы логических аксиом (10)»
![]() |
Теоретическая часть:
Каждому символу u произвольной теории первого порядка K следующим образом поставим в соответствие положительное число g(u), называемое гёделевым номером символа u.
Предложение3.17. Отношения, которые можно получить из примитивно рекурсивных (или рекурсивных) с помощью пропозициональных связок и ограниченных кванторову также примитивно ре — курсивны (соответственно рекурсивны); применение ограниченных [х-операторов или
к примитивно рекурсивным (рекурсивным) отношениям приводит к примитивно рекурсивным (рекурсивным) функциям.
Доказательство:
;
1) g(x, y)
g(x,0)=1=S(N(x))
g(x, y+1)==
∙ x=f(g(x, y),x)
2) x∙y ζ(x, y)
ζ(x,0)=0
ζ(x, y+1)=x(y+1)=xy+x=f(ζ(x, y)+(x))= f(ζ(x, y)+
(x, y))
3) x=y
Отношение х=у примитивно рекурсивно, так как его характеристическая функция совпадаетс функцией sg(|x-y|), которая в свою очередь примитивно рекурсивна так как:
|x-y|=(x-y)+(y-x) (подставновка) – рекурсия
sg(0)=0
sg(y+1)=1 — рекурсия
4) x*y
Если число х = «представляет» последовательность положительных чисел
, а число у=
«представляет» последовательность положительных чисел
, то число х*у=
«представляет» последовательность
, которая получается, если вторую из данных последовательностей записать непосредственно вслед за первой. Здесь мы имеем k+1=lh(x), m+1=lh(y) и bj=(y)j
Поэтому х*у=, следовательно, функция «*» является примитивно рекурсивной.
5) Пусть R(x, y)- рекурсивное отношение. Обозначим через Q(x, z) отношение R(x, y). Тогда
, где
рекурсивная функция. Ограниченный квантор
равносилен ограниченному квантору
, который в свою очередь может быть получен с помощью подстановки из ограниченного квантора
.
Функция принимает значение 1 при каждом у, для которого R(x, u) ложно при всех
и принимает 0всякий раз, когда существует такое
, при котором R(x, u) истинно.
Поэтому, если для данного z существуют числа у, меньшие чем z, и такие, что R(x, y) истинно, то значение функции равно числу целых неотрицательных чисел, меньших чем наименьшее из таких чисел у; в протвном случае значение функции
будет рано z. но это значит, что
=
R(x, y). Следовательно, применение ограниченного квантора приводит к рекурсивной функции.
Список используемой литературы:
1. Э. Мендельсон. Введение в математическую логику. М., 1971
2. Лекции и семинары