Клини С.К. Введение в метаматематику ОНЛАЙН

Первая часть книги содержит необходимый подготовительный материал; далее проведено метаматематическое исследование элементарной арифметики с необходимым материалом из математической логики. В восьмой главе второй части изложены знаменитые теоремы Гёделя о неполноте. Третья часть, содержащая в числе прочего изложение теории общерекурсивных и частично-рекурсивных функций, может служить руководством для изучения теории рекурсивных функций.
ОГЛАВЛЕНИЕ
От переводчика…………………….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



Читать онлайн
скачать бесплатно


Теги:
Клини Математическая логика, метаматематика, теория рекурсивных функций

Коментарі до Клини С.К. Введение в метаматематику ОНЛАЙН