У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
Шрифт:
В предыдущей главе мы сформулировали первую теорему Гёделя о неполноте (теорему Гёделя) следующим образом.
Если выбрать в качестве аксиом любое множество истинных арифметических высказываний и требовать, чтобы доказательства, которые получены на их основе, могли быть проверены алгоритмически, то будет по крайней мере одно истинное высказывание, которое не может быть доказано на основе этих аксиом.
В этой формулировке теоремы появляется семантическое понятие истинности. Поэтому Гёдель представил его в статье 1931 года не в такой форме. Формулировка Гёделя аналогична, но записана с помощью только синтаксических понятий.
Определим синтаксические
Для начала скажем, что "являться доказательством, соответствующим требованиям программы Гильберта" — это синтаксическое свойство, поскольку его можно проверить с помощью компьютера посимвольно. Следовательно, идея "доказуемого высказывания" также синтаксическая, поскольку высказывание Р доказуемо, если существует доказательство, заканчивающееся этим высказыванием.
Даже понятие "высказывание" может быть определено синтаксически. Для начала, в аристотелевском определении говорится, что высказывание — это выражение, которому можно назначить значение истинности (истинно или ложно). Так,
"х — простое число"
не является высказыванием, поскольку его значение истинности зависит от того, каково х. И напротив, из двух высказываний:
"Существует некоторое х} являющееся простым числом", "Для любого х справедливо, что х — простое число"
первое истинное, а второе ложное.
Итак, это семантическое понятие может быть сформулировано синтаксически: высказывание — это выражение, не имеющее переменных (букв х, у, z), которые могут быть свободно заменены числами. То есть это выражение, в котором либо нет переменных, как в случае "4 = 2 + 2", либо все они сопровождаются выражениями типа "для любого х справедливо, что..." или "существует некоторое х, которое...", как это происходит в предыдущих двух примерах. Является выражение высказыванием или нет — это условие можно проверить посимвольно, при этом нет необходимости рассматривать значение выражений. Итак, "высказывание" и "доказуемое высказывание" — два синтаксических понятия, которые Гёдель мог использовать при формулировании своей теоремы.
В своей работе Principia Mathematica ("Принципы математики") Бертран Рассел утверждал, что все известные парадоксы всегда порождаются самореференцией. То есть они возникают из-за того, что в высказываниях прямо или косвенно говорится о них самих. Способ избежать любого парадокса, говорил Рассел, — исключить из языка любой намек на самореференцию. В семантическом самореферентном высказывании говорится о семантической характеристике как таковой. Таков случай "это предложение ложно", то есть утверждение, вызывающее парадокс лжеца. В синтаксической самореференции, наоборот, в самореферентном высказывании говорится о синтаксической характеристике как таковой. Например: "в этом предложении пять слов". Семантическая самореференция, как говорил Рассел, всегда опасна и подводит нас к границе парадокса. Синтаксическая самореференция, наоборот, не несет в себе никакого риска. Почему? Потому что синтаксическая самореференция иллюзорна; кажется, что в предложении говорится о нем самом, но на самом деле здесь раздвоение: в значении предложения говорится не о нем самом, а о символах, которые его образуют. Когда мы говорим: "в этом предложении пять слов", мы имеем в виду:
"В предложении "в этом предложении пять слов" содержится пять слов".
Отрицание этого:
"В предложении "в этом предложении пять слов" содержится не пять слов".
Мы
Другое важное понятие для синтаксической формулировки первой теоремы о неполноте — это понятие непротиворечивости. Множество аксиом является непротиворечивым, если не существует ни одного высказывания Р такого, чтобы Р и не-Р были одновременно доказуемы на основе этих аксиом (с синтаксической точки зрения не-Р получается простым размещением слева от Р символа, обозначающего отрицание).
Хотя далее мы увидим, какая связь существует между тем, чтобы быть "непротиворечивым" и быть "истинным", очевидно, что непротиворечивость — это чисто синтаксическое понятие (поскольку зависит от синтаксического понятия доказуемости).
Если все аксиомы — истинные высказывания, то множество аксиом непротиворечиво. Действительно, из истинных предпосылок получаются только истинные выводы. Тогда только одно из высказываний Р и не-Р ложно; следовательно, если все аксиомы истинны, невозможно, чтобы Р и не-Р были доказуемы одновременно (ложное не будет доказуемым).
Значит ли это, что выражение "непротиворечивое множество аксиом" равносильно "множеству истинных аксиом"? Это тонкий вопрос, который заслуживает тщательного анализа.
Начнем с вопроса, является ли высказывание "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 году Туральфом Скулемом для общего случая): множество аксиом является непротиворечивым, если существует какой-нибудь мир, в котором все аксиомы являются истинными высказываниями. Следовательно, множество, образованное двумя аксиомами: