Текст книги "Teopeмa Гёделя"

Автор книги: Эрнст Нагель

Соавторы: Джеймс Ньюмен
сообщить о нарушении

Текущая страница: 3 (всего у книги 6 страниц)

5
Один пример абсолютного доказательства непротиворечивости

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

Мы покажем здесь коротко, как можно формализовать элементарную логику высказываний, являющуюся некоторым фрагментом системы, описанной в Principia Mathematica. В результате формализации упомянутый фрагмент Principia станет исчислением, состоящим из неинтепретированных символов. После этого мы уже сможем провести нужнее нам доказательство.

Формализация проходит в четыре этапа. Прежде всего нам понадобится полный перечень символов, которые используются в нашем исчислении, они составят так называемый алфавит системы. Далее нам надо будет сформулировать «правила образования», согласно которым из «букв» алфавита составляются «формулы» (причем только такие, «правильно составленные», сочетания символов мы будем считать предложениями нашей системы). Можно было бы считать совокупность правил «грамматикой» исчисления. Затем мы отбираем некоторые формулы нашей системы в качестве ее аксиом (или «исходных формул»), аксиомы служат «базисом» системы. И, наконец, мы сформулируем «правила преобразования», точно описывающие, каким образом из одних формул некоторого вида «выводятся» другие формулы определенного вида; иначе говоря, правила эти – не что иное, как правила вывода. Теоремой нашей системы мы будем называть теперь любую формулу, получаемую посредством последовательного применения правил преобразования к аксиомам. Формальным «доказательством» мы будем называть любую конечную последовательность формул рассматриваемого исчисления, каждая из которых либо является аксиомой, либо выводима из предшествующих формул данной последовательности с помощью правил преобразования[1]1
  Из этого определения немедленно вытекает, что аксиомы также причисляются к теоремам (доказательство каждой такой теоремы состоит из единственной формулы – из нее самой). – Прим. перев.


[Закрыть].

Алфавит логики высказываний (называемой часто «пропозициональным исчислением») очень несложен. Он состоит из переменных и констант. Переменные, поскольку вместо них можно подставлять предложения (sentences) системы, называют сентенциональными (чаще – пропозициональными) переменными. В качестве переменных мы будем использовать буквы «p», «q», «r», …, «p₁», «p₂» …, «q₁», «q₂» ….

Постоянные символы (константы) – это «пропозициональные» связки и знаки препинания. Мы будем употреблять следующие пропозициональные связки: «~» читается как «не»; ˅ – «или»; «ﬤ» – «если…, то…»; «·» – «и»; знаки препинания: «(» – «левая скобка», «)» – «правая скобка».

^{Действительно, перечисленные связки возникли как сокращенные обозначения для указанных в скобках выражений; более того, при устном чтении формул исчисления высказываний этими выражениями часто называют соответствующие формальные символы (скажем, формула «~ p ˅ q» читается как «не p или q» и т. п.). Следует, однако, твердо помнить, что эти «названия» связок не нужны для описания исчисления (неинтерпретированного!) как такового; они относятся к его метатеории, и, скажем, электронно-вычислительная машина, производящая операции с формулами исчисления высказываний как с таковыми, в такого рода «названиях» не нуждается. – Прим. перев.}

Правила образования указывают, какие именно комбинации элементарных символов алфавита мы будем считать формулами нашего исчисления. Прежде всего формулой, по определению, является каждая пропозициональная переменная. Далее, если «S» обозначает некоторую формулу[2]2
  Именно обозначает, но не является формулой (является именем формулы); S, не принадлежащая алфавиту описываемого исчисления, относится к его метаязыку. – Прим. перев.


[Закрыть], то ее «формальное отрицание» «~ (S)» также есть формула. Аналогично, если «S₁» и «S₂»суть обозначения некоторых формул, то выражения «(S₁) ˅ (S₂)», «(S₁) ﬤ (S₂)» и «(S₁)·(S₂)» также суть формулы.

Примеры формул:

«p», «~ p», «(р) ﬤ (q)», «((q) ˅ (r)) ﬤ (p)».

Однако выражения «(p)(~ q)» или «((р)ﬤ(q))˅» формулами не являются, так как они не удовлетворяют приведенному здесь определению формулы[3]3
  В тех случаях, когда нечего опасаться недоразумений, часть скобок в записях формулы опускают.


[Закрыть].

Правил преобразования имеется два. Первое из них – правило подстановки (вместо пропозициональных переменных) – гласит, что из произвольной формулы можно вывести другую формулу посредством одновременной подстановки некоторой формулы вместо некоторой входящей в исходную формулу пропозициональной переменной, причем такая подстановка (одна и та же) должна производиться вместо каждого вхождения выбранной переменной. Например, из формулы «p ﬤ p» можно, подставив вместо переменной «p» переменную (а тем самым – формулу) «q», вывести формулу «q ﬤ q»; подставив в ту же исходную формулу вместо «p» формулу «p ˅ q», мы выведем формулу «(p ˅ q) ﬤ (p ˅ q)» и т. п. Или, если интерпретировать «p» и «q» как некоторые русские предложения, то из «p ﬤ p» можно, например, получить предложения «Лягушки квакают ﬤ лягушки квакают», «(Летучие мыши слепы ˅ летучие мыши едят мышей) ﬤ (летучие мыши слепы ˅ летучие мыши едят мышей)» и т. п. Второе правило преобразования – это так называемое правило отделения (или modus ponens). Согласно этому правилу из любых двух формул, имеющих соответственно вид «S₁» и «S₁ ﬤ S₂», можно вывести и формулу «S₂». Например, из формул «p ˅ ~ p» и «(p ˅ ~ p) ﬤ (p ﬤ p) мы можем вывести «p ﬤ p».

Наконец, аксиомами нашего исчисления (по существу теми же, что в Principia Mathematica[4]4
  В Principia была еще аксиома «(p ˅ (q ˅ r)) ˅ (q ˅ (p ˅ r))» выводимая, однако, как установил П. Бернайс (1926), из остальных четырех аксиом. – Прим. перев.


[Закрыть]являются следующие четыре формулы[5]5
  Начиная отсюда, мы будем, как обычно, опускать кавычки при записях формул, напечатанных в отдельную строку. Нам, ведь, нужны не сами по себе кавычки, а уверенность в том, что не возникнет недоразумений (ср. с названием книги Рассела и Уайтхеда, всюду в настоящей книжке выделяемым не кавычками, а курсивом). – Прим. перев.


[Закрыть];

1. (p ˅ p) ﬤ p

[если p или p, то p];

2. p ﬤ (p ˅ q)

[если p, то p или q];

3. (p ˅ q) ﬤ (q ˅ p)

[если p или q, то q или p];

4. (p ﬤ q) ﬤ ((r ˅ р) ﬤ (r ˅ q))

[если p влечет q, то (r или p) влечет (r или q)].

Здесь вначале приведены аксиомы, а в квадратных скобках указаны их «переводы» на обычный язык[6]6
  «Переводы» эти, разумеется, к самому исчислению не относятся. – Прим. перев.


[Закрыть].

Каждая из приведенных аксиом представляется довольно-таки «очевидной» и тривиальной.

^{Если, конечно, иметь в виду некоторые «естественные переводы» (т. е. интерпретации!) аксиом, самих по себе никакого «смысла» не имеющих. Аналогичное замечание следует иметь в виду при чтении следующей фразы текста и всюду в аналогичных случаях далее. – Прим. перев.}

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

((p ﬤ q) ﬤ ((r ﬤ s) ﬤ t)) ﬤ ((u ﬤ ((r ﬤ s) ﬤ t)) ﬤ ((p ﬤ u) ﬤ (s ﬤ t))).

В данный момент нас, однако, не интересует вывод теорем из аксиом. Цель наша состоит в том, чтобы показать непротиворечивость этой системы аксиом, т. е. дать «абсолютное» доказательство невозможностивывода из данных аксиом с помощью правил преобразования никакой формулы S одновременно с ее формальным отрицанием ~S.

Оказывается, что к числу теорем нашего исчисления относится формула «p ﬤ (~ p ﬤ q)» (выражаемая словесно следующим образом: «если p, то не p влечет q»). (Мы примем этот результат к сведению, не проводя фактического его доказательства.) Допустим, что некоторая формула S, так же как и ее отрицание ~ S, выводима из аксиом. Подставляя тогда S вместо переменной «p» в только что упомянутую теорему (пользуясь правилом подстановки) и применяя затем дважды modus ponens, мы получим, что теоремой является и формула «q».

^{Подставляя S вместо (p) в «p ﬤ (~ p ﬤ q)», мы получим сначала «S ﬤ (~ S ﬤ q)». Беря затем эту формулу и формулу S в качестве посылок modus ponens, получим «~ S ~ q». Наконец, из последней формулы и ~ S также по modus ponens получим формулу «q».}

Но если формула, состоящая из одной-единственной переменной «q», является теоремой, то поскольку вместо «I» можно подставить любую формулу, то любая формула нашего исчисления оказывается выводимой из аксиом. Отсюда видно, что если какая– либо формула S вместе со своим отрицанием ~ S является теоремой рассматриваемого исчисления, то в нем теоремой является любая формула. Короче говоря, каждая формула противоречивого исчисления является теоремой – из противоречивой системы аксиом можно вывести любую формулу. Но этот же результат можно выразить и в «обратной» форме: если не каждая формула исчисления является теоремой (т. е. имеется хотя бы одна формула, не выводимая из данных аксиом), то это исчисление непротиворечиво. Таким образом, наша задача сводится к тому, чтобы показать, что имеется по крайней мере одна формула, не выводимая из рассматриваемой системы аксиом.

Задача может быть решена посредством некоторого метаматематического рассуждения о рассматриваемой системе. Идея такого рассуждения весьма прозрачна. Суть ее сводится к нахождению некоторого структурного свойства формул данной системы, удовлетворяющего следующим трем условиям:

(1) Свойство это должно выполняться для всех четырех аксиом.

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

(3) Искомому свойству должны удовлетворять не все формулы, которые можно построить с помощью правил образования данной системы. Мы должны уметь показать, что по крайней мере одна формула системы этим свойством не обладает.

Если нам удастся найти свойство формул системы, удовлетворяющее перечисленным трем условиям, то задача построения абсолютного доказательства непротиворечивости системы будет решена. В самом деле, это свойство, будучи наследственным и принадлежа аксиомам, принадлежит и теоремам; значит, если некоторое знакосочетание, являясь формулой данной системы, не обладает указанным свойством, то это – не теорема. Иначе говоря, если член, подозреваемый в принадлежности некоему семейству (формула), лишен фамильных черт, присущих каждому настоящему члену семейства (идущих от общих предков – аксиом), то он на самом деле не может принадлежать этого клану (быть теоремой). Но если нам удалось найти формулу данной системы, не являющуюся теоремой, то мы тем самым доказали непротиворечивость этой системы – ведь, как мы совсем недавно отмечали, в системе, не являющейся непротиворечивой, каждая формула выводима из аксиом (т. е. каждая формула является теоремой). Короче говоря, все, что нам надо для решения нашей задачи, – это найти хоть одну формулу, не обладающую наследственным свойством, удовлетворяющим описанным выше условиям.

В качестве такого свойства годится, например, свойство «быть тавтологией». Вы знаете, что так обычно именуют утверждения, дважды повторяющие внешне различным образом одну и ту же мысль и не несущие поэтому фактически никакой информации. Например, «раз Джон есть отец Чарлза, то Чарлз – сын Джона». В обобщение этого свойства «неинформативности» в логике тавтологиями принято называть утверждения, которые не могут не быть истинными. Примером может служить высказывание: «дождь идет или дождь не идет». Говорят также, что тавтологии – «истины во всех возможных мирах», или, еще по-другому, что это необходимо (или логически) истинные высказывания.

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

Напомним, что формула нашего исчисления – либо просто одна из букв, используемых в нем в качестве пропозициональных переменных (назовем такие формулы «элементарными»), либо же составлена из таких букв с помощью пропозициональных связок и скобок. Условимся отнести каждую элементарную формулу в один из двух непересекающихся классов, в сумме дающих все множество формул исчисления – K₁ или K₂. Формулы, не являющиеся элементарными, относятся к тому или иному из этих классов в силу следующих соглашений:

1) формула, имеющая вид S₁ ˅ S₂, принадлежит классу K₂, если как S₁, так и S₂ принадлежат K₂; в противном случае она принадлежит K₁;

2) формула, имеющая вид S₁ ﬤ S₂, принадлежит классу K₂, если S₁ принадлежит K₁, a S₂ принадлежит K₂; в противном случае она принадлежит K₁;

3) формула, имеющая вид S₁ · S₂, принадлежит классу K₁, если как S₁, так и S₂ принадлежат K₁; в противном случае она принадлежит K₂;

4) формула, имеющая вид ~ S, принадлежит классу K₂, если S принадлежит K₁; в противном случае она принадлежит K₁.

Теперь мы определяем свойство «быть тавтологией»: формула есть тавтология тогда и только тогда, когда она принадлежит классу K₁ независимо от того, какому из классов K₁ и K₂ принадлежит любая из входящих в нее элементарных формул (т. е. переменных). Ясно, что это определение не использует никакой модели или интерпретации нашей системы. Мы можем установить, является ли какая-либо данная формула тавтологией, просто исследуя ее строение с точки зрения выполнения приведенных выше четырех условий.

Такая проверка приводит к выводу, что каждая из четырех аксиом является тавтологией. Процедура такой проверки сводится к составлению таблицы, в которой учитываются все возможные варианты соотнесения элементарных компонент данной аксиомы к любому из двух классов, K₁ и K₂. Просматривая последовательно строки такой таблицы, мы можем определить для каждого из возможных распределений «значений» (т. е. принадлежности классам K₁ и K₂) элементарных формул (т. е. попросту переменных), какому из классов принадлежит каждая неэлементарная «подформула» данной формулы и вся рассматриваемая формула в целом. Возьмем, например, первую аксиому. Таблица для нее состоит из трех столбцов: первый из них соответствует единственной ее элементарной компоненте «p», второй – неэлементарной подформуле «(p ˅ p)», а третий – всей формуле «(p ˅ p) ﬤ p». В каждом из столбцов указаны классы, которым принадлежат соответствующие формулы при данных распределениях значений переменных по этим классам. Вот как выглядит таблица для первой аксиомы:

p p˅p (p˅p)ﬤp

K ₁ K ₁ K ₁

K ₂ K ₂ K ₁

В первом столбце таблицы приведены возможные значения единственной элементарной компоненты рассматриваемой аксиомы, во втором – соответствующие значения неэлементарной компоненты аксиомы (согласно условию (1), в третьем – значения самой аксиомы (согласно условию (2)). Из последнего столбца сразу видно, что первая аксиома принадлежит классу K₁ всегда, независимо от того, к какому классу отнесена ее элементарная компонента. Значит, первая аксиома является тавтологией.

А вот такая же таблица для второй аксиомы:

p q p˅q рﬤ(р˅q)

K ₁ K ₁ K ₁ K ₁

K ₁ K ₂ K ₁ K ₁

K ₂ K ₁ K ₁ K ₁

K ₂ K ₂ K ₂ K ₁

В первых двух столбцах таблицы указаны все возможные распределения двух элементарных компонент аксиомы по двум классам, в третьем – соответствующие значения ее неэлементарной компоненты (согласно условию (1)), в четвертом – значения самой аксиомы. И здесь из рассмотрения последнего столбца таблицы сразу видно, что аксиома является тавтологией. Точно так же устанавливается тавтологичность остальных двух аксиом.

Докажем теперь, что свойство «быть тавтологией» наследственно относительно применений правила modus ponens. (Доказательство его наследственности относительно правила подстановки предоставляется читателю.) Пусть формулы S₁ и S₁ ﬤ S₂ – тавтологии; нам надо доказать, что тогда и формула S₂ есть тавтология. Допустим, что S₂ не является тавтологией. В таком случае для хотя бы одного распределения элементарных компонент этой формулы по классам K₁ и K₂ она принадлежит классу K₂. Но, по предположению, S₁ является тавтологией, т. е. принадлежит классу Ki при любых распределениях своих элементарных компонент, в том числе и при том, при котором S₂ принадлежит K₂[7]7
  Причем сказанное верно безотносительно к тому, входит ли в формулы S₁ и S₂ хоть одна общая переменная. – Прим. перев.


[Закрыть]. Но тогда при этом распределении формула S₁ ﬤ S₂ должна (в силу второго условия) принадлежать классу K₂, что, однако, противоречит предположению о тавтологичности S₁ ﬤ S₂. Противоречие показывает, что S₂ должна быть тавтологией. Таким образом, тавтологичность формулы есть свойство наследственное, т. е. передаваемое от посылок правила modus ponens к его заключению.

Теперь нам остается указать пример формулы нашего исчисления, не являющейся тавтологией. Такова, например, формула «p ˅ q», принадлежащая классу K₂, если обе ее компоненты («p» и «q») принадлежат этому классу[8]8
  Конечно, еще более простой пример – формула, состоящая из одной-единственной переменной p. – Прим. перев.


[Закрыть]. (В переводе на содержательный язык: высказывание «„p“ или q“» ложно, если ложны оба входящие в его состав высказывания «p» и «q».)

Наша цель достигнута. Мы нашли формулу, не являющуюся теоремой нашей системы. Но в случае противоречивости выбранной нами системы аксиом такой формулы в нашем исчислении не нашлось бы. Таким образом, из аксиом исчисления высказываний нельзя вывести никакой формулы одновременно с ее отрицанием. Этим и завершается абсолютное доказательство непротиворечивости исчисления высказываний.

Легко видеть, что классы K₁ и K₂ можно понимать соответственно как класс истинных и класс ложных высказываний. Мы, однако, намеренно воздерживались от этой терминологии в ходе самого доказательства (хотя не раз, комментируя отдельные ее шаги, подразумевали возможность ее использования), чтобы подчеркнуть то обстоятельство, что наше доказательство в принципе не нуждается в ссылках на какую бы то ни было интерпретацию формул исчисления высказываний, хотя понять его как следует легче именно при таком «переводе» на содержательный язык.

В заключение следует сказать еще об одной важной проблеме, относящейся к исчислению высказываний. Мы установили, что каждая теорема этого исчисления является тавтологией, т. е. – если выражаться в терминах неоднократно упоминаемой выше содержательной интерпретации – логической истиной, «законом логики». Естественно задать в известной мере и обратный вопрос: каждое ли логически истинное высказывание, выразимое на языке нашего исчисления (т. е. каждая ли тавтология), является теоремой данного исчисления (выводимой из его аксиом)? И на этот вопрос можно дать положительный ответ; но доказательство такого факта слишком длинно, чтобы приводить его здесь. Но нам хотелось бы обратить внимание на одно обстоятельство, не имеющее отношения к самому доказательству: дело в том, что результат этот свидетельствует о достаточности выбранных нами аксиом для получения всех тавтологичных формул – иными словами, всех логически истинных высказываний, выразимых на языке исчисления высказываний. Системы аксиом, обладающие таким свойством, принято называть «полными».

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

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

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

6
Идея кодирования и ее использование в математике

Исчисление высказываний представляет собой пример математической системы, по отношению к которой задачи, выдвигаемые гильбертовской теорией доказательства, оказались, как мы видели, полностью реализованными. Конечно, это исчисление формализует лишь некоторый фрагмент формальной логики, язык и дедуктивный аппарат которого недостаточны даже для формального построения элементарной арифметики. Но возможности гильбертовской программы отнюдь не ограничиваются доказательством непротиворечивости исчисления высказываний. Можно привести примеры гораздо более богатых теорий, для которых оказалось возможным дать строго метаматематические доказательства непротиворечивости и полноты. Примером может служить арифметическая система с операцией сложения (но без операции умножения) натуральных чисел, для которой также можно провести абсолютное доказательство непротиворечивости. Но достаточно ли сильны финитные методы Гильберта для установления непротиворечивости систем вроде Principia – систем, выразительные и логические средства которых позволяют построить всю арифметику, а не только отдельные ее фрагменты? Неоднократные попытки найти такое доказательство успехом не увенчались, а работа Гёделя 1931 г. показала, что они и не могли быть успешными, так как, строго придерживаясь границ, предначертанных в исходной формулировке гильбертовской программы, эту задачу вообще решить нельзя.

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

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

Это обстоятельство играет решающую роль для оценки всей работы Гёделя, и на нем стоит остановиться несколько подробнее. Математикам хорошо известны примеры общих утверждений, для которых до сих пор не найдено никакого опровергающего примера, но не найдено и доказательства. Классическим примером такого рода может служить знаменитая «теорема Гольдбаха», утверждающая, что каждое четное число можно представить в виде суммы двух простых чисел. Мы не можем указать ни одного четного числа, которое не являлось бы суммой двух простых, но у нас нет и доказательства гипотезы Гольдбаха, пригодного для всех четных чисел. Таким образом, перед нами – арифметическое утверждение, которое вполне может быть истинным, но не выводимым из аксиом арифметики. Допустим, что это действительно так (утверждать подобное мы, разумеется, не можем). Представим себе, что мы изменили или пополнили исходную аксиоматику таким образом, чтобы все истинные, но не выводимые в исходной системе предложения (к их числу относится, по сделанному только что предположению, гипотеза Гольдбаха) станут в расширенной системе выводимыми[9]9
  Такое расширение можно произвести, просто присоединив эти недоказуемые предложения к арифметике в качестве новых аксиом. Поскольку мы считаем их истинными, то отрицания их не должны и не могут быть доказуемы в арифметике; значит, такое расширение непротиворечивой системы не может сделать ее противоречивой. – Прим. перев.


[Закрыть]. Теорема Гёделя показывает, что никакое такое расширение арифметической системы не может сделать ее полной, т. е. что даже если пополнить ее бесконечным множеством аксиом, все равно в новой системе найдутся истинные, но не выводимые (хотя и выразимые!) ее средствами предложения.

^{Истинность таких предложений, как мы ниже увидим, можно установить посредством некоторого метаматематического рассуждения об арифметической системе. Но такое рассуждение не удовлетворяет требованию, согласно которому исчисление должно быть, так сказать, «замкнутой системой», т. е. все доказуемые в нем истинные предложения должны быть получены как формальные следствия из аксиом внутри самого исчисления. Таким образом, аксиоматический метод как средство построения всей содержательной арифметики оказывается принципиально ограниченным.}

Чтобы читателю было легче понять идею доказательства Гёделя, мы (следуя Гёделю) приведем вначале схему рассуждения, посредством которого получается логическая антиномия (противоречие), известная под названием «парадокса Ришара» (по имени описавшего ее в 1905 г. французского математика).

Возьмем какой-нибудь язык (например, русский)[10]10
  Конечно, у авторов речь шла об английском, а у самого Ришара – о французском языке. – Прим. перев.


[Закрыть], средствами которого можно описывать и определять все чисто арифметические свойства чисел. Рассмотрим определения, которые можно сформулировать на этом языке. Ясно, что некоторые термины, относящиеся к арифметическим свойствам, нам определить явным образом все равно не удастся (с чего-то надо начать и в определениях во избежание ситуаций, известных под названиями «порочного круга» и «бесконечного спуска»), хотя, конечно, мы можем в принципе понимать смысл этих слов и без определений. Для нашей цели несущественно, какие именно термины принять в качестве исходных, неопределяемых; мы можем, например, считать, что мы понимаем смысл предложений «целое число делится на другое целое число», «целое число является произведением двух целых чисел» и т. п. Свойство быть простым числом тогда можно определить следующим образом: «не делиться ни на одно целое число, кроме самого себя и числа 1»; свойство быть точным квадратом: «быть произведением некоторого целого числа на то же число» и т. п.

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


[Закрыть], одно из них считать предшествующим другому в обычном лексикографическом (алфавитном, словарном) порядке. Исходя из такого упорядочения можно теперь расположить все определения рассматриваемого вида в последовательность, сопоставив каждому из них единственное натуральное число – номер в этой же последовательности. Тогда самое короткое (и стоящее ранее других в алфавитном порядке) определение получит номер 1, следующее за ним в этом «словаре определений» – номер 2 и т. д.

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

^{Ситуация здесь в точности такова же, как в том случае, когда все слова в обычном орфографическом словаре делятся на два класса: односложные и многосложные; при этом слово «многосложное» само оказывается многосложным.}

Пусть, например, определяющее выражение «не делиться ни на одно натуральное число, кроме самого себя и числа 1» оказалось в нашей последовательности на 17-м месте; ясно, что сопоставленное ему число 17 само подпадает под это определение. Пусть, с другой стороны, определяющее выражение «быть произведением некоторого натурального числа на то же самое число» получило номер 15; само число 15, очевидно, не является точным квадратом и потому данным свойством не обладает. Назовем числа, не обладающие свойствами, определяемыми предложениями, которым они соответствуют в описанной нами нумерации, ришаровыми. Таким образом, «x – ришарово число» – это просто сокращение выражения «x не обладает свойством, определяемым предложением, имеющим номер x в данной словарной последовательности определяющих предложений». (Скажем, число 17 из нашего первого примера не является ришаровым, а число 15 из второго примера – ришарово.)

Теперь мы уже можем сформулировать парадокс Ришара. Определяющее выражение для свойства быть ришаровым числом описывает, очевидно, некоторое арифметическое свойство натуральных чисел. Значит, само определяющее выражение входит в описанную выше последовательность определяющих выражений. Но тогда оно имеет в этой последовательности некоторый номер, который мы обозначим через n. Зададим теперь вполне естественный вопрос (немедленно приводящий к антиномии Ришара): является ли число n ришаровым? Читатель, конечно, сразу увидит, что противоречие теперь неизбежно. В самом деле, число n является ришаровым в том и только в том случае, если оно не обладает свойством, описываемым предложением, имеющим номер n, т. е. не обладает свойством быть ришаровым! Короче говоря, n ришарово тогда и только тогда, когда оно не ришарово, т. е. утверждение «n – ришарово число» является одновременно истинным и ложным.

Следует заметить, что это противоречие в известном смысле есть трюк, который нам удался благодаря не вполне точному соблюдению правил игры. Дело в том, что мы фактически использовали одно допущение, которое, однако, предпочли в явном виде не формулировать. Мы согласились рассматривать определения чисто арифметических свойств натуральных чисел, т. е. свойств, формулируемых в терминах таких понятий, как арифметическое сложение, умножение и т. п. Затем, однако, без дополнительных оговорок мы включили в ту же последовательность определений предложение, сформулированное посредством упоминания о некотором способе записи арифметических свойств. Строго говоря, определение свойства быть ришаровым числом просто не принадлежит к той последовательности определений, которая вначале описывалась, так как это определение использует такие метаматематические понятия, как номер буквы (или вообще знака) в некоторой последовательности. Таким образом, если мы будем четко различать утверждения самой арифметики (относящиеся к числам, а отнюдь не к записям, в которые такие числа входят, т. е. к равенствам, неравенствам и вообще формулам) и утверждения относительно арифметики (т. е. как раз утверждения об арифметических формулах), то мы не получим никакого парадокса Ришара.