Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 66
Текст из файла (страница 66)
1Р Х1(пт, 1) (между тем как в противном Отсюда получается, что функция »(т) — ~ зяп(Х1(п1, х) — Х1(п1, х )) «< рр числа гп, являющегося номером какой-л "- ибо бескванлы изоб ажает число различных входящих в нее собственных элементарных рмул, и числа 11 в его за висимости от 1 дается функцией «(й) =Х»(((й)). г, нкцня Х1(т, 1) в сочетании с функцией рр, ме а фо м лы ч) как рекурсивной функции ~мыл 1.
Дейстеит ительно, нкцня р»1(х1(т, 1)) для лю ьшего т представляет номер (1+ 1)-и ю егося номером какой-ли скван (р, и для юбогочисла(, меньшегох,(п1), пр из различных со Поэтому для 1( (Ь) значение функции р1(Х1(((й), 1)) в ил нашей нумерации представляет является числом, которое в силу собой номер формулы РЛ)1,1. 4 Я АРИФМЕТИЗАЦИЯ ТЕОРЕМЫ ГЕДЕЛЯ О ПОЛНОТЕ зоз ЗО2 МЕТОД АРИФМЕТИЗАЦИИ МЕТАМАТЕМАТИКИ [ГЛ <Ч Для любого й справедливо неравенство й(с(к) т у каждой фо м лы с , так как " ф р у ы 3! в качестве нового аргумента добавляется по крайней мере одна цифра, а именно 6 ! + 1, а значит, и одна новая, т. е. еще не встречавшаяся в конъюнкции юай...йе» элементарная формула. о Поэтому для любого ! функция 1<(1) =р (Х»(((1), !)) изображает (в рассматриваемой нумерации) номер элементарной ления Далее, используя функцию е(й), можно предс истинностных значений по элементарн дставить распредеарным подформулам формулы 3! с помощью рекурсивной функции тх(т, й, 1) =р(л(т, 2"»'-'ич и), 2), значение которой для любых чисел л<, й, 1, л<...
удовлетворяющих условиям т<2«»< и 1~с(й), равно 0 или ! в зависимости от того, какое значение — «истина» или «ложь»вЂ” » — принимает элеменформула <4)<„т при том распределении истинностных значе- ний по элементарным подформулам формулы 5, к представляется числом л<'). Теперь мы сравнительно легко получим рекурсивное изоб а- жение понятия выполняющего распределе ния истинностных знаизо ра- чений.
Мы определим функцию 7(а (т л, Й, 1) рекурсией: т, л,, ) примитивной Хз(л<, и, Й, 0) т, 'Аз(т, П, й, !')= =<рз(уз(т, п, й, 1), Ч<х(7(а(т, и, й, !), 10-(-20 (л й !))) Если положить по определению й(й, и) =Хз(((й), и, й, г(й)), то для любого значения й и для любого и ( 2'<"' ф б етизб уд ображать номер той построенной из символа (7 с помо ью и функция й(й, п) связок исчисления высказываний форм из формулы 5» в результате внесения того распределения истин- ностных значений по элементарным подформ лам, к т ставляется числом и.
х) О ностиых зна й, ) Отметим, что мы здесь нспольз ем уе. представление распределений истин- ~ачени, отличное от того, кото ым мы пол фе ( 282 283) Зт употреблявшейся там функции у(т, О им, в частности, вызвано и то, что вместо т,(т, й, 7). ии у(т, ) мы вынуждены здесь ввести функцию Результат вычисления этой формулы можно выразить с помощью введенной в предыдущем параграфе функции <ра (л<) '), которая при любом т, являющемся номером какой-либо формуль, построенной из символа Р' с помощью связок исчисления высказываний, принимает значение О, если вычисление этой формулы приводит к значению «истина», и значение 1, если это вычисление дает значение «ложь».
Действительно, каковы бы ни были й и п, предикат п(2"~'й<рз(й()г, а))=0 выполняется тогда и только тогда, когда число и представляет такое распределение нстинностных значений по элементарным формулам 7„ ..., $,<»и при котором формула 5» принимает значение «истинаж Следовательно, этот рекурсивный предикат, который мы будет обозначать посредством к» (й, а), изображает условие, необходимое и достаточное для того, чтобы число и представляло выполняющее распределение истинностных значений по элементарным подформулам формулы 5». Заодно мы получаем, что выполнимость формулы 5», которая, как мы знаем, утверждает, что среди чисел, меньших 2"»', существует число х, для которого имеет место г1(й, х), может быть выражена в виде где <((и) — некоторая рекурсивная функция.
Далее, предположение о том, что для каждого числа Й формула 5» должна быть выполнимой (из которого исходит проводимое в данный момент рассмотрение), оказывается равносильным верифицирйемости формулы (!). й теперь мы можем арифметически изобразить и понятие выделен н ого распределения истинностных значений (правда, уже не в рамках рекурсивной арифметики, а с использованием кванторов и )<-символа). Тем самым мы попадаем в сферу действия того арифметического формализма, который получается из рекурсивной арифметики в результате присоединения исчисления предикатов (в полном объеме), а также распространения на расширенную область формул схемы индукции н добавления )ь-символа с относящимися к нему формулами (!Ах), (р,) и ((хз)з). Этот формализм равносилен рассмотренному в гл. П11 т.
1 формализму арифметики, который получается из формализма системы (Е) в результате присоединения р-символа и формул (<»т), ((Аз) и ((хз). Действительно, как мы показали, в этом формализме с помощью р-символа можно ') См. с. 286. ») См. с. 74 — 75. 898 МЕТОЙ АРИФМЕТИЗАЦИИ МЕТАМАТГМАТИКИ 1гл щ АРИФМЕТИЗАИИЯ ТЕОРЕМЫ ГЕЙЕЛЯ О ПОЛНОТЕ дать явные определения рекурсивных функций, и в силу этих Определений рекурсивные равенства для них станут выводимыми формулами').
С другой стороны, аксиомы системы (Е) выводятся в упомянутом ранее формализме'), получающемся расширением рекурсивной арифметики. Как было показано ранее, вместо того чтобы вводить р-символ вместе с формулами ()А,), (р,) и (у,) прямо в формализм, можно было бы поступить иначе: а именно, можно было бы добавить к формализму системы (2) ыправило, с помощью которого р-символу можно дать явное определение, в результате чего формулы (р,), (р,) и (ра) окажутся выводимыми').
Искомое представление понятия выделенного распределения мы без труда получим с помощью предшествующих рекурсивных определений из содержательного определения этого понятия. Выделенное распределение истинностных значений по элементарным подформулам формулы 51 — это такое выполняющее распределение истинностных значений, которое для любого числа 1, большего 1, представляет собой Е-компоненту некоторого выполняющего распределения истинностных значений по элементарным подформулам формулы 51,' а среди этих последних оно характеризуется тем, что число, представляющее его, является наименьшим.
А теперь высказывание «т является числом, представляющим й-компоненту некоторого, представленного числом и выполняющего распределения истинностных значений по элементарным подформулам формулы 5«а изобразится формулой й =(й11(1, и) йт=п(п„2«ш — ''м>), которую мы будем кратко обозначать посредством зз(й, т, 1, и). После этого представляющее число выделенного распределения истинностных значений по элементарным подформулам формулы 1«1 может быть охарактеризовано как наименьшее среди таких чисел т (меньших 2«(~)), что для каждого числа 1, большего нли равного 1, существует число и, меньшее 2'и', для которого имеет место ср(1, т, 1, и). Таким образом, оно изображается (в зависимости от 1) следующей, определенной с помсщью («-символа, функцией: а(й)=)«Чу(й-=у- Ь2«р(л, х, у, г)>.
Конечно, соответствие между этим формальным определением и 9 См. ь 1, с. 499 — 5Ю. «) См. т. 1, с. 368 — 369. а) См. Приложеаае 1, с. 468 и далее. понятием числа, представляющего выделенное распределение истинностных значений, пока усматривается только на основе содержательного смысла р-символа. Чтобы убедиться, что в ариф- метическом формализме это Определение может быть использовано аналогично соответствующему содержательному понятию, мы должны проверить, что в арифметическом формализме выводима формула (2) ЧЛЧу(й=-у-+.агат(й, х, у, г)), нз которой затем на основании определения функции е(й) и фор- мул (р,) и (р ) могут быть получены формулы (3) Чу (й ( у — Зг,р (й, а (й), у, г)) и (4) Чу(Уг(у-е.'Згф(Ь, т,'у, г))- а(Ь) =-т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
