Теорема Геделя
РЕФЕРАТ
на тему: «ТЕОРЕМА ГЁДЕЛЯ»
Курт Гёдель
Курт Гёдель – крупнейший специалист по математической логике – родился 28 апреля 1906 г. В Брюнне (ныне г. Брно, Чехия). Окончил Венский университет, где защитил докторскую диссертацию, был доцентом в 1933–1938 гг. После аншлюса эмигрировал в США. С 1940 по 1963 г. Гёдель работал в Принстонском институте высших исследований. Гёдель – почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества.
В 1951 г. Курт Гёдель был удостоен высшей научной награды США – Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал1: «Вклад Курта Гёделя в современную логику поистине монументален. Это – больше, чем просто монумент. Это веха, разделяющая две эпохи… Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки».
Действительно, даже сухой перечень достижений Гёделя в математической логике показывает, что их автор по существу заложил основы целых разделов этой науки: теории моделей (1930 г.; так называемая теорема о полноте узкого исчисления предикатов, показывающая, грубо говоря, достаточность средств «формальной логики» для доказательства всех выражаемых на ее языке истинных предложений), конструктивной логики (1932–1933 гг.; результаты о возможности сведения некоторых классов предложений классической логики к их интуиционистским аналогам, положившие начало систематическому употреблению «погружающих операций», позволяющих осуществлять такое сведение различных логических систем друг другу), формальной арифметики (1932–1933 гг.; результаты о возможности сведения классической арифметики в интуиционистскую, показывающие в некотором смысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивных функций (1934 г.; определение понятия общерекурсивной функции, сыгравшего решающую роль в установлении алгоритмической неразрешимости ряда важнейших проблем математики, с одной стороны. И в реализации логико-математических задач на электронно-вычислительных машинах – с другой), аксиоматической теории множеств (1938 г.; доказательство относительной непротиворечивости аксиомы выбора и континуум-гипотезы Кантора от аксиом теории множеств, положившее начало серии важнейших результатов об относительной непротиворечивости и независимости теоретико-множественных принципов).
Теорема Гёделя о неполноте
Введение
В 1931 г. В одном из немецких научных журналов появилась сравнительно небольшая статья с довольно устрашающим названием «О формально неразрешимых предложениях Principia Mathematica и родственных систем». Автором ее был двадцатипятилетний математик из Венского университета Курт Гедель, впоследствии работавший в Принстонском институте высших исследований. Работа эта сыграла решающую роль в истории логики и математики. В решении Гарвардского университета о присуждении Гёделю почетной докторской степени (1952) она была охарактеризована как одно из величайших достижений современной логики.
Однако в момент опубликования ни название гёделевской работы. Ни содержание ее ничего не говорили большинству математиков. Упомянутые в ее названии Principia Mathematica – это монументальных трехтомный трактат Альфреда Норта Уайтхеда и Бертрана Рассела, посвященный математической логике и основаниям математики; знакомство с трактатом отнюдь не являлось необходимым условием для успешной работы в большей части разделов математики. Интерес к разбираемым в работе Гёделя вопросам всегда был уделом весьма немногочисленной группы учёных. В то же время рассуждения, приведенные Гёделем в его доказательствах, были для своего времени столь необычными. Что для полного их понимания требовалось исключительное владение предметом и знакомство с литературой, посвященной этим весьма специфическим проблемам.
Первая теорема о неполноте
Первая теорема Гёделя о неполноте, по всей видимости, является наиболее знаменательным результатом в математической логике. Она звучит следующим образом:
Для произвольной непротиворечивой формальной и вычислимой теории, в которой можно доказать базовые арифметические высказывания, может быть построено истинноеарифметическое высказывание, истинность которого не может быть доказана в рамках теории[1]. Другими словами, любая вполне полезная теория, достаточная для представления арифметики, не может быть одновременно непротиворечивой и полной.
Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказатьпротиворечивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.
Предположение о том, что теория вычислима, обозначает, что в принципе возможно реализовать компьютерный алгоритм (компьютерную программу), которая (если ей разрешено вычислять произвольно долгое врея, вплоть до бесконечности) вычислит список всех теорем теории. Фактически, достаточно вычислить только список аксиом, и все теоремы могут быть эффективно получены из такого списка.
Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I. В оригинальной записи Гёделя она звучала как:
«Общий вывод о существовании неразрешимых пропозиций заключается в следующем:
Теорема VI.
Для каждого ω-согласованного рекурсивного класса k ФОРМУЛ существуют рекурсивные ЗНАКИ r такие, что ни (vGenr), ни ¬(vGenr) не принадлежат Flg(k) (где v есть СВОБОДНАЯ ПЕРЕМЕННАЯ r)[2]».
Обозначение Flg происходит от нем. Folgerungsmenge – множество последовательностей, Gen происходит от нем. Generalisation – обобщение.
Грубо говоря, высказывание Гёделя G утверждает: «истинность G не может быть доказана». Если бы G можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если G недоказуемо, то оно истинно, а потому теория неполна (высказывание G невыводимо в ней).
Это пояснение на обычном естественном языке, а потому не совсем математически строго. Для предоставления строгого доказательства, Гёдель пронумеровал высказывания при помощи натуральных чисел. В этом случае теория, описывающая числа, также принадлежит множеству высказываний. Вопросы о доказуемости высказываний представимы в данном случае в виде вопросов о свойствах натуральных чисел, которые должны быть вычислимы, если теория полна. В этих терминах высказывание Гёделя гласит, что не существует числа с некоторым определённым свойством. Число с этим свойством будет являться доказательством противоречивости теории. Если такое число существует, теория противоречива вопреки первоначальному предположению. Так что предполагая, что теория непротиворечива (как предполагается в посылке теоремы), получается, что такого числа не существует, и высказывание Гёделя истинно, но в рамках теории этого доказать невозможно (следовательно, теория неполна). Важное концептуальное замечание состоит в том, что необходимо предположить, что теория непротиворечива, для того чтобы объявить высказывание Гёделя истинным.
Вторая теорема Гёделя о неполноте
Вторая теорема Гёделя о неполноте звучит следующим образом:
Для любой формально рекурсивно перечислимой (то есть эффективно генерируемой) теории T, включая базовые арифметические истинностные высказывания и определённые высказывания о формальной доказуемости, данная теория T включает в себя утверждение о своей непротиворечивости тогда и только тогда, когда теория T противоречива.
Иными словами, непротиворечивость достаточно богатой теории не может быть доказана средствами этой теории. Однако вполне может оказаться, что непротиворечивость одной конкретной теории может быть установлена средствами другой, более мощной формальной теории. Но тогда встаёт вопрос о непротиворечивости этой второй теории, и т.д.
Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми – однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».
Дискуссии
Следствия теорем затрагивают философию математики, особенно такие формализмы, которые используют формальную логику для определения своих принципов. Можно перефразировать первую теорему о неполноте следующим образом: «невозможно найти всеохватывающую систему аксиом, которая была бы способна доказать все математические истины, и ни одной лжи». С другой стороны, с точки зрения строгой формальности, эта переформулировка не имеет особого смысла, поскольку она предполагает понятия «истина» и «ложь» определёнными в абсолютном смысле, нежели в относительном для каждой конкретной системы.
А вот такое перефразирование второй теоремы является ещё более тревожным для основ математики:
Если невозможно доказать непротиворечивость и полноту системы в рамках неё самой, то эта система противоречива.
Следовательно, для установления факта непротиворечивости некоторой системы S необходимо использовать более мощную систему T, но доказательство в рамках T не может быть полностью законченным, пока не доказана непротиворечивость самой T (причём без использования системы S).
Вначале казалось, что всё-таки теоремы Гёделя оставляют немного надежды, поскольку можно создать общий алгоритм, который решает, является ли заданное утверждение разрешимым или нет. Этот алгоритм позволит математикам обойти все неразрешимые проблемы сразу вместе. Однако, отрицательный ответ на проблемы выбора, полученный в 1936 году, показал, что такого алгоритма не существует.
Некоторые исследователи предполагают, что утверждение, которое недоказуемо в рамках дедуктивной системы, может быть совершенно доказуемо на некотором метаязыке. А то, что не может быть доказано на этом метаязыке, может, в свою очередь, быть доказано на мета-метаязыке, и так до бесконечности. Применяя такие системы типизированных метаязыков совместно с аксиомой редуцируемости, которая по индуктивному предположению применяется ко всему набору языков, можно для любых областей знаний обходить проблему неполноты.
Необходимо также отметить, что теоремы Гёделя применимы только к достаточно сильным системам аксиом. «Достаточно сильный» в данном контексте обозначает, что теория содержит достаточно средств для представления данных, необходимых для доказательства первой теоремы о неполноте. Существенно то, что для этого нужны базовые аксиомы, представляющие операции сложения и умножения, как, к примеру, в арифметике Робинсона Q. Существуют более слабые системы аксиом, которые полны и непротиворечивы, например, арифметика Пресбургера, которая доказывает истинность утверждений первого порядка только относительно сложения.
Система аксиом может содержать бесконечное количество аксиом (как, к примеру, арифметика Пеано первого порядка), но для применимости к такой системе теоремы Гёделя. должен быть эффективный алгоритм, который позволяет проверять корректность. Например, можно рассмотреть множество всех высказываний первого порядка, который истинны в стандартной модели натуральных чисел. Эта система полна, но теорема Гёделя неприменима в данном случае, поскольку не существует эффективной процедуры, которая определяет, является ли заданная последовательность аксиомой. Фактически, это так по следствию из первой теоремы Гёделя о неполноте.
Другой пример теории, к которой неприменима первая теорема Гёделя о неполноте, может быть построен следующим образом: необходимо отсортировать все возможные истинные утверждения относительно натуральных чисел сначал по длине строки, а затем лексикографически. Далее система аксиом строится так – вначале берётся система аксиом Пеано, после чего необходимо в списке утверждений выбирать первое по порядку утверждение, которое не может быть доказано. Далее это утверждение вносится в список аксиом новой системы. И так до конца. В конечном итоге этот процесс создаст полную, непротиворечивую и достаточно мощную формальную систему, которая, однако, не будет перечислимой.
Сам Гёдель доказал технически более слабые версии теорем. Первое доказательство теорем в приведённых в статье формулировках впервые было приведено Д.Б. Россером в 1936 году.
По существу, доказательство первой теоремы содержит процесс конструирования утверждения p в рамках формальной системы, которое можно описать на метаязыке следующим образом:
p= «Это утверждение не может быть доказано в рассматриваемой формальной системе»
Как видно, это, всего лишь, современный вариант парадокса лжеца, который в отличие от классической формулировки, не совсем парадоксальный.
Если система аксиом непротиворечива, доказательство теоремы Гёделя показывает, что p (и его отрицание) не могут быть доказаны в рамках системы. Следовательно утверждение p истинно (это утверждение о том, что оно само недоказуемо, и оно действительно недоказуемо). Если система аксиом ω-непротиворечива, то отрицание p также не может быть доказано, и таким образом p невычислимо. В системах, которые ω-противоречивы (но непротиворечивы), либо имеется такая же ситуация, либо утверждение ¬p может быть доказано.
Добавление утверждения p в качестве аксиомы не решает проблемы, поскольку для такой расширенной системы будет существовать иное утверждение Гёделя. Такие теории, как арифметика Пеано, для которых не может быть построено перечислимого расширения, называются существенно неполными.
Список литературы
гедель математический теорема неполнота
В.А. Успенский. Теорема Геделя о неполноте. – М.: Наука, 1982.
Теорема Геделя / Э. Нагель, Дж.Р. Ньюмен. – М.: Красанд, 2010. – 120 с.
Традиция. Русская энциклопедия: URL: http://traditio.ru/wiki/
1 Цитата сборника статей «Основания математики» выпущенному в Нью-Йорке в честь 60-летия К. Гёделя.