Можно ли записать доказательства теорем о неполноте Курта Гёделя человеческим языком?

88
1
0
10 мая
04:17
май
2016

В общей форме не смогу, а частный случай - без проблем.

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

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

Если мы доказали первую теорему, то со второй уже проще, она на самом деле практически содержится в первой. Формулировка: "если формальная система непротиворечива, то в ней невыводима формула, содержательно утверждающая непротиворечивость этой системы". Построим формулу В, выражающую невозможность вывода в нашей системе какой-либо формулы вместе с её отрицанием (то есть, условие непротиворечивости нашей системы). Тогда утверждение первой теоремы выражается как В ⊃ А, где А — наша невыводимая формула из первой теоремы. Все рассуждения для доказательства первой теоремы могут быть выражены и проведены средствами нашей формальной системы (это суть "настоящего" доказательства первой теоремы), то есть в нашей системе выводима формула В ⊃ А. Тогда если выводима В, то выводима и А. Однако, согласно первой теореме Гёделя, если наша система непротиворечива, то А в ней невыводима. Следовательно, если наша система непротиворечива, то в ней невыводима и формула В.

1
0
Если вы знаете ответ на этот вопрос и можете аргументированно его обосновать, не стесняйтесь высказаться
Ответить самому
Выбрать эксперта