Gustavo Pineiro - У интуиции есть своя логика. Гёдель. Теоремы о неполноте.

• Название: У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
• Автор: Gustavo Pineiro
• Издательство: ООО «Де Агостини»,
• Жанр: Научпоп
• Год: 2015

Курт Гёдель изменил понимание математики. Две теоремы о неполноте, сформулированные им в 1931 году, с помощью формальной логики выявили хрупкость фундамента великого здания математики, которое усердно строили со времен Евклида. Научное сообщество было вынуждено признать, что справедливость той или иной гипотезы может лежать за гранью любой рациональной попытки доказать ее, и интуицию нельзя исключить из царства математики. Гёдель, получивший образование в благополучной Вене межвоенного периода, быстро заинтересовался эпистемологией и теорией доказательств. Так же как и его друг Альберт Эйнштейн, он оспаривал догмы современной науки, и точно так же в его жизни присутствовали война и изгнание.

---

На самом деле смысл в высказывании есть: Кипа mbwa nyekundu на суахили означает "бывают красные собаки" (см. рисунок). Теперь мы можем задаться вопросом, истинно предложение или ложно, но все равно ответ дать непросто. Ведь что такое красная собака? Она должна была родиться со шкурой такого цвета или ее могли покрасить позже? Уж не говоря о том, что люди воспринимают цвета по-разному. Целью всех этих рассуждений является пояснение: синтаксические аспекты языка прозрачны, а вот семантические — связаны с путаницей и парадоксами. В соответствии с этой идеей основная предпосылка программы Гильберта состояла в требовании того, чтобы справедливость семантических аспектов математики контролировалась синтаксическими методами. Синтаксис, ясный и не вызывающий сомнений, должен был ограничивать семантику, грозящую парадоксами.

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

Оно является семантическим, если зависит от значения (например, утверждение об истинности или ложности предложения). Синтаксические свойства проверяются механически; семантические — нет.

ПЕРЕСМОТР ПЕРВОЙ ТЕОРЕМЫ

Итак, Курт Гёдель представил доказательство первой теоремы о неполноте таким образом, что всем было очевидно: ее можно проверить с помощью компьютера. Он изложил свое высказывание и каждый шаг доказательства теоремы, апеллируя только к синтаксическим понятиям. 

В предыдущей главе мы сформулировали первую теорему Гёделя о неполноте (теорему Гёделя) следующим образом.

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

В этой формулировке теоремы появляется семантическое понятие истинности. Поэтому Гёдель представил его в статье 1931 года не в такой форме. Формулировка Гёделя аналогична, но записана с помощью только синтаксических понятий.

Определим синтаксические понятия, которыми пользовался Гёдель, и переформулируем первую теорему о неполноте.

Для начала скажем, что "являться доказательством, соответствующим требованиям программы Гильберта" — это синтаксическое свойство, поскольку его можно проверить с помощью компьютера посимвольно. Следовательно, идея "доказуемого высказывания" также синтаксическая, поскольку высказывание Р доказуемо, если существует доказательство, заканчивающееся этим высказыванием.

Даже понятие "высказывание" может быть определено синтаксически. Для начала, в аристотелевском определении говорится, что высказывание — это выражение, которому можно назначить значение истинности (истинно или ложно). Так,

"х — простое число"

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

"Существует некоторое х} являющееся простым числом", "Для любого х справедливо, что х — простое число"

первое истинное, а второе ложное.

Итак, это семантическое понятие может быть сформулировано синтаксически: высказывание — это выражение, не имеющее переменных (букв х, у, z), которые могут быть свободно заменены числами. То есть это выражение, в котором либо нет переменных, как в случае "4 = 2 + 2", либо все они сопровождаются выражениями типа "для любого х справедливо, что..." или "существует некоторое х, которое...", как это происходит в предыдущих двух примерах. Является выражение высказыванием или нет — это условие можно проверить посимвольно, при этом нет необходимости рассматривать значение выражений. Итак, "высказывание" и "доказуемое высказывание" — два синтаксических понятия, которые Гёдель мог использовать при формулировании своей теоремы.

СИНТАКСИЧЕСКАЯ АВТОРЕФЕРЕНЦИЯ

В своей работе Principia Mathematica ("Принципы математики") Бертран Рассел утверждал, что все известные парадоксы всегда порождаются самореференцией. То есть они возникают из-за того, что в высказываниях прямо или косвенно говорится о них самих. Способ избежать любого парадокса, говорил Рассел, — исключить из языка любой намек на самореференцию. В семантическом самореферентном высказывании говорится о семантической характеристике как таковой. Таков случай "это предложение ложно", то есть утверждение, вызывающее парадокс лжеца. В синтаксической самореференции, наоборот, в самореферентном высказывании говорится о синтаксической характеристике как таковой. Например: "в этом предложении пять слов". Семантическая самореференция, как говорил Рассел, всегда опасна и подводит нас к границе парадокса. Синтаксическая самореференция, наоборот, не несет в себе никакого риска. Почему? Потому что синтаксическая самореференция иллюзорна; кажется, что в предложении говорится о нем самом, но на самом деле здесь раздвоение: в значении предложения говорится не о нем самом, а о символах, которые его образуют. Когда мы говорим: "в этом предложении пять слов", мы имеем в виду: 

"В предложении "в этом предложении пять слов" содержится пять слов". 

Отрицание этого: 

"В предложении "в этом предложении пять слов" содержится не пять слов". 

Мы говорим о символах, а не о смысле, так что нет риска получить парадокс. В высказывании Гёделя G утверждается, что оно недоказуемо, то есть речь идет о синтаксической характеристике себя самого. Так как самореференция синтаксическая, рассуждения на основе G никогда не приведут нас к парадоксу.

НЕПРОТИВОРЕЧИВОСТЬ

Другое важное понятие для синтаксической формулировки первой теоремы о неполноте — это понятие непротиворечивости. Множество аксиом является непротиворечивым, если не существует ни одного высказывания Р такого, чтобы Р и не-Р были одновременно доказуемы на основе этих аксиом (с синтаксической точки зрения не-Р получается простым размещением слева от Р символа, обозначающего отрицание).

Хотя далее мы увидим, какая связь существует между тем, чтобы быть "непротиворечивым" и быть "истинным", очевидно, что непротиворечивость — это чисто синтаксическое понятие (поскольку зависит от синтаксического понятия доказуемости).

Если все аксиомы — истинные высказывания, то множество аксиом непротиворечиво. Действительно, из истинных предпосылок получаются только истинные выводы. Тогда только одно из высказываний Р и не-Р ложно; следовательно, если все аксиомы истинны, невозможно, чтобы Р и не-Р были доказуемы одновременно (ложное не будет доказуемым).

Значит ли это, что выражение "непротиворечивое множество аксиом" равносильно "множеству истинных аксиом"? Это тонкий вопрос, который заслуживает тщательного анализа.

Начнем с вопроса, является ли высказывание "2 — простое число" истинным. Почти любой человек сразу же скажет, что его истинность очевидна. Однако более правильным ответом будет "когда как". Это зависит от Вселенной, в контексте которой мы сейчас работаем. Если подразумевается, что речь идет о натуральных числах, то высказывание действительно истинно, но в другом контексте оно может быть ложным.

Вспомним, что число (отличное от единицы) является простым, если делится только на единицу и само на себя. Можно выразить это понятие по-другому: 2 — простое число, поскольку единственный способ представить его в виде произведения двух чисел тривиален: 2 = 2 x 1 (запись 2 = 1 x 2 считается совпадающей с ней, так как в ней используются те же числа). А вот число 15 не является простым, поскольку его можно представить, помимо тривиального способа 15 = 1 х 15, также как 15 = = 3 x 5.

Но точно ли единственный способ записать число 2 в виде произведения — это 2 = 2 х 1? В мире натуральных чисел — да. Но существуют и другие миры.

Расширим наш числовой мир и включим в него все числа, которые получаются умножением √2 на натуральное число (и на нуль), а затем прибавлением другого натурального числа (или нуля). Например, этот мир содержит числа 3 + 4 √2 или 7 √2. Также в нем содержится само число √2, которое записывается как 0+1 √2, и все натуральные числа, которые могут быть записаны как:

1 = 1 + 0 √2

2 = 2 + 0 √2

3 = 3 + 0 √2.

Итак, в этом мире 2 — не простое число, поскольку может быть записано как 2 = √2 х √2. Высказывание "2 — простое число" верно среди натуральных чисел, но ложно в мире, который мы определили по-другому (см. схему).

Какова связь между непротиворечивостью и истинностью? Ответ дан теоремой Лёвенгейма — Скулема (доказанной в 1915 году Леопольдом Лёвенгеймом для частного случая и в 1920 году Туральфом Скулемом для общего случая): множество аксиом является непротиворечивым, если существует какой-нибудь мир, в котором все аксиомы являются истинными высказываниями. Следовательно, множество, образованное двумя аксиомами: