У интуиции есть своя логика. Гёдель. Теоремы о неполноте - [41]
Аксиома 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 году Эудженио Бельтрами доказал, что пятый постулат неразрешим относительно остальных четырех, то есть ни сам постулат, ни его отрицание не могут быть доказаны на их основе. Это был первый в истории известный пример неразрешимости относительно множества аксиом — за несколько десятков лет до того, как Гёдель доказал свою теорему. У пятого постулата есть два отрицания: в одном из них говорится, что через точку, не лежащую на прямой, не проходит ни одной прямой, параллельной данной, в другом — что через нее проходит больше одной параллельной прямой. Как пятый постулат, так и его отрицания могут быть добавлены к оставшимся четырем, и во всех случаях получается непротиворечивое множество аксиом. Когда добавляется пятый постулат, получается, конечно же, геометрия Евклида; в оставшихся двух случаях возникают так называемые неевклидовы геометрии. Сегодня считается, что все эти геометрии одинаково справедливы; неевклидовы больше подходят для описания эйнштейновского пространства, искривленного присутствием масс, в то время как евклидова больше приспособлена к нашему восприятию повседневных явлений.
