В каком контексте возникла теорема о неполноте Гёделя, и почему она так важна?

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

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

Математики тоже хотели бы как-то механизировать, упростить процесс доказательства. Ведь как было бы хорошо. Ты математик, или физик, наблюдаешь десять частных случаев, и, кажется, видишь закономерность. Ты не уверен, что оно верно. Тогда ты формулируешь ее на специальном логическом языке, идешь в библиотеку, и просишь первые сорок томов труда «Вся математика. Все математические формулы вплоть до двадцати символов». Находишь в нем свое утверждение (или отрицание к нему), видишь его доказательство. Ну здорово же. Утопия.

В 1913 году Бертран Рассел и Альфред Норт Уайтхед выпускают труд «Principia Mathematica», («Принципы математики», «Основы математики») который представил в единой форме основные теоремы некоторых областей математики. Это еще не книга из нашего мысленного эксперимента, но первый шаг к ней. Рассел и Уайтхед разработали способ говорить о математике почти только математическим языком, без вставок естественного языка. Книга устроена так: в начале дается система обозначений, правило вывода одних утверждений из других, и описывается небольшой набор базовых понятий и аксиом, которые эти понятия связывают. Затем из этих аксиом и ранее доказанных теорем доказываются все более и более глубокие утверждения. Совокупность базовых понятий, аксиом, и правил вывода еще называют формальной системой. Такую книгу очень удобно переводить: первые, например, 20 страниц вступления требуют перевода, но оставшиеся 180 страниц математического текста перепечатываются без изменений.
В этой книге Рассел отходит от наивной теории множеств, предложенной Фреге, чтобы избежать парадокса, с которым он столкнулся ранее, и который теперь носит его имя.

Пусть R — множество всех множеств, которые не содержат себя в качестве элемента. Содержит ли R само себя? Если да, то по определению оно не должно себя содержать. Если нет, то оно должно себя содержать. Противоречие.

Я попробую объяснить его на естественном языке. Давайте назовём себяшными такие слова, которые описывают сами себя. Например, русское и english – себяшные слова, а russian и немецкое — несебяшные. Двадцатичетырехбуквенное — себяшное слово, потому что в нем двадцать четыре буквы, а недвадцатичетырехбуквенное — тоже себяшное слово, потому что в нем не двадцать четыре буквы. Рассмотрим утверждение «слово «несебяшное» — является себяшным». То есть, «слово «несебяшное» описывает себя?». Если да, то слово «несебяшное» несебяшное, а мы предполагали что себяшное. Наоборот, если нет, то «несебяшное» не должно быть несебяшным, значит оно себяшное, но мы предполагали что нет. Опять противоречие. Это утверждение парадоксально, оно ни истинно, ни ложно.

В Principia Mathematica Рассел обходит этот парадокс, но делает это довольно искусственно, и получает критику от других математиков. Немедленно встает вопрос, не привели ли его изменения к новым парадоксам, может быть более изощренным. Отсутствие парадоксов, утверждений, которые одновременно верны и неверны, называется непротиворечивостью. Непротиворечивость в некотором смысле естественное свойство, если формальная система им не обладает, то она нам неинтересна. Доказать непротиворечивость своей системы Рассел не смог. Из этой и похожих проблем выросла более глобальная задача.

В 1920-х годах известный математик Дэвид Гильберт, автор «Оснований геометрии» поставил задачу поиска основания для всей математики.

Это должна была быть формальная система, для которой доказаны:
1) Полнота — любое утверждение либо доказуемо, либо опровержимо; причем доказуемо средствами этой формальной системы. Другими словами, каждое утверждение либо истинно, либо ложно, и это можно доказать, не вводя новых понятий.
2) Разрешимость — существует алгоритм, который для произвольного утверждения говорит, истинно оно или нет.
3) Непротиворечивость — нет такого утверждения, что и оно истинно, и его отрицание истинно.

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

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

Такая формальная система должна была формализовать все математические утверждения.

В 1930 году 24-летний математик Курт Гёдель выступил на конгрессе математиков в Кенигсберге с двумя утверждениями о формальной арифметике.

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

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

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

Гилберту казалось, что математика стоит на пороге доказательства самой себя, полного описания, полного решения. Доказать пару теорем, и мы получим мощный инструмент механического доказательства математических утверждений. Гёдель показал, что не просто не существует такого инструмента, некоторые задачи решить в принципе невозможно. Мы никогда не сможем остановиться, описав конечное число абстракций и соотношений между ними, ведь это задаст формальную систему. Действуя внутри нее, мы всегда можем столкнуться с недоказуемым утверждением (нерешаемой задачей, недоказуемой гипотезой). Кроме того, мы вынуждены двигаться в постоянном сомнении, что встретим противоречие (ведь доказать непротиворечивость изнутри невозможно). Может быть, какая-то область математики прямо сейчас содержит противоречие в своих аксиомах? Чтобы уверенно ответить «нет», чтобы решить все поставленные задачи, мы вынуждены строить новые абстракции. А это приведет нас к новой формальной системе с теми же изъянами, поставит новые вопросы. Что гораздо хуже, нет гарантии, что уже существующая математика непротиворечива. В теории, в любой момент может оказаться, что и 2*2=4, и 2 2 = 5, и 2 2 = 0, и E = mc2 + AI. Разум и логика таких гарантий не дают. Полного решения математики нет.

Автор: Егор Кривотулов

Оригинал