Интересные факты и полезные советы. Теоремы Гёделя о неполноте Суть теоремы к геделя в

А б с у р д н о с т ь рационализма
о т к р ы л а с ь м а т е м а т и к е -
той самой науке, на которой он пытался утвердиться.
В. Тростников

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

Создатель теории множеств Георг Кантор, а затем его последователи обнаружили ряд неразрешимых парадоксов множества порядковых чисел, указывающих на то, что сама конструкция такого множества внутренне противоречива и практически логически нереализуема. После установления внутренней противоречивости первого из возможных множеств математические парадоксы посыпались как из рога изобилия, приведя математиков к настоящей панике. Любопытна реакция другого великого математика Германа Вейля, разрешающая парадокс запретом: "...Нельзя допустить существование некоей определенной в себе и замкнутой совокупности всех возможных множеств натуральных чисел или всех возможных свойств натуральных чисел".

Э.Касснер, Д.Р.Ньюмен: "Когда математик говорит, что такие-то утверждения истинны для некоторого объекта, то это может быть интересно и наверняка безопасно. Но когда он пытается распространить свое утверждение на все объекты, то хотя это значительно более интересно, но и намного опаснее. В переходе от одного ко всему, от специального к общему математика добилась своих величайших успехов, но и испытала свои самые серьезные неудачи, самую важную часть которых составляют логические парадоксы".

Сегодня мы понимаем, что парадоксы теории множеств в частности и математики в целом связаны с тем, что множество не есть универсум, оно недостаточно для отражения всеобщего в знании, целостности знания как такового. Предельные конструкции, ведущие к единому или всеобщему, часто исключаются из математического анализа, ведя его к указанным парадоксам.

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

Неэвклидова геометрия Гаусса-Лобачевского–Больяи-Швейкарта и обнаружение антиномий в теории множеств сотрясло математику XIX века, поставив под сомнение ее основы. Подумайте, писал Давид Гильберт, в математике - этом образце достоверности и истинности - образование понятий и ход умозаключений приводит к нелепостям. Где же искать надежность и истинность, если даже само математическое мышление дает осечку?

И вот Давид Гильберт (1862-1943) выдвигает программу построения внутренне непротиворечивой математики, программу математического обоснования науки с целью изгнания из нее недостоверности. Из сформулированных Д.Гильбертом 23 знаменитых проблем математики первые два места занимают связанные между собой проблема континуума и проблема непротиворечивости аксиом арифметики. Последняя, по словам Гильберта, представляет собой обоснование правил арифметических действий совместно с аксиомой непрерывности: доказательство непротиворечивости аксиом арифметики вещественных чисел равносильно, по Гильберту, доказательству отсутствия противоречий в определении вещественного числа и континуума. Иными словами, Д.Гильберт ставил задачу наряду с доказательством непротиворечивости аксиом арифметики дать строгое обоснование понятия вещественного числа и, тем самым, определенное решение проблемы континуума: "В самом деле, если удастся полностью доказать непротиворечивость этих аксиом, то все соображения, которые подчас приводились против существования понятия вещественных чисел, теряют всякое основание".

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

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

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

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

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

В 1931 году Курт Гёдель опубликовал две теоремы о неполноте, смысл которых заключается в установлении принципиальной неосуществимости программы Д.Гильберта создать полную и непротиворечивую систему оснований математики. Хотя в этих теоремах ("Uber die unentscheidbaren Satze der formalen Systeme") речь идет об арифметике натуральных чисел, установленные им ограничения можно распространить на любую арифметику натуральных чисел.

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

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

Теорему Гёделя можно переформулировать следующим образом: «Все непротиворечивые аксиоматические формулировки теории чисел содержат неразрешимые суждения».

Это означает, что никакая достаточно большая система, вместе со своим алфавитом и своей грамматикой (или со своим конечным набором знаков и правилами их преобразования) НЕ ЯВЛЯЕТСЯ ПОЛНОЙ. «Логическая полнота (или неполнота) любой системы аксиом не может быть доказана в рамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы)». Несколько упрощая, можно сказать, что любая теория содержит проблемы, которые не могут быть решены в рамках самой теории и требуют ее обобщения.

Доказательство, данное Гёделем, не так просто. Однако, положенная в его основу идея довольно проста и восходит к «парадоксу лжеца», известному еще древним грекам. Гёдель перевел на язык математики утверждение, утверждавшее о самом себе, что оно недоказуемо в данной формальной системе. А если утверждение о недоказуемости доказуемо, то оно ложно…

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

Из теорем Гёделя следует, что никакое понятие истинным образом не раскрывается внутри области его существования или, по-иному, что само раскрытие предмета требует выхода за пределы осознанных смыслов, составляющих мир наших представлений: «Поэтому бессмысленно требовать изначальных доказательств сказанного, так как все они лежат по эту сторону привычного смыслового пространства». На обыденном языке суть аналитики Гёделя заключается в том, что мы никогда не сможем получить ВСЮ правду о мире, то есть человеческое познание внутренне ограничено, то есть какие-то аспекты мира всегда будут сопротивляться описанию.

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

Значение полученных Куртом Гёделем и затем Герхардом Генценом результатов, далеко выходит за пределы математики, свидетельствуя о том, что даже в царице наук возможна лишь относительная непротиворечивость, то есть абсолютное знание недостижимо.

Дуглас Хофштадтер в замечательной книге "Гёдель, Эшер, Бах" пошел еще дальше: теорема Гёделя имеет глубоко скрытую цель - раскрыть тайну слова "я": "Эта абстрактная структура, как мне казалось, и была ключом к загадке самопознания и возникновения "я". Также эта книга описывает, как человек может думать о себе, как он может себя познавать, а также способы представления и сохранения знаний, методы и ограничения символьного представления и даже фундаментальное понятие «значение».

После Гёделя Алан Туринг тоже выяснил, что многие математические предложения «нерешаемы», то есть в конечном счете нельзя определить, являются ли предложения истинными или ложными. Еще один ученый Трауб попытался перефразировать вопрос «Является ли реальный мир слишком сложным для нашего понимания?» в более позитивном свете: «Можем ли мы узнать то, что не можем знать?» Можем ли мы доказать, что у науки есть границы, точно так же, как К.Гёдель и А.Туринг доказали, что они есть у математики?

Философским и гносеологическим следствием великого открытия Гёделя является осознание неизбежной дилеммы, стоящей перед человеческим разумом в области оснований точных наук: либо тавтология (только тавтология!), либо (если система достаточно богата) - относительная непротиворечивость. На бытовом языке жизни выражение «ты не прав» может свидетельствовать лишь об ограниченности говорящего. Без элементов свободного допущения никакая достаточно богатая теория невозможна, так что любые утверждения науки всегда содержат в себе элемент относительности, непредсказуемости и неопределенности.

По словам П.Коэна, теорема Гёделя является величайшим, непреодолимым препятствием для любой попытки понять природу множественного и целого. Что до проблемы континуума и математических множеств, то теоремы Гёделя сделали проблему бесконечных множеств, с одной стороны, окончательно неразрешимой и, с другой, принципиально неотвергаемой: «Теорема Гёделя чрезвычайно затрудняет отстаивание той точки зрения, что высшие бесконечности можно попросту отвергнуть».

Несколько ранее в исследованиях Лёвенгейма и Скулема 1915-1920 годов (теорема Лёвенгейма-Скулема) обнаружен еще один обескураживающий факт: никакая аксиоматическая система не может быть категорична. Иными словами, при любой тщательности формулировки система аксиом, всегда найдётся интерпретация, совершенно не похожая на ту, ради которой эта система проектировалась. Это обстоятельство также подрывает веру в универсальность аксиоматического подхода.

Я не случайно заговорил об аксиоматике и математических множествах, потому что одной из главных проблем оснований математики является преодоление пропасти между дискретным и непрерывным, арифметикой и геометрией. Собственно, теория множеств возникла как способ описания континуума, однако детальное обследование проблемы континуум-множество (Г.Кантор, И.Кёниг, Д.Гильберт, К.Гёдель, П.Коэн, Э.Цермело, Т.Скулем, Н.Н.Лузин) выявило невозможность представления континуума любым, сколь угодно мощным множеством, что подвигло Г.Вейля на мысль, что континуум вообще не является множеством точек: континуум - среда свободного становления, которую невозможно исчерпать никакими множествами любых чисел.

Обнаруженный факт невозможности исчерпывающего и однозначного описания континуума как множества ведет к признанию в нем свойств нетривиальной целостности, которую следует понимать как отрицание и исключение всякой множественности. Эта целостность и единство в континууме есть свойства более сильные, чем обычная непрерывность множеств, они лежат как бы в ее основе.

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

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

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

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

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

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

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

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

Кстати, Гёдель, как свидетельствуют его записные книжки, всю жизнь размышлял не только о математике, но о природе и пределах самого мышления, а также о проблеме существования абсолютно неразрешимых утверждений. Внутренне тяготея к парадоксам, он часто повторял: «Либо наш разум не является механическим, либо математика, даже арифметика, не является нашей собственной конструкцией». Позже эта «закрученная формулировка» стала предметом обширной полемики о соотношении ума и компьютера, особенно в связи с интерпретацией теорем о неполноте Геделя гениальным физиком Р.Пенроузом.

Гёдель считал, что философия математики должна стать частью самой математики, приобретая определенность, и в то же время теряя характер собственно философский.

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

Сам Гёдель часто говорил о «незавершаемости или неисчерпаемости математики» и, возможно, впервые поставил вопрос, может ли этот процесс незавершаемости математики осуществляться конечной машиной или же только человеком. Если это доступно только человеку, тогда он действительно превосходит по своим возможностям конечную машину.

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

В итоге эссенциализм не только стимулировал пустые словопрения, но и привел к разочарованию в возможностях аргументации, а значит, и в возможностях разума.
Возможности аристотелевской логики ограничены, возможности человеческого разума безграничны. Даже сама логика не осталась неизменной: следуя за «неклассической» физикой, логика обогатилась рядом релятивистских, релевантных, вероятностных, паранепротиворечивых логик, трех- и четырехзначных логик, логик с не всюду определенным понятием истинности, с пересыщенными оценками и т. д., и т. п., что существенно изменило облик современной математики.

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

Не выдержала испытания и концепция математики и физики как «знания без познающего субъекта», верного всегда и во всех мирах.

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

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

Дискуссии о научной рациональности и успешности науки как возможности выбора метода, адекватно поставленной цели, зашли в тупик. Многое по-прежнему неясно.

Каковы критерии научной рациональности? Какие познавательные стандарты оценивать как «универсалии», а какие имеют исторически ограниченную область действия (например, ориентация на выдвижение фальсифицируемых теорий, избегание модификаций ad hoc, постулирующих ненаблюдаемые сущности; предпочтение предсказательных теорий теориям, обладающим красотой и изяществом, простотой; предпочтение количественных или качественных процедур анализа и т. п.)?

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

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

П.Фейерабенд считает, что попперовская схема развития не универсальна, иллюстрируя свою точку зрения следующими доводами:
1. Замена теории не всегда происходит как фальсификация. Так, в случае с системой Птолемея, или с электронной теорией Лоренца нельзя привести таких фактов, которые стимулировали отказ от этих систем.
2. Содержание теории, которую мы хотим проверить, и наше решение относительно фальсифицирующих примеров не столь независимы друг от друга, как это подразумевается в теории Поппера.
3. Переход от одной системы знания не всегда приводит к содержательному росту, как, например, переход к научной психологии, приведший к существенному сужению содержания.
4. Требование поиска опровергающих обстоятельств и серьезного к ним отношения может привести к устойчивому прогрессу тогда, когда опровергающие факты единичны и редки. Если же теория окружена «океаном аномалий», то правила фальсификации могут быть использованы только как временные, а отнюдь не необходимые условия научной рациональности.

П.Фейерабенд полагает, что рациональные схемы развития науки вообще неадекватны ее сущности и противоречат истории развития знания:

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

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

Что до научного консерватизма, то он свойствен даже выдающимся творцам науки: Д.И.Менделеев отказывался слушать доводы в пользу возможной трансформации элементов, Ч.Дарвин с присущей ему непоследовательностью, граничащей с беспринципностью, впадал в ламаркизм, Эйнштейн до конца жизни отказывал в правоте Бору и Гейзенбергу...

Упомянув имена Дарвина и Ламарка, я должен напомнить теории развития науки, принадлежащие Чарльзу Сандерсу Пирсу, считавшему, что эволюция знания может идти тремя путями:
- путем дарвиновской эволюции - медленными, случайными и незаметными изменениями в процессе борьбы за существование;
- путем ламаркистской эволюции - медленными, но закономерными изменениями в результате собственных устремлений индивидов;
- путем катаклизмов Кювье - внезапных скачков, связанных с резкими изменениями окружающей среды.

Чарльз Сандерс Пирс полагал, что как в эволюции жизни, так и в эволюции знания возможны все три типа эволюции, но среди них преобладает ламаркистский тип эволюции:

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

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

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

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

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

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

Возвращаясь к Курту Гёделю, я должен отметить, что его рационалистический оптимизм не исключал ни фактора человеческой субъективности, ни интитивности, ни априорности знания, ни даже элемента мистицизма. Весьма характерно признание математика и писателя Р.Рукера: «Я спросил Гёделя, верит ли он, что за всеми различными явлениями и действиями в мире стоит единый Ум. Он ответил утвердительно, и что Ум структурирован, но при этом Ум существует независимо от индивидуальных свойств. Тогда я спросил, верит ли он, что Ум находится везде, в противоположность тому, что локализуется в мозгах людей. Гёдель ответил: “Конечно. Это основа мистического учения”». Видный логик Раймонд Смаллиан, много делающий для популяризации математических достижений Гёделя, рассказал, что в одной из бесед с ним Гёдель произнес замечательную фразу «когда время созреет». В этом духе можно предположить, что Гёдель мог рассчитывать как рационалистический оптимист на то, что «однажды, но никак не ранее, время придет», когда не будет опасений перед абсолютно неразрешимыми проблемами.

Несколько слов о Гёделе-человке. Курт Гёдель родился в 1906 г. в Австро-Венгрии, в городе Брюнн (ныне Брно в Чехии). По завершению Венского университета и защиты диссертации остался там преподавателем. После аннексии Австрии он автоматически получил паспорт гражданина Германии, но, испытывая лютую ненависть к нацистам, бежал в США, получив предварительно приглашение занять пост в Принстонском институте перспективных исследований, где ранее обустроился А.Эйнштейн.

Несмотря на 27-летнюю разницу в возрасте и несовместимость темпераментов, Курт быстро сблизился с Эйнштейном. Каждый день их видели идущими вместе в Институт и обратно, увлеченными разговором, причем говорил в основном Гёдель. Известный математик Арман Борель вспоминал: «Я не знаю, о чем они разговаривали; наверное, о физике, ведь Гёдель в молодости занимался физикой. Больше они ни с кем не общались, разговаривали только друг с другом». А экономист Оскар Моргенштерн позже пересказал слова Эйнштейна: «Моя работа теперь не имеет никакого значения. Я хожу в Институт только для того, чтобы иметь удовольствие возвращаться домой вместе с Гёделем».

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

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

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

Из книги И.Гарина "Что такое наука?" Примечания и цитирования даны в тексте книги.

на тему: «ТЕОРЕМА ГЁДЕЛЯ»

Курт Гёдель

Курт Гёдель – крупнейший специалист по математической логике – родился 28 апреля 1906 г. В Брюнне (ныне г. Брно, Чехия). Окончил Венский университет, где защитил докторскую диссертацию, был доцентом в 1933–1938 гг. После аншлюса эмигрировал в США. С 1940 по 1963 г. Гёдель работал в Принстонском институте высших исследований. Гёдель – почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества.

В 1951 г. Курт Гёдель был удостоен высшей научной награды США – Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал : «Вклад Курта Гёделя в современную логику поистине монументален. Это – больше, чем просто монумент. Это веха, разделяющая две эпохи… Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки».

Действительно, даже сухой перечень достижений Гёделя в математической логике показывает, что их автор по существу заложил основы целых разделов этой науки: теории моделей (1930 г.; так называемая теорема о полноте узкого исчисления предикатов, показывающая, грубо говоря, достаточность средств «формальной логики» для доказательства всех выражаемых на ее языке истинных предложений), конструктивной логики (1932–1933 гг.; результаты о возможности сведения некоторых классов предложений классической логики к их интуиционистским аналогам, положившие начало систематическому употреблению «погружающих операций», позволяющих осуществлять такое сведение различных логических систем друг другу), формальной арифметики (1932–1933 гг.; результаты о возможности сведения классической арифметики в интуиционистскую, показывающие в некотором смысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивных функций (1934 г.; определение понятия общерекурсивной функции, сыгравшего решающую роль в установлении алгоритмической неразрешимости ряда важнейших проблем математики, с одной стороны. И в реализации логико-математических задач на электронно-вычислительных машинах – с другой), аксиоматической теории множеств (1938 г.; доказательство относительной непротиворечивости аксиомы выбора и континуум-гипотезы Кантора от аксиом теории множеств, положившее начало серии важнейших результатов об относительной непротиворечивости и независимости теоретико-множественных принципов).

Теорема Гёделя о неполноте

Введение

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

Однако в момент опубликования ни название гёделевской работы. Ни содержание ее ничего не говорили большинству математиков. Упомянутые в ее названии Principia Mathematica – это монументальных трехтомный трактат Альфреда Норта Уайтхеда и Бертрана Рассела, посвященный математической логике и основаниям математики; знакомство с трактатом отнюдь не являлось необходимым условием для успешной работы в большей части разделов математики. Интерес к разбираемым в работе Гёделя вопросам всегда был уделом весьма немногочисленной группы учёных. В то же время рассуждения, приведенные Гёделем в его доказательствах, были для своего времени столь необычными. Что для полного их понимания требовалось исключительное владение предметом и знакомство с литературой, посвященной этим весьма специфическим проблемам.

Первая теорема о неполноте

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

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

Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказатьпротиворечивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.

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

Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I . В оригинальной записи Гёделя она звучала как:

«Общий вывод о существовании неразрешимых пропозиций заключается в следующем:

Теорема VI .

Для каждого ω-согласованного рекурсивного класса k ФОРМУЛ существуют рекурсивные ЗНАКИ r такие, что ни (v Genr ), ни ¬(v Genr )не принадлежат Flg (k )(где v есть СВОБОДНАЯ ПЕРЕМЕННАЯ r ) ».

Обозначение Flg происходит от нем. Folgerungsmenge – множество последовательностей, Gen происходит от нем. Generalisation – обобщение.

Грубо говоря, высказывание Гёделя G утверждает: «истинность G не может быть доказана». Если бы G можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если G недоказуемо, то оно истинно, а потому теория неполна (высказывание G невыводимо в ней).

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

Вторая теорема Гёделя о неполноте

Вторая теорема Гёделя о неполноте звучит следующим образом:

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

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

Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми – однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».

Дискуссии

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

Признаюсь, что саму идею рассмотрения вопроса о существовании бога с этой стороны я вычитал у Анатолия Александровича Вассермана:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92%D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8.D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0.B4.D1.8B

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

Рассмотрим с этих позиций религиозные верования. Важнейшая аксиома религии: "бог существует и является первопричиной всего сущего".
Теперь вспомним одну из важнейших математических теорем, теорему Гёделя.
http://elementy.ru/trefil/21142
Слабая теорема Гёделя: "Любая формальная система аксиом содержит неразрешенные предположения" или "если система аксиом полна, то она противоречива."
Сильная теорема Гёделя: "Логическая полнота (или неполнота) любой системы аксиом не может быть доказана в рамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы)."

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

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

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

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

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

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

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

Что же получается в итоге... любой хоть сколько-нибудь рациональный человек, конечно, признает справедливость законов логики, а значит неизменно приходит к выводу, что бог в определении "причина всего сущего" не существует. Человек не рациональный, который утверждает, что бога можно познать только с помощью чувств (а не разума), конечно, может так утверждать, однако нету никакого способа убедить в этом другого, чувства не возможно передать. Более того понятие бога является понятием сформулированным разумом. Каким образом предлагается транслировать понятие разума в ощущение, да еще так, чтобы это можно было передать другому человеку - не ясно. Опять же хоть сколько-нибудь рациональный человек скажет, что это не возможно: абстрактное понятие разума перевести в чувство и ощутить его.

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

P.S. Стоит отметить еще одну любопытнейшую вещь, любопытную уже для физиков. В данном определении бога ничего не говорится о его разумности. То есть можно было бы добавить "бог - разумная причина всего сущего", однако это сужение определения, которое изначально и не требуется для доказательства. Без разумности понятие "бога" можно легко заменить на "сингулярность и большой взрыв - причина всего сущего". И ответ будет тот же самый: сингулярность и большой взрыв - не первопричина всего сущего.
Проведя еще большее абстрагирование можно сказать, что ни одно явление или причина не могут являться первопричиной всего сущего, то есть первопричины не существует в принципе. Рассуждая в рамках любой аксиоматики можно прийти к выводу, что первопричины всего не существует. Говоря совсем просто, до каких бы основ мы ни познали вселенную, всегда останутся вопросы в духе: "откуда появился большой взрыв, откуда появилась сингулярность, откуда появилась пульсирующая вселенная, откуда появилась мультивселенная, почему вселенная существует всегда?" и т.п. Первопричину всего не возможно найти в принципе, она не содержится ни в одном объекте, явлении или понятии. Следовательно для человека это эквивалентно ее отсутствию. Теоретически можно предположить существование стороннего наблюдателя за пределами нашей вселенной, который даст ответ на вопрос, откуда все взялось (та самая дополнительная аксиома, расширение в теореме Гёделя), однако тогда возникнет вопрос, откуда взялся сторонний наблюдатель, его вселенная и первопричина всего этого.

Экология жизни. Наука и открытия: Теореме Гёделя о неполноте, одной из самых известных теорем математической логики, повезло и не повезло одновременно. В этом она похожа на специальную теорию относительности Эйнштейна. С одной стороны, почти все о них что-то слышали. С другой интерпретации теория Эйнштейна «говорит, что всё в мире относительно».

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

С одной стороны, почти все о них что-то слышали. С другой - в народной интерпретации теория Эйнштейна , как известно, «говорит, что всё в мире относительно ». А теорема Гёделя о неполноте (далее просто ТГН), в примерно столь же вольной фолк-формулировке, «доказывает, что есть вещи, непостижимые для человеческого разума ».

И вот одни пытаются приспособить её в качестве аргумента против мат ериализма , а другие, напротив, доказывают с её помощью, что бога нет. Забавно не только то, что обе стороны не могут оказаться правыми одновременно, но и то, что ни те, ни другие не удосуживаются разобраться, что же, собственно, эта теорема утверждает.

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

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

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

Начнём с того, что попытаемся разобраться, что такое доказательство. Возьмём какую-нибудь школьную задачку по арифметике. Например, пусть требуется доказать верность следующей незамысловатой формулы: «∀x(x−1)(x−2)−2=x(x−3)» (напомню, что символ ∀ читается «для любого» и называется «квантор всеобщности»). Доказать её можно, тождественно преобразуя, скажем, так:

∀x(x−1)(x−2)−2=x(x−3)

∀xx2−3x+2−2=x2−3x

∀xx2−3x–x2+3x=0

∀x0=0

ИСТИНА

Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе - такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ - если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество S так называемых высказываний - то есть грамматически осмысленных фраз, каждая из которых истинна или ложна . Можно сказать, что существует функция P, сопоставляющая высказываниям из S одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество B из двух элементов).

Назовём такую пару - множество высказываний S и функция P из >S в B - «языком высказываний» . Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда! » не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

Для дальнейшего нам понадобится понятие алгоритма. Приводить здесь формальное его определение я не буду - это завело бы нас довольно далеко в сторону. Ограничусь неформальным: «алгоритм» - эта последовательность однозначных инструкций («программа»), которая за конечное число шагов переводит исходные данные в результат.

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

Спросим себя: для всякой ли функции P существует «доказывающий алгоритм» (или, короче, «дедуктика »), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима?

Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая - существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

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

Но, если вдуматься, это совершенно не очевидно. Некоторые теоремы доказываются довольно просто (например, перебором небольшого числа вариантов), а некоторые - очень сложно. Вспомним, например, знаменитую Великую теорему Ферма :

Не существует таких натуральных x,y,z и n>2, что xn+yn=zn,

доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.

Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно.

Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее - после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание . Примете его в качестве ещё аксиомы - наткнётесь на третье. И так до бесконечности.

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

В таких случаях говорят, что дедуктика противоречива. Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика » - отсюда и название теоремы.

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

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

Курт Гедель

Любому школьнику известно, что, скажем, в случае функции sin⁡x вам должно сильно повезти с аргументом, чтобы процесс вычисления точного десятичного представления значения этой функции окончился за конечное число шагов.

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

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

Понятно, что не все такие строки осмысленны (например, «12=+∀x>» - это бессмыслица). Подмножество осмысленных выражений из этого класса (то есть строк, которые истинны или ложны с точки зрения обычной арифметики) и будет нашим множеством высказываний.

Примеры высказываний формальной арифметики:

1=1

2×2=5

∃xx>3

∀y∀zy×z>y+ z

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром x):

x=0

2×2=x

∃yx+y>x

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

Обозначим множество всех ФСП буквой F. Понятно, что его можно упорядочить (например, сначала выпишем упорядоченные по алфавиту однобуквенные формулы, за ними - двухбуквенные и т.д.; по какому именно алфавиту будет происходить упорядочивание, нам непринципиально). Таким образом, любой ФСП соответствует её номер k в упорядоченном списке, и мы будем обозначать её Fk.

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.

Доказывать будем от противного.

Итак, допустим, что такая дедуктика существует. Опишем следующий вспомогательный алгоритм A, ставящий в соответствие натуральному числу k булево значение следующим образом :

1. Находим k-ю формулу в списке F.

2. Подставляем в неё число k в качестве аргумента.

3. Применяем к полученному высказыванию наш доказывающий алгоритм (по нашему предположению, он существует), который переводит его в ИСТИНУ или ЛОЖЬ.

4. Применяем логическое отрицание к полученному результату.

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

Очевидно, что, при сделанном выше предположении, любой ФСП из F можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение.

Менее очевидно обратное утверждение:

Лемма: Любому алгоритму, переводящему натуральное число в булево значение, соответствует какая-то ФСП из множества F.

Доказательство этой леммы потребовало бы, как минимум, формального, а не интуитивного, определения понятия алгоритма. Однако, если немного подумать, то она довольно правдоподобна.

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

Пройдя это скользкое место, мы быстро добираемся до конца.

Итак, выше мы описали алгоритм A. Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке F - скажем, n. Спросим себя, чему равно Fn(n)? Пусть это ИСТИНА. Тогда, по построению алгоритма A (а значит, и эквивалентной ему функции Fn), это означает, что результат подстановки числа n в функцию Fn - ЛОЖЬ.

Аналогично проверяется и обратное: из Fn(n)=ЛОЖЬ следует Fn(n)=ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

Здесь уместно вспомнить Эпименида, который, как известно, заявил, что все критяне - лжецы, сам являясь критянином. В более лаконичной формулировке его высказывание (известное как «парадокс лжеца») можно сформулировать так: «Я лгу ». Именно такое высказывание, само превозглашающее свою ложность, мы и использовали для доказательства.

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

Приведённый набросок доказательства относился к формальной арифметике, но нетрудно понять, что ТГН применима и к многим другим языкам высказываний. Разумеется, не всякие языки таковы. Например, определим язык следующим образом:

«Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».

Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:

«Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».

Здесь нас спасает то, что любой цитатник, очевидно, конечен, поэтому процесс «доказывания» неминуемо закончится. Таким образом, к языку догматических высказываний ТГН неприменима. Но мы ведь говорили о сложных языках, правда? опубликовано

Теорема Геделя о неполноте

Успенский В.А.

Пожалуй, теорема Геделя о неполноте является воистину уникальной. Уникальной в том, что на нее ссылаются, когда хотят доказать "все на свете" - от наличия богов до отсутствия разума. Меня всегда интересовал более "первичный вопрос" - а кто из ссылающихся на теорему о неполноте смог-бы не только сформулировать ее, но и доказать? Я публикую данную статью по той причине, что в ней изложена вполне доступная формулировка теоремы Геделя. Рекомендую предварительно ознакомиться со статьей Туллио Редже Курт Гедель и его знаменитая теорема

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

Карл Поппер

Успенский Влaдимиp Aндpеевич pодился 27 ноябpя 1930 г. в г. Москве. Окончил мехaнико-мaтемaтический фaкультет МГУ (1952). Доктоp физико-мaтемaтических нaук (1964). Пpофессоp, заведующий кaфедpой мaтемaтической логики и теоpии aлгоpитмов мехaнико-мaтемaтического фaкультетa (1966). Читает курсы лекций "Введение в математическую логику", "Вычислимые функции", "Теорема Геделя о полноте". Подготовил 25 кандидатов и 2 докторов наук

1. Постановка задачи

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

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

1.1. Язык

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

1.1.1. Алфавит

Под алфавитом мы понимаем конечный набор элементарных знаков (то есть - вещей, которые невозможно разбить на составные части). Эти знаки называются буквами алфавита. Под словом алфавита мы понимаем конечную последовательность букв. Например, обыкновенные слова в английском языке (включая имена собственные) являются словами 54-хбуквенного алфавита (26 маленьких букв, 26 прописных, тире и апостроф). Другой пример - натуральные числа в десятичной записи являются словами 10-тибуквенного алфавита, чьи буквы - знаки: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для обозначения алфавитов мы будем использовать обыкновенные заглавные буквы. Если L - алфавит, то L? будет обозначать множество всех слов алфавита L, - слов, образованных из его букв. Мы предположим, что любой язык имеет свой алфавит, так что все выражения этого языка (т. е. - имена различных объектов, утверждения относительно этих объектов и т.д.) являются словами этого алфавита. Например, любое предложение английского языка, равно как и любой текст, написанный по-английски, может рассматриваться как слово расширенного алфавита из 54-х букв, включающего также знаки пунктуации, междусловный пробел, знак красной строки и, возможно, некоторые другие полезные знаки. Предполагая, что выражения языка являются словами некоторого алфавита, мы, таким образом, исключаем из рассмотрения "многослойные" выражения типа???f(x)dx. Однако, это ограничение не слишком существенно, так как любое подобное выражение, при использовании подходящих конвенций, может быть "растянуто" в линейную форму. Любое множество М, содержащееся в L? называется словным множеством алфавита L. Если мы просто говорим, что М - словное множество, то мы подразумеваем, что оно является словом некоторого алфавита. Теперь сформулированное выше предположение о языке может быть перефразировано следующим образом: в любом языке любое множество выражений является словным множеством.

1.1.2. Множество истинных утверждений

Мы предположим, что нам задано подмножество Т множества L? (где L алфавит некоторого рассматриваемого нами языка), которое называется множеством "истинных утверждений" (или просто "истин"). Переходя непосредственно к подмножеству Т, мы опускаем следующие промежуточные шаги рассуждения: во-первых, какие именно слова алфавита L являются корректно образованными выражениями языка, то есть - имеющими определенное значение в нашей интерпретации этого языка (например, 2+3, х+3, х=у, х=3, 2=3, 2=2 являются корректно образованными выражениями, в то время как выражения типа +=х таковыми не являются); во-вторых, какие именно выражения являются формулами, т.е. могут зависеть от параметра (например, х=3, х=у, 2=3, 2=2); в третьих, какие именно из формул являются закрытыми формулами, т.е. утверждениями, не зависящими параметров (например, 2=3, 2=2); и наконец, какие именно закрытые формулы являются истинными утверждениями (например, 2=2).

1.1.3. Фундаментальная пара языка

1.2. "Недоказуемые"

"Недоказуемые" значит не имеющие доказательства.

1.3. Доказательство

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

Будучи записано, доказательство становится словом в некотором алфавите Р, так же как любой английский текст является словом алфавита L, пример которого был приведен выше. Множество всех доказательств образуют подмножество (и довольно-таки обширное подмножество) множества Р?. Мы не будем пытаться дать точное определение этой одновременно "наивной" и "абсолютной" концепции доказательства, или - что равносильно - дать определение соответствующему подмножеству Р?. Вместо этого мы рассмотрим формальный аналог этого смутного понятия, для обозначения которого в дальнейшем мы все же будем пользоваться термином "доказательство". Этот аналог имеет две весьма важные особенности, кои отличают его от интуитивного понятия (хотя интуитивная идея доказательства все же отражает в некоторой степени эти особенности). Прежде всего мы допустим, что существуют разные концепции доказательства, то есть - допустимы разные подмножества доказательств в Р?, и даже больше того: мы, на деле, будем допускать, что сам алфавит доказательств Р может изменяться. Далее мы потребуем, чтобы для каждой такой концепции доказательства существовал эффективный метод, другими словами, алгоритм, который бы с необходимостью определял, является ли данное слово алфавита Р доказательством или нет. Мы также предположим, что существует алгоритм, с помощью которого всегда можно определить, какое именно утверждение доказывает данное доказательство. (Во многих ситуациях доказываемым утверждением просто является последнее утверждение в последовательности шагов, образующих доказательство.)

Таким образом, наша окончательная формулировка определения выглядит следующим образом:

(1) У нас имеются алфавит L (алфавит языка) и алфавит Р (алфавит доказательства).

(2) Нам дано множество Р, являющееся подмножеством Р?, и чьи элементы называются "доказательствами". В дальнейшем мы будем предполагать, что также у нас имеется алгоритм, который позволяет нам определить является ли произвольное слово алфавита Р элементом множества Р, то есть доказательством, или нет.

(3) Также у нас есть функция? (для нахождения того, что именно было доказано), чья область определения? удовлетворяет условию Р???Р?, и чья область значений находится в Р?. Мы предполагаем, что у нас есть алгоритм, который вычисляет эту функцию (точное значение слов "алгоритм вычисляет функцию" следующее: значения функции получаются при помощи этого алгоритма - набора специальных правил преобразования). Мы будем говорить, что элемент р? Р есть доказательство слова?(р) алфавита L.

Тройка <Р, Р, ?>, удовлетворяющая условиям (1)-(3) называется дедуктивной системой над алфавитом L.

Для читателя, знакомого с обычным способом определения "доказательства" в терминах "аксиома" и "правило вывода", мы сейчас поясним, как этот метод может рассматриваться в качестве специального случая определения, данного в параграфе 1.3.2. То есть - доказательство обычно определяется как последовательность таких выражений языка, каждое из которых является либо аксиомой, либо ранее полученным из уже существующих утверждений при помощи одного из правил вывода. Если мы добавим новое слово * к алфавиту нашего языка, то мы сможем записать такое доказательство в виде слова составленного при помощи полученного в результате такой модификации алфавита: последовательность выражений становится словом C1*C2*...*Cn. В таком случае, функция, определяющая, что именно было доказано, своим значением имеет часть этого слова, стоящую сразу за последней в последовательности буквой *. Алгоритм, существование которого требуется в части 1.3.2. определения, может легко быть сконструирован, как только мы точно определим какое-либо из принятых значений слов "аксиома" и "правила вывода".

1.4.Попытки точной формулировки теоремы о неполноте

1.4.1. Первая попытка

"При определенных условиях для фундаментальной пары языка алфавита L и дедуктивной системы <Р, Р, ?> над L - всегда существует слово в Т, не имеющее доказательства". Этот вариант все еще выглядит смутным. В частности, мы могли бы запросто придумать сколько угодно дедуктивных систем, имеющих очень немного доказуемых слов. Например, в пустой дедуктивной системе (где Р = ?) совсем нет слов, у которых были бы доказательства.

1.4.2. Вторая попытка

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

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

Однако такое утверждение, очевидно, ложно, так как необходимо лишь взять такую дедуктивную систему, в которой Р = L, Р = Р? и?(р) = р для всех р из Р?; тогда каждое слово из L? является тривиально доказуемым. Следовательно, нам нужно принять некоторое ограничение на то, какими дедуктивными системами мы пользуемся.

1.5. Непротиворечивость

Было бы вполне естественно потребовать, что только "истинные утверждения", то есть только слова из Т, могут быть доказаны. Мы будем говорить, что дедуктивная система <Р, Р, ?> является непротиворечивой относительно фундаментальной пары, если?(Р)?Т. Во всех последующих рассуждениях нас будут интересовать только такие непротиворечивые дедуктивные системы. Если же нам задан язык, то было бы чрезвычайно соблазнительно найти такую непротиворечивую дедуктивную систему, в которой каждое истинное утверждение имело бы доказательство. Интересующий нас вариант теоремы Геделя в точности утверждает, что при определенных условиях относительно фундаментальной пары, невозможно найти такую дедуктивную систему.

1.6. Полнота

Говорится, что дедуктивная система <Р,Р,?> полна относительно фундаментальной пары, при условии если?(Р)?Т. Тогда наша формулировка теоремы о неполноте приобретает следующий вид:

При определенных условиях относительно фундаментальной пары, не существует такой дедуктивной системы <Р,Р,?> над L, которая была бы одновременно полна и непротиворечива относительно.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://filosof.historic.ru