РЕФЕРАТ
на тему: «ТЕОРЕМАГЁДЕЛЯ»
КуртГёдель
Курт Гёдель –крупнейший специалист по математической логике – родился 28 апреля 1906 г.В Брюнне (ныне г. Брно, Чехия). Окончил Венский университет, где защитилдокторскую диссертацию, был доцентом в 1933–1938 гг. После аншлюсаэмигрировал в США. С 1940 по 1963 г. Гёдель работал в Принстонскоминституте высших исследований. Гёдель – почетный доктор Йельского иГарвардского университетов, член Национальной академии наук США и Американскогофилософского общества.
В 1951 г.Курт Гёдель был удостоен высшей научной награды США – Эйнштейновской премии. Встатье, посвященной этому событию, другой крупнейший математик нашего времениДжон фон Нейман писал[1]: «Вклад КуртаГёделя в современную логику поистине монументален. Это – больше, чем простомонумент. Это веха, разделяющая две эпохи… Без всякого преувеличения можносказать, что работы Гёделя коренным образом изменили сам предмет логики какнауки».
Действительно,даже сухой перечень достижений Гёделя в математической логике показывает, чтоих автор по существу заложил основы целых разделов этой науки: теории моделей(1930 г.; так называемая теорема о полноте узкого исчисления предикатов,показывающая, грубо говоря, достаточность средств «формальной логики» длядоказательства всех выражаемых на ее языке истинных предложений),конструктивной логики (1932–1933 гг.; результаты о возможности сведениянекоторых классов предложений классической логики к их интуиционистскиманалогам, положившие начало систематическому употреблению «погружающихопераций», позволяющих осуществлять такое сведение различных логических системдруг другу), формальной арифметики (1932–1933 гг.; результаты о возможностисведения классической арифметики в интуиционистскую, показывающие в некоторомсмысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивныхфункций (1934 г.; определение понятия общерекурсивной функции, сыгравшегорешающую роль в установлении алгоритмической неразрешимости ряда важнейшихпроблем математики, с одной стороны. И в реализации логико-математических задачна электронно-вычислительных машинах – с другой), аксиоматической теории множеств(1938 г.; доказательство относительной непротиворечивости аксиомы выбора иконтинуум-гипотезы Кантора от аксиом теории множеств, положившее начало серииважнейших результатов об относительной непротиворечивости и независимости теоретико-множественныхпринципов).
ТеоремаГёделя о неполноте
Введение
В 1931 г.В одном из немецких научных журналов появилась сравнительно небольшая статья сдовольно устрашающим названием «О формально неразрешимых предложениях PrincipiaMathematica и родственных систем». Автором ее был двадцатипятилетний математикиз Венского университета Курт Гедель, впоследствии работавший в Принстонскоминституте высших исследований. Работа эта сыграла решающую роль в историилогики и математики. В решении Гарвардского университета о присуждении Гёделю почетнойдокторской степени (1952) она была охарактеризована как одно из величайшихдостижений современной логики.
Однако вмомент опубликования ни название гёделевской работы. Ни содержание ее ничего неговорили большинству математиков. Упомянутые в ее названии PrincipiaMathematica – это монументальных трехтомный трактат Альфреда Норта Уайтхеда и БертранаРассела, посвященный математической логике и основаниям математики; знакомствос трактатом отнюдь не являлось необходимым условием для успешной работы в большейчасти разделов математики. Интерес к разбираемым в работе Гёделя вопросамвсегда был уделом весьма немногочисленной группы учёных. В то же время рассуждения,приведенные Гёделем в его доказательствах, были для своего времени стольнеобычными. Что для полного их понимания требовалось исключительное владениепредметом и знакомство с литературой, посвященной этим весьма специфическимпроблемам.Первая теорема о неполноте
Перваятеорема Гёделя о неполноте, по всей видимости, является наиболее знаменательнымрезультатом в математическойлогике. Она звучит следующим образом:
Дляпроизвольной непротиворечивой формальной и вычислимой теории, в которой можно доказатьбазовые арифметическиевысказывания, может быть построено истинноеарифметическоевысказывание, истинность которого не может быть доказана в рамках теории[1].Другими словами, любая вполне полезная теория, достаточная для представления арифметики, не может быть одновременнонепротиворечивой и полной.
Здесьслово «теория» обозначает «бесконечное множество» высказываний, некоторые изкоторых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут бытьвыведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание«доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории(константных символов алфавита) при помощи стандартной логики (первого порядка)». Теорияявляется непротиворечивой (согласованной), если в ней невозможнодоказатьпротиворечивое высказывание. Словосочетание «может быть построено»обозначает, что существует некоторая механическая процедура (алгоритм), котораяможет построить высказывание на основе аксиом, примитивов и логики первогопорядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральнымичислами. Результирующее истинное, но недоказуемое высказывание частообозначается для заданной теории как «последовательность Гёделя», однакосуществует бесконечно количество других высказываний в теории, которые имеюттакое же свойство: недоказуемая в рамках теории истинность.
Предположениео том, что теория вычислима,обозначает, что в принципе возможно реализовать компьютерный алгоритм(компьютерную программу), которая (если ей разрешено вычислять произвольнодолгое врея, вплоть до бесконечности) вычислит список всех теорем теории.Фактически, достаточно вычислить только список аксиом, и все теоремы могут бытьэффективно получены из такого списка.
Перваятеорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931года On Formally UndecidablePropositions 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 в качестве аксиомы не решает проблемы,поскольку для такой расширенной системы будет существовать иное утверждениеГёделя. Такие теории, как арифметика Пеано, для которых не может быть построеноперечислимого расширения, называются существеннонеполными.
Списоклитературы
гедель математический теорема неполнота
1. В.А. Успенский. Теорема Геделя о неполноте. – М.: Наука, 1982.
2. Теорема Геделя / Э. Нагель, Дж.Р. Ньюмен.– М.: Красанд, 2010. – 120 с.
3. Традиция. Русская энциклопедия: URL:traditio.ru/wiki/