Читать онлайн «Теория формальных систем»

Оглавление МАТЕМАТИЧЕСКАЯ ЛОГИКА И ОСНОВАНИЯ МАТЕМАТИКИ МОСКВА «НАУКА* ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ ТЕОРИЯ ФОРМАЛЬНЫХ СИСТЕМ Р. СМАЛЬЯН Перевод с английского Н. К. КОСОВСКОГО Под редакцией Н. А. ШАНИНА МОСКВА «НАУКА* ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ 1981 22. 12 С 50 УДК 512 THEORY OF FORMAL SYSTEMS BY Raymond M. Главная редакция физико-математической литературы, 1981 ОГЛАВЛЕНИЕ Предисловие редактора русского перевода ... . 9 Введение ^ Глава I Формальные математические системы 15 Раздел # А. Элементарные формальные системы . 16 § 0. Мотивировка 16 § 1. Определение элементарной формальной системы 18 § 2. Альтернативное определение элементарных формальных систем 21 § 3. Представимость 22 § 4. Математические системы 25 Раздел ф Б. Рекурсивная перечислимость ... . 27 § 5. Рекурсивно перечислимые отношения в множестве чисел 27 § 6. Гёделева нумерация 28 § 7. Универсальная система U 31 § 8. Рекурсивная неразрешимость системы U . 33 Добавление. Формальная представимость Т и Т0 35 Глава II Формальная представимость и рекурсивная перечислимость 39 § 0. Некоторые предварительные принципы . 39 Раздел # А. Свойства замкнутости 41 § 1. Замкнутость относительно экзистенциальной определимости . ... 41 Приложения 45 § 2. Разрешимость над К 48 Раздел ф Б. Рекурсивная перечислимость ... . 50 § 3. Рекурсивная перечислимость некоторых основных арифметических отношений 50 § 4. Рекурсивные и частичные рекурсивные функции 51 § 5. Ограниченная квантификация; конструктивная определимость 52 Раздел # В. Преобразования алфавитов. Гёделева нумерация 55 § 6. Расширения алфавитов 55 § 7. Диадическая гёделева нумерация ... . 56 6 ОГЛАВЛЕНИЕ § 8. Разрешимость 58 § 9. Лексикографическое упорядочение; и-адическое представление чисел 59 § 10. Допустимые гёделевы соответствия ... 63 § 11. Дополнительные результаты о допустимости . 64 Раздел # Г. Краткое резюме 65 Глава III Неполнота и неразрешимость 66 Раздел # А. Неполнота 69 § 1. Представляющие системы 69 § 2. Первая диагонализационная лемма. Теорема Тар- ского 71 § 3. Непротиворечивость и полнота. Теорема Гёделя 74 § 4. Вполне представимость и определимость в Z . 75 § 5. Отделимость в Z. Теоремы Россера ... . 77 § 6. Симметричные системы 80 § 7. Расширения 82 Раздел # Б. Неразрешимость 83 § 8. Системы с эффективной представляющей функцией 84 § 9. Неразрешимость 86 § 10. Нормальность 88 § 11. Дополнительные теоремы 88 § 12. Универсальные системы 90 § 13. Неразрешимость и неполнота ... . 91 Раздел # В. Неразрешимость и рекурсивная неотделимость 92 § 14. Определимость в формальных системах ... 92 § 15. Расширения 93 § 16. Рекурсивная неотделимость 93 § 17. Отделение РН множеств в системах ... 95 § 18. Системы Россера 96 § 19. Рекурсивная неотделимость диагональных множеств Т*, R* 97 Глава IV Теория рекурсивных функций 102 Раздел # А.