В книге Э. Мендельсона «Введение в математическую логику» дается доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих ее приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств, отсутствующие в книге С. К. Клини «Введение в метаматематику», которая до настоящего времени служила наиболее полным пособием по математической логике. Следует однако отметить, что в отличие от книги С. К. Клини в этой книге по существу не затрагиваются интуиционистское и конструктивное направления математической логики.
Изложение материала в книге ясное и лаконичное. Основной текст перемежается с большим числом примеров и упражнений. В упражнения автор вынес также некоторые результаты, используемые затем в основном тексте. Это, наряду с лаконичностью изложения, способствовало сокращению размеров книги при весьма обширном содержании.
Переводчик и редактор перевода позволили себе без специальных оговорок и примечаний исправить ряд неточностей и опечаток, имевшихся в оригинале, а также привести терминологию и обозначения в соответствие с принятыми в русской литературе.
Книгу Э. Мендельсона можно рекомендовать в качестве пособия не только студентам и аспирантам, специализирующимся по математической логике, но также всякому, кто захочет начать систематическое изучение этого предмета.
Во втором издании книги исправлены опечатки и отдельные погрешности, замеченные после выхода в свет первого издания. Редактор благодарен Н. М. Нагорному и А. Л. Семенову, указавшим на ряд неточностей, допущенных в первом издании книги.
С. И. Адян
***
Предисловие
В этой книге мы попытались представить сжатое введение в некоторые основные разделы математической логики. Чтобы дать полное и точное изложение основных и наиболее важных вопросов, мы опустили такие дополнительные темы, как модальная, комбинаторная и интуиционистская логики, а также некоторые интересные, но более специальные вопросы, как, например, степени рекурсивной неразрешимости.
Придерживаясь того мнения, что начинающим следует предлагать наиболее естественные и легкие доказательства, мы применяем самые непринужденные теоретико-множественные методы. Значение требования конструктивных доказательств может быть оценено только после известного опыта занятий математической логикой. В конце концов, если уж нам предстоит быть изгнанными из «канторова рая» (как назвал Гильберт неконструктивную теорию множеств), то по крайней мере мы должны знать, чего лишаемся.
Пять глав книги удобно распределить на два семестра, а для курса в один семестр вполне подойдут главы с 1 по 3 (при этом можно, если это потребуется для ускорения, опустить §§ 5 и 6 главы 1 и §§ 10—12 главы 2). Мы будем отмечать верхним индексом Б упражнения, которые, вероятно, будут трудны для начинающего, и верхним индексом А — упражнения, предполагающие знакомство с материалом, недостаточно освещенным в тексте.
Настоящая книга представляет собой расширенное воспроизведение записей полугодового курса лекций по математической логике, читанного автором с 1958 по 1960 г. в Колумбийском университете, а в 1961 и 1962 гг. в Куинс колледже. Автор надеется, что эта книга может быть прочитана без особого труда всяким, кто имеет некоторый опыт абстрактного математического мышления; при этом каких-либо конкретных предварительных знаний не требуется. Автор хотел бы поблагодарить Дж. Баркли Россера за поддержку и руководство во время аспирантских занятий логикой, а также с признательностью отметить несомненное влияние, оказанное на него книгами Гильберта и Бер-найса [1934, 1939], Клини [1952], Россера [1953] и Чёрча [1956].
Эллиот Мендельсон
New York, Январь 1963
