Текст книги "Teopeмa Гёделя"

Автор книги: Эрнст Нагель

Соавторы: Джеймс Ньюмен
сообщить о нарушении

Текущая страница: 5 (всего у книги 6 страниц)

7.3. Изложение доказательств

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

Прежде всего Гёдель показывает (1), как построить арифметическую формулу G, представляющую («кодирующую») метаматематическое высказывание «формула G недоказуема». Иначе говоря, формула G гласит о себе самой, что она недоказуема.

Идея построения такой формулы G по существу заимствована из рассуждения, приводящего к парадоксу Ришара. В этом парадоксе, как мы помним, выражению «ришарово число» сопоставляется некоторое число n, после чего рассматривается предложение «n есть ришарово число». В гёделевском же доказательстве формуле G сопоставляется некоторое число h, причем это делается так, чтобы оно соответствовало предложению «Формула, которой сопоставлено число h, недоказуема». Но затем Гёделю удается показать (2), что формула G доказуема тогда и только тогда, когда доказуемо ее формальное отрицание ~G. И этот шаг доказательства аналогичен соответствующему этому рассуждению в парадоксе Ришара, где доказывается, что п есть ришарово число в том и только в том случае, если п не есть ришарово число. Но если некоторая формула и ее отрицание доказуемы, то арифметическое исчисление, в котором возможны оба доказательства, противоречиво.

Значит, если это исчисление непротиворечиво, то как G, так и ~ G не выводимы из аксиом арифметики. Следовательно, если арифметика непротиворечива, то G является формально неразрешимой формулой. Далее Гёдель доказывает (3), что хотя формула G формально недоказуема, она является тем не менее истинной арифметической формулой. Она является истинной в том смысле, что утверждает про каждое натуральное число, что оно обладает некоторым арифметическим свойством, причем свойство это такого рода, что наличие его у каждого натурального числа можно действительно подтвердить посредством прямой проверки (4). Поскольку формула G, будучи истинной, является формально недоказуемой, система аксиом арифметики неполна. Иными словами, из аксиом арифметики нельзя вывести все истинные стремления арифметики. Более того, Гёдель доказал существенную неполноту[19]19
  Это свойство называют чаще непополнимостью. – Прим. перев.


[Закрыть] арифметики: даже если присоединить к ее аксиоматике новые аксиомы, обеспечивающие выводимость истинной формулы G, все равно и для такой пополненной (расширенной) системы можно всегда указать истинную, но формально недоказуемую формулу (5). В заключение Гёдель указал, как построить арифметическую формулу А, представляющую метаматематическое высказывание «Арифметика непротиворечива», и доказал, что формула «А ﬤ G» формально недоказуема. Из этого следует недоказуемость и самой формулы А. Окончательный вывод: непротиворечивость арифметики нельзя установить посредством рассуждения, представимого в формальном арифметическом исчислении.

Перейдем теперь к более подробному изложению доказательства теоремы Гёделя.

1. Мы уже определили выше формулу «~ Dem(x, z)», представляющую в формальном арифметическом исчислении метаматематическое высказывание: «последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z». Теперь мы доставив перед формулой приставку «∀x», являющуюся формальным аналогом языкового оборота «для всех x» (или «для любого x»), и получим в результате новую формулу «∀ x ~ Dem (x, z)», представляющую в формальной арифметике метаматематическое высказывание: «для любого x последовательность формул, имеющая гёделевский номер x, не является доказательством формулы, имеющей гёделевский номер z». Таким образом, эта новая формула является как раз той формулой формального арифметического исчисления, которая представляет в нем метаматематическое высказывание «формула, имеющая гёделевский номер z, недоказуема», или, что то же: «для формулы с гёделевским номером z нельзя построить доказательство».

Гёдель далее показал, что некоторый частный случай этой формулы является формально недоказуемым. Чтобы получить формулу, мы будем исходить из следующей формулы:

∀ x ~ Dem(x, sub(y, 13, y)) (1)

Эта формула, принадлежащая формальному арифметическому исчислению, представляет некоторое метаматематическое высказывание. Какое же именно? Читатель должен помнить, что выражение «sub(y, 13, y)» обозначает некоторое число, которое есть гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер у, подстановкой вместо переменной, имеющей гёделевский номер 13, (т. е. переменной y) цифры, обозначающей число у. Отсюда видно, что формула (1) представляет метаматематическое высказывание: «формула, имеющая в качестве гёделевского номера число sub(y, 13, y), недоказуема».

Но так как формула (1) принадлежит арифметическому исчислению, она имеет некоторый гёделевский номер, который можно фактически вычислить. Пусть этим номером является число n. Подставим в (1) вместо переменной, имеющей гёделевский номер 13 (т. е. вместо переменной «y»), цифру, обозначающую это число n. В результате подстановки мы получим некоторую формулу, которую назовем (в честь Гёделя) «G»:

∀ x ~ Dem(x, sub(n, 13, n)). (G)

Формула G и есть тот частный случай формулы (1), который мы хотели построить. Формула G принадлежит арифметическому исчислению и должна иметь некоторый гёделевский номер. Каков же этот номер? Нетрудно показать, что таким номером задается число sub(n, 13, n). В самом деле, вспомним, что sub(n, 13, n) есть гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер n, подстановкой вместо переменной «y» (имеющей гёделевский номер 13) цифры, обозначающей число п. Но ведь формула G как раз и получена из формулы, имеющей гёделевский номер n (т. е. из формулы (1)), подстановкой цифры для числа n вместо входящей в формулу переменной у. Таким образом, действительно sub(n, 13, n) есть гёделевский номер формулы G.

Однако формула G – арифметическая формула, которая представляет в арифметическом исчислении математическое высказывание

«формула „∀ x ~ Dem(x, sub(n, 13, n))“ недоказуема».

Можно, следовательно, сказать, что формула G утверждает свою собственную недоказуемость.

2. Следующий шаг, как уже говорилось, состоит в доказательстве того факта, что формула G является формально недоказуемой. Доказательство очень похоже на рассуждение, приводящее к парадоксу Ришара, но не подвержено тем возражениям, которые вызывает последнее.

^{Как мы помним, в парадоксе Ришара фигурирует некоторое число n, связанное с определенным математическим высказыванием. В рассуждении же Гёделя число п связывается с определенной арифметической формулой (которая лишь прелставляет метаматематическое высказывание). Таким образом, в теореме Гёделя в отличие от парадокса Ришара идет речь о некотором арифметическом свойстве чисел (задается вопрос, обладает ли число sub(n, 3, n) свойством, выражаемым формулой «∀ x ~ Dem(x, sub(n, 13, n))»), а не о метаматематическом, благодаря чему и не возникает дискредитирующего парадокса Ришара смешения высказывания на языке арифметики с высказыванием об арифметике.}

Ход рассуждения относительно несложен. Задача его сводится к тому, чтобы доказать, что если бы формула G была доказуема, то ее формальное отрицание (т. е. формула «~ ∀ x ~ Dem(x, sub(n, 13, n))» также было бы доказуемо, и обратно, если бы отрицание формулы G было доказуемо, то была бы доказуема и сама формула G. Отсюда мы получаем, что формула G доказуема в том и только в том случае, если доказуема формула ~ G.

^{Это утверждение доказано, строго говоря, не самим Гёделем, а Аж, Б. Россером (1936). Гёдель же получил несколько более слабый результат, позволяющий, впрочем, получить все интересующие нас важные выводы.}

Воспроизведем вкратце первую часть рассуждения Гёделя, согласно которой, если G доказуема, то и ~ G доказуема. Пусть G доказуема. Тогда должна существовать последовательность арифметических формул, являющаяся доказательством для G. Пусть гёделевский номер доказательства есть k. В таком случае между этим k и числом sub(n, 13, n), являющимся гёделевским номером G, должно иметь место арифметическое отношение, обозначаемое через «Dem(x, z)», т. е. «Dem(k, sub(n, 13, n)» должна быть истинной арифметической формулой. Можно, однако, показать, что это арифметическое отношение обладает тем свойством, что если оно имеет место для каких– либо двух чисел, то формула, выражающая это обстоятельство, непременно доказуема. Таким образом, формула «Dem(x, sub(n, 13, n))» не только истинна, но и формально доказуема, т. е. является теоремой. Но правила вывода элементарной логики позволяют нам немедленно вывести из этой теоремы формулу «~ ∀ x ~ Dem(x, sub(n, 13, n))». Таким образом, мы вывели из доказуемости формулы G доказуемость ее формального отрицания. Значит, если наша формальная система непротиворечива, то G в ней недоказуема.

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

Как мы уже отмечали, если и некоторая формула, и ее отрицание выводимы из некоторой системы аксиом, то эта система противоречива (несовместна). Поэтому если аксиомы формализованной системы арифметики совместимы, то ни G, ни ее отрицание не могут быть доказуемыми. Иначе говоря, если наши аксиомы непротиворечивы, то G формально неразрешима в том точном смысле, что ни G, ни ~ G не выводимы из арифметических аксиом.

3. Важность предыдущего заключения не сразу бросается в глаза. Что особенного – можно было бы задать вопрос – в том, что некоторая формула, сформулированная на арифметическом языке, оказалась неразрешимой? Но приходится признать, что из этого результата действительно вытекают чрезвычайно важные выводы. Все дело в том, что, хотя формула G и является недоказуемой, можно, как выясняется, чисто метаматематическим рассуждением установить ее истинность. Иными словами, удается показать, что формула G выражает некоторое (довольно-таки громоздко выражаемое, но тем не менее вполне определенное) свойство, с необходимостью принадлежащее всем натуральным числам (аналогично, скажем, свойству, выражаемому гораздо более простой формулой «∀ x ~ (x + 3 = 2)», интерпретируемой обычно как утверждение, что никакое натуральное число, сложенное с числом 3, не дает в сумме 2).

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

«формула „∀ x ~ Dem(x, sub(n, 13, n))“ недоказуема»

истинно. Во-вторых, такое утверждение представляется (выражается) в арифметике той самой формулой, которая в нем упоминается. В-третьих, мы вспоминаем, что истинным метаматическим утверждениям при осуществляемом посредством гёделевской нумерации отображении их в арифметику соответствуют истинные же арифметические формулы. (Именно это обстоятельство обусловливает всю плодотворность такого отображения; ситуация здесь совершенно та же, что в аналитической геометрии, где координатное «кодирование» обеспечивает перевод истинных геометрических высказываний в истинные алгебраические высказывания.) Отсюда и вытекает, что формула G, соответствующая истинному метаматематическому высказыванию, сама должна быть истинной. Следует, однако, еще раз подчеркнуть, что истинность арифметического высказывания установлена нами отнюдь не формальным выводом выражающей его формулы из аксиом, а посредством некоторого метаматематического рассуждения.

4. Теперь нам придется напомнить читателю понятие «полноты», введенное нами в заключение раздела, посвященного исчислению высказываний. Мы назвали тогда систему аксиом полной, если любое истинное предложение, выражаемое на языке данной системы, можно из них вывести. В противном случае (т. е. если не каждое истинное предложение, выразимое в данной системе, выводится из ее аксиом) система аксиом «неполна». Но мы только что как раз и установили, что G есть истинная арифметическая формула, не выводимая из арифметических аксиом, иными словами, система аксиом арифметики неполна (разумеется, в предположении непротиворечивости этой системы аксиом), более того, формальная арифметика существенно неполна: даже если добавить к ней формулу G в качестве новой аксиомы, расширенная система аксиом будет все равно недостаточна для формального вывода всех арифметических истин. Дело в том, что по отношению к пополненной таким образом системе аксиом мы можем провести в точности то же рассуждение, что и раньше, и та же конструкция даст нам новый пример предложения, истинного в расширенной арифметической системе, но не выводимого из ее аксиом, и такое предложение будет снова выражаться неразрешимой арифметической формулой. И этот поистине удивительный вывод остается в силе независимо от того, сколько раз мы ни производили бы такое расширение системы. Таким образом, мы вынуждены признать некоторую принципиальную ограниченность возможностей аксиоматического метода. Вопреки, казалось бы, самым естественным ожиданиям, запас арифметических истин оказывается столь обширным, что ни из никакой точно зафиксированной системы аксиом не удается их все формально вывести.

5. Мы подошли теперь к месту, которое можно назвать кодой это поразительной интеллектуальной симфонии – творения Гёделя. Описанные выше шаги позволили обосновать метаматематическое утверждение «если арифметика непротиворечива, то она неполна». Но Гёделю удалось доказать и нечто большее, а именно, что само условное метаматематическое утверждение (именно все утверждение в целом) изображается в формализованной арифметике некоторой доказуемой формулой.

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

Ǝ y ∀ x ~ Dem(x, y). (А)

Формула эта, если выразить ее словесно, гласит: «существует по крайней мере одно натуральное число у, такое что для любого натурального x числа x и у не находятся между собой в отношении Dem». Если же интерпретировать формулу как метаматематическое высказывание, то мы получим: «существует по крайней мере одна арифметическая формула, для которой никакая последовательность формул не является ее доказательством». Таким образом, формула А как раз и представляет посылку метаматематического утверждения «Если арифметика непротиворечива, то она неполна». В то же время заключение утверждения «Она (т. е. арифметика) неполна» непосредственно вытекает из высказывания «имеется истинное арифметическое утверждение, не являющееся формально доказуемым в арифметике»; последнее же высказывание представляется в арифметическом исчислении посредством нашей старой знакомой – формулы G. Итак, условное метаматематическое высказывание «Если арифметика непротиворечива, то она неполна» представимо формулой

Ǝ у ∀ x ~ Dem(x, y) ﬤ ∀ x ~ Dem(x, sub(n, 13, n)),

которую можно было бы теперь сокращенно обозначить через «A ﬤ G». Именно для этой формулы можно установить ее формальную доказуемость, но мы не будем здесь пытаться это делать.

Покажем лишь, что формула А недоказуема. Допустим противное. Тогда, поскольку формула A ﬤ G доказуема, modus ponens позволяет нам заключить, что доказуемой должна бы быть и формула G. Но если наше исчисление непротиворечиво, G формально неразрешима, а потому, конечно, недоказуема. Таким образом, если арифметика непротиворечива, то формула А недоказуема.

Что это означает? Формула А представляет метаматематическое высказывание «Арифметика непротиворечива». Значит, если бы высказывание можно было обосновать каким нибудь рассуждением, отобразимым в последовательность формул, являющуюся доказательством в арифметическом исчислении, сама формула А была бы доказуема. Но это, как мы только что видели, невозможно, если во всяком случае считать, что арифметика непротиворечива. Мы дошли, наконец, до заключительного аккорда: нам приходится согласиться, что если арифметика непротиворечива, то непротиворечивость ее не может быть установлена никаким метаматематическим рассуждением, допускающим представление в арифметическом формализме

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

^{Положение здесь очень напоминает то, которое сложилось в геометрии в связи о доказательством невозможности деления произвольного угла на три части о помощью циркуля и линейки. Доказательство это отнюдь не исключает возможности произвести искомое деление при помощи каких-либо более сильных средств. И действительно, его можно осуществить, добавив к циркулю и линейке ещё постоянный эталон длины.}

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

Заключительные замечания

Выводы, к которым пришел Гёдель, имеют ряд важных следствий, безусловно, не оцененных еще в достаточной мере. Выводы эти показывают прежде всего, что решение задачи отыскания для каждой дедуктивной системы (и в частности, для системы, в которой можно было бы выразить всю совокупность арифметических теорем) абсолютного доказательства непротиворечивости, удовлетворяющего предложенным Гильбертом «финитистским» критериям, если и не является логически невозможным (хотя бы в силу некоторой неопределенности самого понятия «финитности»), то во всяком случае в высшей степени маловероятно. Выводы эти показывают также, что имеется бесконечно много истинных арифметических предложений, которые нельзя формально вывести из произвольной данной системы аксиом посредством некоторого точного перечня правил вывода. Отсюда следует, что аксиоматический подход к арифметике натуральных чисел, кроме всего прочего, не в состоянии охватить всю область истинных арифметических суждений. Отсюда также вытекает, что то, что мы понимаем под процессом математического доказательства, не сводится к использованию аксиоматического метода. Формализованные аксиоматические процедуры доказательств основаны на некотором множестве выделенных и фиксированных с самого начала аксиом и правил вывода. Как видно уже из самих рас– суждений, использованных в гёделевских доказательствах, изобретательность математиков в деле отыскания новых правил доказательства не поддается никаким априорным ограничениям. Таким образом, совершенно безнадежно рассчитывать на то, что понятию убедительного математического доказательства можно придать раз навсегда четко очерченные логические формы. В связи со всем этим возникает целый ряд новых проблем, далеко еще не решенных и слишком трудных для подробного рассмотрения их здесь – независимо от того, можно ли рассчитывать на то, что понятия математической и логической истинности можно исчерпывающим образом определить или же (мнение, к которому стал склоняться сам Гёдель) такое определение находится в компетенции безоговорочного философского «реализма» платонистского толка.

^{Платонизм (реализм) – доктрина, согласно которой математика не творит и не придумывает рассматриваемые в ней «объекты», а открывает их, подобно тому как, например, Колумб открыл Америку. Таким образом, согласно этой точке зрения, объекты должны в некотором смысле «существовать» до их «открытия». Платонистская доктрина не предполагает, что объекты математического исследования находятся между собой в пространственно-временных отношениях. Обьекты эти суть отделенные от материальных оболочек вечные Формы, прототипы, населяющие особые абстрактные Сферы, доступные лишь Интеллекту. Согласно такой концепции треугольные или круглые формы физических предметов, данные нам в ощущениях, сами по себе вовсе не являются объектами математического исследования. Эти пространственные формы суть лишь несовершенные воплощения единого «совершенного» Треугольника или «совершенного» Круга, вечных, неизменных, лишь частично проявляющихся в облике материальных предметов и являющихся подлинными объектами рассмотрения математической мысли. Сам Гёдель обнаружил близость к такого рода воззрениям, заявляя, «что допущение… классов и общих понятий столь же законно, как и допущение физических тел… и имеются столь же высокие основания верить в их существование» (из работы Гёделя «Russell's, Mathematical Logic» в книге The Philosophy of Bertrand Russei. Evanston; Chicago, 1944. C. 137). (Данная здесь авторами характеристика «платонизма» довольно-таки поверхностна, а традииионная квалификаиия Гёделя как платониста далеко не бесспорна. Впрочем, тема эта далеко выходит за рамки настоящей книги. См., например: Френкель А., Бар-Хиллел И. Основания теории множеств / Пер. с англ. М.: Мир, 1966. Гл. X. § 8; 3-е изд. М.: URSS, 2010. Прим. перев.)}

Заключения, к которым пришел Гёдель, порождают, естественно, и вопрос, можно ли построить вычислительную машину, сравнимую по своим «творческим» математическим возможностям с человеческим мозгом. Современные вычислительные машины обладают некоторым точно фиксированным запасом команд, которые умеют выполнять их элементы и блоки; команды соответствуют фиксированным правилам вывода некоторой формализованной аксиоматической процедуры. Таким образом, машина решает задачу, шаг за шагом выполняя одну из «встроенных» в нее заранее команд. Однако, как видно из гёделевской теоремы о неполноте, уже в элементарной арифметике натуральных чисел возникает бесчисленное множество проблем, выходящих за пределы возможностей любой конкретной аксиоматической системы, а значит, и недоступных для таких машин, сколь бы остроумными и сложными ни были их конструкции и с какой бы громадной скоростью ни проделывали они свои операции. Для каждой конкретной задачи в принципе можно построить машину, которой эта задача была бы под силу, но нельзя создать машину, пригодную для решения любой задачи. Правда, и возможности человеческого мозга могут оказаться ограниченными, так что и человек тогда сможет решить не любую задачу. Но даже если это так, структурные и функциональные возможности человеческого мозга пока еще намного больше по сравнению с возможностями самых изощренных из мыслимых пока машин, так что непосредственной опасности вытеснения людей роботами не видно[20]20
  При всем правдоподобии последней фразы она никак не следует из предыдущего. Вообще, далеко не ясно, как распространенный тезис об ограниченности возможностей моделирования человеческого мышления можно согласовать с материалистической гипотезой о его природе. Ср., впрочем, заключительные два абзаца авторского текста. – Прим. перев.


[Закрыть].

При всем сказанном теорему Гёделя отнюдь не следует расценивать как некое основание для интеллектуального пессимизма или оправдания мистических представлений о разуме. Обнаружение того факта, что для любой формальной системы существуют арифметические истины, которые нельзя в ней формально доказать, вовсе не означает наличия каких-то совершенно непознаваемых истин или же что роль строгого доказательства отныне должна занять некая «мистическая» интуиция, заслуживающая большего доверия, чем применяемые нами формы интеллектуального исследования. Не означает оно и утверждаемой некоторыми мыслителями «принципиальной ограниченности человеческого мышления». Означает оно лишь то, что возможности нашего мышления не сводятся к полностью формализуемым процедурам и что нам еще предстоит открывать и изобретать новые принципы доказательств. Мы ведь видели уже, что истинности некоторых математических утверждений, не выводимых из данного множества аксиом, можно тем не менее установить при помощи метаматематических рассуждений. И утверждать, что для обоснования таких формально недоказуемых (но устанавливаемых посредством метаматематических рассуждений) истин можно в лучшем случае рассчитывать лишь на интуицию, было бы совершенно безответственно.

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