Gustavo Pineiro - У интуиции есть своя логика. Гёдель. Теоремы о неполноте.

— Шаг 2: Гёдель доказал, что пропозициональная функция

"у — код доказательства высказывания с кодом х"

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

"я — код доказательства высказывания с кодом r"

всегда финитно.

— Шаг 3: Гёдель определил пропозициональную функцию

"Не существует у, которое было бы кодом доказательства высказывания с кодом х".

— Шаг 4: Гёдель определил диагональную функцию. Если n — код пропозициональной функции Р(х), то d(n) — код Р(n). Следовательно, определение диагональной функции, которое основывается на механизме назначения кодов, синтаксическое.

— Шаг 5: На основе шагов 3 и 4 метод самореференции позволил Гёделю записать высказывание G:

"Не существует у, которое было бы кодом доказательства высказывания с кодом m",

код которого — само число m.

— Шаг 6: Теперь докажем синтаксически, что G недоказуемо. Предположим, от противного, что G доказуемо.

Тогда существует доказательство G, и ему соответствует код, к примеру k. Следовательно, высказывание

"k — код доказательство высказывания с кодом m"

истинное (поскольку m — код G, a k — код доказательства G) и, кроме того, финитное, поскольку можно проверить его истинность за конечное число шагов (можно проверить алгоритмически, что k — действительно код доказательства G). Так как оно финитное и истинное, то, по гипотезе, высказывание доказуемо. Тогда одно из правил логики позволяет нам сделать вывод, что также доказуемо высказывание

"Существует у, являющееся кодом доказательства высказывания с кодом т".

Схема доказательства того, что G недоказуемо.

Мы исходим из предположения, что G доказуемо. Стрелки показывают последовательные выводы, которые получаются из этого предположения, пока мы не приходим к заключению, что отрицание G также доказуемо. Это содержит противоречие, следовательно G не может быть доказуемо.

Если сравнить последнее высказывание с тем, как мы формулировали G, оказывается ясным, что оно соответствует не-G. Получается, мы говорим, что G и не-G одновременно доказуемы. Мы пришли к противоречию. Оно возникает из предположения, что G доказуемо, следовательно делаем вывод: G недоказуемо (см. схему на предыдущей странице).

— Шаг 7: Теперь докажем, что не-G также недоказуемо. Снова сделаем это от противного. Предположим, что не-G доказуемо, и придем к противоречию. Так как множество аксиом непротиворечиво, если не-G доказуемо, то G не может быть доказуемым.

Когда мы показали, что высказывание не-G недоказуемо, мы основывались на том факте, что если для свойства Р верно

высказывание "1 не удовлетворяет свойству Р" доказуемо,

высказывание "2 не удовлетворяет свойству Р" доказуемо,

высказывание "3 не удовлетворяет свойству Р" доказуемо

...и так далее,

то высказывание "существует некое х, удовлетворяющее свойству Р" недоказуемо. Но так ли это? Сначала рассмотрим этот вопрос семантически. Предположим, что Р — арифметическое свойство, для которого выполняется:

высказывание "1 не удовлетворяет свойству Р" истинно,

высказывание "2 не удовлетворяет свойству Р" истинно,

высказывание "3 не удовлетворяет свойству Р" истинно

...и так далее,

то есть для любого числа л справедливо, что свойство Р не выполняется. Тогда ясно, что высказывание "существует некоторый х, для которого выполняется свойство Р" ложно (поскольку мы сказали, что ни для 1, ни для 2, ни для 3 и так далее свойство не выполняется). Но оно ложно, если мы говорим о мире натуральных чисел, и может быть истинным, когда говорим о другом мире. Например, если свойство Р — это "х² = 2", а мы говорим о мире чисел, образованных на основе √2, то для 1 свойство не выполняется, как и для 2, 3 и так далее. Но для √2 свойство Р выполняется. Что же происходите синтаксической точки зрения? Рассмотрим снова свойство Р, но теперь предположим, что:

"1 не удовлетворяет свойству Р" доказуемо,

"2 не удовлетворяет свойству Р" доказуемо,

"3 не удовлетворяет свойству Р" доказуемо

...и так далее.