Клини С.К. Введение в метаматематику. Пер. с анг. - М., 1957. - 528 с.
Книга, написанная выдающимся американским математиком Стивеном Клини, является одной из самых обширных из имеющихся монографий по математической логике и теории рекурсивных функций. Этот фундаментальный труд по праву стал настольной книгой для всех, кто занимается математической логикой, рекурсивными функциями и основаниями математики. Цель автора - дать читателю связное введение в область данных научных дисциплин, а также в исследования по основаниям математики вообще. Первая часть книги содержит необходимый подготовительный материал; далее проведено метаматематическое исследование элементарной арифметики с необходимым материалом из математической логики. В восьмой главе второй части изложены знаменитые теоремы Гёделя о неполноте. Третья часть, содержащая в числе прочего изложение теории общерекурсивных и частично-рекурсивных функций, может служить руководством для изучения теории рекурсивных функций.
ОГЛАВЛЕНИЕ
От переводчика.........................5
Предисловие.............................7
Часть первая ПРОБЛЕМЫ ОСНОВАНИЙ МАТЕМАТИКИ
Глава 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
Часть вторая МАТЕМАТИЧЕСКАЯ ЛОГИКА
Глава 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
§ 27. Эквивалентности, двойственность ....................109
§ 28. Оценка, непротиворечивость........................114
§ 29. Полнота, нормальная форма ......................120
§ 30. Разрешающая процедура, интерпретация ....................125
Глава VII. Исчисление предикатов ......................130
§ 31. Предикатные формулы ...........................130
§ 32. Выводимые правила, свободные переменные .......... 134
§ 33. Замена........... ..........138
§ 34. Подстановка ...............................141
§ 35. Эквивалентности, действенность, предваренная форма 147
§ 36. Оценка, непротиворечивость....... 157
§ 37. Теоретико-множествевная логика предикатов, k-образы .....158
Глава VIII. Формальная арифметика .........................165
§ 38. Индукция, равенства, замена ..................165
§ 39. Сложение, умножение, порядок .............................168
§ 40. Дальнейшее построение арифметики.......................171
§ 41. Формализованные вычисления ............................175
§ 42. Теорема Гёделя ..............................184
Часть третья РЕКУРСИВНЫЕ ФУНКЦИИ
Глава 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
Часть четвертая 4 МАТЕМАТИЧЕСКАЯ ЛОГИКА (дополнительные разделы)
Глава XIV. Исчисление предикатов и системы аксиом . ...................343
§ 72. Гёделевская теорема о полноте ...........................343
§ 73. Исчисление предикатов с равенством .................353
§ 74. Элиминируемость (устранимость) описательных определений .......359
§ 75. Система аксиом, парадокс Сколема, натуральный ряд чисел.......373
§ 76. Проблема разрешимости................................382
Глава XV. Непротпворечивость; классическая и интуиционистская системы 389
§ 77. Формальная система Генцена .......................389
§ 78. Теорема Генцена о нормальной форме..........................396
§ 79. Доказательства непротиворечивости . . . .....................406
§ 80. Разрешающая процедура, интуиционистская недоказуемость .......424
§ 81. Редукции классических систем к интуиционистским..........434
§ 82. Рекурсивная реализуемость.......................442
ДОБАВЛЕНИЯ ПЕРЕВОДЧИКА
Добавление 1. Доказательство второй теоремы Гёделя........469
Добавление 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
Часть 1
Часть 2
