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