Математика. Утрата определенности.
Шрифт:
Гильберт был уверен, что его теория доказательств позволит разрешить проблемы непротиворечивости и полноты.
К 30-м годам были получены некоторые результаты о полноте различных аксиоматических систем. Сам Гильберт построил несколько искусственную систему, охватывающую лишь часть арифметики, и доказал ее полноту и непротиворечивость. Аналогичные ограниченные результаты вскоре удалось получить и другим авторам. Так, была доказана непротиворечивость и даже полнота таких сравнительно тривиальных аксиоматических систем, как исчисление высказываний. Некоторые из доказательств принадлежали ученикам Гильберта. В 1930 г. Курт Гёдель (1906-1978), ставший впоследствии профессором Института высших исследований в Принстоне, доказал полноту исчисления предикатов первой ступени, охватывающего высказывания и пропозициональные функции. {136} Формалисты были в восторге от полученных результатов. Гильберт еще больше уверовал в то, что его метаматематике (его теории
136
Исчисление предикатов первой ступени, как доказали Гильберт и другие, непротиворечиво, и аксиомы его независимы.
Но уже в следующем году Гёдель опубликовал другую работу, поистине открывшую ящик Пандоры. В этой работе, называвшейся «О формально неразрешимых утверждениях [оснований математики] и родственных систем» (1931), содержались два поразительных результата. Наибольшее смятение у математиков вызвал один из них — утверждающий, что непротиворечивость любой достаточно мощной математической системы, охватывающей арифметику целых чисел, не может быть установлена средствами самой этой системы на основе математических принципов, принятых различными школами в основаниях математики: логицистами, формалистами и представителями теоретико-множественного направления. Это утверждение Гёделя прежде всего касалось формалистской школы, ибо Гильберт по собственной воле ограничил свою метаматематику такими логическими принципами, которые были приемлемы даже для интуиционистов, чем сузил арсенал доступных формалистам логических средств. Результат Гёделя послужил поводом для известного высказывания Германа Вейля: «Бог существует, поскольку математика, несомненно, непротиворечива, но существует и дьявол, поскольку доказать ее непротиворечивость мы не можем».
Приведенный результат Гёделя является следствием из установленного им другого, не менее поразительного результата, который известен как теорема Гёделя о неполноте.Она утверждает, что если формальная теория T, включающая арифметику целых чисел, непротиворечива, то она неполна. {137} Иначе говоря, существует имеющее смысл утверждение арифметики целых чисел (обозначим его S), которое в рамках данной теории невозможно ни доказать, ни опровергнуть. Но либо утверждение S,либо утверждение «не S» истинно. Следовательно, в арифметике существует истинное утверждение, которое недоказуемо, а значит, и неразрешимо. Хотя Гёдель не указал точно, о каком классе аксиоматических систем идет речь в полученном им результате, теорема о неполноте применима к системам Рассела — Уайтхеда, Цермело — Френкеля, гильбертовской аксиоматике чисел и ко всем наиболее распространенным аксиоматическим системам. Казалось, непротиворечивость достигается ценой неполноты. И словно для того, чтобы разбередить рану и вновь унизить математиков, истинность некоторых неразрешимых утверждений удалось доказать с помощью рассуждений (правил логики), выходящих за рамки допустимого в перечисленных выше формальных системах.
137
Теорема Гёделя о неполноте применима и в случае обращения к исчислению предикатов второй ступени (гл. VIII). [По поводу теорем Гёделя см., например, [81], а также обращенные к более широкому кругу читателей статью [82] и брошюру [83]. — Ред.]
Как и следовало ожидать, получение столь поразительных результатов потребовало от Гёделя немалых усилий. Основная идея его работы состояла в том, чтобы каждому символу или каждой последовательности символов в системе, принятой, например, логицистами или формалистами, сопоставить определенное число. Любому утверждению или последовательности утверждений, образующих доказательство, Гёдель также ставил в соответствие некоторое число — гёделевский номер. {138}
138
Доступное изложение теоремы Гёделя и некоторых других упомянутых ниже понятий и результатов имеется в небольшой по объему и требующей минимальной предварительной подготовки книге [84].
Рассмотрим схему Гёделя подробнее. Произведенная Гёделем арифметизация состояла в том, что каждому математическому понятию он сопоставлял некоторое натуральное число. Числу 1 Гёдель поставил в соответствие число 1, знаку равенства — число 2, введенному Гильбертом символу отрицания — число 3, знаку плюс — число 5 и т.д. Таким образом, набору символов 1 = 1 Гёдель сопоставляет числовые символы 1, 2, 1, тогда как равенству (формуле) 1 = 1 сопоставляется не три (числовых) символа 1, 2, 1, а единственное число, структура которого позволяла бы восстановить все входящие в него символы-компоненты. А именно: Гёдель выбрал три первых простых числа 2, 3
Каждой формуле рассматриваемых систем Гёдель поставил в соответствие некоторое число. Каждой последовательности формул, образующих доказательство, он также сопоставил определенное число. Показатели в разложении номера доказательства в произведение степеней простых чисел сами не являются простыми числами, хотя и связаны с ними довольно просто. Так, число 2 900•3 90может быть гёделевским номером доказательства. Это доказательство содержит формулы с гёделевскими номерами 900 и 90. Следовательно, по номеру доказательства мы можем восстановить входящие в него формулы.
Утверждения метаматематики о формулах рассматриваемой аксиоматической системы Гёдель также представил с помощью чисел. Каждое метаматематическое утверждение получило свой гёделевский номер. Тем самым получено «отображение» метаматематики в арифметику.
Осуществив перевод словесных утверждений метаматематики на арифметический язык, Гёдель показал, как построить арифметическое утверждение G,означающее в переводе на метаматематический язык, что утверждение с гёделевским номером mнедоказуемо. Но утверждение G, рассматриваемое как последовательность символов, имеет гёделевский номер m.Следовательно, Gутверждает о самом себе, что оно недоказуемо. Итак, если Gдоказуемо, то оно должно быть недоказуемым, а если Gнедоказуемо, то оно должно быть доказуемым, поскольку недоказуемо, что оно недоказуемо. Так как любое арифметическое утверждение либо истинно, либо ложно, формальная система, которой принадлежит G, неполна (если только она непротиворечива). Тем не менее арифметическое утверждение Gистинно, так как является утверждением о целых числах, которое можно доказать, используя более интуитивные рассуждения, чем допускает формальная система.
Поясним суть гёделевской схемы на примере. Рассмотрим утверждение S: «Это утверждение ложно». Оно приводит к противоречию. Действительно, если S,рассматриваемое как единое целое, истинно, то оно, согласно ему самому, должно быть ложным, а если Sложно, то ложно, что Sложно, в силу чего Sдолжно быть истинным. Гёдель заменил слово «ложно» словом «недоказуемо», превратив Sв утверждение S— «Это утверждение недоказуемо». Если утверждение недоказуемо, то утверждаемое им истинно. С другой стороны, если утверждение доказуемо, то оно ложно, или, в соответствии с обычной логикой, если утверждение истинно, то оно недоказуемо. Следовательно, утверждение истинно в том и только в том случае, если оно недоказуемо. Мы приходим не к противоречию, а к истинному утверждению, которое недоказуемо, т.е. неразрешимо.
Заготовив впрок неразрешимое утверждение, Гёдель построил арифметическое утверждение A,соответствующее метаматематическому утверждению «Арифметика непротиворечива», и доказал, что из Aследует G.Поэтому если бы Aбыло доказуемым, то и Gбыло бы доказуемым. Но так как Gнеразрешимо, Aнедоказуемо. Иными словами, утверждение Aнеразрешимо. Тем самым установлена невозможность доказать «внутренними средствами» (т.е. в рамках той же системы) непротиворечивость арифметики любым методом — с помощью любой системы логических принципов, представимой в виде арифметической системы.
На первый взгляд кажется, что неполноты можно было бы избежать, если ввести в формальную систему дополнительный логический принцип или математическую аксиому. Но метод Гёделя позволяет доказать, что если дополнительное утверждение допускает перевод на язык арифметики по предложенной Гёделем схеме (согласно которой символам и формулам мы ставим в соответствие некоторые числа — их гёделевские номера), то и в расширенной системе можно сформулировать неразрешимое утверждение. Иначе говоря, избежать неразрешимых утверждений и доказать непротиворечивость можно лишь с помощью логических принципов, «не отображаемых» в арифметику. Чтобы пояснить суть дела, воспользуемся аналогией (хотя и несколько неточной): если бы логические принципы и математические аксиомы были сформулированы на японском языке, а арифметизация Гёделя означала бы перевод на английский язык, то результаты Гёделя получались бы до тех пор, пока был бы осуществим перевод с японского на английский.