Гильберт, Бернайс - Основания математики. Теория доказательств (947376), страница 31
Текст из файла (страница 31)
Для этого заметим следующее: 1. Изменение функции замены какого-либо основного типа может заключаться лишь в том, что одной илн нескольким системам значений аргументов, которым первоначально в качестве значения функции была сопоставлена цифра О, в новой замене сопоставляется цифра, отличная от О. Следовательно, значение функции, Отличное от О, при всех изменениях сохраняется и в дальнейшем могут добавляться только значения, отличные от О. Аналогично, модификация какой-либо замены для основного типа без аргументов может заключаться только в том, что вместо О-замены появится замена некоторой цифрой, отличной от О.
144 исследовАние АРифметики пги помощи с-символ4 1гл и 2. Эффективная замена для какого-либо Б-герма ,г~определенная по некоторой общей замене '), при очередной сбщей замене может измениться только тогда, когда либо эта,~эффективная замена является О-заменой, на смену которой приходит какая-нибудь другая цифровая замена, либо когда эта эффективная замена изменяется для какого-нибудь вложенного в с а-терма.
Это утверждение вытекает из предшествующего утверждения 1, если дополнительно учесть, что эффективная замена для с определяется по замене для основного типа терма с и, быть может, по эффективным заменам для каких-либо вложенных в с е-термов. В качестве следствия из утверждения 2 получается утверждение 3. Если какая-либо общая замена отличается от другой, предшествующей ей общей замены теми или иными эффективными заменами, то для тех е-термов наименьшей степени, эффективные замены которых подвергаются каким-либо изменениям, эти изменения заключаются в замещении О-замены какой-нибудь другой цифровой заменой. Это можно уточнить следующим образом. Условимся сопоставлять каждой общей замене в качестве ее индекса последовательность, состоящую из р чисел, такую, что р представляет собой максимум степеней е-термов, встречающихся в заданном списке формул, а 4-й член последовательности (при 4=1, ..., р) указывает число тех Б-термов степени с, для которых при данной общей замене эффективная замена отлична от О-замены.
Пусть даны два различных индекса. Более высоким из них мы будем называть тот индекс, у которого на первом слева различающем месте стоит большее число. Тогда утверждению 3 можно будет придать следующий вид: 4. Из двух общих замен, которым соответствуют различные эффективные замены, более поздняя имеет более высокий индекс. 5, Пусть ис (4=1, ..., Р) обозначает число различных е-термов степени 4, входящих в рассматриваемый нами список формул. Тогда число различных возможных индексов общих замен равно (и,+1) ...
(яр+1). В самом деле, каково бы ни было с, число е-термов я-й степени, имеющих отличную от О-замены эффективную замену, равняется одному из чисел О, ..., и„. 6. При переходе от одной общей замены к другой, происходящем ввиду отыскания одной или нескольких новых экземплярных замен, эффективная замена модифицируется по крайней мере для одного из е-термов. Фн ПЕРБОНАЧАЛЬНЫЛ ГИЛЬБЕРТОВСКИЯ ПОДХОД 145 В самом деле, пусть БЗ(Е, 1„..., 1„) — е-терм, с которым связана одна из критических формул, дающих какую-либо экземплярную замену при построении новой общей замены по старой.
Пусть, далее, е 6(х, ап ..., и„) — основной тип этого е-герма, и пУсть 1,, ..., )с — значениЯ теРмов 1,, ..., 1„в момент постРоениЯ этой экземпляриой замены, Если при новой общей замене термы 1, , 1„ снова получают ЗНаЧЕНИЯ ~,, ..., )с, тО В ЭффЕКтИВНОЙ ЗаМЕНЕ тЕРМа Е 6 (Х, 1,, ... ..., 1„) используется новое значение функции, которое функция замены для терма а З(й, а,, ..., а„) принимает в в соответствии с модификацией функциональной замены для этого основного типа, — когда ее аргументы принимают значения ~,, ..., 1„. Следовательно, в этом случае при переходе к новой общей замене модифицируется эффективная замена для терма е Э (Е, 1,, ..., 1„).
Если же при новой общей замене по крайней мере один из термов 1,, ..., 1„ получает значение, отличное от предыдущего, то должна быть модифицирована эффективная замена хотя бы для одного из встречающихся в этих термах е-термов. В силу утверждений 4 и б это означает, что при нашем способе построения общих замен за каждой общей заменой, не являющейся резольвентой, следует очередная общая замена, имеющая более высокий индекс, откуда в силу утверждения 5 мы получаем, что не позже чем через (и, + 1) .... (ир+ 1) шагов очередная общая замена окажется резольвентой. Таким образом мы получим способ построения резольвенты в том случае, когда все е-термы, фигурирующие в заданном списке формул, имеют ранг 1. По оценке, найденной для числа требующихся при этом общих замен, мы можем получить еще одну, более простую (хотя и менее точную) оценку, которая имеет то преимущество„что зависит только от общего количества и=и,+...+и„ е-термов, встречающихся в заданном нам списке формул.
Так как для любого числа 1 выполняется соотношение 1+1 -21 то (и,+1) ... (и„+1)~2 ' ... 2" ( 2 '+"'+ " (2п 1) См. с. !зз. Таким образом„если п — число различных, встречающихся в задан- !46 исслгдоалние АРиФметики пРи помо1ци ФсимВОлл !Гл 1! 4 е! пеавоилчлльнын гнльвегтовскии подход !47 ном списке формул е-термов, то количество необходимых общих замен не будет превосходить числа 2". Для получения этого результата метод функциональных замен с помощью основных типов нами не использовался, хотя в данном случае он н способствовал бы упрощению рассмотрения.
Существенное применение этот метод найдет лишь в общем случае, когда нам придется иметь дело с е-термами и критическими формулами, имеющими ранг выше единицы. г) Построение последовательности общих замен в общем случае. Для подготовки к рассмотрению общего случая мы будем стремиться описать такой процесс построения последовательности общих замен, который будет обрываться только тогда, когда очередная полученная общая замена оказывается резольвентой. С учетом нашего способа построения замен, при котором замена для основных типов ранга выше 1 сводится к заменам для основных типов ранга 1, естественно требовать, чтобы получение общих замен происходило рекурсивным образом, т.
е. так, чтобы рассмотрение совокупности формул, у которой максимальный ранг е-термов равен а1+1, всегда сводилось к рассмотрению совокупности, имеющей максимальный ранг е-термов, не превосходящий а. Максимальный ранг е-термов, встречающихся в данном списке критических формул н формул е-равенства, мы будем для краткости называть рангом этого списка. В том случае, когда ранг списка равен 1, мы уже располагаем способом, позволяющим, исходя из общей замены со сплошными О-значениями, строить новые общие замены до тех пор, пока не будет получена резольвента. При этом возникают только такие функции замены, значения которых отличаются от О лишь для конечного числа систем значений их аргументов').
Чтобы от этого, уже известного нам способа перейти к способу, дающему аналогичный результат для списков формул, имеющих ранг, больший 1, мы воспользуемся тем, что если для заданного списка формул, имеющего произвольный ранг, выбрать замены для основных типов встречающихся в нем е-выражений ранга 1 и если эти замены (с использованием символов, выбранных для функций замены) символьно внести в критические формулы и формулы е-равенства ранга выше 1, то эти формулы снова перейдут в формулы того же самого типа, причем ранг их понизится на единицу.
В самом деле, стабильность вида критических формул н формул е-равенства вытекает из того, что при заменах для основных типов нх аргументы (если таковые имеются) сохраняются, и из того, что между наличием а-выраженнй в некотором е-терме а е!(х), с одной стороны, и в соответствующей формуле й(с), 1) См.
с. 14! — !42, !49 — 150. с другой, имеется определенная, рассмотренная нами ранее связь1). А то обстоятельство, что ранг е-термов ранга 2 и выше в результате внесения замен для основных типов ранга 1 понижается на единицу, легко усматривается из определения ранга '), Таким образом, если ранг заданного списка формул равен ае + 1, то по этим критическим формулам и формулам е-равенства, имеющим ранг выше 1, в результате символьного внесения замен для основных типов ранга 1 мы получим некоторый список критических формул и формул е-равенства, имеющих ранг, не превосходящий ш. Теперь допустим, что нам известен способ, позволяющий для любого списка формул ранга г, исходя нз обяцей замены со сплошными О-значениями, строить новые общие замены до тех пор, пока не будет построена резольвента. Располагая таким способом, мы получим интересующую нас процедуру для списков формул Я ранга ш+ 1 следук1щпм образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
