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

(D) Если А, и В, и С истинны, Z ДОЛЖНО быть истинно.

Уже записали?»

«Записал, записал!» — радостно воскликнул Ахилл, вкладывая карандаш в футляр. «Наконец-то мы пришли к концу нашей воображаемой беговой дорожки! Теперь, когда вы принимаете А, и В, и С, и D, вы, КОНЕЧНО, принимаете и Z.»

«Неужели?» — спросила Черепаха с невинным видом. «Давайте-ка это выясним. Я принимаю А, и В, и С, и D. Что, если я ВСЕ ЕЩЕ отказываюсь принять Z?»

«Тогда госпожа Логика возьмет вас за горло и ЗАСТАВИТ!» — торжествующе ответил Ахилл. «Логика скажет вам: „У вас нет выхода. Теперь, когда вы согласились с А, и В, и С и D, вы ОБЯЗАНЫ согласиться с Z!“ Так что у вас нет выбора, как видите.»

«То, что произносит госпожа Логика, уж конечно стоит того, чтобы быть ЗАПИСАНО,» — сказала Черепаха. «Так что, пожалуйста занесите и это в ваш блокнот. Мы назовем это

(E) Если А и В и С и D истинны, Z должно быть истинным.»

«До тех пор, пока я не согласилась с ЭТИМ утверждением, я не обязана принимать Z за истинное. Теперь вы видите, что это совершенно НЕОБХОДИМЫЙ шаг?»

«Вижу, вижу…» — сказал Ахилл, и в его голосе явственно послышались грустные нотки.

В этот момент рассказчику пришлось покинуть счастливую парочку, так как ему срочно нужно было в банк. Он снова попал в те места только через несколько месяцев. Доблестный герой Ахилл все еще восседал на спине долготерпеливой Черепахи и писал в своем блокноте, который уже почти заполнился, а Черепаха говорила: «Записали последний шаг? Если я не сбилась со счета, у нас набралось уже 1001. Осталось всего каких-нибудь несколько миллионов… Зато подумайте только, какую ОГРОМНУЮ пользу наша беседа принесет Логикам Девятнадцатого Века!»

«Не думаю, что кто-нибудь из них сможет разобраться во всей этой чепухе», — отвечал усталый воин, в отчаянии пряча лицо в ладонях. «Сделайте милость, разрешите мне позаимствовать каламбур, который в девятнадцатом столетии придумает знакомая Алисы, ваша кузина Черепаха Квази, и переименовать вас в г-жу Чепупаху.»

«Ахиллес, бедняга, вы видно совсем устали, такую вы несете ахиллею… по этому поводу, я, пожалуй, позволю себе каламбур, до которого моя кузина Черепаха Квази не додумается, и переименую вас в Ахинесса.»

ЭТА ДВУХГОЛОСНАЯ ИНВЕНЦИЯ оказалась для моих героев вдохновляющей идеей. Так же, как Льюис Кэрролл позволил себе вольное обращение с Ахиллом и Черепахой Зенона, я позволил себе некоторые вольности с Ахиллом и Черепахой Льюиса Кэрролла. У Кэрролла одни и те же события повторяются снова и снова, каждый раз на более высоком уровне; это замечательная аналогия Баховского Естественно Растущего Канона. Если лишить диалог Кэрролла его блестящего остроумия, в нем останется глубокая философская проблема: подчиняются ли слова и мысли каким-либо формальным правилам? Это и есть основной вопрос, на который пытается ответить моя книга.

В этой и следующей главах мы рассмотрим несколько новых формальных систем; это поможет нам лучше понять саму идею формальной системы. Когда вы дочитаете эти две главы до конца, у вас должно сложиться неплохое представление о мощности формальных систем и о том, почему они представляют интерес для математиков и логиков.

В этой главе мы будем рассматривать систему pr. Ни математики, ни физики ею не заинтересуются; признаться, она — всего лишь мое собственное изобретение. Система pr интересна лишь постольку, поскольку она хорошо иллюстрирует многие идеи, играющие в этой книге важную роль. В этой системе три символа:

p r - — буквы p и r и тире.

Система pr имеет бесконечное множество аксиом. Поскольку мы не можем записать их все, мы должны придумать какой-нибудь метод их описания. На самом деле, нам нужно не просто описание этих аксиом; нам нужен способ, позволяющий узнать, является ли данная последовательность символов аксиомой. Простое описание аксиом охарактеризовало бы их полностью, но недостаточно сильно; именно в этом была проблема с описанием теорем системы MIU.

Мы не собираемся возиться в течении неопределенного — возможно, бесконечного — времени, чтобы определить, является ли некая строчка символов аксиомой. Нам необходимо такое определение аксиом, которое предоставит в наше распоряжение надежный алгоритм разрешения, устанавливающий аксиоматичность любой строчки, состоящей из символов p, r и тире.

ОПРЕДЕЛЕНИЕ: xp-rx- является аксиомой, когда x состоит только из тире.

 Обратите внимание, что каждый из этих двух x-ов замещает одинаковое число тире. Например, --p-r--- является аксиомой. Само выражение xp-rx-, разумеется, не аксиома, так как x не принадлежит системе pr; оно, скорее, походит на форму, в которой отливаются все аксиомы данной системы. Такая «форма» называется схемой аксиом.

Система pr имеет только одно правило вывода:

ПРАВИЛО: Пусть x, у и z — строчки, состоящие только из тире. Пусть xpyrz является теоремой. Тогда xpy-rz- также будет теоремой.

Пусть, например, x будет «--», у — «---» и z — «-». Правило говорит нам:

Если --p---r- является теоремой, то --p----r-- также будет теоремой.

Это утверждение типично для правил вывода: оно устанавливает связь между двумя строчками, не сообщая нам ничего о том, является ли каждая из них по отдельности теоремой.

Очень полезное упражнение — попытаться найти разрешающий алгоритм для теорем системы pr. Это нетрудно — после нескольких попыток вы, скорее всего, найдете решение. Попробуйте!

Надеюсь, что вы уже попытались найти решение. Во-первых, хотя это и кажется очевидным, я хотел бы заметить, что каждая теорема системы pr имеет три отдельных группы тире, и что разделяющими элементами являются p и r, именно в таком порядке. (Это можно доказать, основываясь на аргументах «наследственности», так же, как мы смогли доказать, что теоремы системы MIU всегда должны начинаться с М.) Это означает, что уже сама форма такой строчки как --p--p--p--r-------- исключает ее из числа теорем.

Читатель может подумать, что, подчеркивая фразу «уже сама форма», автор поступает довольно глупо: что еще может быть в такой строчке, кроме формы? Что, кроме ее формы, может играть какую-либо роль в определении особенностей данной строчки? Совершенно ясно, что ничего больше! Однако имейте в виду, читатель, что по мере того, как мы будем углубляться в обсуждение формальных систем, понятие «формы» будет становиться все сложнее и абстрактнее и нам придется все чаще задумываться о значении самого этого слова. Во всяком случае, мы будем называть «правильно составленной строчкой» любую строчку следующей структуры: группа тире, одно p, вторая группа тире, одно r, завершающая группа тире.

Вернемся к алгоритму разрешения. Для того, чтобы данная строчка считалась теоремой, первые две группы тире в сумме должны давать третью группу тире. Так, например, --p--r---- является теоремой, так как 2 плюс 2 равняется 4, в то время как --p--r- теоремой не является, так как 2 плюс 2 не равняется 1. Чтобы понять, почему этот критерий верен, взгляните сначала на схему аксиом. Очевидно, она производит только такие аксиомы, которые удовлетворяют критерию сложения. Теперь обратитесь к правилу вывода. Если первая строчка удовлетворяет критерию сложения, то же условие необходимо будет выполняться и во второй строчке. И, наоборот, если первая строчка не удовлетворяет критерию сложения, не будет удовлетворять ему и вторая строчка. Это правило превращает критерий сложения в наследственное качество теорем; каждая теорема передает его своим «отпрыскам». Это показывает, почему критерий сложения верен.