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