Вычислимость и конструктивность в ограниченных фрагментах теорий тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Подзоров, Сергей Юрьевич

• Подзоров, Сергей Юрьевич
• кандидат физико-математических наук
• 1999

Оглавление диссертации кандидат физико-математических наук Подзоров, Сергей Юрьевич

Содержание

1 Основные определения

1.1 Основные понятия, относящиеся к теории моделей, теории рекурсии и общим вопросам

1.2 Основные понятия, относящиеся к булевым алгебрам, и иерархия Фейнера

2 Вычислимые классы конструктивизацдй

2-конструктивизируемых моделей

2.1 Предварительные сведения

2.2 Доказательство эффективной бесконечности

3 Ограниченно полные модели

3.1 Ограниченно полные булевы алгебры в константных обогащениях

3.2 Ограниченно полные булевы алгебры в обогащении идеалом

4 Рекурсивные однородные булевы алгебры

4.1 Необходимое и достаточное условия рекурсив-ности

4.2 Простые и счетно-насыщенные булевы алгебры

5 Список литературы

Введение диссертации (часть автореферата) на тему «Вычислимость и конструктивность в ограниченных фрагментах теорий»

Введение

Основные результаты этой диссертации относятся к конструктивным моделям — сравнительно новому направлению математической логики, возникшему на стыке теории моделей и теории рекурсий. Можно считать, что в настоящий момент теория конструктивных моделей переживает свой расцвет: начиная с пионерских работ А.И.Мальцева количество статей, посвященных этой тематике, исчисляется сотнями. Несмотря на многообразие уже достигнутых результатов, в этой области постоянно появляются новые проблемы, привлекающие внимание специалистов во всем мире. В то время как одни направления исследований только начинают развиваться, другие уже стали классическими. На протяжении последних двадцати лет получен ряд нетривиальных и глубоких результатов, изданы монографии, посвященные различным вопросам теории конструктивных моделей.

В этой работе изучается ряд различных вопросов, связанных с описанием классов конструктивизаций моделей различной степени сложности.

Первая глава диссертации является вводной. В ней излагаются наиболее важные определения, с которыми автор работает в следующих трех главах. Необходимость выделения их в отдельную главу объясняется, во первых, большим количеством основных понятий, которые автор считает нужным обозначить или даже дать подробное описание, не ограничиваясь ссылками на зачастую неполные и противоречащие друг другу первоисточники, а, во вторых, тем, что в литературе нет устоявшейся системы обозначений для многих важных универсальных понятий, которые используются на протяжении всей диссертации. В связи с наличием такой главы автор не считает нужным давать какие-либо точные определения и формулировки в этом введении (авторский стиль и так страдает от большого количества повторов: зачем усугублять ситуацию и определять два раза одно и то же?)

Во второй и третьей главах содержатся результаты, напрямую относящиеся к классической проблеме алгоритмической размерности моделей. Хотя, как показал С.С.Гончаров [8], существуют не автоустойчивые модели конечной алгоритмической размерности, для большинства естественных классов алгебраических систем (булевы алгебры, линейные порядки и др.) таких моделей нет (модели конечной размерности приходится строить специально, они получаются в результате довольно сложной конструкции). Существует хороший критерий, позволяющий устанавливать бесконечность алгоритмической размерности — так называемая эффективная бесконечность класса конструктивизаций моде-

ли. В связи с широкой применимостью этого критерия в последнее время наметилась тенденция "приравнивать" модели с вычислимым классом всех конструктивизаций к моделям конечной размерности. И при изучении класса конструктивизаций той или иной модели на первый план выходит не вопрос о числе конструктивизаций, а вопрос об эффективной бесконечности (невычислимости) класса всех конструктивизаций модели.

Наряду с группой алгебраических критериев С.С.Гончаровым доказано несколько теоретико-модельных, позволяющих утверждать эффективную бесконечность класса конструктивизаций модели, удовлетворяющей этим критериям. Основные идеи этого подхода заложены в работе [6]: в ней доказаны две теоремы.

1. Класс конструктивизаций 1-конструктивизируемой предельно 0-полной модели эффективно бесконечен.

2. Класс конструктивизаций 1-полной 2-конструктивизируемой модели, не обладающей вычислимым семейством Скотта ни в каком обогащении конечным числом констант, эффективно бесконечен.

Как следует из результата О.В.Кудинова [13], второй критерий нельзя улучшить, сняв ограничение на 2-конструктивизируемость. Можно ли его улучшить, сняв ограничения на 1-полноту?

Если модель не 1-полна ни в каком конечном обогащении константами, то класс ее конструктивизаций будет эффективно бесконечен согласно первому критерию. Если же она не 1-полна, но 1-полна в обогащении конечным числом констант, то ответ неизвестен, хотя про такую модель молено сказать довольно много. Во первых, можно показать, что в этом случае модель имеет бесконечно много конструктивизаций. Во вторых, как следует из результатов второй главы, либо класс ее конструктивизаций в самом деле эффективно бесконечен, либо это Д^-автоустойчивая модель, простая в некотором конечном обогащении, причем все полные формулы являются В-формулами. В третьих, можно предполагать, что эта модель 2-полна в некотором конечном обогащении константами, потому что ... Тут мы опять возвращаемся к первому критерию.

В работах [9, 10] этот критерий улучшен: доказано, что для п £ N и {и} класс конструктивизаций (1 + п)-конструктивизируемой предельно п-полиой модели эффективно бесконечен. В связи с этим одна из старых проблем теории конструктивных моделей, поставленная А.Т.Нуртазиным [16], оказалась решенной: если модель имеет сильную и слабую конструктивизации, то класс ее конструктивизаций эффективно бесконечен.

А что будет, если все коиструктивизации модели сильные? Ответ неизвестен. Существующие на настоящий момент методы подталкивают нас к построению конструкций, похожих на конструкцию из доказательства второго критерия. И мы опять приходим к той же проблеме, что и раньше; сильная конструктивизируемость по сравнению с 2-конструк-тивизируемостью ничего не дает. Кстати, для не автоустойчивой сильно конструктивизируемой модели существует бесконечно много попарно не автоэквивалентных конструктивизаций.

Основным результатом второй главы является следствие 2.2.2. Оно, хоть и не решает очерченную выше проблему, но значительно сужает ее. В третьей главе для каждого п е N11 {а;} строится пример предельно п-полиой модели, что показывает определенную "содержательность" критерия, доказанного в [9, 10]. Кроме того, в этой главе доказано одно довольно интересное свойство, касающееся ограниченных теорий булевых алгебр. Основным результатом здесь является, пожалуй, утверждение 3.1.1, хотя в контексте главы оно носит вспомогательный характер.

Третью главу можно также рассматривать как переходную между второй и четвертой, поскольку в ней круг вопросов, характерных для второй главы, обсуждается на материале булевых алгебр. Четвертая глава диссертации посвящена однородным булевым алгебрам.

Впервые счетные однородные булевы алгебры были подробно исследованы А.С.Морозовым [15]. Им получено описание всех таких алгебр с точностью до изоморфизма и установлен критерий разрешимости. В случае рекурсивных булевых алгебр столь простой характеризации получить не удается.

Соответствующая проблема — описать все рекурсивные однородные булевы алгебры с точностью до изоморфизма — была поставлена С.С.Гончаровым на международной конференции по теории сложности и теории рекурсий, проходившей в Казани летом 1997 года. В данной работе получено некоторое достаточное условие рекурсивности, которое показывает, что рекурсивными являются однородные булевы алгебры с достаточно сложным описанием. В частности, если искомая харак-теризация существует, то в силу результатов четвертой главы можно ожидать, что она окажется достаточно сложной.

Во второй части главы показано, что простая и счетно-насыщенная булевы алгебры характеристики (оо,0,0) имеют достаточно много рекурсивных представлений, различных с точки зрения арифметической сложности формульных подмножеств. Центральным результатом главы 4 является теорема 4.1.2.

Содержание диссертации представлено в работах автора [23] - [27]. Результаты, изложенные здесь, докладывались на международных на-

учных конференциях WORCT97, "Мальцевские чтения"-98; на семинарах "Алгебра и логика", "Конструктивные модели" Новосибирского Государственного Университета.

В заключении автор выражает глубокую признательность своему научному руководителю С.С.Гончарову за постановку задач, интерес, проявленный им к исследованиям автора, и постоянную поддержку в работе.

1 Основные определения

В этой короткой главе мы обозначим основные понятия и введем необходимые определения, относящиеся к теме этой диссертации.

1.1 Основные понятия, относящиеся к теории моделей, теории рекурсии и общим вопросам

В части основных определений, касающихся языков первого порядка (понятия сигнатуры, терма, атомарной формулы, формулы и т.п.), автор придерживается книги [4]. Основные понятия теории моделей взяты из [4, 12, 22], теории рекурсий — из [21]. В вопросах, относящихся к теории нумераций, мы будем придерживаться книги [2], в теории конструктивных моделей — [3] и [11].

Носитель модели мы будем отождествлять с самой моделью (и писать х £ ЭДТ вместо х £ |ЭД?|). Модели будем обозначать большими готическими буквами.

Для множества й" через Б<ш мы будем обозначать множество конечных последовательностей элементов из Я. Пустую последовательность будем обозначать через Л. Под мы понимаем множество бесконечных последовательностей элементов из Б (или, что то же самое, множество отображений натурального ряда в Б). Для т £ Б<ш, а € запись

г * а будет обозначать последовательность, в которой сначала идут все элементы г, а потом — все элементы ст. Запись т ^ а обозначает, что для некоторой последовательности 5 сг = т * 5. Длину последовательности г обозначаем через |т|. Для 0 < % ^ |г| через т» или 7Г;(т) мы обозначаем г-ый член последовательности т.

Под 2<ш и 2Ш мы понимаем множества {0,1}<ш и {0,1}ш. Натуральные числа обозначаем через М; и>, если не стоит в индексах и не является частью термина, обозначает линейный порядок по типу порядка на натуральных числах.

Для конечной последовательности п — (щ,... ,Пк) элементов из N через Сп и хп будем обозначать конечные последовательности символов

(СП11 • ■ • 1 спк) И (жП1 , . . . , ХПк).

Для множества £ С N через Хз будем обозначать характеристическую функцию множества 51, определенную на всех натуральных числах и равную единице только на элементах из Б.

Кванторы 3°° и В<0° обозначают "существует бесконечно много" и "не существует или существует не более конечного числа".

Для линейных порядков Ь и М под произведением Ь х М будем

понимать линейный порядок

(/ьШз.) ^ (/2,^2) ™>1 < т2 или (ш! = т2) & (/1 ^ /г)-

Через Аи1;(9Н) мы обозначаем группу автоморфизмов модели 9Л.

Объекты конструктивной природы (конечные последовательности, пары чисел, конечные подмножества, метки, формулы эффективно заданной сигнатуры и т.п.) мы будем отождествлять с их номерами в некоторой фиксированной геделевской нумерации. Это соглашение позволит нам, не нарушая формальной строгости изложения, избежать введения громоздкой системы обозначений.

Для частичной функции / : А —> В через 5/ будем обозначать ее область определения, а через р/ — область значений.

Введем семейство частичных функций, представляющее универсальную частично рекурсивную функцию. Пусть

Таким образом, по & и га мы можем эффективно вычислить /¿(га), 5/1 и р/*к. Пусть /к = ШЯ : ^ £ Щ- Тогда {/&} — семейство всех частично рекурсивных функций от одной переменной.

Всюду определенные частично рекурсивные функции мы называем вычислимыми или рекурсивными. Множество А С N называем вычислимым или рекурсивным, если ХА — вычислимая функция.

Пусть = 5/1 и \Ута = и!1^ : 2 € М} — универсальная вычислимая нумерация всех рекурсивно перечислимых множеств.

Под т-эквивалентностью множеств А, В С N мы будем понимать их т-эквивалентность в обычном смысле [21, 7.1].

Классы арифметической иерархии мы будем обозначать через , и Л». Расширим иерархию, определив эти классы для п 6 2: для га < О полагаем = П° = Д° = Д§.

Под формулами языка рекурсивной арифметики мы понимаем нормальные формы арифметических отношений в смысле [21, 14.2].

Пусть ЭДТ — модель, £(ЭД?) — язык модели 971 (включающий в себя множество формул сигнатуры этой модели). Через Е„, (Пп) мы обозначаем множество формул языка £(ЯЯ), имеющих в пренексной нормальной форме не более чем га различных групп кванторов и, в случае, когда число различных групп кванторов равно п, начинающихся с квантора

Л(п) =

т,

если машина Тьюринга с номером к при входном значении га дает на выходе т не более чем за £ шагов ип^;

не определено, иначе.

существования (всеобщности). Ап полагаем равным Ета П Пга (в главе 3 мы частично отступим от этого соглашения в части, касающейся классов £„). Ех-формулы будем называть 3-формулами, П„-формулы — \/-формулами. Формулы из класса £„ и Пп мы называем га-формулами.

Пусть Г С £(971) — некоторое множество формул языка модели 971. Пусть Ф(х) — формула этого языка. Мы будем говорить, что формула Ф(ж) аппроксимируется множеством формул Г на модели 971 [6], если для любой конечной последовательности т элементов из ЯЛ, такой что 97Т \= ф(т), найдется формула Ф(ж) из Г, для которой:

Ш |=Ф(т);

97Г |=(Уж)(Ф(ж) —->. ф(г)).

Для га £ N модель 971 будем называть п-полной [6], если любая га-формула из £(971) аппроксимируется множеством 3-формул на модели 971. Будем называть эту модель о;-полной [1, 6] (или просто полной), если любая формула из £(971) аппроксимируется множеством 3-формул.

Модель 971 называем предельно га-полной [9], если для некоторого набора а констант из 971 модель (971, а) га-полна, но 971 не (га + 1)-полна ни в каком конечном обогащении константами. Модель 971 называется предельно си-полной [10], если для каждого га £ N найдется набор констант ап из 971, такой что модель (971, ап) га-полна, но для любого набора констант а из 971 модель (971, а) не является полной.

3-формулу Ф(х) языка £(971) будем называть Э-атомной на модели 971, если 971 |= (Зж)Ф(ж) и для любой 3-формулы Ф(ж) если 971 |= (Зж)[Ф(ж) к Ф(ж)], то 971 |= (Уж)[Ф(ж) Ф(ж)]. Множество формул Г будем называть плотным на модели 971, если для любой конечной последовательности (й!,... ,ап) элементов из 97Т существует формула Ф(ж) £ Г, для которой набор свободных переменных х имеет длину га и 971 |= Ф(а1?... ,ап). Будем говорить, что модель 971 является 1-простой, если для нее существует плотное множество 3-атомных 3-формул [6]. В литературе [13] для обозначения плотных множеств 3-атомных 3-формул употребляется также термин "семейства Скотта".

Теорией ТЬ(9Я) модели 971 называем множество предложений языка £(971), истинных на модели 971. Под га-теорией ТЬП(971) модели 971 мы понимаем множество га-предложений языка £(971), истинных на модели 97Т.

Под нумерованной моделью (971, г/) будем понимать пару, состоящую из модели и нумерации и носителя этой модели. Для нумерованной модели (971, и) сигнатуры £ га-диаграммой Д,(971, и) этой модели будем называть множество га-предложений сигнатуры Е и {со, С1,... } (со, ... ^

X), такое что для любого набора натуральных чисел (ni,... , и для любой те-формулы ... ,Хк) сигнатуры S ... ,сПк) £ Оп(Ш, и)

<£4> ШТ \= ip(i/n\,... , vrik). Будем называть 0-диаграмму просто диаграммой и вместо Do(Üft,v) писать г/).

Про нумерованную модель (ШХ,и) будем говорить, что она конструктивна (n-конструктивна), если множество D(fflt,v) (Dn(fflt,v)) вычислимо. Модель (ЭДТ, и) называем сильно конструктивной, если вычислимо множество ДДЯЯ, и) = (J Dn(ÜJl, и).

neN

Про модель ЯП говорим, что она конструктивизируема (п-конструк-тивизируема, сильно конструктивизируема), если для некоторой нумерации v нумерованная модель (ПЛ, и) конструктивна (??,-конструктивна, сильно конструктивна). Саму нумерацию и в этом случае называют конструктивизацией (n-конструктивизацией, сильной конструктивиза-цией).

В западной литературе принят другой подход к этим понятиям. Модель Ш эффективно заданной сигнатуры называют рекурсивной, если носителем модели ЙЯ является вычислимое подмножество натуральных чисел (как правило, это само N), а все операции, отношения и выделенные элементы модели равномерно вычислимы. В случае, когда модель Ш рекурсивна и теории ТЬ(ШТ, N) (ТЬП(ПЯ, N)) вычислимы, говорят о разрешимой (тг-разрешимой) модели. Эквивалентность этих двух подходов хорошо известна.

В рамках второго подхода про конструктивизируемую (п-конструк-тивизируемую, сильно конструктивизируемую) модель говорят, что она имеет рекурсивное (n-разрешимое, разрешимое) представление.

Допуская некоторую вольность в использовании этих понятий, мы будем говорить, что модель Ш рекурсивна (разрешима), если она имеет рекурсивное (разрешимое) представление. Главным образом это относится к главе 4.

Для п £ Z модель DR эффективно заданной сигнатуры будем называть (П°-, Д°-) моделью, если носителем модели Ш является множество N, а все операции, отношения и выделенные элементы модели представлены некоторым (П°, Д°) отношением (Е°-модели еще называют позитивными). Будем также называть модель 9Л (П°-, Д°-) моделью, если она изоморфна некоторой (П°-, Д°-) модели.

Две нумерации v и ¡л модели 9Jt будем называть автоэквивалентными, если найдется автоморфизм tp £ Aut(9Jt) и две вычислимые функции h\ и /¿2, такие что <pv = p,hi и tpvh2 = /i.

Под алгоритмической размерностью конструктивизируемой модели будем понимать число попарно не автоэквивалентных конструктивиза-

ций этой модели. Конструктивизируемую модель будем называть автоустойчивой, если ее алгоритмическая размерность равна единице. Довольно давно было известно, что алгоритмическая размерность модели не может быть больше и; (здесь ш — первый бесконечный кардинал). Как показал С.С.Гончаров [8], любой элемент множества КГи{си} может быть алгоритмической размерностью некоторой конструктивизируемой модели.

Пусть Б — некоторый класс конструктивизаций модели ПК. Будем говорить, что класс Б вычислим (с точностью до автоэквивалентности) [6], если существует последовательность конструктивизаций 70,71,-.. модели 971, такая что множества /7(971,7„) вычислимы равномерно по

п и

1. для любого та £ N найдется ц £ для которой 7„ и ¡л автоэквивалентны;

2. для любой ц £ Б найдется п € М, такой что -уп ж ¡1 автоэквивалентны.

В этом случае последовательность 70,71, • • • мы называем представляющей последовательностью для 5.

Будем говорить, что класс конструктивизаций модели 971 эффективно бесконечен [6], если для любого вычислимого класса конструктивизаций Б равномерно по любой его представляющей последовательности 70,71,... вычисляется конструктивизация //, модели 971, не автоэквивалентная никакой конструктивизации из Б. Очевидно, что в этом случае класс всех конструктивизаций модели 971 невычислим и 971 имеет бесконечно много попарно не автоэквивалентных конструктивизаций.

1.2 Основные понятия, относящиеся к булевым алгебрам, и иерархия Фейнера

В качестве основного источника определений, относящихся к булевым алгебрам, мы будем использовать монографию [11].

Булевы алгебры мы будем обозначать большими готическими буквами (как правило, это 21 и 03). Мы будем рассматривать их в сигнатуре £ = {V, Л, С, 0,1}. Аксиомы теории булевых алгебр [11, 1.2] мы обозначаем через ВА.

Далее везде в тексте этого параграфа 53 обозначает булеву алгебру. Для а,Ь 6 под а \ Ъ мы подразумеваем значение выражения а Л С(Ь). Мы пишем а ^ Ь, если а Л Ъ = а. Будем говорить, что элемент

а лежит под элементом Ъ, если а ^ Ь. Будем говорить, что элемент Ь расщепляется на элементы ^ и «2, если V а2 = Ь и а\ Л а2 = 0.

Для Ъ £ 03 через Ъ мы обозначаем булеву алгебру, получающуюся из 03 при ограничении на главный идеал, порожденный элементом Ъ, то есть Ъ = ({ж £ 03 : х < 6}, V, Л, 6 \ •, 0, Ь).

Для ХСШ под '¿тХ мы понимаем подалгебру в 03, порожденную элементами множества X.

Понятия последовательности итерированных идеалов Ершова-Тар-ского и элементарной характеристики булевой алгебры хорошо известны [11, 2.2]. Для булевой алгебры 03 через «/„(93) мы обозначаем п-ый идеал Ершова-Тарского. Вместо «Д(03) мы пишем просто «/(03) («/0(93) — нулевой идеал).

Элементарную характеристику булевой алгебры 03 будем обозначать через сЬ(ОЗ); элементарную характеристику элемента Ъ £ 03 — через сЬ(Ь). Компоненты элементарной характеристики обозначаются как с^, сЬ-2 и сЬ3.

Идеал Фреше алгебры 03 [11, 1.3] мы обозначаем через F(03) или /'®. п-ый итерированный идеал Фреше будем обозначать через .РЦОЗ).

Пусть Ь — линейный порядок с наименьшим элементом, но без наибольшего элемента. Под булевой алгеброй 03^, построенной по линейному порядку Ь [11, 1.6] мы понимаем подалгебру алгебры всех подмножеств Ь, порожденную элементами вида [а,Ь) = {х £ Ь : а х < Ь}. Если Ь — конструктивный линейный порядок, то алгебра 03/, конструк-тивизируема: для нее существует стандартная конструктивизация, которая строится по конструктивизации линейного порядка Ь [11, 3.2].

Пусть {03г- : г £ /} — семейство булевых алгебр. Прямая сумма

03 = {од}93{ алгебр этого семейства по множеству констант {0,1} ¿6/

определяется в [11, 1.1]. Мы будем придерживаться этого определения. Для вычислимой последовательности {(03„, ип) : п £ М} конструктивных булевых алгебр в [11, 3.5] определена конструктивная булева алгебра (03, г/), для которой 03 = ^ {од}®« и конструктивизацию V мож-

пем

но найти эффективно по семейству г/о,^,...: она называется эффективным представлением прямой суммы булевых алгебр (03„,г^п). Если (03, и) эффективно представима в виде прямой суммы булевых алгебр (93п,г/„), то мы, следуя [И, 3.5], пишем

(Я, V) =гес]Г{0,1 }(®п^п).

пем

Термины "простая", "счетно-насыщенная" и "однородная" булева алгебра мы понимаем в теоретико-модельном смысле [12, 22] (под одно-

родностью понимается (^-однородность). В [11, 2.3] определено понятие плотной булевой алгебры; доказывается, что булева алгебра является плотной тогда и только тогда, когда она счетно-насыщена. В связи с этим термины "плотная булева алгебра" и "насыщенная булева алгебра" взаимозаменяемы. Мы будем пользоваться как тем, так и другим.

В связи с изучением однородных булевых алгебр было введено понятие относительно плотной булевой алгебры. Определим его подробнее. Следуя [11, 2.3], будем называть булеву алгебру 05 относительно плотной, если выполнены следующие условия:

1. для любого п, если существует элемент а £ 03, такой что сЬ(а) = (п, оо, 0), то

(a) для любого Ъ £ 03, такого что сЬ^Ь) > п, найдется а' ^ Ъ, такой что сЬ(а') = (п,оо,0);

(b) если п < сЬх(ОЗ) или п = сЬ^ОЗ) и существуют три элемента а,1,а2,а,з, такие что а; Л а^ = 0, % ф и сЬ(аг) = (п,оо,0), то любой элемент характеристики (п, со, 0) расщепляется на два элемента характеристики (гг,оо,0);

2. если 03 имеет бесконечную первую характеристику сЬ^ОЗ) = оо и существуют три элемента а1,а2,а3, такие что ах V а2 V а3 = 1, щ Л а^ = 0, г ф и сЬ^а;) = оо, то любой элемент с бесконечной первой характеристикой расщепляется на два элемента с бесконечной первой характеристикой.

Известно [11, 2.3], что булева алгебра является относительно плотной тогда и только тогда, когда она однородна.

Счетные однородные булевы алгебры были подробно исследованы А.С.Морозовым [15]. В его работе для каждой однородной булевой алгебры 03 определяется тип однородности 1;ь(03). Ниже мы приводим определение этого понятия для случая, когда первая элементарная характеристика алгебры 03 бесконечна (остальные случаи для нас мало интересны).

Пусть 03 — однородная булева алгебра с бесконечной первой характеристикой. Под типом однородности булевой алгебры 03 будем понимать пару

14») = (а,р),

где а € {1,2,3}, а р = (р0,р1,р2,...) — счетная последовательность элементов множества {0,2}. Будем считать

1. а = 1, если для любого а; 6 ® сЬ^ж) < оо или сЬ^С^ж)) < оо;

2. а = 2, если существует х £ 03 такой, что сЬДж) = сЬх(С(ж)) = оо, но для булевых алгебр ж и С(ж) выполняется первый случай;

3. а = 3, если для любого г £ !В такого, что сЬх(ж) = оо, найдется у ^ ж, для которого сИ^у) = оо и сЬх(ж \ у) = оо.

Для последовательности р полагаем рп = 2 тогда и только тогда, когда найдется ж £ 95, для которого сЬ(ж) = (га, оо, 0).

Доказано [15], что элементарно эквивалентные булевы алгебры с одинаковым типом однородности изоморфны.

Пусть 95 — однородная булева алгебра с бесконечной первой характеристикой и типом однородности (а,р). Под инвариантом Морозова алгебры 53 будем понимать множество

М(03) = {га £ N : рп = 0} .

В [15] доказано следующее утверждение: для однородной булевой алгебры 93

1. если сЬх(ОЗ) < оо, то 03 разрешима;

2. если сЬх(ОЗ) = оо, то 03 разрешима тогда и только тогда, когда М(03) € П°.

Одним из самых мощных инструментов исследования рекурсивных булевых алгебр является техника нормальных сегментов, впервые примененная Одинцовым и Селивановым [17] для изучения арифметических булевых алгебр. Ниже мы, следуя [11, 3.7], дадим необходимые определения.

Нормальным сегментом Т называется подмножество 2<ш, удовлетворяющее следующим двум свойствам:

1. если <т 6 Т и т =<! <7, то г £ Г;

Список литературы диссертационного исследования кандидат физико-математических наук Подзоров, Сергей Юрьевич, 1999 год

Список литературы

[1] Cusin, R., The number of countable generic models for finite forcing, Fund.Math., 84, No. 3, 265 - 270, 1974.

[2] Ершов, Ю. Д., Теория нумераций, Москва, Наука, 1977.

[3] Ершов, Ю. Л., Проблемы разрешимости и конструктивные модели, Москва, Наука, 1980.

[4] Ершов, Ю. Л., Палютин, Е. А., Математическая логика, Москва, Наука, 1981.

[5] Feiner, L., Hierarchies of Boolean algebras, J. Symbolic Logic, 35, No. 3, 305 - 373, 1970.

[6] Гончаров, С. С., Автоустойчивость и вычислимые семейства кон-структивизадий, Алгебра и Логика, 14, No. 6, 647 - 680, 1975.

[7] Гончаров, С. С., Ограниченные теории конструктивных булевых алгебр, Сиб.Мат.Журн., 16, No. 4, 797 - 812, 1976.

[8] Гончаров, С. С., Проблема числа не автоэквивалентных конструк-тивизаций, Алгебра и Логика, 19, No. 6, 621 - 639, 1980.

[9] Гончаров, С. С., Вычислимые классы конструктивизаций моделей конечного типа, Сиб.Мат.Л{урн., 34, No. 5, 23 - 37, 1993.

[10] Гончаров, С. С., Эффективно бесконечные классы слабых конструктивизаций, Алгебра и Логика, 32, No. 6, 631 - 664, 1993.

[11] Гончаров, С. С., Счетные булевы алгебры и разрешимость, Новосибирск, Научная книга, 1996.

[12] Кейслер, Г., Чэн, Ч. Ч., Теория моделей, Мир, 1977.

[13] Кудинов, О. В., Автоустойчивая 1-разрешимая модель без вычислимого семейства Скотта 3-формул, Алгебра и Логика, 35, No. 4, 458 - 467, 1996.

[14] Lachlan, А. Н., On the lattice of recursively enumerable sets, Trans.Am.Math.Soc., 130, No.l, 1 - 36, 1968.

[15] Морозов, А. С., Счетные однородные булевы алгебры, Алгебра и Логика, 21, No. 3, 269 - 282, 1982.

[16] Нуртазин, А. Т., Сильные и слабые конструктивизации и вычислимые семейства, Алгебра и Логика, 13, No. 3, 311 - 323, 1974.

[17] Одинцов, С. П., Селиванов, В. JL, Арифметическая иерархия и идеалы нумерованных булевых алгебр, Сиб.Мат.Журн., 30, No. 6, 140 - 149, 1989.

[18] Пальчунов, Д. Е., Счетно-категоричные булевы алгебры с выделенными идеалами, Новосибирск, 1986 (Препринт N12 ИМ СО АН СССР).

[19] Pal'chunov, D. Е., Countably-categorical Boolean algebras with distinguished ideals, Studia Logica, 46, No. 2, 121 - 135, 1987.

[20] Пальчунов, Д. E., Теории булевых алгебр с выделенными идеалами, не имеющие простой модели, Труды Инст. Матем. СО РАН, 25, Новосибирск, 104 - 132, 1993.

[21] Роджерс, X., Теория рекурсивных функций и эффективная вычислимость, Москва, Мир, 1972.

[22] Сакс, Дж., Теория насыщенных моделей, Москва, Мир, 1976.

Работы автора по теме диссертации

[23] Podzorov, S. Yu., Restricted completeness of extended Boolean algebras, Siberian Adv. in Math., 7, No. 2, 98 - 123, 1997.

[24] Подзоров, С. Ю., Арифметическая сложность формульных подмножеств рекурсивных булевых алгебр, Вычисл.Сист., No. 161, 129 -140, 1998.

[25] Podzorov, S. Yu., Arithmetic complexity of first-order definable subsets of recursive Boolean algebras, Siberian Adv. in Math., 8, No. 1, 141 -150, 1998.

[26] Подзоров, С. Ю., Вычислимые классы конструктивизаций 2-конс-труктивизируемых моделей, Препринт No. 44, издательство НИИ МИОО НГУ, 1999.

[27] Подзоров, С. Ю., Рекурсивные представления однородных булевых алгебр, Препринт No. 45, издательство НИИ МИОО НГУ, 1999.