| От Логики Первого Порядка к Теории Моделей |
Feb. 25th, 2023|11:56 am |
Как и с логикой высказываний. Важнейшим результатом в логике первого порядка являются теоремы о полноте и компактности. Теорема полноты говорит, что любое утверждение истинное для любой модели неких аксиом, можно из этих аксиом доказать. А теорема компактности говорит, что утверждение всегда истинное для любой модели бесконечного множества аксиом, может быть истинно и для любой модели конечного подмножества этих аксиом. Обычно курс логики устроен так: разбирается некий вид логического вывода, потом для этого вида доказывается теорема о полноте, а потом из нее сразу следует теорема о компактности. Но сейчас популярность получило мнение, что теорема о компактности важнее. Потому что это чисто семантическое утверждение полностью независимое от методов логического вывода. И для всех интересных результатов нужна именно теорема о компактности.
Например, один из самых красивых результатов, который следует из теоремы о компактности, это теорема Акса-Гротендика. Это теорема утверждает, что любое инъективное полиномиальное отображение из С^n в С^n будет биекцией. А все дело в том, что из компактности можно вывести, что если какое-то утверждение на языке логике первого порядка и теории колец верно для бесконечного числа алгебраически замкнутых полей конечной характеристики, то они верны и для комплексных чисел. И можно показать, что такие полиномиальные функции действительно биекции в алгебраически замкнутых полях конечной характеристики. Потому что каждый полином имеет конечное число коэффициентов и любая точка, которую мы хотим получить это тоже n элементов поля, то мы можем с их помощью сгенерировать подполье, которое само будет конечным. А инъективное отображение из конечного множества в само себя всегда будет биекцией. Это очень красивый результат. И я очень рад, что решил заняться логикой, только потому что с ним познакомился.
Другой интересный результат это 0-1 закон для случайных графов. Контекст этого закона таков, что в случайном графе из n вершин ребра независимо добавляются или убираются с вероятностью 1/2. Cам закон говори, что если взять любое утверждения на языке теории графов первого порядка, и устремить n к бесконечности, то придел будет либо 0, либо 1. Рассмотрим утверждения типа для любых n вершин и любых других m вершин в графе найдется еще одна вершина x, которая смежно с первыми n вершинами, и не смежно с никакими из остальных m. Эти утверждения называются Аксиомами ресторана Алисы, потому что в ресторане у Алисы можно заказать все что угодно. С помощью элементарной комбинаторики и теории предела, можно доказать, что 0-1 закон выполняется для ресторана Алисы. Добавим аксиомы ресторана Алисы к аксиомам теории графов и получим теорию детерминированных "cлучайных" графов. Очевидно, что у этой теории не будет конечных моделей. Более того, можно доказать, что все теории детерминированных случайных графов счетные модели изоморфны. Поэтому тест Воща-Вогта говорит, что это теория полна. Благодаря компактности мы видим, что любое утверждение в теории детерминированных случайных графов можно получить из конечного числа аксиом. Поэтому можно ограничиться конечным числом аксиом ресторана Алисы и таким образом ограничить рост сумм при вычислении предела вероятностей. Вспомним про полноту, получим 0-1 закон.
Теперь нужно ответить на вопрос, как эту замечательную компактность доказывать? Есть много способов, например можно использовать полноту, понятия непротиворечивости, ультрапроизведения или алгебры Линденбаума. Мне больше всего нравятся алгебры Линденбаума, поэтому расскажу именно о них. Как я уже писал Алгебра Линденбаума для некой теории это булева алгебра, элементами которой будут классы эквивалентных формул в этой теории. При этом все большие теории будут задавать фильтры, а полные теории ультрафильтры. Можно доказать, что существует однозначное соответствие между классами изоморфных моделей этой теории и ультрафильтрами, сохраняющему кванторы. А кванторы в этой Булевой алгебре могут быть получены как инфинумы и супремумы классов соответствующих формул. Лемма Расиовы-Сикорского говорит, что для любой счетной последовательности множеств имеющих супремумы, можно расширить, сохраняющей эти супремумы. А это тоже самое, что сохранение кванторов в контексте Алгебр Линденбаума. Теперь рассмотри какой-то язык первого порядка со счетной сигнатурой, и четную теорию такую, что все его конечные подмножества имеют модель. Тогда можно определить новую Булеву алгебру где классы эквивалентности задаются отношением, можно доказать эквивалентность, используя конечное число аксиом. У нас счетное число экзистенциональных утверждений. Поэтому мы можем применить Лемму Расиовы-Сикорского и получить ультрафильтр. А из ульрафильтра можно построить модель уже для самой изначальной теории.
Тут вот, что лично мне интересно отметить. В случае логики высказываний можно было просто взять пространство Стоуна алгебры Линденбаума. При этом, для полноты замечу, что ультрафильры соответствуют элементам пространства Стоуна (положительное значение на элементе = принадлежность). Но тут все эти нюансы сидят в теореме Расиовы-Сикорского. Изначально ее доказали применяя теоремы Бэра в этом пространстве Стоуна. Поэтому у всех этих красивых результатов сверху, можно сказать, топологические корни. Вообще Белл пишет, что само понятие компактность, как пишет Белл, связана с тем, что элементарные классы, то есть классы задаваемые единичными высказываниями, задают компактную топологию на классе всех моделей. Грубо говоря, какой-то набор высказываний, противоречив если из него можно доказать все что угодно, а это тоже самое, что быть покрытием всего пространства моделей. Тогда, то что можно выбрать конечное подпокрытие говорит о том, что взять конечное противоречивое подмножество. А то можно перевести как, если каждое конечное подмножество утверждений в множестве утверждений непротиворечиво, то и все множество непротиворечиво, то есть утверждение теоремы о компактности. Причем, это элементарная топологи будет похожа на топологию пространства Стоуна, будет полностью несвязной. Но нормальным множеством с кардинальностью это пространство не будет. Вообще в теории моделей иногда вполне естественно возникают очень большие объекты. Такие объекты называются моделями-монстрами. Поэтому теории моделей тесно в нормальных основаниях математики и теории категорий.
Вообще, когда я брался за эту тему, у меня было две цели. Во первых посмотреть на применения булевых алгебр в логике. Второй целью было познакомиться с теорией моделей. Для меня это был самый загадочный раздел матлогики. Теперь мне кажется, что его правильнее было назвать семантической комбинаторикой, и тогда было бы понятно. Очень сильно углубляться в теорию моделей для себя я сейчас не вижу, потому что это сложная и запутанная дисциплину. Тем же, кто хочет с ней ознакомиться, я рекомендкую книгу Болдуина Model Theory and the Philosophy of Mathematical Practice, а не стандартные учебники. Потому что, там есть определенная систематизация основных результатов и их смысла. Еще, чтобы познакомиться с современной теорией моделей можно посмотреть презентацию того же автора
Основным понятием теории моделей является категоричность. Он не имеет отношения к теории категорий. к-категоричность означает, что у теории есть только один класс изоморфных моделей кардинальности к. Если у к-категоричной теории нет конечных моделей, и к не меньше сигнатуры языка, то она будет полна. Основной результат классической теории моделей это теорема Морли. Она говорит, что если теория к-категорична для какого-то несчетного кардинала, то она к-катигорична для любого.
Другой интересный результат, который тоже можно отнести к классической теории моделей это теоремы Лёвенхейма-Сколема. Одна из них утверждает, что у любого набора формул, у которого может быть бесконечная модель, есть модель кардинальность, которой не превышает кардинальность сигнатуры языка. Так как сигнатура теории множеств счетная отсюда следует, что существует счетная модель теории множеств. И все классические теоремы вроде Кантора-Бернштейна там выполняются (При этом все множества счетные). Изначально этот результат вызвал большой переполох, и стал известен как парадокс Сколема. Но на самом деле никакого парадокса тут нет, так как само понятие функции и кардинальности в счетной модели тоже меняется. Про этот эффект говорят, что логика первого порядка не может нормально выразить понятие кардинальности.
Так мы плавно переходим к ограничением логике первого порядка. Как мы уже на языке логике первого порядка хорошо описываются простые алгебраические и комбинаторные структуры, где все операции и предикаты применяются к однотипным элементам. Сюда относятся группы, поля и графы, например. А вот применять логику первого порядка к алгебрам Хопфа, метрическим пространствам и пространством с мерой довольно затруднительно. Вообще в элементарных курсах логики часто говорят, что логики старшего порядка не нужны, потому что все логики можно сводить к логике первого порядка добавляя дополнительные элементы и предикаты. Но с теорией моделей этот поход плохо стыкуется, потому что при таком сведении херится кардинальность. А в теории моделей, как я уже писал, кардинальность это все. Также можно упоминать нестандартный анализ и арифметику. Потому что если просто взять теорию действительных чисел или соответственно целых чисел, мы всегда будем получать нестандартные модели с бесконечно малыми и бесконечно большими. Поэтому говорят, что логика первого порядка не может адекватно закодировать нормальную школьную математику. Вообще мне теперь кажется, что нестандартный анализ намного больше интересен логикам, чем аналитикам.
Тут я показал, что логика первого порядка вполне способна решать задачи для core mathematics. Например, Акс-Гротендик и 0-1 закон для случайных графов. При этом в глубене тут лежи теорема о компактности, которая имеет псевдо-топологическую природу и компактность. И получается, что логика внезапно играет роль способа контрабандно протаскивать топологию в лог Думаю на этом мы прощаемся с логикой первого порядка и почти прощаемся с Милети. Дальше будет вычислимость, теория рекурсии и теорема Геделя о неполноте. |
|