Теорема геделя о формальной логике. Множество истинных утверждений

на тему: «ТЕОРЕМА ГЁДЕЛЯ»

Курт Гёдель

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

В 1951 г. Курт Гёдель был удостоен высшей научной награды США – Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал : «Вклад Курта Гёделя в современную логику поистине монументален. Это – больше, чем просто монумент. Это веха, разделяющая две эпохи… Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки».

Действительно, даже сухой перечень достижений Гёделя в математической логике показывает, что их автор по существу заложил основы целых разделов этой науки: теории моделей (1930 г.; так называемая теорема о полноте узкого исчисления предикатов, показывающая, грубо говоря, достаточность средств «формальной логики» для доказательства всех выражаемых на ее языке истинных предложений), конструктивной логики (1932–1933 гг.; результаты о возможности сведения некоторых классов предложений классической логики к их интуиционистским аналогам, положившие начало систематическому употреблению «погружающих операций», позволяющих осуществлять такое сведение различных логических систем друг другу), формальной арифметики (1932–1933 гг.; результаты о возможности сведения классической арифметики в интуиционистскую, показывающие в некотором смысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивных функций (1934 г.; определение понятия общерекурсивной функции, сыгравшего решающую роль в установлении алгоритмической неразрешимости ряда важнейших проблем математики, с одной стороны. И в реализации логико-математических задач на электронно-вычислительных машинах – с другой), аксиоматической теории множеств (1938 г.; доказательство относительной непротиворечивости аксиомы выбора и континуум-гипотезы Кантора от аксиом теории множеств, положившее начало серии важнейших результатов об относительной непротиворечивости и независимости теоретико-множественных принципов).

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

Введение

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

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

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

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

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

Здесь слово «теория» обозначает «бесконечное множество» высказываний, некоторые из которых полагаются истинными без доказательств (такие высказывания называются аксиомами), а другие (теоремы) могут быть выведены из аксиом, а потому полагаются (доказываются) истинными. Словосочетание «доказуемый в теории» обозначает «выводимый из аксиом и примитивов теории (константных символов алфавита) при помощи стандартной логики (первого порядка)». Теория является непротиворечивой (согласованной), если в ней невозможно доказатьпротиворечивое высказывание. Словосочетание «может быть построено» обозначает, что существует некоторая механическая процедура (алгоритм), которая может построить высказывание на основе аксиом, примитивов и логики первого порядка. «Элементарная арифметика» заключается в наличии операций сложения и умножения над натуральными числами. Результирующее истинное, но недоказуемое высказывание часто обозначается для заданной теории как «последовательность Гёделя», однако существует бесконечно количество других высказываний в теории, которые имеют такое же свойство: недоказуемая в рамках теории истинность.

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

Первая теорема о неполноте была озаглавлена как «Теорема VI» в статье Гёделя от 1931 года On Formally Undecidable Propositions in Principia Mathematica and Related Systems I . В оригинальной записи Гёделя она звучала как:

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

Теорема VI .

Для каждого ω-согласованного рекурсивного класса k ФОРМУЛ существуют рекурсивные ЗНАКИ r такие, что ни (v Genr ), ни ¬(v Genr )не принадлежат Flg (k )(где v есть СВОБОДНАЯ ПЕРЕМЕННАЯ r ) ».

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

Грубо говоря, высказывание Гёделя G утверждает: «истинность G не может быть доказана». Если бы G можно было доказать в рамках теории, то в таком случае теория содержала бы теорему, которая противоречит сама себе, а потому теория была бы противоречива. Но если G недоказуемо, то оно истинно, а потому теория неполна (высказывание G невыводимо в ней).

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

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

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

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

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

Использовать эту теорему для доказательства того, что разумная деятельность не сводится к вычислениям, пытались многие. Например, еще в 1961 году известный логик Джон Лукас (John Lucas) выступал с подобной программой. Его рассуждения оказались довольно уязвимыми – однако он и задачу ставил более широко. Роджер Пенроуз использует несколько другой подход, который излагается в книге полностью, «с нуля».

Дискуссии

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

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

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

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

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

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

Можно показать, что эта ф-ла сама выводима из аксиом Пеано. Отсюда легко получается вторан теорема Гёделя о неполноте, которая (нестрого) утверждает, что непротиворечивость формальной системы А нельзя доказать средствами этой системы. Более строго, если формальная система А непротиворечива и содержит аксиомы Пеано, то ф-ла недоказуема в . В самом деле, из доказуемости ф-л (1) и (2) вытекает, что формулы и эквивалентны в системе А. Но недоказуема в Л, согласно первой теореме Гёделя; значит, тоже недоказуема.

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

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

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

Лит.: Клини С. К. Математическая логика. Пер. с англ. М., 1973 [библиогр. с. 451-465); FefermanS. Arithmetization of metamathematics in a general setting. «Pundamenta mathematicae», 1960, v. 49; Линдон P. Заметки по логике. Пер. с англ. М., 1968 [библиогр. с. 123]; Арбиб М. Мозг, машина и математика. Пер. с англ. М., 1968 [библиогр. с. 217- 224]; Нагель Э., Ньюмен Д. Р. Теорема Гёделя. Пер. с англ. М., 1970.

Всякая система математических аксиом начиная с определенного уровня сложности либо внутренне противоречива, либо неполна.

В 1900 году в Париже прошла Всемирная конференция математиков, на которой Давид Гильберт (David Hilbert, 1862–1943) изложил в виде тезисов сформулированные им 23 наиважнейшие, по его мнению, задачи, которые предстояло решить ученым-теоретикам наступающего ХХ века. Под вторым номером в его списке значилась одна из тех простых задач, ответ на которые кажется очевидным, пока не копнешь немножечко глубже. Говоря современным языком, это был вопрос: самодостаточна ли математика? Вторая задача Гильберта сводилась к необходимости строго доказать, что система аксиом - базовых утверждений, принимаемых в математике за основу без доказательств, - совершенна и полна, то есть позволяет математически описать всё сущее. Надо было доказать, что можно задать такую систему аксиом, что они будут, во-первых, взаимно непротиворечивы, а во-вторых, из них можно вывести заключение относительно истинности или ложности любого утверждения.

Возьмем пример из школьной геометрии. В стандартной Евклидовой планиметрии (геометрии на плоскости) можно безоговорочно доказать, что утверждение «сумма углов треугольника равна 180°» истинно, а утверждение «сумма углов треугольника равна 137°» ложно. Если говорить по существу, то в Евклидовой геометрии любое утверждение либо ложно, либо истинно, и третьего не дано. И в начале ХХ века математики наивно полагали, что такая же ситуация должна наблюдаться в любой логически непротиворечивой системе.

И тут в 1931 году какой-то венский очкарик - математик Курт Гёдель - взял и опубликовал короткую статью, попросту опрокинувшую весь мир так называемой «математической логики». После долгих и сложных математико-теоретических преамбул он установил буквально следующее. Возьмем любое утверждение типа: «Предположение №247 в данной системе аксиом логически недоказуемо» и назовем его «утверждением A». Так вот, Гёдель попросту доказал следующее удивительное свойство любой системы аксиом:

«Если можно доказать утверждение A, то можно доказать и утверждение не-A».

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

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

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

Спокойнее было бы думать, что теоремы Гёделя носят отвлеченный характер и касаются не нас, а лишь областей возвышенной математической логики, однако фактически оказалось, что они напрямую связаны с устройством человеческого мозга. Английский математик и физик Роджер Пенроуз (Roger Penrose, р. 1931) показал, что теоремы Гёделя можно использовать для доказательства наличия принципиальных различий между человеческим мозгом и компьютером. Смысл его рассуждения прост. Компьютер действует строго логически и не способен определить, истинно или ложно утверждение А, если оно выходит за рамки аксиоматики, а такие утверждения, согласно теореме Гёделя, неизбежно имеются. Человек же, столкнувшись с таким логически недоказуемым и неопровержимым утверждением А, всегда способен определить его истинность или ложность - исходя из повседневного опыта. По крайней мере, в этом человеческий мозг превосходит компьютер, скованный чистыми логическими схемами. Человеческий мозг способен понять всю глубину истины, заключенной в теоремах Гёделя, а компьютерный - никогда. Следовательно, человеческий мозг представляет собой что угодно, но не просто компьютер. Он способен принимать решения, и тест Тьюринга пройдет успешно.

Интересно, догадывался ли Гильберт, как далеко заведут нас его вопросы?

Курт ГЁДЕЛЬ
Kurt Gödel, 1906–78

Австрийский, затем американский математик. Родился в г. Брюнн (Brünn, ныне Брно, Чехия). Окончил Венский университет, где и остался преподавателем кафедры математики (с 1930 года - профессором). В 1931 году опубликовал теорему, получившую впоследствии его имя. Будучи человеком сугубо аполитичным, крайне тяжело пережил убийство своего друга и сотрудника по кафедре студентом-нацистом и впал в глубокую депрессию, рецидивы которой преследовали его до конца жизни. В 1930-е годы эмигрировал было в США, но вернулся в родную Австрию и женился. В 1940 году, в разгар войны, вынужденно бежал в Америку транзитом через СССР и Японию. Некоторое время проработал в Принстонском институте перспективных исследований. К сожалению, психика ученого не выдержала, и он умер в психиатрической клинике от голода, отказываясь принимать пищу, поскольку был убежден, что его намереваются отравить.

Комментарии: 0

Как развивается научная модель в естественных науках? Накапливается житейский либо научный опыт, его вехи аккуратно формулируются в виде постулатов и образуют базу модели: набор утверждений, принимаемых всеми, кто работает в рамках этой модели.

Анатолий Вассерман

В 1930 году Курт Гедель доказал две теоремы, которые в переводе с математического языка на человеческий означают примерно следующее: Любая система аксиом, достаточно богатая, чтобы с ее помощью можно было определить арифметику, будет либо не полна, либо противоречива. Не полная система – это значит, что в системе можно сформулировать утверждение, которое средствами этой системы нельзя ни доказать, ни опровергнуть. Но Бог, по определению, есть конечная причина всех причин. С точки зрения математики это означает, что введение аксиомы о Боге делает всю нашу аксиоматику полной. Если есть Бог, значит любое утверждение можно либо доказать, либо опровергнуть, ссылаясь, так или иначе, на Бога. Но по Геделю полная система аксиом неизбежно противоречива. То есть, если мы считаем, что Бог существует, то мы вынуждены прийти к выводу, что в природе возможны противоречия. А поскольку противоречий нет, иначе бы весь наш мир рассыпался от этих противоречий, приходиться прийти к выводу, что существование Бога не совместимо с существованием природы.

Сосинский А. Б.

Теорема Гёделя, наряду с открытием теории относительности, квантовой механики и ДНК, обычно рассматривается как крупнейшее научное достижение ХХ века. Почему? В чем ее суть? Каково ее значение? Эти вопросы в своей лекции в рамках проекта «Публичные лекции "Полит.ру"» раскрывает Алексей Брониславович Сосинский, математик, профессор Независимого московского университета, офицер Ордена академических пальм Французской Республики, лауреат премии Правительства РФ в области образования 2012 года. В частности, были даны несколько разных ее формулировок, описаны три подхода к ее доказательству (Колмогорова, Чейтина и самого Гёделя), и объяснено ее значение для математики, физики, компьютерной науки и философии.

Успенский В. А.

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

Успенский В. А.

Лекции летней школы «Современная математика», г. Дубна.

1. Формальные аксиоматические теории и натуральные числа

2. Формальная арифметика и ее свойства

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

4. Гёдель и его роль в математической логике XX в

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

После доказательства теоремы 35.7 о том, что существует перечислимое, но неразрешимое множество натуральных чисел, было заявлено, что она фактически включает в себя в неявном виде теорему Гёделя о неполноте формальной арифметики. Цель настоящего параграфа состоит в том, чтобы обосновать это заявление. Таким образом, в рамках общей теории алгоритмов, кроме тех теорем, которые были доказаны в двух предыдущих параграфах, будет продемонстрировано продвижение теории алгоритмов в направлении решения чисто логических проблем. Для этого сначала предстоит увязать терминологию логической проблемы о неполноте формальной арифметики с методологической терминологией общей теории алгоритмов, методами которой эта проблема будет решена. При этом утверждение теоремы 35.7 о существовании перечислимого, но неразрешимого множества натуральных чисел будет основополагающей предпосылкой для доказательства теоремы Гёделя, которую мы докажем в следующей формулировке: "Каждая адекватная со-непротиворечивая формальная арифметика неполна". Далее, мы поясним, что будем понимать под формальной арифметикой, а также определим и разъясним те понятия, которые участвуют в приведенной формулировке теоремы Гёделя. Начнем с формальных аксиоматических теорий.

Формальные аксиоматические теории и натуральные числа

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

Понятия вывода и теоремы в формальной аксиоматической теории даны в определении 28.2.

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

Теорема 37.1. Множество всех теорем формальной аксиоматической теории Т перечислимо.

Доказательство. Мы уже отметили, что множество аксиом формальной теории перечислимо, т. е. мы можем их эффективно перенумеровать A_1,A_2,A_3,\ldots . Поскольку все формулы состоят из конечного числа букв (символов), все выводы содержат конечное число формул и каждый вывод использует лишь конечное число аксиом, то ясно, что для каждого натурального п существует лишь конечное число выводов, имеющих не более чем п формул (шагов) и использующих только аксиомы \{A_1,A_2,\ldots,A_n\} . Следовательно, двигаясь от n=1 к n=2,~ n=3 и т.д., можно эффективно перенумеровать все теоремы данной теории. Это и означает, что множество теорем перечислимо.

Теперь от произвольных формальных теорий будем переходить к таким, которые так или иначе имеют дело с натуральными числами. Если мы хотим в нашей теории говорить о подмножестве Q множества натуральных чисел, то мы должны иметь эффективный способ выписывания для каждого натурального п формулы W_n , означающей, что n\in Q . Более того, если мы сможем доказать, что формула W_n является теоремой теории T тогда и только тогда, когда n\in Q , то будем говорить, что теория T полуполна для Q (или что в T имеется полуполное описание Q ). Точнее, это определение сформулируем так.

Определение 37.2. Теория T называется полуполной для множества натуральных чисел Q\subseteq \mathbb{N} , если существует перечислимое множество формул W_0,W_1,\ldots,W_n,\ldots , такое, что .

Определение 37.3. Теория T называется полной для Q , если она полуполна для Q и мы также имеем формулу \lnot W_n , которая интерпретируется как n\notin Q , и мы можем доказать, что \lnot W_n является теоремой теории T тогда и только тогда, когда n\notin Q . Другими словами, теория T полна для Q , если в T для каждого п мы можем установить, принадлежит оно Q или нет. Точнее, это означает, что теория T называется полной для множества натуральных чисел T , если она полуполна для Q и полуполна для его дополнения \overline{Q} .

Теорема 37.4. Если теория T полуполна для множества Q , то Q перечислимо.

Доказательство. По определению полуполноты T для Q множество Q есть множество номеров тех формул из некоторого перечислимого множества \{W_0,W_1,\ldots,W_n,\ldots\} формул, которые являются теоремами теории T , т.е. принадлежит и множеству \operatorname{Th}(T) . Таким образом, Q есть множество номеров всех формул из множества \operatorname{Th}(T)\cap \{W_0,W_1,\ldots,W_n,\ldots\} . Каждое из этих пересекаемых множеств перечислимо: первое - по предыдущей теореме 37.1, второе - по сказанному в начале доказательства. Следовательно, и их пересечение, по теореме 35.5, перечислимо. Но тогда пере-цислимо и множество номеров тех формул, которые входят в это пересечение.

Следствие 37.5. Если Q перечислимое, но неразрешимое множество натуральных чисел, то никакая формальная теория не может быть полной для Q .

Доказательство. Если множество Q перечислимо, но неразрешимо, то в силу теоремы 35.6 его дополнение \overline{Q} неперечис-лимо. Тогда по теореме 37.4 никакая теория T не является полуполной для \overline{Q} . Следовательно, никакая теория T неполна для Q .

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

Формальная арифметика и ее свойства

Формальная арифметика как формальная аксиоматическая теория строится на базе формализованного исчисления предикатов, рассмотренного ранее. Предметные переменные здесь будем называть числовыми, потому что вместо них будем подставлять натуральные числа.

Предметная переменная называется свободной в формуле, если она не стоит под знаком квантора (общности или существования), и связанной - в противном случае. Формула называется замкнутой, если все ее предметные переменные связаны, и открытой, если в ней имеются свободные переменные. Замыканием формулы F называется формула C(F) , получающаяся из F дописыванием спереди кванторов общности по всем переменным, свободным в F . Ясно, что для любой F формула C(F) замкнута. Если F замкнута, то C(F)=F .

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

С понятием подстановки в формулу мы уже знакомы. Если в формулу F вместо символа (слова) X везде, где он входит в F , вставить слово (формулу) H , то получим новое слово (формулу), обозначаемое S_X^HF и называемое результатом подста-новки в F слова H вместо слова X . Тогда ясно, что

\begin{gathered}S_X^H(\lnot F)\equiv \lnot S_X^HF;\qquad S_X^H(F\to G)\equiv S_X^HF\to S_X^HG;\\ \text{esli}~ i\ne j,~ \text{to}~ S_{x_i}^N(\forall x_j)(F)\equiv (\forall x_j)S_{x_i}^NF,~ S_{x_i}^N(\exists x_j)(F)\equiv (\exists x_j)S_{x_i}^NF. \end{gathered}

Имея дело с натуральными числами, мы хотели бы иметь возможность подставлять их в формулы формальной теории (арифметики), т.е. иметь возможность говорить о числах на языке нашей формальной теории. Для этой цели в формальной теории необходимо иметь слова, которые служили бы названиями натуральных чисел. Такие слова называются нумералами. Нумерал числа п обозначается n^{\ast} . Требование к этим названиям (именам) вполне естественное: различные числа должны называться различными именами, т.е. если m\ne n , то m^{\ast}\ne n^{\ast} . (Идея введения нумералов состоит в том, чтобы разделить вещи и имена этих вещей.)

Таким образом, в формулы арифметики мы будем подставлять вместо числовых переменных x_1,x_2,x_3,\ldots не сами натуральные числа m,n,k,\ldots , а их нумералы (имена) m^{\ast},n^{\ast},k^{\ast},\ldots соответственно.

Наконец, мы можем сформулировать последнее требование (аксиому), которое мы предъявляем к формальной арифметике. Назовем его аксиомой арифметики: если предметная переменная jc, не связана в F , то

\text{(AA)}\colon~ S_{x_i}^{n^{\ast}}F\to (\exists x_i)(F).

Если ввести для S_{x_i}^{n^{\ast}}F обозначение F(n^{\ast}) , то эта аксиома принимает вид:

\text{(AA)}\colon~ F(n^{\ast})\to (\exists x_i)(F).

Это исключительно естественное требование: если формула F превращается в истинное высказывание при подстановке в нее вместо переменной x_i какого-нибудь натурального числа n^{\ast} , то истинно и высказывание (\exists x_i)(F) .

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

Итак, определившись с понятием формальной арифметики, посвятим оставшуюся часть этого пункта понятиям ю-непротиво-речивости, адекватности и полноты этой формальной теории, участвующим в точной формулировке теоремы Гёделя.

Начнем с понятия непротиворечивости. Как и всякая аксиоматическая теория, формальная арифметика называется непротиворечивой, если в ней нельзя доказать какое-либо утверждение и его отрицание, т.е. если не существует такой формулы F , что одновременно \vdash F и \vdash\lnot F .

Предположим теперь, что для некоторой формулы G(x) , содержащей свободно единственную предметную переменную х, установ-дено, что для всех натуральных чисел n=0,1,2,3,\ldots . Даже если в формальной арифметике невозможно доказать \vdash (\forall x)(G(x)) , мы конечно же можем считать это утверждение следствием приведенного списка теорем. Следовательно, если в теории удастся доказать теорему , то такую формальную арифметику следует считать противоречивой.

Определение 37.6. Формальная арифметика называется ω-непротиворечивой, если в ней нет такой формулы G(x) с единственной свободной предметной переменной x , что для всех натуральных чисел n справедливы теоремы \vdash G(n^{\ast}) и \vdash\lnot (\forall x)(G(x)) .

Теорема 37.7. Если формальная арифметика ^-непротиворечива, то она непротиворечива.

Доказательство. В самом деле, если бы она была противоречива, то, как доказано в §27, после определения 27.1, все ее формулы были бы теоремами, в том числе и те, которые создают ω-противоречивость формальной арифметики, и последняя была бы ω-противоречива.

Определение 37.8. Назовем n-местный предикат P(x_1,\ldots,x_n) над множеством натуральных чисел N вполне представимым в формальной арифметике, если существует такая формула F(x_1,\ldots,x_n) , свободными предметными переменными которой являются п переменных x_1,\ldots,x_n (и только они), что:

а) для каждого набора n натуральных чисел (a_1,\ldots,a_n) , для которого предикат P превращается в истинное высказывание P(a_1,\ldots,a_n) , имеет место теорема: \vdash F(a_1^{\ast},\ldots,a_n^{\ast}) ;

б) для каждого набора n натуральных чисел (a_1,\ldots,a_n) , для которого предикат P превращается в ложное высказывание P(a_1,\ldots,a_n) , имеет место теорема: \vdash\lnot F(a_1^{\ast},\ldots,a_n^{\ast}) .

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

Разъясним теперь понятие адекватности формальной арифметики, участвующее в формулировке теоремы Гёделя. Мы хотели бы иметь возможность отвечать на вопросы о перечислимых множествах в такой арифметике. В теореме 37.4 мы показали, что лишь перечислимые множества чисел могут иметь полуполное описание в формальной теории, т.е. существует перечислимое множество формул W_0,W_1,W_2,\ldots , такое, что Q=\{n\colon \vdash W_n\} . Адекватность нашей формальной теории (арифметики) могла бы означать, что она является полуполной для каждого перечислимого Множества натуральных чисел, т.е. что в ней имеет полуполное описание всякое множество, которое вообще может иметь такое описание хотя бы в какой-нибудь теории.

В теореме 37.1 мы установили, что множество всех теорем фор. мальной теории перечислимо, т.е. все теоремы и, значит, приво-дящие к ним выводы (доказательства) могут быть эффективно перенумерованы. Возьмем наше множество Q и соответствующее ему множество теорем \{W_0,W_1,W_2,\ldots\} . Рассмотрим следующий предикат P(x,y)\colon " y - номер доказательства теоремы W_x ". Если высказывание P(m,n) истинно, то это означает, что n есть номер вывода теоремы W_m , что, в свою очередь, означает, что m\in Q , т.е. n есть номер вывода о том, что m\in Q . Обратно, взяв конкретные числа m и n , мы можем эффективно построить теорему (формулу) W_m и эффективно построить n-й вывод, после чего эффективно определить, является ли построенный вывод выводом теоремы W_m , т.е. эффективно узнать, истинно ли высказывание P(m,n) . Следовательно, P(x,y) - такой вычислимый предикат, что .

Сформулируем теперь определение.

Определение 37.9. Формальная арифметика называется адекватной, если для каждого перечислимого множества Q натуральных чисел существует вполне представимый в этой арифметике предикат P(x,y) такой, что Q=\bigl\{x\colon (\exists y)(\lambda =1)\bigr\} .

Под полнотой формальной арифметики будем понимать абсолютную полноту, т.е. если для каждой замкнутой формулы F этой теории либо она сама, либо ее отрицание является теоремой этой теории: \vdash F или \vdash\lnot F .

Теперь мы можем перейти непосредственно к формулировке и доказательству теоремы Гёделя.

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

Теорема утверждает следующее. Всякая ω-непротиворечивая и адекватная формальная арифметика не является полной.

▼ Доказательство

Согласно теореме 35.7, выберем такое множество Q натуральных чисел, которое перечислимо, но неразрешимо. Так как наша формальная арифметика адекватна, то существует вполне представимый в ней перидикат P(x,y) такой, что

Q= \bigl\{x\colon\, (\exists y)\bigl(\lambda =1\bigr)\bigr\}.

Вполне представимость предиката P(x,y) в формальной арифметике означает, что найдется такая формула F(x,y) этой теории, содержащая лишь две свободных предметных переменных, что для каждой пары натуральных чисел (a,b) , для которой , имеет место теорема: \vdash F(a^{\ast},b^{\ast}) , а для каждой пары натуральных чисел (a,b) , для которой \lambda =1 , имеет место теорема: \vdash\lnot F(a^{ast},b^{\ast}) .

Применим к формуле F(x,y) квантор общности по переменной y . Получим формулу с единственной свободной предметной переменной x\colon\, G(x)\equiv (\exists y)(F(x,y)) . Покажем, что

Q= \bigl\{x\colon\, \vdash G(x^{\ast})\bigr\}.

Предположим, что m\in Q . Тогда (согласно (*)) найдется такое натуральное n , что высказывание P(m,n) истинно. Следовательно, имеет место теорема: \vdash F(m^{\ast},n^{\ast}) В силу аксиомы арифметики \text{AA} имеем теорему:

\vdash F(m^{\ast},n^{\ast})\to (\exists y)\bigl(F(m^{\ast},y)\bigr).

Из двух последних теорем по правилу МР заключаем:

\vdash (\exists y)\bigl(F(m^{\ast},y)\bigr) , то есть .

Это означает, что m\in \bigl\{x\colon \vdash G(x^{\ast})\bigr\} . Таким образом, Q \subseteq \bigl\{x\colon\vdash G(x^{\ast})\bigr\} .

Обратно, предположим, что m\in \bigl\{x\colon\vdash G(x^{\ast})\bigr\} , то есть \vdash G(m^{\ast}) , то есть \vdash (\exists y)(F(m^{\ast},y)) . Отсюда, в силу известного выражения (по закону де Моргана) квантора существования через квантор общности, заключаем, что

\vdash\lnot (\forall y)\bigl(\lnot F(m^{\ast},y)\bigr).

Поскольку наша формальная арифметика, кроме того, со-непро-тиворечива, то, ввиду наличия в ней последней теоремы, должно существовать такое натуральное число n_0 , что формула - \lnot F(m^{\ast},n^{\ast}_0) не является теоремой этой арифметики. А раз так, то высказывание P(m,n_0) истинно (если бы оно было ложно, то мы имели бы теорему \vdash\lnot F(m^{\ast},n^{\ast}_0) , что не так). По определению (*) множества Q , это означает, что m\in Q . Таким образом, \{x\colon\vdash G(x^{\ast})\}\subseteq Q . Итак, равенство (**) доказано.

Теперь выясним, в каком отношении находятся между собой множества \overline{Q} (дополнение Q ) и \{x\colon\vdash G(x^{\ast})\} . Пусть me m\in \{x\colon\vdash\lnot G(x^{\ast})\} , то есть \vdash\lnot G(x^{\ast}) . Тогда m\in \overline{Q} , ибо если бы m\in Q , то в силу (**) мы имели бы \vdash G(m^{\ast}) и наша формальная арифметика была бы противоречивой, но это не так в силу ее ©-непротиворечивости (по условию) и теоремы 37.7. Таким образом, \{x\colon\vdash G(x^{\ast})\}\subseteq \overline{Q} .

Покажем, что последнее включение является строгим. Напомним, что мы выбрали множество Q перечислимым, но не являющимся разрешимым. Тогда согласно следствию 37.5 из теоремы 37.4, никакая формальная теория не может быть полной для Q . Равенство (**) говорит, что наша формальная арифметика полуполна для Q . Если бы имело место равенство \overline{Q}= \{x\colon\vdash G(x^{\ast})\} , то это означало бы, что наша формальная арифметика полуполна и для \overline{Q} и, значит, она была бы полной для Q . Последнее невозможно в силу следствия 37.5 из теоремы_37.4. Следовательно, \{x\colon\vdash G(x^{\ast})\}\ne \overline{Q} .

Итак, \{x\colon\vdash\lnot G(x^{\ast})\}\subset \overline{Q} . Следовательно, существует такое число m_0\in \overline{Q} , что m_0\notin \{x\colon\vdash\lnot G(x^{\ast})\} , т. е. неверно, что \vdash\lnot G(m_0^{\ast}) . В тоже время неверно также, что \vdash G(m_0^{\ast}) , поскольку это, в силу (**), означало бы, что m_0\in Q , а это не так. Следовательно, мы нашли формулу G(m_0^{\ast}) , такую, что ни она сама, ни ее отрицание не являются теоремами нашей формальной арифметики. Это и означает, что данная формальная арифметика не является полной.

Теорема Гёделя полностью доказана.

Обратимся еще раз к высказыванию \lnot G(m_0^{\ast}) . Согласно равенству (**), его можно интерпретировать как m_0\on \overline{Q} и, следовательно, оно обязательно является "истинным" высказыванием. Но тем не менее оно не является теоремой нашей формальной арифметики. Если добавить формулу G(m_0^{\ast}) к списку аксиом и рассмотреть новую формальную арифметику, то положение не изменится: для вновь полученной формальной арифметики верны все те предпосылки, которые привели нас к теореме Гёделя. Значит, мы снова найдем такое число m_1 , что высказывание \lnot G(m_1^{\ast}) истинно, но не является теоремой новой формальной арифметики и т.д.

Гёдель и его роль в математической логике XX в

Курт Гёдель родился 28 апреля 1906 г. в г. Брюнне (ныне г. Брно в Чехии). Окончил Венский университет, где защитил докторскую диссертацию и был доцентом в период 1933- 1938 гг. После оккупации Австрии фашистской Германией эмигрировал в США. С 1940 по 1963 г. Гёдель работает в Принстонском институте высших исследований (с 1953 г. он профессор этого института). Гёдель - почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества. В 1951 г. Гёдель удостоен высшей научной награды США - Эйнштейновской премии. В статье, посвященной этому событию, другой крупнейший математик нашего времени Джон фон Нейман писал: "Вклад Курта Гёделя в современную логику поистине монументален. Это - больше, чем просто монумент, это веха, разделяющая две эпохи... Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки". Гёдель заложил основы целых разделов математической логики: теории моделей (1930), конструктивной логики (1932-1933), формальной арифметики (1932-1933), теории алгоритмов и рекурсивных функций (1934), аксиоматической теории множеств (1938). Гёдель умер в Принстоне (США) 14 января 1978 г.

В вашем браузере отключен Javascript.
Чтобы произвести расчеты, необходимо разрешить элементы ActiveX!

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

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

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

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

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

Переход от одной формулы к другой происходит по некоторым известным правилам. Переход от 4-й формулы к 5-й произошёл, скажем, потому, что всякое число равно самому себе - такова аксиома арифметики. А вся процедура доказывания, таким образом, переводит формулу в булево значение ИСТИНА. Результатом могла быть и ЛОЖЬ - если бы мы опровергали какую-то формулу. В таком случае мы бы доказали её отрицание. Можно себе представить программу (и такие программы действительно написаны), которые бы доказывали подобные (и более сложные) высказывания без участия человека.

Изложим то же самое чуть более формально. Пусть у нас есть множество, состоящее из строк символов какого-то алфавита, и существуют правила, по которым из этих строк можно выделить подмножество так называемых высказываний - то есть грамматически осмысленных фраз, каждая из которых истинна или ложна. Можно сказать, что существует функция , сопоставляющая высказываниям из одно из двух значений: ИСТИНА или ЛОЖЬ (то есть отображающая их в булево множество из двух элементов).

Назовём такую пару - множество высказываний и функция из в - «языком высказываний» . Заметим, что в повседневном смысле понятие языка несколько шире. Например, фраза русского языка «А ну иди сюда!» не истинна и не ложна, то есть высказыванием, с точки зрения математической логики, не является.

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

Спросим себя: для всякой ли функции существует «доказывающий алгоритм» (или, короче, «дедуктика» ), эквивалентный этой функции, то есть переводящий каждое высказывание именно в то булево значение, что и она? Лаконичнее тот же вопрос можно сформулировать так: всякая ли функция над множеством высказываний вычислима ? Как вы уже догадываетесь, из справедливости ТГН следует, что нет, не всякая - существуют невычислимые функции такого типа. Иными словами, не всякое верное высказывание можно доказать.

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

доказательство которой нашли только через три с половиной века после первой формулировки (и оно далеко не элементарно). Следует различать истинность высказывания и его доказуемость. Ниоткуда не следует, что не существует истинных, но недоказуемых (и не проверяемых в полной мере) высказываний.

Второй интуитивный довод против ТГН более тонок. Допустим, у нас есть какое-то недоказуемое (в рамках данной дедуктики) высказывание. Что мешает нам принять его в качестве новой аксиомы? Тем самым мы чуть усложним нашу систему доказательств, но это не страшно. Этот довод был бы совершенно верен, если бы недоказуемых высказываний было конечное число. На практике же может произойти следующее - после постулирования новой аксиомы вы наткнётесь на новое недоказуемое высказывание. Примете его в качестве ещё аксиомы - наткнётесь на третье. И так до бесконечности. Говорят, что дедуктика останется неполной . Мы можем также принять силовые меры, чтобы доказывающий алгоритм заканчивался через конечное число шагов с каким-то результатом для любого высказывания языка. Но при этом он начнёт врать - приводить к истине для неверных высказываний, или ко лжи - для верных. В таких случаях говорят, что дедуктика противоречива . Таким образом, ещё одна формулировка ТГН звучит так: «Существуют языки высказываний, для которых невозможна полная непротиворечивая дедуктика» - отсюда и название теоремы.

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

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

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

Примеры высказываний формальной арифметики:

и т.д. Теперь назовём «формулой со свободным параметром» (ФСП) строку, которая становится высказыванием, если в качестве этого параметра подставить в неё натуральное число. Примеры ФСП (с параметром ):

и т.д. Иными словами, ФСП эквивалентны функциям натурального аргумента с булевыми значением.

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

Перейдём теперь к наброску доказательства ТГН в такой формулировке:

• Для языка высказываний формальной арифметики не существует полной непротиворечивой дедуктики.

Доказывать будем от противного.

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

Проще говоря, алгоритм приводит к значению ИСТИНА тогда и только тогда, когда результат подстановки в ФСП её собственного номера в нашем списке даёт ложное высказывание.

Тут мы подходим к единственному месту, в котором я попрошу читателя поверить мне на слово.

Очевидно, что, при сделанном выше предположении, любой ФСП из можно сопоставить алгоритм, содержащий на входе натуральное число, а на выходе – булево значение. Менее очевидно обратное утверждение:

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

Пройдя это скользкое место, мы быстро добираемся до конца.

Итак, выше мы описали алгоритм . Согласно лемме, в которую я попросил вас поверить, существует эквивалентная ему ФСП. Она имеет какой-то номер в списке - скажем, . Спросим себя, чему равно ? Пусть это ИСТИНА. Тогда, по построению алгоритма (а значит, и эквивалентной ему функции ), это означает, что результат подстановки числа в функцию - ЛОЖЬ. Аналогично проверяется и обратное: из ЛОЖЬ следует ИСТИНА. Мы пришли к противоречию, а значит, исходное предположение неверно. Таким образом, для формальной арифметики не существует полной непротиворечивой дедуктики. Что и требовалось доказать.

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

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

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

• «Любая фраза китайского языка является верным высказыванием, если она содержится в цитатнике товарища Мао Дзе Дуна, и неверна, если не содержится».

Тогда соответствующий полный и непротиворечивый доказывающий алгоритм (его можно назвать «догматической дедуктикой») выглядит примерно так:

• «Листай цитатник товарища Мао Дзе Дуна, пока не найдёшь искомое высказывание. Если оно найдено, то оно верно, а если цитатник закончился, а высказывание не найдено, то оно неверно».

Здесь нас спасает то, что любой цитатник, очевидно, конечен, поэтому процесс «доказывания» неминуемо закончится. Таким образом, к языку догматических высказываний ТГН неприменима. Но мы ведь говорили о сложных языках, правда?

Теги: Добавить метки