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