Гёдель, Эшер, Бах. Эта бесконечная гирлянда

Пример формальной системы, полной на своем скромном уровне — наша система 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 становится как непротиворечивой, так и полной. И эта полнота подтверждает правильность нашей интерпретации.

Неполнота формализованной теории чисел

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