Ю. И. Манин
Лекции
по математической
логике
Части 1 и 2
*** 1974 ***
От нас: 500 радиоспектаклей (и учебники)
на SD‑карте 64(128)GB — ГДЕ?..
Baшa помощь проекту:
занести копеечку — КУДА?..
|
РАСПОЗНАННЫЕ ФРАГМЕНТЫ
0.1. Содержанием математической логики является изучение языка математики. Разумеется, забота о языке и постоянная его перестройка для приведения в соответствие с меняющимся состоянием знаний характерна для любой естественной науки (ср. судьбу "флогистона" и "мирового эфира" в физике). Тем не менее, необходимая работа обычно осуществляется по ходу дела, и то пристальное критическое рассмотрение, которому математика подвергла самое себя и свои средства выражения, представляется уникальным. Причина этого состоит, конечно, в том, что все остальные естественные науки имеют предмет, внеположный им, и эволюция языка науки определяется постоянным сравнением научного описания с описываемой реальностью. Попытка применить эту же схему к математике сразу наталкивается на принципиальную трудность, ибо совершенно не ясно, в каком омыоле числа и множества являются реальностью. Столь же не яоным при внимательней рассмотрении становится ответ на вопрос, что такое истинность (математического рассуждения). Если быть до конца последовательным, следует признать это обстоятельство роковым. * Действительно, до выяснения природы истинностя, мы, по-видимому, нс в состоянии сделать ни одного истинного утверждения, и исследование должно остановиться не начавшись. * Предыдущий абзац не является просто софизмом. Он предопределяет две характерные черты математической логики. Первая состоит в той, что строя формализмы логики, мы неизбежно должны пользоваться неформализованными, интуитивными представлениями, близкими к обычной рабочей интуиции математика. Технический термин для этого - "метаязык”, на котором идет описание "формальных языков", в свою очередь являющихся моделями дедуктивных, в том числе математических (в том числе метаязыксвых!) рассуждений. Положение дел здесь можно сравнить с понятием "элементарности" в физике. Элементарные частицы - это не те объекты, которые являются последними кирпичиками анализа, - скорее это те объекты, дальнейший анализ которых обнаруживает повышение уровня сложности вместо его понижения. "Элементарность" понятия истины имеет сходные черты. Вторан характерная черта логики состоит в том, что рассуждение, выделенное двумя звездочками в шестом абзаце служит (очень грубой) моделью доказательства нетривиальных теорем о невозможности тех или иных математических конструкций. Такие теоремы о невозможности, сопоставимые о “принципом запрета" в современной физике, составляют вершины современной математической логики. Чтобы убедитьои в этом, достаточно указать, что фундаментальные результаты Геделя и других авторов называются теоремами о неполноте, неразрешимости, независимости и т.п. Такого типа результаты, представляющие очевидный общегуманитарный интерео, не имеют прецедентов в развитии философской мысли до XX века, и являются существенным вкладом естественных паук в фонд гуманитарных. С ним можно сравнить по значению и глубине только анализ квантовомеханических представлений о "дополнительноега" и "неопределенности", распространенный Нильсон Борон далеко за пределы физики никронира. Вознокво, что оба круга идей - логики и квантовой механики - иыеют глубинную связь. Дело в тон, что результаты о невознохности, упонянутые выше, относятоя к детернинированнын ("запрограммированный" как принято говорить сейчас) мыслительным процессан, а квантовая неханика как раз очерчивает границы наивного детернинизиа. Практические применения нетодов математической логики к проектированию и эксплуатации вычислительных и управляющих оистен сейчас хороно известны, и мы позволим себе не останавливаться ва них здесь подробно. 0.2. Для поникания генезиса и отруктуры математической логики необходимо проследить ее многостроннюю овязь о теорией множеств, "наивная” или "содержательная" форма которой была основана в работах Г.Кавтора на рубеже нанего веха. Прежде всего, вой современная математика может быть построена на базе теории множеств. (Наиболее последовательное и целостное изложение этой позиции предпринято в многотомной труде "Основы математики" Н.Бураки). Поэтому логика как "теория натематики" вынуждена соотноситься о теорией множеств. Далее, уже в начале века обнаружилось, что некоторые конструкции, основанные на интуитивном представлении о тон, что множества могут состоить из каких угодно объектов, быстро приводят к противоречию (парадоксы Бурали-Форти, Расселла и др.). Разные попытки устранить эти противоречия породили первые понятия и результаты современной натематичеокой логики. Наконец, теория множеств полужила для логики источником нескольких важнейших идей (диагональный процесс, интерпретация) задач (гипотеза континуума), во многом предопределивших направление ее развития. Доя большей конкретности дальнейшего обсуждения кратко опишем три теоретико-множественных конструкции. (...) 0.5. Теперь читателю полезно будет мысленно вернуться к конструкции вещественных чисел С, в которой, по-видимому, обращение с множествами бьйо гораздо более многоступенчатым и сложным, чем в парадоксе Рассела; вообразить себе все здание Анализа - с интегрированием Лебега, кривыми Пеано и т.п., надстроенным над IP в соответствии с теоретикомножественными принципами; и задаться вопросом: Существуют ли вещественные числа IR Различные школы в математической логике, особенно в ее мета-матических аспектах, удобно характеризовать тем, как они относятся к этому вопросу. Нижеследующее описание нескольких основных направлений очень неполно и, наверняка, содержит искажения: эта тема совершенно не поддается формализации. а) Формализм в стиле Гильберта. Математика есть игра, в ходе которой по определенным правилам пишутся значки на бумаге. Вещественные числа IP фигурируют в массе неформализованных математических текстов вместе со обоими свойствами. Анализируя реальные тексты, следует составить список основных значков и жестких правил составления из них правильных формальных математических текстов. Если, следуя этим правилам, можно составить, скажем, текст 0 = 1, то наша "формальная математика" будет противоречивой, и ничего, с чем мы в ней работаем, "не существует". На самом деле, мы надеемся, что все (или большая часть) классических математических объектов "существует", то есть ( ->сС !), что рассуждая о них по правилам, мы не можем прийти к противоречию. Мы надеемся также, что это утверждение можно доказать, исследуя тексты и правила их составления безотносительно к их "содержанию". Вот грубая модель такой программы. Рассмотрим тексты, которые являются записями шахматных партий в стандартной нотации от начальной позиции до какого-то хода. Ясно, что правила "ходов" можно сформулировать как правила последовательного составления таких текстов безотносительно к реальным деревянным олонам, пешкам и т.д. Ясно также, что по записи можно подсчитать, скажем, количество фигур того или иного цвета на доске в конечной позиции текста. При этом утверждение о том, что "на дооке не может оказаться больше двух кора лей" можно сформулировать и доказать, анализируя только правила составления текстов и не аппелируя к "настоящей" шахматной доске. б) Конотруктивизм. "Все" вещественные числа, безусловно, не существуют. Имеет смысл говорить лишь о тех из них, для которых указан алгоритм вычислении, скажем, их последовательных десятичных знаков (типа программы для ЭВМ). Вообще "существуют" только объекты, которые можно построить, хотя бы в принципе. Для очень многих понятий и результатов классической математики можно указать их конструктивные варианты. Те результаты, которые являются по существу неконструктивными, подлежат полной дискредитации, в том числе практичеоки вся теория множеств и вещественного континуума и т.п. Особенно широко известен кон- структивистский отказ от принципа исключенного третьего. в) Интуиционизм. Концепция, близкая к конструктивизму. Ее сторонники, однако, подчеркивают свою отделенность от формализованной (метаматематики и тяготение к философии и сош" льным наукам. г) Логицизм. Концепция, в которой логическая система предшествует математической; представлена, в частнооти, фундаментальным трудом Уайтхеда и Расселла " PlLticipiCi. Согласно Клини, "логицистический тезис может быть ... подвергнут сомнению по той причине, что логика уже предполагает математические идеи в своей формулировке ... Существенное математическое ядро содержится в идее итерации, которой приходится пользоваться, например, при описании ... вывода из данных пооылок". 0.6. Рабочая точка зрения, которую принимает автор этих записок, состоит в том, что математическая логика есть часть "наивной" математики. Так она и будет излагаться. Метаматематическое истолкование логических теорем приводится лишь в качестве интуитивных объяснений, возможность которых, однако, определяет эмоциональную ценность логики. Оправдание такой точки зрения в значительной мере основано на результатах К.Геделя, лежащих в русле гильбертовского формализма. Эти результаты, как уже говорилось, носят отрицательный характер. Теорема о "неполноте" любой формализованной теории, содержащей определенную часть арифметики,асверждает, что всегда существуют содержательно истинные теоремы этой теории, которые нельзя доказать средствами этой теории. Проблема непротиворечивости достаточно богатой формальной теории также не может быть решена только средствами, формализуемыми в этой теории. Математику нельзя формализовать. Попытки формализовать ее, однако, ооставляют содержательную и интересную часть математики. 0.7. В заключение мы приведем здесь простую, но уже нетривиальную теорему, родственную геделевским "принципам запрета". Чтобы избежать долгих формальных объяснений, мы аппелируем к интуиции читателя с небольшим опытом работы на ЭВМ. Постановка задачи. В Вычислительный центр поступают тексты, написанные на алгоритмическом языке (окажем, типа АЛГОЛа). Транслятор - специальная программа - превращает эти тексты в программы на машинном языке. Некоторые тексты содержат ошибки, скажем, синтаксические; транслятор реагирует на некоторые из ошибок остановом. Естественно поставить задачу написания транслятора, который обнаруживал бы все больше и больше типов ошибок и, может быть, даже и "все" ошибки в любом тексте на алгоритмическом языке. |
