Клини С.К. Математическая логика.
Пер. с англ. Изд. 4

Оглавление

Предисловие к русскому изданию

Имя автора этой книги не нуждается в рекомендации. На его "Введении в метаматематику" выросло не одно поколение специалистов по математической логике и основаниям математики. Отличия настоящей книги от классического "Введения" достаточно ясны из авторского предисловия. В двух словах они сводятся к тому, что перед нами теперь не руководство, претендующее (и не без оснований) на полноту освещения обширного комплекса проблем, а университетский учебник. С другой стороны, в этот учебник, несмотря на его скромный объем, попали многие вопросы, не нашедшие места в большой книге Клини (например, иерархия степеней неразрешимости, интерполяционная теорема, теоремы Бета и Робинсона).

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

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

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

Мы выражаем искреннюю признательность автору, любезно приславшему список опечаток и исправлений к английскому изданию (французский перевод, изданный в 1970 г., оказался практически калькой с английского и дополнительных изменений не вызвал), а также Р.И.Пименову и В.А.Лившицу за помощь при переводе.

Предисловие

После выхода в свет моего "Введения в метаматематику" (1952), предназначенного для студентов старших курсов, я не собирался писать другую книгу. Но в силу различных обстоятельств мне пришлось размышлять о необходимости краткого изложения отдельных разделов "Введения", рассчитанного на более широкую аудиторию или на менее подготовленных читателей. Эти размышления привели меня к новым вариантам изложения, и благоприятный прием, который они встретили, в конечном счете и склонил меня к тому, чтобы подготовить теперешнюю книгу, рассчитанную на начинающих.

Во "Введении в метаматематику" (в дальнейшем цитируется как [ВМ]) изложение математической логики как таковой начиналось лишь с пятой главы (на основе некоторых определений, данных в гл.IV). Подготовленные студенты могут пройти вводный материал первых глав [ВМ] достаточно быстро. Но для менее подготовленных студентов или в условиях, когда на курс отведено меньше времени, трата времени на столь подробное введение является ненужной роскошью. И теперь я пришел к убеждению, что как с педагогической, так и с научной точек зрения более разумно с самого начала приступать непосредственно к изучению логики, даже если и не все мотивы и не все критерии выбора того или иного способа изложения выявлены заблаговременно. А соответствующее "введение" можно сделать и позже.

Исходя из этих соображений, я отвел часть 1 (гл.I–III) настоящей книги достаточно подробному, хотя и элементарному рассмотрению математической логики (узкому исчислению предикатов), что по существу соответствует материалу гл.V–VII и § 73 [ВМ]. Изложение здесь не исчерпывается каким-либо одним вариантом формулировки логической теории и приобретением должных навыков в этом направлении, что можно было бы сделать даже и на более элементарном уровне. Для работ современных логиков характерно весьма гибкое изложение материала, использующее различные формулировки одних и тех же идей, с переходами от одной формулировки к другой, более соответствующей конкретным целям данного момента. В соответствии со сказанным читатель в части I книги встретится сначала с более полным, нежели в [ВМ], изложением теории моделей (основанном на истинностных таблицах), затем с гильбертовской теорией доказательств (основанной на системах постулатов с правилом modus ponens) и, наконец, с теорией доказательств, пользующейся и производными правилами вывода. Эти производные правила по существу очень близки к правилам, принятым в генценовских системах натурального вывода, которыми я пользуюсь при преподавании логики начиная с 1936 г. (В гл.VI вводится четвертая формулировка логики в виде генценовских секвенциальных систем.)

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

Если говорить о содержании части II более конкретно, то гл.IV служит запоздалым "введением" (сокращенным вариантом гл.I–III [ВМ]) и содержит также введение и в общий очерк формальной арифметики (гл.IV и VIII [ВМ]). Глава V содержит обзор знаменитых результатов Геделя, Черча и др., касающихся неполноты и неразрешимости; изложение ведется в терминах машин Тьюринга, зачастую без подробных доказательств. (Обзор этот касается основных результатов § 42 и части III [BM], но не касается подробностей развитой там теории.) Эти главы посвящены не столько чистой логике, сколько основаниям математики.

В гл.VI основное внимание вновь уделяется логике. Теорема Геделя о полноте и теорема Генцена (а также теоремы Левенгейма, Скулема, Эрбрана, Генкина, Бета, Крейга и А.Робинсона) доказываются здесь с помощью методов, получивших распространение лишь начиная с 1955 г. Имеются более компактные доказательства теоремы Геделя о полноте. Избранный здесь способ изложения основ предмета удобен, по-видимому, тем, что почти с самого начала ясно общее направление движения, а кроме того, можно надеяться, что, проявив достаточно терпения при рассмотрении деталей, мы в конце концов достигнем цели. Кроме того, такой подход позволяет быстро (хотя и неконструктивно) доказать теорему Генцена. (Глава эта соответствует части IV [ВМ], но сильно отличается от нее по общему подходу и отбору результатов.)

Прохождение всего материала гл.VI в. течение одного семестра может быть облегчено за счет того, что гл.IV и V полностью исключаются из курса, который, таким образом, минуя вопросы оснований математики, полностью сосредоточивается на проблемах логики. (Из материала гл.IV и V лишь очень немногое используется, затем в гл.VI, так что, опуская эти две главы, мы пожертвуем очень немногим из содержания последней главы.)

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

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

Благодарю Х.Уильяма Оливера и Эдварда Полса за предоставление мне записей моих лекций, которые читались в летних школах, организованных Национальным научным фондом, в Уильямстауне в 1956 г. и в Брунсвике в 1961 г. Лекции и конспекты в 1961 г. были переработаны, а в настоящей книге подверглись дальнейшей переработке и изложены значительно более подробно. При переработке были использованы предложения X. Джерома Кислера, Георга Крайзеля и Джулиуса Р.Вайнберга. Кислер на основе своего опыта преподавания по рукописи книги предложил дальнейшие усовершенствования, а также добавил в нее восемь упражнений. Вайнберг, Уильям У.Бун, Бартон Дребен и Ян ван Хейеноорт помогли мне в составлении библиографии. Дребен и ван Хейеноорт, кроме того, помогли оценить результаты Левенгейма, Скулема и Эрбрана более точно, нежели это обычно делается. В заключение благодарю Уильяма Э.Риттера, читавшего корректуру книги параллельно со мной и внесшего в нее ряд исправлений.

Об авторе

Выдающийся американский ученый, посвятивший жизнь исследованиям в области логики и математики ("Введение в метаматематику", "Математическая логика", "Основания интуиционистской математики"). Доктор философии Принстонского университета (1934 г.), профессор Висконсинского университета (Мадисон) с 1948 г. В своих трудах особое внимание уделял алгоритмам и рекурсивным функциям, а также проблемам интуиционистской логики и математики. Ему принадлежит доказательство эквивалентности введенного А. Черчем понятия l-определимости функций с общерекурсивностью. С.К.Клини ввел понятие рекурсивной реализуемости формул, положенное в основу интуиционистской интерпретации арифметических суждений. Участвовал в создании классификации для теоретико-числовых предикатов (1943 г.). С.К.Клини – автор ряда широко известных монографий по математической логике, основаниям математики и теории рекурсивных функций.