Шенфилд Дж. Математическая логика: Пер. с англ. М., 1975. - 528 c.
Книга известного американского логика Дж.Шенфилда знакомит читателя с основами современной математической логики и теории алгоритмов.
Книга может быть рекомендована в качестве учебника по курсам математической логики и теории алгоритмов в университетах и пединститутах.
ОГЛАВЛЕНИЕ
Предисловие редактора ...................... 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
Часть 1
Часть 2
