Текст книги "Teopeмa Гёделя"
Автор книги: Эрнст Нагель
Соавторы: Джеймс Ньюмен
Жанр:
Математика
сообщить о нарушении
Текущая страница: 2 (всего у книги 6 страниц)
Мы убедились в важности проблемы непротиворечивости (совместимости) и ознакомились с классическим, «стандартным», методом ее решения с помощью моделей. Мы видели, что проблема эта обычно требует использования бесконечных моделей, описание которых, однако, само чревато внутренними противоречиями. Нам придется согласиться поэтому, что метод моделей имеет ограниченную ценность в качестве орудия решения проблемы и недостаточен для получения окончательного ответа на нее.
3
Абсолютные доказательства непротиворечивости
Принципиальные ограничения, препятствующие использованию моделей для установления непротиворечивости и перерастающие в уверенность подозрения, что многие математические системы чреваты внутренними противоречиями, привели к тому, что были предприняты совершенно новые попытки решения проблемы непротиворечивости. Альтернативный – по отношению к упоминавшимся до сих пор доказательствам относительной непротиворечивости– подход был указан Гильбертом. Его целью было построение «абсолютных» доказательств непротиворечивости различных систем – доказательств, не исходящих из предположений о непротиворечивости какой-либо другой системы. Чтобы понять сущность открытия Гёделя, нам понадобится разобраться в общих чертах в гильбертовском подходе к проблеме.
Первым шагом построения абсолютного доказательства непротиворечивости, согласно такому подходу, должна явиться полная формализация исследуемой дедуктивной системы, состоящей, грубо говоря, в том, что все входящие в данную, систему выражения рассматриваются как лишенные какого бы то ни было значения – просто как некоторые сочетания символов. Способы соединения символов и обращения с составленными из них выражениями четко предусмотрены специальными правилами. В результате мы получаем систему символов (называемую «исчислением»), содержащую все те и только те символы, на которые мы явным и недвусмысленным образом указали. Постулаты и теоремы полностью формализованной системы – просто «строчки» (т. е. конечные последовательности) ничего не означающих значков, достроенные из элементарных символов согласно правилам данной системы. В такой полностью формализованной системе вывод теорем из постулатов – не что иное, как преобразование (согласно правилам системы) одной совокупности «строчек» в другую. Поступая таким образом, мы избегаем опасности, связанной с неявным использованием каких-либо сомнительных методов рассуждения.
Формализация – дело довольно-таки трудное и требующее немалой изобретательности; но она хорошо служит намеченной задаче. Формализация позволяет ясно видеть структуру системы и назначение отдельных ее элементов аналогично тому, как структура и работа отдельных узлов какой-нибудь машины легче уясняются на модели такой машины, чем при рассмотрении самой машины. Логические соотношения между отдельными предложениями становятся после формализации хорошо обозримыми; мы видим в ней структурные соотношения между различными «строчками» и «бессмысленными» символами, уясняем, каким образом они связаны друг с другом, правила их комбинации и взаимного следования и т. п.
До сих пор мы говорили, что «бессмысленные» значки такой формализованной математики ничего не утверждают– это пока просто некая абстрактная картинка, иллюстрирующая строение интересующей нас системы. Но, конечно, строение такой картинки – а тем самым и иллюстрируемой ею системы – мы можем описывать на обычном человеческом языке, делая определенные высказывания, относящиеся к ее общей конфигурации и соотношениям отдельных ее элементов.
Мы можем, например, отметить простоту или симметричность какой-нибудь «строчки», сходство ее с некоторой другой «строчкой» можем заметить, что одна «строчка» может быть представлена в виде сочленения трех других «строчек» и т. п. Такие высказывания, безусловно, осмыслены и, более того, могут выражать весьма существенную информацию о нашей формальной системе. Следует, однако, сразу же отметить, что все эти осмысленные высказывания о бессмысленной (или, что то же самое, – формализованной) математике никоим образом не принадлежат сами по себе этой математике. Они относятся к области, которую Гильберт назвал «метаматематикой», к языку, на котором говорят о математике. Метаматематические высказывания – это высказывания о символах, входящих в формализованную математическую систему (т. е. в исчисление), о видах символов, об их упорядочении внутри формальной системы, о способах составления из этих символов более длинных знакосочетаний («строчек»), которые естественно называть «формулами» системы, наконец, о соотношениях между формулами, в частности о том, какие формулы могут быть получены (по фиксированным нами правилам обращения с ними) в качестве «следствий» других формул.
Приведем несколько примеров, иллюстрирующих различие между математикой и метаматематикой. Скажем, выражение «2+3=5» принадлежит математике (арифметике) и строится исходя лишь из элементарных арифметических символов, в то время как высказывание «„2+3=5“ есть арифметическая формула» утверждает нечто об этом выражении. Оно само по себе не выражает никакого арифметического факта и не принадлежит формальному языку арифметики, а относится к метаматематике, характеризуя некоторую строчку, составленную из арифметических символов, как формулу.
Формулы
x = x,
0 = 0,
0 ≠ 0
принадлежат математике (арифметике); каждая из них составлена из одних только арифметических знаков. Высказывание же «„x“ есть переменная» относится уже к метаматематике, поскольку оно характеризует некоторый арифметический символ, утверждая, что он принадлежит некоторому специальному классу символов (а именно, классу переменных). Принадлежит метаматематике и высказывание «формула „0 = 0“ выводима из формулы „x = x“ посредством подстановки „0“ вместо переменной, x“», описывающее определенное отношение между некоторыми двумя формулами. Относится к метаматематике и утверждение «„0 ≠ 0“ не есть теорема», гласящее, что некоторая арифметическая формула не может быть выведена из аксиом арифметики. Метаматематике, конечно, принадлежит и высказывание «арифметика непротиворечива» (иными словами, из аксиом арифметики нельзя вывести двух взаимно противоречивых формул, например формул «0 = 0» и «0 ≠ 0»). Ясно, что это высказывание гласит нечто об арифметике, а именно, оно утверждает, что пары арифметических формул определенного вида не находятся в определенном отношении к формулам, составляющим систему аксиом арифметики.
Следует отметить, что все эти метаматематические высказывания не содержат никаких математических знаков и формул, а содержат лишь их имена. Различие между выражениями и именами выражений очень важно. Кстати, и в обычном разговорном языке никакое предложение не содержит объектов, о которых в нем говорится, – оно содержит лишь их имена. Скажем, когда мы говорим о каком-нибудь городе, то мы вставляем в предложение не сам город, а его имя (название). Точно так же, если мы хотим сказать что-нибудь о каком-либо слове (или вообще любом языковом выражении), то мы должны использовать в качестве члена предложения не само слово/выражение, а его имя. Обычно это делается при помощи кавычек. Наше изложение как раз и следует этому обычаю. Мы можем сказать, например, «Чикаго – большой город». Но фраза «Чикаго состоит из трек слогов» бессмысленна (безграмотна). Чтобы выразить последнее утверждение правильно, мы должны написать: «„Чикаго" состоит из трех слогов».
Точно так же неверно было бы написать:
«x = 5 есть уравнение».
Правильная запись такова:
«„x = 5" есть уравнение».
Конечно, различие между теорией и метатеорией может относиться не только к математике – ведь это просто хорошо известное всем нам различие между каким-либо изучаемым нами предметом и разговорами об этом предмете. Например, высказывание «у птиц из рода плавунчиков яйца высиживают самцы» относится к предмету, изучаемому зоологами, и принадлежит зоологии; но если мы скажем, что утверждение относительно плавунчиков показывает, что в зоологии есть много загадочного, то это уже будет утверждение не о плавунчиках, а о предыдущем высказывании, и дисциплину, в которую входит такое суждение, следовало бы назвать метазоологией.
Точно таково же соотношение между математикой и метаматематикой: предмет первой составляют сами формальные системы, которые придумывают математики, предмет второй – описание таких формальных систем, выяснение и обсуждение их свойств.
Важность столь настоятельно подчеркиваемого нами различения математики и метаматематики трудно переоценить. Игнорирование или недооценка этого различения приводят к недоразумениям, а то и к прямым противоречиям. Осознание его важности позволило глубже уяснить логическую структуру математических методов рассуждения и четко регламентировать употребление различных формальных символов, превращая математику в чисто формальное исчисление, свободное от всяческих неявно подразумеваемых допущений и побочных смысловых ассоциаций. Только на базе таких новых представлений стало возможным дать точные определения математических операций и логических правил, которыми математики пользовались до тех пор без ясного понимания того, что же, собственно, они делают.
Гильберт уловил самую суть проблемы, положив в основу своих попыток построения «абсолютных» доказательств непротиворечивости различие между формальным исчислением и его описанием. Он поставил задачу развития специального метода, с помощью которого можно было бы проводить доказательства непротиворечивости той же степени убедительности, что и доказательства, использующие конечные модели, на которых реализуются определенные системы постулатов. Искомый метод должен был бы состоять в исчерпывающем анализе конечного числа структурных свойств выражений в полностью формализованных исчислениях. Анализ должен исходить из точной фиксации различных видов, входящих в рассматриваемое исчисление символов, указания на способы соединения этих символов в формулы, описания способа вывода одних формул из других и давать способ решения вопроса, выводимы ли формулы какого-либо определенного вида из некоторых определенных формул посредством явно сформулированных правил оперирования с формулами. Гильберт был убежден в том, что каждое математическое исчисление можно представить «на геометрический манер», т. е. в виде такой совокупности формул, каждая из которых связана с любой другой формулой того же исчисления лишь структурными соотношениями из некоторого конечного перечня соотношений.
На этом убеждении и основывался его расчет, что он сумеет посредством систематического и исчерпывающего обозрения этих структурных свойств выражений данной системы показать, что из аксиом данного исчисления нельзя получить формально противоречащие друг другу формулы. Существеннейшим условием гильбертовской программы в первоначальной ее формулировке было разрешение употреблять в доказательствах непротиворечивости лишь такие приемы рассуждений, которые ни в какой форме не используют ни бесконечного множества структурных свойств формул, ни бесконечного множества операций над формулами.
Такие методы рассуждений он назвал «финитными», а доказательства непротиворечивости, проведенные финитными средствами, – «абсолютными». «Абсолютное» доказательство достигает своей цели с помощью некоторого минимального арсенала принципов вывода и не исходит из непротиворечивости никакой другой системы аксиом. Таким образом, если бы, например, удалось получить абсолютное доказательство непротиворечивости арифметики, оно должно было бы посредством некоторой финитной метаматематической процедуры установить невозможность одновременного вывода из аксиом (т. е. из исходных формул) арифметики с помощью фиксированных правил вывода никакой пары взаимно противоречивых формул, скажем «0 = 0» и ее отрицания «~ (0 = 0)» (здесь знак «~» означает «не»).
Вполне точных указаний на то, какие именно математические методы следует считать «финитными», Гильберт не дал. В первоначальной формулировке его программы требования, которым должны были удовлетворять абсолютные доказательства непротиворечивости, были значительно более сильными, чем в последующих разъяснениях гильбертовской программы, данных представителям школы Гильберта.
Будет, пожалуй, небесполезно сравнить метаматематику, понимаемую как теорию доказательства, с теорией шахматной игры. В шахматы играют с помощью 32 фигур определенного вида, передвигающихся по квадратной доске, разделенной на 64 клетки, причем передвижения эти («ходы») совершаются по некоторым строго определенным правилам. Разумеется, для игры не требуется никакой «интерпретации» фигур и их различных положений на доске, хотя такую интерпретацию при желании можно было бы и придумать. Например, можно было бы считать, что пешки – это армейские полки, а клетки доски – определенные географические районы и т. п. Но такого рода соглашения (интерпретации) не употребительны – на самом деле ни фигуры, ни клетки доски, ни положения фигур не означают ровно ничего вне игры как таковой. Иначе говоря, можно было бы сказать, что фигуры и их положения на доске «бессмысленны». Таким образом, игра в шахматы является далеко идущим аналогом формализованного математического исчисления. Фигуры и клетки доски соответствуют элементарным символам исчисления; допустимые правилами игры позиции соответствуют формулам исчисления; начальная позиция партии (или любой шахматной задачи) соответствует набору аксиом исчисления; последующие позиции – формулам, выводимым из аксиом (т. е. теоремам); наконец, правила игры соответствуют правилам вывода (правилам преобразования) исчисления. Аналогия простирается и дальше. Хотя сами по себе позиции (расположения фигур на доске), подобно формулам исчисления, «бессмысленны», высказывания об этих позициях, подобно метаматематическим высказываниям о формулах, вполне осмысленны.
«Меташахматное» утверждение может, например, гласить, что в данной позиции у белых возможны двадцать различных ходов, или, скажем, что в данной позиции белые, начиная, могут заматовать черных за три хода. Более того, можно говорить и об общих «меташахматных» теоремах, в доказательствах которых используется наличие лишь конечного числа возможных позиций. Можно, например, получить теорему относительно числа возможных ходов для белых в начальной (или любой другой) позиции; или, скажем, доказать теорему, согласно которой два белых коня с королем не могут форсировать мат одинокому черному королю. Эти и другие «меташахматные» теоремы удается, таким образом, доказывать, пользуясь финитными методами рассуждений, т. е. исследуя лишь конечное число возможных позиций, удовлетворяющих четко сформулированным условиям. Совершенно аналогично цель гильбертовской теории доказательства состоит в доказательстве такого же рода финитными методами невозможности вывода противоречащих друг другу формул в данном математическом исчислении.
4
Систематическое построение формальной логики
Прежде чем перейти к самой теореме Гёделя, нам придется преодолеть еще два препятствия. Прежде всего нам надо разобраться, зачем, собственно, ему понадобилась Principia Mathematica Уайтхеда и Рассела и в чем суть этой системы; далее, нам понадобится рассмотреть в качестве примера формализации дедуктивной системы один небольшой фрагмент системы Principia,и показать, как можно получить абсолютное доказательство непротиворечивости этого фрагмента.
Обычно, даже если математические доказательства проводятся с соблюдением общепринятых норм профессиональной строгости, эта строгость существенно умаляется в результате некоторого упрощения весьма принципиального характера. Дело в том, что принципы (правила) вывода, употребляемые в доказательствах, в явной форме не формулируются, так что математики применяют их не вполне осознанно. Возьмем, например, евклидовское доказательство того факта, что не существует наибольшего простого числа (целое число, как известно, называется простым, если оно не делится без остатка ни на одно число, кроме единицы и самого себя). Доказательство, проводимое методом reductio ad absurdum (от противного), выглядит следующим образом.
Пусть, в противоречии с доказываемым утверждением, имеется наибольшее простое число. Обозначим его через «x». Тогда:
1. x есть наибольшее простое число.
2. Образуем произведение всех простых чисел, меньших или равных x, и прибавим к этому произведению число 1. В результате получим некоторое число y:
y = (2 × З × 5 × 7 × … × x) + 1.
3. Если у само есть простое число, то x не есть наибольшее простое число, так как у, очевидно, больше x.
4. Если y – составное число (т. е. не является простым), то и тогда х не есть наибольшее простое число; в самом деле, если у – составное, то оно должно иметь некоторый простой делитель z; но z непременно должно быть отличным от всех простых чисел 2, 3, 5, 7, …, x, меньших или равных x, так что z должно в этом случае быть простым числом, превосходящим x.
5. Но у есть либо простое, либо составное число.
6. Следовательно, x не есть наибольшее простое число.
7. Наибольшего простого числа не существует.
Мы выписали здесь только основные шаги доказательства. Можно, однако, показать, что для восполнения всей цепочки рассуждений так или иначе пришлось бы использовать некоторые неявно подразумеваемые правила вывода и законы (теоремы) логики. Некоторые из этих правил и законов принадлежат самой элементарной части формальной логики, другие – более высоким ее разделам, например правила и законы, составляющие так называемую «теорию квалификаций». В этой теории формулируются правила употребления «кванторных» оборотов речи, вроде «все», «некоторые» и их синонимов. Приведем здесь примеры элементарной логической теоремы и правила вывода, используемые, хотя и неявно, в приведенном выше доказательстве теоремы Евклида.
Обратите внимание на 5-й шаг этого доказательства. Откуда он, собственно, получен? – Из логической теоремы («необходимой истины»), согласно которой «либо p, либо не p», где через «p» обозначена переменная («пропозициональная переменная»). Но как же именно 5-й шаг доказательства получается из этой теоремы? Посредством правила вывода, называемого «правилом подстановки вместо пропозициональных переменных», согласно которому из любого высказывания можно вывести другое высказывание, подставляя вместо каждого вхождения в исходное высказывание некоторой пропозициональной переменной (в нашем примере переменной «p») любого (одного и того же) высказывания (в рассматриваемом случае высказывания «y – простое число»). Применение такого рода правил и логических теорем, как мы уже отмечали, происходит на каждом шагу, но часто совершенно неосознанным образом. Явная же формулировка правил (даже для столь простого случая, как теорема Евклида) есть достижение лишь последнего столетия в истории логики.
Подобно мольеровскому господину Журдену, всю жизнь говорившему прозой, но не подозревавшему об этом обстоятельстве, математики в течение по крайней мере двух тысячелетий обходились без точной формулировки принципов, лежащих в основе всех их рассуждений. Понимание подлинной природы таких принципов – достижение самого недавнего времени.
Почти две тысячи лет аристотелевская теория правильных форм логического вывода безоговорочно считалась исчерпывающей и не нуждающейся в дальнейшей разработке. Еще в 1787 г. Иммануил Кант говорил, что формальную логику Аристотеля «не продвинешь дальше ни на один шаг – это наиболее завершенная и полная из всех наук». На самом же деле традиционная логика существеннейшим образом не полна, и средств ее недостаточно для обоснования многих принципов вывода, используемых даже во вполне элементарных математических рассуждениях.
Простым примером могут служить принципы, используемые при следующем выводе: 5 > 3, следовательно, 52 > 32.
Возрождение логических исследований в новое время началось с опубликования «Математического анализа логики» Джорджа Буля (1847). Буль и его последователи занимались прежде всего разработкой так называемой алгебры логики, посвященной выяснению и уточнению более общих и более разнообразных типов логической дедукции, нежели подпадающие под традиционные логические принципы. С помощью булевой техники легко выражаются, конечно, и традиционные умозаключения.
Другое направление исследований, тесно связанное с разработкой математиками XIX столетия проблематики оснований анализа, также оказалось близким программе Буля. Целью нового направления было представить всю чистую математику как часть формальной логики. Классическое выражение эта линия развития логики и математики получила в Principia Mathematica Уайтхеда и Рассела (1910–1913). Математикам XIX-го столетия удалось «арифметизировать» алгебру и так называемое «исчисление бесконечно малых», показав, что различные понятия, используемые в математическом анализе, определимы исключительно в арифметических терминах (т. е. в терминах целых чисел и арифметических операций над ними). Например, вместо того чтобы допускать мнимое число √-1 в качестве некоей мистической «сущности», его стали определять как упорядоченную пару целых чисел (0,1), причем над такими парами разрешено было производить определенного рода операции «сложения» и «умножения». Аналогично, иррациональное число √2 теперь стали определять как некоторый класс рациональных чисел, а именно, как класс рациональных чисел, квадраты которых меньше 2. Рассел же (а еще ранее немецкий математик Готтлоб Фреге) поставил своей целью показать, что все арифметические понятия можно определить в чисто логических терминах, а все аксиомы арифметики вывести из небольшого числа предложений, которые можно было бы квалифицировать как чисто логические истины.
Приведем пример. В логике имеется понятие класса. Два класса, по определению, «подобны», если между их членами можно установить взаимно-однозначное соответствие (причем понятие взаимно-однозначного соответствия само может быть определено в терминах других логических понятий). Класс, имеющий единственный член, называется «единичным классом» (таков, например, класс естественных спутников Земли); кардинальное (количественное) число 1 определяется как класс всех классов, подобных какому-либо единичному классу. Аналогично можно определить и другие кардинальные числа; различные арифметические операции (сложение, умножение и т. д.) также можно определить через понятия формальной логики. Произвольное арифметическое утверждение (скажем, «1 + 1 = 2») можно теперь представить как сокращенную запись некоторого утверждения, составленного исключительно из выражений, принадлежащих обычной логике, и все такие чисто логические утверждения, как можно показать, выводимы из некоторой системы логических аксиом.
Таким образом, Principia Mathematica явилась существенным продвижением в решении проблемы непротиворечивости математических систем, в частности арифметики, в том смысле, что посредством этой системы P. M. было достигнуто некоторое сведение упомянутой проблемы к проблеме непротиворечивости самой формальной логики. В самом деле, если аксиомы арифметики суть просто-напросто сокращенные записи некоторых теорем логики, то вопрос о том, совместимы ли арифметические аксиомы, эквивалентен вопросу о совместимости основных логических аксиом.
Далеко не все математики (по разным причинам) согласились с тезисом Фреге-Рассела, согласно которому математика есть не что иное, как часть логики. Кроме того, как мы уже отмечали, антиномии канторовской теории бесконечных множеств, если не принять специальных мер предосторожности, легко воспроизводятся и в рамках чистой логики. Но независимо от степени приемлемости самого по себе тезиса Фреге-Рассела два достоинства системы P. M. позволяют считать ее неоценимым достижением на пути к дальнейшему изучению проблемы непротиворечивости. В Principia разработана замечательная своей краткостью система обозначений, при помощи которой все предложения чистой математики (в частности, арифметики) могут быть записаны некоторым стандартным образом. Кроме того, в этой книге явным образом сформулировано большинство правил вывода, используемых в математических доказательствах (быть может, известных и ранее, но не в столь точном и полном виде). Резюмируя, можно сказать, что в Principia создан весьма совершенный инструмент для исследования всей системы арифметики как неинтерпретированного исчисления, т. е. как системы бессмысленных значков, из которых посредством точно сформулированных правил образуются и преобразуются «строчки» знаков – формулы.
