Десять великих идей науки. Как устроен наш мир. - Эткинз (Эткинс) Питер

Существуют несколько теорем, связанных с именем Гёделя. Здесь мы сосредоточимся на теореме, опубликованной в 1931 г. в статье Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme(О формальной неразрешимости предложений в Principia Mathematicaи связанных с ней системах). В этой статье он показал, что в любой системе математических аксиом существуют метаматематические предложения, которые нельзя ни доказать, ни опровергнуть посредством формального вывода, основанного на аксиомах системы.

Это мы и сделаем. Математика представляет собой последовательность предложений, таких как 1 + 1 = 2, и «это является доказательством данного предложения»; первое предложение является математическим, в смысле Гильберта, а второе метаматематическим. Давайте предположим, что мы можем записать все предложения, которые можно вывести из фундаментальных аксиом (например, из аксиом Пеано или более разработанной системы, основанной на усовершенствованной теории типов, которой пользовались Рассел и Уайтхед). Это даст нам предложения p 0, p 1, p 2, … и так далее. Как мы решим пронумеровать предложения, не имеет значения, но несколько изложенных ниже аргументов дадут вам ощутить аромат того, как действовал Гёдель.

В формулировке арифметики, подобной формулировке Пеано, имеется лишь небольшое число символов.

Например, одна из аксиом гласит «элемент, непосредственно следующий за числом, есть также число». Мы ввели обозначение х' = sx, где sозначает «непосредственно следующий за», так что s0 = 1, s1 = ss0 = 2, и так далее. Гёдель приписал число каждому элементарному знаку, используемому в выражениях. Предположим, что он приписал 5 знаку «=» и 7 знаку s. Каждая отдельная переменная, такая как x, описывается отдельным простым числом, большим 10. Например, мы припишем  xчисло 11, а х'число 13. Гёделевским номером предложения является произведение всех чисел, соответствующих символам, которые содержит предложение; так, нашему предложению х' = sxприписывается значение 13 (для x') × 5 (для «=») × 7 (для s) × 11 (для x), что дает 5005. Заметим, что посредством этой процедуры каждое предложение, включая аксиомы формализма, наделяется единственным номером [52], поэтому связи между предложениями становятся связями внутри арифметики. Например, мы можем ответить на метаматематический вопрос: встречается ли это предложение в более длинном, более сложном предложении, выяснив, является ли 5005 множителем в гёделевском номере сложного предложения, также как 5 является множителем 75.

Снабдим предложения индексами, используя их гёделевские номера, так что предложение х' = sxотносительно числа 6 (которое должно читаться 6 = s5 ,«6 непосредственно следует за 5») есть предложение p 5005(6). Вы можете ожидать, что сложные предложения имеют большие гёделевские номера, но в том, что последует ниже, мы будем делать вид, что можем обойтись малыми номерами, такими как p 1(6)и p 4(6). Например, мы можем сделать вид, что Предложение 4, примененное к числу 6, является метаматематическим утверждением «6 есть совершенное число» (число, являющееся суммой своих простых множителей, в данном случае включая 1, 6 = 1 + 2 + 3 и 6 = 1 × 2 × 3), а Предложение 5 может сообщать о простых числах, и мы можем прочесть p 5(11)как «11 есть простое число».

Математическое доказательство состоит из строки предложений, которые выводятся одно из другого с помощью использования правил обращения с символами. Это означает, что мы можем приписать отдельный номер целому доказательству, отметив гёделевские номера всех входящих в него предложений. Если доказательство состоит из трех предложений с гёделевскими номерами 6, 8 и 2 (на практике эти номера были бы огромны), то всему доказательству приписывается номер 2 6× 3 8× 5 2= 10 497 600 (для более длинных доказательств ряд простых чисел 2, 3, 5 последовательно продолжают). Как вы можете вообразить, длинные доказательства, состоящие из сложных предложений, имеют астрономически большие гёделевские номера. И снова смыслом этой процедуры является то, что целые доказательства включаются в область арифметики. Мы можем использовать арифметические процедуры, чтобы, например, судить, используется ли одно доказательство в другом, определяя, входит ли гёделевский номер первого множителем в гёделевский номер второго, подобно тому, как 15 = 5 × 3 означает, что 5 и 3 являются компонентами 15.

Теперь мы воспользуемся этими гёделевскими номерами, чтобы вывести результат Гёделя с помощью вариации процедуры из метода Кантора и решения Тьюрингом проблемы вычислимости. На самом деле Гёдель использовал гораздо более глубокие методы, доказав пятьдесят промежуточных теорем — опорные базы, — прежде чем достичь завершения доказательства. Следующий далее текст лишь ухватывает суть дела: представьте себе это как полет вертолета над вершиной горы. Однако, поскольку доказательство все же является трудным, даже урезанное и упрощенное до той степени, до которой мне удалось его адаптировать, вы можете свободно перескочить к месту, где восстанавливается нормальный размер шрифта.

Предположим, что у нас есть некоторое предложение относительно числа 0, мы назовем это предложение p 0(0), и такое же предложение относительно числа 1, которое мы назовем p 0(1), и так далее. Обозначим вообще это предложение относительно числа  xкак p 0(x). Эти предложения могут быть истинными, а могут ложными. Например, предложение «квадратный корень из  xравен 1» в случае p 0(0)ложно, поскольку утверждает, что √0 = 1, что неверно, но в случае p 0(1)оно истинно, так как √1 = 1. Каждое из этих предложений имеет гёделевский номер, который мы можем вычислить, и существует бесконечное число таких предложений относительно каждого из бесконечного числа натуральных чисел. Обозначим эти предложения как p 0(x), p 1(x)и так далее: некоторые из них являются мусором, некоторые верны. Организуем теперь все соответствующие им гёделевские номера в огромную таблицу (с астрономически большими номерами там, где мы подставили малые номера). Верхний левый фрагмент этой таблицы может быть чем-то вроде:

Вход 0 1 2 3 Предложение 0 0 55 27 4 1 51 3 7 17 2 0 20 30 40 3 13 22 11 2

где каждое число во внутренних клетках таблицы есть (фальшивый) гёделевский номер соответствующего предложения. Так, фальшивый гёделевский номер предложения p 3(x)относительно числа 2 равен 11.

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

И здесь, как и в аргументах Тьюринга, нас ожидает провал. Рассмотрим следующее предложение:

Гёделевский номер этого диагонального члена отсутствует в списке доказуемых утверждений.

«Диагональным членом» является предложение относительно собственного номера предложения, например, предложение p 2относительно числа 2. Поскольку это утверждение является предложением, оно должно уже содержаться где-то в первоначальном исчерпывающем списке предложений. Для простоты давайте предположим, что оно оказывается Предложением 2. Коль это так, рассмотрим соответствующий диагональный гёделевский номер, который в этом случае равен 30. Этот гёделевский номер соответствует Предложению 2 относительно числа 2, которое гласит:

Не существует доказательства Предложения 2 относительно числа 2.

Теперь мы подходим к противоречию. Предположим, что мы узнали, обратись к полному списку доказуемых утверждений, что это предложение действительно верно (а значит, его гёделевский номер должен быть в списке доказуемых утверждений), то есть можно доказать, что доказательства Предложения 2 относительно числа 2 не существует. Тогда у нас получается противоречие, поскольку, если не существует доказательства Предложения 2 относительно числа 2, то его номера не должно быть в списке доказуемых утверждений! Если мы вместо этого предположим, что предложение о том, что не существует доказательства Предложения 2 относительно числа 2, является ложным, тогда его нет в списке доказуемых утверждений, а тогда это предложение истинно!