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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 34)

Так как частичные замены Е,*, Е*„,, Е;, совпадают, то, согласно 4 и 5, в первом столбце замел имеется не более 2и эффективно различных общих замен и в последовательности общих замен Е,, Е,,, Е!,, между двумя эффективно равными общими заменами не может стоять эффективно отличная от них общая замена. Следовательно, первый столбец замен разлагается не более чем на 2" идущих друг за другом отрезков, в каждом из которых любые две общие замены аффективно равны. Заметим также, что если замены Ер, и Е„, эффективно равны между собой, то строки замен с номерами р и о 1-кратно однородны. Отсюда получается, что последовательность строк замен разлагается не более чем на 2" отрезков таким образом, что внутри каждого из них строки замен 1-кратно однородны.

Далее, из утверждения 6 вытекает, что если строки замен с р-й по а-ю включительно (р(Ч) г-кратно однородны, то либо все эти строки обрываются еще до появления (г-)-1)-го столбца, а значит, и (г+ 1)-кратно однородны, либо частичные замены Еа,,„ь! совпадают для всех В от р до ! включительно, а значит, совпадают и соответствующие списки формул И,+,. Но отсюда вытекае! (снова ввиду утверждений 4 и б), что любая последовательность строк замен, являющихся г-кратно однородными, либо обрывается еще до появления (г+ 1)-го столбца (и, значит, образует последовательность (!+1)-кратно однородных строк замен), либо распадается не более чем на 2" отрезков, в каждом из которых строки (г+1)-кратно однородны.

А теперь можно рассудить следующим образом. Как мы уже установили, последовательность, состоящая из этих! строк замен, распадается не более чем на 2" различных отрезков таких, что в каждом из иих строки 1-кратно однородны; каждый из этих отрезков в свою очередь распадается не более чем на 2" отрезков, внутри которых строки 2-кратно однородны; каждый из них снова распадается не более чем на 2" отрезков, внутри которых строки 3-кратно однородны. 157 ПЕРВОНАЧАЛЬНЫЙ ГИЛЬВЕРТОВСКНЙ ПОДХОД 441 1Ьй исследОВАние АРиФметики пРи пОмОН!и з-симВОлА [Гл.

н Продолжая это рассуждение и далее, мы получим, что рассматриваемая последовательность строк распадется не более чем иа (2а)Ф(з) таких отрезков, внутри которых строки замен будут ф(и)-кратно однородными. Однако двух различных ф(и)-кратно однородных строк замен быть не может. Действительно, пусть 9 и 4 — номера различных строк, и пусть ! (4. Тогда, согласно утверждению 7, строка с номером 9 не может быть 1„-крзтно однородна са строкой с номером 4 и, следовательно, эти строки не могут быть зр(п)-кратна однородны друг с другом, так как 1„~ зр (и). Поэтому в рассмотренной нами последовательносчи строк замен может быть не более (2а)Ф(Я) строк, т.

е. всякий раз 1~ 2а. Ф (я), а значит, в результате применения нашей процедуры построения общих замен может появиться не более 2я'Р(я) ф(и) общих замен. Таким образом, не позже чем через 2я'Ф(я) зр(и) шагов построенная общая замена окажется резольвентой. Если мы будем знать, что ф(п) является верхней оценкой для любого списка формул, имеющего ранг щ, то приведенная оценка будет годиться для любого списка формул, имеющего ранг щ+1. Для списков ранга 1 у нас имеется оценка 2".

Поэтому, если положить 2Я ф(щ+1, п)=2" 9 ж ") зр(4и, и), то у нас получится рекурсивное определение некоторой оценки ф(4и, и) для количества общих замен, необходимых для получения резольвенты в случае списка формул, имеющего ранг щ и состоящего из критических формул первого рода и формул е-равенства с не более чем и различными имеющимися в них е-термами.

Эти рекурсивные равенства имеют вид примитивной рекурсии. е) Несостоятельность рассмотренного метода в случае критических формул второго рода с произвольным рангом. Дополнение к предыдущему результату. Приведенное в предыдущем пункте доказательство показывает возможность построения резольвенты для любого наперед заданного списка критических формул первого рода и формул е-равенства. Как мы убедились, для рассмотрения списков формул, имеющих ранг, больший 1, к основной идее гильбертовского подхода должны быть добавлены новые соображения.

Метод доказательства, используемый здесь, берет свое начало от В. Аккермана'). Другим, но тоже исходящим из гильбертавскога подхода путем той же самой цели достиг Дж. фон Нейман' ). Сначала складывалось впечатление, что методы этих доказательств позволят без особых трудностей включить в рассмотрение и критические формулы второго рода. На самом же деле связанные с этим затруднения оказались скрытыми глубоко. Что касается приведенного здесь доказательства, то процедура построения общих замен была задумана таким образом, чтобы она охватывала и критические формулы второго рода.

Предположение, что рассматриваемый список формул не содержит критических формул второго рода, нам потребовалось ввести только для доказательства того факта, что применение нашей процедуры завершается 4). Эта предположение позволило нам при построении общей замены обойтись без перехода от экземплярных замен к минимальным. Теперь посмотрим, где же это упрощение проявляется в нашем доказательстве. Способ получения общих замен в доказательстве учитывается в утверждениях 1 — 7. При этом утверждения 1 — 5 и 7 абсолютно не зависят от того, прямо ли мы используем экземплярные замены или же через посредство минимальных. Для утверждений 1 — 3 это усматривается без труда. Утверждения же 4, 5 и 7 получаются из рассмотрения общих замен для списков формул ранга ! совершенно аналогично тому, как это уже делалось раньше при добавлении критических формул второго рода' ). Единственным местом, где различие между экземплярными и минимальными заменами становится существенным, является обоснование утверждения 6.

Здесь используется следующее рассуждение. Если у нас имеются две критические формулы, которые получаются из одной и той же критической формулы ранга, большего единицы, в результате внесения двух различных частичных замен Е, и Ез и если результирующая для замен Е, и Е;,, общая замена эффективно равна результирующей для замен Ез 4) Это доказательство представляющее собой некоторое уточнение я уирощеяке доказательства, содержащегося з его диссертации: А с 14 Е Г щ а П И %. Вейгзидиий без '1ег!шщ иоц ба1цг' зиц1е!з бег Н!1Ьег!зсьеи Тьеопе бег ц41бегзргцеьзгге!Ье!!.— Май, Аии., 1924, 93 Аккермая язложяд только з едком яз своих писем.

') Смс !4 ецш а пи з. ч. Ацг Н!!Ьег1зсьеи Ве4че!з!Ьеаг!е.— Маьь а,, 1927, 29. По времени это дцказатедьстзо предшествует изложенному нами доказатедьстзу Аккермаяз. Как об этом уже упоминалось з этой работе было впервые введено понятие основного типа, используемое нами !с яеззачятель. кымк отклонениями з определении). ') См. с.

!16. 4) На еоотзетс4вующяе места была сделаны ссылка. шз исследовлние АРнеметнки пгн помощи е-символА !гл и е„(а' = у) = О-«а = 1, и пусть г — е-терм е„6 (х), т. е. е, (е„(х' = у) = 0 — «х = !) (этот терм имеет ранг 2). Пусть список формул, кол орый мы будем рассматривать, состоит из формул (1) 6 (!) — «6 (е„6 (х)), (2) (3) 6 (6(е,6 (х)))- е 6(х) чьб(е,6 (х))', е„6 (х) = е 6 (х) -« е„6 (х) = е„ (е„6 (х) = у), формул (ее (!' = у) = 0 -« „' = !) — «(е„(е' = у) = 0-«г = 1), (ее (6 (е) ' = у) = 0 — «6 (г) = !) -«е ~ 6 (е)', г = г -«е = ь„(е = у). т.

е. из (1) (2) (3) и Е„', общей замене Е„„то каждой экземплярной замене, которая находится из первой критической формулы в результате общей залгены Е'„„соответствуег некоторая экземплярная замена с тем вгсе самым цифровым значением, которая находится из второй критической формулы в результате общей замены Е„',. При этом совпадение упомянутых цифровых значений основывается на эффективном равенстве общих замен Е,, и Е„, Однако из этого еще нельзя заключить, что связанные с рассматриваемыми экземплярными заменами минимальные замены имеют одно и то же цифровое значение. Напротив, может случиться, что при двух различных эффективно равных общих заменах некоторая экземплярная замена ! для одного и того же е-герма приведет к различным минимальным заменам, хотя их количество и не может превышать Ь Поэтому в случае, когда имеются критические формулы второго рода, мы не можем сделать вывод, что любая последовательность г-кратно однородных последовательностей замен распадается не более чем на 2" отрезков, состоящих из (г-(-1)-кратно однородных последовательностей замен.

Напротив, число таких отрезков может зависеть от тех цифровых значений экземпляриых замен, которые используются при переходе от общей замены с номером г к общей замене с номером г+1. Эта ситуация может быть пояснена на следующем примере, принадлежащем фон Нейману. Пусть ! — какая-либо отличная от О и от О' цифра, пусть 6 (а) †форму пеРВОЯАчАльный ГильееРТОВОКНЙ подход 159 Формула (1) представляет собой связанную с термам г критическую формулу первого рода, формула (2) — связанную с г критическую формулу второго рода, а формула (3) — связанную с е-термом ранга 1 е„(г=у) критическую формулу первого рода.

Характеристики

Список файлов книги