270. Теорема Гёделя

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

В 1931 г. Курт Гёдель совершил поразительное открытие. Он установил, что математическую истину в некотором смысле нельзя формализовать полностью. Гёдель доказал, что в математической системе, принадлежащей широкому классу систем, всегда найдется утверждение, недоказуемое (то есть невыводимое из аксиом системы), несмотря на свою истинность! Следовательно, ни одной аксиоматической системы, сколь бы остроумно она ни была устроена, не достаточно для доказательства всех математических истин. Гёдель впервые доказал свою теорему для системы «Principia Mathematica» Уайтхеда и Расселла, но предложенное им доказательство, как я уже говорил, допускает перенос и на многие другие системы. Во всех этих системах существует вполне определенное множество выражений, называемых предложениями, которые подразделяются на истинные и ложные. Некоторые истинные предложения приняты за аксиомы системы. Точный перечень правил вывода позволяет доказывать (выводить из аксиом) одни предложения и опровергать другие. Помимо предложений система содержит имена различных множеств (целых и положительных) чисел. Любое множества чисел, наделенное в рассматриваемой системе именем, можно назвать именуемым, или определимым, множеством системы (в предыдущей задаче такие множества скрывались под псевдонимом «учтенные множества»). Весьма существенно, что все предложения можно перенумеровать, а все определимые множества перечислить по порядку. Это означает, что математическая система удовлетворяет условиям E1, E2, C и H нашей задачи. (Номер, присваиваемый каждому предложению, — в задаче мы называли его просто номером — в математической логике известен подназванием гёделевого номера предложения.) Доказать, что система удовлетворяет условиям C и H, очень просто. Доказательство того, что система удовлетворяет условиям E1 и E2, в принципе несложно[12], но довольно громоздко. Коль скоро доказано, что система удовлетворяет всем четырем условиям, они позволяют построить предложение, которое истинно, но недоказуемо (невыводимо) в данной системе.

Это предложение можно представлять себе как некоторое предложение X, содержащее утверждение о своей недоказуемости. Такое предложение действительно должно быть истинно, но недоказуемо (подобно тому как житель острова G, утверждавший, что он непризнанный рыцарь, действительно был рыцарем, но не был признанным рыцарем). Возможно, вы спросите: но если известно, что предложение X (содержащее утверждение о своей недоказуемости) истинно, то почему бы не принять его за новую аксиому? Разумеется, мы можем пополнить список аксиом системы еще одной аксиомой, но расширенная система также будет удовлетворять условиям E1, E2, C и H. Следовательно, в ней найдется другое предложение X1, которое будет истинным, но недоказуемым в расширенной системе. Таким образом, хотя расширенная система позволяет доказать больше истинных предложений, чем старая, тем не менее и в ней доказать все истинные предложения невозможно.

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

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