Теоремы геделя о неполноте реферат

Обновлено: 04.07.2024

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

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

Введение

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

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

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

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

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

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

Теорема VI.

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

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

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

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

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

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

Дискуссии

А вот такое перефразирование второй теоремы является ещё более тревожным для основ математики:

Если невозможно доказать непротиворечивость и полноту системы в рамках неё самой, то эта система противоречива.

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

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

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

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

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

Сам Гёдель доказал технически более слабые версии теорем. Первое доказательство теорем в приведённых в статье формулировках впервые было приведено Д.Б. Россером в 1936 году.

По существу, доказательство первой теоремы содержит процесс конструирования утверждения p в рамках формальной системы, которое можно описать на метаязыке следующим образом:

Как видно, это, всего лишь, современный вариант парадокса лжеца, который в отличие от классической формулировки, не совсем парадоксальный.

Если система аксиом непротиворечива, доказательство теоремы Гёделя показывает, что p (и его отрицание) не могут быть доказаны в рамках системы. Следовательно утверждение p истинно (это утверждение о том, что оно само недоказуемо, и оно действительно недоказуемо). Если система аксиом ω-непротиворечива, то отрицание p также не может быть доказано, и таким образом p невычислимо. В системах, которые ω-противоречивы (но непротиворечивы), либо имеется такая же ситуация, либо утверждение ¬p может быть доказано.

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

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

гедель математический теорема неполнота

1. В.А. Успенский. Теорема Геделя о неполноте. – М.: Наука, 1982.

2. Теорема Геделя / Э. Нагель, Дж.Р. Ньюмен. – М.: Красанд, 2010. – 120 с.

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

Рубрика	Математика
Вид	контрольная работа
Язык	русский
Дата добавления	16.12.2014
Размер файла	262,7 K

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

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

Содержание

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

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

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

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

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

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

Что же доказал Гёдель?

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

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

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

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

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

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

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

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

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

В своей формулировке теоремы о неполноте Гёдель использовал понятие щ-непротиворечивой формальной системы -- более сильное условие, чем просто непротиворечивость. Формальная система называетсящ-непротиворечивой, если для всякой формулы 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 иногда называют гёделевой неразрешимой формулой.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Подобные документы

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

реферат [21,5 K], добавлен 03.05.2011

Теорія множин як абстрактно-теоретична наука про множини довільної природи, розгляд головних проблем. Загальна характеристика теореми Кантора-Берштейна. Знайомство з властивостями множин потужності континууму. Аналіз діяльності математика К. Геделя.

курсовая работа [325,6 K], добавлен 27.04.2016

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

дипломная работа [500,8 K], добавлен 13.02.2010

Биография русского ученого Н.И. Лобачевского. Система аксиом Гильберта. Параллельные прямые, треугольники и четырехугольники на плоскости и пространстве по Лобачевскому. Понятие о сферической геометрии. Доказательство теорем на различных моделях.

реферат [564,5 K], добавлен 12.11.2010

Понятие формальной системы. Основные понятия логики первого порядка. Доказательство неразрешимости проблемы остановки. Машина Тьюринга, ее структура. Вывод неразрешимости логики первого порядка из неразрешимости проблемы остановки и методом Геделя.

курсовая работа [243,0 K], добавлен 16.02.2011

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

курсовая работа [26,2 K], добавлен 24.05.2009

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 4 3 11 5 8 7 11 11 5 13 7 17 13 19 9

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

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

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

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

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

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

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

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

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

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

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

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

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

Кто же такой Гёдель?

Что же доказал Гёдель?

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

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

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

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

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

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

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

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

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

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

[МК] Чтобы проиллюстрировать полярность точек зрения современных исследователей на интерпретацию теоремы Гёделя в применении к человеческому мышлению, приведу две цитаты. Одна из них проливает свет на воззрения самого Курта Гёделя.

Шкорубская Е.Г. – Проблемное поле теорем Гёделя о неполноте

Целищев В.В. – Рационалистический оптимизм и философия Курта Геделя

Игорь Гарин – Математическая логика и теорема Курта Гёделя

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

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

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

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

Читайте также: