Содержание к диссертации
Введение
1. Основные понятия 12
1.1. Разрешимые структуры 12
1.2. Некоторые сведения из теории конечных автоматов 15
1.3. Автоматные структуры 19
2. Линейные порядки 25
2.1. Предварительные сведения о линейных порядках 25
2.2. Автоматные линейные порядки 29
2.3. Разрешимые и автоматные линейные порядки 33
2.4. Некоторые примеры автоматных линейных порядков 40
3. Автоустойчивость 46
3.1. Для автоматных отношений эквивалентности 47
3.2. Для линейных порядков 50
4. Сложность автоматных частичных порядков 59
4.1. Сведение модели в конечной предикатной сигнатуре к частичному порядку 60
4.2. Сохранение автоматности 64
Литература 68
- Некоторые сведения из теории конечных автоматов
- Разрешимые и автоматные линейные порядки
- Для линейных порядков
- Сохранение автоматности
Введение к работе
Объектами изучения математики являются модели (структуры) — множества с заданными на них отношениями и операциями. В середине прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, М. О. Рабина, Р. Воота и других появилось понятие вычислимой или конструктивной модели, то есть модели, которая может быть описана алгоритмически. С этого момента в математической логике образовалась новая подобласть — конструктивные модели, активное развитие которой продолжается до сих пор. Класс вычислимых моделей является наиболее общим и довольно сложным, в связи с этим возникло стремление выделить простейший с алгоритмической точки зрения подкласс вычислимых моделей. Одним из предложенных на эту роль классов является класс автоматных структур. Достоинства этого класса заключаются в том, что наиболее естественные проблемы и свойства автоматных моделей являются разрешимыми.
Упоминания такого рода моделей впервые появились в работах Дж.Р.Бюхи и М. О.Рабина [15], [16], [37], [38], которые изучали теорию конечных автоматов и рассматривали представления некоторых структур с помощью автоматов. С появлением в 1995 году статьи А. Нероуда и
Б.Хусаинова [25], в которой было предложено систематическое исследование автоматных структур, последние подверглись интенсивному изучению. К настоящему времени теория автоматных структур представляет одно из основных направлений исследований в области конструктивных моделей.
Под автоматной структурой подразумевается модель в конечной предикатной сигнатуре, основное множество и все отношения которой распознаются конечными автоматами (автоматы, распознающие п-местные отношения, работают синхронно на п-ках слов). Различные типы конечных автоматов, таких как автоматы на конечных словах, автоматы Бюхи, автоматы на деревьях, порождают различные типы автоматных структур. Автоматные структуры всех перечисленных типов обладают рядом разрешимых свойств. Элементарная теория автоматных структур, например, является разрешимой [22, 25, 12].
Класс словесно-автоматных структур, то есть структур в конечной предикатной сигнатуре, распознаваемых автоматами на конечных словах, наиболее простой среди упомянутых, в него попадают лишь счётные модели. Словесно-автоматными структурами, например, являются: (N,+), (Q, <), булева алгебра Вш конечных и коконечных подмножеств натуральных чисел, в то время как такие структуры, как (N, х) [12], (Q,+) [44], безатомная булева алгебра [28], не являются словесно-автоматными.
Класс Бюхи-автоматных структур, где автоматы работают на бесконечных словах, охватывает как счётные так и несчётные структуры, хотя на счётных структурах эти два класса совпадают [10, 11]. В класс древесно-автоматных структур также попадают только счётные модели, однако, он обширнее класса автоматных структур, (N, х) и безатомная булева алгебра, например, являются древесно-автоматными. Интересен также класс Рабин-автоматных структур, распознаваемых конечными автоматами, работающими на бесконечных полных бинарных деревьях. В этой работе мы будем касаться только словесно-автоматных структур, так как они всё ещё остаются слабо изученными, поэтому мы будем использовать везде термин автоматная структура, подразумевая под ним словесно-автоматную структуру.
Основные результаты этой работы касаются наиболее естественных классов структур, таких как линейные порядки, частичные порядки и отношения эквивалентности. В области характеризации типов изоморфизма автоматных моделей из перечисленных классов получены следующие результаты: автоматными ординалами являются в точности те ординалы, которые строго меньше чем шы [17]; С. Рубин, Ф.Стефан и Б.Хусаинов доказали, что -FC-ранг автоматных линейных порядков и деревьев конечен [29]; в [23, 24, 33] исследованы автоматные вполне упорядочиваемые частичные порядки и показано, что они являются автоматными тогда и только тогда, когда их ранг строго меньше иґ. В [31] исследованы некоторые теоретико-модельные свойства автоматных представлений плотного линейного порядка, а именно, доказано существование автоматно-однородного представления для (Q, <), то есть любые два одинаково упорядоченных кортежа в этом представлении могут быть переведены один в другой с помощью автоматного изоморфизма, и также было показано, что любой автоматный линейный порядок автоматно вкладывается в подходящее автоматное представление плотного порядка. Мы показали, что любой автоматный линейный порядок формульно определим в подходящем автоматном линейном порядке ранга 1.
Известно, что вычислимые модели определимы формулами в языке логики первого порядка в (N, +, х). Аналогичное утверждение верно для автоматных структур, то есть любая автоматная структура определима в JVfc = (N, +, |fc), где 1 — двухместное отношение и х\ъу, если у является степенью кя х делится на у (см. [12, 41]). Пусть к > 1 и Е& = {0,1,..., к— 1}, рассмотрим структуру Wk = (S^, (cra)^6Sfc, ^2,eZ2), где aa(w) = wa, x < у, если x есть префикс у, и el{u,v), если \и\ = |г>|. Для всех fc > 1, Wk является автоматной и полной, в том смысле, что любая автоматная структура определима в ней (см. [12, 41]).
Как уже было сказано выше, естественные теоретико-модельные свойства для автоматных структур являются разрешимыми. А именно, модели, обладающие автоматным представлением, являются разрешимыми и, более того, разрешимыми в некоторых кванторных расширениях. Рассмотрим квантор Э, трактуемый как «существует бесконечно много», и для к,т Є N, О < к < т, т > 1, кванторы 3^k'm\ обозначающие «существует к по модулю т много», тогда теория первого порядка в языке, расширенном квантором 3 и кванторами 3^k'm\ автоматных структур является разрешимой [12, 30, 41]. Мы показали, что класс автоматных линейных порядков не совпадает с классом разрешимых в расширенном квантором 3 языке линейных порядков.
Так как модель может обладать различными вычислимыми представлениями, то естественным образом возникает вопрос об эквивалентно- сти этих представлений с алгоритмической точки зрения. Исследование этого вопроса было начато А. И. Мальцевым, который заметил, что конечно порождённые алгебраические системы обладают единственным с точностью до вычислимого изоморфизма представлением, то есть все разрешимые свойства в одном представлении остаются разрешимыми в другом. Но уже в [5] было показано, что для бесконечномерного векторного пространства над полем рациональных чисел можно построить два различных вычислимых представления, таких, что в одном проблема линейной зависимости векторов разрешима, а в другом нет. Таким образом, различные вычислимые представления одной модели могут обладать различными алгоритмическими свойствами. Модели, любые два вычислимых представления которых вычислимо изоморфны, были названы автоустойчивыми (вычислимо категоричными), а вычислимые представления, между которыми существует вычислимый изоморфизм, автоэквивалентными. Исследование автоустойчивости моделей и более общего понятия алгоритмической размерности моделей продолжили такие математики, как С. С. Гончаров, А. Т. Нуртазин, Дж. Б. Реммел, Б. Хусаинов, Р. Шор и другие.
В диссертации поднимается вопрос об автоустойчивости моделей в классе автоматных представлений. Естественней было бы называть автоэквивалентными автоматные представления, между которыми существует автоматный изоморфизм, но в таком случае каждая бесконечная модель имеет счётное число не автоматно изоморфных автоматных представлений [25]. Таким образом, здесь мы будем называть модель автоустойчивой в классе автоматных представлений, если любые два её автоматных представления вычислимо изоморфны. Нас интересует в каких моделях разрешимые свойства сохраняются при переходе от одного автоматного представления к другому.
В этой работе мы исследовали автоустойчивость для некоторых, упомянутых выше, подклассов автоматных структур. Автоустойчивость доказана для автоматных отношений эквивалентности, автоматных полных порядков и автоматных разреженных линейных порядков FC-ранга, не превосходящего 2.
Так как автоматные модели являются разрешимыми, то представляется интересным исследовать связь автоустойчивости в классе разрешимых представлений с автоустойчивостью в классе автоматных представлений. Пусть А — класс автоматных линейных порядков, АА — класс автоустойчивых в классе автоматных представлений линейных порядков, AT) — класс автоустойчивых в классе разрешимых представлений линейных порядков. Очевидно, что АТ>Г\А С AT). Ввиду разрешимости автоматных структур AT) ПА С АА, несложно показать, что AT) П А не пусто, как минимум там содержатся все конечные линейные порядки. Мы показали, что существует линейный порядок С\ Є АА, такой, что 1 . AT), и линейный порядок С2 Є AT), такой, что Hi . А. Тем самым показано, что включения AT) П А С AT) и АТ> О А с АА строгие.
Другое определение эквивалентных автоматных представлений было рассмотрено в диссертации В. Барани [10], представления являются эквивалентными, если при переходе от одного представления к другому сохраняются автоматные (регулярные) свойства. Там же показано, что если модель обладает единственным с точностью до описанной эк- вивалентности представлением, то она является полной. Примером, автоматной структуры обладающей «единственным» автоматным представлением служит полная модель Wk- Кроме того, в [10, 41] исследуется, связанное с понятием автоустойчивости, понятие внутренней регулярности отношения, то есть осуществляется поиск условия, гарантирующего регулярность отношения во всех автоматных представлениях.
Исследование автоустойчивости в классе автоматных представлений тесно связано с описанием типов изоморфизма для автоматных структур. Для некоторых классов структур описание было найдено. Как уже говорилось выше, ординалы, обладающие автоматными представлениями, описаны полностью. Бесконечные автоматные булевы алгебры, как показано в [28], — это в точности конечные декартовы произведения булевой алгебры Вш. Конечно порождённые группы описаны в [36] и являются автоматными тогда и только тогда, когда содержат абелеву подгруппу конечного индекса .
Однако в общем случае возможность хорошего описания типов изоморфизма автоматных структур не представляется. Мерой сложности типа изоморфизма модели является ее ранг Скотта. М. Минее и Б.Хусаиновым [23, 24, 33] было показано, что для любого ординала а < u>fK + 1 существует автоматная структура с рангом Скотта равным а, что в месте с тем фактом, что ранг Скотта вычислимой модели не превосходит сої к + 1 (см. [9]) говорит о том, что типы изоморфизма автоматных структур максимально сложны. Таким образом, задача сводится к описанию типов изоморфизма для различных подклассов автоматных структур. Здесь мы покажем, что автоматные частичные порядки также могут обладать сколь угодно большим рангом Скотта.
Проблема изоморфизма для класса всех автоматаных структру является Е^-полной [28, 41]. Однако для некоторых подклассов автоматных структур, например, ординалов и булевых алгебр является разрешимой (см. [41]). Недавним, еще не опубликованным, результатом Д. Куске, М. Лори и Дж. Лю является П?-полнота проблемы изоморфизма для автоматных отношений эквивалентности и оценка сложности проблемы изоморфизма для автоматных линейных порядков как неарифметической. В этой работе приведены некоторые примеры автоматных линейный порядков, наталкивающие на мысль о том, что автоустойчивость для линейных порядков высоких рангов не может быть получена.
В работе А. Нероуда и Б.Хусаинова [27] приведены открытые вопросы и направления для дальнейших исследований в теории автоматных структур. Для случая словесно-автоматных структур сделан обзор в статье С. Рубина [42].
Некоторые сведения из теории конечных автоматов
Пусть Е — конечный набор символов, называемый алфавитом, конечная последовательность символов алфавита называется словом алфавита, пустая последовательность есть пустое слово — е, множество всех слов алфавита Е обозначим через Е (Е+ — множество непустых слов алфавита Е). Языком алфавита Е будем называть любое L С Е . Обозначим через \w\ длину слова w, fc-ую букву слова w обозначим через (w)k- Будем называть конкатенацией слов и и v (обозначим через uv) слово, полученное приписыванием к правому концу слова гі слова v. Положим и = еи для всех к 0 положим wk равным wh 1w. Будем говорить, что слово и является префиксом слова v и обозначать и v, если существует слово w, такое, что uw — v. Если слово w не пустое, то будем говорить, что и собственный префикс v (и - v). Пусть Е — некоторый алфавит. Регулярными выражениями алфавита Е будем называть слова алфавита Е U {(,)), ,е}, полученные в результате следующего рекурсивного определения: 1) Слова е и а, где а Є Е, являются регулярными выражениями. 2) Если а и /? —- регулярные выражения, то (а/?), {ct(3) и (а) являются регулярными выражениями. При записи регулярных выражений мы будем опускать лишние скобки и символ е, руководствуясь теми же правилами, что и при записи арифметических выражений. А именно, с будем поступать, как со сложением, с конкатенацией как с умножением, — возведением в степень, с символ е, как с 1. Эти действия довольно естественны ввиду приведенного ниже соответствия регулярных выражений языкам. Каждому регулярному выражению а сопоставим язык La: 1) Сопоставим регулярным выражениям е и а (при а Є Е) языки Le = {е} и La — {а} соответственно; 2) Регулярному выражению a = ot\\a.2 — язык La = Lai U La2, выражению a = a\a2 — язык La — LaiLa2 = {uv и Є Lai,v Є La2} и выражению а = /3 — язык La = L p — {w\... Wk А; Є N, wx Є I//3, для г n}. Заметим, что для любого языка L язык L содержит пустое слово. Язык L называется регулярным, если L = 0 или существует регулярное выражение а, такое, что L = La. Определение 1.2.1. Недетерминированным конечным автоматом над алфавитом Е называется четвёрка (Q,i,A,F), где Q — конечное множество состояний, і Є Q — выделенное начальное состояние, А С (Q х Е) х Q — отношение перехода и F С Q — множество заключительных состояний. Слово w Є Е распознаётся недетерминированным автоматом Л = (Q, г, A,F), если в этом автомате существует последовательность переходов вида (i,(w)i,gi) Є Д,( 7і,0)і, 72) Є A,...,(gn_i,(tw)n,gn) Є А и qn Є F, где \w\ = п. Множество слов, распознаваемых автоматом Л, будем называть языком автомата и обозначать L(A). Недетерминированный конечный автомат Л = (Q, i, A, F), в котором отношение перехода А является функцией, заданной на всем множестве Q х Е, называется детерминированным конечным автоматом.
Напомним, что класс языков, распознаваемых детерминированными конечными автоматами, совпадает с классом языков, распознаваемых недетерминированными конечными автоматами. В связи с этим мы часто будем говорить конечный автомат, опуская слово недетерминированный или детерминированный. Также напомним, что язык является регулярным тогда и только тогда, когда он распознаётся конечным автоматом. Пусть L — некоторый язык алфавита . Определим отношение эквивалентности ь относительно языка L на Е следующим образом: W\ L W2, если для любого слова v Є S выполнено: W\V Є L 4Ф- u Обозначим через O(L) число классов эквивалентности, на которое , делит Е . Теорема 1.2.2 (Майхил-Неруод). Язык L распознаётся конечным автоматом тогда и только тогда, когда O(L) ш. И если O(L) ш, то минимальное количество состояний в детерминированном конечном автомате, распознающем L, равно O(L). Заметим, что два слова эквивалентны относительно некоторого регулярного языка, если детерминированный автомат с минимальным количеством состояний, распознающий этот язык, считывая любое из этих слов, попадает в одно и то же состояние. Эта теорема вместе с леммой о накачке, приведённой ниже, обеспечивают нас техникой доказательства нерегулярности языков. Теорема 1.2.3. Пусть L — язык, распознаваемый конечным автоматом, тогда существует константа п (равная O(L)), такая, что для любого слова w Є L длины большей либо равной п существует разбиение w = uzv, такое, что \uz\ п, z ф е и для всех г Є N выполнено uz%v Є Подробные сведения из теории конечных автоматнов можно найти в [8, 26]. Как уже было сказано ранее, автоматная структура — это структура, основное множество и все отношения которой распознаются конечными автоматами. Для формального определения необходимо уточнить, что подразумевается под словами «отношение распознаётся автоматом». Пусть _1_ Е, обозначим через Ед_ алфавит Е U {J_}. Определение 1.3.1. Назовём конволюцией кортежа (wi,...,wn) Є ( )" кортеж (wi,...,wn)± = (w[,..., w n) Є (S _)n, такой, что \w[\ = ...= \w n\ = maxj n iOj = m и для і n, k m ( ) = {щ)к если к \wi\, и {w i)k =-L иначе. Иными словами, к правым концам слов из кортежа (w\, ...,wn) мы добавляем наименьшее количество символов _L таким образом, чтобы длины всех слов в этом кортеже стали одинаковыми. Определение 1.3.2. Конволюция отношения R С (Е )п — это отношение R± = {гїї_і_ I w Є R} С (E )n, полученное как множество конво-люций всех кортежей отношения R. Определение 1.3.3. Структура (Л, Яі, ...,) называется автоматной над алфавитом Е, если её носитель А С Е и конволюции всех отношений R{ С (Е _)Пі для г к распознаются некоторыми конечными автоматами над алфавитами Е и (Ej_)ni для і к соответственно.
Будем говорить, что структура Л имеет автоматное представление Л , если Л автоматная структура над некоторым алфавитом и Л = Л . Иногда будем говорить, что отношение распознаётся автоматом или является автоматным, подразумевая, что конволюция этого отношения распознаётся конечным автоматом. Также будем иногда называть структуру автоматной, если она имеет автоматное представление над некоторым алфавитом. Приведём простой пример автоматной структуры. Рассмотрим унарный алфавит Е = {1} и зададим функцию следования, представленную её графиком, следующим образом: Q) (-f). Таким образом, мы показали, что натуральные числа с функцией следования (N, s1) обладают автоматным представлением. Рассмотрим бинарный алфавит {0,1}, тогда отношение записывается с помощью регулярного выражения ((о)(і)) ((о)І(і)) и следовательно, распознаётся конечным автоматом. И так как — частичный порядок, задающий на {0,1} структуру полного бинарного дерева, получаем еще один пример автоматной структуры. За счёт замкнутости класса регулярных языков относительно булевых операций и разрешимости проблемы пустоты языка, распознаваемого конечным автоматом, верна приведённая ниже теорема, послужившая мотивом к изучению автоматных структур. Теорема 1.3.4 (Ходгсон, Нероуд-Хусаинов, см. [22, 25, 41]). Существует алгоритм, строящий равномерно по отношению R, определимому в автоматной структуре Л формулой логики первого порядка (с параметрами), автомат, распознающий R±. И, следовательно, теория любой автоматной структуры разрешима. Из этой теоремы, более того, следует, что автоматные структуры яв- ляются разрешимыми. Расширим язык логики первого порядка, добавив новый квантор 3, трактуемый как «существует бесконечно много». Формулы логики первого порядка в расширенном языке мы будем называть FO + 3-формулами и соответствующие теории FO + 3-теориями.
Разрешимые и автоматные линейные порядки
Линейный порядок = 1 + С + 2 + С + ... + С + Рп + + ..., где рп — простое число с номером п, обладает разрешимым в расширенном языке представлением, но не является автоматным. Докажем, что этот порядок не является автоматным. Предположим, напротив, что данный линейный порядок является автоматным. Так как одноместное отношение С(ж) истинное на элементах, принадлежащих интервалам типа С, двухместное отношение с(х,у), истинное на элементах между которыми лишь конечное число элементов и двухместное отношение х у, истинное на элементах, принадлежащих соседним конечным интервалам, являются формульно определимыми в расширенном языке: то из теоремы 1.3.5 следует, что эти отношения распознаются конечными автоматами. Пусть отношение х« у распознается конечным автоматом над алфавитом Е и Е) = с. Так как ] является локально конечным, то по лемме 1.3.11 существует константа а, такая, что если ж К)у, то }у\ \х) +а. Пусть 6— 1 — длина слова, соответствующего первому элементу из первого конечного интервала. Тогда длина слов в n-том конечном интервале не должна превосходить 6 — 1+an. Слов длины, не превосходящей 6—1+an, не более чем (i -l+an+1_ Получили, что рп сап+6, что неверно. Покажем, что линейный порядок С обладает разрешимым представлением. Для этого докажем следующие 3 леммы: Лемма 2.3.2. Теория Т = Th() является разрешимой. Доказательство. Т = Th() — полная вычислимо перечислимо аксиоматизируемая теория и, следовательно, разрешимая. Докажем аксиоматизируемость, для этого введём отношения: dis(x, у) (х у)& (3z)(x z у)& - (3z)(x 3 z) & (3z)(z y)k & (\fz)((x z y) — (3zj, 22)(2:1 z 3 22)) — интервал (x,y) не пустой и является дискретным без концов. z2)) — интервал [ж,?/] является дискретным с левым и правым концом. maxdisend(x,y) ±=? disend(x,y) &c(Vz)((z ж) — — disend{z,y)) & &(Vz)((y z) — - disend(x,z)) — интервал [ж, у] является максимальным дискретным интервалом с левым и правым концом.
Итак, выпишем список аксиом Лж: - 1) Ті, — аксиомы линейного порядка. 2) Счетное число аксиом: 3) Аксиома (Уж)((3у)(у ж) — (Зг)((ж 3г) V (гож))), утверждающая отсутствие плотных подинтервалов. 4) Аксиома (Vx,y)(disend(x,y) —» (Зжі,уі)((ж1 ж у Уі) & &.(dis(xi,yi) V maxdisend(xi,yi))), утверждающая, что каждый дискретный интервал с левым и правым концом может быть расширен или до максимального дискретного интервала с левым и правым концом, или до дискретного интервала без концов. 5) Аксиома (Vx,y)(dis(x,y) — (3z)maxdisend(y,z)), утверждающая, что за каждым дискретным интервалом без концов непосредственно следует максимальный дискретный интервал с левым и правым концом. 6) Аксиома (\/x,y)((dis(x, у) & —"COC J У)) (3z)maxdisend(z,x)), утверждающая, что каждому дискретному интервалу без концов (кроме первого) непосредственно предшествует максимальный дискретный интервал с левым и правым концом. 7) Аксиома (Vx,y)(maxdisend(x,y) — (3z)dis(y, z)), утверждающая, что за каждым максимальным дискретным интервалом с левым и правым концом непосредственно следует дискретный интервал без концов. 8) Аксиома (Vx,y)(maxdisend(x,y) —» (3z)dis(z, х)), утверждающая, что каждому максимальному дискретному интервалу с левым и правым концом непосредственно предшествует дискретный интервал без концов. 9) И для каждого п 2 аксиома (\/жі,..., хп)(((хі ]... ] хп) & k.maxdisend(xi,xn)) — (Vyi,z)(((a;„ уі) &cmaxdisend(yi,z)) — (Зг/2, ,Уп)(Уі У2 - - уп z))). Эти аксиомы говорят о том, что размер конечных максимальных дискретных интервалов с левым и правым концом возрастает. Очевидно, что С (= Ах. Пусть Сі \= Ах, тогда С\ = 1+ 2 (Т п + рп) + Y2 (Dn + Т п), где а — некоторый линейный порядок, Т п — произволь- пЄСха ные дискретные линейные порядки без концов, при п Є ш или пах(,и Т — произвольные бесконечные дискретные линейные порядки с левым и правым концом, при га Є а х (. Покажем, что модели С и С\ элементарно эквивалентны. Пусть С — насыщенная модель мощности ш\ для некоторого счётного линейного порядка С (= Ах, являющаяся его элементарным расширением, в предположении континуум гипотезы такая модель существует. Из С\ \= Ах и, следовательно, С (= Ах следует, что С = 1 + Е (Р п + Рп) + Е (Рп + Ю ) Для некоторых V n, a , (D )\ Утверждается, что 1) для всех п Є. и ип Є а линейные порядки Т п = (I? , цэ«) являются насыщенными дискретными линейными порядками без концов мощности u i; 2) для всех п Є а линейные порядки (D ) = ((D ) , DEy) являются насыщенными дискретными линейными порядками с левым и правым концом мощности и\, 3) w + (xa = (А, [А), где А = {а \ С (= (3x)maxdis(a, х)}, является насыщенным дискретным линейным порядком с левым концом мощности Ct i. Приведём доказательство пункта 3, как наиболее сложного. Доказательства остальных пунктов аналогичны. Итак, пусть Л = (А, \А)- Рассмотрим счётное множество X (X С А) и некоторый гг-тип р теории Th((A,Ci)i x)- Будем считать, что п = 1. Пусть Ф(ж) — формула типа р в пренексной нормальной форме, заменим в ней (поочередно, начиная с самого внутреннего) каждое вхождение (Эу)Ф(у) на (3y)((3z)maxdis(y, z) &Ф(у)), и каждое вхождение (\/?/)Ф(у) на (Vy)((3z)maxdis(y,z) —у Ф(у)), после такого преобразования получим формулу Ф (х).
Рассмотрим множество формул pi = {Ф (х) &c(3z)maxdis(x,z) Ф(ж) Є р}, оно является совместным с Th((C ,Ci)i&x) и, следовательно, может быть расширено до типа теории Th((C ,Ci)iex)- Пусть а реализация этого типа, тогда С \= (3x)maxdis(a, х) и, следовательно, а Є А и элемент а реализует тип р в (А, Сг)іх- Случай с п 1 рассматривается аналогично. Без ограничения общности можно считать, что С\ является счётным, иначе возьмём его счётную элементарную подмодель. Рассмотрим элементарное расширение порядка С до насыщенного порядка мощности и)\ и элементарное расширение порядка С\ до насыщенного порядка С\ мощности u i, из доказанного выше вытекает, что С = С\. Тогда из С , і С\ и С = С\ следует, что С = Сг Итак, модели С и С\ элементарно эквивалентны и, следовательно, теория Тдх = {Ф Ах Ь Ф} является полной и совпадает с Т = Th(C). Лемма 2.3.3. С — простая модель теории Т = Th(C). Доказательство. На каждой тг-ке порядка С реализуется некоторая пол- ная формула, следовательно, модель С — атомная и, будучи счётной, является простой. Лемма 2.3.4. Семейство главных типов теории Т вычислимо. Доказательство. Пусть Ф(х) главная формула для n-типар. Тогда Ф го ворит о том, к какому типу интервала принадлежит каждый ХІ Єх для г п (имеются ввиду интервалы, определяемые формулами Со, 2, d,...), для конечных интервалов указывается точное расположение каждого элемента и, если для некоторого подмножества {її,... , г" ,} С {1,... ,п} элементы хч,..., Xik лежат в одном интервале, то дополнительно указы вается их расположение друг относительно друга и точное количество элементов между ними. Несложно показать, что существует вычислимая нумерация всех главных формул и, следовательно, существует вычисли мая нумерация всех главных типов. Таким образом, семейство главных типов теории Т вычислимо. Из предыдущих лемм и теоремы 1.1.4 следует, что порядок С обладает разрешимым представлением.
Для линейных порядков
Полная характеризация класса линейных порядков автоустойчивых в классе вычислимых представлений приведена в следующей теореме. Теорема 3.2.1 (Реммел, см. [18, 39]). Линейный порядок автоустойчив в классе вычислимых представлений тогда и только тогда, когда он имеет порядковый тип XX + v) + kn+\, где кг — конечные интервалы для г п + 1. Автоустойчивость линейных порядков в классе 1-разрешимых представлений описана Мозесом: Теорема 3.2.2 (Мозес, см. [18, 34, 35]). Линейный порядок автоустойчив в классе 1-разрешимых представлений тогда и только тогда, когда он имеет порядковый тип 5 (/ + gi) + kn+x, где ki — конечные интер-валы для і п + 1, а дг є {и, ш , } U {d х г} d Є N} для і п. Перейдем к автоустойчивости относительно автоматных представлений. Теорема 3.2.3. Ординалы автоустойчивы в классе автоматных представлений. Доказательство. Из теоремы 2.2.3 следует, что нам необходимо доказать, что любые два автоматных представления ординала а иш вычислимо изоморфны. Предположим, что существует эффективная процедура, перечисляющая последовательность FO-формул Фо(ж), Фі(ж),..., Фп(х), ., такую, что на каждом элементе из а истинна в точности одна формула из этой последовательности и каждая формула из этой последовательности истинна в точности на одном элементе из а. Тогда из существования такой последовательности следует существование искомого изоморфизма для а. Действительно, мы можем строить изоморфизм по шагам и на шагах п отображать элемент, на котором истинна формула Фп в одном представлении, в элемент, на котором истинна эта формула в другом представлении. Из теоремы 1.3.4 следует, что изоморфизм строится эффективно. Покажем, что для всех а шш такая последовательность существует. а = и. Пусть 32 — отношение непосредственного следования, определённое ранее, Ыт(х) t=; (Vy)(x у) — формула, выделяющая наименьший элемент. Тогда для а — ш последовательность формул выглядит следующим образом: Фо(ж) Ыт(х), Фі(ж) ±=Ї а = ш2. Рассмотрим отношения Ытх{х) ±=F - (3у)(у х), определяющее предельные элементы первого порядка, И X i у =i Lirni(x)&Limi(y)$z- (3z)(Limi(z)&(x z у)), задающее непосредственное следование на предельных элементах первого порядка.
Теперь определим формулы Фк,т(х) Для к,т 0, обозначающие, что х лежит в к-том интервале типа ш и расположен в этом интервале на месте га: fc.m ) = (Зу)(Ф/с,т-і(у) & (у яг) для fc, га 1. Таким образом, каждый элемент задаётся некоторой формулой и каждая формула задаёт некоторый элемент из а = аА Для случая а = а/т получаем набор формул Фаь...,ат для аі,...,от Є N, истинных на единственных элементах из шт и задающих каждый элемент и)т. Для их построения для всех п 2 определим отношения, уже определенные для 1, Ытп{х) Limn-i(x) &- (3y)(y n-i х), выделяющие предельные элементы порядка п, и х п у ь=? Ытп(х) & Ытп(у) & - (3z){Limn{z) & (ж z у)), задающие непосредственное следование на предельных элементах порядка п. Формулы Фа1)...,ат получаются, как и в предыдущем случае: находим предельные элементы, затем находим предельные среди предельных, повторяем т раз. Найдя предельный элемент га-того порядка (то есть наименьший элемент), отсчитываем от него с помощью непосредственного следования на предельных элементах (га — 1)-го порядка ai-ый предельный (га — 1)-го порядка. Затем находим аг-ой (от только что найденного элемента) предельный (то — 2)-го порядка и так далее до ат-того непредельного. При а = штп формулы определяются аналогично случаю а = шт+1. Получим набор формул Фв1 ami0nl+1 для сц, ...,om,am+i Є N и ат+1 п. Рассмотрим теперь самый общий случай для произвольного а шш, в таком случае а может быть представлен как шт1п\ +шт2п2 +... +шткПк, где к,п\,... ,Пк,тх,... ,rrik Є N, щ ф 0 и тщ ... m 0. Тогда с помощью введённых отношений находим предельные (т .+1)-го порядка, среди них наибольший, который является наименьшим элементом для и ткщ. Дальше действуем так, как действовали бы отдельно для шШкПк, используя найденный наименьший элемент. Затем аналогично находим предельные (гпк-і + 1)-го порядка и среди них наибольший, он является наименьшим для шТПк-1Пк-і. И так далее, в итоге получим к наборов формул: (где (где Ol, . . . , йщ , оПг .і Є Ми amfc+i ПІ), истинных на единственных элементах из а и задающих каждый элемент а.
Очевидно, что эти формулы могут быть эффективно перечислены. Теорема 3.2.4. Разреженные линейные порядки FC-ранга, не превосходящего 2, автоустойчивы в классе автоматных представлений. Доказательство. Пусть С — автоматный линейный порядок FC-ранга, не превосходящего 2. Как и в предыдущей теореме, достаточно показать, что существует эффективное перечисление формул задающих все элементы из С Согласно теореме 2.1.9, если FC-ранг С равен 1, тогда он является либо конечным линейным порядком, либо порядком типа и (эти случаи разобраны в предыдущей теореме), либо типа ш (этот случай аналогичен случаю сш,в формулах, выделяющих элементы, необходимо сменить все знаки меньше на больше), либо типа . Построим последовательность формул для последнего случая, когда С = . Пусть о — некоторый параметр, для к 1: Заметим, что здесь мы доказываем только существование изоморфизма между любыми двумя автоматными представлениями. Если определить эффективный способ выбора параметра, например, выбирать л-лексикографически наименьший элемент из каждого автоматного представления, то искомый изоморфизм может быть построен равномерно эффективно по данным автоматным представлениям. Таким образом, для линейных порядков ранга 1 всё доказано. Итак, пусть С = (L, ) — автоматный разреженный линейный порядок, имеющий FC-ранг 2. Из теорем 2.1.7 и 2.1.9 следует, что С = ]Г) ЛІ, где J,ЛІ Є {w,u ,} U {а}п ш. Наибольшую сложность представляет случай, когда X = , поэтому мы будем проводить доказательство для этого случая, которое является наиболее общим и также работает для остальных случаев. Мы построим последовательность FO + 3- формул, и каждая формула этой последовательности будет истинна на не более чем одном элементе из С. При этих обобщениях утверждение о существовании изоморфизма остаётся верным в силу теоремы 1.3.5 и модифицированной пошаговой конструкции. А именно, если на каком-то шаге п мы обнаружим, что не существует элемента, на котором Фп истинна, то на этом шаге ничего больше делать не будем и перейдём к следующему шагу. С помощью отношения с(ж, у) ±=т (х у) !k-i(3z)(x z у), истинного на элементах, между которыми конечное число элементов, определяются формулы со(х),со (х),({х),п(х), определяющие какому типу ЛІ принадлежит х, здесь п(х) истинно на элементах, принадлежащих конечным интервалам. Определим, например, со (х) ±= Далее с помощью л-лексикографического порядка выделим л-лексикографически наименьший элемент в каждом интервале типа . В интервалах типов со и конечных интервалах возьмём наименьший элемент, в интервалах типа со возьмём наибольший элемент. Получим отношения со(х), со (ж), С(ж), п(х).
Сохранение автоматности
Объектами изучения математики являются модели (структуры) — множества с заданными на них отношениями и операциями. В середине прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, М. О. Рабина, Р. Воота и других появилось понятие вычислимой или конструктивной модели, то есть модели, которая может быть описана алгоритмически. С этого момента в математической логике образовалась новая подобласть — конструктивные модели, активное развитие которой продолжается до сих пор. Класс вычислимых моделей является наиболее общим и довольно сложным, в связи с этим возникло стремление выделить простейший с алгоритмической точки зрения подкласс вычислимых моделей. Одним из предложенных на эту роль классов является класс автоматных структур. Достоинства этого класса заключаются в том, что наиболее естественные проблемы и свойства автоматных моделей являются разрешимыми. Упоминания такого рода моделей впервые появились в работах Дж.Р.Бюхи и М. О.Рабина [15], [16], [37], [38], которые изучали теорию конечных автоматов и рассматривали представления некоторых структур с помощью автоматов. С появлением в 1995 году статьи А. Нероуда и Б.Хусаинова [25], в которой было предложено систематическое исследование автоматных структур, последние подверглись интенсивному изучению. К настоящему времени теория автоматных структур представляет одно из основных направлений исследований в области конструктивных моделей. Под автоматной структурой подразумевается модель в конечной предикатной сигнатуре, основное множество и все отношения которой распознаются конечными автоматами (автоматы, распознающие п-местные отношения, работают синхронно на п-ках слов). Различные типы конечных автоматов, таких как автоматы на конечных словах, автоматы Бюхи, автоматы на деревьях, порождают различные типы автоматных структур. Автоматные структуры всех перечисленных типов обладают рядом разрешимых свойств. Элементарная теория автоматных структур, например, является разрешимой [22, 25, 12]. Класс словесно-автоматных структур, то есть структур в конечной предикатной сигнатуре, распознаваемых автоматами на конечных словах, наиболее простой среди упомянутых, в него попадают лишь счётные модели.
Словесно-автоматными структурами, например, являются: (N,+), (Q, ), булева алгебра Вш конечных и коконечных подмножеств натуральных чисел, в то время как такие структуры, как (N, х) [12], (Q,+) [44], безатомная булева алгебра [28], не являются словесно-автоматными. Класс Бюхи-автоматных структур, где автоматы работают на бесконечных словах, охватывает как счётные так и несчётные структуры, хотя на счётных структурах эти два класса совпадают [10, 11]. В класс древесно-автоматных структур также попадают только счётные модели, однако, он обширнее класса автоматных структур, (N, х) и безатомная булева алгебра, например, являются древесно-автоматными. Интересен также класс Рабин-автоматных структур, распознаваемых конечными автоматами, работающими на бесконечных полных бинарных деревьях. В этой работе мы будем касаться только словесно-автоматных структур, так как они всё ещё остаются слабо изученными, поэтому мы будем использовать везде термин автоматная структура, подразумевая под ним словесно-автоматную структуру. Основные результаты этой работы касаются наиболее естественных классов структур, таких как линейные порядки, частичные порядки и отношения эквивалентности. В области характеризации типов изоморфизма автоматных моделей из перечисленных классов получены следующие результаты: автоматными ординалами являются в точности те ординалы, которые строго меньше чем шы [17]; С. Рубин, Ф.Стефан и Б.Хусаинов доказали, что -FC-ранг автоматных линейных порядков и деревьев конечен [29]; в [23, 24, 33] исследованы автоматные вполне упорядочиваемые частичные порядки и показано, что они являются автоматными тогда и только тогда, когда их ранг строго меньше иґ. В [31] исследованы некоторые теоретико-модельные свойства автоматных представлений плотного линейного порядка, а именно, доказано существование автоматно-однородного представления для (Q, ), то есть любые два одинаково упорядоченных кортежа в этом представлении могут быть переведены один в другой с помощью автоматного изоморфизма, и также было показано, что любой автоматный линейный порядок автоматно вкладывается в подходящее автоматное представление плотного порядка. Известно, что вычислимые модели определимы формулами в языке логики первого порядка в (N, +, х). Аналогичное утверждение верно для автоматных структур, то есть любая автоматная структура определима в JVfc = (N, +, fc), где 1 — двухместное отношение и х\ъу, если у является степенью кя х делится на у (см. [12, 41]).
Пусть к 1 и Е& = {0,1,..., к— 1}, рассмотрим структуру Wk = (S , (cra) 6Sfc, 2,eZ2), где aa(w) = wa, x у, если x есть префикс у, и el{u,v), если \и\ = г . Для всех fc 1, Wk является автоматной и полной, в том смысле, что любая автоматная структура определима в ней (см. [12, 41]). Как уже было сказано выше, естественные теоретико-модельные свойства для автоматных структур являются разрешимыми. А именно, модели, обладающие автоматным представлением, являются разрешимыми и, более того, разрешимыми в некоторых кванторных расширениях. Рассмотрим квантор Э, трактуемый как «существует бесконечно много», и для к,т Є N, О к т, т 1, кванторы 3 k m\ обозначающие «существует к по модулю т много», тогда теория первого порядка в языке, расширенном квантором 3 и кванторами 3 k m\ автоматных структур является разрешимой [12, 30, 41]. Мы показали, что класс автоматных линейных порядков не совпадает с классом разрешимых в расширенном квантором 3 языке линейных порядков. Так как модель может обладать различными вычислимыми представлениями, то естественным образом возникает вопрос об эквивалентно- сти этих представлений с алгоритмической точки зрения. Исследование этого вопроса было начато А. И. Мальцевым, который заметил, что конечно порождённые алгебраические системы обладают единственным с точностью до вычислимого изоморфизма представлением, то есть все разрешимые свойства в одном представлении остаются разрешимыми в другом. Но уже в [5] было показано, что для бесконечномерного векторного пространства над полем рациональных чисел можно построить два различных вычислимых представления, таких, что в одном проблема линейной зависимости векторов разрешима, а в другом нет. Таким образом, различные вычислимые представления одной модели могут обладать различными алгоритмическими свойствами. Модели, любые два вычислимых представления которых вычислимо изоморфны, были названы автоустойчивыми (вычислимо категоричными), а вычислимые представления, между которыми существует вычислимый изоморфизм, автоэквивалентными. Исследование автоустойчивости моделей и более общего понятия алгоритмической размерности моделей продолжили такие математики, как С. С. Гончаров, А. Т. Нуртазин, Дж. Б. Реммел, Б. Хусаинов, Р. Шор и другие. В диссертации поднимается вопрос об автоустойчивости моделей в классе автоматных представлений. Естественней было бы называть автоэквивалентными автоматные представления, между которыми существует автоматный изоморфизм, но в таком случае каждая бесконечная модель имеет счётное число не автоматно изоморфных автоматных представлений [25].
