Эрнст Нагель - Teopeма Гёделя

• Название: Teopeма Гёделя
• Автор: Эрнст Нагель
• Издательство: КРАСАНД
• Жанр: Математика
• Год: 2010
• ISBN: 978-5-396-00092-6

Нагель Эрнест, Ньюмен Джеймс Рой. Теорема Гёделя: Пер. с англ. Изд. 2-е, испр. — М.: КРАСАНД, 2010. — 120 с. (НАУКУ — ВСЕМ! Шедевры научно-популярной литературы.)

Вниманию читателя предлагается книга известного американского логика Э. Нагеля и опытного популяризатора науки Дж. Р. Ньюмена, посвященная теореме Гёделя о неполноте. Эта теорема была изложена в небольшой статье К. Гёделя, которая впоследствии сыграла решающую роль в истории логики и математики. Авторы настоящей книги, не пытаясь дать общий очерк идей и методов математической логики, строят изложение вокруг центральных, с их точки зрения, проблем этой науки — проблем непротиворечивости и полноты. Доказательство того факта, что для достаточно богатых математических теорий требования эти несовместимы, и есть то поразительное открытие Гёделя, которому посвящена книга. Не требуя от читателя по существу никаких предварительных познаний, авторы с успехом объясняют ему сущность одной из самых замечательных и глубоких теорем математики и логики.

Для специалистов по математической логике, студентов и аспирантов, а также всех заинтересованных читателей.

---

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

Будет, пожалуй, небесполезно сравнить метаматематику, понимаемую как теорию доказательства, с теорией шахматной игры. В шахматы играют с помощью 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). Буль и его последователи занимались прежде всего разработкой так называемой алгебры логики, посвященной выяснению и уточнению более общих и более разнообразных типов логической дедукции, нежели подпадающие под традиционные логические принципы. С помощью булевой техники легко выражаются, конечно, и традиционные умозаключения.