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

К концу 1920-х годов ангел формализма и демон интуиционизма все еще боролись за душу каждого математика. Но, к удовольствию Гильберта, формализм мчался на всех парусах. Казалось, «программа Гильберта» вот-вот свершится. Никто, даже самые реакционно и революционно настроенные математики, не могли изгнать формалистов из фантасмагорического собора, выстроенного из бесконечностей Кантора. Никто не мог заставить их перестать слушать симфонию бесконечности — классического анализа.

После 1900 года, когда Гильберт прочитал ту знаменитую лекцию в Париже, на III Международном конгрессе математиков 1904 года, проведенном в Гейдельберге, он представил свою точку зрения на кризис оснований, но в течение следующих 15 лет больше не возвращался к этой теме — анализ и физика полностью захватили его. Движимый желанием дать отпор интуиционистам, он снова обратился к теме основ математики сначала в 1917 году, а затем постоянно возвращался к ней с 1922 года. Для Гильберта и формалистской школы объекты математической мысли — это символы сами по себе, и фундаментальная проблема — это проблема устойчивости или непротиворечивости математики. Чтобы окончательно обосновать математику, он не нуждался ни в Боге, как Кронекер, ни в предположении об особенностях нашего восприятия в соответствии с принципом индукции, как Пуанкаре, ни в оригинальной интуиции, как Брауэр, ни даже в аксиоме о бесконечности или аксиоме о редуктивности, как Рассел и Уайтхед. Как таковая проблема оснований математики должна была окончательно устраниться после проверки на непротиворечивость аксиоматической системы математики.

СИЛЬНЫЕ СТОРОНЫ ПРОГРАММЫ

Несложно проследить происхождение идей Гильберта. В 1900 году он опубликовал лекцию «Понятие числа», прочитанную годом ранее на ежегодной ассамблее Немецкого математического общества. После книги об основаниях геометрии эта работа стала его второй публикацией, касающейся аксиоматического метода. В ней он рассматривал два возможных подхода к математическим понятиям — генетический и аксиоматический. Классический пример применения генетического метода характерен для арифметики. Натуральные числа появляются на основе базовой интуиции счета: если требуется произвести вычитание любых натуральных чисел, система расширяется, чтобы включить в себя целые числа. Необходимость разделить два любых целых числа приводит к введению рациональных чисел, а чтобы иметь возможность извлекать корни, добавляются иррациональные числа и дается определение действительным числам. Гильберт отмечал, есть аксиоматический метод, типичный для геометрии (и для анализа, поскольку Гильберт показал, как аксиоматизировать действительные числа). Несмотря на высокую дидактическую ценность генетического метода, аксиоматический метод имеет преимущество обеспечения полной логической надежности. В этой ранней работе Гильберт открыто и впервые заявил о необходимости подхода к проблеме абсолютной непротиворечивости арифметики как к унаследованной от геометрии (относительную непротиворечивость которой он сам доказал). Этот вопрос занял второе место (ему предшествует только континуумгипотеза) в списке из 23 открытых проблем 1900 года; Гильберт вернулся к нему на конгрессе 1904 года, хотя и недооценил его сложность. Задача заключалась не в том, чтобы найти самые базовые модели, на которые можно было бы опереться, чтобы вывести непротиворечивость арифметики, как это было сделано с аксиомами геометрии (при этом была бы доказана только относительная непротиворечивость). Следовало разработать доказательство абсолютной непротиворечивости, основываясь на синтаксисе, а не на семантике, то есть выяснив, позволяет формальная система, выражающая арифметику, прийти к противоречиям или нет.

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

На первом этапе было необходимо формализовать теорию множеств, а также логику и арифметику. Наивные определения не позволяли вывести строгие рассуждения, лишенные парадоксов. Следовало полностью формализовать известную математику, переведя все ее содержимое в формальную систему, выраженную с помощью нового символического языка: 0 (число нуль), s (функция последующего члена), ¬ (не), v (или), ^ (и), →(вывод), Ǝ (квантор существования), перевернутое А(квантор всеобщности), = (равенство), х (переменная) и так далее. Как раз в 1928 году, спустя 50 лет после первого шага Фреге, Гильберт и Аккерман опубликовали «Основы теоретической логики» — учебник по дисциплине, сегодня называемой логикой первого порядка. Их формализация достигла канонического уровня, и сегодня она известна как система Гильберта — Аккермана. Они установили формальный синтаксис, а также предложили аксиомы и правила этой логики, что позволяет выводить новые формулы. Логика первого порядка превратилась в настоящее исчисление.

Вначале был знак.

Давид Гильберт, «Новые основания математики» (1922)

В учебнике Гильберта и Аккермана были сформулированы некоторые металогические вопросы о свойствах исчисления, ими разработанного. Они перекликались, в частности, с доказательством (в 1926 году предложенным Бернайсом) того, что элементарная логика, или логика пропозиций, является верной (любая доказуемая формула верна) и полной (любая логическая истина, в свою очередь, доказуема), и к этому же результату в 1922 году независимо пришел Эмиль Пост (1897- 1954). Авторы задавались вопросом — является ли таковой логика первого порядка? — хотя признавали, что ответ не найден. Ровно через год, в 1929 году, молодой австрийский логик Курт Гёдель доказал полноту логики первого порядка в своей докторской диссертации, написанной под руководством Ханса Хана (1879-1934), хотя опубликовал ее он лишь в 1930 году Эта логика была верной (все доказуемые формулы истинны) и полной (все логические истины, все тавтологии доказуемы). При исчислении предикатов первого порядка синтаксическое понятие дедукции и семантическое понятие истины совпадают, имеют одно и то же расширение.

Программа Гильберта неожиданно обрела успех: любая логически справедливая формула, то есть истинная в любой возможной интерпретации, выводима с помощью описанных исчислений. Но что произойдет, если к этому чистому исчислению предикатов добавить аксиомы и правила, которые относились бы к арифметике или к теории множеств? Останется ли оно верным и непротиворечивым? И полным?

На втором этапе в объект математического изучения следовало превратить само понятие доказательства, чтобы таким образом доказать непротиворечивость арифметики и искоренить все сомнения. В математике нет места полуправде. Для Гильберта математик занимается понятием математического доказательства, точно так же как физик проверяет работу своих приборов или философ критически осмысливает свои же аргументы. Разработка «теории доказательства» позволит рассматривать доказательства в качестве результата чистых сочетаний символов, согласно предписанным формальным правилам. В этих условиях было достаточно доказать, что никакое формальное выведение, никакое сочетание символов не может привести к формуле 0≠0 (что является противоречием). Так была бы установлена непротиворечивость арифметики. Достаточно доказать, что есть одна недоказуемая формула, поскольку если бы все формулы были доказуемы, мы могли бы вывести противоречие (доказав пропозицию и обратную ей), и система оказалась бы противоречивой. И наоборот, если бы система была противоречивой, поскольку из противоречия следует что угодно (ex contradictione sequitur quodlibet, как уверяли схоластики), мы могли бы доказать любую формулу (формула «если 0≠0, то Р» всегда истинна, справедлива, поскольку таковой не является предпосылка).

В 1920 годы Гильберт ввел идею о том, что его «теория доказательства» подходит к вопросу непротиворечивости на двух уровнях рассмотрения. С одной стороны, это математический уровень, как представлено в рамках формальной системы. С другой стороны, это метаматематический, дискурсивный уровень, на котором говорится об аксиоматизированной математике. На данном уровне следовало доказать непротиворечивость посредством ряда техник, которые изучали бы формальную систему извне, отключив ее от любого числового значения или значения, связанного с бесконечностью, просто в качестве конечных цепочек первичных знаков, на основе которых можно образовать формулы и доказательства в соответствии с некоторыми предопределенными правилами. Пропозиции, которые относятся к этому формальному скелету, к этой арифметике, лишенной значения, — это метаматематические пропозиции, которые формулируются не на языке объекта, а на метаязыке. Это как если бы на уроке английского использовался испанский язык, чтобы показать оттенки какого-нибудь англосаксонского слова. Вопрос о непротиворечивости в математике или вопрос, является ли формула 0≠0 доказуемой, — по сути, то же самое, что спрашивать, является ли определенная шахматная позиция правомерной, то есть можно ли достичь ее из исходного положения партии и по правилам передвижения фигур. Чтобы на него ответить, мы не играем в шахматы, а размышляем о собственно шахматах.

Сомневайся в данных, пока данные не оставят места сомнению.

Анри Пуанкаре

Но Гильберт настаивал на том, что математическое доказательство непротиворечивости арифметики должно удовлетворить как классических математиков, так и интуиционистов, то есть оно должно проводиться финитными, конструктивными методами, которые не требуют вмешательства бесконечности. В конце жизни Пуанкаре подчеркивал, что если для доказательства непротиворечивости арифметики — даже в математическом плане — воспользоваться принципом индукции, то есть пятой аксиомой Пеано, получится порочный круг: попытка доказать связность арифметики с помощью арифметического принципа. Нужно было доказать это посредством самоочевидных рассуждений, что сами математические методы, даже когда они предполагают присутствие актуальной бесконечности, справедливы, то есть не позволяют вывести противоречие. Более того, Гильберт хотел доказать не только непротиворечивость математики, но также ее полноту. Это был другой нерешенный вопрос из его лекции 1900 года: возможность решения любого математического вопроса.

Гильберту и его соратникам удалось доказать непротиворечивость некоторых простых формальных систем. Так, в 1922 году Гильберт сконцентрировался на элементарной части арифметики и, изучая вид доказуемых формул, сделал вывод, что формула 0≠0 — не из их числа. Это доказательство позже было развито Аккерманом в его докторской диссертации (датированной 1925 годом и написанной под руководством Гильберта), а также в 1927 году элегантно упрощено фон Нейманом. Но это были фрагментарные достижения: формальные арифметические системы, из которых следовала непротиворечивость, не включали в себя принцип индукции. В 1929 году польскому математику Мойжешу Пресбургеру (1904-1943) удалось доказать непротиворечивость арифметики, включающей в себя принцип индукции и сложение, но не умножение. Эти результаты обрели форму двухтомника, написанного Бернайсом от лица Гильберта и озаглавленного «Основания математики» (1934-1939). Однако непротиворечивость систем, описывающих достаточно большую область арифметики с натуральными числами, все еще оставалась неохваченной.

ГЁДЕЛЬ: БУРИ И ШКВАЛЫ

К 1930 году первый пункт программы Гильберта в целом был выполнен: логика, теория множеств и арифметика аксиоматизированы. Но все еще оставался вопрос об их непротиворечивости и полноте.

Гильберт вышел на пенсию, когда ему исполнилось 68 лет. В связи с получением звания почетного гражданина Кёнигсберга заслуженный профессор Гёттингенского университета произнес речь в своем родном городе. В ней он вновь отстаивал идею, что в математике нет неразрешимых проблем. Записывая обращение для местного радио, он четко произнес последнюю фразу своей речи: «Мы должны знать. Мы будем знать» и улыбнулся. Запись сохранилась, и если прислушаться, в конце можно уловить смех Гильберта. Это было 8 сентября 1930 года.

По иронии судьбы, за три дня до этого в Кёнигсберге состоялась конференция по эпистемологии точных наук. Цель встречи состояла в том, чтобы определить, на какой стадии находится разрешение кризиса оснований математики. Выступали представители каждого из связанных с основаниями течений. От логицизма — Рудольф Карнап (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 году этому польскому ученому удалось переехать в США и на несколько десятилетий превратить университет Беркли в мировую столицу математической логики. Он любил работать ночью и увлекался психотропными средствами, которые помогали ему бодрствовать и трудиться без устали, а также имел репутацию Казановы.

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

Альфред Тарский, 1968 год.

Еще одна ограничительная теорема

В 1933 году, через два года, после того как Гёдель объявил о двух результатах о неполноте, Тарский извлек на свет другую ограничительную теорему, хотя она уже была провозглашена и доказана Гёделем в письме Цермело, датированном 1931 годом. В этой ограничительной теореме установлено, что любая формальная теория первого порядка, содержащая базовую арифметику, неспособна (если она непротиворечива) выразить свое собственное понятие истины. Интересные непротиворечивые теории не могут содержать выражения «быть истинным» в своем языке, поскольку в этом случае они породили бы парадокс лжеца. С помощью гёделизации можно воспроизвести формулу Г, которая утверждает о самой себе, что она ложная. Воспользовавшись выражением «быть истинным», которое, предположительно, существует в языке, мы придем к следующему противоречию: Т истинное тогда и только тогда, если оно ложное, поскольку именно это утверждает Т. Как в случае с лжецом: я говорю правду, если я лгу. Без сомнения, математические логики сумели применить цикличность, лежащую в основе парадоксов, с большой пользой.

ENTSCHEIDUNGSPROBLEM, ИЛИ ПРОБЛЕМА РАЗРЕШЕНИЯ

На IX Международном конгрессе математиков, проходившем в 1928 году в Болонье, Гильберт воспользовался случаем, чтобы предложить свой план по спасению математики и обозначить следующий вопрос: существует ли механическая процедура, которая решала бы все и каждую проблему математики, алгоритм, способный принципиально разрешить все математические вопросы, который при заданной математической пропозиции дал бы нам знать, является она теоремой или нет? Другими словами, является ли она разрешимой в математике? Как и на вопросы непротиворечивости и полноты, ответ на нее был отрицательным. После теорем Гёделя стало ясно, что ответ на эту проблему — категорическое «нет», поскольку математика является неполной: предполагаемый алгоритм в течение бесконечного времени «думал» бы над неразрешимым высказыванием, поскольку ни оно, ни его отрицание не являются теоремой. Следовательно, ответ на проблему разрешения оставалось дать только для логики первого порядка, которая, напомним, является полной. Однако в 1936 году Алан Тьюринг (1912-1954) и независимо от него Алонзо Чёрч (1903-1995) доказали, что логика первого порядка также неразрешима.

Тезис Чёрча — Тьюринга

Для начала Тьюринг сформулировал, что означает думать как машина, механически. Его первая победа заключалась в определении понятия вычислимой функции: это функция, которую способна вычислить машина Тьюринга — вид компьютера без ограничений в пространстве или времени. Одновременно, по другую сторону Атлантического океана, Чёрч пришел к аналогичным выводам, разработав формальную систему, которую назвал лямбда-исчислением. С тех пор под названием тезиса Чёрча — Тьюринга известен постулат, утверждающий, что любое альтернативное определение вычислимости равносильно определению, данному Тьюрингом в терминах его машин. Прибегнув к изобретательному варианту диагонального аргумента Кантора, Тьюринг доказал, что существует намного больше функций, чем машин Тьюринга. Другими словами, существуют невычислимые функции.

Исчислимые функции, как и машины Тьюринга, имеются в счетном количестве, то есть они как иголки в стоге сена всех функций.

Наконец, рассмотрев проблему остановки, он предложил отрицательный ответ на вопрос Гильберта — Entscheidungsproblem: если бы существовала эта процедура, она также была бы способна определить за конечное время, останавливается любая машина Тьюринга через конечное число шагов или входит в бесконечную петлю, когда на входе вводятся некоторые данные. Но последнее, как он доказал, невозможно. Не существует алгоритма, способного получить на входе логическое или математическое высказывание и выдать на выходе: «теорема» или «не теорема» (хотя свойство выводимости действительно разрешимо в ограниченной логике пропозиций).

Сланцевая статуя и портрет Алана Тьюринга в музее Блетчли-Парка.

Это означает, что теории первого порядка не могут контролировать кардинальное число своих моделей. Так, например, если сформулировать аксиомы арифметики Пеано в логике второго порядка (неполной), то они категориальны (то есть все их возможные модели изоморфны, имеют одно и то же кардинальное число), но если сформулировать их в логике первого порядка (полной), то мы расплачиваемся тем, что теряем категориальность. Появятся стандартная и нестандартная модели натуральных чисел. Скупость логика имеет свою цену.

Вскоре Гёдель предположил, что континуум-гипотеза Кантора, которую в 1925 году Гильберт считал почти доказанной на основе выведенной из его теории доказательства изящной техники, была примером неразрешимого высказывания в привычной теории множеств. В 1938 году, ограничиваясь подмножеством конструктивных множеств, Гёдель доказал: невозможно доказать, что она ложная в ZFC. И обратно, в 1963 году Пол Коэн (1934-2007), использовав метод форсинга, доказал: также невозможно доказать, что она истина в ZFC. Гёдель и Коэн построили модели, в которых гипотеза истинна и ложна соответственно. Так что ни утверждение, ни отрицание континуум-гипотезы недоказуемо. То же самое происходит с аксиомой выбора, непротиворечивость и независимость которой относительно остальных аксиом также доказали оба математика. Следовательно, статус аксиомы выбора и континуум-гипотезы в теории множеств аналогичен статусу аксиомы параллельных прямых в геометрии. Рай Кантора — не единственный доступный рай теории множеств.

Программа Гильберта выбыла с поля боя после двух ударов, полученных от Гёделя. Как первая, так и вторая проблемы знаменитого списка из 23 проблем Гильберта в итоге оказались решены, хотя и способом, который в 1900 году было трудно вообразить. В математике истинное не совпадает с доказуемым. Аксиом и правил выведения, которые Гильберт поставил во главу угла, было недостаточно, чтобы вывести все математические теоремы, при этом можно представить себе пропозиции истинные, но невыводимые в формальной системе классической математики. «Арифметика непротиворечива» — вот пример этого типа неразрешимых пропозиций. Гильберт, узнав о теоремах Гёделя спустя несколько дней (благодаря Бернайсу), попытался спасти часть своей программы, позволив использование нефинитных методов для доказательства непротиворечивости математики. Но эти методы совсем не очевидны. Гильберт и его команда походили на пастухов, которые построили убежище, чтобы защитить стадо от волков, но не могли быть уверены в том, что внутри нет ни одного волка.

БАЛАНС: ТРЕЩИНЫ ФОРМАЛИЗМА

Несмотря на то что скептические сомнения так и не были устранены, классическая математика все же чувствовала себя неплохо. Твердость и энтузиазм Гильберта смогли поддерживать курс большого корабля математики. С точки зрения обоснования математики формализм был отправлен в нокаут, но в отношении философии математики выиграли по очкам.

Часто говорят, что платоническая позиция лучше всего характеризует отношение математика к сути этой дисциплины. Математик верит в реальность математических объектов. Но, конечно, когда философы начинают одолевать его своими вопросами, он бежит и прячется под юбкой формализма и заявляет: «Математика — всего лишь сочетание знаков, лишенных значения, красивая игра формул, еще интереснее, чем шахматы». Но при этом ее отношение к их реальному значению скрыто сумерками: если нужна точность, надо исключить любое значение; но если нужно, чтобы математика имела смысл, нужно отказаться от точности. Для строгого формалиста любая математическая теория — всего лишь сочетание знаков, не имеющих значения, как иероглиф, лишенный смысла. Большинство математиков являются платонистами по будням, пока работают с теоремами, пропозициями и выводами, и становятся формалистами по выходным, когда оставляют работу и беседуют с философами.

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

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

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

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

Если мы посмотрим на математика за работой, поскольку статьи — всего лишь продукты его деятельности, то удивимся, сколько неформальных рассуждений он выдает. Что доказывают ограничительные теоремы Гёделя или Тарского для математика в действии? Что математика — слишком крупный кролик для того, чтобы вытащить его из столь маленького цилиндра аксиоматической системы, каким бы ловким ни был этот фокусник Гильберт. Более того, аксиоматика возможна, только если ей предшествовала фаза работы с моделью, то есть аксиомы чисел могут быть сформулированы, если уже есть некоторое представление о том объекте, с которым мы имеем дело. Генетический метод предшествует аксиоматическому, и замена первого вторым предполагает похищение честно заработанного (аксиоматика немедленно присваивает себе все построенное).

Могила Гильберта в Гёттингене. У основания памятника высечена знаменитая фраза «Мы должны знать. Мы будем знать».

Альфред Тарский и Курт Гёдель в Вене в 1935 году. Своими ограничительными теоремами оба поспособствовали разрушению возведенной Г ильбертом конструкции математики.

Давид Гильберт, 1930-е годы. 

БУРБАКИ

После Второй мировой войны ультраформалистская концепция математики сформировалась в виде бурбакизма. Группа молодых французских математиков (Андре Вейль, Анри Картан, Жан Дьёдонне и другие) собралась в 1935 году и решила назвать себя именем потерпевшего поражение французского генерала Бурбаки, поскольку еще в университете один шутник-студент, учившийся на курс старше, подбросил им неверные теоремы, носящие имена известных генералов. Коллектив Бурбаки подписывался под многочисленными докладами и монографиями и считал себя настоящим интеллектуальным наследником Гильберта. Под лозунгом «Долой Евклида!» Бурбаки представлял математику в абстрактном и чистом виде, который выкристаллизовался в виде высокоаксиоматичной работы «Элементы математики». Эта традиция представлять математику как подарок небес, лишенный любой земной неточности, в течение 1970-1980-х годов оказывала влияние на преподавание абстрактной теории множеств в средних школах Европы.

Собрание Бурбаки, 1938 год. Слева направо: С. Вейль, Ш. Пизо, А. Вейль, Ж. Дьёдонне, К. Шаботи, Ш. Эресманн и Ж. Дельсарт.

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

ГИБЕЛЬ БОГОВ

С приходом Гитлера к власти в 1933 году Людвиг Бибербах (присоединившийся к нацистской партии) встал во главе математики в Германии, продвигая «арийскую, или немецкую», математику (Deutsche Mathematik). Теория относительности была отвергнута как еврейское мошенничество. Та же участь постигла теорию множеств — вероятно, из-за использования в ней еврейского алфавита для обозначения трансфинитных кардинальных чисел (хотя также сыграло роль то, что Бибербах был сторонником Брауэра в Берлине). Еврейским преподавателям было запрещено вести занятия, и одного за другим их сняли с должностей.

Математический институт в Гёттингене быстро сдал позиции, и его международный престиж был утрачен, к большому огорчению Гильберта. Герман Вейль — любимый ученик, который сменил его на кафедре, — был вынужден эмигрировать, поскольку его жена была еврейкой по происхождению, и в итоге он присоединился к Альберту Эйнштейну и Курту Гёделю в Институте перспективных исследований в Принстоне. Рихард Курант был отстранен от работы и обосновался в Нью-Йоркском университете. Бернайс вернулся в Швейцарию.

Гильберт был обескуражен новой политической ситуацией в Германии. Как-то он спросил у Блюменталя, своего первого аспиранта, какой курс тот читает, и услышал в ответ, что ему больше не разрешено вести занятия. Старик был ужасно возмущен. Когда на банкете его усадили рядом с новым министром образования и тот спросил: «Как в Гёттингене с математикой теперь, когда его очистили от еврейского влияния?», Гильберт парировал: «Математика в Гёттингене? Но ведь ее уже нет!»

С началом Второй мировой войны все стало еще более мрачным. Блюменталь эмигрировал в Нидерланды, однако немцы захватили эту страну в 1940-м и его арестовали. Он умер в том же году в печально известном лагере Терезиенштадт, что на территории современной Чехии. Феликс Хаусдорф, который написал первый учебник по теории множеств, покончил жизнь самоубийством, когда узнал, что ему и его семье предстоит депортация в концентрационный лагерь. Другие, например Банах, выжили, но серьезно пострадали физически, работая «кормителями вшей» в возглавляемом немцами бактериологическом институте, где исследовался тиф.

Давид Гильберт умер в Гёттингене 14 февраля 1943 года под рев орудий. На похоронах ученого присутствовали менее дюжины человек. Но сегодня живы слова, ставшие его эпитафией: Wir müssen wissen. Wir werden wissen — «Мы должны знать. Мы будем знать».