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

Теорема утверждает следующее.

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

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

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

______________________________________________________

Th Гёделя

Любое ИП содержащее А₀ не является полным.

Следствие 1

Существуют утверждения верные для натуральных чисел, которые нельзя доказать.

Следствие 2

Множество номеров тождественно истинных формул даже не являющимся арифметическим, т.е. не существует единого алгоритма для проверки тождественности истинности арифметических формул средствами самого исчисления А_0.

Следствие 3

Th Райса

Пусть дано некоторое непустое семейство n-местных частично рекурсивных функций не совпадающих с совокупностью n-местных ЧСФ. Тогда множество номеров этих функций не являются рекурсивным, т.е. не существует алгоритм который по номеру этой функции определял принадлежность этой функции.

Вывод: по тексту программы нельзя сказать о свойствах функций вычисляемой этой программой.