Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 67
Текст из файла (страница 67)
В самом деле, вывод формулы (2) о использованием формулы (1) в качвстве исходной может быть осуществлен следующим образом. Сначала из формулы (1) на основании рекурсивного опреде- ления функции 9(й) получается формула ЛЕС(й, г), из которой далее — если для краткости обозначить выражение п(п, 2""'-'"') через с,(п, (, й) — получается формула й(1-м:-)гор(й, е,(г, 1, й), 1, г), а из нее, в сочетании с легко выводимой формулой ф (й, т, (, и) -+- т(2ыа1, †форму (б) Чо(й =о-+-=(и(и(2 оой ")г$(й, и, о, г))). Затем, с помощью полной индукции по г, может быть выведена формула (6) ЧиВуА(и, у)йЧИЧОЧш(А(и, о)йо(ы~- А(и, и)) Ф -~-ЗуЧи(и(г- А(и, у)). Эта формула после подстановки формулы Чх(ь(х-«-Чг 1вт(й, а, х, г)) вместо именной формулы А (а, Ь) и терма 2'"' вместо переменной г — ввиду выводимости формулы, кагор;я получается в результате такой же подстановки в формулу ЧИЧОЧи(А(и, о)йо(ш А(и, го)), Звт зоз МЕТОД АРИФМЕТИЗАЦИИ МЕТАМАТЕМАТИКИ [ГЛ.
[Ч АРИФМЕТИЗАЦИЯ ТЕОРЕМЫ ГЕДЕЛЯ О ПОЛНОТŠ†~мес с формулой (5) и формулой Зо (с «о й й «о) средствами исчисления предикатов дает формулу 3и 11уЛо (у ( о й Мгам (11, и, о, г)), а от нее можно прийти к искомой формуле (2) с помощью фор- мулы (7) л«зйз 1й«т(й, т, 1, и) «РР(й, т, з, ес(п, 1, е)), которая получается на основании выражения, задающего формулу ер(lе, т, 1, и), н рекурсивного определения предиката А1(л, и) с использованием вывода формулы (3) з«1йь[(1, п)-«С(з, с,(п, 1, з)). [Формула (8) выражает тот факт, что если 6 меньше 1, то выполняющее распределение истинностных значений по элементарным подформулам формулы [т[ включает в себя некоторое выполняющее распределение по элементарным подформулам формулы [Р .
— Правда, фактическое осуществление вывода формулы (8) является делом весьма утомительным.) Как уже отмечалось выше'), после вывода формулы (2) могут быть получены и выводы формул (3) и (4). Из формулы (3) мы получаем формулу (0) которая выражает тот факт, что для каждого й значение а(й) представляет выполняющее распределение истинностных значений для 1'11.
Затем мы получаем формулу (10) 11 .,1- АР(й, а(й), 1, а(1)) следующим образом. Из формулы (3) получаем 1<1-+1го(1«о- лг4)(й, а(й), о, г)), а потом, используя формулу (7) и выражение для ат(л, т, 1, и), получаем формулу Ф lг ( 1- Чо [1 ( о - ЗЕЗи (,Р (й, а (л), 1, и) й $ (1, и, о, г))1, которая может быть преобразована в формулу й«1-«Чо[1«- о-« =(и(и(2'"'йч)(й, а(й), 1, и)й :-(г,ф(1, и, о, г))). ') Ся. с.
305. А теперь из этой формулы — снова с помощью формулы (6), в ко- торую на этот раз вместо именной формы А(а, Ь) подставляется формула 'ах(б(хйср(л, а(й), 1, и)-«1Е[г ),Р(1, а, х, г)), а вместо переменной г терм 2"",— сначала получается формула й«1-«ЗЦЧуЗо(у«ой(з(й, а(й), 1, и) йЗгф(1, и, о, г)), а нз нее с помощью (7) формула й(1- Зх($(й, а(й), 1, х) й [ау(1«у-«Эгр(1, х, у, г)). Если теперь терм Р„[[Р (й, а (й), 1, х) й 11[у (1 = у -« ЗгЗР (1, х, у, г))1 мы обозначим через с(й, 1), то получим формулу й -1-э ф(й, а(Й), 1, с(й, 1))й[еу(1«у-+-=)гср(1„с(л, 1). у, г)).
Из этой формулы, используя выражение для „,, „,Й т 1 и, по- лучаем формулу у~1 — а(й) =Р1(с(й, 1), 1, й) и, кроме того, используя (4), мы получаем формулу 11 «. 1-«а (1) - е ([е, 1). А из этих двух формул, взятых совместно, с помощью легко вы- 1Д ОИ фО Г=.з — «Р1(Г, 1, [е) «Р1(з 1 [с) получается формула (11) й «,1 — «е1 (а (1), 1, [с) «а ([с). С другой стороны, формула (3), если в ней подставить 1 вместо е, в сочетании с легко выводимой формулой й «1й 1 «Г. с, (с, (п, Г, 1), 1, й) = с, (п, Г, й) и с использованием выражения для $(е, т, 1, и) дает нам формулу Й«-1-«Чу(1«у- Зг(Р(Й, с,(а(1), 1„Й), у, г)), а затем с по[)сошью (7) формулу уу(й«у-«~г$(й, с1(а (1), 1, й), у, г))> из которой на основе (4) получается ф~рмула (12) й«1 «.а(й) «е,(а(1), 1, й). а г~ АРифглетизАпнн теОРемы геделя О полноте 309 метод Ариометизлции метямлтемятики Егл ги Формулы (1!) и (12), взятые совместно, дают формулу й ( Е -ь а (й) = гг (а (Е), Е, Ег), которая в сочетании с формулой Аз(Е, а(Е)), получающейся подстановкой из (9), приводит нас к искомой формуле (10) Ег ( Š— аз (Ег, а (Ег), Е, а (Е)) Формула (10) выражает тот факт, что если число Ег меньше числа Е, то выделенное распределение истинностных значений для формулы (ч является Ег-компонентой выделенного распределения для формулы ()ь а формулы (9) и (10)„взятые друг с другом, выражают то обстоятельство, что выделенные распределения для фомул г)а (й=О, 1, ...) обьединяются в некоторую модель нашей исходной формулы и.
Разумеется, это истолкование формул (9) и (10) как формул, выражающих некоторую модель формулы 5, представляет собой некий неформальный комментарий. Мы вывели не формулу, представляющую собой какую-либо формализацию утверждения о выполнимости 5„а только некоторые арифметические формулы, интерпретация которых — если взять за основу неформальное понятие выполнимости — позволяет заключить о выполнимости фомулы Я. и рОднако, используя только что построенные нами формальные выводы, утверждение о выполнимости 5 можно усилить до установления некоторого дедуктивного факта, касающегося арифметического формализма. Именно, мы установим выводимость н й неко- торо формулы, получающейся из 5 подстановкой вместо формульных переменных, причем эта выводимость будет иметь место в арифметическом формализме с добавлением новой исходной формулы ч(1) =О, которая, как мы знаем, изображает некоторое арифметическое следствие, вытекающее из нашего допущения о неопровержимости 5.
б) Усиление выполнимости до выводимости. Для того чтобы установить указанную нами выводимость, мы сначала построим такие подстановки вместо формульных переменных формулы К которые будут подходить для модели формулы 5, образованной выделенными распределениями истинностных значений. Рассмотрим какую-нибудь формульную переменную с произвольным числом е аргументов. В качестве аргументйых переменных ее именной формы можно взять переменные а„..., ае, Пусть З(а,, ..., ас) — эта именная форма.
В формулах 3 формульная 1 переменная З всегда входит с какими-нибудь цифрами в каче- стве аргументов. Если и„..., пв — какие-либо цифры и элементарная формула З(п,, ..., и„) встречается в одной из формул 3;, то она является одной из элементарных формул $„..., Зей), н, значит, тогда формула З(п,, ..., пр) совпадает с некоторой формулой З;+, (! (с(1)), имеющей в нашей нумерации номер 1)(1) г). Номером элементарной формулы З(п„..., пр) является число ! О, (з.з"г) . , Ч(з.з з) а где Ч„..., йз суть отличные друг от друга простые числа. Это число, в его зависимости от и„..., и„, с помощью рекурсивной функции 1(а„..., ар) =10.9( ' ').....Ч(з' ") г р изображается термом 1(п,, ..., и„).
Поэтому число г, при котором элементарная формула $г,, г совпадает с З(н,, ..., и„), арифметически может быть изображено термом ') рм(1)(х)=1(п„..., и )), а если воспользоваться определениями !), (а) = Ег„(() (х) = а), 1(а„..., а„) =Е)г(1(аз, ..., а„)), то и термом 1(п„..., пв). Благодаря тому, что выполнено нера- венство Ег(г()г), в формулу 5ь в которую входят элементарные формулы '1гы ..., 7,0), входит и формула ф ьм Поэтому в слу- чае совпадения формулы З(п„..., и„) с формулой $;+, истин- постное значение, получаемое формулой З(п,, ..., и„) при выпол- нении Я с помощью выделенных распределений истинностных значений, можно охарактеризовать как то значение, которое в вы- деленном распределении исгинностных значений для $, принимает формула ~1;+,, 'условие, что это значение представляет собой значение «нстнна», изображается равенством у,(а(г), 1, 1) =О, ') См.
с. 302. ') Зтот терм не является термом рекурсивной арифметики. Число г в его зависимости от и,, ..., из можно было бы изобразить и рекурсивным термом, Во для етого надо было бы указать какую-нибудь оценку для О однако получение такой оценки в данном случае себя не оправдывает. пя хриеметизхция теоремы геделя о полнота зы з!о метод лрифмгтизхции мвтхмхтвмптики ~гл. ш а потому и — в зависимости от чисел и„..., пр — формулой у,(п(1(п„..., пр)), Е(п,, ..., пр), Е(пд„..., пр)) =О.
Поэтому формула у,(п(1(а,, ..., ар)), 1(а,, ..., ар), 1(а,, ..., ар)) =О представляет собой заменитель для формульной переменной 'хг(а„..., ар), подходящий для модели формулы 5, построенной с помощью выделенных распределений истинностных значений. Этим способом мы для каждой формульной переменной с аргументами и без них получим некоторый сопоставленный ей заменитель, который мы будем кратко называ гь с о о т в е т с т в у юш им ей заменителем. Представим себе формульные переменные формулы и выписанными в порядке их первого появления в й, и пусть число этих переменных равно ь Пусть З;(а„ ..., ар) — именная форма формульной переменной, стоящей в этом упорядочении на йм месте, причем число р; может быть равно и нулю. Номер, соответствующий в нашей нумерации формуле З(п„..., пр'1 с циф!) рами и„..., пр в качестве аргументов, изображается, если г; равно нулю, некоторой цифрой Еп а в противном случае — с помощью некоторой рекурсивной функции Е;(ам ..., ар ) термом Е) 1;(и„..., пр); при этом з, ченителем, соответствующим формуль!) ной переменной /о(а„..., ар), будет формула ~!) у, (и (Е; (а„..., а )), Е! (а„..., а„), Е; (аг, ..., ар ) ) = О, где 1;(а„ ..., ар ) определяется равенством Е/ 1,(ам ..., а ) =Е)г(й (а„..., а„)).
Этот заменитель, соответствующий переменной В; (а,, ..., ар 1, ~/ мы будем сокращенно записывать в виде 6~(а„..., ар'!=О, 1) обозначив через 6, (а„..., ар'! терм 1) у,(п (Е, (а„..., а„)), 1,(ад, ..., а„), Е;(а„..., ар)), для которого левко может быть выведена формула 6,!а„..., ар ) = 0 ~7 6, 7аг, ..., ар '1 = !. () '/ 3 а меч а н не. Для правильного понимания встречающихся здесь термов надо обратить внимание на роль, которую играют свободные нндивидные переменные. В то время как терм 1;(и„..., пр'ь где и,, ..., пр — цифры, имеет своим значением !! номер формулы З,(и„..., пр), терм г,(а„..., ар) не изобра- ~/ ,) жает никакого определенного номера, а значит, в частности, н номера формулы З(аг, ..., а ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
