Войти
В этой статье дается набросок доказательства первой теоремы Гёделя о неполноте. Эта теорема применима к любой формальной теории, удовлетворяющей определенным техническим гипотезам, которые при необходимости обсуждаются во время наброска. В оставшейся части статьи мы будем предполагать, что была выбрана фиксированная теория, удовлетворяющая этим гипотезам.
В этой статье слово «число» относится к натуральному числу. Ключевым свойством этих чисел является то, что любое натуральное число можно получить, начав с числа 0 и добавив 1 конечное число раз.
Теорема Гёделя применима к любой формальной теории, удовлетворяющей определенным свойствам. Каждая формальная теория имеет подпись, которая определяет нелогичные символы на языке теории. Для простоты предположим, что язык теории состоит из следующего набора из 15 (и только 15) символов:
Это язык арифметики Пеано. Правильно сформированная формула - это последовательность этих символов, сформированная так, чтобы иметь четко определенное прочтение в виде математической формулы. Таким образом, x = SS 0 сформирован правильно, в то время как x = ∀ + сформирован неправильно. Теория - это набор правильно построенных формул без свободных переменных.
Теория непротиворечива, если не существует формулы F такой, что и F, и ее отрицание доказуемы. ω-согласованность - более сильное свойство, чем согласованность. Предположим, что F ( x) - формула с одной свободной переменной x. Для того, чтобы быть ω-последовательны, теория не может доказать, как ∃ м F ( м), а также доказать, ¬ F ( п) для каждого натурального числа п.
Предполагается, что теория эффективна, а это означает, что набор аксиом должен быть рекурсивно перечислимым. Это означает, что теоретически возможно написать компьютерную программу конечной длины, которая, если ей разрешено работать вечно, выводила бы аксиомы теории (обязательно включая каждый правильно сформированный экземпляр схемы аксиомы индукции ) по одной за раз и больше ничего не выводить. Это требование необходимо; есть теории, которые являются полными, непротиворечивыми и включают элементарную арифметику, но никакая такая теория не может быть эффективной.
Набросок здесь разбит на три части. В первой части каждой формуле теории присваивается номер, известный как число Гёделя, таким образом, чтобы можно было эффективно восстановить формулу из числа. Эта нумерация распространяется на конечные последовательности формул. Во второй части, конкретная формула ПФ ( х, у) построена таким образом, что для любых двух чисел п и т, ПФ ( п, т) имеет место тогда и только тогда, когда п представляет собой последовательность формул, составляющие доказательство формулы что представляет m. В третьей части доказательства мы строим формулу самореференции, которая неформально говорит: «Я не доказуем», и доказываем, что это предложение нельзя ни доказать, ни опровергнуть в рамках теории.
Важно отметить, что все формулы в доказательстве могут быть определены с помощью примитивных рекурсивных функций, которые сами могут быть определены в арифметике Пеано первого порядка.
Первым шагом доказательства является представление (правильно построенных) формул теории и конечных списков этих формул в виде натуральных чисел. Эти числа называются числами Гёделя формул.
Начните с присвоения натурального числа каждому символу языка арифметики, аналогично тому, как код ASCII присваивает уникальное двоичное число каждой букве и некоторым другим символам. В этой статье будет использоваться следующее задание, очень похожее на то, которое Дуглас Хофштадтер использовал в своих работах «Гедель, Эшер, Бах» :
|
|
Число Гёделя формулы получается путем объединения чисел Гёделя каждого символа, составляющего формулу. Числа Гёделя для каждого символа разделены нулем, потому что по замыслу ни один гёделевский номер символа не включает 0. Следовательно, любую формулу можно правильно восстановить по ее гёделевскому числу. Пусть G ( F) обозначит число гёделевских формул F.
Учитывая вышеприведенную нумерацию Гёделя, предложение, утверждающее, что сложение коммутирует, ∀ x ∀ x * ( x + x * = x * + x) переводится как число:
(Пробелы были вставлены с каждой стороны от каждого 0 только для удобства чтения; числа Гёделя представляют собой строгие конкатенации десятичных цифр.) Не все натуральные числа представляют собой формулы. Например, число
переводится как « = ∀ + x », что не является правильным.
Поскольку каждое натуральное число можно получить, применяя операцию преемника S к 0 конечное число раз, каждое натуральное число имеет собственное число Гёделя. Например, число Гёделя, соответствующее 4, SSSS 0, будет:
Назначение чисел Гёделя может быть расширено до конечных списков формул. Чтобы получить число Гёделя для списка формул, запишите числа Гёделя формул по порядку, разделяя их двумя последовательными нулями. Поскольку число Гёделя в формуле никогда не содержит двух последовательных нулей, каждую формулу в списке формул можно эффективно восстановить из числа Гёделя для списка.
Крайне важно, чтобы формальная арифметика была способна доказать минимальный набор фактов. В частности, он должен быть в состоянии доказать, что каждое число m имеет гёделевское число G ( m). Второй факт, который должна доказать теория, заключается в том, что для любого гёделевского числа G ( F ( x)) формулы F ( x) с одной свободной переменной x и любым числом m существует гёделевское число формулы F ( m) получается путем замены всех вхождений G ( х) в G ( F ( х)) с G ( м), и что это второе число Гедель может быть эффективно получен из числа Гёделя G ( Р ( х)) из F ( х) как функция от G ( x). Чтобы убедиться, что это действительно возможно, обратите внимание, что с учетом гёделевского числа F ( x) можно воссоздать исходную формулу F ( x), произвести замену x на m, а затем найти гёделевское число G ( F ( m)) полученной формулы F ( m). Это единая процедура.
Тогда правила дедукции могут быть представлены бинарными отношениями на гёделевских числах списков формул. Другими словами, предположим, что существует правило вычет D 1, с помощью которого можно перемещать из формул S 1, S 2 к новой формуле S. Тогда отношение R 1, соответствующее этому правилу вывода, говорит, что n связано с m (другими словами, выполняется n R 1 m), если n - гёделевское число списка формул, содержащих S 1 и S 2, а m - гёделевское число. номер списка формул, состоящих из тех, в списке кодируются п вместе с S. Поскольку каждое правило вывода является конкретным, можно эффективно определить для любых натуральных чисел n и m, связаны ли они соотношением.
Второй этап доказательства - использовать гёделевскую нумерацию, описанную выше, чтобы показать, что понятие доказуемости может быть выражено на формальном языке теории. Предположим, что теория имеет правила дедукции: D 1, D 2, D 3,.... Пусть R 1, R 2, R 3,... их соответствующие отношения, как описано выше.
Каждое доказуемое утверждение либо само по себе является аксиомой, либо его можно вывести из аксиом с помощью конечного числа применений правил дедукции. Доказательство формульной S сама строка математических утверждений, связанных определенными отношениями (каждый является либо аксиомой, либо связаны с бывшими заявления правил вывода), где последнее утверждение S. Таким образом, можно определить гёделевское число доказательства. Более того, можно определить форму утверждения Proof ( 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), но не оба сразу. Это потому, что соотношение между этими двумя числами можно просто «проверить». Формально это можно доказать по индукции, где все эти возможные отношения (число которых бесконечно) строятся одно за другим. Детальное построение формулы Proof существенно использует предположение об эффективности теории; без такого предположения построить эту формулу было бы невозможно.
Для каждого числа n и каждой формулы F ( y), где y - свободная переменная, мы определяем q ( n, G ( F)), отношение между двумя числами n и G ( F), такое, что оно соответствует утверждению « n не является гёделевским числом доказательства F ( G ( F)) ». Здесь F ( G ( F)) можно понимать как F со своим собственным числом Гёделя в качестве аргумента.
Обратите внимание, что д принимает в качестве аргумента 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)) доказуемо, если конечный список формул, закодированных n, не является доказательством F ( G ( F)), и ¬ q ( 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)) не доказуемо. Поскольку либо q ( n, G ( P)), либо ¬ q ( n, G ( P)) должны быть доказуемыми, мы заключаем, что для всех натуральных чисел n, q ( n, G ( P)) доказуемо.
Предположим, что отрицание P ( G ( P)), ¬ P ( G ( P)) = ∃ x ¬ q ( x, G ( P)), доказуемо. Доказывание как ∃ х ¬ Q ( х, G ( P)) и д ( п, G ( P)), для всех натуральных чисел п, нарушает со-непротиворечивости формальной теории. Таким образом, если теория ω-непротиворечива, то ¬ P ( G ( P)) не доказуемо.
Мы набросали доказательство, показывающее, что:
Для любой формальной, рекурсивно перечислимой (т. Е. Эффективно порожденной) теории арифметики Пеано,
Только что набросанное доказательство теоремы Гёделя о неполноте является теоретико-доказательственным (также называемым синтаксическим), поскольку оно показывает, что если существуют определенные доказательства (доказательство P ( G ( P)) или его отрицание), то ими можно манипулировать для получения доказательства. противоречия. Это не апеллирует к тому, является ли P ( G ( P)) «истинным», а только к тому, доказуемо ли оно. Истина - это теоретико-модельное или семантическое понятие, которое не эквивалентно доказуемости, за исключением особых случаев.
Более подробно проанализировав ситуацию приведенного выше доказательства, можно сделать вывод об истинности P ( G ( P)) в стандартной модели натуральных чисел. Как только что было замечено, q ( n, G ( P)) доказуемо для каждого натурального числа n и, таким образом, истинно в модели. Следовательно, в рамках этой модели
держит. Это то, к чему обычно относится утверждение « P ( G ( P)) истинно» - предложение истинно в предполагаемой модели. Однако это верно не для каждой модели: если бы это было так, то по теореме Гёделя о полноте это было бы доказуемо, что, как мы только что видели, не так.
Джордж Булос (1989) значительно упростил доказательство Первой теоремы, если согласиться с тем, что эта теорема эквивалентна:
«Не существует алгоритма M, на выходе которого содержатся все истинные арифметические предложения и нет ложных».
«Арифметика» относится к арифметике Пеано или Робинсона, но в доказательстве не упоминается ни одна из них, молчаливо предполагается, что эти системы позволяют символам «lt;» и «×» иметь их обычные значения. Булос доказывает теорему примерно на двух страницах. Его доказательство использует язык логики первого порядка, но не использует никаких фактов о связках или кванторах. Область дискурса - натуральные числа. Предложение Гёделя основано на парадоксе Берри.
Пусть [ n ] сокращает n последовательных применений функции- преемника, начиная с 0. Затем Boolos утверждает (детали только наброски), что существует определенный предикат Cxz, который оказывается истинным, если арифметическая формула, содержащая символы z, называет число x. Этот набросок доказательства содержит единственное упоминание о нумерации Гёделя ; Boolos просто предполагает, что каждая формула может быть пронумерована. Здесь формула F называет число n тогда и только тогда, когда доказуемо следующее:
Затем Boolos определяет связанные предикаты:
Fx формализует парадокс Берри. Остаток доказательства, требующий всего 12 строк текста, показывает, что предложение ∀ x ( Fx ↔ ( x = [ n ])) верно для некоторого числа n, но ни один алгоритм M не идентифицирует его как истинный. Следовательно, в арифметике истина опережает доказательство. QED.
Вышеупомянутые предикаты содержат единственные кванторы существования, появляющиеся во всем доказательстве. Знаки «lt;» и «×», встречающиеся в этих предикатах, являются единственными определенными арифметическими понятиями, которые требует доказательство. В доказательстве нигде не упоминаются рекурсивные функции или какие-либо факты из теории чисел, и Булос утверждает, что его доказательство обходится без диагонализации. Подробнее об этом доказательстве см . Парадокс Берри.
