Неполнота математики

 

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

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

В 1889 г. Пеано предложил свои аксиомы для аксиоматизации понятия натурального числа и, после этого была создана формальная теория, известная под названием формальная арифметика. Это теория является расширением исчисления предикатов. Аксиомы Пеано следующие:

1) 1 есть натуральное число;

2) следующее за натуральным числом есть натуральное число;

3) 1 не следует ни за каким натуральным числом;

4) если натуральное число a следует за натуральным числом b и за натуральным числом c, то натуральные числа b и c тождественны;

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

 

Естественно было надеяться, что метод формальной аксиоматической теории позволит строить все содержание математики на такой точной и, казалось бы, надежной основе, как понятие выводимой формулы (теоремы формальной системы). Однако в 1931 году Курт Гедель доказал свою знаменитую теорему о неполноте.

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

При доказательстве своей теоремы Гедель, образно говоря, построил математическую формулу, которая гласит следующее: "Я не доказуема". Если эта формула ложна, то тогда получаем, что она доказуема. Но поскольку любое доказательство в математике приводит только к истинным утверждениям, то мы приходим к противоречию. Обратное предположение, т. е. истинность этой формулы, сразу приводит к неполноте математики. Занимательное изложение теоремы Гёделя вместе с доказательством можно прочитать в книге Р. Смаллиана [27].

Со времен доказательства Геделем своей теоремы математики искали пример такой истинной теоремы, которую было бы невозможно доказать используя аксиоматику Пеано. Только в 1977 году удалось обнаружить такую теорему в комбинаторики, так называемую бесконечную теорему Рамсея.

То, что истинное предложение бывает недоказуемым, можно проиллюстрировать таким примером. Рассмотрим предложение: для всякого натурального n имеет место формула 1+2+…+n = n(n+1)/2. Обычно это доказывают, применяя аксиому математической индукции. Если бы в нашем распоряжении не было аксиомы индукции, то эту формулу нельзя было бы доказать, ибо среди всех аксиом арифметики и логики одна лишь аксиома индукции позволяет делать утверждения обо всей бесконечной совокупности натуральных чисел.

Можно было бы попытаться сбросить ярмо индукции и рассуждать так: если бы для некоторого n сумма 1+2+…+n не равнялась числу n(n+1)/2, то существовало бы наименьшее такое n; оно не могло бы равняться 1, поскольку наше утверждение для n=1 верно; но оно не могло бы и быть больше 1, ибо тогда можно было бы показать, что n-1 тоже исключительное число, а это противоречит тому, что n - наименьшее из таких чисел. Увы, это рассуждение основано на принципе, утверждающем, что каждое непустое множество натуральных чисел имеет наименьший элемент, а этот принцип равносилен аксиоме индукции.

Итак, без аксиомы индукции простые арифметические утверждения вроде 1+2+…+n = n(n+1)/2 даже, несмотря на то, что они истинны, нельзя было бы вывести из остальных аксиом; можно сказать, что без аксиомы индукции арифметика была бы неполной.

 

 

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

М.В. Ломоносов