| Вокруг теорем Гёделя о неполноте |
Apr. 9th, 2023|04:36 pm |
Теоремы Гёделя о неполноте исторически очень важны в развитие логики и математики. Но так ли важно владение самими этими теоремами и умения их доказывать для современного математика? Думаю, не очень. Намного важнее разные конструкции, которые эти теоремы мотивируют.
Например, и Манин, и Белл, в cвоих доказательствах ссылаются на теорему Матиясевича-Робинсон-Дэвиса-Путнама (MRDP) из доказательства 10-й проблемы Гильберта. Но это доказательство было получено намного позже жизни Гёделя. Поэтому должны быть другие доказательства, которые, можно так cказать, ближе к корням. Например, узнать о них в доступной форме можно из книжки Смульяна, на которую ссылается Манин, в той части своей книги, которая относится к советскому изданию "Доказуемое и недоказуемое" (это начало). Другая интересная книга это Питер Смит. Он про Гёделя написал целых две книги, одну простую и одну более сложную. Там вроде ссылок на MRDP тоже нет. Но я их не читал, потому что сбор диковинок для меня было более приоритетной целью , поэтому ответственно про их качество высказаться не смогу.
Одним из главных таких мотивируемых конструкций становятся рекурсивные или вычислимые функции, а также рекурсивно-перечислимые множества. Обычно изложения этих тем в курсах логики получается достаточно "занудным", потому что требует освоение такой темы как Модели Вычислений собственно для определения вычислимости. Для этого обычно использует Машины Тьюринга, Мужика Поста или автомат Маркова. В итоге сводится к проблеме их программирования. Белл использует УРиМ (и ТУМиМ). К хвале Манина, он ничего не использует, и это делает его изложение наименее занудным. В остальном и Белл, и Манин тут снова близки друг-другу и ссылаются на классический учебник Роджерса по Теории Рекурсии. Я по этой теме отметил еще для себя современную классику классики Classical Recursion Theory П. Оддифреди в 2-х томах. Вроде еще есть неплохая книга, Барри Куппер, теория вычислений, но это уже не совсем классика. Я бы к ним обратился, если бы было время и желания изучать эту тему более подробно.
Но еще одно отступления. Я писал, что попрощался с Милети. Но я хотел бы еще раз к нему вернуться, чтобы прорекламировать вторую главу этой книги, которою по замыслу автора нужно читать в самом начале, но я читал ее в самом конце. Сложен и извилист мой путь. Там тема что-то типа индукция и рекурсия. Это совсем элементарная тема, которую надо по хорошему относить не к предмету "Теория Рекурсия", а к предмету типа "Теория Натуральных Чисел", который, наверное, слишком элементарный для вузовской программы. Но, во первых, он на самом деле получается не совсем элементарным, потому что Милете обсуждает индукцию и рекурсию, не только на натуральном ряде, но и на произвольных множествах с системам порождающих. И хотя, это действительно совершенно элементарная тема, мало где я видел такое полное ее изложения с таким количеством примеров. И как мы увидим дальше, логика, вычислимость и арифметика в смысле теории натурального ряда очень сильно связаны. И эта теория рекурсии действительно много что проясняет в логике и функциональном программировании. Почти все остальные структуры логики, о которой я писал раньше, рекурсивны. И такая открывающая глава позволяет сделать изложение динамичной с опорой на несколько базовых теорем про индукцию и рекурсию. Кажется, отсюда сразу можно доказывать рекурсивную перечислимость Большинства структур логики.
Теперь собственно о рекурсивных или вычислимых функциях. Это частично определенные функции между декартовыми степенями натуральных чисел. Вычислимость определяется через конструирование алгоритмов в моделях вычислений. Но мы уже решили, что они нам не нравятся. Хочется определять эти функции как-то аксиоматически. Поэтому их можно определить индуктивно как множество с системой порождающих (как во второй главе Милети). В качестве порождающих элементов берется всякая мелочевка типа константы 0, операции следующий элемент и проекции. А в качестве порождающих операторов объединение, композицию, рекурсию и мю-оператор. Мю-оператор, это что-то вроде поиска в глубину. Если его не брать, то получится множество примитивных рекурсивных функций. Они примечательны тем, что никогда бесконечно не зацикливаются. Причем любую вычислимую функцию, можно реализовать так, что мю-оператор будет использован всего один раз. То есть будет как-бы один цикл, который вызывает примитивные рекурсивные функции. Вообще, результат, что эти рекурсивные функции и есть все вычислимые функции называется Тезисом Черча. Но я бы предпочел использовать его в качестве определения. И тут встает вопрос, что если мы можем так ловко определить такое множество функций на натуральных числах, то можно использовать те же методы на произвольных множествах. Это ведет к теории E-рекурсивных функций. Я вижу тут параллель между порождающими операциями и дедукциями в логики и выводе типа в программировании.
Множество называется рекурсивно перечислимым, если оно является областью определения какой-то рекурсивной функции. Это определения можно трактовать так: если у нас есть волшебный компьютер с неограниченной памятью, который может запускать неограниченное число процессов, то мы можем вывести все элементы этого множества за бесконечное время. Например так, обходим натуральный ряд, и на каждом числе вычисляем функцию, областью определения которой это множество является. Если функция вычислялась как-то, то выводим это число, но вначале запускаем похожий процесс для следующего числа, чтобы не застрять. Поэтому такие множества еще называют полувычислимыми. Если само множество и его дополнение является полувычислимым, то такое множество называется вычислимым или разрешимым. Про эти множества и функции есть много результатов, я все повторять тут не буду. Скажу, только, что тут все совсем круто, потому что частично рекурсивные множества с рекурсивными функциями на них образуют пучки. Поэтому если прорваться сквозь модели вычислений, то дальше будет интересное взаимодействие с теорией топосов, о которой я надеюсь в будущем написать поподробней. Пока скажу, что Манин касается этой темы и даже определяет когомологии Чех для рекурсивно перечислимых разбиений рекурсивно перечислимых множеств.
Вообще, мы как-бы снова вернулись к общей топологии, н теперь как бы по секретному подземному ходу, проложенному под оживленной улицей. Через элементарную теорию пучков нащупываются соответствия между полувычислимыми и открытыми множествами в топологии. Даже аксиома про бесконечные объединения тут выполняется, если брать объединения не абы каких классов а сечения полувычеслимых множеств большей размерности. Тогда разрешимые множества это открытозамкнутые. Рекурсивные функции это функции непрерывные в области. А примитивные рекурсивные функции, это как непрерывные открытые тогда? У меня вопрос, короче. Про это соответствие я уже писал в посте про общую топологию. Но теперь оно для меня стало более осязаемо.
Теорема MRDP утверждает, что любое рекурсивно перечислимое множество можно представить как множество натуральных решений некоторого Диофантового уравнения с параметрами. Этот путь к теореме Геделя для меня казался очень привлекательным, потому что я вспомнил как в дестве любил элементарную теорию чисел. Манин тут как опытный числовик, делает тут довольно лихие броски. Поэтому мне больше понравилось изложение в книжке Белла. Я получил много фана, доказывая теоремы про делимость чисел Фибоначчи и факты про уравнение Пелля. Но тут я действительно закопался. Поэтому на подготовку этого поста про логику ушло так много времени. Действительно там есть очень сложные технические результаты и такие же теоремы про сводимость. Поэтому я не думаю, что это действительно педогогично выводить теорему Гёделя из MDRP. Потому что ни у какой аудитории не хватит сил на ее полное доказательство. Это too much теории чисел в курсе логики! По этой теме могу рекомендовать книгу самого Матиясевич Десятая проблема Гильберта. Кроме результатов типа Теоремы Гёделя там есть и другие, типа неразрешимости проблем анализа и задач про многомерные шахматы. Я бы вернулся к этой теме, после того, как бы систематизировал свои знания по элементарной теории числел, но скорее всего это будет не скоро. Десятая проблема Гильберта в листочках. Курс лекций Матиясевича На youtube
И вот вот мы подошли собственно к Теоремам Геделя о неполноте. И тут силы мои кончились. Ну для начала нужно научиться различать разные модели арифметики. А совсем в начале нужно выбрать некий язык арифметики первого порядка и научиться сопоставлять его формулам и термам натуральные числа. Тогда множество натуральных чисел называется арифметическим, если оно определяется каким-то высказыванием на этом языке. Удивительно, но оказывается, что множество арифметических множеств является алгеброй (простое доказательство с MRPD; сложное без?), порождённой рекурсивно перечислимыми множествами. И даже "сигма-алгеброй" в том же смысле в каком рекурсивно перечислимые множества являются "Открытыми в топологии". Поэтому мы уже сейчас можем предсказать глубокую сходства между арифметическими и Борелевскими множествами.
Так вот, бывает модель арифметики просто как теория порожденная всеми натуральными числами. Это модель полна, то есть там лежит как в множестве либо каждое конкретное утверждение, либо его синтактическое отрицание. Но это модель не аксиоматическая, а как бы семантическая. Аксиоматическая модель это та, которую можно вывести из набора высказывания, номера которых рекурсивно перечислимы. Используя MRDP можно показать, что чтобы выразить любое рекурсивно перечислимое множество достаточно очень простой аксиоматической модели арифметики. Отсюда сначала выводится "теорема неразрешимости" про то, что любая теория, которая не противоречит арифметики Пеано первого порядка будет рекурсивно неразрешима. А отсюда уже выводится собственно первая теорема Геделя о неполноте: в любой непротиворечивой аксиоматической теории, которая содержит "элементарную арифметику", можно конструктивно построить утверждение (на языке арифметики первого порядка), такое что не оно само, ни его отрицание там не лежит. Вторая теорема более хитрая: В любой непротиворечивой аксиоматической теории, содержащий арифметику Пеано первого порядка, не содержится утверждения, что она сама непротиворечива. Считается, что это вторая теорема привела к глубоким последствиям для философии математики. Но тут конечно встает вопрос, как такое утверждение кодируется на языке арифметики. Про философские аспекты этих теорем я хотел бы почитать в книге Use and Abuse.
В общем, в этом посте мы наблюдали святую троицу из логики, вычислений и теории чисел. С одной стороны у нас есть MRPD, которая сопоставляет перечислимым множествам диофантовы уравнения, с другой стороны у нас есть арифметизация Гёделя, которая превращает логические формулы в числа. А взаимодействия между логикой и вычислениями само-по-себе фундаментально, потому что по своей структуре синтактическая логика рекурсивна. В следующем посте из этой серии я надеюсь продолжить разбирать эти тройственные взаимодействия. |
|