Последняя теорема геделя. Теорема Гёделя о неполноте формальной арифметики. Отдаленное будущее — это отдаленное прошлое

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

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

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

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

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

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

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

Теоремы Гёделя о неполноте - две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой достаточно сильной теории первого порядка .

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

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

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

Утверждение первой теоремы Гёделя о неполноте можно сформулировать следующим образом:

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

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

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

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

Набросок доказательства

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

Выражения формальной системы являются, если смотреть извне, конечными последовательностями примитивных символов (переменных, логических постоянных, и скобок или точек) и нетрудно строго уточнить какие последовательности примитивных символов являются формулами, а какие нет. Аналогично, с формальной точки зрения, доказательства есть ни что иное, как конечные последовательности формул (со строго заданными свойствами). Для математического рассмотрения не имеет значения, какие объекты взять в качестве примитивных символов, и мы решаем использовать для этих целей натуральные числа. Соответственно, формула является конечной последовательностью натуральных чисел, вывод формулы - конечной последовательностью конечных последовательностей натуральных чисел. Математические понятия (утверждения) таким образом становятся понятиями (утверждениями) о натуральных числах или их последовательностях, и, следовательно, сами могут быть выражены в символизме системы PM (по крайней мере частично). Может быть показано, в частности, что понятия "формула", "вывод", "выводимая формула" определимы внутри системы PM, то есть можно восстановить, например, формулу F (v ) в PM с одной свободной переменной v (тип которой - числовая последовательность) такую, что F (v ), в интуитивной интерпретации, означает: v - выводимая формула. Теперь построим неразрешимое предложение системы PM, то есть предложение A , для которого ни A , ни не-A невыводимы, следующим образом:

Формулу в PM с точно одной свободной переменной, тип которой натуральное число (класс классов), будем называть класс-выражением. Упорядочим класс-выражения в последовательность каким-либо образом, обозначим n -е через R (n ), и заметим, что понятие "класс-выражение", также как и отношение упорядочения R можно определить в системе PM. Пусть α будет произвольным класс-выражением; через [α;n ] обозначим формулу, которая образуется из класс-выражения α заменой свободной переменной на символ натурального числа n . Тернарное отношение x = [y ;z ] тоже оказывается определимым в PM. Теперь мы определим класс K натуральных чисел следующим образом:

n ∈ K ≡ ¬Bew[R (n );n ] (*)

(где Bew x означает: x - выводимая формула). Так как все понятия, встречающиеся в этом определении, можно выразить в PM, то это же верно и для понятия K , которое из них строится, то есть имеется такое класс-выражение S , что формула [S ;n ], интуитивно интерпретируемая, обозначает, что натуральное число n принадлежит K . Как класс-выражение, S идентична некоторому определенному R (q ) в нашей нумерации, то есть

S = R (q )

выполняется для некоторого определенного натурального числа q . Теперь покажем, что предложение [R (q );q ] неразрешимо в PM. Так, если предложение [R (q );q ] предполагается выводимым, тогда оно оказывается истинным, то есть, в соответсвии со сказанным выше, q будет принадлежать K , то есть, в соответствии с (*), ¬Bew[R (q );q ] будет выполняться, что противоречит нашему предположению. С другой стороны, если бы отрицание [R (q );q ] было выводимым, то будет иметь место ¬ n ∈ K , то есть Bew[R (q );q ] будет истинным. Следовательно, [R (q );q ] вместе со своим отрицанием будет выводимо, что снова невозможно.

Полиномиальная форма

Для каждой непротиворечивой теории T можно указать такое целое значение параметра K, что уравнение (θ + 2z − b 5) 2 + (u + t θ − l ) 2 + (y + m θ − e ) 2 + (n − q 16) 2 + ((g + e q 3 + l q 5 + (2(e − z λ)(1 + g ) 4 + λb 5 + λb 5 q 4)q 4)(n 2 − n ) + (q 3 − b l + l + θλq 3 + (b 5 − 2)q 5)(n 2 − 1) − r ) 2 + (p − 2w s 2 r 2 n 2) 2 + (p 2 k 2 − k 2 + 1 − τ 2) 2 + (4(c − k s n 2) 2 + η − k 2) 2 + (r + 1 + h p − h − k ) 2 + (a − (w n 2 + 1)r s n 2) 2 + (2r + 1 + φ − c ) 2 + (b w + c a − 2c + 4αγ − 5γ − d ) 2 + ((a 2 − 1)c 2 + 1 − d 2) 2 + ((a 2 − 1)i 2 c 4 + 1 − f 2) 2 + (((a + f 2 (d 2 − a )) 2 − 1)(2r + 1 + j c ) 2 + 1 − (d + o f ) 2) 2 + (((z + u + y ) 2 + u ) 2 + y − K ) 2 = 0 не имеет решений в неотрицательных целых числах, но этот факт не может быть доказан в теории T. Более того, для каждой непротиворечивой теории множество значений параметра K, обладающих таким свойством, бесконечно и алгоритмически неперечислимо .

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

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

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

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

Набросок доказательства

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

Примечания

См. также

Ссылки

В. А. Успенский Теорема Гёделя о неполноте . - М.: Наука, 1982. - 110 с. - (Популярные лекции по математике).
Академик Ю. Л. Ершов «Доказательность в математике» , программа А. Гордона от 16 июня 2003 года
А. Б. Сосинский Теорема Геделя // летняя школа «Современная математика» . - Дубна: 2006.
П. Дж. Коэн Об основаниях теории множеств // Успехи математических наук . - 1974. - Т. 29. - № 5(179). - С. 169–176.
М. Кордонский Конец истины . - ISBN 5-946448-001-04
В. А. Успенский Теорема Гёделя о неполноте и четыре дороги, ведущие к ней // летняя школа «Современная математика» . - Дубна: 2007.
Зенкин А. А. Принцип разделения времени и анализ одного класса квазифинитных правдоподобных рассуждений (на примере теоремы Г. Кантора о несчётности) // ДАН . - 1997. - Т. 356. - № 6. - С. 733-735.
Чечулин В. Л. О кратком варинте доказательства теорем Гёделя // «Фундаментальные проблемы математики и информационных наук», материалы XXXIV Дальневосточной Математической Школы-семинара имени академика Е.В. Золотова . - Хабаровск, Россия: 2009. - С. 60-61.

Wikimedia Foundation . 2010 .

Смотреть что такое "Теоремы Гёделя о неполноте" в других словарях:

У этого термина существуют и другие значения, см. Теорема Гёделя. Теорема Гёделя о неполноте и вторая теорема Гёделя[ 1] две теоремы математической логики о принципиальных ограничениях формальной арифметики и, как следствие, всякой… … Википедия

Теоремы Гёделя о неполноте две теоремы математической логики о неполноте формальных систем определённого рода. Содержание 1 Первая теорема Гёделя о неполноте 2 Вторая теорема Гёделя о неполноте … Википедия

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

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

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

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

Theoretical Computer Science 130,1994, pp.273-238.

Пожалуй, теорема Геделя о неполноте является воистину уникальной. Уникальной в том, что на нее ссылаются, когда хотят доказать "все на свете" - от наличия богов до отсутствия разума. Меня всегда интересовал более "первичный вопрос" - а кто из ссылающихся на теорему о неполноте смог-бы не только сформулировать ее, но и доказать? Я публикую данную статью по той причине, что в ней изложена вполне доступная формулировка теоремы Геделя. Рекомендую предварительно ознакомиться со статьей Туллио Редже Курт Гедель и его знаменитая теорема

Вывод о невозможности универсального критерия истины является

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

теоремы Геделя о неразрешимости с его собственной теорией истины, согласно

которому универсального критерия истины не может быть даже для относительно

узкой области теории чисел, а значит, и для любой науки, использующей

арифметику. Естественно, что этот результат применим a fortiori к понятию истины

в любой нематематической области знания, в которой широко

используется арифметика.

Карл Поппер

Успенский Влaдимиp Aндpеевич pодился 27 ноябpя 1930 г. в г. Москве. Окончил мехaнико-мaтемaтический фaкультет МГУ (1952). Доктоp физико-мaтемaтических нaук (1964). Пpофессоp, заведующий кaфедpой мaтемaтической логики и теоpии aлгоpитмов мехaнико-мaтемaтического фaкультетa (1966). Читает курсы лекций "Введение в математическую логику", "Вычислимые функции", "Теорема Геделя о полноте". Подготовил 25 кандидатов и 2 докторов наук

1. Постановка задачи

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

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

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

1.1.1. Алфавит

Под алфавитом мы понимаем конечный набор элементарных знаков (то есть - вещей, которые невозможно разбить на составные части). Эти знаки называются буквами алфавита. Под словом алфавита мы понимаем конечную последовательность букв. Например, обыкновенные слова в английском языке (включая имена собственные) являются словами 54-хбуквенного алфавита (26 маленьких букв, 26 прописных, тире и апостроф). Другой пример - натуральные числа в десятичной записи являются словами 10-тибуквенного алфавита, чьи буквы - знаки: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Для обозначения алфавитов мы будем использовать обыкновенные заглавные буквы. Если L - алфавит, то L? будет обозначать множество всех слов алфавита L, - слов, образованных из его букв. Мы предположим, что любой язык имеет свой алфавит, так что все выражения этого языка (т. е. - имена различных объектов, утверждения относительно этих объектов и т.д.) являются словами этого алфавита. Например, любое предложение английского языка, равно как и любой текст, написанный по-английски, может рассматриваться как слово расширенного алфавита из 54-х букв, включающего также знаки пунктуации, междусловный пробел, знак красной строки и, возможно, некоторые другие полезные знаки. Предполагая, что выражения языка являются словами некоторого алфавита, мы, таким образом, исключаем из рассмотрения "многослойные" выражения типа???f(x)dx. Однако, это ограничение не слишком существенно, так как любое подобное выражение, при использовании подходящих конвенций, может быть "растянуто" в линейную форму. Любое множество М, содержащееся в L? называется словным множеством алфавита L. Если мы просто говорим, что М - словное множество, то мы подразумеваем, что оно является словом некоторого алфавита. Теперь сформулированное выше предположение о языке может быть перефразировано следующим образом: в любом языке любое множество выражений является словным множеством.

1.1.2. Множество истинных утверждений

Мы предположим, что нам задано подмножество Т множества L? (где L алфавит некоторого рассматриваемого нами языка), которое называется множеством "истинных утверждений" (или просто "истин"). Переходя непосредственно к подмножеству Т, мы опускаем следующие промежуточные шаги рассуждения: во-первых, какие именно слова алфавита L являются корректно образованными выражениями языка, то есть - имеющими определенное значение в нашей интерпретации этого языка (например, 2+3, х+3, х=у, х=3, 2=3, 2=2 являются корректно образованными выражениями, в то время как выражения типа +=х таковыми не являются); во-вторых, какие именно выражения являются формулами, т.е. могут зависеть от параметра (например, х=3, х=у, 2=3, 2=2); в третьих, какие именно из формул являются закрытыми формулами, т.е. утверждениями, не зависящими параметров (например, 2=3, 2=2); и наконец, какие именно закрытые формулы являются истинными утверждениями (например, 2=2).

1.1.3. Фундаментальная пара языка

1.2. "Недоказуемые"

"Недоказуемые" значит не имеющие доказательства.

1.3. Доказательство

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

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

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

(1) У нас имеются алфавит L (алфавит языка) и алфавит Р (алфавит доказательства).

(2) Нам дано множество Р, являющееся подмножеством Р?, и чьи элементы называются "доказательствами". В дальнейшем мы будем предполагать, что также у нас имеется алгоритм, который позволяет нам определить является ли произвольное слово алфавита Р элементом множества Р, то есть доказательством, или нет.

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

Тройка, удовлетворяющая условиям (1)-(3) называется дедуктивной системой над алфавитом L.

Для читателя, знакомого с обычным способом определения "доказательства" в терминах "аксиома" и "правило вывода", мы сейчас поясним, как этот метод может рассматриваться в качестве специального случая определения, данного в параграфе 1.3.2. То есть - доказательство обычно определяется как последовательность таких выражений языка, каждое из которых является либо аксиомой, либо ранее полученным из уже существующих утверждений при помощи одного из правил вывода. Если мы добавим новое слово * к алфавиту нашего языка, то мы сможем записать такое доказательство в виде слова составленного при помощи полученного в результате такой модификации алфавита: последовательность выражений становится словом C1*C2*...*Cn. В таком случае, функция, определяющая, что именно было доказано, своим значением имеет часть этого слова, стоящую сразу за последней в последовательности буквой *. Алгоритм, существование которого требуется в части 1.3.2. определения, может легко быть сконструирован, как только мы точно определим какое-либо из принятых значений слов "аксиома" и "правила вывода".

1.4.Попытки точной формулировки теоремы о неполноте

1.4.1. Первая попытка

"При определенных условиях для фундаментальной пары языка алфавита L и дедуктивной системы над L - всегда существует слово в Т, не имеющее доказательства". Этот вариант все еще выглядит смутным. В частности, мы могли бы запросто придумать сколько угодно дедуктивных систем, имеющих очень немного доказуемых слов. Например, в пустой дедуктивной системе (где Р = ?) совсем нет слов, у которых были бы доказательства.

1.4.2. Вторая попытка

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

"При определенных условиях относительно фундаментальной пары не существует такой дедуктивной системы, в которой бы каждое слово из Т имело бы доказательство".

Однако такое утверждение, очевидно, ложно, так как необходимо лишь взять такую дедуктивную систему, в которой Р = L, Р = Р? и?(р) = р для всех р из Р?; тогда каждое слово из L? является тривиально доказуемым. Следовательно, нам нужно принять некоторое ограничение на то, какими дедуктивными системами мы пользуемся.

1.5. Непротиворечивость

Было бы вполне естественно потребовать, что только "истинные утверждения", то есть только слова из Т, могут быть доказаны. Мы будем говорить, что дедуктивная система является непротиворечивой относительно фундаментальной пары, если?(Р)?Т. Во всех последующих рассуждениях нас будут интересовать только такие непротиворечивые дедуктивные системы. Если же нам задан язык, то было бы чрезвычайно соблазнительно найти такую непротиворечивую дедуктивную систему, в которой каждое истинное утверждение имело бы доказательство. Интересующий нас вариант теоремы Геделя в точности утверждает, что при определенных условиях относительно фундаментальной пары, невозможно найти такую дедуктивную систему.

1.6. Полнота

Говорится, что дедуктивная система полна относительно фундаментальной пары, при условии если?(Р)?Т. Тогда наша формулировка теоремы о неполноте приобретает следующий вид:

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

Признаюсь, что саму идею рассмотрения вопроса о существовании бога с этой стороны я вычитал у Анатолия Александровича Вассермана:
http://ru.wikipedia.org/wiki/%D0%90%D0%BD%D0%B0%D1%82%D0%BE%D0%BB%D0%B8%D0%B9_%D0%90%D0%BB%D0%B5%D0%BA%D1%81%D0%B0%D0%BD%D0%B4%D1%80%D0%BE%D0%B2%D0%B8%D1%87_%D0%92%D0%B0%D1%81%D1%81%D0%B5%D1%80%D0%BC%D0%B0%D0%BD#.D0.A0.D0.B5.D0.BB.D0.B8.D0.B3.D0.B8.D0.BE.D0.B7.D0.BD.D1.8B.D0.B5_.D0.B2.D0.B7.D0.B3.D0.BB.D1.8F.D0.B4.D1.8B

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

Рассмотрим с этих позиций религиозные верования. Важнейшая аксиома религии: "бог существует и является первопричиной всего сущего".
Теперь вспомним одну из важнейших математических теорем, теорему Гёделя.
http://elementy.ru/trefil/21142
Слабая теорема Гёделя: "Любая формальная система аксиом содержит неразрешенные предположения" или "если система аксиом полна, то она противоречива."
Сильная теорема Гёделя: "Логическая полнота (или неполнота) любой системы аксиом не может быть доказана в рамках этой системы. Для ее доказательства или опровержения требуются дополнительные аксиомы (усиление системы)."

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

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

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

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

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

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

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

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

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

P.S. Стоит отметить еще одну любопытнейшую вещь, любопытную уже для физиков. В данном определении бога ничего не говорится о его разумности. То есть можно было бы добавить "бог - разумная причина всего сущего", однако это сужение определения, которое изначально и не требуется для доказательства. Без разумности понятие "бога" можно легко заменить на "сингулярность и большой взрыв - причина всего сущего". И ответ будет тот же самый: сингулярность и большой взрыв - не первопричина всего сущего.
Проведя еще большее абстрагирование можно сказать, что ни одно явление или причина не могут являться первопричиной всего сущего, то есть первопричины не существует в принципе. Рассуждая в рамках любой аксиоматики можно прийти к выводу, что первопричины всего не существует. Говоря совсем просто, до каких бы основ мы ни познали вселенную, всегда останутся вопросы в духе: "откуда появился большой взрыв, откуда появилась сингулярность, откуда появилась пульсирующая вселенная, откуда появилась мультивселенная, почему вселенная существует всегда?" и т.п. Первопричину всего не возможно найти в принципе, она не содержится ни в одном объекте, явлении или понятии. Следовательно для человека это эквивалентно ее отсутствию. Теоретически можно предположить существование стороннего наблюдателя за пределами нашей вселенной, который даст ответ на вопрос, откуда все взялось (та самая дополнительная аксиома, расширение в теореме Гёделя), однако тогда возникнет вопрос, откуда взялся сторонний наблюдатель, его вселенная и первопричина всего этого.

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!