Характеристика теорем Геделя

Размещено на http://www.allbest.ru/

Московский Авиационный Институт (национальный исследовательский университет)

Контрольная работа

по дисциплине «Теоретические основы»

На тему «Теоремы Геделя»

Москва - 2014

Содержание

Вступление

1. Биография Гёделя

2. Обобщённые формулировки

Прежде чем перейти к изложению теоремы, обессмертившей имя Гёделя, необходимо хотя бы вкратце рассказать о том, перед какими проблемами оказалась к концу 20-х годов прошлого века математика, точнее, ее раздел, выделившийся на рубеже XIX--ХХ вв. и получивший название «основания математики».

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

В конце XIX века все пробелы евклидовых «Начал» (с точки зрения возросших требований математиков к строгости и точности своих рассуждений) были заполнены. Итогом новейших исследований стала книга немецкого математика Давида Гильберта «Основания геометрии».

Успех методики Евклида побудил ученых распространить его принципы и на другие разделы математики. После геометрии настала очередь арифметики. В 1889 году итальянский математик Джузеппе Пеано впервые сформулировал аксиомы арифметики, казавшиеся до смешного очевидными (существует нуль; за каждым числом следует еще число и т. д.), но на самом деле абсолютно исчерпывающие. Они играли ту же роль, что и постулаты великого грека в геометрии. Исходя из подобных утверждений, с помощью логического рассуждения можно было получить основные арифметические теоремы.

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

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

Однако Расселу удалось вывести вариант формальной системы, позволяющий охватить всю математику и свободный от всех известных к тому времени парадоксов, с опорой именно на идеи и работы Фреге. Полученный им результат, опубликованный в 1902 году в книге Principia Mathematica (написанной совместно с Алфредом Нортом Уайтхедом), фактически стал аксиоматизацией логики, а Давид Гильберт считал, что его «можно рассматривать как венец всех усилий по аксиоматизации науки».

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

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

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

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

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

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

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

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

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

Однако «вселенская аксиоматизация» не состоялась. Вся суперамбициозная, грандиозная программа, над которой несколько десятилетий работали крупнейшие математики мира, была опровергнута одной-единственной теоремой. Ее автором был Курт Гёдель, которому к тому времени едва исполнилось 25 лет.

В 1930 году на конференции, организованной «Венским кружком» в Кенигсберге, он сделал доклад «О полноте логического исчисления», а в начале следующего года опубликовал статью «О принципиально неразрешимых положениях в системе Principia Mathematica и родственных ей системах». Центральным пунктом его работы были формулировка и доказательство теоремы, которая сыграла фундаментальную роль во всём дальнейшем развитии математики, и не только ее. Речь идет о знаменитой теореме Гёделя о неполноте. Наиболее распространенная, хотя и не вполне строгая ее формулировка утверждает, что «для любой непротиворечивой системы аксиом существует утверждение, которое в рамках принятой аксиоматической системы не может быть ни доказано, ни опровергнуто». Тем самым Гёдель дал отрицательный ответ на первое утверждение, сформулированное Гильбертом.

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

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

Теорема Гёделя

Формулировка первой теоремы.

В первоначальной форме

В своей формулировке теоремы о неполноте Гёдель использовал понятие щ-непротиворечивой формальной системы -- более сильное условие, чем просто непротиворечивость. Формальная система называетсящ-непротиворечивой, если для всякой формулы A(x) этой системы невозможно одновременно вывести формулы А(0), А(1), А(2), … и ?x ¬A(x) (другими словами, из того, что для каждого натурального числа nвыводима формула A(n), следует невыводимость формулы ?x ¬A(x)). Легко показать, что щ-непротиворечивость влечёт простую непротиворечивость (то есть, любая щ-непротиворечивая формальная система непротиворечива).

В процессе доказательства теоремы строится такая формула A арифметической формальной системы S, что:

Если формальная система S непротиворечива, то формула A невыводима в S; если система S щ-непротиворечива, то формула ¬A невыводима в S. Таким образом, если система S щ-непротиворечива, то она неполна и A служит примером неразрешимой формулы.

Формулу A иногда называют гёделевой неразрешимой формулой.

Интерпретация неразрешимой формулы

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

В форме Россера

В процессе доказательства теоремы строится такая формула B арифметической формальной системы S, что:

Если формальная система S непротиворечива, то в ней невыводимы обе формулы B и ¬B; иначе говоря, если система S непротиворечива, то она неполна, и B служит примером неразрешимой формулы.

Формулу B иногда называют россеровой неразрешимой формулой. Эта формула немного сложнее гёделевой.

Интерпретация неразрешимой формулы

В стандартной интерпретации формула B означает «если существует вывод формулы B, то существует вывод формулы ¬B». Согласно же теореме Гёделя в форме Россера, если формальная система S непротиворечива, то формула B в ней невыводима; поэтому, если система S непротиворечива, то формула B верна в стандартной интерпретации.

2. Обобщённые формулировки

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

Всякая достаточно сильная рекурсивно аксиоматизируемая непротиворечивая теория первого порядка неполна.

В частности, теорема Гёделя справедлива для каждого непротиворечивого конечно аксиоматизируемого расширения арифметической формальной системы S.

Формулировка второй теоремы

В формальной арифметике S можно построить такую формулу, которая в стандартной интерпретации является истинной в том и только в том случае, когда теория S непротиворечива. Для этой формулы справедливо утверждение второй теоремы Гёделя:

Если формальная арифметика S непротиворечива, то в ней невыводима формула, содержательно утверждающая непротиворечивость S.

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

Заключение и выводы

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

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

Что же касается фантасмагорического видения компьютеров, непрерывно доказывающих всё новые теоремы, то смысл подобной деятельности у многих специалистов вызывает большое сомнение. Ведь для математики важна не только формулировка доказанной теоремы, но и ее понимание, поскольку именно оно позволяет выявить связь между различными объектами и понять, в каком направлении можно двигаться дальше. Без такого понимания теоремы, генерируемые на основе правил формализованного вывода, представляют собой лишь своего рода «математический спам», -- таково мнение сотрудника кафедры математической логики и теории алгоритмов мехмата МГУ Александра Шеня.

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

Гёдель и Эйнштейн (фото: «В мире науки»)

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

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

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

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

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

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

Размещено на Allbest.ru