Чтение онлайн

на главную - закладки

Жанры

Жар холодных числ и пафос бесстрастной логики
Шрифт:

N=29 • З17 • 511 • 7289• 1111• 1317 • 1718 • 1913.

Наконец, нумеруются последовательности формул. Если дана последовательность из 5 формул с номерами m1, m2, m3..., ms, то номер последовательности определяется как 2m1 • 3m2 • 5m3 • ... • psms, где ps — 5-тое простое число.

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

между числами (гёделевыми номерами). Скажем, утверждение «Данная комбинация символов есть формула» выражается некоторым арифметическим предикатом от гёделева номера этой комбинации n, то есть записывается в виде некоторой арифметической формулы q2n.

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

Решающий момент в построении Гёделя наступает тогда, когда он предъявляет формулу, которая представляет в его системе кодировки метавыоказывание о собственной недосказуемости. В этом случае возникает следующая ситуация. Предположим, что формула, говорящая «Я недоказуема», доказуема. Тогда, если логико-арифметическая система непротиворечива — и, значит, все доказуемые в ней формулы (тождественно)истинны[3], данная формула не может быть доказуемой; в самом деле, если бы она была доказуемо и, то заключенное в ней утверждение «Я недоказуема» следует считать истинным, то есть признать формулу недоказуемой[4]. Но данная формула не только недоказуема, но и неопровержима, то есть недоказуемо ее отрицание. Таким образом, формулу, имеющую смысл «Я недоказуема», в системе «типа РМ» нельзя ни доказать, ни опровергнуть —это неразрешимая формула.

Существование же в формальной системе неразрешимой формулы — и к тому же содержательно истинной, так как ее смысл «Я недоказуема» соответствует ситуации в данной системе, означает неполноту системы. Заметим, наконец, что формула с таким смыслом на деле является схемой формул вида «Я формула Ф;, недоказуема», — так что в системе оказывается бесконечное множество неразрешимых высказываний, получаемых различным выбором значений Ф5.

Итак, если формальная арифметика («типа РМ») непротиворечива, то она неполна. А что если она противоречива? Тогда ее теоремы теряют всякую ценность, поскольку в этом случае доказывается, что можно доказать любую наперед заданную теорему —для этого достаточно даже одного-единственного противоречия между доказанной формулой и доказанным ее отрицанием. В этом случае, конечно, гёделева формула, говорящая «Я недоказуема», будет доказуема, но будет доказуемо и ее отрицание. Математики всей душой надеются, что арифметика непротиворечива. Но нельзя ли эту надежду превратить в твердую уверенность и доказать непротиворечивость формальной арифметики?

Исследование Гёделя привело к следующему результату. С помощью своего метода кодировки Геделю удалось доказать в логико-арифметическом исчислении формулу, метаматематический смысл которой таков: «Если формальная арифметика непротиворечива, то формула, говорящая «Я недоказуема», доказуема» (обозначим эту формулу через (*)). Предположим теперь, что мы сумели в рассматриваемом исчислении доказать формулу, утверждающую непротиворечивость формальной арифметики. Тогда, в силу доказанной Гёделем формулы (»), по модесу поненсу следует заключение, что формула, говорящая «Я недоказуема», доказуема. Но это противоречит предыдущей теореме (называемой теоремой о неполноте, или первой теоремой Гёделя). Поэтому получается, что формулу, говорящую о непротиворечивости формальной арифметики, доказать в этой последней нельзя, если только сама формальная арифметика не противоречива. Если же она противоречива, то в ней, как мы отметили выше, доказуема любая формула, в том числе и формула, которую можно считать выражающей наличие у данной формальной системы свойства «быть непротиворечивой».

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

Мы все время говорим о формальной арифметике, но результаты Гёделя относятся к любому формальному исчислению, достаточно богатому, чтобы содержать в себе арифметику, то есть к исчислению, «начиная с арифметики». Исчисление высказываний беднее арифметики, поэтому на него теорема Гёделя не распространяется — и, как мы знаем, легко доказать его непротиворечивость (оно также полно). Таким образом, работы Гёделя были первыми строгими исследованиями возможностей дедуктивного метода познания. И эти исследования привели к результатам, которые никак не могла предвидеть наука «догелевского» периода.

'Открытия Гёделя вызвали множество толкований. Общим их мотивом — полностью убедительным —- является заключение об определенной внутренней ограниченности регулярных процедур дедуктивного и вычислительного характера, о невозможности представления процесса расширения знания (начиная с математики) и в виде завершенной формальной системы. Как отметил П. С. Новиков, «понятия и принципы всей математики не могут быть полностью выражены никакой формальной системой, как бы мощна она ни была»[6]. Но это так же мало означает дискредитацию метода построения формальных систем, как открытие предельности скорости света — дезавуацию физической теории пространства и времени. Из «ограничительных» результатов математической логики — эти результаты не исчерпывались открытиями Гёделя, о которых шла речь, а получили дальнейшее продолжение в большой серии теорем, касающихся неразрешимости и неполноты формальных теорий, тем более не следует заключение о превосходстве интуиции над разумом.

Гносеологические выводы из теоремы Гёделя нужно делать с большой осторожностью. То, на что наталкивает нас в философском плане эта теорема, высказано Э. Нагелем и Дж. Ньюменом в следующей форме: «Заключения, к которым пришел Гёдель, порождают, естественно, вопрос, можно ли построить вычислительную машину, сравнимую по своим «творческим» математическим возможностям с человеческим мозгом. Современные вычислительные машины обладают некоторым точно фиксированным запасом команд, которые умеют выполнять их элементы и блоки; команды соответствуют фиксированным правилам вывода некоторой формализованной аксиоматической процедуры. Таким образом, машина решает задачу, шаг за шагом выполняя одну из «встроенных» в нее заранее команд. Однако, как видно из гёделевской теоремы о неполноте, уже в элементарной арифметике натуральных чисел возникает бесчисленное множество проблем, выходящих за пределы возможностей любой конкретной аксиоматической системы, а значит, и недоступных для таких машин, сколь бы остроумными и сложными ни были их конструкции и с какой бы громадной скоростью ни проделывали они свои операции. Для каждой конкретной задачи в принципе можно построить машину, которой эта задача была бы под силу, но нельзя создать машину, пригодную для решения любой задачи. Правда, и возможности человеческого мозга могут оказаться ограниченными, так что и человек тогда сможет решить не любую задачу. Но даже если это так, структурные и функциональные возможности человеческого мозга пока еще намного больше по сравнению с возможностями самых изощренных из мыслимых пока машин... Единственный непреложный вывод, который мы можем сделать из гёделевской теоремы о неполноте, состоит в том, что природа и возможности человеческого разума неизмеримо тоньше и богаче любой из известных пока машин»[7].

Действительно, электронная вычислительная машина есть универсальный инструмент вычисления, о чем пойдет речь ниже. Конечно, в самой схеме ЭВМ вовсе не заложен аксиоматически-дедуктивный метод получения теорем. Но машину в принципе всегда можно «научить» выводить теоремы с помощью заданных правил вывода из заданных аксиом (правда, соответствующие программы могут оказаться очень сложными). В результате машина «овладевает» дедуктивным методом доказательства теорем и, естественно, оказывается подвластной ограничениям, которые налагают на этот процесс положения Гёделя. Но эти же самые ограничения распространяются ина человека, если он работает строго по дедуктивному методу[8].

Впрочем, ограничения, вытекающие из результатов Гёделя, относятся не к дедуктивному методу вообще, а к таким дедуктивным системам, которые содержат теорию натуральных чисел и в которых доказательства представляют собой эффективно распознаваемые (за конечное число шагов) объекты. Но как показало последующее развитие математической логики, проблему непротиворечивости и другие проблемы, касающиеся формальных систем, можно исследовать методами, выходящими за пределы подобного финитизма, но представляющимися достаточно надежными. На этом пути становится возможным, например, доказательство непротиворечивости классической формальной арифметики[9].

Поделиться:
Популярные книги

Утопающий во лжи 4

Жуковский Лев
4. Утопающий во лжи
Фантастика:
фэнтези
боевая фантастика
рпг
5.00
рейтинг книги
Утопающий во лжи 4

Пожиратель душ. Том 1, Том 2

Дорничев Дмитрий
1. Демон
Фантастика:
боевая фантастика
юмористическая фантастика
альтернативная история
5.90
рейтинг книги
Пожиратель душ. Том 1, Том 2

Релокант. По следам Ушедшего

Ascold Flow
3. Релокант в другой мир
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Релокант. По следам Ушедшего

Любовь Носорога

Зайцева Мария
Любовные романы:
современные любовные романы
9.11
рейтинг книги
Любовь Носорога

Измена. Верни мне мою жизнь

Томченко Анна
Любовные романы:
современные любовные романы
5.00
рейтинг книги
Измена. Верни мне мою жизнь

Изгой. Пенталогия

Михайлов Дем Алексеевич
Изгой
Фантастика:
фэнтези
9.01
рейтинг книги
Изгой. Пенталогия

Осознание. Пятый пояс

Игнатов Михаил Павлович
14. Путь
Фантастика:
героическая фантастика
5.00
рейтинг книги
Осознание. Пятый пояс

Темный Патриарх Светлого Рода 4

Лисицин Евгений
4. Темный Патриарх Светлого Рода
Фантастика:
фэнтези
юмористическое фэнтези
аниме
5.00
рейтинг книги
Темный Патриарх Светлого Рода 4

Лорд Системы 12

Токсик Саша
12. Лорд Системы
Фантастика:
фэнтези
попаданцы
рпг
5.00
рейтинг книги
Лорд Системы 12

Генерал Империи

Ланцов Михаил Алексеевич
4. Безумный Макс
Фантастика:
альтернативная история
5.62
рейтинг книги
Генерал Империи

Пятничная я. Умереть, чтобы жить

Это Хорошо
Фантастика:
детективная фантастика
6.25
рейтинг книги
Пятничная я. Умереть, чтобы жить

Кодекс Охотника. Книга XVII

Винокуров Юрий
17. Кодекс Охотника
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Кодекс Охотника. Книга XVII

Физрук 2: назад в СССР

Гуров Валерий Александрович
2. Физрук
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Физрук 2: назад в СССР

Провинциал. Книга 3

Лопарев Игорь Викторович
3. Провинциал
Фантастика:
космическая фантастика
рпг
аниме
5.00
рейтинг книги
Провинциал. Книга 3