В книге дается доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих ее приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств. Следует однако отметить, что в этой книге по существу не затрагиваются интуиционистское и конструктивное направления математической логики. Изложение материала в книге ясное и лаконичное. Основной текст перемежается с большим числом примеров и упражнений. В упражнения автор вынес также некоторые результаты, используемые затем в основном тексте. Это, наряду с лаконичностью изложения, способствовало сокращению размеров книги при весьма обширном содержании. Переводчик и редактор перевода позволили себе без специальных оговорок и примечаний исправить ряд неточностей и опечаток, имевшихся в оригинале, а также привести терминологию и обозначения в соответствие с принятыми в русской литературе. Книгу Э. Мендельсона можно рекомендовать в качестве пособия не только студентам и аспирантам, специализирующимся по математической логике, но также всякому, кто захочет начать систематическое изучение этого предмета.
Author(s): Мендельсон Эллиот
Publisher: ФМЛ
Year: 1971
Language: Russian
Pages: 321
Глава 1. Исчисление высказываний
§ 1. Пропозициональные связки. Истинностные таблицы 19
§ 2. Тавтологии 24
§ 3. Полные системы связок 31
§ 4. Система аксиом для исчисления высказываний 36
§ 5. Независимость. Многозначные логики 46
§ 6. Другие аксиоматизации 48
Глава 2. Теории первого порядка
§ 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
§ 1. Система аксиом 115
§ 2. Арифметические функции и отношения 132
§ 3. Примитивно рекурсивные и рекурсивные функции 135
§ 4. Арифметизация. Геделевы номера 151
§ 5. Теорема Гёделя для теории S 158
§ 6. Рекурсивная неразрешимость. Теорема Тарского. Система Робинсона 167
Глава 4. Аксиоматическая теория множеств 177
§ 1. Система аксиом 177
§ 2. Порядковые числа 188
§ 3. Равномощность. Конечные и счетные множества 199
§ 4. Теорема Хартогса. Начальные порядковые числа. Арифметика порядковых чисел 207
§ 5. Аксиома выбора. Аксиома ограничения 217
Глава 5. Эффективная вычислимость 228
§ 1. Нормальные алгорифмы Маркова 228
§ 2. Алгорифмы Тьюринга 251
§ 3. Вычислимость по Эрбрану—Гёделю. Рекурсивно перечислимые множества 261
§ 4. Неразрешимые проблемы 278
Дополнение. Доказательство непротиворечивости формальной арифметики 282
