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

конечное число общ их только конечное чис т ЕР к Рп+1, что в любом замен, а затем, путем перехода от ЕР к Рп, о «и-списке может содержаться только конечное число общих замен. Но если у — число осн овных типов в нашем списке основных типов, то наша посл д ле овательность общих замен каждый раз о ого + 1 -списка, тавляет собой начальный отрезок некоторого (д )- представл так как характеристическое число любой обще" ей замены не может т, в этой последовательности после коиеч- быть больше д, и, значит, в зом, в олжен будет наступить обрыв.

Таким обра о, ного числа шагов дол сы и их друг за друактически остается показать, что индексы идущ ггм Рп-списков любого (Рп+!)-списка образует убывающую после- ГОМ д овательиость. С этой целью из наше й леммы 3 мы выведем следствие, котоб бщая замена 9» прогрессивна по отноше ое гласит, что нию Если какая-ли о о щая (Э, то либо индекс 9» меньше индекса 9ь к другой общей замене „т д с и за залей б замены имеют один и тот же ин екс и ной 9» идет общая замена (Э5»,м прогрессивная по отноше нию к 9. и имеющая то же самое х арактеристическое число и ту же самую нов ю замену примером, что и 9ит. й, " мест место тогда, когда выполняется одна Первы, случай и из первых двух альте„н тернатив в заключении леммы 3.

о следует из того, что и в том случае, когда уменьшается первое р ду- ционное число р какой-л ой-либо общей замены, и в том случае, когда кцион- оно остается неи ме змеиным, но уменьшается второе ее редукР ается и индекс ит г+е этой замены. Втор ой иое число з, уменьшается ль е натива случай имеет место, когда выполняется третья альт р в заключении леммы 3. е что если общая А»О авив Д б к этому лемму 1, мы получаем также, что то ее индекс замена 9;„прогрессивна по отношению к меньше индекса 5ь об замены, образующие Отсюда емедлеи о ду н сле ет, что щие 2- я, имеют убывающие индексы. е" какой-либо -р д, вой, имеют характеристическое все эти замены, не считая перво ', им число 1 и, значит, характе ристический номер д. Следовательно, каждой из этих о щих б х замен все замены примером сохраняются.

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

Кроме того, верно также, что если у двух 2-спискоа 94 9РО "° А+А~ 9НРРм (не обязательно идущих непосредственно друг за другом) индексы общих замен совпадают вплоть до замен 9н А и 9„„,, включишельно, а замена 9н., имеет больший индекс, чем Я~++„то индекс первого из этих двух 2-списков тоже больше индекса второго. Теперь утверждения, доказанные здесь для 2-списков, надлежит доказать для произвольных ш-списков при а ) 2. Соответствующие утверждения гласят: (1) Для каждого входящего в рассмотрение числа а фигуры, представляющие собой индексы (а — 1)-списков, являются О-а-фигурами. (2) Индексы (а — 1)-списков, идущих друг за другом в каком- либо а-списке, убывают. (3) Если нам даны два а-списка, начинающиеся общими заменами 9; и 9;, (эти списки не обязаны идти непосредственно друг за другом), и если индекс 9~ больше индекса 9нр, то индекс первого из этих двух а-списков больше индекса второго.

Аналогичное утверждение имеет место в том случае, когда оба эти а-списка начинаются соответственно общими заменами 9ь 9ы ' 9н. и %+р~ 9й-Р+м ° ю 9нтн-г причем индекс 9;„больше индекса 9;+ .,„а при О ~: ! ( г индексы замен 9иу и 9~,Р,~ равны и при 1~/(г равны характеристические числа замен 9;,~ и 9О +г. Эти утверждения мы докажем путем перехода от а к а+1; т.

е., допустив, что они уже доказаны для чисел до в включи. тельно, мы докажем их для а+1. Для этого мы прежде всего заметим, что из высказываний (1) и (2) об (а — 1)-списках, составляющих какой-либо а-список, немедленно вытекает утверждение (1) для этого а-списка. Это обстоятельство будет явно использовано в утверждении (3), когда мы будем говорить о «большем» из индексов двух а-списков. Нам нужно также доказать утверждение (2) для а-списков, следующих в каком-либо (ш+ 1)-списке друг за другом. При этом мы воспользуемся справедливостью утверждения (3) для а-списков.

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

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

Действительно, если бы это было так, то новая замена примером из 9ы „была бы той же самой, что и в 9~.,р. Но эта замена, как мы знаем, не была ликвидирована заменой 9н „., (потому что эта замена имеет не большее,— собственно говоря, даже меньшее — характеристическое число чем 9; ); следовательно, она не может фигурировать в 9,+ „в качестве новой замены примером. Таким образом, р> 2 и 9~+, пока еще принадлежит первому а-списку, а 9нр., — второму а-списку. Так как в последнем случае общая замена 9~+,+, прогрессивна Г>42 ПРНЛОЖЕННЕ докАЗАтельстео АккеРНАнА 4 «1 по отношению к 9;„, то мы можем тем же самым способом продолжить этот процесс дальше. Таким образом, в обоих щ-списках 6, Ент, ." Енр Ег+Р+ совпадение индексов и характеристических чисел замен Ену н Ег„ры, а также найденных на основе этих общих замен новых заме~ примером будет продолжаться до тех пор, пока мы не дойдем до такой общей замены Е;„, которой во втором списке соответствует общая замена Ягтр„с меньшим индексом.

Это должно случиться не позже того момента, когда мы дойдем до замены ГУ)н. т. е. (з5;, не может быть заменой Ен В самом деле, этой замене не может соответствовать такая замена 9;„з.р, в которой новая замена примером, ведущая от Ег,, к 65г+р, снова вводилась бы в качестве новой, так как эта замена во втором щ-списке удерживается постоянно. Таким образом, получается следующая альтернатива: либо 9; имеет больший индекс„чем йзнр, либо следующие друг за другом два щ-списка начинаются соответственно заменами Фг Юз Н ", Егзг и ЕНР Еыртх ' ' ' Еырчт~ пРичем (Эне имеет больший индекс, чем Ег р „и г(Р, в гг вРемЯ как длЯ О ==1(г индекс Е,ы совпадает с индексом Янры, а кроме того, для ! «=.1(г совпадают характеристические числа замен 6гчу и Юо.р,р Таким образом, ввиду справедливости утверждения (3) для числа щ, в обоих случаях первый из рассматриваемых двух щ-списков имеет больший индекс, чем второй, и тем самым справедливость утверждения (2) для гн+1 нами установлена.

Отсюда также следует, что фигуры, представляющие собой индексы (нт+ 1)-списков, являются О-ю-фигурами. Остается еще доказать, что для нч-1-1 имеет место утверждение (3). Для этого достаточно рассмотреть разложение обоих (а+ 1)-списков на щ-списки. Действительно, в том случае, когда йзг имеет больший индекс'), чем Ег,р, из справедливости (3) для щ вытекает, что первый из а-списков, получающихся при разложении первого (а+1)-списка, имеет больший индекс, чем первый щ-список при разложении второго (щ+1)-списка. В противном случае из совпадения характеристических чисел замен хч1ну х) Мы пользуемся здесь обозначениями, фигурирующими в формулировке утверждения (3), в применении н (а+1)-спнснвм.