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

"45 делится на 9"

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

истинны (во всех этих случаях мы рассматриваем мир натуральных чисел), а "2 х 3 = 10" — финитное и ложное. Высказывание "Любое четное число, большее 2, является суммой двух простых чисел" не является финитным, поскольку предполагает бесконечное число случаев. Действительно, это равносильно "4 — сумма двух простых чисел, и 6 — сумма двух простых чисел, и 8 — сумма двух простых чисел (и так далее)".

Заметим, что "36 — сумма двух простых чисел" является финитным высказыванием. Действительно, если 36 — сумма двух простых чисел, то они обязательно меньше 36. Существует всего 11 простых чисел, меньших 36 (это 2,3,5, 7,11,13,17,19, 23, 29, 31), и 55 пар, которые из них можно образовать. Чтобы посмотреть, истинно ли высказывание, достаточно проверить одну за другой эти 55 пар и убедиться, даст ли какая-нибудь в сумме 36. Высказывание истинно, поскольку 36 = 5 + 31.

Напротив, для высказывания "43 является суммой или разностью трех последовательных простых чисел" тот факт, что мы говорим о сумме или разности, предполагает: задействованные простые числа могут быть настолько большими, насколько мы захотим. Поиск простых чисел потенциально бесконечен, поэтому высказывание не финитное.

ГИПОТЕЗА ГОЛЬДБАХА

Утверждение о том, что любое четное число является суммой двух простых, известно как гипотеза Гольдбаха. Он сформулировал ее в 1742 году в письме знаменитому швейцарскому математику Леонарду Эйлеру (1707-1783).

До сих пор неизвестно, верна ли эта гипотеза. Она выполняется для большого числа четных чисел, но до сих пор никто не нашел доказательства для всех возможных случаев, так же как и не нашли примера, при котором гипотеза была бы ложной.

Итак, если мы предложим множество аксиом арифметики, то наименьшее, чего мы можем от него требовать — это способности доказать все финитные истинные высказывания. Следует заметить: во всем, что мы только что сказали, слово "истинное" связано с финитными высказываниями. В этом ограниченном контексте "истинное" и "ложное" становятся синтаксическими условиями, поскольку они проверяются механически за конечное число шагов. С точки зрения синтаксиса программа Гильберта предполагала нахождение непротиворечивого и полного множества аксиом арифметики, которое было бы способно доказать все финитные истинные высказывания. В первой теореме Гёделя о неполноте доказывается как раз то, что эта цель недостижима.

ПЕРЕСМОТР ДОКАЗАТЕЛЬСТВА ГЁДЕЛЯ

Так мы дошли до синтаксической формулировки первой теоремы Гёделя о неполноте:

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

В этой версии теоремы появляются только синтаксические понятия ("непротиворечивый", "неполный", "высказывание" и "доказуемый"). Понятие "истинность" связано с финитными высказываниями, то есть появляется в более ограниченной, синтаксической версии.

Эту синтаксическую формулировку Гёдель представил в своей статье 1931 года, и синтаксическими также были аргументы, которые он использовал для доказательства. Далее вспомним рассмотренное в предыдущей главе доказательство и посмотрим, как его можно реализовать на основе исключительно синтаксических аргументов.

— Шаг 1. Предположим, что у нас есть непротиворечивое множество арифметических аксиом, позволяющих доказать все финитные истинные высказывания (мы не указываем на то, что это истинные высказывания, поскольку апеллируем только к синтаксическим понятиям). Нам нужно доказать, что существует такое высказывание G, что ни Gy ни не-G недоказуемы. Как мы увидели в предыдущей главе, каждому высказыванию и каждой пропозициональной функции назначается код (или число Гёделя), но сейчас мы должны подчеркнуть, что назначение происходит чисто синтаксически, на основе символов, образующих высказывание или функцию, вне зависимости от того, каково их значение. Точно так же, синтаксически, назначается код каждой последовательности высказываний и, в частности, каждому доказательству.

— Шаг 2: Гёдель доказал, что пропозициональная функция

"у — код доказательства высказывания с кодом х"

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

"я — код доказательства высказывания с кодом r"

всегда финитно.

— Шаг 3: Гёдель определил пропозициональную функцию

"Не существует у, которое было бы кодом доказательства высказывания с кодом х".

— Шаг 4: Гёдель определил диагональную функцию. Если n — код пропозициональной функции Р(х), то d(n) — код Р(n). Следовательно, определение диагональной функции, которое основывается на механизме назначения кодов, синтаксическое.

— Шаг 5: На основе шагов 3 и 4 метод самореференции позволил Гёделю записать высказывание G:

"Не существует у, которое было бы кодом доказательства высказывания с кодом m",

код которого — само число m.

— Шаг 6: Теперь докажем синтаксически, что G недоказуемо. Предположим, от противного, что G доказуемо.

Тогда существует доказательство G, и ему соответствует код, к примеру k. Следовательно, высказывание

"k — код доказательство высказывания с кодом m"

истинное (поскольку m — код G, a k — код доказательства G) и, кроме того, финитное, поскольку можно проверить его истинность за конечное число шагов (можно проверить алгоритмически, что k — действительно код доказательства G). Так как оно финитное и истинное, то, по гипотезе, высказывание доказуемо. Тогда одно из правил логики позволяет нам сделать вывод, что также доказуемо высказывание

"Существует у, являющееся кодом доказательства высказывания с кодом т".

Схема доказательства того, что G недоказуемо.

Мы исходим из предположения, что G доказуемо. Стрелки показывают последовательные выводы, которые получаются из этого предположения, пока мы не приходим к заключению, что отрицание G также доказуемо. Это содержит противоречие, следовательно G не может быть доказуемо.

Если сравнить последнее высказывание с тем, как мы формулировали G, оказывается ясным, что оно соответствует не-G. Получается, мы говорим, что G и не-G одновременно доказуемы. Мы пришли к противоречию. Оно возникает из предположения, что G доказуемо, следовательно делаем вывод: G недоказуемо (см. схему на предыдущей странице).

— Шаг 7: Теперь докажем, что не-G также недоказуемо. Снова сделаем это от противного. Предположим, что не-G доказуемо, и придем к противоречию. Так как множество аксиом непротиворечиво, если не-G доказуемо, то G не может быть доказуемым.

ОМЕГА-НЕПРОТИВОРЕЧИВОСТЬ

Когда мы показали, что высказывание не-G недоказуемо, мы основывались на том факте, что если для свойства Р верно

высказывание "1 не удовлетворяет свойству Р" доказуемо,

высказывание "2 не удовлетворяет свойству Р" доказуемо,

высказывание "3 не удовлетворяет свойству Р" доказуемо

...и так далее,

то высказывание "существует некое х, удовлетворяющее свойству Р" недоказуемо. Но так ли это? Сначала рассмотрим этот вопрос семантически. Предположим, что Р — арифметическое свойство, для которого выполняется:

высказывание "1 не удовлетворяет свойству Р" истинно,

высказывание "2 не удовлетворяет свойству Р" истинно,

высказывание "3 не удовлетворяет свойству Р" истинно

...и так далее,

то есть для любого числа л справедливо, что свойство Р не выполняется. Тогда ясно, что высказывание "существует некоторый х, для которого выполняется свойство Р" ложно (поскольку мы сказали, что ни для 1, ни для 2, ни для 3 и так далее свойство не выполняется). Но оно ложно, если мы говорим о мире натуральных чисел, и может быть истинным, когда говорим о другом мире. Например, если свойство Р — это "х² = 2", а мы говорим о мире чисел, образованных на основе √2, то для 1 свойство не выполняется, как и для 2, 3 и так далее. Но для √2 свойство Р выполняется. Что же происходите синтаксической точки зрения? Рассмотрим снова свойство Р, но теперь предположим, что:

"1 не удовлетворяет свойству Р" доказуемо,

"2 не удовлетворяет свойству Р" доказуемо,

"3 не удовлетворяет свойству Р" доказуемо

...и так далее.

Верно ли, что "существует некоторое х, которое удовлетворяет свойству Р" недоказуемо? Поскольку в некоторых мирах это истинно, мы не можем точно утверждать, что это никогда не будет доказуемо. В доказательстве того, что не-G недоказуемо, имеется логический пробел, поскольку мы не можем утверждать, что это высказывание не окажется доказуемым. Чтобы справиться с этой проблемой, Гёдель ввел синтаксическое понятие омега-непротиворечивости. Множество аксиом омега-непротиворечиво, если притом что каждое из высказываний "1 не удовлетворяет свойству Р", "2 не удовлетворяет свойству Р", и так далее доказуемо, "существует некоторый х, который удовлетворяет свойству Р" недоказуемо (в какой-то степени это синтаксически вынуждает считать, что мы имеем в виду мир натуральных чисел). Следовательно, в начало синтаксического изложения первой теоремы Гёделя, где говорится, что множество аксиом непротиворечиво, следовало бы добавить "омега-непротиворечиво".

Вклад Россера

К счастью, в 1936 году американский логик Джон Б. Россер в статье объемом всего две страницы изменил рассуждение Гёделя так, чтобы оно было справедливо и при гипотезе непротиворечивости. Благодаря Россеру в изложении теоремы Гёделя можно опустить упоминание омега-непротиворечивости, и она может быть записана в том виде, в каком мы привели ее в тексте. Изменение, внесенное Россером в рассуждение Гёделя, состояло в том, чтобы заменить самореферетное высказывание "это высказывание недоказуемо" другим: "если это высказывание доказуемо, то также доказуемо и его отрицание".

Это означает, что не существует доказательства G; следовательно, ни одно число не является кодом доказательства G: число 1 — не код доказательства G, так же как 2,3 и так далее.

Получается, что высказывания

"1 — не код доказательства высказывания с кодом m",

"2 — не код доказательства высказывания с кодом m", "k — не под доказательства высказывания с кодом т" и так далее являются финитными истинными высказываниями. Раз они финитные и истинные, они доказуемы. Следовательно,

"существует у, являющееся кодом доказательства высказывания с кодом m" недоказуемо. Но это высказывание — не-G, следовательно, не-G не будет доказуемым; однако это противоречит предположению того, что не-G доказуемо. От противного получили, что не-G в итоге недоказуемо (см. схему).

Итак, синтаксически доказано, что как G, так и не-G, ни одно из двух, недоказуемо. Таким образом, доказательство первой теоремы о неполноте может быть полностью переведено в синтаксические аргументы и понятия, как этого требует программа Гильберта. Этот способ представления доказательства, основанный исключительно на синтаксических аргументах, проверяемых механически, спас от любых споров.

ВТОРАЯ ТЕОРЕМА

В программе Гильберта требовалось, как мы уже сказали, найти непротиворечивое множество аксиом арифметики таким образом, чтобы каждое высказывание Р (либо его отрицание) было доказуемым. Но также требовалось, чтобы непротиворечивость этих аксиом проверялась алгоритмически, — это придавало уверенности, что аксиомы не приведут к парадоксу. В своей статье 1931 года Гёдель доказал вторую теорему, так называемую вторую теорему о неполноте. В ней доказывается, что эта цель также неосуществима.

Эта теорема часто формулируется следующим образом:

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

В выражении "содержит арифметики, достаточной..." речь идет об уже упомянутом условии того, что множество аксиом, о котором мы говорим, способно доказать все финитные истинные высказывания. Но как же может множество доказать или не доказать собственную непротиворечивость? Для начала арифметические аксиомы позволяют доказать только те высказывания, в которых говорится о числах, но не такие, в которых говорится о непротиворечивости множества аксиом. Мы уже сталкивались с подобной проблемой в предыдущей главе, когда хотели записать арифметическое высказывание, которое говорило бы о себе самом. Как добиться того, чтобы арифметическое высказывание, в котором говорится о числах, начало говорить о самом себе? Способом достижения этого была идентификация высказываний с помощью их кодов, так чтобы разговор о высказывании был равносилен разговору о его коде.

Для доказательства непротиворечивости аксиом арифметики необходим прямой метод.

Давид Гильберт на инаугурационном докладе на Втором Международном математическом конгрессе в Париже в 1900 году

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

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

"существует некоторое высказывание, не являющееся доказуемым".

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

У нас есть два уровня прочтения для "существует некоторое простое число, не являющееся суммой или разностью трех последовательных простых чисел": арифметический, где указывается только арифметическое свойство; и более высокий уровень прочтения, зависящий от нумерации Гёделя, на котором заявляется непротиворечивость множества аксиом. Теперь сформулируем вторую теорему о неполноте:

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

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

если множество аксиом непротиворечиво, то G недоказуемо.

Заметим, что высказывание, в котором говорится: "G недоказуемо", — это само G. То есть G = "G недоказуемо". Следовательно, в предыдущее утверждение, в котором говорится: "G недоказуемо", можно просто поставить G. Или, что то же самое, в своей первой теореме Гёдель доказал:

если множество аксиом непротиворечиво, то справедливо G.

Итак, если доказать, что система аксиом непротиворечива, то высказывание "если множество аксиом непротиворечиво, то справедливо G" будет доказуемым. То есть "если множество аксиом непротиворечиво, то справедливо G" доказуемо, тогда доказуемо "множество аксиом непротиворечиво".

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

В последней главе мы рассмотрим некоторые философские следствия обеих теорем Гёделя о неполноте.

ГЛАВА 4

Гёдель и Эйнштейн

Курт Гёдель и Альберт Эйнштейн были большими друзьями и в Принстоне много времени проводили вместе. Благодаря этой дружбе появились три статьи Гёделя о теории относительности Эйнштейна — в отличие от остальных его опубликованных работ, они полностью чужды математической логике.

Несмотря на все политические и экономические проблемы (первые были вызваны нацистами, а вторые — кризисом 1929 года), в 1930-е годы в Вене бурлила не только богатая ночная жизнь, но и не менее разнообразная интеллектуальная. В кафе, кабаре и клубах по ночам слушали музыку и танцевали, а днем обсуждали искусство, науку и философию. В том же самом баре, где собирался Венский кружок, ночью звучали джазовые оркестры.