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

Министерство общего и профессионального образования РФ Новосибирский Государственный университет

Вычислимость и конструктивность в ограниченных фрагментах теорий

01.01.06. - математическая логика, алгебра и теория чисел

Диссертация на соискание ученной степени кандидата физико-математических наук

На правах рукописи УДК 510.5 + 510.67 + 512.563

Подзоров Сергей Юрьевич

Научный руководитель

член-кореспондент РАН доктор физико-математических наук профессор С.С.Гончаров

НОВОСИБИРСК-1999

Содержание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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

Во второй и третьей главах содержатся результаты, напрямую относящиеся к классической проблеме алгоритмической размерности моделей. Хотя, как показал С.С.Гончаров [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)) вычислимы, говорят о разрешимой (тг-разрешимой) модели. Эквивалентность этих д