Перевод с английского А.С. Есенина-Вольпина.
Под редакцией В.А. Успенского.
Имя одного из крупнейших современных специалистов в области математической логики С. К. Клини знакомо советскому читателю по русскому переводу его фундаментального труда "Введение в метаматематику" (ИЛ, 1957), ставшего настольной книгой для всех, кто занимается математической логикой, рекурсивными, функциями и основаниями математики.
Книга является самой обширной из имевшихся на момент её выхода в свет монографий по математической логике и теории рекурсивных функций. Она не предполагает со стороны читателя никаких специальных познаний и поэтому может считаться общедоступной. Книга предназначена для глубокого изучения предмета и рассчитана как на специалистов по математической логике и теории рекурсивных функций, так и на лиц, желающих впервые, но серьезно, изучить эти науки.
Author(s): Клини С.К.(Kleene S.C.)
Publisher: ИЛ
Year: 1957
Language: Russian
Commentary: вычищен от грязи (точек); по сравнению с предыдущими файлами djvu практически нет "проблемы ИНЬ" (замена "и" на "н" и "н" на "и", особенно в мелком тексте: оглавлении, сносках и т.п.)
Pages: 527
Титульный лист 3
Аннотация 4
От переводчика 5
Предисловие 7
Часть первая. ПРОБЛЕМЫ ОСНОВАНИЙ МАТЕМАТИКИ 9
Глава I. Теория множеств 11
§ 1. Счетные множества 11
§ 2. Канторовский диагональный метод 13
§ 3. Кардинальное число 15
*§ 4. Теорема эквивалентности, конечные и бесконечные множества 18
*§ 5. Высшие трансфинитные кардинальные числа 21
Глава II. Некоторые основные концепции 25
§ 6. Натуральные числа 25
§ 7. Математическая индукция 27
§ 8. Система объектов 29
*§ 9. Арифметика и анализ 33
§ 10. Функции 36
Глава III. Критика математических рассуждений 39
§ 11. Парадоксы 39
§ 12. Первые выводы из парадоксов 42
§ 13. Интуиционизм 47
§ 14. Формализм 53
§ 15. Формализация теории 58
Часть вторая. МАТЕМАТИЧЕСКАЯ ЛОГИКА 65
Глава IV. Формальная система 67
§ 16. Формальные символы 67
§ 17. Правила образования 69
§ 18. Свободные и связанные переменные 72
§ 19. Правила преобразования 76
Глава V. Формальный вывод 81
§ 20. Формальный вывод 81
§ 21. Теорема о дедукции 84
§ 22. Теорема о дедукции (окончание) 87
§ 23. Введение и удаление логических символов 91
*§ 24. Зависимость формул и варьирование переменных 94
Глава VI. Исчисление высказываний 100
§ 25. Формулы исчисления высказываний 100
§ 26. Эквивалентность, замена 104
§ 21. Эквивалентность, двойственность 109
§ 28. Оценка, непротиворечивость 114
§ 29. Полнота, нормальная форма 120
§ 30. Разрешающая процедура, интерпретация 125
Глава VII. Исчисление предикатов 130
§ 31. Предикатные формулы 130
§ 32. Выводимые правила, свободные переменные 134
§ 33. Замена 138
*§ 34. Подстановка 141
§ 35. Эквивалентности, двойственность, предваренная форма 147
§ 36. Оценка, непротиворечивость 153
*§ 37. Теоретико-множественная логика предикатов, k-образы 158
Глава VIII. Формальная арифметика 164
§ 38. Индукция, равенства, замена 164
§ 39. Сложение, умножение, порядок 168
*§ 40. Дальнейшее построение арифметики 171
§ 41. Формализованные вычисления 175
§ 42. Теорема Гёделя 184
Часть третья. РЕКУРСИВНЫЕ ФУНКЦИИ 193
Глава IX. Примитивно-рекурсивные функции 195
§ 43. Примитивно-рекурсивные функции 195
§ 44. Явное определение 198
§ 45. Предикаты, представления с помощью простых множителей 201
§ 46. Возвратная рекурсия 207
*§ 47. Равномерность 210
§ 48. β-функция Гёделя 214
§ 49. Примитивно-рекурсивные функции и арифметический формализм 217
Глава X. Арифметизация метаматематики 221
§ 50. Метаматематика как обобщенная арифметика 221
§ 51. Рекурсивные метаматематические определения 225
§ 52. Гёделевская нумерация 228
*§ 53. Индуктивные и рекурсивные определения 231
Глава XI. Обще-рекурсивные функции 234
§ 54. Формальное вычисление примитивно-рекурсивных функций 234
§ 55. Обще-рекурсивные функции 241
§ 56. Арифметизация формализма рекурсивных функций 246
§ 57. μ-оператор, нумерация, диагональный процесс 248
§ 58. Нормальная форма, теорема Поста 257
*§ 59. Обще-рекурсивные функции и арифметический формализм 262
§ 60. Теорема Чёрча, обобщенная теорема Гёделя 265
§ 61. Симметричная форма теоремы Гёделя 273
Глава XII. Частично-рекурсивные функции 283
§ 62. Тезис Чёрча 283
§ 63. Частично-рекурсивные функции 288
§ 64. 3-значная логика 296
§ 65. Гёделевские номера 303
§ 66. Теорема о рекурсии 310
Глава XIII. Функции, вычислимые по Тьюрингу 317
§ 67. Машины Тьюринга 317
§ 68. Вычислимость рекурсивных функций 323
§ 69. Рекурсивность вычислимых функций 332
§ 70. Тезис Тьюринга 334
*§ 71. Проблема тождества для полугрупп 338
Часть четвертая. МАТЕМАТИЧЕСКАЯ ЛОГИКА (дополнительные разделы) 343
Глава XIV. Исчисление предикатов и системы аксиом 345
§ 72. Гёделевская теорема о полноте 345
§ 73. Исчисление предикатов с равенством 353
*§ 74. Элиминируемость (устранимость) описательных определений. 359
§ 75. Система аксиом, парадокс Сколема, натуральный ряд чисел 373
§ 76. Проблема разрешимости 382
Глава XV. Непротиворечивость; классическая и интуиционистская системы 389
§ 77. Формальная система Генцена 389
§ 78. Теорема Генцена о нормальной форме 396
*§ 79. Доказательства непротиворечивости 406
§ 80 Разрешающая процедура, интуиционистская недоказуемость 424
§ 81. Редукции классических систем к интуиционистским 434
§ 82. Рекурсивная реализуемость 442
ДОБАВЛЕНИЯ ПЕРЕВОДЧИКА 457
Добавление I. Доказательство второй теоремы Гёделя 459
Добавление II. Восполнение пробела в §§ 49 и 74 474
Добавление III. О формализуемости перехода от (iv) к (v) в доказательстве теоремы 36 479
Добавление IV. Построение формулы В примера 2 § 79 479
Добавление V. Об устранимости равенства и неопределенных описаний 481
Добавление VI. О формализации индукции до порядковых чисел, меньших ε_0, в системе гл. IV (по Гильберту—Бернайсу [1939,стр.361—366]) 484
Добавление VII. Доказательство непротиворечивости классической арифметики с помощью индукции до ε_0 (по Шютте). Результат П. С. Новикова 485
Библиография 493
Символы и обозначения 510
Список сокращений 511
Предметный и авторский указатель 511
Оглавление 524
Исправление и опечатки 527
