Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 60
Текст из файла (страница 60)
Терм з|п1 изображает арифметическую функцию своих аргументов, однозначно определенную рассматриваемым рекурсивным предикатом, в то время как в изображении этого предиката равенством 1= 0 арифметическая функция, изображаемая термом 1, определяется этим предикатом не однозначно. 8. Если р„..., 41« — взаимоисключающие друг друга рекурсивные предикаты, т. е. если никакие два нз ннх не выполняются одновременно ни для одного набора значений аргументов„ и если е„..., е«, е — какие-либо рекурсивные термы, то функция, зависящая от аргументов, фигурирующих в 7„..., ф«и дм ..., е, е, и определяемая условием, что для любой системы значений своих аргументов, для которой имеет место ()),, ее значение равно значению терма е,, для любой системы значений аргументов, для которой имеет место 7«, ее значение равно значению терма е,, ..., для любой системы значений аргументов, для которой имеет место 7«„ее значение равно значению терма е«, а в остальных случаях ее значение равно значению терма е, рекурсивна.
Действительно, рекурсивные предикаты $„..., '~1«изображаются некоторыми равенствами 1,=0, ..., 1„=О с рекурсивными термами 1», ..., 1„, из которых, по предположению, никакие два не принимают значения 0 для одной и той же системы значений аргументов; а потому функция, удовлетворяющая приведенному выше условию, изображается выражением Е, зйп1,+Е» зйп 1„+...+Е, зйп 1„+Е зйп(1,....
1,) и, значит, является рекурсивной. 9. Любую рекурсию пробега'), т. е. любое рекурсивное определение вида 1 (а„..., ап 0) = а (а„..., а1), ((а„..., ап и') =. -1 (а„..., а1, п, 1(а„..., а1„1«(и)), ..., ((а„..., а1, 1,(л)), где (( ) — вводимый функциональный знак с 1+1 аргументом, а(а„..., а~) и 1(а„..., ап с„..., с„) — рекурсивные термы, а 1, (и), ..., 1„(и) — рекурсивные термы, удовлетворяющие соотношениям 1, ( и) -:-.
и, ..., 1«( и) -=. и, можно свести к примитивным рекурсиям. Рекурсия пробега может быть сформулирована также и в следующей форме: ((и,, ..., иь 0) = а(а,, ..., а«), пчьО- 1(а„..., аь и)=Ь(а„..., а1, и), ((а,, ..., ап е,(и)), ..., ((а,, ..., аь е«(п))), где (рекурсивные) термы е, (и), ..., е«(и) при и чь 0 должны удовлетворять условиям ег (и) ~ и.
3 а м е ч а и и е. Утверждения 1 — 9 формулируются нами не как сугубо формальные теоремы рекурсивной арифметики, а с исполь') См, т. 1, с. 402, 277 МЕТОД АРИФМЕТИЗАЦИИ МЕТАМАТЕМАТИКИ АРифмет!«зьпия исчисления пгглиелтов 4 !! !гл ъй зованием содержательной финитной арифметики, которая„ как мы знаем, может быть формализована в рекурсивной арифметике '). Так, мы говорим о функциях и о их значениях, о предикатах и о том, что они имеют место, и т.
п. Этот способ выражаться здесь оказывается пригодным потому, что в настоящем рассмотрении нам важно с помощью наших нумераций перевести в арифметический формализм содержательно устанавливаемые летаматемотические отношения. в) Арифметизация понятия формулы. После проведенных приготовлений мы возьмем какое-нибудь метаматематическое понятие, и, пользуясь им как примером, продемонстрируем наш способ перевода на язык рекурсивной арифметики. Остановимся на понятии формулы исчисления высказываний. Этому понятию соответствует свойство числа быть (на основании нашей нумерации) номером некоторой формулы исчисления высказываний. Этот числовой предикат «число л является (в соответствии с нашей нумерацией) номером некоторой формулы исчисления высказываний» вне зависимости от способа нумерации мы можем определить следующим образом: «число п является либо номером какой-либо формульной переменной без аргументов, либо номером отрицания какой-либо формулы исчисления высказываний, либо номером конъюнкции или дизъюнкции, или импликации, или эквивалентности каких-либо двух формул исчисления высказываний».
Правда, сказанное еще не дает нам явного определения, так как определяемое понятие номера формул ы исчисления высказываний входит в определяющее выражение. Но при этом мы все-таки получаем некоторое рекурсивное определение. Действительно, арифметический перевод сформулированного определения выглядит следующим образом: «Число и является номером формулы исчисления высказываний, если оно либо имеет вид 10 р, где р — простое число, большее 5, либо имеет вид З.Ь, где Ь вЂ” отличное от 0 число, являющееся номером некоторой формулы исчисления высказываний, либо имеет вид 1 7'11', где ! — одно из чисел 40, 80 и 160, а а и Ь являются номерами некоторых формул исчисления высказываний».
Если определяемый нами числовой предикат обозначить через Ф(п), то это определение можно будет изобразить следующей эквивалентностью: Ф(п) (10~ад!Рг(л(л, 10))йЛ(л)=зЗ) ъ~ (3(пЬФ(п(п, 3)) Ел~о) Ъ7 (т(п. 0))! З:ъ(п, 0):=5дт(п, 1)=ох, т(п, 2) =1о!Ф(ъ(п, 3))в!Ф(т(л, 4))4«Л(л) 4). О См. т. 1, с. 400. Эту эквивалентность можно легко превратить в рекурсию пробега для некоторой функции !(п), с помощью которой предикат Ф(л) изобразится в виде ((и) = О. Действительно, сначала из этой эквивалентности получится (дедуктивно или содержательно) ) Ф(0), а тем самым и Ф(0) 1 =О.
Следовательно, мы можем положить 1(О) =1. Если теперь мы добавим к указанной эквивалентности в каче- стве посылки формулу л ~ 0 и опустим во втором дизъюнктивном члене ее правой части условие п~О, заменим каждое выраже- ние Ф(з) равенством !(Е)=0 и затем переведем всю стоящую в правой части эквивалентности формулу в формулу вида 1=0, то в результате получится следующая формула: лФО-~[((п)=0 [р(п,!0)+(п(п,!О) — 'Ръ! !,!»!!)+(3 — 'Л(п))] [р(л, 3)+((п(п, 3!)].[(2 — - т(п, 0))+(ъ (и, 0) — '5)+ ъ!(л, 1)+(т(п, 2) — ' 1)+(1 - т(п, 2))+((т(п, 3))+ ! (т(п, 4))+(Л(п) -'- 4)+(4 — ' Л(п))]=0).
После этого предикат Ф(п) можно выразить в виде ър(п)=0 с помощью функции Ч!(и), определяемой следующей рекурсией: ч (О) = 1, !ъ Ф В -+. <Р (л) = [Р (п, ! 0) + (л (и, 1 0) — ' 1»ъ ! „оь ъь! >) + (3 — 'Л(п))] [р(п, 3)+ър(л(п, 3))] [(2 — ъ (л, 0))+ (т(л, 0) — '5)+т(п, 1)+(т(л, 2) — 1)+(1 — 'т(п, 2))+ <р(ъ!(л, 3))+Ч!(ъ!(л, 4))+(Л(п) ' — 4)+(4 — 'Л(п))]. Но эти две формулы представляют собой рекурсию пробега. Действительно, вторая из них имеет вид лчьО-~<р(!!) = (!(и, «р(п(п, 3)), Ч!(Р(!ъ, 3)), Ч!(т(л, 4))), где ! (и, а, Ь, с), л(л, 3), т(п, 3) и т(п, 4) суть рекурсивные функции и для о~О выполняются неравенства л(л, 3) ( и, т (л, 3) ( п н ъ! (л, 4) < л.
Таким образом, для понятия формула исчисления вы с к аз ы за н и й арифметическая формализация (на основе нашей нумерации) может быть произведена с помощью некоторого рекур- 27В мвтод»лнэл)ятиз»пии метлмктгмхтики Сгл. )ч сявного определения. Используемый здесь вид рекурсии — рекурсия пробега — не является самым общим из числа тех, с которыми нам придется иметь дело при арифметизации метаматематических понятий.
Однако и все те более общие типы рекурсий, которые здесь будут встречаться, аналогично рекурсии пробега могут быть сведены к примитивной рекурсии. В качестве примера, иллюстрирующего эту мысль, мы разперем арифметизацию понятия терм, причем это понятие мы пределим для того формализма„для которого была введена паша нумерация, т.
е. для исчисления предикатов с добавлением цифр и функциональных знаков. Выражение этого формализма является термам, если оно либо является свободной индивидной переменной или цифрой, либо представляет собой функциональный знак с термами и качестве аргументов. Замечание. Под выражением формализма здесь понимается такая построенная из символов и переменных формализма фигура, которая является либо формулой, либо такой составная частью формулы, у которой каждый знак, снабженный местами для аргументов, содержит соответствующие аргументы, а каждый логический символ содержится вместе с областью или с областями, на которые простирается его действие. В соответствии со сказанным выражение рассматриваемого нами формализма либо является термам или формулой, либо получается из терма или йз формулы в результате замены некоторых свободных переменных связанными.
Поэтому на основе произведенной нами нумерации полу-, чается, что число является номером какога-либо терма тогда и только тогда, когда оно является либо умноженным на 2 простым числом, ббльшим 5; либо умноженной на 2 степенью числа 3; ли о умноженным на 5 произведением степеней простых чисел, ббльших или равных 7, причем показатели этих степеней суть номера каких-либо термов. Если перевести эту содержательную формулировку в формализм рекурсивной арифметики, то для предиката «число и является номером некоторого герма», который мы будем обозначать символом Тсп(п), получится следующая эквивалентностсп Тш(л) (2~пйрг(л(п, 2))В)Л(л)р=3) )/ (ч (п, 0) = 1 й Л (п) =.= 1) )/ (т(л, 0) =*Ой)ч(п, 1) =ОВст(п, 2) =1В)Л(п) ~ЗВ) Ух(х(п- ч(п„х)=0 ~ х 2 ~/ Тш(ч(п, х)))).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
