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

Автор книги: Борис Бирюков

Соавторы: В. Тростников
сообщить о нарушении

Текущая страница: 8 (всего у книги 14 страниц)

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

Это было связано с его теорией «идеальных элементов» в математике. Гильберт принимал, что бесконечные множества не соответствуют ничему реальному в природе. Но ведь и в задачах, где исследуются целые числа, могут в промежуточных фазах вычисления встретиться дроби, которые тоже ничему в данном случае не соответствуют и которые в окончательный результат не войдут, они введены нами для удобства вычислений, из соображений формальной простоты и компактности. То же можно сказать о комплексных числах, встречающихся в уравнениях прогиба стержней. Комплексные числа не описывают непосредственно стержня, но, появляясь в промежуточных стадиях вычисления, сокращают путь решения задачи, делают решение лаконичным и простым. Иными словами, кратчайшая дорога, соединяющая области реальные, может пролегать по области «воображаемых» объектов – «идеальных элементов». Мы сможем без опаски пользоваться этими элементы ми, если докажем раз навсегда, что теория, построенная с их участием, не приведет к противоречию^[13]. И тогда не нужно искать никакой «изначальной индукции» разума или других столь же туманных источников надежности математики. Ее надежность – это ее непротиворечивость, другие требования просто лишены смысла.

Попробуем проследить идейные основы концепции идеальных элементов» Гильберта.

Воспитанный в немецком университете профессорами, целиком принадлежавшими к поколению, считавшему теоретико-множественное мышление идеалом строгости, он и сам впитал смолоду этот образ мышления. Канторовская теория множеств рисовалась ему одним из величайших завоеваний человеческого гения. «Никто не сможет изгнать нас из рая, который создал нам Кантор», сказал Гильберт^[14], осуждая попытки Брауэра я его учеников «развалить» математику.

Но Гильберт уже не верил в существование в каком-то «царстве идей» множеств множеств множеств. Гильберт просто считал, что такие понятия полезны для математики, в могуществе которой был глубоко убежден. В конце вступительной части своего исторического доклада о проблемах математической науки он произнес вдохновенные слова: «мы слышим внутри себя постоянный призыв: вот проблема, ищи решение. Ты можешь найти его с помощью чистого мышления, ибо в математике не существует Ignorabimus»^[15]. Это был прямой вызов агностическим установкам в науке, так как выражение ignorabimus—«мы не будем знать» (лат.) было сказано физиологом Э. Дюбуа-Реймоном о некоторых нерешенных проблемах (касающихся взаимоотношения физиологического и психического).

Новаторство Гильберта проявилось как в том, что он объявил теоретико-множественные построения лишь вспомогательными элементами науки, так и в подробно развитом им подходе к основаниям математики, получившем название гильбертовского формализма и финитизма. Познакомимся с основным тезисом гильбертовского формализма из уст его автора.

Гильберт считал, что в качестве предварительного условия для осуществления логических умозаключений и выполнения логических операций в человеческом представлена уже должны быть даны определенные внелогические конкретные объекты – даны наглядно, в качестве непосредственных переживаний до какого бы то ни было мышления. «Для того чтобы логические выводы были надежны, эти объекты должны быть обозримы полностью во всех частях; их показания, их отличие, их следование, расположение одного из них наряду с другим дается непосредственно наглядно, одновременно с самими объектами, как нечто такое, что не может быть сведено к чему-либо другому и не нуждается в таком сведении. Это – та основная философская установка, которую я считаю обязательной как для математики, так и вообще для всякого научного мышления, понимания и общения и без которой совершенно невозможна умственная деятельность. В частности, в математике предметом нашего рассмотрения являются конкретные знаки сами по себе, облик которых... непосредственно ясен и может быть впоследствии узнаваем»^[16].

Если глубоко вдуматься в это программное заявление, мы увидим, что перед нами, несомненно, плодотворный тезис. По существу, Гильберт утверждает здесь, что мышление, научная работа нуждаются в системе знаков, на которые могут опереться логические рассуждения. Знаки – внелогическая категория, утверждает Гильберт. В самом деле, ведь это материальные объекты, состоящие из засохшей типографской краски, из микроскопических ракушек, образующих мел, и т. п.

Они могут отображаться в представлении, в сознании, но в этом случае они выступают в качестве образов тех же материальных объектов. Для научного мышления представляют ценность не любые знаки, а такие, которые человек может уверенно отличать друг от друга или, наоборот, отождествлять друг с другом – только в этом случае их можно использовать для построения теории.

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

«Эта игра формул допускает, что все содержание идей математической науки можно единообразно выразить и развить таким образом, чтобы вместе с тем соотношения и отдельные теоремы были понятны. Выставить общее требование, согласно которому отдельные формулы сами по себе должны быть изъяснимы, отнюдь не разумно; напротив, сущности теории соответствует, что при ее развитии нет необходимости, между прочим, возвращаться к наглядности или значимости. Физик как раз требует от теории, чтобы частные теоремы были выведены из законов природы или гипотез с помощью одних только умозаключений, не вводя при этом дальнейших условий, то есть. на основании чистой игры формул. Только известная часть комбинаций и следствий из физических законов может быть контролируема опытом, подобно тому как в моей теории доказательства только реальные высказывания могут быть непосредственно проверяемы»^[17].

Было бы неправильным усматривать здесь философски неубедительные тенденций. Основная цель науки, по Гильберту, познание мира. Но сущность вещей не лежит в их «верхнем слое», непосредственно открытом чувственному восприятию. Поэтому методологически, неправильно каждую отдельную формулу и каждый отдельный знак «проверять» сопоставлением с действительными объектами. Теория – вещь горазда более сложная, чем простое «фотографирование» объектов. Установив правила работы со знаками с помощью глубинных законов природы или с помощью некоторых» гипотез (которые потом могут быть отвергнуты, если теория: не оправдает себя), на следующем этапе работы мы можем отвлечься: от внешней реальности, вернее, рассматривать в качестве реальности уже не окружающую природу, а саму знаковую систему с ее правилами, каковые, хотя и были установлены нами самими», теперь предстают перед нами как объективная: данность»

Чтобы лучше пояснить сущность гильбертовской идеи «игры в символы», проведем такую параллель. В современной практике получили распространение аналоговые электрические машины, с помощью которых исследователи решают многие важные проблемы. Принцип действия таких устройств состоит в том, что параметры электрических цепей (омического сопротивления, индуктивности, напряжения; и т. д.) подобраны так, что изменение тока или напряжения во времени оказывается подчиненным тем же законам, которые, по предположению, управляют некоторым физическим или технологическим процессом.

Придав параметрам исходные значения, затем предоставляют развиваться электрическим процессами смотрят, что получится в результате. Это – электрическое моделирование неэлектрического (а, скажем, механического или теплового) процесса. В этом случае никто не будет настаивать, чтобы мы истолковывали токи или напряжения содержательным образом на каждом этапе исследования. Запустив машину, исследователь некоторое время имеет дело только с происходящими в ней электрическими явлениями. Если бы он отказался от такой методики и подвергал все промежуточные значения параметров мелочной проверке и сопоставлению с моделируемым процессом, это могло бы принести только вред (он мог навязать машине свои представления об изучаемом явлении, которые могли бы оказаться ошибочными). Гильбертова методика знакового моделирования ничем, в сущности, не отличается от обрисованной нами сейчас методики электрического моделирования. Роль токов и напряжений, измеряемых с помощью приборов, а в конечном счете – с помощью человеческого глаза, смотрящего на шкалу прибора, у Гильберта играют знаки, опознаваемые и различаемые математиком, а в роли условий, определяющих характер электрического процесса в аналоговой машине, выступают аксиомы и правила вывода одних знаковых комбинаций из других, предварительно установленные на основании некоторых разумных соображений и в дальнейшем ни в коем случае не нарушаемые. Впоследствии мы увидим, какую существенную роль играет знаковое моделирование в кибернетике.

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

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

Приведем пример финитного доказательства непротиворечивости, который позволит конкретно представить существо подхода Гильберта. Докажем, что дедуктивно-аксиоматическая система исчисления высказываний, описанная в главе 4 (система Фреге), непротиворечива, то есть, что в ней нельзя доказать в качестве теоремы некоторую формулу а и ее отрицание ~α^[18].

Доказательство любой теоремы в данной системе можно представить как цепочку формул, каждая из которых есть либо аксиома, то есть формула, подпадающая под какую-либо схему аксиом, либо получена из каких-либо формул, стоящих в цепочке ранее, по модесу поненсу; последняя формула цепочки есть доказываемая теорема. В силу этого самое первое применение правила вывода должно обязательно относиться к аксиомам. В этом смысле можно сказать, что все доказательства – выводы теорем – начинаются на аксиомах, а затем с помощью правила модус поненс получаются новые формулы (причем каждая из них есть теорема). Но поскольку любая формула, подпадающая под какую-либо схему аксиом (аксиома), как мы установили, тождественно-истинна, а модус поненс этой истинности не «портит», то свойство «быть тождественно-истинной формулой» становится в нашей системе «наследственным» – присущим всем теоремам. Это свойство похоже на некий генетический признак, непременно передающийся от родителей к детям. При таком положении дел можно с полной уверенностью утверждать, что среди даже самых дальних потомков прародителей не встретятся экземпляры, лишенные наследуемого признака.

Рассмотрим теперь некие две формулы а и ~а. Если обе они – доказуемые формулы, то есть «потомки» аксиом, порожденные посредством модуса поненса, то они должны быть обе тождественно-истинными. Но это невозможно: из табличного определения отрицания следует, что если одна из этих формул будет тождественно-истинной, то другая окажется тождественно-ложной. Но тождественно-ложная формула не может быть выводимой из аксиом – доказуемой (так как если бы она была доказуемой, то была бы тождественно-истинной и, значит, не тождественно-ложной). Следовательно, одна из формул, а или ~а, недоказуема.

Это рассуждение является совершенно «финитным», оно не использует ни идеи канторовской актуальной бесконечности, ни «идеальных элементов»^[19].

Гильберт хотел осуществить такого же рода (мета)доказательство непротиворечивости для более сложной дедуктивной системы – арифметики. Для этого арифметику нужно было построить как аксиоматически-дедуктивную систему и показать, что, пользуясь разрешенными в ней правилами переработки знакосочетаний, мы никогда не выведем в качестве теорем а и ~а. Поскольку арифметика занимается установлением соотношений не только для конкретыых натуральных чисел, но и формулирует законы, которым подчиняются все натуральные числа (например, что а + b = b + а, каковы бы ни были a и b) или какие-то (бесконечные) их множества, и утверждения о существовании чисел с определенными свойствами, то соответствующая формальная система должна быть основана на логике предикатов, в которой имеются правила обращения с кванторами общности V («все») и существования Э («существует»).

Интересно, что у Гильберта в течение нескольких лет, по-видимому, имелось чувство уверенности, что данная проблема вот-вот будет решена, что осталось совсем немного усилий, и непротиворечивость, арифметики будет строго установлена начертанным им в 1927 году на Математическом семинаре в Гамбурге путем^[20]. Но шли годы, а дело не сдвигалось с места. А в 1931 году молодей австрийский математик Курт Гёдель опубликовал найденное им доказательство (мета)теоремы, которая многими рассматривается как поворотный пункт в науке об основаниях математики и в математической логике. Методами, признанным» подавляющим большинством математиков совершенно строгими, Гёдель доказал, что в формализованной арифметической системе есть такие формулы, которые по своему содержанию должны быть либо истинными, либо ложными, но которые не могут быть в этой системе ни доказаны, ни опровергнуты. Но это еще не все. Опираясь на этот результат, названный Теоремой о неполноте, Гёдель доказал, что если арифметика непротиворечива, то ее непротиворечивость нельзя; доказать формальными средствами.

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

6. ТЕОРЕМА ГЁДЕЛЯ

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

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

Курт Гёдель родился в Праге (Чехия в то время входила в состав Австро-Венгрии) в 1906 году. Главные свои открытия он сделал в возрасте 24 лет (заметим, что и Ньютон написал свои лучшие работы примерно в таком же возрасте), однако и в дальнейшем получал крупные научные результаты, относящиеся, в частности, к теории множеств; в 1949 г. он предложил новый тип решения уравнений общей теории относительности, заслужив похвалу Эйнштейна^[1]. В настоящее время Гёдель живет в Соединенных Штатах и является профессором Института высших исследований в Принстоне, штат Нью-Джерси. В 1951 г. он был удостоен высшей награды, присуждаемой в США за научные достижения, Эйнштейновской премии.

В статье, в которой доказывалась теорема о неполноте формальной арифметики, Гёдель исследует систему формальной арифметики Principia Mathematica (он называет эту аксиоматически-дедуктивную теорию «системой PM»). Начинает он свою статью следующими словами: «Развитие математики в направлении все увеличивающейся строгости привело, как известно, к формализации многих ее частей, так что стало возможным доказывать теоремы, не пользуясь ничем, кроме нескольких механических правил. Наиболее широкие формальные системы, построенные к настоящему времени, это, с одной стороны, система Principia Mathematica (РМ) и, с другой стороны, система аксиом Цермело—Френкеля для теории множеств (развитая в дальнейшей Дж. фон Нейманом).

Обе эти системы настолько широки, что все методы доказательства, применяемые ныне в математике, в них формализованы, то есть сведены к небольшому числу аксиом и правил вывода. Поэтому можно предположить, что этих аксиом и правил вывода окажется достаточным, чтобы получить ответ на любой математический вопрос, который вообще может быть формально выражен в этих системах. Ниже будет показано, что это не так, что, наоборот, в обеих упомянутых системах имеются проблемы даже относительно простые, относящиеся к теории обычных целых чисел, которые нельзя решить, исходя из аксиом. Это обстоятельство не связано с какой-то специфической природой этих систем, напротив, оно имеет силу для очень широкого класса формальных систем, к которым, в частности, принадлежат все системы, получающиеся из упомянутых двух посредством присоединения к ним конечного числа аксиом, если только это присоединение не приводит к тому, что доказуемым становится какое-либо ложное предложение»^[2].

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

Это делается так: вводится символ для числа «нуль» (0), а также символ «следования за» f, который трактуется так, что f0 есть единица, ff0 – два и т. д.

Но для целей, которые преследует Гёдель, недостаточно иметь лишь символы для логических операций и чисел. Нужно выразить также основные арифметические предикаты, такие, как «простое число», «делится нацело» и т. п. В этом месте Гёдель, используя понятия системы РМ и известную в математике процедуру рекурсивного задания функции, то есть задания новых значений функции через предыдущие (рекурсивно, например, определяется функция «факториал» – произведение всех натуральных чисел от единицы до данного числа: (1)0! = 1; (2) (n+ 1)! = (n!) (n + 1)), вводит понятие рекурсивной функции, которое заведомо выразимо средствами формальной арифметики. Делается это так: задаются исходные рекурсивные функции – константа 0 и функция «следования за» – а затем устанавливается способ, с помощью которого из них можно получать более сложные рекурсивные функции. В самом начале этой части работы Гёдель показывает, что такие важные функции, как сложение, умножение и возведение в степень, рекурсивны. Он определяет также понятие рекурсивного арифметического предиката; n-местным арифметическим рекурсивным предикатом (отношением между n числами) называется такой предикат, который определяется уравнением φ (х1, х2,..., хn) = 0, где φ—рекурсивная функция, а х1, х2, ..., >Хn – переменные для чисел. Примером рекурсивного предиката является двуместный предикат «меньше». Рассмотрим этот случай подробнее, так как в дальнейшем нам понадобится представление о рекурсивных функциях и предикатах.

1. Функция δ, определяемая условиями

а) δ(0)=0, б) δ(у+1)= y,

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

2. Функция х ∸ у, определяемая условиями

а) х ∸ О = х, б) х ∸ (у+1)=δ(х ∸ у),

рекурсивна, как выраженная стандартной схемой рекурсии через рекурсивную функцию δ. Как нетрудно убедиться, смысл функции х ∸ у (она называется усеченным вычитанием) таков: функция эта равна х – у, если х >= у и равна нулю, если х < у.

В самом деле, посмотрим, каково значение функции х ∸ у для х, у = 0, 1, 2, 3 (над знаками равенств помечаем какой пункт определений 1, 2 применяется или какое из ранее полученных значений функции х – у используется):

Подобным же образом вычисляется 0∸3=0,0∸4=0 (вообще, легко усматривается, что при дальнейшем возрастании значения у выражение 0 ∸ у будет оставаться равным нулю).

При дальнейшем возрастании значения y выражение 2 ∸ у становится равным нулю. Аналогично вычисляется, что 3 ∸ 0 = 3, 3 ∸ 1 = 2, 3 ∸ 2 = 1, но при y > 2 выражение 3 ∸ y равно нулю.

3. Предикат, опередляемый уравнением х ∸ у = 0, рекурсивен; это очевидно, поскольку функция х ∸ у, как мы показали, рекурсивна. Но смысл этого предиката выражается в обычном языке утверждением x <= у.

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

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

Сначала нумеруются знаки логических операций, вспомогательные символы и другие исходные знаки: символ 0 получает номер 1; символ f – номер 3; символ ~ – номер 5; символ V – номер 7; символ Ɐ – номер 9; символ ), то есть левая скобка, – номер 11; символ ), то есть правая скобка, – номер 13. Таким образом, для нумерации исходных знаков используются нечетные числа от 1 до 13. Символы импликации, конъюнкции и эквиваленции и квантор существования в исчислении Гёделя не фигурируют; эти логические операции могут быть выражены через отрицание, дизъюнкцию и квантор общности.

Далее нумеруются переменные x1, у1, z1,..., вместо которых в арифметические формулы подставляются числа. Для этого используются простые числа, начиная с 17. Аналогичным способом нумеруются предикатные переменные x2, y2, z2,... (переменные, на места которых в формулах подставляются знаки свойств и отношений), только для нумерации используются квадраты простых чисел, начиная с 17 (символ х2 получает номер 17², символа y2– номер 19² и т. д.).

Затем следует нумерация последовательностей символов (частным случаем которых являются формулы). Здесь правило присвоения номеров таково: если имеется последовательность из k символов, имеющих номера соответственно n1, n2, ... nk, то номер этой последовательности имеет вид: 2ⁿ¹ * Зⁿ² * 5ⁿ³– ... pk^nk, где pk – k-тое простое число, начиная с двух. Покажем наглядно, как «работает» в этом случае гёделизация. Пусть дана формула Vх1(х2(х1)) (она читается: «Для всякого натурального числа x1 выполняется свойство х2). Найдем ее гёделев номер. Выпишем по порядку гёделевы номера входящих в формулу символов: 9, 17,11,289,11,17,13,13. Номер N рассматриваемой формулы таков:

N=2⁹ • З¹⁷ • 5¹¹ • 7²⁸⁹• 11¹¹• 13¹⁷ • 17¹⁸ • 19¹³.

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

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

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

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

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

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

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

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

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