Гильберт, Бернайс - Основания математики. Теория доказательств (Гильберт Д. - Основания математики и прочие работы), страница 136

Редукционное число замены 9, относительно первого из упомянутых списков е-термов мы будем сокращенно называть первым редукц ионным числом этой замены, а редукционное число относительно второго списков вторым редукционным числом 9Ь Нам потребуются некоторые факты, относящиеся к этим редукционным числам.

Лемма 1. Первые редунг(ионные числа общих зал«ем 9, и 9„, различны. Действительно, при переходе от 9, к 9..., как мы помним, в точности один основной тип е 6(х, а„..., а,) получает дополнительную замену примером для некоторого набора (и„..., и,) его аргументов. При этом цифры и„..., и, получаются из некоторого е-герма Вгб(к, и,, ..., и,), с которым связана одна из наших критических формул, редуцирующаяся при замене 9; в значение «ложын Термы а„..., а, при замене 9«редуцируются г) для етого годится, напрнмеп, нумерапня, которая получается нз аней л Ч на с.

367 †3 нУмеРапнн дла ФоРмализма (хн) в Рс»Ультаге сопосгаалення каждому е.герму « номера, получаемого а указанно нумепацнн й термам Ь представляющим собой результат замены каждого входящего а « а-снмаола соогаетстнующнм ему )»-снмаолом. б37 ПРИЛОЖЕНИЕ ДОКАЗАТЕЛЬСТВО АККЕРМАИА в цифры пм ..., п„а терм егЯ(~, в„..., в,) в цифру О. Может оказаться, что е-термы, фигурирующие в термах аг, ..., Е„при замене 91„, редуцируются точно так же, как и при 9» В этом случае упомянутые термы при замене 91, редуцируются тоже в цифры и„..., и,. Но терм е Я(г, и„, ..., и,) при замене 9„1 редуцируется в цифру, отличную от О, и, значит, терм е Я(х, в, ..., а,) при замене 91„, редуцируется иначе, чем при 9» (Это верно, конечно, и в том случае, когда число г аргументов а,, ...

..., а, равно нулю.) В противном случае по крайней мере один из в-термов, фигурирующих в термах а„..., а„при замене 91„, редуцируется иначе, чем при 91, и один из таких термов входит и в список е-терман, встречающихся в наших критических формулах первого рода. Итак, в любом случае в этом списке имеется по крайней мере один терм, который при замене Я;„редуцируется иначе, чем при замене 9» Но это различие может заключаться только в том, что при одной из этих двух общих замен данный е-терм редуцируется в О, а при другой — в цифру, отличную от О.

В самом деле, изменение значений основных типов при переходе от замены 91 к замене Ф';„состоит лишь в том, что, с одной стороны, вместо некоторого значения функции, равного О, появляется новое ее значение, отличное от О, а с другой стороны, для некоторых основных типов происходит возврат к О-замене. Следовательно, в выражении п» 2" + и, 2' '+...+п„, 2+п„, определяющем первое редукционное число, при переходе от 9, к Яг„изменяется по крайней мере одно из чисел п„п„..., и„. Но тем самым изменяется и значение этого выражения, что и требовалось доказать. Лемма 2.

Если общая замена 9» прогрессивна по отношению к 91, то, каков бы ни был нормальный список е-тгрмов, либо е-термы этого списка одинаково редуцируются при заменах 91 и 9», либо редукционное число относительно этого списка у замены 9» меньше, чвм у замены 9» Действительно, возьмем произвольный нормальный список е-термов и предположим, что первый случай альтернативы места не имеет. Пусть ет — первый из тех е-термов этого списка, которые при 9» редуцируются иначе, чем при 9» Пусть этот терм получается из своего основного типа е 8(х, сг, ..., с,) в результате замены аргументных переменных с„..., с, термами г„... ..., г,. Тогда каждый е-терм, встречающийся в термах гг, ..., г„ входит в рассматриваемый нормальный список, причем располагается в нем перед ар Значит, такой терм при замене 9» редуцируется так же, как и при 9» Тем самым термы г,, г, при 9» редуцируются так же, как и при 9» Пусть,'„..., 1,— цифры, в которые эти термы редуцируются при обеих пассматриваемых нами общих заменах.

Тогда основной тип ер(х, с„... ..., с,) при замене 9» получает в точке 11, ..., 1, замену, отличную от той, которую он получает при 9» Так как замена 9» прогрессивна по отношению к 9» то это изменение должно заключаться в переходе от О-замены к некоторой замене примером. Поэтому в выражении и, 2" +пг 2' '+...+п»-1 2+и»* определяющем редукционные числа этих общих замен относительно рассматриваемого нормального списка е-термов, значения п„..., пт, у замен Я; и 9» совпадают, пт у 9; имеет значение 1, а у 9» — значение О, что и требовалось доказать.

Лемма 3. Если общая замена 9» прогрессивна по отношению к 91, то либо первое редукционное число у 9» меньше, чгм у 9» либо эти числа равны и второе редукционног число у Я, меньше, чем у 9, либо же оба эти редукционные числа у замен 91 и 9» равны, и в этом случае за 9» следует общая замена 9»»1, про- 1 » гргссивная по отношению к Я;,1 и имеющая то же самое характеристическое число, что и Я;.;, в последнем случае, кроме того, новая замена примером при переходе от 9» к 9» 1 оказывается той же самой, что и при переходе от 91 к Я;„. В самом деле, применив лемму 2 к списку е-термов, определяющему первое редукционное число, мы сможем заключить, что либо это число у замены 9» меньше, чем у 91, либо все в-термы, входящие в рассматриваемые критические формулы первого рода, при обеих этих заменах редуцируются одинаково.

Нахождение новой замены примером для Я; и для Я, в этом случае будет связано с одной и той же формулой. К замене Я„ так же как и к 9» примыкает следуюгцая за ней общая замена 9»„.„и характеристический номер 1 замены Я»„будет тем же самым, что и у замены Я,„, Кроме того, вторые редукционные числа у Я; и у 9» относятся к одной и той же совокупности е-термов. Отсюда по лемме 2 получается, что либо второе редукциониое число у замены Я» меньше, чем у 9» либо все е-термы этой совокупности при замене 9» редуцируются так же, как при 9» Но отсюда следует, что добавляющаяся в 9„, замена примером будет той же самой, что и в 91„,.

Кроме того, можно утверждать, что все замены примером, имеющиеся в 91„, будут присутствовать также и в 9»„,. Действительно, замены примером, входящие 9, состоят, как мы помним, из замен, входящих в 91 и в оеами касающихся определения значений основных типов с номер обавне превосходящими 1, а кроме того, из замены приме"ом, д ляющейся в Я . Но все такие замены, входящие в О1» присутствуют и в 9», так как Я„прогрессивна по отношению 1+1. Б39 ПР И ЛОЖЕ И И Е поскольку эти замены относятся к основным типам с номерами, не превосходящими 1, то они сохраняются при переходе от 9» к 9»+,. Кроме того, при этом переходе добавляется та же самая замена примером, которая добавляется при переходе от 9; к 9;„. Таким образом, общая замена 9„„прогрессивна по отношению к 9о„что и требовалось доказать.

Теперь мы введем понятия Рп-списка Общих замен и индекса а-списка. Последовательность идущих друг за другом общих замен 9ь 9»Р„..., 9»Р мы будем называть 1-списком, если р=О, т. е. если эта последовательность состоит в точности из одной общей замены. При а~ 1 последовательность 9О 9О», ... ..., 9»Р будег называться Рп-списком, если характеристические числа всех замен (9;„, ..., 9;Р меньше т, а 9; либо совпадает с О-заменой 9„либо имеет характеристическое число, большее или равное е«, и если, кроме того, в случае, когда 9»Р не является последней общей заменой, 9»»р„имеет характерйстическое число, большее или равное ЕР. Таким образом, у и«-списка 9Ь 9„О ..., 9и.р последовательность 9ит, ..., 9;,р представляет собой непродолжимую в обе стороны последовательность общих замен с характеристическими числами, меньшими Рп. Согласно этому определению (Рп+1)-список может одновременно быть и Рп-списком, но, вообще говоря, он состоит из нескольких Рп-списков, у которых, начиная со второго подсписка, начальный член имеет характеристическое число, равное ЕР.

Очевидно, что у общих замен любого (Рп+1)-списка значения всех основных типов, за исключением последних ЕР, определены одинаково. Индексом любого !-списка, состоящего, как мы помним, из единственной общей замены 9, мы будем называть О-ю-фигуру а' г+ю«.в, или, короче, в г+з, в которой р — первое, а з— второе редукционное число замены 9. Индексом (ЕР+!)-списка, у которого следующие друг за другом ЕР-списки, из которых ои состоит, имеют индексы а», ..., аю мы будем называть фигуру ю«Р + + юии То, что определенные таким образом индексы Рп-списков при а«-» 1 тоже являются О-«в-фигурами, мы докажем путем перехода от ЕР к и«+1, показав, что индексы следующих друг за другом Рп-списков, составляющих данный (Рп+1)-список, всегда образуют убывающую последовательность О-«о-фигур. Доказав это, мы одновременно достигнем и нашей конечной цели, т. е. покажем, что последовательность идущих друг за другом общих замен всегда ведет к обрыву, т.

е. приводит к такой общей замене, в результате которой все критические формулы редупируются в значение «истина». ДОКАЗАТЕЛЬСТВО АККЕРМАИА В самом деле, любая убывающая последьеательность О-ю-фигур после кон конечного числа шагов, как мы помьчм, рывается. По- этому если индексы идущих друг за другом ч-списков в каком- ли о (Рп+ 1)-списке образуют убывающую последовательность идти только конечное число ЕР-списков. В соответствии с этим мы сначала получи, получим, что в любом 2-списке может содержаться число 1-списков, т. е.