Вначале была аксиома. Гильберт. Основания математики

По иронии судьбы, за три дня до этого в Кёнигсберге состоялась конференция по эпистемологии точных наук. Цель встречи состояла в том, чтобы определить, на какой стадии находится разрешение кризиса оснований математики. Выступали представители каждого из связанных с основаниями течений. От логицизма — Рудольф Карнап (1891-1970), изложивший концепцию математики, которую сформулировал в Венском кружке: математические теоремы как тавтологии, логические истины. От интуиционизма — Аренд Гейтинг, выступавший за исключение бесконечности из математики. И от формализма — Джон фон Нейман, сторонник Гильберта. А 6 сентября слово взял 24-летний австрийский логик Курт Гёдель и доложил о недавно полученных им результатах: «Я могу привести примеры истинных арифметических пропозиций, недоказуемых в формальной системе классической математики». Несмотря на важность этого заявления, оно осталось незамеченным. И только фон Нейман был в недоумении. Несмотря на то что он всегда мечтал доказать непротиворечивость всей математики посредством финитных методов, в его голову уже закралось сомнение, что на самом деле это невозможно, и краткое выступление застенчивого юноши в круглых очках показалось его событием невероятного значения. Это был смертный приговор красивому девизу Гильберта. Надежда, которая теплилась в душе немецкого математика более 30 лет, должна была окончательно угаснуть. Математика больше никогда не будет надежной. Когда в 1931 году были опубликованы теоремы Гёделя о неполноте, в программе Гильберта произошло короткое замыкание. Чтобы объяснить, почему это произошло, нам нужно обратиться к математической логике.

С эпохи Аристотеля, не забывая о вкладе схоластиков, логика задумывалась как учение о рассуждении, которое никогда не происходит в пустоте, а всегда в рамках какого-то языка. С течением времени математики обращали все большее внимание на логику языков, на которых они изъясняются, чтобы определить их возможности. Логика научила математиков тому, что в языке существует два основных понятия: одно — семантического характера, понятие истины, другое — синтаксического характера, понятие доказательства. Сложность заключалась в том, чтобы определить радиус их действия: совпадают ли эти два понятия экстенсионально, пусть они сильно различаются интенсионально. Другими словами, является ли все доказуемое истинным (правильность) и все истинное — доказуемым {полнота). В целом языку, богатому в плане выражения, соответствует логика, бедная на интересные свойства. Так, логика языков первого порядка является правильной и полной, но математику ее обычно не хватает в ежедневной работе (когда нужно количественно оценить свойства, а не только объекты).

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

Гёдель — величайший логик со времен Аристотеля.

Джон фон Нейман о Гёделе

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

Возникает важный вопрос: можно ли свести всю математику к теории множеств? Если истолковать объекты нашего языка первого порядка как множества, легко эмпирически убедиться, что большинство математических сущностей можно определить на основе множеств. Эта программа исследования основывалась на вышеупомянутой теории множеств ZF: на базе небольшого количества аксиом, сформулированных в первом порядке, эта теория множеств была способна охватить значительную часть математики того времени.

Снова, как в итоге понял Гёдель, цена этого теоретического богатства (выразимость) — метатеоретическая бедность, которая проявляется в нескольких ограничивающих результатах: теоремах о неполноте. В первой теореме доказывается, что существует истинная формула, которая недоказуема в ZF (хотя в работе Гёделя в качестве отправной формальной системы взят труд Рппсгрга mathematica, а его результаты справедливы для ZFи других смежных систем). А во второй — что невозможно доказать непротиворечивость ZF в ZF. Более того, доказательство в ZF отсутствия противоречия в ZF и, следовательно, в математике доказало бы исключительно, что ZF и математика противоречивы. Гёдель положил конец надежде на формализм Гильберта. Все усилия, направленные на доказательство непротиворечивости математики, обречены на провал. Точнее, невозможно доказать посредством финитных методов отсутствие противоречий любой формальной системы, содержащей арифметику Пеано (если позволить себе применение тяжелой артиллерии, непротиворечивость все-таки возможно доказать, как в 1936 году это сделал ученик Гильберта Герхард Генцен (1909-1945), хотя и посредством трансфинитных методов, очевидность которых спорная).

Кто из нас не возликовал бы, подними он занавес, за которым скрывается будущее, загляни он в последующие достижения науки и секреты ее развития?!

Давид Гильберт, из речи на II Международном конгрессе математиков в Париже

Парадокс лжеца был для Гёделя одним из двигателей доказательства теорем о неполноте. Поскольку доказательство было на грани перехода в цикличность, некоторые математики — в частности, 60-летний Цермело — не осознали его ценности. Гёдель придумал ловкий перевод на метаязык внутри языка: арифметизацию метаматематики. С помощью смелой цифровой кодификации, основанной на простых числах (которую с тех пор называют гёделизацией), он назначил номера знакам так, чтобы с каждой формулой (и также с каждым доказательством) можно было связать число, кодировавшее бы всю структуру. Пропозиции, в которых говорилось о свойствах формальной системы, выражались в рамках системы посредством арифметических формул. Доказуемость, например, была представлена в виде числового отношения.

В таких условиях Гёдель вышел из ситуации, составив формулу G, которая говорит сама о себе: «я недоказуемо». Эта формула стала примером неразрешимого утверждения внутри формальной системы: ни она, ни ее отрицание не являются теоремами, то есть чем-то доказуемым. Действительно, Іеделю удалось доказать, что G доказуемо тогда и только тогда, когда ¬G доказуемо. Следовательно, если мы хотим, чтобы формальная система была непротиворечивой, ни G, ни ¬G не могут быть таковыми. Если бы G было доказуемо, так как ¬G утверждает в метаматематических терминах, что G доказуемо (отрицает то, что оно недоказуемо, как сказано в нем самом), то было бы возможно доказать также ¬G и вывести противоречие (G^¬G). И наоборот, если бы ¬G было доказуемым, мы могли бы по той же причине доказать G и прийти к тому же противоречию. В итоге доказательство любой из этих двух формул автоматически предполагало бы противоречивость системы. Более того, если допустить, что формальная система непротиворечива, то G недоказуемо, но истинно. Если бы G было ложно, так как в G говорится: «я недоказуемо», то G было бы доказуемо, что невозможно. Следовательно, у нас есть высказывание G, которое, хотя и недоказуемо, является истинным.

Существование неразрешимого утверждения предполагает, что аксиомы теории не содержат ответа на все вопросы, формулируемые формальным языком, потому что ни утверждение, ни его отрицание не являются теоремами. И так как либо оно, либо его отрицание должно быть истинным, у нас есть истинная недоказуемая формула. Хуже всего, что если добавить неразрешимое утверждение в качестве аксиомы, появляются другие, новые. Математика вдруг очнулась от гильбертова сна — от мечты о полноте, в которой аксиоматические системы не содержат неразрешимых формул, а истинное всегда совпадает с доказуемым. Проще говоря, «непротиворечивый» предполагает «неполный», и наоборот, «полный» предполагает «противоречивый». Ни одна формальная система, содержащая привычную арифметику, не может быть одновременно и той и другой. Если мы предположим, что она непротиворечива, она всегда будет неполной, то есть будет содержать недоказуемые истины. Будут существовать некоторые истинные свойства формально неразрешимых чисел, то есть свойства, которые мы не можем ни доказать, ни отвергнуть на основе аксиом.

Но за первой теоремой о неполноте следует вторая: так как непротиворечивость равносильна утверждению, что формула 0/=0 недоказуема, Гёдель трансформировал это последнее математическое свойство в арифметическую формулу (назовем ее С) и заметил, что в первой теореме установлено, по сути, что «C->G». Непротиворечивость предполагает, что существует неразрешимое утверждение и, следовательно, неполнота. Так что доказательство С позволило бы нам исключить G из импликации «C->G» посредством modus ponens и, следовательно, доказать G, что невозможно, поскольку G недоказуемо. Это удивительное следствие сводится к тому, что непротиворечивость формальной системы, которая включает в себя арифметику, недоказуема в рамках формальной системы. Гёдель не доказал должным образом эту вторую теорему, он только высказался о ее приемлемости, но так никогда и не записал обещанного доказательства. Первое полное доказательство, очень тщательное, появилось, что любопытно, в 1939 году, во втором томе «Оснований математики» Бернайса и Гильберта.

Мало того, к синтаксическим ограничениям, которые открыл Гёдель, присоединилось другое ограничение — семантическое, формальных систем первого порядка: теорема, сформулированная Леопольдом Лёвенгеймом (1878-1957) и Туральфом Скулемом (1887-1963) около 1920 года (Скулем вернулся к ней в 1933 году). В 1930 году в рамках своего доказательства полноты логики первого порядка Гёдель мимоходом доказал, что любая непротиворечивая теория первого порядка имеет модель, в которой аксиомы проверяются, хотя и ничего не добавил о том, какие характеристики имеет эта модель и как ее построить. Лёвенгейм и Скулем до этого заметили, что любая непротиворечивая формальная система первого порядка имеет, по сути, счетную модель. Это порождает парадокс Скулема: если ZF непротиворечиво, то оно обладает счетной моделью. То есть несчетный континуум, которым мы намереваемся оперировать в ZF, может относиться к счетному множеству вне ZF. Теория действительных чисел, от которой мы ждем знакомой несчетной модели («настоящие» действительные числа), также имеет счетную модель.

ТЕОРЕМА ТАРСКОГО О НЕВЫРАЗИМОСТИ ИСТИНЫ

Альфред Тарский (1902-1993) считал себя лучшим из живущих математических логиков с ясным умом (чтобы избежать сравнения с Гёделем, страдавшим маниями и навязчивыми идеями).

В 1939 году этому польскому ученому удалось переехать в США и на несколько десятилетий превратить университет Беркли в мировую столицу математической логики. Он любил работать ночью и увлекался психотропными средствами, которые помогали ему бодрствовать и трудиться без устали, а также имел репутацию Казановы.