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

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

Полное доказательство этой теоремы о неполноте немного выходит за рамки настоящей книги, поскольку в своем непосредственном виде оно занимает не меньше 30 страниц, но мы здесь приведем его набросок. Начнем с логической теории чисел. В этой теории существует единственная константа, 0, и единственная функция, 5 (функция определения преемника). В намеченной модели интерпретации этой теории 5(0) обозначает 1, 5(5(0) ) обозначает 2 и т.д., поэтому в рассматриваемом языке имеются имена для всех натуральных чисел. Кроме того, словарь языка включает функциональные символы +, χ и Expt (возведение в степень), а также обычное множество логических связок и кванторов. Прежде всего, следует отметить, что множество высказываний, которые могут быть записаны на этом языке, может быть пронумеровано. (Для этого достаточно представить себе, что определен алфавитный порядок символов, а затем в алфавитном порядке расположено каждое из множеств высказываний с длиной 1, 2 и т.д.) Затем можно обозначить каждое высказывание α уникальным натуральным числом #а (которое называется гёделевским номером). Это— самый важный момент доказательства; в нем утверждается, что теория чисел включает отдельное имя для каждого из ее собственных высказываний. Аналогичным образом, с помощью гёделевского номера G(P) можно пронумеровать каждое возможное доказательство Р, поскольку любое доказательство — это просто конечная последовательность высказываний.

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

• — не гёделевский номер доказательства высказывания, гёделевским номером которого является j, где в доказательстве используются только предпосылки из множества А.

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

Теперь применим следующий остроумный довод: предположим, что высказывание σ доказуемо из А; в таком случае высказывание σ ложно (поскольку в высказывании σ утверждается, что оно не может быть доказано). Но это означает, что имеется некоторое ложное высказывание, которое доказуемо из А, поэтому А не может состоять только из истинных высказываний, а это противоречит нашей предпосылке. Поэтому высказывание σ не доказуемо из А. Но именно это и утверждает о самом себе высказывание σ, а это означает, что σ — истинное высказывание.