Вычислимость и разрешимость в классе булевых алгебр

• Автор: Алаев, Павел Евгеньевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Новосибирск
• Количество страниц: 119 с.

Глава 1. Сильно конструктивные булевы алгебры

1.1. Один признак конструктивизируемости

1.2. Критерий изоморфизма

1.3. Оценка сложности моделей

Глава 2. Однородные булевы алгебры

2.1. Критерий вычислимости для однородных булевых алгебр

2.2. Метатеорема для «-систем

2.3. Метатеорема для фактор-алгебр

2.4. Две вспомогательные конструкции и отношения <а

Глава 3. Автоустойчивые 1-алгебры

3.1. Псевдо-неразложимые I-алгебры

3.2. Алгебраические инварианты
3.3. Критерий изоморфизма
3.4. Теорема о ветвлении
3.5. Необходимые условия автоустойчивости
3.6. Критерий автоустойчивости
Литература

Диссертация посвящена решению некоторых проблем из теории вычислимых (конструктивных) моделей. Её основные результаты относятся к вычислимым булевым алгебрам, хотя некоторые рассматриваемые вопросы имеют более широкий характер. Теория вычислимых моделей возникла в 50-х годах прошлого века в работах А.И. Мальцева, О. Рабина и др., и с тех пор активно развивается. Объём литературы, посвящённой этой теме, очень велик. В качестве наиболее важных и современных источников можно указать [11, 30, 35]. Булевы алгебры, в свою очередь, тоже являются классическим объектом, привлекающим внимание математиков уже в течение полутора веков. Попытка собрать хотя бы основные достижения в этой области привели к появлению в 1989 году трёхтомного справочника [34].
Вычислимые булевы алгебры нашли многочисленные приложения в теории алгоритмов, математической логике, теории моделей и др. областях. Хорошим источником по этой теме является монография [9], в которой представлены, впрочем, достижения в первую очередь новосибирского коллектива математиков, являющегося одним из лидеров в данной области. Диссертация является, в частности, естественным продолжением этой монографии — она отвечает на некоторые поставленные там вопросы и развивает ряд затронутых тем. Неплохим обзором является [31].
Напомним, что модель А конечного языка называется вычислимой, если её носитель — вычислимое подмножество множества натуральных чисел из, а операции и предикаты — вычислимые функции на этом подмножестве. В свою очередь, под вычислимыми функциями понимаются те, которые могут быть вычислены с помощью некоторой машины Тьюринга, а под вычислимыми множествами — обладающие вычислимыми характеристическими функциями. Понятие констрг/ктивной модели даёт нам другой подход к тому же классу объектов, который фактически основан на использовании другого языка; немного более подробно связь между ними обсуждается в начале Главы 1. Говорим, что произвольная модель А кон-структивизируема, если она изоморфна некоторой вычислимой модели.
Центральными проблемами теории вычислимых моделей являются вопрос о

том, какие модели являются конструктивизируемыми, и насколько велико число различных вычислимых представлений у данной модели. Последнее понятие, число различных представлений, может пониматься в разных смыслах, и в литературе рассматривается несколько подходов, которые сводятся к разным определениям “эквивалентных” представлений. В настоящей диссертации используется наиболее сильный подход: две вычислимые модели Аг,А2 считаются “эквивалентными”, если между ними существует вычислимый изоморфизм / А -> Л2, то есть изоморфизм, одновременно являющийся вычислимой функцией на носителе Лі- В этом случае мы говорим, что модели А и А2 вычислимо изоморфны. Изучение этой темы было начато А.И. Мальцевым, который в [17] назвал автоустпойчивы-ми те модели, у которых все вычислимые представления вычислимо изоморфны. Максимальное число вычислимых представлений модели А, которые не являются вычислимо изоморфными друг другу, называется алгоритмической размерностью модели А, бішс(А), или авторазмерностъю (это понятие было впервые введено в
[7])-
Когда мы говорим о булевых алгебрах, в первую очередь разумно задаться вопросом об описании тех из них, которые являются конструктивизируемыми. К сожалению, на данный момент эта задача представляется неразрешимой — этот класс очень велик, и нет никаких разумных гипотез о его алгебраической характеризации. При этом существует несколько способов сводить проблему такого описания к некоторым другим: например, булева алгебра А конструктивизируема тогда и только тогда, когда она может быть порождена некоторым вычислимым линейным порядком (см. [9]). Этот факт позволяет нам свести описание конструктиви-зируемых булевых алгебр к описанию конструктивизируемых линейных порядков, К сожалению, последняя задача является ещё более сложной, чем предыдущая. Точно так же от вычислимых булевых алгебр можно перейти к вычислимым бинарным деревьям, или булевым кольцам.
Но при этом для некоторых важных подклассов булевых алгебр ситуация является не столь безнадёжной. Например, в [4] было найдено описание копструктиви-зируемых суператомных булевых алгебр — критерием оказалась конструктивность ординала, который является естественным рангом алгебры. В [20] была получена

(3) если (а,Ь) е М, хх,х2а, то существуют (01,61),(а„, Ъп) € N такие, что аг апа, Ъ ЬпЬ их,х2 представимы как суммы некоторых подиаборов из {щ, •••) оп},
(4) если (а,Ь) € ./V, У1,У2Ь, то существуют (а,Ь{),... ,(ап,Ьп) € N такие, что ах апа, Ь ЪпЬ и ух, у2 представимы как суммы некоторых поднаборов из {£>1 Ьп}
(5) существуют а1 о„|1 в А, Ь Ъп|1 в В такие, что (щ,Ьх) € N для г € {1
Тогда А изоморфна В.
Предложение 2.3.4. Пусть Л0 ^ Ах ^ ... — последовательность ненулевых конечных алгебр, Т — стабильный идеальный оператор, В — алгебра, В/Т = 1. Пусть А — и 1еиАх, С = Ънп{В-Ах,кх}х^ш, еде 1ц : В-Ах -> В-Л,+1 — канонические вложения. Тогда А = С /Т.
Доказательство. Существуют естественные вложения ух : В • Ах —> С, которые в силу условия будут Т-стабильными. Если {рх рД — все атомы Ах, то пусть В • Ах — ® • • • ®
Воспользуемся критерием Вота: положим N — {(р, Ух{^х,Р) /Т(С)) | г € со, р — атом в Ах} и {(0,0/Т(С))}. Проверим свойства из леммы 2.3.3:
(1): 1*,р £ Т(В • Ах), поэтому уД1,,р) £ Т(С).
(2): следует непосредственно из определения.
(5): если {рх,... ,рк} — все атомы Л0, то рь... ,р*|1 в А0, 10,Р1 1о,^|1 в В ■ А0. (4): пусть (р,МЫ/ПС)) € ЛГ, яМ/Т(С) = х'/Т(С) + у'/Т(С% х'/Т(С) ■ у'/Т(С) — 0. Можно считать, что дх(1х,р) = х' + у', х' ■ у' = 0. Нужно рассмотреть только случай х',у' Т(С). Пусть у > г, х,у е В • А^ таковы, что
х' = &'(*)> У' — 9з(у)- Положим hxj = Лу_хо. ■ -°1ц. Тогда дх = Уjoh^j, ДДДр) = £+у. Дальнейшие рассуждения ведем в В ■ А^.
Если ух,... ,уп ~ атомы Aj,q^ упр, то из определения легко следует, что МЧр) = Чя1 ® • • • ® Для каждого £ € {1 п} либо х • 1Л?( € Т(В • ЛД и У' ^ Т(В • ЛД, либо наоборот а; • 1^9( ^ Т(В ■ ЛД и у • € Т(В • ЛД. Отсюда