У интуиции есть своя логика. Гёдель. Теоремы о неполноте. - Gustavo Pineiro

9. Ни одно множество не является членом самого себя.

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

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

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

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

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

Аксиома 1: нет ни одного числа с последующим элементом 1.

Аксиома 2: если у двух чисел один и тот же последующий элемент, то они равны.

Аксиома 3: последующий элемент для х — это х + 1.

Аксиома 4: (х + у) + 1 = х + (у + 1).

Аксиома 5: произведение х на 1 равно х.

Аксиома 6: х · (у + 1) = х · у + х.

Аксиома 7: если 1 выполняет некое свойство и можно быть уверенным, что и х выполняет это свойство, а значит, его последующий элемент тоже его выполняет, то при таких условиях можно быть уверенным: любое число выполняет это свойство.

Докажем, что аксиомы Пеано непротиворечивы. Для начала заметим, что все семь аксиом — это истинные высказывания (в мире натуральных чисел). Мы уже сказали, что из истинных предпосылок можно вывести только истинные утверждения, следовательно, из аксиом Пеано нельзя вывести ни одного ложного высказывания. Но если множество аксиом противоречиво, то на его основе доказуемо любое высказывание. Поскольку есть высказывания, которые недоказуемы на основе аксиом Пеано (ложные высказывания недоказуемы), то мы делаем вывод, что аксиомы Пеано непротиворечивы.

Во второй теореме о неполноте говорится, что нельзя доказать непротиворечивость аксиом Пеано... но мы только что его доказали. Как это возможно? Ответ, конечно же, в том, что во второй теореме о неполноте на самом деле говорится: невозможно доказать непротиворечивость аксиом Пеано, пользуясь методами программы Гильберта. Доказательство непротиворечивости, которое мы только что осуществили, следовательно, является корректным рассуждением, но не подчиняется ограничениям этой программы: корректность доказательства нельзя проверить алгоритмически.

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

Итак, вторая теорема о неполноте оказывается ложной, если мы применим при доказательстве семантические методы. Но что произойдет с первой теоремой Гёделя? Можно доказать, что если мы допустим семантические методы, то любая арифметическая истина доказуема на основе аксиом Пеано. Под семантическими методами мы понимаем те, что основаны на понятии истины. Логическое правило, которое используется в этих рассуждениях, таково: из Р выводится Q, если во всех мирах (или моделях), где Р истинно, Q также истинно (см. рисунок). Вновь возьмем пример доказательства, который мы рассматривали в главе 2, и зададимся вопросом, справедлив ли вывод:

из равенства (а - b) · а = (а - b) с мы делаем вывод, что а = с,

где Р — это высказывание "(а - b) · а = (а - b) · с", a Q — это "а = с". Вывод несправедлив, поскольку существует модель (пример), в которой Р истинно, a Q ложно. Действительно,

если мы возьмем а = b = 2 и с = 3, то получается, что Р истинно, a Q ложно.

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

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

1. Через две точки можно провести единственную прямую.

2. Отрезок можно продолжить из любого его конца.

3. При любом центре и любом радиусе можно провести окружность.

4. Все прямые углы равны между собой.

5. Через точку, не лежащую на прямой, можно провести единственную прямую, параллельную данной.

Итальянский математик Эудженио Бельтрами.

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

В течение многих веков считалось, что пятый постулат можно доказать на основе четырех других. Было сделано много попыток найти доказательство, но все они провалились. Наконец, в 1868 году Эудженио Бельтрами доказал, что пятый постулат неразрешим относительно остальных четырех, то есть ни сам постулат, ни его отрицание не могут быть доказаны на их основе. Это был первый в истории известный пример неразрешимости относительно множества аксиом — за несколько десятков лет до того, как Гёдель доказал свою теорему. У пятого постулата есть два отрицания: в одном из них говорится, что через точку, не лежащую на прямой, не проходит ни одной прямой, параллельной данной, в другом — что через нее проходит больше одной параллельной прямой. Как пятый постулат, так и его отрицания могут быть добавлены к оставшимся четырем, и во всех случаях получается непротиворечивое множество аксиом. Когда добавляется пятый постулат, получается, конечно же, геометрия Евклида; в оставшихся двух случаях возникают так называемые неевклидовы геометрии. Сегодня считается, что все эти геометрии одинаково справедливы; неевклидовы больше подходят для описания эйнштейновского пространства, искривленного присутствием масс, в то время как евклидова больше приспособлена к нашему восприятию повседневных явлений.

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

Нечто подобное происходит с семантическими доказательствами; мы можем быть уверены, что из Р выводится Q... пока не найдем мир, в котором Р будет истинным, a Q не работает. В программе Гильберта предполагалось избавление от этой неточности и предлагались методы доказательства, правильность которых можно было бы проверить раз и навсегда.