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