Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 68
Текст из файла (страница 68)
Номер этой формулы не изобра- жается и тем термом, который получается из терма 1, (а,, ..., ар 'ь если в нем вместо свободных переменных подставить номера, со- поставленные в нашей нумерации переменным а„..., ар. Так, например, номер формулы А (и) в его зависимости от цифры п изо- бражается термом !О 7(' ' ); роль Е(а) здесь играет функция !0.7('"), а номером переменной а является число !4. Однако номером формулы А (а) является не число !О 7<г г"', а число 10.7м. Формулу, получающуюся из 5 в результате подстгновки вме- сто формульных переменных соответствующих им аменителей, мы будем обозначать посредством 5*.
Она имеет гнд г/дг гг/Е,ЭВг" Зг)га" (Зг, ", р1), где выражение г)" (х„..., р,) получается из 3(хм ..., 1)г) в результате указанных подстановок. Далее, формулу З(ам ..., ар, 6 г) (а„..., а„)+1, ..., д.г) (а„..., а,)+ 6) мы обозначим посредством !т, а получающуюся из нее в результате указанных подстановок формулу 6' (а„..., а,, д Ч(а„..., аг)+ 1, ..., 6 т)(а„..., аг)+6) посредством /;*.
Мы покажем, что формула (Е* может быть выведена в формализме арифметики с добавлением верифицируемой формулы и(/г)=0 в качестве исходной. Для этого достаточно показать, что в указанном формализме выводима формула 5", так как от формулы 5р можно легко перейти к формуле 5" средствами исчисления преднкатов. Мы разобьем это рассуждение на несколько этапов. 312 МЕТОП АРИОМЕТИЗАЦИИ МЕТАМЛТЕМАТИКИ ггл !у З1З 1. Функция Ь(й) была определена') выражением 0о(Ч»(й)., Ч,(и), б )г+1, ..., б й+6), где функция 0, обладает тем свойством, что для любых чисел пг...., и,+о значение выражения 0о(п„..., н„ггт ьи ..., и„+о) равно номеру формулы З(иг, ..., и„, гт,+„..., И„„о). Имеют место равенства т),(т)(а„..., а,)) =а„..., Ч,(Ч(а,, ..., а,)) =а„ которые могут быть выведены на основании рекурсивных опре- делений функций Ч, Ч,, ..., Чс Из них мы получаем равенство Ь(т)(а„..., а,))= =0,(а„..., а, 6 Ч(а„..., а„)+1, ...,+6 т1(а„..., ат)+е), а заодно получгется, что для любого т-членного набора цие)р и„..., и, терм Ь(т)(п,, ит)) изображает номер той формулы 'тг(гт„..., п„1„..., 1,), у которой цифры 1„..., 1, представляют собой значения терман 6'Ч(п» ..
пс)+1 ... б'Ч(пт ... п)+6. 2. Мы можем Определить функцию 9»(з, и, )г), которая для любой тройки чисел 3, и и й, удовлетворяющих условиям и й, и -2«»>, в качестве значения принимает номер той формулы, КОтОРаЯ ПОЛУЧаЕтСЯ НЗ ФОРМУЛЫ тлг, В РЕЗУЛЬтатЕ ВНЕСЕНИЯ В НЕЕ представленного числом и распределения истинностных значений по элементарным подформулам формулы 5», так что для любой тройки чисел 3, и, й упомянутого вида значение функции ер»(9»(и, и, й)) равно 0 или 1 в зависимости от того, какое значение — «истина» нли «ложь» — принимает формула З«при представленном числом и распределении нстинностных значений для формулы 11».
Действительно, сначала мы положим ()а(а, гг)= М(п (Ь(х) =а), «<е<М Если й — какое-либо число, а а — номер какой-либо входящей в 5» элементарной формулы ег), +, (в смысле нашей нумерации), то значение функции ()а(а, й) равно 1. Связь между рекурсивной ») См. с. 299 и далее. АРтив»тетиздция теОРемы геделя О полиотг фУнкцйей Ьт(а, й) н фУнкцией 1;,(а) (котоРаЯ ОИРеделена не Рек урснвно ')) выражается выводимостью формулы (13) Зх(Ь(х) =абел(е(й)) — Ь. (а, й)=Ь»(а).
Затем, аналогично тому, как мы ранее определили функцию )(о(ги, и, lг, 1), определим рекурсивную функцию 9„(з, и, й, 1) с помощью рекурсивных равенств а„(5, и, й, 0)=Ь(Р), ро (3, и, й, Г) = еР»(йо(и, и, й, 1), «Рт (9о(и, и, )г, 1)), 1О+ +20 у,(и, й, 1)а(ерг(9о(и, и, й, 1))). Искомую функцию 9»(и, и, й) мы теперь определим с помощью функции ро(и, и, й, 1) равенством 9»(з гг )г)=йо(з и, й, Ь(и)). Заодно для произвольных чисел з, и, )г, 1, удовлетворяющих условиям э()г, и(2'м' и 1(е(й), функция ер,(9,(и, и, й, 1)) выражает номер (в смысле нашей нумерации) (1+1)-й из входящих г), элементарных подформул, упорядоченных по их первому появлению в этой формуле.
Из рекурсивных определений функции 9»(и, и, й) и предиката ьг()г, и) выводится следующая формула'): (14) г1(lг, и)- (Е.=.й- еР»(9»(а, и, )г))=0). 3. Как было показано ранее'), с помощью формулы 9(й) =0 может быть выведена формула Е1(гг, «(й)), которая вместе с формулой (14) дает нам (15) з~)г- ера(гтг(з, «(й), й))=0.
Затем из формулы (10) )г -1-«$()г, «(й), 1, «(1)), которая„как мы установили'), выводится с помощью формулы 9(гг)=0, на основе определений формулы гр и функции тг получаем (10) а е(й)бг)г(1«у»(«(й), й, а) =у,(«(1), 1, а). 4. Мы сложим термы 1; (аи ..., ар ), сопоставленные различным ! входящим в формулу 5 формульным переменным'), и к полу- ~) См. о. 309. а) Вывод формулы (141 является, впрочем, довольно длиииым.
»1 См. с. 306 и далее. »] См. с, 309 и далее. 3!4 мгтод лгиФметизжши мгтлмлтемлтики !гл ш ы , а,) ). остроенный чнвшейся сумме прибавим терм е)(а ..., )'. П таким образом терм, который не со е жи д р т никаких свободных „, мы обозначим посредством х, отличных от а, ... а в а„..., а„), Из способа построения этого терма непосре с получаются фо я формулы о редственно (17) 1;(а, ..., а„,)л-в(а„..., а,) (1=1, ... !)„ еЕ(ам ..., а,) (в(а,, ..., ас). Формулы (17), взятые совместно с фо м лой й<е(й), дают равенства формулой (16) и формулой у, (л (1! (а,, ..., а„)), Е! (ам ..., а„)„1 (а„..., а„)) = =7,(а(в(ам ..., а,)), в(а,, ..., а,), Е,(а„... а Ф Р )), ' (ае ° ° ., ОР ) = 7~ (а (в (ам ° ° ., ае)), в (а„ ...
а ) (18) д (а, ... с* Е;(а„..., а )) (! С другой стороны, из фо м лы (15) в ф (17' ) мы получаем равенство (19) а, ... ) ере(9,(е)( „..., а,), а(в1(а„..., а,)), в(а„..., а,)))=0, 5. Тепе что ы с помощью рь наша задача сводится и тому, б формул (13), (17) — (19) вывести формулу 5*. С этой целью мы а как оно было дано с помо ью , ы рассмотрим ойределение функции (з,, й) Ь Е) , л...
Если мы подставим в эти равенства вместо и термы е! (аь ..., ае), а (в (а„..., ас)) и в(а„..., а„), то для функции йо(т)(ам ..., ае), а(в(ам ..., ас)), в(а„, ..., а,), Е), которую мы обозначим посредством 9 (а, ..., Е) м ..., а„), получим следующие рекурсивные равенства: 3,(а„..., а,, 0) =Ь(е)(ам ..., а,)), йе(ам ..., а„, Е') =ере(йе(ам ..., а„Е), ер,(йе(а» ... а, Е)) 10+20 у,(а(в(а„..., а,)), в(а,, ..., а,.), !)4(ер,(й!4(им ..., а„Е)), в (а„..., ае)))). 4) См. с. 228.
4 Е! АРИФМЕТИЗЛЦИЯ ТЕОРЕМЫ ГЕДЕЛЯ О ПОЛНОТЕ 8!5 Теперь с помощью этих равенств можно вывести формулу ер, (йе (а„..., ае, Е)) = 0 !Е лх(Е)(х)=ер,(йе(ам ..., О„Е))8ех -е(в(а„..., а,))), из которой ввиду формулы (13) получается формУла Че(йе(ам ..., Ое Е))=0 ~/ ( ~ (й (а а Е)) ве(ат, а )) Ь (ер (9 (ат а Е))) С помощью этой формулы и равенства ер,(т, О, г)=т, выводи- мого из рекурсивного определения') функции ер,(пе, а, Ь), мы из рекурсивных равенств для й,(а„..., ас, Е) получаем формулы 9 (а„..., а„О) = 5(е) (а„..., а„)), (20) йе(а,, ..., ас, Е')=<ре(8,(ам ..., а„, Е), ч.,(йе(ам ..., а„Е)), 10+20 у, (а(в(а,, ..., ае)), в (а„..., а,), 1)т(ер,(йе(ам ..., ае, Е))))).
Вторая из этих формул в использованием равенства ере(т, О„г) =т дает формулу (2!) ер,(9,(ам ..., а,, Е))=0-Ф 9,(а„..., ас, Е)=9,(ам ..., ае, Е); кроме того, с использованием равенств, определяющих функции 1,(а, ..., а„) (1=1, ..., !), н равенств (18) получаются фор- мулы (22) ер,(й,(а„..., О„Е))=1,(ам ..., а„)лйе(ам ..., ае, Е') =ере(94(ам ..., а„Е)„1;(а„..., а„), 10+20 6,(ам ..., а„)) (1=1, ..., !), ! Далее, на основании определений функций й, (з, и, й) и йе(а,, ..., а„Е) формула (19) может быть переведена в формулу (23) р, (а, (а„..., а„Ь (т! (а„..., а„)))) = О. б. Пусть Ь*(т1(а,, ..., а„)) обозначает терм, получающийся из Ь (е! (а„..., а,)) в результате замены каждого из термов 1 (а,, ..., аР ), связанных с элементарными подформулами ! ТВ (а„..., а„) формулы $, соответствующим ему термом 10-1- + 20 8,(а„..., ае ).
Тогда из формул (20) — (22) с помощью вы- 1) См. с. 285. З>7 з>а метод АРифметизАции мгтАмАтсмАтики <гл. 1ч АРИФМЕТИЗАЦИЯ ТЕОРЕМЫ ГЕДЕЛЯ О ПОЛНОТЕ ражения для <0, т. е. для 2>(а>ь ..., а<, д 7)(а„..., а<)+1, ..., а 71(а„..., а<)+6), по правилу дизъюнкции, которое, будучи истолковано содержательно, сводится к разбору различных возможностей, касающихся графических совпадений и различий между элементарными подформуламн данной формулы Э (п>, ..., и„, 6 7! (пз, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
