Московский государственный университет icon

Московский государственный университет



НазваниеМосковский государственный университет
Дата конвертации14.09.2012
Размер254.75 Kb.
ТипРеферат

Московский государственный университет


имени М.В. Ломоносова


Факультет журналистики


Курт Гедель. Теорема Геделя о неполноте


Реферат по философии

студентки II курса 201 группы

Филатовой И.М.

Преподаватель: Радул Д.Н.





Москва 2005


Курт Гедель родился в 28 апреля 1906 года в чехословацком городе Брно. Его отец, австриец Рудольф Гедель, был владельцем крупнейшей текстильной фабрики в Брно. Мать Курта Марианна Хандшу училась во Франции и получила гуманитарное образование. Гедель был очень привязан к матери, у него было счастливое детство.

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

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

Окончив школу в 1923 году, Гедель поступил в Венский университет. Однако к тому времени он так и не решил, в какой области будет специализироваться, – в математике или теоретической физике. В университете он слушал лекции таких выдающихся профессоров математики, как Филипп Фуртвенглер, Ханс Хан, Вильгельм Виртингер, Карл Менгер и других. Особое влияние на юного Геделя оказали лекции Фуртвенглера, и он выбрал математику в качестве специализации. Тому было две причины: во-первых, Фуртвенглер был выдающимся математиком и преподавателем; во-вторых, он был парализован и читал лекции сидя на инвалидном кресле, в то время как его ассистент делал записи на доске. Это произвело на Геделя особенно сильное впечатление.

В 1929 году Гедель защитил докторскую диссертацию, в которой доказал полноту исчисления предикатов первой ступени. В этом же году умер отец Геделя. У него был хороший бизнес, поэтому после его смерти семья осталась финансово обеспечена. После смерти мужа мать Геделя купила большую квартиру в Вене, где поселилась с двумя сыновьями. В 1930 году Гедель стал преподавать в Венском университете, где принадлежал к школе логического позитивизма до 1938 года.
Он был одним из главных участников Венского кружка – философского объединения, где были разработаны основы логического позитивизма. Кружок сложился еще в 1922 году вокруг австрийского физика М. Шлика – профессора Венского университета Шлика, семинары которого вызвали интерес Геделя к логике.

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

Несмотря на проблемы со здоровьем, Гедель продолжал свои исследования, в которых доказывал согласованность аксиомы выбора с другими аксиомами теории набора. Однако вскоре его ждал новый удар. Он был связан с внезапным убийством профессора Шлика. «Это происшествие, несомненно, послужило причиной серьезного нервного расстройства брата, что вызвало беспокойство матери. Вскоре после выздоровления его пригласили работать в США», – писал Рудольф Гедель.

Летом 1938 года Гедель отправился в Геттинген, где читал лекции о своих исследованиях в области теории набора. Осенью того же года он вернулся в Вену и женился на Адель Поркерт, с которой познакомился еще в 1927 году в одном из венских ночных клубов. Она была на шесть лет старше и разведена с первым мужем. Родители Геделя, и особенно его отец, всегда были против этой свадьбы.

В марте 1938 года Австрия была присоединена к Германии, но Геделя это не интересовало. Он во второй раз побывал в Принстоне, где работал в Институте высших исследований (the Institute for Advanced Study), а вторую часть учебного года провел во Франции, где прочел курс лекций. После присоединения Австрии к Германии большинство ученых, носивших степень приват-доцента, стали получать жалование за лекции. Гедель такого жалования не получал, так как многие полагали, что он еврей. Это было неправдой, хотя у Геделя действительно было много друзей евреев.

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

Гедель приехал в Америку в 1940 году, а в 1948 году стал гражданином США. С 1940 по 1953 год Гедель проработал в Институте высших исследований, а с 1953 года вошел в преподавательский состав Принстонского института.

Одним из ближайших друзей Геделя в Принстоне был Альберт Эйнштейн. Неясно, как Эйнштейн повлиял на Геделя, заставив его заниматься исследованиями теории относительности, но Гедель внес свой вклад в ее развитие.

В 1951 году Гедель получил высшую научную награду США – Эйнштейновскую премию, а в 1974 году – Национальную Медаль Науки. Он был членом Национальной Академии Наук США, Института Франции и почетным членом Лондонского Математического общества. Гедель состоял в Королевском обществе и Королевской Академии. О его отношении к Австрии говорит тот факт, что Гедель дважды отказался от членства в Академии Наук в Вене. Он также не принял Национальной Медали за научные и культурные достижения. Отношение к нему и к его семье в Австрии вызывало у Геделя чувство глубокой обиды.

Переехав в США, Гедель продолжил свою научную работу в области теории набора, которая имела огромное значение. Его шедевр «Согласованность аксиомы выбора и обобщенной континуум-гипотезы с аксиомами теории набора» (1940) стал классикой современной математики. В этой работе он доказал, что если аксиоматическая система теории набора, построенная по типу, предложенному Расселом и Уайтхедом в «Principia Mathematicа»1, последовательна, то она останется таковой в случае если аксиома выбора и обобщенная континуум-гипотеза будут добавлены к системе. Геделю не удалось доказать независимости этих аксиом от других аксиом теории набора. Она была доказана в 1963 году Германом Коэном2, который строил свое доказательство на геделевских идеях.

С годами Гедель все больше волновался о своем здоровье. Его брат Рудольф, врач по образованию, очень точно описал состояние Геделя в последние годы жизни ученого: «У моего брата всегда было собственное непоколебимое мнение обо всем, что его окружало, и его трудно было убедить в обратном. К несчастью, на протяжении всей жизни он полагал, что всегда прав не только в математике, но и в медицине, поэтому он был очень трудным пациентом. После сильного кровотечения, вызванного язвой двенадцатиперстной кишки он до конца жизни придерживался строгой (слишком строгой?) диеты, в результате чего медленно терял вес».

Адель, жена Геделя, оказывала ему очень большую поддержку. Но у нее тоже были проблемы со здоровьем: она сама перенесла два удара и операцию. В последние годы жизни Гедель пришел к выводу, что причиной язвы стало то, что он был отравлен. Отказываясь есть, чтобы избежать повторного отравления, Гедель практически приговорил себя к смерти. Как писал его брат, Гедель умер, «14 января 1978 года в Принстоне, сидя в кресле в больничной палате».

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


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


В 1931 году в одном из немецких научных журналов появилась статья двадцатипятилетнего Геделя, которая называлась «Über formal unentscheidbare Sätze der Principia Mathematicа und verwandter Systeme» («О формально неразрешимых предложениях Principia Mathematicа и родственных систем»). Эта работа сыграла решающую роль в истории логики и математики. В решении Гарвардского университета о присуждении Геделю почетной докторской степени (1952 год) она была охарактеризована как одно из величайших достижений современной логики.

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

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

Знаменитая работа Геделя посвящена центральной проблеме оснований математики.

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

Честь открытия аксиоматического метода принадлежит греческим математикам. Для аксиоматического метода характерно, что некоторые предложения – так называемые аксиомы, или постулаты (примером может служить предложение, согласно которому через любые две точки можно провести одну и только одну прямую) – принимаются без доказательства; остальные предложения данной теории выводятся из этих аксиом. Можно сказать, что аксиомы образуют «базис» системы, в то время как теоремы, получаемые из аксиом при помощи логических законов, – это «надстройка».

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

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

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

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

Как уже было сказано выше, Гедель рассматривает в работе систему «Principia Mathematicа» Уайтхеда и Рассела. В чем суть этой системы и почему именно она заинтересовала Геделя?

Работа «Principia Mathematicа» связана с возникновением в XIX веке нового направления в математическом анализе. Целью нового направления было представить всю чистую математику как часть формальной логики. Классическое выражение эта лини развития логики и математики получила в «Principia Mathematicа» Уайтхеда и Рассела (1910-1913 гг.). Зная интерес Геделя к логике, нетрудно догадаться, почему его увлекла именно эта работа.

Математикам XIX столетия удалось «арифметизировать» алгебру и так называемое «исчисление бесконечно малых», показав, что различные понятия, используемые в математическом анализе, определимы исключительно в арифметических терминах (т.е. в терминах целых чисел и арифметических операций над ними). Например, вместо того чтобы допускать мнимое число «квадратный корень из -1» в качестве некоей мистической «сущности», его стали определять как упорядоченную пару целых чисел (0,1), причем над такими парами разрешено было производить определенного рода операции «сложения» и «умножения». Аналогично иррациональное число «квадратный корень из 2» стали определять как некоторый класс рациональных чисел, а именно как класс рациональных чисел, квадраты которых меньше 2. Рассел же (а еще ранее немецкий математик Готтлоб Фреге) поставил своей целью показать, что все арифметические понятия можно определить в число логических терминов, а все аксиомы арифметики вывести из небольшого числа предложений, которые можно было бы квалифицировать как чисто логические истины.

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

Далеко не все математики согласились с тезисом Фреге-Рассела, согласно которому математика есть не что иное, как часть логики. Но независимо от степени приемлемости самого тезиса Фреге-Рассела, достоинства системы «Principia Mathematicа» позволяют считать ее неоценимым достижением на пути к дальнейшему изучению проблемы непротиворечивости. В «Principia Mathematicа» разработана система обозначений, при помощи которой все предложения чистой математики (в частности, арифметики) могут быть записаны некоторым стандартным образом. Кроме того, в этой работе явно сформулировано большинство правил вывода, используемых в математических доказательствах. Подводя итоги, можно сказать, что в «Principia Mathematicа» создан весьма совершенный инструмент для исследования всей системы арифметики как неинтерпретированного исчисления, т.е. как системы бессмысленных значков, из которых посредством точно сформулированных правил образуются и преобразуются «строчки» знаков – формулы.

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

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

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

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

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

В чем же состоит этот парадокс? Возьмем какой-нибудь язык (например, русский), средствами которого можно описывать и определять все чисто арифметические свойства чисел. Рассмотрим определения, которые можно сформулировать на этом языке. Ясно, что некоторые термины, относящиеся к арифметическим свойствам, определить явным образом все равно не удастся, хотя, конечно, мы можем понимать смысл этих слов и без определений. Несущественно, какие именно термины принять за исходные; мы можем, например, считать, что мы понимаем смысл предложений «целое число делится на другое целое число», «целое число является произведением двух целых чисел» и т.п. Свойство быть простым числом тогда можно определить следующим образом: «не делится ни одно целое число, кроме самого себя и числа 1»; свойство быть точным квадратом: «быть произведением некоторого целого числа на то же число» и т.п.

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

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

Теперь можно сформулировать парадокс Ришара. Определяющее выражение для свойства быть ришаровым числом описывает, очевидно, некоторое арифметическое свойство натуральных чисел. Значит, само определяющее выражение входит в описанную выше последовательность определяющих выражений. Но тогда оно имеет в этой последовательности некий номер. Обозначим его через n. Является ли число n ришаровым? Здесь неизбежно противоречие: число n является ришаровым в том и только в том случае, если оно не обладает свойством, описанном в предложении, которое имеет номер n, т.е. не обладает свойством быть ришаровым! Короче говоря, n ришарово тогда и только тогда, когда оно не ришарово, т.е. утверждение «n – ришарово» является одновременно и истинным и ложным.

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

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

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

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

Геделевский номер любого объекта формальной системы можно вычислить. Элементарные символы, составляющие алфавит системы, бывают двух сортов – константы и переменные. Допустим, что у нас есть десять символов-констант, которым припишем в качестве геделевских номеров числа от 1 до 10. Это такие символы, как «~» (сокращение для «не»), «V» («или»), «¬» (если…то…»), «=» («равно»), «0» (цифровой знак, изображающий число нуль), а также три знака препинания: левая скобка – ( ; правая скобка - ); и запятая – «,». Кроме того, понадобятся перевернутая буква «Ξ» (читаемая как «существует» и называемая «квантором существования») и строчная латинская буква «s», обозначающая числовой оператор, сопоставляющий каждому натуральному числу непосредственно следующее за ним число.

Приведем пример. Формулу «Ξx (x=s0)» можно прочесть как «существует такое x, что x непосредственно следует за числом 0». Каждому символу соответствует свой геделевский номер:


~ – 1

V – 2

¬ – 3

Ξ – 4

= – 5

0 – 6

s – 7

( – 8

) – 9

, – 10


Кроме элементарных символов-констант, в алфавит входят также переменные трех сортов: числовые переменные «x», «y», «z» (их геделевские номера – различные числа, большие 10), пропозициональные переменные «p», «q», «r» (их геделевские номера – квадраты различных простых чисел, больших 10) и предикатные переменные (их геделевские номера – кубы различных простых чисел, больших 10). Таким образом, сопоставим каждую переменную с ее геделевским номером:


x – 11

y – 13

z – 17


p – 112

q – 132

r – 172


P – 113

Q – 133

R – 173


Возьмем любую формулу системы и вычислим ее геделевский номер.

Например, Ξx (x=sy), которую можно прочесть как «существует такое x, что x непосредственно следует за у» и которая выражает то обстоятельство, что для каждого числа есть непосредственно следующее за ним. Выпишем геделевский номер для каждого входящего в формулу символа:


Ξ – 4

x – 11

( – 8

x – 11

= – 5

s – 7

y – 13

) – 9


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


24 311 58 711 115 137 1713 199


Это произведение и есть геделевский номер формулы Ξx (x=sy).

Подобным образом можно вычислить геделевский номер любой формулы. Его можно вычислить по схеме «2m умножить на 3n», где 2 и 3 – простые числа, а m и n – геделевские номера входящих в формулу символов.


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

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

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

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

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

Значит, если это исчисление непротиворечиво, то как G, так и ~G не выводимы из аксиом арифметики. Следовательно, если арифметика непротиворечива, то G является формально неразрешимой формулой.

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

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

(5) В заключение Гедель указал, как построить арифметическую формулу А, представляющую математическое высказывание «Арифметика непротиворечива», и доказал, что формула «А ¬ G» (если не А, то G) формально недоказуема. Из этого следует недоказуемость и самой формулы А.

^ Окончательный вывод: непротиворечивость арифметики нельзя установить посредством рассуждения, представимого в формальном арифметическом исчислении.


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

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

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

Итак, в работе «О формально неразрешимых предложениях ^ Principia Mathematicа и родственных систем» Гедель доказал, что внутри любой абстрактной системы выводного знания сколь угодно высокого уровня, начиная с определенного уровня сложности (с арифметики и выше), всегда имеются истинные утверждения, которые не могут быть доказаны средствами этой системы, и ложные утверждения, которые не могут быть опровергнуты.

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

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

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


Источники:


  1. Нагель Э., Ньюмен Д.Р. Теорема Геделя. – М.: Знание, 1970.

  2. Советский энциклопедический словарь. – М.: Советская энциклопедия, 1985.

  3. http://www.biglib.com.ua/read.php?pg_which=17&dir=0013&f=13_113&book_id=2385




  1. http://www.booksite.ru/fulltext/slo/var/cul/tur/rud/nev/rudnev_v/84.htm




  1. http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Godel.html




  1. http://www.inventors.ru/index.asp?mode=3556








1 Рассел Бертран (1872-1970) – английский философ, логик, математик, общественный деятель. Основоположник английского неореализма и неопозитивизма; эволюционировал от объективного к субъективному идеализму. Развил дедуктивно-аксиоматическое построение логики в целях логического обоснования математики. Автор (совместно с А. Уайтхедом) основополагающего труда по математической логике – «Основания математики» («Principia Mathematicа»). См. стр. 7

Уайтхед Альфред Норт (1861-1947) – англо-американский математик, логик и философ, представитель неореализма.

2


 Коэн Герман (1842-1918) – немецкий философ-идеалист, глава марбургской школы неокантианства. Мышление у Коэна, в отличие от Канта, порождает не только форму, но и содержание познания (идеальный образец которого – математика). Развил теорию этического социализма.

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


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





Похожие:

Московский государственный университет iconОргкомитет всероссийского тренинга «путь к олимпу»
Благотворительный фонд наследия Менделеева, Химический факультет мгу им. М. В. Ломоносова, рхту им. Д. И. Менделеева, рхо им. Д....
Московский государственный университет iconМосковский государственный областной университет

Московский государственный университет iconМосковский Государственный Университет имени М. В. Ломоносова

Московский государственный университет iconМосковский Государственный Университет имени М. В. Ломоносова

Московский государственный университет iconМосковский государственный университет Им. Ломоносова Фридрих Ницше
Введение
Московский государственный университет iconМосковский инженерно – физический институт (государственный университет)
Тема проекта (работы)
Московский государственный университет iconМосковский инженерно – физический институт (государственный университет)
Фамилия, имя, отчество дипломанта
Московский государственный университет icon2. Учетные унифицированные регистры
Фгоу впо московский государственный агроинженерный университет им. В. П. Горячкина
Московский государственный университет iconДепартамент образования города москвы московский городской педагогический университет вильнюсский педагогический университет информационное письмо уважаемые коллеги!
Московский городской педагогический университет на базе филологического факультета с 15 по 17 ноября 2007 года проводит международную...
Московский государственный университет iconМинистерство образования российской фередации
Московский государственный институт радиотехники электроники и автоматики (технический университет)
Московский государственный университет iconФилологический факультет
...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов