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

Смальян Реймонд М.

В книге в систематической форме излагаются основы обширной области математической логики — общей теории формальных систем. Изложение охватывает также основные сведения об алгорифмических (рекурсивных) функциях, перечислимых, разрешимых и креативных множествах, эффективных операциях над множествами и функциями. Автору с помощью удачных теоретических и методических находок (таких, как понятие рудиментарного предиката, специальные способы кодирования слов, существенно упрощающие арифметизацию, и др.) удалось многие результаты математической логики, ранее излагавшиеся громоздко и разрозненно, объединить в единое целое, отделив в них принципиальное ядро от деталей. Это распространяется, в-частности, на знаменитую теорему К. Гёделя о неполноте формализации арифметики и на родственные ей теоремы. Многие интересные результаты, содержащиеся в книге, получены ее автором.

Эта книга — полезное учебное пособие для студентов, аспирантов и математиков различных специальностей, заинтересованных в кратком и ясном изложении важнейших результатов тео­рии формальных систем, теории алгорифмов и их приложений к математической логике.

Москва «Наука» Главная редакция физико-математической литературы 1981

Содержание:

Предисловие редактора русского перевода 9
Введение 13

Г л а в а 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
 §  8. Разрешимость 58
 §  9. Лексикографическое упорядочение; n-адическое представление чисел 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

Раздел # А. Эффективные операции и теоремы о неподвижной точке 102
 §  1. Теорема о перечислимости 103
 §  2. Индексация 105
 §  3. Итерационные теоремы для РП отношений 105
 §  4. Эффективные операции 109
 §  5. Теоремы о неподвижной точке 111
 §  6. Теоремы о сдвоенной рекурсии 115
Раздел # Б. Конструктивно арифметические и рудиментарные отношения 117
 §  7. Некоторые предварительные замечания 118
 §  8. Диадическая конкатенация 119
 §  9. Рудиментарные отношения 121
 § 10. Строгие элементарные формальные системы 126
 § 11. Арифметизация элементарной диадической арифметики 127
Раздел # В. Перечислимость и теоремы о нормальной форме 133
 § 12. Теорема Клини о перечислимости 133
 § 13. Отделимость разностей РП множеств 133
 § 14. Частичные рекурсивные функции 134
 § 15. Индексация функций 135

Г л а в а V
Креативность и эффективная неотделимость 138

Раздел # А. Креативность и эффективная неотделимость 138
 §  1. Продуктивные и креативные множества; рекурсивная и эффективная неотделимость 138
 §  2. Много-односводимость и одно-односводимость 141
 §  3. Креативные системы 143
 §  4. Эффективная неотделимость 144
 §  5. Эффективно россеровские системы 146
Раздел # Б. Дальнейшее построение теории продуктивных множеств 147
 §  6. Слабо продуктивные функции 147
 §  7. Равномерная сводимость 149
 §  8. Универсальные множества 152
 §  9. 0 равномерной сводимости 153
 § 10. Равномерная представимость 155
 § 11. Биравномерность 155
Раздел # В. Эффективная неотделимость, и сдвоенная продуктивность 157
 § 12. Сдвоенно продуктивные пары 157
 § 13. Сводимость пар к парам 161
Раздел # Г. Сдвоенная универсальность 163
 § 14. Сдвоенно универсальные и вполне сдвоенно универсальные пары 163
 § 15. Равномерная сводимость 163
 § 16. Слабо сдвоенно продуктивные пары 165
 § 17. О сдвоенно продуктивных парах 166
 § 18. Применение к системам Россера 170
 § 19. Равномерная сводимость 170
 § 20. Обобщение эффективной неотделимости 173
Раздел # Д. Сдвоенный изоморфизм 175
 § 21. Сдвоенный изоморфизм 175
 § 22. Эквивалентность и сдвоенный изоморфизм 178
 § 23. Сдвоенный изоморфизм систем Россера 180

Д о п о л н е н и е.
Приложения к математической логике 181

 §  1. Теории 181
 §  2. Определимость функций; нормальность теории 186
 §  3. ω-непротиворечивость. Перечислимость в (Т). Теорема Гёделя 187
 §  4. Конструкция Россера 189
 §  5. Теории Гёделя и теории Россера 191
 §  6. Теории, в которых определимы сложение и умножение 194
 §  7. Некоторые специальные теории 195
 §  8. Существенная неразрешимость 196
 §  9. Существенная креативность 197
 § 10. Точные теории Россера 199

Библиография 202

Указатель определений 205

Указатель обозначений 207
Шкаф 3, полка В