Полнота
Если непротиворечивость — это минимальное условие, при котором символы приобретают пассивные значения, то ее дополнение, полнота — максимальное признание этих пассивных значений. Непротиворечивость означает, что «все, что производит система, истинно»; полнота же, наоборот, утверждает, что «все истинные утверждения производятся данной системой». Точнее, мы не имеем в виду все истинные утверждения в мире, а только находящиеся в области, которую мы пытаемся воспроизвести в данной системе. Таким образом, более точное определение полноты следующее: «Каждое истинное утверждение, которое может быть выражено в нотации данной системы, является теоремой.»
Непротиворечивость: когда каждая теорема, будучи интерпретирована, оказывается истинной (в каком-либо из возможных миров).
Полнота: когда все утверждения, которые истинны (в каком-либо из возможных миров) и выразимы в виде правильно сформированных строчек системы, являются теоремами.
Пример формальной системы, полной на своем скромном уровне — наша система 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) и подумайте над ответом!
Маленький гармонический лабиринт
Черепаха и Ахилл проводят день в Кони Айленде, огромном парке аттракционов. Купив себе по палочке «сахарной ваты», они решают прокатиться на колесе обозрения.
Черепаха: Это мой любимый аттракцион. Кажется, что едешь так далеко — а на самом деле никуда не попадаешь!
Ахилл: Понятно, почему это вам так нравится. Вы уже пристегнулись?
Черепаха: Да, все ремни на месте. Поехали! Ур-ра!
Ахилл: Я вижу, вы сегодня предовольны.
Черепаха: И не без основания: моя тетушка-гадалка предсказала мне на сегодня необыкновенную удачу. Так что я вся трепещу в предвкушении.
Ахилл: Неужели вы верите в предсказания судьбы?
Черепаха: Вообще-то нет… но говорят, что они действуют, даже когда в них не веришь.
Ахилл: Ну, в таком случае, вам действительно повезло.
Черепаха: Ах, какой вид! Пляж, толпа, океан, город…
Ахилл: И правда, великолепно. Взгляните-ка на вертолет — вон там. Кажется, он летит в нашем направлении. На самом деле, он уже почти над нами.
Черепаха: Странно, оттуда свисает какая-то веревка… и она совсем близко к нам — можно ухватиться…
Ахилл: Смотрите-ка: на конце веревки огромный крюк и на нем — записка.
(Он протягивает руку и срывает записку. Колесо начинает опускаться.)
Черепаха: Ну как, что там написано? Можете разобрать?
Ахилл: Да… Здесь написано: «Приветик, друзья. Будете снова наверху — хватайтесь за крюк, и получите Сюрприз!»
Черепаха: Записка грубовата… но кто знает, к чему это может привести. Может, это начинается обещанное везенье. Давайте попробуем!
