Даглас Хофштадтер - ГЕДЕЛЬ, ЭШЕР, БАХ: эта бесконечная гирлянда

Этот тип противоречивости, созданный наложением (1) пирамидальной семьи теорем, которые, вместе взятые, утверждают, что все натуральные числа имеют определенное свойство, и (2) одной теоремы, утверждающей, что не все числа обладают этим свойством, называется ω- противоречивостью . ω- противоречивая система похожа на сначала-раздражающую-но-в-конце-концов-приемлемую неэвклидову геометрию. Чтобы построить мысленную модель того, что происходит, вообразите себе, что имеются некоторые дополнительные числа — давайте будем называть их не натуральными, а экстранатуральными — у которых нет численных символов Поэтому их свойства не могут быть представлены в пирамидальной семье (Это немного напоминает представление Ахилла о БОГе — что-то вроде «супергения», существа, находящегося выше всех гениев. Хотя это представление и было опровергнуто Гением, тем не менее это хороший образ, и может помочь вам вообразить экстранатуральные числа ).

Все это говорит нам о том, что аксиомы и правила ТТЧ, как мы до сих пор ее представляли, не описывают с достаточной полнотой интерпретации символов этой системы В нашей воображаемой модели понятий, которые эти символы представляют, еще остается место для вариантов Каждый из возможных вариантов системы опишет эти понятия немного полнее, но сделает это по-своему. Какие из символов приобретут «раздражающие» пассивные значения, если мы добавим приведенную выше «шестую аксиому»? Все ли символы окажутся «испорченными», или некоторые из них сохранят то значение, которые мы имели в виду? Предлагаю вам над этим поразмыслить. В главе XIV мы снова встретимся с подобным вопросом; там мы обсудим его подробнее. В любом случае, не будем здесь останавливаться на этом дополнении системы; вместо этого мы попытаемся исправить ω-неполноту ТТЧ.

Недостаток обобщающего правила был в том, что оно требовало знания того факта, что все строчки бесконечной пирамидальной семьи — теоремы; это слишком много для конечного существа. Однако представьте себе, что каждая строчка пирамиды может быть выведена из своей предшественницы регулярным путем. Тогда у нас оказалась бы конечное основание на то, чтобы считать все строчки пирамиды теоремами. Таким образом, трюк состоит в том, чтобы найти ту схему, которая порождает пирамиду, и показать, что сама эта схема является теоремой. Это подобно доказательству того, что каждый гений передает послание своему Мета-гению, как в детской игре в телефончик. Остается только доказать, что эта цепочка посланий начинается с гения — то есть установить, что первая строчка пирамиды — теорема. Тогда мы можем быть уверены, что послание дойдет до БОГа!

В конкретной пирамиде, которую мы рассматривали, такая схема существует; она представлена строчками 4-9 данной ниже деривации.

(1) Aa:Ab:(a+Sb)=S(a+b) аксиома 3

(2) Ab:(0+Sb)=S(0+b) спецификация

(3) (0+Sb)=S(0+b) спецификация

(4) [ проталкивание

(5) (0+b)=b посылка

(6) S(0+b)=Sb добавление S

(7) (0+Sb)=S(0+b) перенос строки 3

(8) (0+Sb)=Sb транзитивность

(9) ] выталкивание

Посылка здесь — (0+b)=b; результат — (0+Sb)=Sb.

Первая строка пирамиды — также теорема; это прямо следует из аксиомы 2. Все, что теперь требуется, это правило, позволяющее нам заключить, что строчка, суммирующая всю пирамиду в целом, тоже является теоремой. Такое правило будет формализованным пятым постулатом Пеано.

Чтобы выразить это правило, нам необходимо ввести кое-какую нотацию.

Давайте запишем правильно сформированную формулу, в которой переменная а свободна:

X{a}

(Там могут встречаться и другие свободные переменные, но нам это неважно.) Тогда запись X{Sa/a} будет обозначать то же самое, с той разницей, что все а будут заменены на Sa. Таким же образом, X{0/а} будет обозначать ту же строку, в которой все а заменены на 0.

Приведем конкретный пример. Пусть X{a} обозначает строчку (0+а)=а. Тогда X{Sa/a} представляет строчку (0+Sa)=Sa, a X{0/a} — строчку (0+0)=0.

(Внимание: эта нотация не является частью ТТЧ; она служит нам лишь для того, чтобы говорить о ТТЧ.)

С помощью этой новой нотации мы можем выразить последнее правило ТТЧ весьма точно:

ПРАВИЛО ИНДУКЦИИ. Предположим, что u — переменная и X{ u } — правильно сформированная формула, в которой и свободно. Если и Au

Мы подошли так близко, как возможно, к введению пятого постулата Пеано в ТТЧ. Давайте теперь используем его, чтобы показать, что Aa:(0+a)=a действительно является теоремой ТТЧ Выходя из области фантазии в приведенной выше деривации, мы можем использовать правило фантазии, чтобы получить

(10) <(0+b)=bэ(0+Sb)=Sb> правило фантазии

(11) Ab:<(0+b)=bэ(0+Sb)=Sb> обобщение

Это — первая из двух вводных теорем, требующихся для правила индукции другая — первая строка пирамиды — у нас уже имелась Следовательно мы можем применить правило индукции и получить то, что нам требуется

Ab:(0+b)=b

Спецификация и обобщение позволят нам изменить переменную с b на a , таким образом, Aa:(0+a)=a перестает быть неразрешимой строчкой ТТЧ.

Я хочу представить здесь более длинную деривацию ТТЧ с тем, чтобы читатель посмотрел, как она выглядит; эта деривация доказывает простой, но важный факт теории чисел.

(1) Aa:Ab:(a+Sb)=S(a+b) аксиома 3

(2) Ab:(d+Sb)=S(d+b) спецификация

(3) (d+SSc)=S(d+Sc) спецификация

(4) Ab:(Sd+Sb)=S(Sd+b) спецификация (строка 4)

(5) (Sd+Sc)=S(Sd+c) спецификация

(6) S(Sd+c)=(Sd+Sc) симметрия

(7) [ проталкивание

(8) Ad:(d+Sc)=(Sd+c) посылка

(9) (d+Sc)=(Sd+c) спецификация

(10) S(d+Sc)=S(Sd+c) добавление S

(11) (d+SSc)=S(d+Sc) перенос 3

(12) (d+SSc)=S(Sd+c) транзитивность

(13) S(Sd+c)=(Sd+Sc) перенос 6

(14) (d+SSc)=(Sd+Sc) транзитивность

(15) Ad:(d+SSc)=(Sd+Sc) обобщение

(16) ] выталкивание

(17) правило фантазии

(18) Ac: обобщение

*****

(19) (d+S0)=S(d+0) спецификация (строчка 2)

(20) Aa:(a+0)=a аксиома 1

(21) (d+0)=d спецификация

(22) S(d+0)=Sd добавление S

(23) (d+S0)=Sd транзитивность (строки 19,22)

(24) (Sd+0)=Sd спецификация (строка 20)

(25) Sd=(Sd+0) симметрия

(26) (d+S0)=(Sd+0) транзитивность (строчки 23, 25)

(27) Ad:(d+S0)=(Sd+0) обобщение

*****

(28) Ac:Ad:(d+Sc)=(Sd+c) индукция (строчки 18,27)

[В сложении S может быть передвинуто вперед или назад.]

(29) Ab:(c+Sb)=S(c+b) спецификация (строчка 1)

(30) (c+Sd)=S(c+d) спецификация

(31) Ab:(d+Sb)=S(d+b) спецификация (строчка 1)

(32) (d+Sc)=S(d+c) спецификация

(33) S(d+c)=(d+Sc) симметрия

(34) Ad:(d+Sc)=(Sd+c) спецификация (строчка 28)

(35) (d+Sc)=(Sd+c) спецификация

(36) [ проталкивание