В позапрошлом разделе мы собирались понять, каким способом Гедель доказал свою теорему о невозможности даже "слабого" (то есть - логического) доказательства непротиворечивости внутри непротиворечивой теории. И в этом разделе на более-менее популярном уровне я постараюсь изложить это доказательство. Кстати, даже сам Гёдель первоначально лишь обозначил доказательство в общих чертах. Но этого оказалось достаточно, чтобы похоронить надежды математиков на достижение абсолютной истины. Идеи были совершенно прозрачными, гениальными, а громоздкую техническую часть выполнили потом на благо всему научному сообществу Д. Гильберт и П. Бернайс в своем двухтомнике "Основания математики".
Итак, утверждение G обладает тем свойством, что оно эквивалентно собственной недоказуемости. Доказуемость утверждения Икс (существование доказательства для утверждения Икс) можно выразить при помощи определенной логической формулы. Обозначим эту формулу P(). Тогда эквивалентность между G и недоказуемостью G имеет следующий формальный вид:
G <=> ~P("G")
Кавычки в ~P("G") подчеркивают тот факт, что формула доказуемости имеет дело не с самими формулами, а с текстами формул. Приведенная эквивалентность имеет довольно простое формальное доказательство, которое можно найти, например, в книге Дж. Булоса и Р. Джеффри "Вычислимость и логика". Но для подготовки к доказательству, для "перевода" идей с "простого" языка на язык логического формализма мне потребовалось бы написать еще одну небольшую книгу. Впрочем, такие книги уже есть - та же "Вычислимость и логика". Однако и без формального доказательства приведенная эквивалентность достаточно очевидна.
Столь же очевидно, что в случае доказательства утверждения G получится противоречие.
Действительно, если будет доказано G, то будет доказано P("G") (наша теория может выражать свои доказательства). И будет еще доказано ~P("G") в силу 2 доказанных формул:
1. G <=> ~P("G")
2. G
(Раз G эквивалентно ~P("G") и G доказано, то доказано и эквивалентное ему ~P("G")).
В результате будут доказаны P("G") и ~P("G"), которые образуют противоречие.
Наша теория T, которая способна выражать свои доказательства, может понять (доказать), что из доказуемости утверждения G можно вывести доказуемость противоречивой формулы: (P("G") & ~P("G")). Но в формальной логике "можно вывести из Икс" означает, то же, что "следует из Икс". Я не углубляюсь в нюансы, при каких условиях такой переход (от "вывести" к "следует") возможен, потому что ознакомиться с ними можно в книгах по логике, прочитав теорему дедукции. Но формально, в теории T доказано:
P("G") => P("~P("G") & P("G")")
То есть, из одного абсурда следует другой абсурд.
В формальной логике будет истинна любая формула, в которой что угодно следует из противоречия. В частности:
(~P("G") & P("G")) => (0=1)
Еще раз воспользуемся тем, что наша теория по условию может выражать свои доказательства. Поэтому теория T в состоянии "понять", что из доказуемости противоречия следует доказуемость чего угодно:
P("~P("G") & P("G")") => P("0=1")
Выпишем теперь пару полученных формул:
P("G") => P("~P("G") & P("G")"); P("~P("G") & P("G")") => P("0=1")
Как видим, заключение 1й формулы здесь совпадает с посылкой 2ой формулы. Воспользуемся силлогизмом и получим:
P("G") => P("0=1")
Замечу, что подготовка к формальному доказательству приведенных здесь формул занимает более одного толстого тома в классическом труде "Основания математики" Гильберта и Бернайса. Но результат довольно прозрачный, поэтому нет нужды принуждать всех к чтению "Оснований математики".
Из последней формулы получим (применив контрапозицию):
~P("0=1") => ~P("G")
Или, говоря "человеческим" языком, если доказана недоказуемость какого-то абсурда (и не только абсурда), то недоказуема и формула Геделя.
Скажу и про контрапозицию. Если из Икс следует Игрек, то отсутствие Игрека (его отрицание) означает, что нет и Икса - ведь если бы Икс был, то был бы и Игрек. Поэтому, если у нас истинна формула X => Y, то истинна и формула ~Y => ~X.
Вернемся к нашей формуле:
~P("0=1") => ~P("G")
Сделанный вывод опять очевиден. Действительно:
Недоказуемость хоть чего-то в теории означает непротиворечивость теории. Об этом было сказано в разделе VII "Проблема доказательства своих границ" главы 2.1 "Что значит "знать"?": "если хоть одно утверждение не может быть доказано в теории, то теория непротиворечива"
А непротиворечивость теории означает отсутствие любых противоречий. В том числе и того противоречия, которое возникает в случае доказательства утверждения G. Вот и получается, что в непротиворечивой теории G недоказуемо.
Однако есть большое но. А именно, недоказуемость G эквивалентно самому G. А это значит, что если теория доказала хоть какую-то недоказуемость, то она доказала вместе с этим недоказуемость утверждения G, а вместе с недоказуемостью утверждения G она доказала и само утверждение G и пришла к противоречию.
Вот и получается, что непротиворечивая теория не может доказать недоказуемость (для себя) никакого утверждения. В частности, она не может доказать недоказуемость противоречия. А это значит, что непротиворечивая теория не может доказать свою непротиворечивость.
Сделанный в предыдущем абзаце вывод представляет собой 2ю теорему Геделя о неполноте.
Для большей полноты картины следует сказать о 1ой теореме Геделя о неполноте.
1ая теорема Геделя о неполноте утверждает, что для достаточно сложных теорий имеются такие утверждения, которые ни сами не доказаны, ни их отрицание не доказано. 1я теорема исторически предшествовала 2ой. Можно даже считать 2ю теорему частным случаем 1ой для утверждения непротиворечивости. Ведь в достаточно выразительной непротиворечивой теории непротиворечивость не доказана, и противоречивость (отрицание непротиворечивости) тоже не доказана. Так же, в достаточно выразительной теории недоказуемо вместе со своим отрицанием утверждение Геделя. Но в некоторых недостаточно выразительных теориях можно доказать отрицание утверждения Геделя, хотя такие теории и непротиворечивы. Ясно, что подобные теории недостаточно выразительны, потому что в них доказана ~G, значит, доказана доказуемость G, доказана P("G") (в силу эквивалентности G<=> ~P("G") есть - по принципу контрапозиции и эквивалентность ~G <=> P("G"), в которой из ~G следует P("G")), но не доказано само G. Однако даже для таких маловыразительных теорий можно доказать 1ю теорему Геделя (в отличие от 2ой). Исторически первым это сделал Россер, который рассмотрел вместо утверждения G утверждение R с таким смыслом:
"Если для утверждения R есть текст доказательства, то имеется и текст опровержения, который не длиннее текста доказательства".
Такое утверждение отличается от G тем, что поиск опровержения приходится вести лишь в ограниченном наборе текстов (все тексты, которые не длиннее текста доказательства R). Отрицание утверждения R будет означать доказуемость R в силу свойств логической конструкции "Если ... то", но к тому же будет означать (в силу свойств той же конструкции "Если ... то"), что текст доказательства R короче текста опровержения. Текст опровержения уже есть (раз доказано отрицание R), поэтому перебирать тексты в поисках доказательства R опять надо лишь в ограниченном наборе. Про ограниченные наборы текстов даже маловыразительные теории имеют правильное "представление" и поэтому не выдают неадекватных результатов. Формальное доказательство 1ой теоремы Геделя в форме Россера можно прочитать, например, в книге "Введение в математическую логику" Э. Мендельсона.
"Обычный" человек, прочитав данный раздел, вполне может сказать:
"Мы построили какое-то крайне хитрое доказательство, нагородили многоэтажную логическую конструкцию, из которой получили ошибку и заявляем, что из-за этой ошибки система не может доказать свою непротиворечивость (и ограниченность). Но "по жизни" мы вполне осознаем свои границы (чего тут доказывать?), а проблема, возникшая в результате нагромождения многоэтажных рассуждений вообще не актуальна, потому что в жизни мы каких-то искусственных и очень частных "формул Геделя" не городим и нужды в них никакой не имеем. И вообще: если нет доказательства теоремы Геделя, то нет противоречия, а нет противоречия - нет и ошибки"
Разобьем предыдущий абзац на четыре вопроса с целью их последующего рассмотрения:
1. Почему выявлять свою непротиворечивость система должна сложными методами? Ведь простые теории и простые системы избегают многих сложностей, которые и создают угрозу противоречий
2. Какое отношение выводы, сделанные о логических системах, применимы к нашим обычным рассуждениям? Может то, что невозможно для логической системы, легко достижимо нашими "обычными" рассуждениями?
3. Разве не сложные искусственные логические конструкции повинны в противоречиях? Какое отношение имеют проблемы, возникающие в очень специфических логических построениях, ко всем остальным теоремам? Пусть даже какое-то отдельное утверждение в данной теории приводит к противоречию (утверждение Геделя, например) - но разве это означает, что ошибки есть и в остальных теоремах данной теории, включая практически важные?
4. Мы отдаем себе отчет в том, что мы ограниченны в пространстве и времени. Как это соотноситься с тем, что теория своей ограниченности не чувствует (не может ее доказать)?
На эти вопросы мы ответим в главе 2.4 ""Окрестности" теоремы Геделя". Желающие могут сразу к ней перейти.
Замечу, что в основе поставленных вопросов лежит, во многом, идеология Запада:
Человек, якобы, может, в принципе, все проконтролировать, может "познать себя". Человек, якобы, может понять работу этих законов во всех важных для себя случаях и развернуть ситуацию к своей выгоде.
Мы, следуя Гёделю, сформулировали в этой главе ключевые математические возражения против Западной идеологии. Однако математические рассуждения слишком оторваны от жизни. Чтобы почувствовать "под ногами" более конкретную "почву", мы в нескольких следующих главах (до главы 2.4 ""Окрестности" теоремы Геделя", не включая её) рассмотрим процесс мышления, процесс принятия решений, совершения поступков и даже механизм чувств с физической точки зрения. И будем иметь еще одну возможность убедиться в несостоятельности Западного подхода.