Перевод с английского
И. А. ЛАВРОВА и И. А. МАЛЬЦЕВА
Под редакцией
Ю. Л. ЕРШОВА
*
От вътрешната страна на обложката:
Книга известного американского логика Дж. Шенфилда знакомит читателя с основами современной математической логики и теории алгоритмов. В книге систематически изучаются такие важные разделы, как теории первого порядка, теория моделей, вычислимость, иерархии, формальная арифметика, аксиоматическая теория множеств. Имеются два приложения: одно алгебраическое — проблема тождества слов в группах, другое — изложение результатов, связанных с исследованиями континуум-гипотезы в аксиоматической теории множеств. Написанная с глубоким педагогическим тактом, книга содержит обширный материал, многое из которого на русском языке не публиковалось. В зарубежной логической литературе в настоящее время книга Дж. Шенфилда стала одним из основных источников для изучения оснований математики. Несомненно, она представляет большой интерес и для советских специалистов.
Книга может быть рекомендована в качестве учебника по курсам математической логики и теории алгоритмов в университетах и пединститутах. Книга предназначена для всех исследователей, преподавателей, аспирантов и студентов, занимающихся основаниями математики.
Серия «Математическая логика и основания математики» состоит из публикаций, посвященных вопросам теории математического доказательства, теории алгоритмов, логическим исчислениям (классическим и конструктивным), истории математической логики и оснований математики, а также приложениям математической логики к вопросам автоматики и лингвистики. В серию входят монографии, обзорные работы и сборники статей на определенную тему, принадлежащие перу как отечественных, так и зарубежных ученых. Они носят различный характер: некоторые из них рассчитаны на широкий круг научных работников, преподавателей и студентов, между тем как другие имеют в виду более узкие круги специалистов разных профилей.
*
ОГЛАВЛЕНИЕ
Предисловие редактора 7
Предисловие 9
Глава 1. Природа математической логики 11
1.1. Аксиоматические системы (11). 1.2. Формальные системы (13). 1.3. Синтаксические переменные (19).
Глава 2. Теории первого порядка 23
2.1. Функции и предикаты (23). 2.2. Функции истинности (25). 2.3. Переменные и кванторы (28). 2.4. Языки первого порядка (31). 2.5. Структуры (37). 2.6. Логические аксиомы и правила (40). Задачи (44).
Глава 3. Теоремы в теориях первого порядка 47
3.1. Теорема тавтологии (47). 3.2. Результаты о кванторах (54). 3.3 Теорема дедукции (56). 3.4. Теоремы эквивалентности и равенства (58). 3.5. Пренексная форма (62). Задачи (65).
Глава 4. Проблема характеризации 67
4.1. Теорема редукции (67). 4.2. Теорема полноты (70). 4.3. Теорема непротиворечивости (79). 4.4. Теорема Эрбрана (84). 4.5. Добавление функциональных символов (90). 4.6. Расширения с помощью определений (93). 4.7. Интерпретации (98). Задачи (103).
Глава 5. Теория моделей 108
5.1. Теорема компактности (108). 5.2. Изоморфизмы и подструктуры (111). 5.3. Мощность моделей (122). 5.4. Совместная непротиворечивость (124). 5.5. Полные теории (128). 5.6. Категоричность (138). Задачи (144).
Глава 6. Неполнота и неразрешимость 102
6.1. Вычислимость (162). 6.2. Рекурсивные функции (165). 6.3. Явные определения (168). 6.4. Номера последовательностей (174). 6.5. Тезис Чёрча (180). 6.6. Номера выражений (185). 6.7. Представимость (190). 6.8. Теорема Чёрча и теорема о неполноте (196). 6.9. Неразрешимость (201). Задачи (206).
Глава 7. Теория рекурсии 215
7.1. Частичные функции (215). 7.2. Функционалы и отношения (220). 7.3. Свойства рекурсивных функционалов (226). 7.4. Индексы (234). 7.5. Арифметическая иерархия (239). 7.6. Относительная рекурсивпость (244). 7.7 Степени (252). 7.8. Аналитическая иерархия (258). 7.9. Гиперарифметические отношения (262). 7.10. Теорема характеризации (267). 7.11. Теоремы о базисе (276). Задачи (283).
Глава 8. Натуральные числа 300
8.1. Арифметика Пеано (300). 8.2. Теорема о доказательствах непротиворечивости (307). 8.3. Доказательство непротиворечивости (315). 8.4. Применения доказательства непротиворечивости (327). 8.5. Арифметика второго порядка (334). Задачи (343).
Глава 9. Теория множеств 348
9.1. Аксиомы для множеств (348). 9.2. Систематическое построение теории множеств (352). 9.3. Ординалы (359). 9.4. Кардиналы (369). 9.5. Интерпретации теории множеств (379). 9.6. Конструктивные множества (393). 9.7. Аксиома конструктивности (401). 9.8. Вынуждение (408). 9.9. Доказательства независимости (422) 9.10. Большие кардиналы (436). Задачи (452).
Приложение I. Проблема тождества слов 459
Приложение II. Неразветвленное вынуждение 482
Предметный указатель 520
