Конструктивные булевы алгебры с выделенными идеалами

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

Оглавление
Введение
Глава 1. Предварительные сведения
§1.1. Предварительные сведения из теории булевых алгебр
§1.2. Предварительные сведения из теории конструктивных
моделей
Глава 2. Универсальная нумерация конструктивных
/-алгебр
§2.1. Порождающие деревья для конструктивных /-алгебр
§2.2. Существование универсальной нумерации
§2.3. Единственность универсальной нумерации
Глава 3. О вычислимых нумерациях конструктивных
/-алгебр
§3.1. Индексные множества некоторых подклассов /-алгебр
§3.2. Бесконечность числа попарно несравнимых вычислимых нумераций
§3.3. Сложность нумерационных эквивалентностей вычислимых нумераций
Глава 4. Алгоритмическая размерность булевых алгебр с выделенным идеалом
§4.1. Ветвящиеся булевы алгебры с выделенным идеалом .

§4.2. Автоустойчивые булевы алгебры с выделенным идеалом 65 §4.3. Критерий автоустойчивости булевых алгебр с выделенным идеалом
Список литературы

Введение
Одним из наиболее интересных и актуальных направлений в современных математических исследованиях феномена вычислимости является теория конструктивных (вычислимых) моделей, которая возникла в 50-е годы прошлого столетия в работах А. Фрелиха, Д. Шефердсона, А. И. Мальцева, В. А. Кузнецова, О. Рабина и Р. Во-ота. Это направление связано с исследованием алгоритмических свойств абстрактных моделей на основе построения для них представления на натуральных числах и изучения взаимоотношений алгоритмических и структурных свойств этих моделей.
В сибирской школе алгебры и логики, основанной А. И. Мальцевым, исследования по конструктивным и вычислимым алгебраическим системам были начаты А. И. Мальцевым и продолжены его учениками и их последователями. В основе предложенного им подхода лежит понятие нумерации. Для алгебраической системы нумерация ее основного множества позволяет точно сформулировать вопросы об алгоритмических свойствах абстрактной системы как вопросы о номерах элементов данной системы. Нумерации позволяют транслировать основные алгоритмические проблемы над абстрактными структурами к изучению алгоритмов на натуральных числах или словах некоторого конечного алфавита.
К числу основных проблем теории конструктивных моделей относятся проблемы существования конструктивизаций, продолжения конструктивизаций, вычислимости семейств конструктивизаций,

(2) Для любого в £ {1,..., Л} множество
к, - и{Ьк I & 3 &, к е {1,..., X - 1}}
является идеальным в £>.
Далее по предложению 2.1.2 существует конструктивизация иц I -алгебры 53£0)...,ьж_1 = (53ц,/^,..., /дгЛ). Обозначим:
Яп т -Гк-!) • • • ) /.Ал) (^Ла(п)! -^1й^1(п); • • • ! -^1^/Зл(п))>
о! — ^ = ОГад, где функции /3,... ,(3 определены в следствии 2.2.1.
Таким образом, определена последовательность
(я}Л),(Я*,о,
конструктивных /-алгебр.
Теорема 2.2.1. Последовательность {(21*, | п £ М) являет-
ся универсальной вычислимой нумерацией класса конструктивных I-алгебр. В частности, класс конструктивных I-алгебр строго вычислим.
Доказательство. В силу предложения 2.1.2 и замечания 2.1.1 индексы рекурсивных функций /”, /", представляющих основные операции в /-алгебре (21*, и*), а также индексы характеристических функций рекурсивных множеств Г]ип = {(ж, у) | га* (ж) = га*(у)} и ГДе 5 ^ (1, - - -, А}, равномерно эффективным образом вычисляются по р.п. индексам множеств Иф0(„),..., то есть
по индексам «о (га),..., ан-{п), которые в свою очередь эффективно вычисляются по номеру п. Если ((03, Д,..., /д), га) - произвольная конструктивная /-алгебра, то по предложению 2.1.3 и предложению 2.2.2 существует га £ N такое, что ((53,1,..., /д), га) и (21*, га*)