Мендельсон Э. Введение в математическую логику

Мендельсон Э. Введение в математическую логику. - М., 1971. - 322 с.
Дается доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих ее приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств, отсутствующие в книге С. К. Клини «Введение в метаматематику», которая до настоящего времени служила наиболее полным пособием по математической логике. Следует однако отметить, что в отличие от книги С. К. Клини в этой книге по существу не затрагиваются интуиционистское и конструктивное направления математической логики.Значительная роль в книге отведена упражнениям, куда вынесена часть материала, используемого в основном тексте.
Оглавление
От редактора перевода..........................................................5
Предисловие ......................................................................6
Введение ..........................................................................7
Глава 1. Исчисление высказываний......................................19
§ 1. Пропозициональные связки. Истинностные таблицы............19
§ 2. Тавтологии..........................................................24
§ 3. Полные системы связок............................................31
§ 4. Система аксиом для исчисления высказываний ................36
§ 5. Независимость. Многозначные логики . .........................46
§ 6. Другие аксиоматизации............................................48
Глава 2. Теории первого порядка......................53
§ 1. Кванторы............................................................53
§ 2. Интерпретации. Выполнимость и истинность. Модели..........57
§ 3. Теории первого порядка ..........................................64
§ 4. Свойства теорий первого порядка................................67
§ 5. Теоремы о полноте ................................................71
§ 6. Некоторые дополнительные метатеоремы........................81
§ 7. Правило С ..........................................................83
§ 8. Теории первого порядка с равенством ..........................86
§ 9. Введение новых функциональных букв и предметных констант 93
§ 10. Предваренные нормальные формы................................96
§ 11. Изоморфизм интерпретаций. Категоричность теорий............102
§ 12. Обобщенные теории первого порядка. Полнота и разрешимость .....104
Глава 3. Формальная арифметика..........................................115
§ Система аксиом......................................................115
§ 2. Арифметические функции и отношения..........................132
§ 3. Примитивно рекурсивные и рекурсивные функции..............135
§ 4. Арифметизация. Гёделевы номера ..............................151
§ 5. Теорема Гёделя для теории S......................................158
§ 6. Рекурсивная неразрешимость. Теорема Тарского. Система Робинсона.......167
Глава 4. Аксиоматическая теория множеств . .........................177
§ 1. Система аксиом.......................................177
§ 2. Порядковые числа..................................................188
§ 3. Равномощность. Конечные и счетные множества................19Ї)
§ 4. Теорема Хартогса. Начальные порядковые числа. Арифметика порядковых чисел.......207
§ 5. Аксиома выбора. Аксиома ограничения............. 217
Глава 5. Эффективная вычислимость ....................................228
§ 1. Нормальные алгорифмы Маркова..................................228
§ 2. Алгорифмы Тьюринга................................................251
§ 3. Вычислимость по Эрбрану—Гёделю. Рекурсивно перечислимые множества............261
§ 4. Неразрешимые проблемы............................................278
Дополнение. Доказательство непротиворечивости формальной арифметики ..........282