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

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

Полнота : когда все утверждения, которые истинны (в каком-либо из возможных миров) и выразимы в виде правильно сформированных строчек системы, являются теоремами.

Пример формальной системы, полной на своем скромном уровне — наша система prв ее первоначальной интерпретации. Все правильные суммы двух положительных целых чисел представлены теоремами данной системы. Можно сказать то же самое по-другому: «Все правильные суммы двух положительных целых чисел доказуемы в данной системе.» (Внимание: используя термин «доказуемые утверждения» вместо термина «теоремы», мы начинаем стирать границу между формальными системами и их интерпретациями. Это не страшно, если мы четко осознаем этот факт, а также то, что некоторые системы допускают множественные интерпретации.) Система prв первоначальной интерпретации полна ; она также непротиворечива , поскольку не содержит таких ложных утверждений, которые были бы — используем наш новый термин — доказуемы внутри системы.

Некоторые читатели могут возразить, что система вовсе не полна, так как она не включает сложения трех положительных целых чисел (например, 2+3+4=9), хотя оно и может быть записано в нотации системы ( --p---p----r---------). Однако эта строчка не является хорошо сформированной и поэтому должна считаться такой же бессмысленной как и prp---rpr. Тройное сложение просто не может быть выраженов данной системе, поэтому полнота системы сохраняется.

Несмотря на полноту системы prв данной интерпретации, эта система, безусловна, далека от того, чтобы полностью выразить понятие истины в теории чисел. Она, например, не может сказать нам, сколько всего простых чисел. Теорема Гёделя о неполноте говорит, что любая «достаточно мощная» система уже в силу своей мощности является неполной, в том смысле, что имеются хорошо сформированные строчки, которые выражают истинные утверждения теории чисел, не являясь при этом теоремами. (Иными словами, в теории чисел имеются истинные утверждения, не доказуемые внутри самой системы.) Системы типа pr, полные но не очень мощные, напоминают патефоны низкого качества — мы сразу видим, что они настолько несовершенны, что никак не могут сделать то, чего бы нам от них хотелось — а именно, сказать нам все о теории чисел.

Что означает выражение, употребленное мною выше, что «полнота — это максимальное подтверждение пассивных значений»? Оно означает, что если система непротиворечива, но не полна, то существует несоответствие между символами системы и их интерпретациями. Система недостаточно мощна, чтобы оправдать данную интерпретацию. Иногда, если интерпретации немного «подправить», система может стать полной. Для иллюстрации этой идеи давайте взглянем на модифицированную систему pr(включая схему аксиом II) и на выбранную нами интерпретацию.

Изменив систему pr, мы изменили также и интерпретацию символа rс «больше» на «больше или равняется». Мы нашли, что измененная система prв такой интерпретации непротиворечива; однако в новой интерпретации есть что-то сомнительное. Проблема весьма проста: теперь имеется множество истинных утверждений, не являющихся теоремами. Например, «2 + 3 больше или равняется 1» выражено не-теоремой --p---r-. Просто эта интерпретация слишком небрежна! Она не отражает того, что делают теоремы системы. В такой неряшливой интерпретации система prнеполна. Мы могли бы поправить дело одним из двух способов: (1) прибавив к системе новые правила и, таким образом, сделав ее более мощной и (2) заменив интерпретацию на более аккуратную . В данном случае, заменить интерпретацию кажется более разумной альтернативой. Вместо того, чтобы интерпретировать rкак «больше или равняется», мы должны сказать «равняется или больше на 1». После такой модификации система prстановится как непротиворечивой, так и полной. И эта полнота подтверждает правильность нашей интерпретации.

В теории чисел мы снова встретимся с неполнотой; но в этом случае, чтобы исправить ситуацию, нам придется пойти в другом направлении — сделать систему более мощной путем прибавления новых правил. Ирония здесь заключается в том, что каждый раз, когда мы прибавляем новое правило, мы думаем, что уж теперь-то система станет полной! Эта дилемма может быть проиллюстрирована с помощью следующей аллегории.

Представьте себе, что у вас есть патефон и пластинка, которой мы пока дадим пробное название «Канон на тему В-А-С-H». Однако, когда мы проигрываем запись на нашем патефоне, вибрации, производимые записью, создают сильные помехи, мешающие нам узнать мелодию. Следовательно, заключаем мы, что-то должно быть не в порядке — или пластинка, или наш патефон. Чтобы проверить качество пластинки , мы должны прослушать ее на патефоне товарища; а чтобы проверить качество патефона , нам придется проигрывать на нем пластинки товарища, и смотреть, соответствует ли музыка этикеткам на них. Если наш патефон выдержит экзамен, тогда мы заключим, что дефект был в пластинке; с другой стороны, если пластинка пройдет свое испытание, то мы решим, что дефект — в нашем патефоне. Однако каково будет наше заключение, если тест выдержат оба ? Вспомните цепь двух изоморфизмов (рис. 20) и подумайте над ответом!

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

Черепаха: Это мой любимый аттракцион. Кажется, что едешь так далеко — а на самом деле никуда не попадаешь!

Ахилл: Понятно, почему это вам так нравится. Вы уже пристегнулись?

Черепаха: Да, все ремни на месте. Поехали! Ур-ра!

Ахилл: Я вижу, вы сегодня предовольны.

Черепаха: И не без основания: моя тетушка-гадалка предсказала мне на сегодня необыкновенную удачу. Так что я вся трепещу в предвкушении.

Ахилл: Неужели вы верите в предсказания судьбы?

Черепаха: Вообще-то нет… но говорят, что они действуют, даже когда в них не веришь.

Ахилл: Ну, в таком случае, вам действительно повезло.

Черепаха: Ах, какой вид! Пляж, толпа, океан, город…

Ахилл: И правда, великолепно. Взгляните-ка на вертолет — вон там. Кажется, он летит в нашем направлении. На самом деле, он уже почти над нами.

Черепаха: Странно, оттуда свисает какая-то веревка… и она совсем близко к нам — можно ухватиться…