ОГЛАВЛЕНИЕ

От редактора перевода .. 5
Предисловие.. 6
Введение 7

Глава 1. Исчисление высказываний .. 19
§ 1. Пропозициональные связки. Истинностные таблицы 19
§ 2. Тавтологии 24
§ 3. Полные системы связок 31
§ 4. Система аксиом для исчисления высказываний 35
§ 5. Независимость. Многозначные логики 45
§ 6. Другие аксиоматизации 47

Глава 2. Теории первого порядка. 52
§ 1. Кванторы. 52
§ 2. Интерпретации. Выполнимость и истинность. Модели .. 56
§ 3. Теории первого порядка.. 63
§ 4. Свойства теорий первого порядка . 67
§ 5. Теоремы о полноте. 71
§ 6. Некоторые дополнительные метатеоремы 80
§ 7. Правило С .. 83
§ 8. Теории первого порядка с равенством. 85
§ 9. Введение новых функциональных букв и предметных констант 92
§ 10. Предваренные нормальные формы .. 95
§ 11. Изоморфизм интерпретаций. Категоричность теорий . 101
§ 12. Обобщенные теории первого порядка. Полнота и разрешимость 103

Глава 3. Формальная арифметика. 115
§ 1. Система аксиом 115
§ 2. Арифметические функции и отношения. 130
§ 3. Примитивно рекурсивные и рекурсивные функции . 133
§ 4. Арифметизация. Гёделевы номера.. 150
§ 5. Теорема Гёделя для теории S 158
§ 6. Рекурсивная неразрешимость. Теорема Тарского. Система Робинсона 166

Глава 4. Аксиоматическая теория множеств 176
§ 1. Система аксиом .. 176
§ 2. Порядковые чис/ьа 187
§ 3. Равномощность. Конечные и счетные множества. 198
§ 4. Теорема Хартогса. Начальные порядковые числа. Арифметика порядковых чисел 205
§ 5. Аксиома выбора. Аксиома ограничения.. 216

Глава 5. Эффективная вычислимость.. 228
§ 1. Нормальные алгорифмы Маркова .. 228
§ 2. Алгорифмы Тьюринга. 251
§ 3. Вычислимость по Эрбрану— Гёделю. Рекурсивно перечислимые множества .. . 261
§ 4. Неразрешимые проблемы. 279

Дополнение. Доказательство непротиворечивости формальной арифметики . . 282

Литература. 296
Алфавитный указатель .. 310
Символы и обозначения.. 318

***

От редактора перевода

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

Изложение материала в книге ясное и лаконичное. Основной текст перемежается с большим числом примеров и упражнений. В упражнения автор вынес также некоторые результаты, ис­пользуемые затем в основном тексте. Это, наряду с лаконич­ностью изложения, способствовало сокращению размеров книги при весьма обширном содержании.

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

Книгу Э. Мендельсона можно рекомендовать в качестве посо­бия не только студентам и аспирантам, специализирующимся по математической логике, но также всякому, кто захочет начать систематическое изучение этого предмета.

В третьем издании книги исправлены опечатки и отдельные погрешности, замеченные после выхода в свет второго издания.

С. И. Адян