Схема доказательства первой теоремы Гёделя о неполноте

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

В этой статье слово «число» относится к натуральному числу (включая 0). Ключевое свойство, которым обладают эти числа, заключается в том, что любое натуральное число можно получить, начав с числа 0 и прибавляя 1 конечное число раз.

Гипотезы теории

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

• Постоянный символ 0 для нуля.
• Символ унарной функции S для последующей операции и два символа двоичной функции + и × для сложения и умножения.
• Три символа для логической конъюнкции ∧ , дизъюнкции ∨ и отрицания ¬ .
• Два символа для универсальных ∀ и ∃ кванторов экзистенциальных .
• Два символа для бинарных отношений, = и < , обозначают равенство и порядок (меньше).
• Два символа для левых ( и правых ) круглых скобок для установления приоритета кванторов.
• Один символ переменной x и отличительный символ * , который можно использовать для создания дополнительных переменных формы x* , x** , x*** ,...

Это язык арифметики Пеано . Правильно составленная формула — это последовательность этих символов, которая сформирована таким образом, чтобы иметь четкое прочтение как математическая формула. Таким образом, x = SS 0 является хорошо сформированным, а x = ∀+ не является хорошо сформированным. Теория — это набор правильно составленных формул без свободных переменных .

Теория непротиворечива , если не существует формулы F такой, что и F , и ее отрицание доказуемы. ω-согласованность — более сильное свойство, чем непротиворечивость. Предположим, что F ( x ) — формула с одной свободной переменной x . Чтобы быть ω-непротиворечивой, теория не может одновременно доказать ∃ m F ( m ) и одновременно доказать ¬ F ( n ) для каждого натурального числа n .

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

Схема доказательства

Для упрощенной схемы доказательства см. теоремы Гёделя о неполноте.

Эскиз здесь разбит на три части. В первой части каждой формуле теории присваивается номер, известный как число Гёделя, таким образом, чтобы можно было эффективно восстановить формулу по этому числу. Эта нумерация расширена и охватывает конечные последовательности формул. Во второй части определенная формула PF ( x , y ) строится для любых двух чисел n и m такая, что PF ( n , m ) выполняется тогда и только тогда, когда n представляет собой последовательность формул, которая представляет собой доказательство формулы что представляет собой m . В третьей части доказательства мы строим самореференциальную формулу, которая неформально говорит: «Я недоказуема», и доказываем, что это предложение не является ни доказуемым, ни опровергнутым в рамках теории.

Важно отметить, что все формулы в доказательстве могут быть определены примитивно-рекурсивными функциями , которые сами могут быть определены в первого порядка арифметике Пеано .

нумерация Гёделя

Первым шагом доказательства является представление (корректных) формул теории и конечных списков этих формул в виде натуральных чисел. Эти числа называются числами Гёделя формул.

Начните с присвоения натурального числа каждому символу языка арифметики, аналогично тому, как код ASCII присваивает уникальное двоичное число каждой букве и некоторым другим символам. В этой статье будет использовано следующее задание, очень похожее на то, которое Дуглас Хофштадтер использовал в своей работе «Гёдель, Эшер, Бах» :

Число Символ Значение 666 0 ноль 123 С функция-преемник 111 = отношение равенства 212 < меньше, чем отношение 112 + оператор сложения 236 × оператор умножения 362 ( левая скобка 323 ) правая скобка

Число Символ Значение 262 х имя переменной 163 * звезда (используется для создания большего количества переменных) 333 ∃ квантор существования 626 ∀ универсальный квантор 161 ∧ логичный и 616 ∨ логичный или 223 ¬ логично нет

Число Гёделя формулы получается путем объединения чисел Гёделя каждого символа, составляющего формулу. Числа Гёделя для каждого символа разделяются нулем, поскольку по замыслу ни одно число Гёделя в символе не содержит 0 . Следовательно, любая формула может быть правильно восстановлена ​​по ее числу Гёделя. Пусть G ( F ) число Гёделя формулы F. обозначает

Учитывая приведенную выше нумерацию Гёделя, предложение, утверждающее, что сложение коммутирует , ∀ x ∀ x * ( x + x * = x * + x ), переводится как число:

626 0 262 0 626 0 262 0 163 0 362 0 262 0 112 0 262 0 163 0 111 0 262 0 163 0 112 0 262 0 323

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

111 0 626 0 112 0 262

переводится как « = ∀ + x », что некорректно.

Поскольку каждое натуральное число можно получить, применяя последующую операцию S к 0 конечное число раз, каждое натуральное число имеет свое собственное число Гёделя. Например, число Гёделя, соответствующее 4, SSSS 0 , равно:

123 0 123 0 123 0 123 0 666 .

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

Крайне важно, чтобы формальная арифметика была способна доказать минимальный набор фактов. В частности, он должен быть в состоянии доказать, что каждое число m имеет число Гёделя G ( m ) . Второй факт, который должна доказать теория, состоит в том, что для любого гёделева числа G ( F ( x )) формулы F ( x ) с одной свободной переменной x и любым номером m существует гёделево число формулы F ( m ). получается путем замены всех вхождений G ( x ) в G ( F ( x )) на G ( m ) , и что это второе число Гёделя может быть эффективно получено из числа Гёделя G ( F ( x )) из F ( x ) как функция G ( x ) . Чтобы убедиться, что это действительно возможно, обратите внимание, что, учитывая число Гёделя F ( x ) , можно воссоздать исходную формулу F ( x ) , заменить x на m , а затем найти число Гёделя G ( F ( m )) полученной формулы F ( m ) . Это единая процедура.

Отношение доказуемости

Тогда правила вывода могут быть представлены в виде бинарных отношений на числах Гёделя списков формул. Другими словами, предположим, что существует правило вывода D ₁ , по которому можно перейти от формул S ₁ , S ₂ к новой формуле S . Тогда отношение R _1, соответствующее этому правилу вывода, говорит, что n связано с m (другими словами, имеет место n R ₁ m ), если n — это число Гёделя списка формул, содержащих S ₁ и S ₂ , а m — это число Гёделя. номер списка формул, содержащих S ₁ , S ₂ и S . можно эффективно определить, Поскольку каждое правило вывода является конкретным, для любых натуральных чисел n и m связаны ли они соотношением.

Второй этап доказательства — использовать описанную выше нумерацию Гёделя, чтобы показать, что понятие доказуемости можно выразить на формальном языке теории. Предположим, что в теории есть правила вывода: D ₁ , D ₂ , D ₃ , ... . Пусть R ₁ , R ₂ , R ₃ , ... будут их соответствующими отношениями, как описано выше.

Каждое доказуемое утверждение либо само по себе является аксиомой, либо может быть выведено из аксиом путем конечного числа применений правил вывода. Доказательство формулы S само по себе представляет собой строку математических утверждений, связанных определенными отношениями (каждое из них является либо аксиомой, либо связано с предыдущими утверждениями правилами дедукции), где последним утверждением является S . Таким образом, можно определить число Гёделя доказательства. Более того, можно определить форму утверждения Доказательство ( x , y ) , которая для каждых двух чисел x и y доказуема тогда и только тогда, когда x — число Гёделя доказательства утверждения S и y = G ( S ) .

Доказательство ( x , y ) на самом деле является арифметическим соотношением, таким же, как « x + y = 6 », хотя и (намного) более сложным. При таком отношении R ( x , y ) любых двух конкретных чисел n и m либо формула R ( m , n ) , либо ее отрицание ¬R для ( m , n ) доказуема , но не то и другое. Это потому, что связь между этими двумя числами можно просто «проверить». Формально это можно доказать методом индукции, где все эти возможные отношения (число которых бесконечно) строятся одно за другим. Детальное построение формулы Доказательство существенно использует предположение об эффективности теории; без такого предположения построить эту формулу было бы невозможно.

Самореферентная формула

Для каждого числа n и каждой формулы F ( y ) , где y — свободная переменная, мы определяем q ( n , G ( F )) , отношение между двумя числами n и G ( F ) , такое, что оно соответствует утверждению « n не является числом Гёделя доказательства F ( G ( F )) ». Здесь F ( G ( F )) можно понимать как F с собственным числом Гёделя в качестве аргумента.

что q принимает в качестве аргумента G ( F ) , число Гёделя F. Обратите внимание , Чтобы доказать либо q ( n , G ( F )) , либо ¬ q ( n , G ( F )) , необходимо выполнить теоретико-числовые операции над G ( F ), которые отражают следующие шаги: декодировать число G ( F ) в формулу F , замените все вхождения y в F на число G ( F ) , а затем вычислите число Гёделя полученной формулы F ( G ( F )) .

Обратите внимание, что для каждого конкретного числа n и формулы F ( y ) q ( n , G ( F )) представляет собой прямое (хотя и сложное) арифметическое отношение между двумя числами n и G ( F ) , основанное на отношении PF , определенном ранее. Далее, q ( n , G ( F )) доказуемо, если конечный список формул, закодированных , не является доказательством F ( G ( F )) и ¬q n ( n , G ( F )) доказуемо, если конечный список формул, закодированных n, является доказательством F ( G ( F )) . Для любых чисел n и G ( F ) либо q ( n , G ( F )) либо ¬ q ( n , G ( F )) доказуемо (но не оба).

Любое доказательство F ( G ( F )) может быть закодировано гёделевым числом n , так что q ( n , G ( F )) не выполняется. Если q ( n , G ( F )) верно для всех натуральных чисел n отсутствует , то доказательство F ( G ( F )) . Другими словами, ∀ y q ( y , G ( F )) , формула о натуральных числах, соответствует «нет доказательства F ( G ( F )) ».

Теперь определим формулу P ( x ) = ∀ y q ( y , x ) , где x — свободная переменная. Сама формула P имеет число Гёделя G ( P ), как и каждая формула.

В этой формуле есть свободная переменная x . Предположим, мы заменим его на G ( F ) , число Гёделя формулы F ( z ) , где z — свободная переменная. Тогда P ( G ( F )) = ∀ y q ( y , G ( F )) соответствует «нет доказательства F ( G ( F )) », как мы видели.

Рассмотрим формулу P ( G ( P )) = ∀ y q ( y , G ( P )) . Эта формула относительно числа G ( P ) соответствует «нет доказательства P ( G ( P )) ». Здесь мы имеем самореферентную особенность, которая имеет решающее значение для доказательства: формула формальной теории, которая каким-то образом связана с ее собственной доказуемостью в рамках этой формальной теории. Очень неформально P ( G ( P )) говорит: «Я недоказуем».

что ни формула P ( G ( P )) ни ее отрицание ¬P Теперь мы покажем , ( G ( P )) не доказуемы.

Предположим, что P ( G ( P )) = ∀ y q ( y , G ( P )) доказуемо. Пусть n — число Гёделя доказательства P ( G ( P )) . Тогда, как было замечено ранее, формула ¬ q ( n , G ( P )) доказуема. Доказательство как ¬ q ( n , G ( P )) и ∀ y q ( y , G ( P )) нарушает непротиворечивость формальной теории. Поэтому мы заключаем, что P ( G ( P )) недоказуемо.

Рассмотрим любое число n . Предположим, что ¬ q ( n , G ( P )) доказуемо. Тогда n должно быть числом Гёделя доказательства P ( G ( P )) . Но мы только что доказали, что P ( G ( P )) недоказуемо. Поскольку либо ( n , G ( P ) ) или ¬q должны быть доказуемы ( n , G ( P )) , мы заключаем, что для всех натуральных чисел n ( q q n , G ( P )) доказуемо.

Предположим, что отрицание P ( G ( P )) , ¬ P ( G ( P )) = ∃ x ¬ q ( x , G ( P )) доказуемо. Доказательство как ∃ x ¬ q ( x , G ( P )) , так и q ( n , G ( P )) для всех натуральных чисел n нарушает ω-непротиворечивость формальной теории. Таким образом, если теория ω-непротиворечива , ¬ P ( G ( P )) недоказуема.

Мы набросали доказательство, показывающее, что:

Для любой формальной, рекурсивно перечислимой (т.е. эффективно порожденной) теории арифметики Пеано ,

если она непротиворечива , то существует недоказуемая формула (на языке этой теории).

если она ω-непротиворечива , то существует формула, такая, что и она, и ее отрицание недоказуемы.

Истинность предложения Гёделя

Доказательство только что обрисованной теоремы Гёделя о неполноте является теоретико-доказательным (также называемым синтаксическим ), поскольку оно показывает, что если существуют определенные доказательства (доказательство P ( G ( P )) или его отрицание), то ими можно манипулировать, чтобы получить доказательство. противоречия. Это не касается того, является ли P ( G ( P )) «истинным», а только вопрос о том, доказуемо ли оно. Истина — это теоретико-модельное или семантическое понятие, и она не эквивалентна доказуемости, за исключением особых случаев.

Более детально анализируя ситуацию приведенного доказательства, можно получить вывод об истинности P ( G ( P )) в стандартной модели. $\mathbb {N}$ натуральных чисел. Как только что видно, q ( n , G ( P )) доказуемо для каждого натурального числа n и, таким образом, верно в модели $\mathbb {N}$. Поэтому в рамках этой модели

$P(G(P))=\forall y\,q(y,G(P))$

держит. Это то, к чему обычно относится утверждение « P ( G ( P )) истинно» — предложение истинно в предполагаемой модели. Гёделя Однако это верно не для каждой модели: если бы это было так, то по теореме о полноте это было бы доказуемо, что, как мы только что видели, не так.

Краткое доказательство Булоса

Джордж Булос (1989) значительно упростил доказательство Первой теоремы, если согласиться с тем, что эта теорема эквивалентна:

«Не существует алгоритма M , выходные данные которого содержат все истинные арифметические предложения и не содержат ложных».

«Арифметика» относится к арифметике Пеано или Робинсона , но доказательство не требует каких-либо особенностей ни той, ни другой, молчаливо предполагая, что эти системы позволяют знакам «<» и «×» иметь свои обычные значения. Булос доказывает теорему примерно на двух страницах. Его доказательство использует язык логики первого порядка , но не использует никаких фактов о связках или кванторах . Областью обсуждения являются натуральные числа . Предложение Гёделя основано на парадоксе Берри .

Пусть [ n ] сокращает n последовательных применений функции -преемника , начиная с 0 . Затем Булос утверждает (детали лишь схематически показаны), что существует определенный предикат Cxz , который оказывается истинным тогда и только тогда, когда арифметическая формула, содержащая z символов, называет число x . Этот набросок доказательства содержит единственное упоминание о нумерации Гёделя ; Булос просто предполагает, что каждая формула может быть пронумерована таким образом. Здесь формула F называет число n тогда и только тогда, когда доказуемо следующее:

$\forall x(F(x)\leftrightarrow x=n)$

Затем Булос определяет связанные предикаты:

• Bxy ↔ ∃ z ( z < y ∧ Cxz ) . (Русский: Bxy становится истинным, если x может быть определен менее чем в символах y ):
• Axy ↔ ¬ Bxy ∧ ∀ а ( а < Икс → Бэй ) . (Английский язык: Axy оказывается истинным, если x - наименьшее число, которое невозможно определить с помощью символов меньше, чем y . Что еще более неловко, Axy выполняется, если x не может быть определен с помощью символов меньше, чем y , и все числа меньше, чем x, могут быть определены с использованием меньшего, чем y символов. символы);
• Fx ↔ ∃ y (( y знак равно [10] × [ k ]) ∧ Axy ) . k = количество символов, появляющихся в Axy .

Форекс формализует парадокс Берри. Итог доказательства, требующий всего 12 строк текста, показывает, что предложение ∀ x ( Fx ↔( x = [ n ])) истинно для некоторого числа n , но никакой алгоритм M не идентифицирует его как истинное. Следовательно, в арифметике истина опережает доказательство. КЭД.

Вышеупомянутые предикаты содержат единственные кванторы существования, встречающиеся во всем доказательстве. Знаки «<» и «×», входящие в эти предикаты, являются единственными определенными арифметическими понятиями, которые требуются для доказательства. В доказательстве нигде не упоминаются рекурсивные функции или какие-либо факты из теории чисел , и Булос утверждает, что его доказательство обходится без диагонализации . Подробнее об этом доказательстве см. в парадоксе Берри .

Ссылки

• 1931, «О формально неразрешимых теоремах Principia Mathematica и родственных систем, I». Ежемесячные выпуски по математике и физике 38 : 173–98.
• Английские переводы предыдущего:
  • Жан ван Хейеноорт , 1967. От Фреге до Гёделя: справочник по математической логике . Издательство Гарвардского университета: 596–616.
  • Хирзель, Мартин (пер.), 2000, «О формально неразрешимых утверждениях Principia Mathematica и родственных системах I». .
• 1951, «Некоторые основные теоремы об основаниях математики и их последствиях» в Соломоне Фефермане , изд., 1995. Собрание сочинений / Курт Гёдель, Vol. III . Издательство Оксфордского университета: 304–23.
• Джордж Булос , 1998, «Новое доказательство теоремы Гёделя о неполноте» в книге Булос, Г., Логика, логика и логика . Гарвардский университет. Нажимать.

Внешние ссылки

• Краткое доказательство теоремы Гёделя о неполноте.