Выявление принципиальных границ програАлмы формализации математики Гильберта

Статья Гёделя содержит два результата.

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

Основные шаги рассуждения Гёделя таковы116. Сначала он строит арифметическое исчисление, которое позволяет переводить все метаматематические высказывания о его свойствах на язык арифметических утверждений о натуральных числах. Это делается посредством приписывания каждому знаку, формуле и доказательству формализованной арифметике определенного (гёделева) номера. Нумерация (кодификация) начинается с логических и математических констант. Знак отрицания кодируется цифрой один, знак дизъюнкции — цифрой два и т. д. Знак Е обозначает квантор существования, s — знак «число, следующее непосредственно за». Итерация знака s (приписывание его слева к цифре 0) позволяет конструировать натуральные числа. Например, $0 соответствует числу 1, ssO — числу 2 и т. д.

-і v Z) Е ~ 0 s ( ) , 123456789 10

Для кодификации констант используются первые десять чисел натурального ряда, исключая число 0. Кодификации подлежат также переменные для числовых высказываний, переменные для высказываний и переменные для предикатов. Процесс кодификации должен удовлетворять следующим правилам: (1)

каждой числовой переменной (jc, у, z,...) соответствует простое число, большее десяти: 11,13,17, (2)

каждой переменной для высказываний (А, В, С, ...) соответст- , вует квадрат простого числа, большего десяти: 11 2, ІЗ2,172, (3)

каждой предикатной переменной (Р, Q, R, ...) соответствует куб простого числа, большего десяти: II3, ІЗ3,173,

Рассмотрим высказывание «существует число х такое, что х есть последователь у». Символически оно выглядит так: (Ех)(х = sy), В формулу входят константы и одна переменная для чисел (дважды). Поэтому она кодируется гёделевыми номерами элементарных знаков:

{&x)(x = sy) 8 4 И 9 8 И 5 7 9 13

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

Код (гёделев номер) формулы (Ех)(х ~ sy) равен числу

28 х З4 х 5" х f х II8 х 13п х 175 х 197 х 2313 х 299.

Пусть т обозначает гёделев номер формулы (Ех)(х = Как вычислить гёделев номер конечной последовательности формул, представляющей доказательство? Это делается по аналогии с вычислением гёделева номера отдельной формулы. Допустим, дана следующая последовательность, в которой нижняя формула представляет заключение верхней:

(Ех)(х = sy);

{Ех)(х = .?0).

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

к=2т у. 3*.

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

Метод кодирования позволяет каждое метаматематическое выражение перевести в арифметическую формулу. Обратная задача состоит в том, чтобы по данной арифметической формуле определять, соответствует ли ей какое-нибудь осмысленное выражение или элементарный знак системы. Если число меньше или равно 10, то оно, по определению, представляет гёделев номер. Если число больше 10, то оно обозначает гёделев номер, если его можно разложить на множители, каждое из которых представляет простое число, взятое в некоторой степени.

Примером может служить декодирование числа 243 ООО ООО117: 1)

243 ООО ООО; . 2)

64 х 243 х 15 625; 3)

26 х З5 х 56; 4)

6 5 6; 5)

0 0; 6)

0 = 0.

Рассматриваемое число представляет результат произведения трех сомножителей, каждый из которых является простым числом, взятым в определенной степени. Следовательно, оно — гёделев номер. Декодирование доказывает, что число 243 000 000 символизирует формулу 0 = 0. Чтение приведенного построения снизу вверх показывает этапы кодирования формулы определенным гёделевым номером. Чтение его в обратном порядке — этапы декодирования предъявленного числа. При этом может случиться так, что число может и не быть гёделевым номером. Например, число 100 больше 10 и должно быть результатом произведения простых чисел, взятых в квадрат или куб. Действительно, 100 можно представить как 22 х 52. Но, по определению, формула должна быть результатом произведения последовательно возрастающих простых чисел. Однако э приведенной последовательности отсутствует простое число 3. Значит, число 100 не является гёделевым номером.

Следующий шаг состоит в объяснении ключевой фразы гёделевского метода арифметизации: «Последовательность формул с гёделевым номером х есть доказательство формулы с гёделевым номером у». Формально: Рг(х, у). Если л: и у не находятся в указан- ном отношении доказательства, это символизируется как —>Рг(х, у), что читается как «неверно, что х представляет доказательство формулы с гёделевым номером у».

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

2 дляр;

2112 х З3 х 58 х 7112 х 112 х 139 х 179 для р г» (р v q).

Легко увидеть, что гёделев номер высказывания р входит в качестве первого сомножителя в гёделев номер высказывания р z> (р v q). Это позволяет сделать важный вывод. Одна формула является частью другой формулы, если и только если гёделев номер первой формулы составляет часть (сомножитель) гёделевого номера второй формулы. Значит, метаматематическое высказывание Рг(х, у) истинно, если и только если гёделев номер заключения у входит в качестве одного из сомножителей в гёделев номер доказательства х. Вернемся к гёделеву номеру доказательства к = 2т х 3й. В новой записи оно выглядит так — Рг(&, и) — и означает, что к является гёделевым номером доказательства формулы под годовым номером п. Так как формула с номером п входит в качестве составной части в номер доказательства к, то высказывание Рг(к, п) истинно.

Сказанного достаточно, чтобы понять смысл основных доказательств Гёделя. (1)

Сначала Гёдель показывает, как в построенном им арифметическом исчислении можно сконструировать формулу G, кодирующую метаматематическое высказывание «формула G не доказуема». Формально: G = —і (Ex) Pr(x, G) (гёделев номер высказывания «не существует ни одного числа х, представляющего гёделев номер доказательства формулы G» равен G). (2)

Затем Гёдель устанавливает, что формула G доказуема, если и только если ее логическое отрицание -іG также доказуемо. Это означает, что если, скажем, формула G выводима из аксиом арифметического исчисления, то должна быть выводимой и формула -»G как ей эквивалентная. Обратное также верно. До- казательство формулы -iG означало бы существование доказательства G. Но арифметическое исчисление непротиворечиво, и наличие в нем двух противоречащих друг другу формул невозможно. Значит, формулы G и -»G обе не выводимы из аксиом арифметического исчисления, т. е. они обе — неразрешимые арифметические высказывания118. (3)

Гёдель также доказывает, что хотя G и не доказуема как арифметическое высказывание, она все же истинное метаматематическое утверждение. Раз формула G сама утверждает о самой себе, что она недоказуема, и это действительно так, то она вне всякого сомнения истинное высказывание. (4)

Таким образом, арифметическое исчисление содержит не только неразрешимое, но и истинное высказывание G. Значит, аксиомы арифметики неполны в том смысле, что из них нельзя дедуцировать все арифметические истины. Кроме того, аксиомы арифметики неполны существенно. Даже если к арифметическому исчислению добавить новые аксиомы, чтобы вывести формулу G, в расширенном исчислении появятся новые неразрешимые высказывания. (5)

Следовательно, если арифметическое исчисление непротиворечиво, то оно неполно. Формула G, которая утверждает свою собственную недоказуемость, эквивалентна высказыванию «эта система аксиом неполна», потому что представляет пример истинного и неразрешимого предложения. Значит, верно «если система аксиом непротиворечива, то следует, что формула G истинна».

Пусть А — высказывание «существует формула, которая недоказуема», которое эквивалентно утверждению «система аксиом арифметики непротиворечива». Тогда истинна формула A z> G, из которой при допущении существования доказательства А следует доказательство G. Но, как было уже показано, формула G недоказуема. Этого достаточно, чтобы сделать решающий вывод: метама- тематическими средствами, переведенными на язык арифметических формул, невозможно доказать непротиворечивость арифметики. Иными словами, непротиворечивость арифметики нельзя доказать арифметическими средствами.