В работе раскрывается методологическая роль классической теоремы Геделя о неполноте формальных теорий. Рассматриваются идея Лейбница об универсальном языке и программа Гильберта обоснования математики, а также выразительные возможности логико-математического языка.
Введение. В человеческом познании Мира и самопознании можно выделить три интеллектуальных уровня, которые условимся называть Разумом, Наукой и Логикой. Мы отождествляем Разум с интеллектом и знанием, Науку - с точным (проверяемым, доказательным) знанием, Логику - с рассудком и формализацией. В статье рассматриваются следующие утверждения:
I. Разум шире Науки, ибо существуют «ненаучные» формы познания, например, философская, художественная или религиозная.
II. Наука шире Логики, поскольку не каждый научный факт допускает адекватную формализацию.
Отметим, что в классической парадигме познания Науку характеризует принцип математизации (точного) знания [1]. Логике же соответствует конструктивная (компьютерная) математика, искусственный интеллект. Разумеется, Наука разумна, а Логика научна. Заметим также, что утверждение II представляет собой некий неформальный аналог теоремы Геделя о неполноте.
Теорема Геделя о неполноте – самое крупное достижение логики в XX веке. Она явилась выдающимся интеллектуальным событием, вошла в монографии и учебники (см., например, [3]-[6], [10], [12]), стала классикой. Велика ее роль в логике и математике, философии и теории познания, психологии и информатике. Теореме Геделя посвящены многочисленные специальные статьи и книги (укажем лишь работы [8], [9], [14]).
Мечта Лейбница – создание идеального языка, в котором строго и адекватно выражалось бы все знание, и построение такой универсальной вычислительной машины, «говорящей» на этом языке, чтобы решение любой интеллектуальной проблемы сводилось к определенным «машинным» вычислениям. Заметим, что еще Платон утверждал, что всякое знание должно быть представлено в виде точных определений, которыми может пользоваться каждый. Все, что не может быть сформулировано в виде четких правил, что опирается на интуицию, мнения или традиции, бессмысленно. Идея мышления как процесса вычисления, «подсчитывания» была сформулирована также Гоббсом.
Лейбниц ввел двоичное счисление и идею универсальной характеристики, позволяющей координатизировать понятия натуральными числами, что предвосхитило нумерацию Геделя. Ранний Лейбниц был уверен в осуществимости своей мечты (но позднее признал безусловную роль бесконечности). Это означало бы тождественность Разума и Логики, возможность замены Разума искусственным интеллектом. Если придерживаться утверждений I и II, то следует признать, что человеческий интеллект неизмеримо шире, тоньше и многограннее любого искусственного интеллекта.
Тем не менее заманчивая и великая мечта Лейбница во многом претворена в жизнь – осуществлена на столько, на сколько это возможно. Созданы и развиваются математическая логика, теория алгоритмов, искусственные языки программирования, современные компьютеры, компьютерная математика. Продуктивен подход к исследованию разума с помощью структур программирования, что находит практическое воплощение при развитии интеллекта учащихся в рамках когнитивной информатики [7]. Говорят даже о «перевороте в сознании», состоящем в том, что открывается новый способ изучения мышления человека, по типу компьютерного программирования. Использование с помощью компьютера принципов кибернетики может способствовать глубинному исследованию структуры знания, что позволит лучше понимать процесс познания, природу нашего сознания.
Однако не следует преувеличивать автономные возможности вычислительных машин. Они четко очерчены: компьютер по своим возможностям находится между новичком и более подготовленным начинающим и не может продвинуться дальше этой границы, поскольку мышление любого новичка включает массу процедур, непосильных для компьютера.
Поэтому необходимо «сотрудничество» компьютера с человеком для создания робота с проблесками разума. Это интересная область науки, называемая искусственным интеллектом. Ее цель - создание эвристических программ, дающих возможность компьютеру, перерабатывающему информацию, проявлять разумность. Проектируя робота, никто не ожидает от него, что он будет воспроизводить любое разумное действие. Можно рассчитывать только на способность человека к формализации своего поведения.
Программа Гильберта представляет собой четко продуманный план работы по безупречному обоснованию всей математики. На пути ее реализации был усовершенствован язык математической логики, разработанный Булем, Шредером, Фреге, Расселом, Уайтхедом, Гильбертом и его последователями, возникла метаматематика, зародилась математическая теория моделей. Полная реализация программы Гильберта означала бы совпадение математики, стало быть, и Науки, с Логикой. Однако грандиозная программа Гильберта в том финитном виде, в каком она была задумана самим Гильбертом, была обречена на неудачу. Это задолго до теоремы Геделя о неполноте отмечал Пуанкаре, указав на порочный круг: в число финитных средств неизбежно попадает метод математической индукции, который сам подлежит формализации, и, заметим, тесно связан с бесконечностью.
Рассмотрим программу Гильберта чуть подробнее. Появившиеся на рубеже XIX и XX веков элементарные логические и теоретико-множественные парадоксы остро поставили проблему пересмотра оснований математики, обоснования непротиворечивости математики. Среди крупнейших математиков того времени возникли споры о надежности и возможности применения в математических рассуждениях тех или иных логических средств (закона исключенного третьего, метода от противного, аксиомы выбора). В результате зародились и возникли основные методологические направления в математике – логицизм (Фреге, Рассел, Уайтхед), интуиционизм (Брауэр, Вейль, Гейтинг), формализм (Гильберт, Бернайс), теоретико-множественное направление (Кантор, Цермело, Бурбаки). В математическом плане интуиционизм есть конструктивизм, развитый создателями теории алгоритмов и ЭВМ (Пост, Черч, Тьюринг, фон Нейман, А.А. Марков).
Гильберт и формалисты видели выход в эффективной аксиоматизации не только существующей математики, но и применяемой математиками логики. К началу XX века были содержательно аксиоматизированы основные числовые системы (Гамильтон, Грассман, Дедекинд, Кантор, Пеано), евклидова геометрия (Гильберт), теория множеств (Цермело). Формализм требует, чтобы изложение велось на строго формализованном языке математической логики. Таким языком служит язык логики первого порядка, т.е. логика предикатов, в которой кванторы связывают только предметные переменные. Этого мнения, называемого тезисом Гильберта, придерживаются многие логики и математики [11]. Все богатство математики должно быть представлено в виде формальных аксиоматических теорий (систем). Во второй половине XIX века произошла арифметизация математики (анализа, геометрии) – сведение классической математики к натуральным числам, то есть в известной степени осуществлена пифагорейская программа «Все есть натуральное число». Поэтому одним из первых шагов программы Гильберта явилась попытка построения внутренне непротиворечивой и адекватной (полной) формальной арифметики.
Формалисты представляют математику как своеобразную игру в формулы по четко определенным правилам. Напомним, что формальная аксиоматическая теория (или просто теория) предполагает наличие языка, аксиом и правил вывода. Язык состоит из алфавита, содержащего знаки предметных переменных и констант, предикатов и функций, скобки, термов и формул. Термы и формулы – это грамматика теории, т.е. четко определенные слова в данном алфавите, интуитивно обозначающие соответственно предметы и высказывания о них. Аксиомы и правила вывода можно назвать дедуктикой формальной системы. Формальный язык с грамматикой и дедуктикой образуют синтаксис. К синтаксису относятся понятия формальной выводимости и доказательства. Смысл и истинностное значение формул принадлежат семантике, связанной с синтаксисом посредством интерпретаций и моделей.
Естественным образом появилась метаматематика – наука о формальных аксиоматических системах, их свойствах. Важнейшими свойствами таких теорий являются непротиворечивость, полнота, разрешимость. Метаматематические рассуждения должны быть общепринятыми, финитными, алгоритмическими. Школой Гильберта были доказаны непротиворечивость, полнота и разрешимость исчисления высказываний, непротиворечивость и полнота чистой логики предикатов, полнота ряда формальных алгебраических теорий. Формалисты приступили к финитному доказательству непротиворечивости и полноты формальной арифметики. И здесь их ждало большое разочарование.
Теорема Геделя о неполноте. В 1931 году австрийский математик и логик Курт Гедель доказал свою знаменитую первую теорему о неполноте:
В любой непротиворечивой (w-непротиворечивой) формальной аксиоматической системе S, содержащей формальную арифметику, существует неразрешимое высказывание.
Напомним, что высказывание – это замкнутая формула логики предикатов (она не содержит свободных переменных), теорема – доказуемая формула, а неразрешимым называется высказывание A, которое нельзя ни доказать, ни опровергнуть, то есть высказывание A и его отрицание ùА не являются теоремами в S. Противоречивые теории – в точности те, все формулы которых суть теоремы. Теория называется полной, если для любого ее высказывания доказуемо либо оно само, либо его отрицание. Сформулированная теорема Геделя утверждает, что такие достаточно богатые теории S не полны. Интересно заметить, что в S найдется недоказуемое высказывание, означающее непротиворечивость теории S. Для построения неразрешимого высказывания Гедель применил кодирование формул натуральными числами (геделева нумерация), позволившее рассуждать о высказываниях теории S (метатеория) как о натуральных числах (предметной теории S). Тем самым показано, что средствами теории S невозможно доказать ее непротиворечивость (вторая теорема Геделя о неполноте, см. [12]). Следовательно, финитная программа обоснования математики не выполнима. Но даже если бы программа Гильберта оказалась полностью выполнимой, то повседневная работа по гильбертовскому шаблону была бы слишком громоздкой, и в своей практике математики продолжали бы пользоваться интуицией.
Пусть S – формальная арифметика и A – некоторое ее неразрешимое высказывание. Теория S служит формализацией содержательной теории натуральных чисел, имеющей стандартную модель – обычный натуральный ряд N. Высказывание A является вполне определенным утверждением о натуральных числах, которое либо истинно, либо ложно в N. Поэтому одно из высказываний A или ùА будет истинным недоказуемым высказыванием. Получаем существование недоказуемых высказываний о свойствах N, причем никакое расширение теории S положение дел не меняет. Из первой теоремы Геделя следует также, что множество всех истинных в N высказываний неразрешимо, т.е. не существует алгоритма, позволяющего решить вопрос об истинности каждого высказывания формальной арифметики.
Чуть позже были доказаны теорема Тарского о невыразимости истины в S и теорема Черча о неразрешимости множества всех общезначимых формул логики предикатов. Общезначимость формулы данной теории означает ее истинность во всех моделях теории. Укажем другие фундаментальные результаты о взаимосвязи между синтаксисом и семантикой формальных систем. Во-первых, назовем теорему Геделя 1930 года о полноте, или адекватности: формула теории первого порядка является теоремой тогда и только тогда, когда она общензначима. Во-вторых, обобщенная теорема о полноте утверждает, что непротиворечивость формальной аксиоматической теории равносильна существованию модели этой теории. Отсюда выводится теорема компактности, впервые доказанная А.И. Мальцевым в 1936 году: множество высказываний некоторой формальной аксиоматической теории имеет модель тогда и только тогда, когда любое его конечное подмножество обладает моделью. Заметим, что в пользу приведенного выше тезиса Гильберта говорит следующий прекрасный результат Линдстрема [11]: логика первого порядка является единственной логикой, замкнутой относительно обычных логических связок и кванторов и удовлетворяющей теоремам компактности и Левенгейма-Скулема. А теорема Левенгейма-Скулема утверждает, что теория с бесконечной моделью имеет и счетную модель.
Поясним первую теорему Геделя о неполноте. В системе S строится высказывание A, говорящее о собственной недоказуемости в терминах геделевой нумерации, т.е. A обозначает высказывание «Это предложение недоказуемо». Здесь, как и в строгом оригинальном рассуждении Геделя, обыгрывается знаменитый парадокс лжеца в форме «Это предложение ложно» с заменой слова «ложно» на «недоказуемо». При любых интерпретациях непротиворечивой теории теоремы истинны. Поэтому высказывание A не может быть ложным. Значит, A – недоказуемая истина и, стало быть, неразрешимое высказывание.
Модификации формализма. Обоснование математики в гильбертовском смысле потерпело неудачу. При построении математики как формальной системы Гильберт допускал только логику первого порядка в качестве предметной теории и только финитные методы в метатеории. Но можно пытаться доказать непротиворечивость математики, либо несколько усилив язык формальной теории, либо используя некоторые достаточно убедительные нефинитные средства в метаматематических рассуждениях. Так, Генцен доказал непротиворечивость формальной арифметики, применив трансфинитную индукцию по счетным ординалам (см. [5]).
Интересна предпринятая Ю.Л. Ершовым реабилитация программы Гильберта [2]. Его подход придает новый смысл программе Гильберта и ее реализации: «для всякой заинтересовавшей нас проблемы ищите систему с обычными правилами вывода, в которой эта проблема представима в виде осмысленной задачи, и затем ищите для такой системы финитное доказательство ее непротиворечивости в соответствии с прежним императивом программы Гильберта». Это определенная локализация гильбертовского глобализма.
А.Н. Паршин рассматривает геделеву нумерацию как определенную систему координат, придавая ей геометрический смысл и имея в виду ее вложение в p-адический континуум [8]. Это открывает новые возможности истолкования теоремы Геделя.
Гносеологические выводы. Теорема Геделя о неполноте ограничивает тотальную формализацию Науки, высвобождая энергию творчества. Она убедительно показывает несводимость мышления к логике, принципиальную неформализуемость Разума, необходимость интуиции.
Как подчеркивает А.Н. Паршин в своей глубокой работе [8], теорема Геделя есть фундаментальный философский факт, говорящий о каком-то глубинном свойстве мышления и указывающий на существование подвижной границы между формальным и интуитивным везде, в частности в самой математике, причем, эта граница «устанавливается каждый раз заново в каждом новом акте познания». Интересно отметить, что зачастую акт обретения нового совершается мгновенно (именно так человек начинает уметь плавать и кататься на велосипеде). Кроме того, надо сказать, что в квантовой физике имеется методологически аналогичный результат – это теорема фон Неймана о невозможности введения скрытых параметров, которые позволили бы свести квантовые системы к системам классической механики.
Теорема Геделя о неполноте, сама будучи вершиной логической мысли, несет огромный жизнеутверждающий заряд – ценность постепенного логического освоения научного знания. Подчеркивая непреходящее значение творчества, она укрепляет веру в бесконечный прогресс рационального познания.
Продолжение темы о заработке золота в WoW: фарм слез сирены и ледяных шаров
