Классической формой парадокса лжеца является высказывание Евбулида (IV в. до н.э.): "Я лгу". Евбулид предложил своим слушателям определить, является ли это высказывание истинным или ложным. И что же получается? Если предположить, что высказывание истинно, это означало бы, что Евбулид лжет, т.е. что его высказывание ложно. Если же предположить, что высказывание Евбулида ложно, это означало бы, что он не лжет, т.е. что он говорит правду и поэтому его высказывание истинно.
Казалось бы, утверждения вроде "Я пишу" все должны иметь определенное значение истинности (истинно или ложно). "Я лгу" является таким же утверждением, однако ему нельзя приписать ни истинность, ни ложность, не впадая в противоречие. Парадоксы такого рода вызывают горячие споры вот уже более двух тысяч лет. С одной стороны, ведутся поиски "законов правильной речи", которые высказывание Евбулида "нарушает" (и поэтому его вообще нельзя считать высказыванием). С другой стороны, всякий такой новонайденный закон сразу же подвергается сомнению (либо как запрещающий наряду с парадоксами также и совсем безобидные высказывания, либо как запрещающий одни парадоксы, но допускающий другие). Нас здесь будет интересовать именно эта другая сторона, так как она раскрывает творческий потенциал, заключенный в парадоксах.
Чтобы отмести возражение, что высказывание Евбулида "слишком неясно" (не ясно, относится ли оно к себе или к другим высказываниям Евбулида, сделанным в течение его жизни), французский логик XIV в. Иоанн Буридан предложил следующую форму парадокса: обозначим через p высказывание, содержащееся в рамке:
p: p ложно
Здесь уже не может быть никаких сомнений, что к чему относится, но противоречие все равно возникает.
Для тех, кто хотел бы объявить высказывание Евбулида неправильным как относящееся к самому себе ("самоссылающееся"), немецкий логик XIV в. Альберт Саксонский предложил следующие парадоксы:
p1: p2 ложно
p2: p1 истинно
q1: q2 ложно
q2: q3 ложно
q3: q1 ложно
Здесь каждое высказывание относится не к себе, а к другому высказыванию. И тем не менее ни одно из них нельзя признать истинным или ложным, не впадая в противоречие.
Упражнение 5.1. Убедитесь, что это действительно так. (Подробнее о дискуссиях по поводу парадоксов в средние века см. книгу Н.И.Стяжкина [1967]. )
Мы можем попытаться "принять" парадокс лжеца, вводя новую, более совершенную классификацию высказываний (взамен обычного подразделения на истинные и ложные):
а) истинные высказывания,
б) ложные высказывания,
в) высказывания, не имеющие значения истинности.
Сделав это, возьмем теперь высказывание
q: q ложно или q не имеет значения истинности
Если q истинно,то q не ложно и q имеет значение истинности. Это значит, что высказывание, содержащееся в рамке, является ложным ..., но это и есть q! Аналогично, если q ложно, то q истинно. Наконец, если q не имеет значения истинности, то q истинно! Наша классификация высказываний опять не является исчерпывающей. (Последний парадокс принято называть Усиленным Лжецом.)
Упражнение 5.2. Вводя свою классификацию, мы по существу пытались заменить обычную двузначную логику трехзначной. С этой точки зрения, Лжец - парадокс двузначной, Усиленный Лжец - парадокс трехзначной логики. Сформулируйте аналогичные парадоксы для четырехзначной логики и т.д.
Попытаемся воспроизвести рассмотренные выше парадоксы средствами теории EA. Чтобы воспроизвести классический парадокс лжеца, мы должны построить формулу Q, "утверждение" которой состояло бы в том, что "Q можно опровергнуть в EA" (в теории EA ложным считается то, что можно опровергнуть исходя из аксиом). Но как добиться, чтобы формула относилась к себе самой, "говорила о себе"?
Формулы EA "умеют говорить" только о натуральных числах. Чтобы формула Q могла говорить "о формулах и о себе", все формулы должны быть закодированы натуральными числами. С этой целью нумеруем сначала все символы языка EA (будем считать, что переменные EA образованы из символов x, a следующим образом: x, xa, xaa,... ):
X a 0 1 + * = ( ) ~ & v -> E A
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Тогда всякая формула EA становится последовательностью натуральных чисел, например, x=1 превращается в 0,6,3. С помощью бета-функции Геделя любую такую последовательность можно закодировать двумя натуральными числами (впереди каждой последовательности ставится ее длина). Формулу x=1, например, кодируют числа a, b такие, что
beta(a, b, 0)=3 (длина формулы),
beta(a, b, 1)=0, beta(a, b, 2)=6, beta(a, b, 3)=3.
Мы знаем, что такие числа a, b существуют. Пару (a, b) легко закодировать одним числом, например
c = (a+b)2 +a
Упражнение 5.3. а) Покажите, как по числу c восстановить числа a, b.
б) Оцените сверху код формулы 0+1=1.
Итак, каждую формулу F из языка EA мы умеем кодировать одним натуральным числом. Соответствующий этому числу терм EA будем обозначать через F и называть геделевым номером F (в честь К.Геделя, который первым ввел кодирование формул числами, чтобы получить возможность "говорить" о формулах на языке арифметики). По формуле F мы умеем строить ее номер F, а по номеру - восстанавливать саму формулу.
Если теперь для некоторой формулы A(x) и другой формулы B удается установить, что EA|- A(B), можно сказать: в теории EA доказано, что формула B "обладает свойством A". Если же удастся установить -
EA|- B <-> A(B),
то получится: формула B "утверждает", что... она обладает свойством A.
ЛЕММА ОБ АВТОССЫЛКАХ. Для любой формулы A(x) из языка EA, имеющей единственную свободную переменную x, можно построить замкнутую формулу B (из языка EA), такую, что EA|- B <-> A(B).
Д о к а з а т е л ь с т в о. Введем следующую так называемую функцию подстановки sub(x,y). Ее значением является геделев номер формулы, полученной из формулы с номером x -подстановкой вместо всех свободных переменных терма y. Если x - не номер формулы, мы полагаем sub(x,y) = 0 для всех y.
Вне всякого сомнения, sub(x,y) - вычислимая функция. В самом деле, зная x, можно проверить, является ли x номером формулы. Если нет - полагаем значение функции равным нулю, если является - восстанавливаем по x формулy, находим ее свободные переменные и подставляем вместо них терм y. Наконец, находим номер полученной формулы, который и будет значением функции. Мы могли бы написать программу для вычисления sub(x,y), скажем, на языке Pascal (это была бы большая работа, но не очень трудная). Несколько труднее написать для вычисления sub(x,y) программу машины Тьюринга. Заниматься в деталях этим делом (осуществимость которого ясна каждому сколько-нибудь опытному программисту) мы здесь не будем. Лучше этого сошлемся на тезис Черча, согласно которому всякая функция, вычислимая в интуитивном смысле этого слова, вычислима и на подходящей машине Тьюринга.
Итак, будем считать, что машина Тьюринга, вычисляющая функцию sub, построена. Используя эту машину и следуя конструкциям, изложенным в доказательстве теоремы о представимости, можно построить в языке EA формулу SUB(x,y,z) такую, что для всех k, m, n: если sub(k,m)=n, то
а) EA|- SUB(k,m,n),
б) EA|- ~(z=n) -> ~SUB(k,m,z).
Имея формулы SUB и A(x), введем, следуя К.Геделю, формулу A1(x):
(Az)(SUB(x,x,z) -> A(z)).
Обратите внимание на повторение переменной x - это ключевая идея! Что же "утверждается" формулой A1(x)? Если взять формулу с номером x и подставить вместо ее свободных переменных терм x (т.е. номер самой формулы), то получится формула, обладающая свойством A. (Мы знаем, что формуле SUB(x, y, z) удовлетворяет единственное z для каждого x, поэтому квантор Az является здесь не более чем декорацией, которая, однако, необходима, поскольку в языке EA нет специального символа для функции sub. ) Таким образом, в формуле A1(x) идет речь о некоторой операции подстановки, причем утверждается, что результат подстановки будет обладать свойством A. Попытаемся применить эту операцию к самой формуле A1(x). Обозначим через n номер этой формулы и подставим терм n вместо x. Полученную формулу A1(n) обозначим через B. Что же "утверждается" в B?
"Если взять формулу с номером n (т.е. A1(x)) и подставить вместо x ее номер (т.е. терм n), то получится формула (A1(n), т.е. B), обладающая свойством A".
Итак, B "утверждает", что она обладает свойством A! Проследите еще два-три раза за этим рассуждением.
Чтобы завершить доказательство леммы об автоссылках, мы должны доказать в EA, что действительно B<->A(B).
1. Покажем, что EA |- B -> A(B). Значение sub(n, n) равно номеру формулы B, т.е. по определению представимости
EA|- SUB(n, n, B), EA|- ~(z=B) -> ~SUB(n, n, z) (1)
Чтобы воспользоваться теоремой дедукции, возьмем в качестве гипотезы формулу B, т.е. (Az)(SUB(n, n, z) -> A(z)). Согласно (1) число z может быть равно только B, т.е. (чисто логическими рассуждениями) мы выводим отсюда A(B). По теореме о дедукции это означает, что EA |- B -> A(B).
2. Покажем, что EA |- A(B) -> B. Имея A(B) в качестве гипотезы, получаем формулу SUB(n, n, B) -> A(B). С учетом (1): (Az)(SUB(n, n, z) -> A(z)), но это и есть формула B. По теореме дедукции отсюда следует, что EA |- A(B) -> B.
Лемма об автоссылках доказана.
Таким образом, для любого свойства формул, которое мы умеем изобразить средствами EA, можно подобрать замкнутую формулу, "утверждающую", что она этим свойством обладает.
Об авторстве. В своей знаменитой работе, опубликованной в 1931 г., К.Гедель использовал конструкцию, которая составляет доказательство леммы об автоссылках, однако в общем виде он эту лемму не сформулировал. На возможность приведенной выше общей формулировки впервые обратил внимание Р.Карнап (см. М.Дэвис [1965]).
Упражнение 5.4 (А.Мостовский, 1961 г.). Покажите, что если A(x, y), B(x, y) - формулы EA с двумя свободными переменными, то найдутся замкнутые формулы C, D, такие, что
EA|- C<->A(C, D), EA|- D<->B(C, D).
Если на самом деле A зависит только от y, а B - только от x, получается, что C и D "наговаривают друг на друга".
5.3. Теорема Геделя о неполноте
Итак, лемма об автоссылках позволяет, по-видимому, воспроизвести парадокс лжеца средствами EA. Какие это будет иметь последствия? Противоречие?
Формула-аналог утверждения "Я лгу" должна утверждать: "Меня можно опровергнуть в EA" (вместо истинности и ложности в EA фигурируют доказуемость и опровержимость). Если
F: "~F доказуема в EA",
то
~F: "~F недоказуема в EA",
поэтому с тем же успехом мы можем рассматривать формулу
F: "F недоказуема в EA", (1)
она также "равносильна" парадоксу лжеца. Именно такой формулой занимался в свое время К.Гедель, и мы не будем нарушать традицию.
Формулу (1) мы могли бы получить из леммы об автоссылках, если бы сумели изобразить в виде формулы EA свойство "формулу с номером x можно доказать в EA".
Понятие формулы мы уже "вложили" в EA - каждая формула кодируется натуральным числом (ее номером). Доказательство в теории EA - это последовательность формул, удовлетворяющая специальным условиям. Если формулы представлены числами, то доказательства превращаются в последовательности чисел. Действуя так же, как в случае формул, мы можем закодировать одним натуральным числом любую последовательность формул. Это число естественно называть геделевым номером данной последовательности.
Разумеется, по номеру можно определить, является ли он номером доказательства, принадлежащего теории EA. В самом деле, по номеру последовательности можно восстановить все входящие в нее формулы и порядок их расположения. Затем мы можем проверить, является ли каждая из этих формул аксиомой EA (логической или собственной) или же она получена из предыдущих формул последовательности с помощью правил вывода. Если для всех формул это так - анализируемый номер представляет доказательство. Можно построить даже машину Тьюринга, реализующую эту процедуру проверки без всякого вмешательства человека.
Таким же образом можно установить разрешимость предиката "y является номером EA-доказательства формулы с номером x". По теореме о представимости найдется формула, выражающая в EA этот предикат. Обозначим ее через PRF(x, y) (proof - доказательство).
Теперь можем построить формулу, которая утверждает "Меня нельзя доказать в EA". Взяв в лемме об автоссылках формулу ~(Ey)PRF(x, y) (т.е. "формула с номером x не имеет доказательства в EA"), получим замкнутую формулу G, такую, что
EA|- G <-> ~(Ey)PRF(G,y). (2)
Действительно, "утверждение" G состоит в том, что "G недоказуема в EA".
Попытаемся теперь выяснить, истинно или ложно то, что G "утверждает". С точки зрения теории EA истинно то, что доказуемо из аксиом EA, а ложно - то, что опровержимо с помощью этих аксиом. -
1. Предположим, что EA|- G. Пусть тогда n - номер доказательства формулы G. Формула PRF(x, y) выражает в EA предикат "y есть доказательство для x", поэтому EA |- PRF(G, n), а также - EA |- (Ey)PRF(G, y). Однако согласно (2) эта последняя формула эквивалентна ~G, т.е. получаем, что EA |- ~G.
Итак, если дано доказательство (средствами EA) для формулы G, то найдется также доказательство и для отрицания ~G, т.е. теория EA окажется в таком случае противоречивой. Ну, а "на самом деле" - G доказуема в EA? Этого мы не знаем. Если EA непротиворечива, то G нельзя доказать в EA. А "на самом деле" - EA непротиворечива? Этого мы также не знаем.
2. Предположим теперь, что EA|- ~G. Согласно (2) - EA |- (Ey)PRF(G, y). В нашем интуитивном понимании формула (Ey)PRF(G, y) утверждает, что в EA существует доказательство формулы G. Это вроде бы опять должно означать, что теория EA противоречива. Не может ли случиться, однако, что, доказав средствами EA формулу -(Ey)PRF(G, y), мы, тем не менее, не в состоянии найти конкретное значение y? Разве, перебирая подряд: 0,1,2,..., мы не должны натолкнуться однажды на номер доказательства G?
К сожалению, у нас нет достаточных оснований для такого заключения. Если мы найдем номер доказательства G, то теория EA окажется противоречивой. Hо если не найдем? Тогда никакое n не будет номером EA-доказательства формулы G, т.е. для любого n: EA |- ~PRF(G, n). С другой стороны, мы знаем, что EA |- (Ey)PRF(G, y). Противоречие? Не совсем, поскольку формула (Ey)PRF(G, y) противоречит формуле (Ay)~PRF(G, y), но ее мы еще не доказали в EA. Все, что мы имеем пока, это бесконечная серия отдельных доказательств: для ~PRF(G, 0), для ~PRF(G, 1) и т.д. Можем ли мы надеяться свернуть всю серию в единое конечное EA-доказательство формулы (Ay)~PRF(G, y)? До сих пор это никому не удалось.
Итак, из предположения EA |- ~G мы не сумели вывести противоречие в теории EA. Максимум, что мы можем утверждать: если EA|- ~G, то найдется формула C(y) с одной свободной переменной y такая, что
а) EA|- (Ey)C(y),
б) для каждого n: EA|- ~C(n).
Формула C(y) не дает "настоящего" противоречия (доказательства формулы вместе с ее отрицанием). Однако, если подобная формула C(y) имеется, это означает все же, что в EA "не все в порядке". "Непорядок" такого рода принято называть w-противоречием. (Это понятие было введено К.Геделем в ходе рассуждений, подобных приведенным выше.)
Упражнение 5.5. Покажите, что "настоящее" противоречие (т.е. формула D такая, что EA|- D и одновременно EA|- ~D) означает также w-противоречие.
Нами доказана знаменитая
ТЕОРЕМА ГЕДЕЛЯ О НЕПОЛНОТЕ (для теории EA). Можно построить замкнутую формулу G из языка EA, такую, что
а) если G доказуема в EA, то теория EA противоречива,
б) если ~G доказуема в EA, то теория EA w-противоречива.
Почему этой теореме придается такое большое значение? Сначала несколько общепринятых терминов. Замкнутую формулу F из языка теории T называют неразрешимой в T, если ни F, ни ~F нельзя доказать средствами T (F предсказывает вполне определенное свойство "объектов" теории T, однако это предсказание нельзя средствами T ни доказать, ни опровергнуть).
Теорию, содержащую неразрешимые формулы, принято называть неполной. Отсюда и название - "теорема о неполноте".
Не следует, однако, думать, что нами доказана неполнота теории EA. Неразрешимость средствами EA формулы G будет доказана только..., если удастся доказать, что теория EA w-непротиворечива (т.е. что в ней не могут возникать w-противоречия). До тех пор мы вправе утверждать только, что доказали несовершенство аксиом EA - эти аксиомы либо w-противоречивы, либо с их помощью нельзя решить некоторые проблемы, касающиеся натуральных чисел (одна такая проблема выражена в формуле G - несмотря на все наши разговоры о том, что G "занимается" собственной доказуемостью, G - замкнутая формула в языке EA и как таковая выражает вполне определенное свойство натуральных чисел).
Несовершенную систему аксиом следует совершенствовать. Может быть, мы "забыли" какие-то важные аксиомы? Следует найти их, присоединить к аксиомам EA, и в результате мы получим... совершенную систему?
К сожалению, рассуждения К.Геделя проходят и для любого расширения EA. Как бы мы ни расширяли EA, в результате должна получиться все же некоторая формальная теория T (язык которой совпадает с языком EA) - предикат "y является номером T-доказательства формулы с номером x" должен быть разрешимым. (Возможность "механической" проверки доказательств является ли предложенный текст корректным доказательством, - это отличительная черта формальной теории.) Отсюда вытекает, что найдется формула PRFT(x, y), выражающая в EA этот предикат. Далее, по лемме об автоссылках можно будет получить замкнутую формулу GT, такую, что
EA|- GT <-> ~(Ey)PRFT(GT, y).
T.е. формула G "утверждает", что она недоказуема в теории T.
Упражнение 5.6. Покажите, что если в теории T доказуемы все теоремы EA, то
а) если формула GT доказуема в T, то эта теория противоречива,
б) если ~GT доказуема в T, то эта теория w-противоречива.
(Указание: повторите - с изменениями - рассуждения, доказывающие теорему Геделя для EA.)
Таким образом, никакие новые аксиомы не могут привести к "совершенной" системе аксиом арифметики. Метод Геделя позволяет доказать принципиальное несовершенство всякой системы аксиом арифметики: каждая такая система неизбежно является либо w-противоречивой, либо недостаточной для решения некоторых проблем, касающихся свойств натуральных чисел.
Курт Гедель (Kurt Goedel) родился 28 апреля 1906 г. в г. Брно (в то время Чехия входила в состав Австро-Венгрии и город назывался Брюнн). Высшее образование получил в Венском университете (изучал математику и физику). Там же в 1930 г. ему была присуждена ученая степень доктора философии. Свою знаменитую теорему о неполноте К.Гедель изложил 23 октября 1930 г. на заседании одной из секций Венской академии наук. Статья с развернутым изложением поступила в редакцию 17 ноября и вышла в следующем, 1931 г. (Оригинальные формулировки К.Геделя см. в книге В.А.Успенского [1982]. По поводу утверждений, что результат К.Геделя был в известной степени предвосхищен П.Финслером в 1926 г., см. статью З.А.Кузичевой [1970]. ) С 1933 по 1938 г. К.Гедель являлся доцентом математики Венского университета. Общался с философами-позитивистами Венского кружка (Р.Карнап и др.). Когда в 1938 г. Гитлер захватил Австрию, К.Гедель эмигрировал в США. С 1940 г. постоянно работал в Институте высших исследований г.Принстона (имел тесные контакты с А.Эйнштейном). Гражданство США получил в 1948 г. В 1949 г. К.Гедель предложил новый тип решения некоторых уравнений общей теории относительности, что было оценено А.Эйнштейном как "важный вклад" в эту теорию. Умер в США 14 января 1978 г.
Упражнение 5.7. Какого рода теоремы о неполноте получаются из парадоксов Альберта Саксонского, приведенных в разделе 5.1? Возьмите в помощь результат упражнения 5.4.
Понятие об w-противоречивости несколько "портит" теорему К.Геделя о неполноте. Однако сам Гедель не пытался освободиться от него, впервые это удалось только Б.Россеру в 1936 г. - в теореме Россера вместо w-противоречивости фигурирует "обычная" противоречивость.
ТЕОРЕМА ГЕДЕЛЯ В ФОРМЕ РОССЕРА. В языке всякой фундаментальной теории T найдется замкнутая формула RT ("выражающая" некоторое свойство натуральных чисел), такая, что если T|- RT или T|- ~RT , то теория T противоречива.
В этой формулировке сделано еще одно усиление теоремы о неполноте, не имеющее отношения к методу Россера. Если теорему Геделя мы обсуждали только для тех формальных теорий, язык которых совпадает с языком EA, то сейчас речь идет о теории T с произвольным языком. Это освобождает нас от подозрений, что принципиальное несовершенство всякой системы аксиом арифметики кроется в неудачном выборе языка EA. Если для теорий с языком EA было достаточно потребовать доказуемость всех теорем EA, то теперь - для теорий с произвольным языком - мы требуем относительную интерпретируемость EA в этих теориях. В разделе 3.2 мы назвали такие теории фундаментальными.
Д о к а з а т е л ь с т в о. Из упражнения 1.4 мы знаем, что фундаментальная теория в состоянии доказать только эффективно перечислимое множество формул языка EA. Построим машину Тьюринга, перечисляющую эти формулы:
F0 , F1 , F2 , F3 ,.. . (1)
(таким образом, T|- pi(Fн) для всех n, где pi - отображение, переводящее формулы EA в формулы теории T). Предикат
"формула с номером x появляется в перечислении (1) как Ft"
является разрешимым. Пусть формула PRFT(x, t) выражает в EA этот предикат (вводя обозначение PRFT , мы как бы считаем число доказательством формулы x). Разрешим также предикат
"отрицание формулы с номером x появляется в перечислении как Ft".
Формулу, выражающую в EA этот предикат, обозначим через REFT(x, t) (refutation - опровержение).
Основная идея Б.Россера состояла в следующем: вместо формулы К.Геделя GT, утверждающей: "Меня нельзя доказать в теории T", взять формулу RT , утверждающую:
"Меня легче опровергнуть, чем доказать в T".
Если под "трудностью" доказательства формулы понимать номер места, в котором она появляется в перечислении (1), то формулу Б.Россера можно получить из леммы об автоссылках, взяв в качестве A(x) формулу
(At)(PRF (x,t) -> (Ez<t)REF (x,z)).
Получится замкнутая формула QT из языка EA, такая, что
EA|- QT <-> (At)(PRFT(QT, t) -> (Ez<t)REFT(QT, z)). (2)
Покажем, что в качестве искомой формулы RT (в языке теории T) можно взять pi(QT).
1. Предположим, T|- RT . Тогда формула QT появляется в перечислении (1), скажем, под номером n. Отсюда
EA|- PRF (QT , n). (3)
Поскольку в теории T доказуемы все теоремы EA (точнее, их переводы), то в ней доказуемы также формулы (2), (3) и их следствие
(Ez<n)REFT(QT, z). (4)
Если ~QT действительно появляется в перечислении (1) под номером <n, то T|- ~RT и теория T противоречива. Если же ~QT не появляется в первых n местах перечисления (1), то
EA|- ~REFT (QT, 0)&~REFT(QT, 1)& ... &~REFT(QT, n-1).
Отсюда
EA|- ~(Ez<n)REFT(QT, z).
Эта формула, так же как (4), доказуема в теории T, вместе они дают противоречие в T, что и требовалось.
2. Предположим теперь, T|- ~RT. Тогда формула ~QT появляется в перечислении (1), скажем, под номером n. Отсюда
EA|- REFT (QT, n). (5)
Если формула Q появляется в (1) раньше ~Q , то T|- RT и получается противоречие в теории T. Если же QT не появляется в первых n местах перечисления (1), то
EA|- ~PRFT(QT, 0)&~PRFT (QT, 1)& ... &~PRFT (QT, n-1),
EA|- ~(Et<n)PRFT(QT, t). (6)
Далее, из (5) вытекает, что - - -
EA|- (At>n)(PRFT(QT, t) -> (Ez<t)REFT(QT, z)),
поскольку при t>n в качестве z можно взять n. Совместно с (6) это дает
EA|- (At)(PRFT(QT, t) -> (Ez<t)REFT(QT, z)).
Вспомнив (2), можно получить EA|- QT и T|- RT , что опять означает противоречие в теории T.
Теорема Россера доказана.
Теперь мы можем сформулировать установленный К.Геделем "принцип несовершенства" в еще более сильной форме: всякая фундаментальная теория несовершенна - она либо противоречива, либо недостаточна для решения всех возникающих в ней проблем. Фундаментальность теории здесь существенна - нефундаментальная теория может оказаться достаточной для решения всех возникающи_в ней проблем. В таких теориях "возникают", однако, только проблемы весьма специального вида (это следствие нефундаментальности, т.е. неспособности воспроизвести полноценное понятие натурального числа).
В качестве примера нефундаментальной теории можно назвать упомянутую в разделе 3.1 арифметику Пресбургера. В 1929 г. М.Пресбургер доказал полноту и непротиворечивость этой теории (полученной из EA удалением символа умножения). В силу теоремы Геделя-Россера тем самым была доказана и ее нефундаментальность.
Прежде чем перейти к методологической оценке революционного открытия, сделанного К.Геделем, представим в сжатой форме чисто математическую сторону вопроса.
Пусть T - любая фундаментальная теория (т.е. формальная теория, в которой можно воспроизвести полноценное понятие натурального числа). По методу Геделя-Россера в языке T строится замкнутая формула RT, трактующая о свойствах натуральных чисел. Если бы RT удалось доказать в теории T, то по другому методу Геделя-Россера мы сумели бы вывести в T противоречие. Если бы, с другой стороны, удалось формулу RT опровергнуть средствами T, то, по тому же методу, мы получили бы в теории T противоречие. Эти два метода - метод построения формул RT и метод, преобразующий всякое T-доказательство или T-опровержение RT в T-доказательство противоречия, и составляют чисто математическую сторону достижений К.Геделя и Б.Россера (без какой-либо философской оценки).
Итак, если T - фундаментальная теория, то T либо противоречива, либо недостаточна для решения вопроса об истинности формулы RT (некоторого утверждения о свойствах натуральных чисел). Поскольку теорию, которая неспособна доказать либо опровергнуть некоторую замкнутую формулу из своего языка, принято называть неполной, теорему Геделя-Россера можно сформулировать более кратко: всякая фундаментальная теория либо противоречива, либо неполна.
Но почему эту теорему называют теоремой о неполноте? Ведь упомянутые выше методы Геделя и Россера не дают никаких средств для решения, какая из двух возможностей имеет место в случае конкретной теории T - противоречивость или неполнота (противоречивая теория неизбежно оказывается "полной" - в ней доказуема любая формула). Поэтому, чтобы доказать "через Геделя" неполноту хотя бы одной формальной теории, нужно доказать непротиворечивость этой теории. Но мы уже знаем (см. раздел 1.6), что к доказательствам непротиворечивости следует предъявлять требования более строгие, чем к обычным математическим доказательствам: если доказывается непротиворечивость теории T, то мы вправе использовать только средства рассуждения, более надежные по сравнению со средствами, содержащимися в самой T. Но если речь идет о теории EA - о простейшей (и самой надежной) из фундаментальных теорий математики, то возможны ли еще более надежные средства рассуждения, не содержащиеся уже в EA? Если нет, то мы вынуждены доказывать непротиворечивость EA средствами самой же EA (или какой-либо "особенно надежной" частью этих средств). Возможно ли такое - теория доказывает свою собс- твенную непротиворечивость?
Чтобы подойти к решению этого вопроса, формулировку его следует уточнить, переведя в формулы. В доказательстве теоремы Геделя-Россера мы построили для фундаментальной теории T формулу PRFT(x, y) (из языка EA), выражающую в EA предикат T
"формула с номером x появляется в перечислении
множества pi-1(T) под номером t". (1)
Напомним, что pi-1(T) - множество тех формул EA, которые (после перевода в язык T) доказуемы в теории T, поэтому, формула (Et)PRFT(x, t) "утверждает", что перевод EA-формулы с номером x доказуем в T.
Мы знаем, что если теория T противоречива, то в ней доказуема любая формула, в частности, перевод формулы 0=1. И наоборот, если доказано, что перевод 0=1 недоказуем в T, то доказана и непротиворечивость теории T. Поэтому формула ~(Et)PRFT(0=1,t) "утверждает", что теория T непротиворечива. Обозначим эту формулу через Con(T) (consistent - согласована, непротиворечива).
Формула Con(T) зависит от выбора формулы PRFT. Последнюю, оказывается, можно выбрать таким образом, что соответствующая Con(T) становится легко доказуемой (здесь мы следуем книге С.К.Клини [1957], с. 473). Пусть PRFT - любая формула, выражающая в EA предикат (1). Введем другую формулу PRF'T(x, t), определяемую как конъюнкция:
PRFT(x,t) & ~PRFT(0=1,t).
Упражнение 5.8. Проверьте, что если теория T непротиворечива (т.е. перевод формулы 0=1 недоказуем в T), то формула PRF'T выражает (в смысле строгого определения выразимости) в EA предикат (1).
Соответствующее PRF'T утверждение о непротиворечивости T,обозначим через Con'(T). В развернутом виде это формула
~(Et)(PRFT(0=1,t) & ~PRFT(0=1,t)).
Но ведь для доказательства этой формулы почти достаточно исчисления высказываний! Исчисление высказываний способно доказать противоречивость любой формальной теории? Да, способно, даже если сама теория противоречива - ведь Con'(T) можно доказать, не зная ничего о теории T. Поэтому грош цена таким "доказательствам". Но в чем же причина их кажущегося "успеха"? В том, что, доказывая Con'(T), мы на самом деле не можем утверждать, что эта формула выражает непротиворечивость теории T. В упражнении 5.8 мы доказали, что формула PRF'T выражает предикат (1), предполагая, что T непротиворечива. Предполагая непротиворечивость, нетрудно... доказать ее в виде формулы Con'(T).
Из этого эксперимента можно извлечь все же один урок: нельзя, оказывается, обсуждать доказуемость (в какой-бы то ни было теории) формулы Con(T), предположив только, что эта формула получена из произвольной формулы PRFT, выражающей предикат (1). Все рассуждения такого рода проходят и для формулы Con'(T), т.е. серъезных результатов таким путем получить не удастся. Если мы собираемся анализировать, какими средствами можно или нельзя доказать Con(T), надо проследить, какие средства использовались для установления того, что соответствующая формула PRFT выражает предикат (1).
Оказывается, что если формула PRFT получена "естественным путем", т.е. путем моделирования машины Тьюринга, перечисляющей pi-1(T) (как в доказательстве теоремы о представимости), то для установления того, что эта формула выражает предикат (1), достаточно средств теории EA. Убедиться в этом с полной строгостью нелегко, хотя удивительного здесь ничего нет: ведь наши рассуждения о формулах и машинах Тьюринга идут в рамках средств, которые формализованы в EA.
Но какие средства нужны, чтобы доказать соответствующую ("естественную") формулу Con(T) (если это вообще возможно, т.е. если теория T "действительно" непротиворечива)? Предположим, что нам удалось каким-то образом доказать Con(T). Какие следствия можно извлечь отсюда? Единственными известными нам теоремами, позволяющими извлечь хотя бы какие-то выводы из непротиворечивости теории, являются теоремы о неполноте. "Если теория T непротиворечива, то формула Геделя GT недоказуема в T". Но ведь GT и "утверждает", что она недоказуема в T! Т.е. если Con(T), то GT. Формально, Con(T)->GT.
Эта импликация может быть не только формально записана, ее удается формально и доказать. Если формула PRFT (исходя из которой строятся как Con(T), так и GT) получена "естественным путем", то всегда оказывается, что
EA|- Con(T)->GT. (2)
Это неудивительно: ведь рассуждения К.Геделя используют вполне элементарные средства (но в остроумном сочетании), которые все формализованы в EA.
Если после всего этого удалось бы доказать средствами EA формулу Con(T) (т.е. непротиворечивость теории T), то в силу (2) отсюда следовало бы, что EA|- GT. Поскольку T - фундаментальная теория, то мы получили бы T|- GT. Однако из теоремы Геделя о неполноте мы знаем, что доказуемость GT влечет противоречие в теории T. Таким образом, если EA в состоянии доказать непротиворечивость T ..., то "на самом деле" T противоречива. В частности, если удастся доказать средствами EA непротиворечивость самой теории EA, то тем самым в EA будет найдено противоречие!
Этот вывод К.Геделя (его вторая теорема в исторической статье, опубликованной в 1931 г.) показывает, что программа Гильберта (см. раздел 1.6) не может быть реализована до конца. Вспомним, что программа включала два этапа:
а) построение формальный теории, охватывающей всю существующую математику,
б) доказательство непротиворечивости полученной теории (в этом доказательстве Д.Гильберт предполагал использовать только надежные средства рассуждения, не выходящие за пределы EA).
Осуществление этапа а) удалось - созданная к началу 30-х гг. формальная теория множеств Цермело-Френкеля действительно охватывает всю математику. Однако трудности, встретившиеся на этапе б), оказались принципиальными - средствами, формализованными в EA, нельзя доказать даже непротиворечивость самой EA, не говоря уже о доказательстве непротиворечивости всей математики.
Может быть, неудача Д.Гильберта объясняется узостью средств рассуждения, которые он допускал в доказательствах непротиворечивости? Обобщение результатов К.Геделя показывает, что причина лежит гораздо глубже. И этим обобщениям мы обязаны в значительной мере самому Д.Гильберту (идея приведенной ниже формулировки второй теоремы Геделя заимствована из книги "Основания математики", написанной совместно Д.Гильбертом и П.Бернайсом [1934, 1939]).
Вместо формулы PRFT(x, t), выражающей предикат (1), введем в рассмотрение формулу (Et)PRFT(x, t), которую будем обозначать через PRT(x). Очевидно, что PRT(x) означает утверждение, что перевод (pi-образ) формулы с номером x доказуем в теории T. Основное свойство формулы Геделя GT можно теперь представить так: GT - любая формула, обладающая свойством
T |- GT <-> ~PR (GT).
Формула Con(T) выражается через PRT(x) как ~PRT(0=1), где 0=1 - номер формулы 0=1.
Забудем теперь о происхождении формулы PRT(x) и будем говорить, что теория T "понимает", что формула Con(T) выражает ее непротиворечивость, если соответствующая формула PRT(x) удовлетворяет следующим условиям Гильберта: для любых формул A, B из языка EA
По условию 2) теория T "сознает", что формула PRT выражает понятие T-доказуемости: ведь смысл импликации 2) -состоит в том, что "если T |- A, то T |- PRT(A)". По условию 3) теория T "сознает", что множество ее (арифметических) теорем замкнуто относительно правила MODUS PONENS: "если T |-A и T |- A->B, то T |-B".
ВТОРАЯ ТЕОРЕМА ГЕДЕЛЯ. Пусть фундаментальная теория T "понимает", что формула Con(T) выражает ее непротиворечивость. Тогда либо T противоречива, либо Con(T) недоказуема в T.
Д о к а з а т е л ь с т в о. Проведем формальное (в теории T) доказательство первой части теоремы Геделя о неполноте: если T|- GT, то теория T противоречива. Другими словами, покажем, что
T |- PRT (GT) -> PRT(0=1). (3)
Так как T|- ~GT <->PRT(GT), то отсюда будет следовать, что T|- Con(T)->GT. Поэтому если T|- Con(T), то T|- GT, что сразу влечет противоречивость теории T.
Итак, остается доказать (3). Воспользуемся теоремой дедукции: возьмем в качестве гипотезы формулу PRT(GT) и попытаемся вывести PRT(0=1). По условию 2)
T |- PRT(GT) -> PRT(PRT(GT)).
При нашей гипотезе тогда получается PRT(PRT(GT)). Поскольку формула Геделя обладает свойством PRT(GT)->~G , то по условию 1)
T |- PRT(PRT(GT)->~GT).
По условию 3) имеем
T |- PRT(PRT(GT)) & PRT(PRT(GT)->~GT) -> PRT(~GT).
Таким образом, из нашей гипотезы выводится формула PRT(~GT). Теперь, имея в виду саму гипотезу PRT(GT), заметим, что T|- GT ->(~GT ->0=1) ("из противоречия следует все, что угодно"). Повторяя дважды проделанную только что манипуляцию с условием 3), получаем формулу PRT(0=1), что и требовалось. По теореме дедукции отсюда следует (3).
Вторая теорема Геделя доказана.,
Вернемся теперь к нашей "патологической" формуле Con (T), которую можно было доказывать почти в исчислении высказываний. Если бы формула PR'T(x), определяемая как (Et)PRF'T(x, t), удовлетворяла условиям Гильберта, то по второй теореме Геделя отсюда следовало бы, что теория T противоречива. С точки зрения нашего определения это означает, что если T непротиворечива, то она "не понимает", что Con (T) выражает ее непротиворечивость. Может доказать Con (T), но не понимает ее!
Если же формула Con(T) получена "естественным путем", то всегда оказывается, что условия Гильберта выполнены (и даже более того - для доказательств, существование которых требуется в этих условиях, достаточно средств EA). Соответственно для таких формул Con(T) справедливо и заключение второй теоремы Геделя: либо теория T противоречива, либо Con(T) нельзя доказать в T. Таким образом, если некоторая фундаментальная теория может доказать свою собственную непротиворечивость, то... эта теория противоречива. Если необходимым элементом обоснования теории считать доказательство ее непротиворечивости, этот вывод можно сформулировать еще более эффектно: фундаментальная теория не может сама себя обосновать.
Ну, а нефундаментальные теории? Они не в состоянии даже поставить "своими силами" проблему своего обоснования. Либо их язык не позволяет написать что-либо подобное формуле Con(T), либо (в случае достаточно богатого языка) их аксиомы не позволяют доказать требуемое в условиях Гильберта (по нашей терминологии, это означает, что такие теории "не понимают" свою формулу Con(T)).
В некоторых случаях одна фундаментальная теория способна доказать непротиворечивость другой ("более слабой"). Так, в теории множеств ZF можно доказать непротиворечивость EA (множество w оказывается моделью, в которой выполняются все аксиомы EA, см. приложение I). Формула Con(EA) недоказуема в EA (если эта теория непротиворечива), однако перевод ее в язык теории множеств можно доказать с помощью аксиом ZF. Формула Con(EA) - замкнутая формула языка EA, т.е. вполне определенное утверждение о свойствах натуральных чисел. Это утверждение в EA недоказуемо, но его можно доказать в теории множеств. Это ответ на вопрос, сформулированный в разделе 3.2: некоторые утверждения о свойствах натуральных чисел, требующие для своей формулировки только понятие натурального числа (и, казалось бы, касающиеся только этих чисел), требуют для своего доказательства сложные понятия, не укладывающиеся в рамки EA (более впечатляющий пример см. в приложении 2).