Читать онлайн «Лекции по математической логике»

Министерстве высшего а среднего специального образовашя РСФСР МОСКОВСКИЙ ИНСТИТУТ ЭЛЕКТРОННОГО МАШИНОСТРОЕНИЯ Ю. И. Ыашм ЛЕКЦИИ ПО МАТЕМАТИЧЕСКОЙ ЛОГИКЕ Часть П Учебиое пессбие для студентов специальности 0647 Рекомендовано Редссветом института в качестве учебного пособия Москва - 1974 Содержание § I* Введение. Интуитивная вычислимость. § 2. Частично рекурсшвные функции. § 3. Примеры рекурсивных функций* § 4* Перечислимые множества. § 5. Формализация аржфметикш (результаты). § 6. Арвфметвзация формализма (регудьтаты). § 7. Теорема Геделя о неполноте. § 8. Формализация арифметики (доказательства). § 9. Нумерации. § 10. Арифметизация формализма (доказательства). § I. Введение. Интуитивная 1*1. Мы продолжаем формализованное ошсапе математики. Основным объектом первой части курса бндо ^тематическое локаватедьство: было показано, что его подходящим формаль- формальным аналогом является понятие вывода в языке, после чете самые интересные результаты утверждали невыводимое» седер- жатедьвнх математических утверждений (например, гнвотеэы континуума). Основным объектом этой второй части курса будет детер- детерминированный процесс вычисления, или переработки нечисловой информации, короче, алгоритм. Будет построено подходящее формальное описание алгоритмов (точнее, результатов их действий), и саше интересные результаты окажутсн утвержде- утверждениями о несуествовании алгоритмов, вычислимой содержательно списываемые функции. Обе теория - доказательства и вычисления - могут доволь- довольно длительное время излагаться независимо, и мы предпочли именно такое изложение, хотя оно не соответствует историчес- историческому ходу открытий. Когда же техника обеих теорий окажется уке достаточно развитой, можно будет эффективно применять каждую из них для исследования другой. В этом параграфе мы наметим основные опорные точки тео- теории вычислимости на совершенно неформальном уровне строгости, который можно назвать йиэическим. Характерной чертой нашего подхода будет апоеляция к интуитивному представление читателя о том, что такое алгоритм, пользуясь которым очень удобно объяснить структуру основных понятий. Однако при формализации этих понятий в следующем параг- параграфе мы дадим точное описание не алгоритмов. а результатов их работы, ю есть вычислимых функций. С нашей точки зрения, понятие алгоритма слишком многс теряет при любой формализа- формализации, тогда как понятие алгоритмической вычислимости, насколь- насколько мы мокем судить, не теряет ничего существенного. 1. 2. Введем несколько простых основных понятий. Пусть Л, J/ - два множества. Частичной функцией (или отображе- отображением) из X в У мы будем называть любую пару (^>(|), | ) t состоящую из подмножества ^D)с л и отображе- отображения ¦J. 'ZYSJ—*-X • Здеоь "^(/J называется об- областью определения J ; / определена в точке -с *• JC , если д; е- "^C/J I / нигде не определена, если "^(/) пусто. Через 2. = j I, 2, 3, ... j будем обозначать мно- множество натуральных чисел, исключая нудь. Если к ъ / , через (Z*/ мы обозначим /г -кратное прямое произве- произведение Л* на себя, то есть множество векторов (х, *^) , *• е z .