Гильберт, Бернайс - Основания математики. Логические исчисления и формализация арифметики (947375), страница 100
Текст из файла (страница 100)
»уу (у~(а Ь = с (шой (у' Й + 1))) и >Уу (Ь вЂ” = с (шой (у' й + 1)) 81 с = — р (и, у' ° 1 + 1) (шой (у' Й + 1)) -э Ь = р (и, у' ° 1 + 1>) (шой (у' Й + 1))) мы выведем формулу тсу (у( а -». с = р (т, у'. Х + 1) (шой (у'-й + 1))) А Ь = с (шой шп15„(х'.Й + 1; а')) А Ь = р (и, а™ 1+ 1) (шой (а" Й + 1)) -~ 'чу (у( а' -э Ь = — р (т, у' 1 + 1) (шой (у' Й + 1))) Объединив полученные нами формулы, мы придем к шп11 (х'; п') ! й А а < п -». (3х'зу (у ( а — х — р (т, у' ° 1 + 1) (шой (у' й + 1))) »- Зхуу (у (а' — >- х = р (т, у' 1 + 1) (шой (у' Й + 1)))); но это как раэ и есть та формула, которую мы сокращенно записали в виде 11Аа<я-э (В(а)-»-В(а')). Из нее мы получим также и формулу (сс А а ( и -»- В (а)) -» (Ц А а' ( и -».
В (а')), Тем Самым ивдукцией по а мы получаем формулу Ц А а ( и ». В (а), т. е. шп1$„(хс1 п') (Й А а(п -» 3х1>у(у<а — »х= р (т, у'.1+1) (шой (у'.й+1)))„ СВЕДЕНИЕ К ЯВНЫМ ОПРЕДЕЛЕНИЯМ 507 500 пОнятие»тОт, кОтОРый» и еГО устРАнимость [Гл. ч[п Если мы подставим в нее п вместо а, то в посылке можно будет опустить член и(п и таким образом мы получим шп11„(х'; и') ~ Й-» Зх[[у (у(и » х = — р (т, у' ° 1 + 1) (шо[] (у' й + 1))). еще раз формулу ] й) -» Рг1ш (пш1[х (х' й + 1; т), т' Й + 1), раз и' вместо т.
Воспользовавшись снова фор- 'Теперь применим [;[х (х ( т -» х' подставив на этот мулами г ( и' -» г' ] пш11х (х', п') г' ] шп]1 (х', и') А шп1[„(х', п') ] Й -» г' ] Й, мы получим формулу шп1$„(х'; и') ] й -» Ргпп (шпПх (х' й + 1; и'), и".Й + 1). Потом возьмем (см. с. 505) формулы Рпш ([пп11х (х' й + 1; и'), и" й + 1) -» Зг (г = с (шо[] пшПх (х' й + 1; и')) А г = Ь(п, р (т, и' 1 + 1)) (шо[] (и' Й + 1))) получим' формулу а = г (шо[] (с' й + 1)) А г(й -» г = р (а, с' Й + 1). Объединив эту формулу с полученной ранее, а также с формулой 7у(у(п-»р(т, у' 1+1) (шах р(т, х'.1+1) х<х' Ь = с (шо[] пшПх (х' й + 1; и')) — » ~/у (у(п Ь = — с (шо[] (у' Й + 1))). Подставив в них р (т, у' 1+ 1) вместо с и добавив к ним предыдущую формулу, мы получим в итоге формулу шс1$„(х', п') ] Й-1- Зх [7у (у(п -» х = р (т, у' 1 + 1) (шо[] (у' й + 1))) А х = Ь (п, р (т, и' 1 + 1)) (шо[] (и' й + 1))].
Воспользуемся, кроме того, формулой а = г (шо[] Ь) А г ( Ь -» г = р (а, Ь); если мы подставим в нее с' й + 1 вместо Ь, то, используя формулу й(с' й+1, мы придем к формуле шп1$х(х'; п )[ЙА шахр(т, х' 1+1)(ЙА5(п, р(т, и'.1+1))(й х<х' -+. Зх 7у (у= п — р (х у'. й+ 1) = р (т. у' 1.-' 1)) Ар(х, и" й+1) = Ь(п, р(т, и' 1+1)). Опираясь на выводимую формулу Зи(шп1[х(х'1 и')]иАшахр(т, хг 1-]-1) (и А х<х' Ь(п р(т и'.1+1))-(и). мы перейдем от этой формулы к формуле ЗиЗх (Ру (у ( п -» р (х, уг и + 1) = р (т, и' 1 + 1)) А р (х, и".
и + 1) = Ь (и, р (т, и'.1 -]- 1))); иа этой формулы мы сначала получим формулу ЗхЗи(р(х, и+1)=р(т, 1+1) А 7г (г'.( п -» р (х, з" и + 1) = р (т, г" 1+ 1) ) А'У ( ( р(, г' +1)=р(т, ' 1+1)) Ар(х, и' и+1)=р(т, п' 1+1) Ар(х, и" и '-1) =Ь(и, р(т, п'.1+1))), а отсюда, далее, получим р (т, 1+ 1) = а А. Чг (г п — » р (т, г". 1+ 1) = Ь(г, р(т, г'-.1+1)))-»ЗхЗи(р(х, и+1) =а АЧг(г(п'-».р(х, г .и+1) =Ь(г, р(х, г[ и+1)))). А эта формула с помощью исчисления предикатов немедленно дает формулу Я (и) -» Я (и'), вывод которой мы и стремились получить. После этого индукцией по п может быть получена формула Я (и), т.
е. формула ЗхЗу [р(х, у+1) = СА»уг(г(п-»р(х, г» у+1) = Ь(г, р(х, г' у+1)))]. Если мы теперь обраауем терм ]гхЗу [ р (х, у + 1) = а А '» г (г ( и -» р (х, г" у -]- 1) = Ь(г, р(х, г' у+1)))], без ПопнтиЕ «тоти Котогыии И ЕРН УСТРАНИ»|ОСТЬ йГЛ, УЫГ который для краткости обоаначнм посредством Ь (и) '), то, применив формулу (рг) в сочетании с доказанной формулой иа' (п), мы получим Зу [р(1)(и), у+1) = аАФг(г(п — р([)(и), г" у+1) = Ь (г, р (() (п), гз у+ 1)))]. Опираясь на эту формулу и применяя к терму р з [р (() (п), у + 1) = а А )г г (г < и -+. р (1) (и), г". у+ 1) Ь(г, р(г) (п), г'.у+1)))], который мы сокращенно обозпачнм посредством 1 (п), формулу (р,), мы получим следующие две формулы: р ( г) (п), $ (п) + 1) = а, а(и-эр(!)(и), а".1(и)+1)=Ь(а, р(Ц)(и), а' 1(и)+1)). Тем самым мы теперь близки к поставленной цели — нахождению герма [ (и), для которого выводимы равенства )(0) = ае ) (и')=Ь(п, [(п)).
В самом деле, если обовначить р (Ь (и), а' 1(п) + 1) посредством т (п, а), то обе полученные нами формулы могут быть аапнсаны в виде г(п, 0)=а, а(п- г(и, а')=Ь(а, г(и, а)). Если в первую иа этих формул мы подставим 0 вместо п, а во вто- рую и' вместо и и п вместо а, а затем опустим посылку и ( и', то получим з) равенства т (О, 0) = а, г(п', п')=Ь(п, г(п', п)). Кроме того, во втором равенстве вместо т (п', и) здесь можно написать т (и, п). Действительно, равенство г (и', п) = г (и, п) может быть выведено следующим образом. ') Мы пользуемся здесь знаком для секрзщенкя, тзк какрзссызгрквзеыый геры уже сзм содержит ебознзчення а, б (, .), не вхеднщке в кап формалнзм.
з) Мы предполагаем здесь, что переменная а, гзк же квк к в, ке входит нк в а, нк в Ь()и, )). Подходящим выбором переменных мы всегда можем удовлетворить »гому условию. То же самое в дальнейшем будет предполагаться к егнесвтельво ви. ЯВеденив К ЯВНЫМ ОПРеДЕленИЯМ Из приведенных выше двух формул для т (и, а) мы можем получить т (т, 0) = т (и, 0) и а ( т А а ( и — и. (т (т, а) = т (п, а) -ь г (т, а') = 'г (и, а')). Вторая из этих формул дает нам, далее, (а<тАа(и-ьт(т, а)= г(п, а)) -ь(а'~(тА а'(п-ь-г(т, а ) =т(п, а )), так что нндукциеи по а мы получим фоРмулу а (т А а( п — и- 'г (т, а) = т (и, а).
Если мы подставим в нее и вместо а и и' вместо т, то можно будет опустить посылку и'. п' А п(п и тогда получится т (и', и) = т (п, п). Таким образом, мы пришли к равенствам т(0, 0)=а, г(и', и") =Ь(п, г (п, п)). В соответствии со сказанным, терм т (и, и) обладает нужными нам свойствами. Ь[ы можем взять его в качестве [ (п), и тогда будут выводимы равенства [(0) = а, [(")=-Ь(., [( И. Заметим, что выражения а и Ь (и, т) здесь могут содержать в качестве параметров какие-либо свободные переменные; зги последние входят тогда в термы Ь(и) и 1(п), а тем самым и в 1(п).
Тем самым мы показали, что в рамках системы (Е) при добавлении функции ркА (х) и относящихся к ней формул рекурсивные определения могут быть сведены к явным. Применимость этого метода не ограничивается рассмотренным случаем примитивно рекурсивных функций. Напротив, совершенно аналогичным образом при помощи функции р„А (х) к явным определениям могут быть сведены и рекурсии более сложных типов. Так, например, «перекрестные» рекурсивные равенства для функции Аккермана $(а, Ь,О) =а+Ь, $(а,О, и) = [3(и,1) +а вдп(б(п)), б (а, Ь', и') = $ (а, $ (а, Ь, и'), п) 5я понятие «тот, кОтОРый» и егО устРАнимОсть (гл тш (здесь Ь и и являются выделенными переменными рекурсии, в то время как а выступает только в роли параметра) могут быть разрешены при помощи некоторого терма 1(т, и), для которого в (Е) удается вывести равенства 1(Ь,О) =а+ Ь, ( (О, и') = () (и, 1) + а ° зяп (б (п)), ) (Ь', и') = 1 (1 (Ь, и'), и). Правда, доказательство етого факта нельзя непосредственно извлечь из того метода, с помощью которого мы рассмотрели простейший тип рекурсии, потому что здесь добавляется трудность, заключающаяся в том, что в то время как в случае примитивной рекурсии набор тех значений аргумента а, для которых при рекурсивном вычислении 1 (п) требуется найти значение 1 (а), состоит просто из последовательности чисел от О до п, в рассматриваемой рекурсии набор пар аначений с, д таких, что значение 1(с, д) фигурирует в рекурсивном вычислении 1(Ь,и), зависит от пары значений Ь, и весьма сложным образом, через посредство некоторого рекурсивного аакона.
Поэтому процедура установления разрешимости этих рекурсивных равенств оказывается значительно более запутанной. Однако, как показали фон Нейман и Гедель, такое доказательство все-таки удается получить '). 9 4. в'странимость характеристик (ь-символов) 1. Обобщение г-правила; связь с первоначальным «-правилом; термы й«1 А(х). Мы рассмотрели вопрос о формализации арифметики х в рамках системы (Е) с присоединенной функцией )«„А(х) и формулами (р,), ()««), ()«») и таким обрааом оанакомились с возможными способами применения функции )«„А (х), а также получили некоторое представление о формальных возможностях, открывающихся в результате ее введения. Функция )«4 (х) в свою очередь определялась нами с помощью «-символа з), а формулы ()«,), ()«з), ()гз) мы вывели с помощью ыправила.
Тем самым связанные с функцией )«„А (х) построения в конце концов сводятся к применениям ыправила. После етого подробного изложения способов применения «-символа, т. е. формализации понятия «тот, который», мы теперь ') Изложенпе этого доказательства по методу фоп Нейыапа было пркеедепо Р.
Петер — которая переопачалько пришла к »топу доказательству другим способом — з ее работе: Р е 1 е г К. ()Ьег 81е шеЬ»1««Ье Кейп«»(оп.— Мз«Ь. Апп., 1936, 113, 8. 489 — 527, 1 5. (Вместо «перекрестной рекурсии» Р. Петер говорит о «многократной рекурсии», я зто еырзжеппе е тех пор получило прае« гражданства.) «) Сы. с. 481. »И УСТРАНИМОСТЬ ХАРАКТЕРИСТИК (~-СИМВОЛОВ1 511 вернемся к ранее ') сформулированной теореме, в которой утверждается устранимость харакгпериспшк.
Эта теорема относится к системе расширенного исчисления предикатов, т. е. исчисления предикатов с присоединенными аксиомами равенства. Она относится также к такнм формальным системам, которые получаются иа этого исчисления в реаультате добавления некоторых индивидных символов, предикатных символов, математических функциональных знаков вместе с относящимися к ним аксиомами, причем огиносительно этих аксиом мы предполагаем, что они не содержат формульных переменных. Такие аксиомы без формульных переменных (а также соответстВующие им содержательные предложения) мы для краткости будем называть собственными аксиомами, в отличие от аксиом, выражающих условия более общего характера.
Однако наша теорема охватывает и тот случай, когда наряду с собственными аксиомами будет иметься аксиома индукции или если вместо пее будет в качестве правила фигурировать схема индукции. Для всех формальных систем указанного типа теорема, которую мы должны будем доказать, выражает тот факт, что в ревультате добавления ысимвола и ыираеила еапас выводимых формул, не содержащих г-символа, не расширяется. Другими словами, если формула рассматриваемой формальной системы оказывается выводимой в реэулыиате введения ыиравила, то она может быть выведена ужв внутри этой системы, бвв присоединения ыпраа»ла. Для доказательства этой теоремы формализм характеристик целесообразно несколько расширить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
