Посвящается Бертрану Расселу

I. Введение

В 1931 г, в одном из немецких научных журналов появилась сравнительно небольшая статья с довольно-таки устрашающим названием» «Uber formal unentscheidbare Satze deu Principia Mathematica iind verwandter Systeme («О формально неразрешимых предложениях Principia Mathematica и родственных систем»). Автором ее был двадцатипятилетний математик из Венского университета Курт Гёдель, впоследствии работавший в Принстонском институте высших исследований. Работа эта сыграла решающую роль в истории логики и математики. В решении Гарвардского университета о присуждении Гёделю почетной докторской степени (1952 г.) она была охарактеризована как одно из величайших достижений современной логики.

Однако в момент опубликования ни название гёделевч ской работы, ни содержание ее ничего не говорили большинству математиков. Упомянутые в ее названии Principia Mathematica — это монументальный трехтомный трактат Алфреда Норта Уайтхеда и Бертрана Рассела, посвященный математической логике и основаниям математики^ знакомство с трудом отнюдь не являлось необходимым условием для успешной работы в большей части разделов математики. Интерес к разбираемым в работе Гёделя вопросам всегда был уделом весьма немногочисленной группы ученых. В то же время рассуждения, приведенные Гёделем в его доказательствах, были для своего времени столь необычными, что для полного их понимания требовалось исключительное владение предметом и знакомство с литературой, посвященной этим весьма специфическим проблемам.

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

Знаменитая работа Гёделя посвящена центральной проблеме оснований математики. Чтобы додать источник возникновения и характер этой проблемы, нам понадобятся некоторые предварительные рассмотрения. Каждый, кому приходилось преподавать элементарную геометрию, помнит, что геометрия строится как дедуктивная наука. Этим она отличается от экспериментальных наук, выводы которых приемлемы постольку, поскольку они согласуются с данными наблюдения и опыта. Идея о том, что любое верное утверждение может быть получено в качестве заключительного шага строгого логического доказательства, сформировалась еще в Древней Греции; именно греческим математикам принадлежит честь открытия так называемого «аксиоматического метода» и применения его для систематического изложения геометрии. Для аксиоматического метода характерно, что некоторые предложения — так называемые аксиомы, или постулаты (примером может служить предложение, согласно которому через любые две точки можно провести одну и только одну прямую) — принимаются без доказательства; все же остальные предложения данной теории выводятся затем из этих аксиом. Можно сказать, что аксиомы образуют «базис» системы, в то время как теоремы, получаемые из аксиом при помощи одних только логических законов, — это «надстройка».

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

Однако в течение последних двух столетий аксиоматический метод стал применяться все более широко и интенсивно.. И для новых областей математики, и для более традиционных ее разделов, таких, например, как обычная арифметика целых чисел, были сформулированы системы аксиом, представляющие эти математические дисциплины в некого-.

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

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

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

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

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

Еще несколько слов об обозначениях, используемых в доказательстве теоремы Гёделя. Начнем с примера. Формула « gx(x=si/)» имеет гёделевский номер т (см. выше, стр. 42), а переменная «</» — гёделевский номер 13. Подставив в эту формулу вместо переменной, имеющей гёделевский номер 13 (т. е. вместо «у») цифру, обозначающую число т, мы получим в результате формулу «Hx(x=Sm)», выражающую утверждение, согласно которому существует такое число х, что это х непосредственно следует за числом т.

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

¹ Читатель должен твёрдо уяснить себе, что хотя «Dem (х, г)» кодирует некоторое метаматематическое утверждение, сама эта запись является формулой арифметического исчисления. Формула эта в более привычных обозначениях может быть записана в виде «f(x, z)=0», где буква f обозначает некоторый довольно-таки сложный комплекс арифметических операции над числами. Однако эта более привычная запись не «подсказывает» сразу своей метаматематической интерпретации, почему мы и предпочли запись, приведенную в тексте.

² Цифра — это числовой знак, или имя числа (ср. выше примечание авторов к стр. 18. — Прим, перев.

менной с гёделевским номером 13 цифры «т». Такая метаматематическая характеристика однозначно определяет некоторое число, являющееся некоторой определенной функцией от чисел т и 13, причем сама эта функция может быть выражена средствами нашей формализованной арифметической системы. Значит, и само число можно выразить внутри нашего исчисления. Обозначим его через «sub(m, 13, /и)», напоминая тем самым, что речь идет о гёделевском номере формулы, полученной из формулы, имеющей гёделевский номер т подстановкой ¹ вместо входящей в нее переменной с гёделевским номером 13 цифры, обозначающей число tn. Вообще, через «sub(у, 13, у)» мы будем обозначать теперь арифметическую формулу, выражающую внутри арифметического исчисления метаматематическую характеристику: «гёделевский номер формулы, получаемой из формулы, имеющей гёделевский номер у, подстановкой вместо входящей в нее переменной, имеющей геделевский номер 13, цифры, обозначающей число «//». Если в выражение «sub(z/, 13, у}» мы подставим теперь вместо ««/» какую-нибудь определенную цифру, скажем, цифру, обозначающую число т, или выражение 243 000 000, то получающееся в результате выражение также будет обозначать некоторое определенное натуральное число, являющееся при том гёделевским номером некоторой определенной формулы.

У читателя не раз мог возникнуть вопрос, почему, собственно, мы говорили сейчас не просто о «числе у», а — столь вычурно и длинно! — о «цифре, обозначающей уъ. Впрочем, сама форма вопроса уже отчасти подсказывает ответ. Мы ведь уже упоминали о важном различии между понятиями «число» и «цифра». Цифра — это некоторый знак, т. е. выражение языка, которое можно записывать, стирать, зачеркивать, повторять и т. д., и т. п. Число же — это то, именем (или названием, обозначением} чего является обозначающая его цифра; само по себе число нельзя записать; стереть, зачеркнуть, повторить. Скажем, когда мы говорим, что 10 — число пальцев на обеих руках, то мы характеризуем этой фразой некоторое «свойство» множества наших пальцев — свойство, которое, разумеется, «цифрой» никак не назовешь. Но число 10 может записываться как арабскими цифрами: «10», тан и римскими цифрами (т. е. прописными латинскими буквами) «X»; эти имена сами по себе, конечно, различны, хотя обозначают они одно и то же число. Так вот, когда мы производим подстановку вместо числовой переменной (которая сама есть-просто знак, буква), то мы ставим вместо одного знака другой знак. Мы не можем подставить вместо знака число — ведь число, являющееся некоторым вом (или, как иногда говорят, понятием), вообще не есть Что-то такое, что можно непосредственно нанести на бумагу. Итак, вместо числовой — а лучше сказать, цифровой! — переменной мы подставляем именно цифру (или цифровое выражение, скажем, «sO» или «7 + 5»)., а не число. Именно поэтому мы выше говорили о подстановке цифры (обозначающей число) у, а не самого числа у, в интересующее нас метаматематическое выражение.

Читатель может далее поинтересоваться, какое же число обозначается выражением «sub (у, 13, у)», если формула, имеющая гёделевский номер у, не содержит переменной, имеющей гёделевский номер 13, т. е. попросту, если формула «е содержит переменной «I/». Скажем, sub (243 000 000, 13, 243 000 000) есть гёделевский номер формулы, полученной из формулы, имеющей гёделевский номер 243 000 000 подстановкой вместо переменной «у» цифры ¹ 243 000 000. Выше (спр, 44—45) мы уже выяснили, что 243 000 000 — гёделевский номер формулы «0 = 0», не содержащей переменной «у». Но какая же формула получится из формулы «0 = 0» в результате подстановки вместо не входящей в нее переменной «г/» цифры, обозначающей число 243 000 000? Ответ очень простой: раз формула не содержит этой переменной, то и подстановка чисто фиктивная, т. е. такая «подстановка» не меняет формулы. Иначе говоря, число, обозначаемое записью «sub (243 000 000, 13, 243 000 000)», есть само число 243 000 000.

Заметим, наконец, что выражение «sub (у, 13, у)» не является формулой нашей арифметической системы в том смысле, в каком, например, являются формулами выражения «х a (x = s«/)» или «Dem (х, г)», и вот почему. Выражение «0=0» мы называем формулой; такая запись утверждает наличие некоторого отношения между двумя числами, так что имеет смысл ставить вопрос, истинно или ложно это утверждение? Аналогично, когда вместо переменных, входящих в выражение «Dem (х, z)», подставляются некоторые цифры, то получающееся выражение оказывается записью некоторого утверждения (о том, что два числа находятся в некотором отношении), о котором опять-таки имеет смысл ставить вопрос, истинно оно или ложно? То же самое можно сказать и о выражении «3x(x = st/)».

Что же касается выражения «sub (у, 13, {/)», даже если переставить в него вместо «у» какую-нибудь конкретную цифру, то оно все равно не будет ничего утверждать и по этой причине не "будет ни истинным, ни ложным. Выражение

* Напоминаем, что «цифрой» мы здесь всюду называем всю запись Числа, а не отдельный знак такой записи, как обычно; скажем «10» есть цифра, обозначающая число 10, хотя обычно и говорят, что это число заннсывается посредством двух цифр; «1» и «0». ■— Прим, перге.

мия относительно несложен. Задача его сводится к тону, чтобы доказать, что если бы формула G была доказуема, то ее формальное отрицание (т. е. формула «~yx~~Dem (х, sub (п, 13, и)») также было бы доказуемо, и, обратно, если бы отрицание формулы G было доказуемо, то была бы доказуема и сама G. Отсюда мы получаем, что G доказуема в том и только в том случае, если доказуема формула -G¹.

Воспроизведем вкратце первую часть рассуждения Гёделя, согласно которой если G доказуема, то и ~G доказуема. Пусть G доказуема. Тогда должна существовать последовательность арифметических формул, являющаяся доказательством для G. Пусть гёделевский номер доказательства есть k. В таком случае между этим k и числом sub (п, 13,я), являющимся гёделевским номером G, должно иметь место арифметическое отношение, обозначаемое через «Dem :(х, г)>, т. е. «Dem (k, sub (n, 13, n)> должна быть истинной арифметической формулой. Можно, однако, показать, что это арифметическое отношение обладает тем свойством, что если оно имеет место для каких-либо двух чисел, то формула, выражающая это обстоятельство, непременно доказуема. Таким образом, формула «Dem (k, sub (и, 13, п)» не только истинна, но и формально доказуема, т. е. является теоремой. Но правила вывода элементарной логики позволяют нам немедленно вывести из этой теоремы формулу «~yx~Dem (х, sub (/г, 13, «))>. Таким образом, мы вывели из доказуемости формулы G доказуемость ее формального отрицания. Значит, если наша формальная система непротиворечива, то G в ней недоказуема.

Чтобы показать, что доказуемость ~G влечет доказуемость G, требуется аналогичное, но несколько более громоздкое рассуждение, которое мы не будем пытаться здесь воспроизводить.

Как мы уже отмечали, если и некоторая формула, и ее отрицание выводимы из некоторой системы аксиом, то эта система противоречива (несовместна). Поэтому если аксиомы формализованной системы арифметики совместимы, то ни G, ни ее отрицание *не могут быть доказуемыми. Иначе говоря, если наши аксиомы непротиворечивы, то G формально неразрешима в том точном смысле, что ни G, ни ~G не выводимы из арифметических аксиом.

(3) Важность предыдущего заключения не сразу бросается в. глаза, Что особенного,— можно было бы задать вопрос,— -в том, что некоторая формула, сформулированная на арифметическом языке, оказалась неразрешимой? Но приходится признать, что из этого результата действительно вытекают чрезвычайно' важные выводы. Все дело в том, что, хотя формула G и является недоказуемой, можно, как выясняется, чисто метаматематическим рассуждением установить ее истинность. Иными словами, удается показать, что формула G выражает некоторое (довольно-таки громоздко выражаемое, но тем не менее вполне определенное) свойство, с необходимостью принадлежащее всем натуральным числам (аналогично, скажем, свойству, выражаемому гораздо более простой формулой « ул~ (х+3 = 2», интерпретируемой обычно как утверждение, что никакое натуральное число, сложенное с числом 3, не дает в сумме 2).

Приведем здесь рассуждение, устанавливающее истинность формулы G. Во-первых, в предположении непротиворечивости арифметики можно доказать, что метаматематическое утверждение «формула «ух—Dem (х, sub (п, 13, п))» недоказуема» истинно. Во-вторых, такое утверждение представляется (выражается) в арифметике той самой формулой, которая в нем упоминается. В-третьих, мы вспоминаем, что истинным математическим утверждениям при осуществляемом посредством гёделевской нумерации отображении их в арифметику соответствуют истинные же арифметические формулы. (Именно это обстоятельство обусловливает всю плодотворность такого отображения; ситуация здесь совершенно та же, что в аналитической геометрии, где координатное «кодирование» обеспечивает перевод истинных геометрических высказываний в истинные алгебраические высказывания.) Отсюда и вытекает, что формула G, соответствующая 'истинному метаматематическому высказыванию, сама должна быть истинной. Следует, однако, еще раз подчеркнуть, что истинность арифметического высказывания установлена нами отнюдь не формальным выводом выражающей его формулы из аксиом, а посредством некоторого метаматематического рассуждения.

(4) Теперь нам придется напомнить читателю понятие «полноты», введенное нами в заключение раздела, посвященного исчислению высказываний. Мы назвали тогда систему аксиом полной, если любое истинное предложение, выражаемое на языке данной системы, можно из них вывести. В противном случае (т. е. если не каждое истинное предложение, выразимое в данной системе, выводится из ее аксиом) система аксиом «неполна». Но мы только что как раз и установили, что G есть истинная арифметическая формула, не выводимая из арифметических аксиом, иными словами, система аксиом арифметики неполна (разумеется, в предположении непротиворечивости этой системы аксиом). Боль-.

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

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

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

3 УЧ %~Dem (х, у). (А)

Формула эта, если выразить ее словесно, гласит:. «Существует по крайней мере одно натуральное число у, такое, что для любого натурального х числа х и у не находятся между собой в отношении Dem». Если же интерпретировать формулу как метаматематическое высказывание, то мы получим: «Существует по крайней мере одна арифметическая формула, для которой никакая последовательность формул не являемся ее доказательством». Таким образом, формула. А как раз и представляет посылку метаматематического утверждения «Если арифметика непротиворечива, то она неполна». В то же время заключение утверждения «Она (т. е. арифме возможностей любой конкретной аксиоматической системы, а значит, и недоступных для таких машин, сколь бы остроумными и сложными ни были их конструкции и-с какой бы громадной скоростью ни проделывали они. свои операции. Для каждой конкретной задачи в принципе можно построить машину, которой эта задача была бы под силу;- но нельзя создать машину, пригодную для решения любой задачи. Правда, и возможности человеческого мозга могут оказаться ограниченными, так что и человек тогда сможет решит:-» не любую задачу. Но даже если это так, структурные и функциональные возможности человеческого мозга пока еще намного больше по сравнению с возможностями самых изощренных из мыслимых пока машин, так что непосредственной опасности вытеснения людей роботами не видно ’.

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

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

¹ При всем правдоподобии последней фразы она никак не следует изг предыдущего. Вообще, далеко не ясно, как распространенный тезис об ограниченности возможностей моделирования человеческого мышления можно согласовать с материалистической гипотезой о его природе. Ср._к впрочем, заключительные два абзаца авторского текста,— Прим, перев.

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

Послесловие переводчика

Курт Гёдель — крупнейший из живущих сейчас специалистов по математической логике — родился 28 .апреля 1906 г. в Брюнне (ныне г. Брно, Чехословакия). Окончил Венский университет, где защитил докторскую диссертацию и был доцентом в 1933—1938 гг. После аншлюса эмигрировал в США. С 1940 по 1963 г. Гёдель работает в Принстонском институте высших исследований (с 1953 г.-— профессор этого института). Гёдель — почетный доктор Йельского и Гарвардского университетов, член Национальной академии наук США и Американского философского общества.

В 1951 г. К. Гёдель удостоен высшей научной награды США — Эйнштейновской премии. В статье, посвященной это-; му событию, другой крупнейший математик нашего времени Джон фон Нейман писал «Вклад Курта Гёделя в современную логику поистине монументален. Это — больше, чем просто монумент, это веха, разделяющая две эпохи... Без всякого преувеличения можно сказать, что работы Гёделя коренным образом изменили сам предмет логики как науки».

Действительно, даже сухой перечень достижений Гёделя в математической логике показывает, что их автор, по' существу, заложил основы целых разделов этой науки: теории моделей (1930 так называемая теорема о (полноте узкого начисленная предикатов, показывающая, грубо говоря, достаточность средств «формальной логики» для доказательства всех выражаемых на ее языке истинных предложений), конструктивной логики (1932—1933 гг.; результаты о возможности сведения некоторых классов предложений классической

* Цитируем ив сборнику статей «Основания математик»», выпущен* ному в Нью-Йорке в честь 06-яегм К. Гёделя. (оттуда же взяты приведенные выше краткие биографические сведения), 60

допита к як мжумционистским аналогам, положившие начала систематическому употреблению «погружающих операций», позволяющих осуществлять такое сведение различных логических систем друг к другу), формальной арифметики (1932—1933 гг.; результаты о возможности «погружения» классической арифметики в интуиционистскую, показывающие в некотором смысле непротиворечивость первой относительно второй), теории алгоритмов и рекурсивных функций (1934 г.; определение понятия общерекурсивной функции, сыгравшего решающую роль в установлении алгоритмической неразрешимости ряда важнейших проблем математики, с одной стороны, и в реализации логико-математических задач на электронно-вычислительных машинах — с другой), аксиоматической теории множеств (1938 г.; доказательство относительной непротиворечивости аксиомы выбора и континуум- гипотезы Кантора от аксиом теории множеств, положившее начало серии важнейших результатов об относительной непротиворечивости и независимости теоретико-множественных принципов.

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

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

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

которой перекомпоновки материала. Все эти отступления от оригинала специально нами не оговаривались. Опущены также предметный указатель и библиография? читатель может найти дополнительные ссылки по заинтересовавшим его вопросам по монографии С. К. Клини «Введение в метаматематику» (пер. с английского.. М.» Изд-во иностр, лит., 1957).