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

Ч ■

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

На правах рукописи

Хисамиев Асылхан Назифович

Определимость в наследственно конечных допустимых множествах

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

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

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

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

ОГЛАВЛЕНИЕ

Введение .................................................3

Глава 1. Е- нумерация и Е - определимость в наследственно конечном допустимом множестве................15

§1. Е- нумерация и критерий Е - определимости в НР(Ш) над моделью Ш, допускающую Е- нумерацию......16

§2. Нумерация конечно порожденных алгебр...........25

§3. Условие существование Е- нумерации..............26

§4. Некоторые применения............................29

§5. Одно условие Е- определимости модели в

наследственно конечном допустимом множестве .... 30

§6. О внутренней перечислимости линейных

порядков .......................................... 35

Глава 2. Сильная Ах- определимость модели в допустимом

множестве ......................................47

§7. В- модели и критерий А\- определимости модели в наследственно конечном допустимом множестве ____47

§8. Абелевы р- группы................................51

§9. Булевы алгебры ...................................61

Литература

67

Введение

Попытки математиков решить трудные алгоритмические проблемы привели к необходимости уточнения понятия алгоритма. В работах Поста, Тьюринга, К лини, Маркова были даны точные определения этого понятия. Эти уточнения относятся только к алгоритмам, входные и выходные данные которых можно считать натуральными числами. В то же время в математике известны алгоритмические проблемы, которые связаны с более широким классом объектов (действительные и комплексные числа, произвольные поля и т.д.). Для охвата этих алгоритмических проблем были предложены различные обобщения обычного понятия алгоритма. Одним из таких важных обобщений является понятие Е- определимости в допустимом множестве над данной моделью. При таком обобщении оказались справедливыми аналоги многих важных теорем обычной теории алгоритмов.

Наименьшим допустимым множеством над моделью Ш является наследственно конечное допустимое множество НР(9Л). Ю.Л. Ершовым в [4] введено понятие Е- определимой модели в НР(Ш), которое является обобщением понятия кон-структивизируемой модели. Например, справедливо следующее утверждение [6]: если модель Ш конструктивизируе-ма, то модель Е1- определима в НР(Ш) тогда и только тогда, когда конструктивизируема. Поэтому представляет интерес исследование Е- определимых моделей в

ЯР(Ш1).

Основные результаты, полученые в этой области, приведены в монографиях Ю.Л.Ершова [4] и Дж.Барвайса [23]. Ю.Л.Ершов [7] получил интересный критерий Е- определимости несчетной модели в наследственно конечном допустимом множестве НР(Ь) над плотным порядком Ь без концов. Отсюда, например, следует, что поле комплесных чисел Е- определимо в НР(Ь) над плотным линейным порядком без концов мощности континиум. В то же время поле действительных чисел Я не Е-определимо в НР(Ь) ни для какого плотного порядка.

Диссертация посвящена исследованию Е- определимости модели в наследственно конечном допустимом множестве. Она состоит из двух глав и девяти параграфов. Перейдем к изложению основных результатов диссертации.

В первой главе введено понятие внутренне перечислимой модели и получен критерий Е- определимости модели в для внутренне перечислимой модели Ш.

Рассматриваются только не более, чем счетные модели конечных сигнатур. Говорят, что алгебраическая система Шх = =< М\, Р"1,Р™3 > сигнатуры о"1 =< Р1,..., Р5 > £- определима в допустимом множестве 21 [4,стр. 190], если существует система Е-формул

такая, что

Х^чРЫ, п ^ 7?и[ж0, х,] П X2 есть отношение конгруэнтности на алгебраической системе

где

Р? = Ф*[х0, ...,®пч_1] П Хт\ 1 < » < а,

и система изоморфна фактор системе Ш[/г] и

|?л[®0,®1] ПХ2 = Х2\ча[а0,а:1],

ФТ^ЕЖО, П Xя4 =

Если в этом определении ср(х) также будет формулой, то будем говорить, что модель Ш\ А1-определима в допустимом множестве 21. Если кроме того, эквивалентность г] является единичной, то будем говорить, что модель Ш\ сильно А\- определима в допустимом множестве 21.

Пусть Ш2 =< М2,<т2 > модель сигнатуры сг2 =<

>• Если 8-множество, то через РР(8) обозначим множество всех конечных подмножеств множества Б. Наследственно конечное допустимое множество Я.Р(9#2) над моделью Ш12 есть модель

< м2 и я-Р(М2), и\ е, ЯъЯк >,

где предикат и выделяет множество М2, элементы которого называют прэлементами, а множество Я.Р(М2) определено так:

ЯР( 0) = 0

Я^м2(гг + 1) = РЯ(М2 и Я^м2(гг)) Я^(М2) = и Я^м2(п)

Известно [4,23], что множество ш всех натуральных чисел в НР(Ш) выделяется Ао- формулой. Отображение и множества ш на основное множество М модели Ш1 называется нумерацией модели 9Я, а пара (ЯЙ, ту)- нумерованной моделью. Через г)у обозначим нумерационную эквивалентность, то есть т]и = {< п,т > | ип = гут}. Нумерацию V модели Ш можно рассматривать, как функцию и : со —у НР(Ш) в НР(Ш).

ОПРЕДЕЛЕНИЕ 1.1 Если нумерация V модели Ш является Е- функцией в НР(Ш), то V называется Е- нумерацией модели Ш. Если существует Е- нумерация V модели Ш, то 9Л называется внутренне перечислимой или Е-перечислимой.

Пусть ту\)- нумерованная модель сигнатуры Через Ш^ обозначим модель < о;, Р1,Р3 >, где предикаты Р; определяется так:

Пусть (Ш2, нумерованная модель сигнатуры сг2 =< (Эь

(¿к >. Если предикаты Р^ 1 < г < «з модели Ш^1 рекурсивны относительно предикатов 77^, модели Што говорят, что нумерованная модель ь>\) рекурсивна относительно нумерованной модели (ЯОТг, ^2)- Модель Шх называется рекурсивной относительно нумерованной модели (ЙЯ2? если существует такая нумерация модели ЯЛ], что пара Р\) рекурсивна относительно пары ^2)- Анологично определяются понятия рекурсивно перечислимости модели относительно нумерованной модели (Я#2,

Основным результатом первой главы является

ТЕОРЕМА 1.1 Пусть не более, чем счетные

модели соответственно сигнатур 01, <72 и V2-Е- нумерация модели Ш2. Тогда модель Е- определима в НР(Ш2) тогда и только тогда, когда модель рекурсивна относительно пары (9^2,^2).

ОПРЕДЕЛЕНИЕ 1.2 Если в определении Е- определимости модели Ш\ б допустимом множестве 21 отсутствуют формулы 77*, Ф*,Ф*, то будем говорить, что модель дЯ\ квази Е- определима в 21.

Анологично теореме 1.1 доказывается

ТЕОРЕМА 1.2 Пусть Шг,Ш2~ не более, чем счетные модели соответственно сигнатур 0"1,(Т2 и Vнумерация модели ЭД12. Тогда модель квази-'Е- определима в #Я(Ш12) тогда и только тогда, когда модель рекурсивна перечислима относительно пары (Ш12,^2).

Из доказательства теоремы 1.1 получаем

СЛЕДСТВИЕ 1.1 Пусть не более, чем счетные

модели и Ш12- внутренне перечислима. Тогда модель Е- определима в НР(9Л2) тогда и только тогда, когда она Ах- определима.

Из теоремы 1.1 следует, что следующие вопросы представляют интерес:

1. Какие модели допускают Е- нумерации?;

2. Какие нумерации данной модели будут Е- нумерациями? В §2 главы 1 изучаются эти вопросы для конечно порожденных алгебр. Доказано

ПРЕДЛОЖЕНИЕ 2.1 Стандартная нумерация конечно порожденной алгебры является её Е- нумерацией.

Отсюда и теоремы 1.1 получаем

СЛЕДСТВИЕ 2.2 Пусть 21- конечно порожденная алгебра, ар- её стандартная нумерация. Тогда модель Ш1 Е-определима в тогда и только тогда, когда модель

ЯЛ рекурсивна относительно пары (21, г/).

В §3 даны условия для того, чтобы модель Ш была внутренне перечислимой. Напомним, что модель называется жесткой, если она не имеет автоморфизмов, отличных от тождественного. Если существует такое обогащение Ш' модели Ш конечным

числом констант, что модель Ш1' является жесткой моделью, то модель Ш назовем /-жесткой моделью.

ПРЕДЛОЖЕНИЕ 3.2 Если модель Ш внутренне перечислима, то Ш /-жесткая модель.

Допустим, что для модели Ш конечной сигнатуры выполнено условие: существует такая конечная последовательность элементов а =< ах,...,ап >, аг Е что для каждо-

го элемента р Е М существует Е- формула (рр{уо) сигнатуры а* =< а, 0, Е,а > с одной свободной переменной г>о, которая выделяет элемент р в то есть в истинна фор-

мула 3\уо(рр(уо) А (рр(р) и множество Ф = {(рр\р Е М} рекурсивно перечислимо. Тогда модель Ш назовем Ф-моделью.

ПРЕДЛОЖЕНИЕ 3.3 Счетная модель внутренне перечислима тогда и только тогда, когда она является Ф-моделью.

В §4 даны ответы на следующие вопросы С.С. Гончарова для случая наследственно конечных допустимых множеств над внутренне перечислимой моделью

1. Если суператомная булева алгебра 93 Е- определима в допустимом множестве 21, то будет ли её ординальный тип Е-определим в 21?

2. Если абелева р-группа С Е- определима в допустимом множестве 21, то будет ли Е-определим её ульмов тип в 21?

ТЕОРЕМА 4.3 Пусть счетная суператомная булева алгебра и о(93)- её ординальный тип, Ш12 внутренне перечислимая модель. Если булева алгебра Е- определима в допустимом множестве #"Р(Ш12)? то её ординальный тип о(93) также Е-определим в НЕ(Ш2).

ТЕОРЕМА 4.4 Пусть А- счетная редуцированная абе-лева р-группа, г(А)- её улъмов тип и 9Й2 внутренне перечислимая модель. Если группа А Е- определима в допустимом множестве НР(Ш2), то и её улъмов тип т(А) Е-определим в НР(Ш2).

В §5 главы 1 приведено еще одно условие Е- определимости модели в наследственно конечном допустимом множестве. Здесь через ш будем обозначать множество конечных ординалов, а через а;* = {0*,1*,...}- множество всех натуральных чисел. Пусть 5*- подмножество множества ш* и гв, : ш ш* определено как гс?(п) = п*. Будем говорить, что модель ОТ рекурсивна относительно множества 5*, если модель 91 рекурсивна относительно нумерованной модели (< а;*, 5* >, гсГ). Для нумерованной модели (Ш, р) через Ш* обозначим модель, основным множеством которой является множество и*, а отображение гс? : ш ш* есть изоморфизм моделей Ши и ШТ*. Пусть модель, которая получена из модели Ши добавлением в сигнатуру операции /- прибавление 1.

Следующее предложение дает необходимое условие Е- определимости.

ПРЕДЛОЖЕНИЕ 5.4 Пусть модель 91 Е- определима в наследственно конечном допустимом множестве НР(Ш) над моделью Ш1. Тогда для любой нумерации V модели Ш модель 91 рекурсивна относительно пары г/).

ТЕОРЕМА 5.5 Пусть 5- подмножество конечных ординалов и для модели Ш выполнены условия:

1°. Ш рекурсивна относительно множества 5* =

{¿Ф е 5}

2°. Множество 5 Е- определимо в допустимом множестве НР(Ш).

Тогда модель Е- определима в ЯР(9Л) тогда и только тогда, когда она рекурсивна относительно множества 5*.

Дано одно применение этой теоремы и показано, что условие 2° теоремы существенно.

В последнем параграфе главы исследуется вопрос какие линейно упорядоченные множества внутренне перечислимы. Для этого установлены критерии экстенсиональной эквивалентно-стей наследственно конечных допустимых множеств, представляющих самостоятельный интерес. Ершов Ю.Л. в [4,стр. 196] получил критерий для достаточно насыщенных моделей когда элементы /¿о? из реализуют один и тот же тип. Оказывается, что этот критерий справедлив для любой модели Ш1, если ограничится рассмотрением только 1-типов. Пусть ЯР(Ш1) модель сигнатуры и Ь элемент из НР(Ш). Множество 3-формул сигнатуры <71 истинных в ЯР(9#) на элементе Ь назовем 1-типом элемента Ь, то есть

*НР(Ж)(Ь) = {фМ1 3-формула и |= Ф(й)}.Пусть

п е СО, ЯР(п) = ЯР({0,1, - 1}), Ш - модель, ^ £ Е ЯР(п), р Е Мп. Определим элемент х(р) Е ЯР(М) следующим образом. Пусть \р : п М определенно так:

=ри г< п, р =<Ро,...,Рп-1 > •

Отображение Хр однозначно продолжается до А^ : НР(п) —> ЯР(М) так, что

А£({а0, ...а*}) = (А^(а0),

для любого множества Е ЯР(п). Тогда х(р) =

= ^(х).

ТЕОРЕМА 6.6 Если из ЯР(ЯЯ), то 1-типы

и ^Зёщял)^1) совпадают тогда и только тогда,

когда существуют такие п Е и, х Е НР(п) и р,д £ Мп, что /¿о = Ь = и ^(р) =

Основным результатом §6 является

ТЕОРЕМА 6.7 Любой бесконечный линейный порядок не внутренне перечислим

В частности, любой счетный ординал не является внутренне перечислимым.

По предложению 3.2 условие /-жесткости модели является необходимым условием для ее внутренне перечислимости, а результат о ординалах, показывает, что оно не является достаточным.

В главе 2 исследуется сильная А\- определимость модели Ш. В дальнейшем под словом " А\- определимость" будем понимать "сильную А\- определимость". Данная глава состоит из параграфов 7,8 и 9.

В §7 введено понятие В- модели и дано условие А\- определимости модели 91 в допустимом множестве НР(9Л) над В-моделью. Напомним определение функции вр(х) в НР(Ш) [23].

^{гг}, если х Е М

11 {зр(у)\у € ж}, если х е ЯР(М)\М

уех

ОПРЕДЕЛЕНИЕ 7.3 Пусть для модели Ш выполнено условие: для любого конечного непустого множества Мо С М существует такое конечное подмножество М0* С М, содержащее Мо, что для любого конечного подмножества М\ ^ МЦ модели Ш найдется такой автоморфизм / модели Ш, что / действует тождественно на Мд и ф М\. Тогда модель Ш назовем В- моделью.

ЛЕММА 7.5 Пусть модель Я1 = Ш х 91 и Ш является В- моделью. Пусть конечное подмножество Мо С Ми модель £; такие что выполнены:

1 С ЯР(21),

2°. для любого автоморфизма } модели НЕ(21) справедливо условие: если / действует тождественно на множестве Мд х А/", то / тождественней и на Ь.

Тогда множество носителей

вржЬ = {х Е М|3у Е Е 5р(г/) Згг Е = (ж,гл))} конечно.

ПРЕДЛОЖЕНИЕ 7.8 Пусть ^ = Ш х % Ш- В- модель, £- А-определимая модель в допустимом множестве ЯР(21) и множество параметров в формулах, определяющих £ есть ао, Предположим, что множество Мо = < ^ модель £ удовлетворяют условию 2° леммы 7.5. Тогда существует такое конечное подмножество М' С М, что модель £ А\- определима в ЯР(2I'), где 21' = ШГ х 9Г

ПРЕДЛОЖЕНИЕ 7.9 Пусть модели 21 и £ такие же как и в предложении 7.8. Тогда если модель конструк-тивизируема, то и модель £ также конструктивизируе-ма.

Из предложении 7.8 и 7.9 получаем следующий критерий определимости жесткой модели.

СЛЕДСТВИЕ 7.7 Пусть модель 21 = Ш х % Ш- В- модель, а 91 конструктивизируемая модель. Тогда жесткая модель £ Д1- определима в ЯР(21) тогда и только тогда, когда £ конструктивизируема.

В §8 доказывается, что любая счетная редуцированная абе-лева р-группа является В-моделью. Отсюда и следствия 7.7 вытекает

ТЕОРЕМА 8.8 Пусть 21 не более, чем счетная абеле-ва р- группа. Тогда жесткая модель £ А\- определима в НР(Щ тогда и только тогда, когда £ конструктиви-зируема.

СЛЕДСТВИЕ 8.10 Существуют абелева р- группа А и допустимое множество *В такие, что группа А Аопределима в но её ульмов тип т(А) не А\- определим в *В.

Следствие 8.10 отрицательно решает вопрос для случая сильной Дх- определимости.

В последнем параграфе главы 2 доказано, что любая счетная булева алгебра является В-моделью. Отсюда и следствия 7.7 вытекает

ТЕОРЕМА 9.10 Пусть 21 не более, чем счетная булева алгебра. Тогда жесткая модель £ А\- определима в Д\Р(21) тогда и только тогда, когда £ конструктивизируема.

СЛЕДСТВИЕ 9.12 Существуют счетная суператомная булева алгебра 21 и допустимое множество Ъ такие, что алгебра 21 Д1- определима в $3, но её ординальный тип о(21) не А\- определим в Ъ.

Таким образом, в диссертации введены понятия внутренне перечислимой и В-моделей, получены критерии Е и Д1- определимости модели в наследственно конечном допустимом множестве над внутренне перечислимой и В-моделями. Эти критерии использованы для решения вышеупомянутых вопросов С.С.Гончарова. Найдены условия внутренней перечислимости модели. Дано необходимое и достаточное условие для того, чтобы два элемента из наследственно конечного допустимого множества реализовали один и тот же 1-тип. На основе этого

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

Содержание диссертации опубликовано в [17-22] и докладывались на Международных конференциях "Мальцевские чтения" в 1997 и 1998 годах, на Первом съезде математиков Казахстана, на конференции по математике, посвященной памяти А.Д.Тайманова, на XXXVII научно-технической конференции Восточно-Казахстанского технического университета, на семинарах " Теория конструктивных моделей" Новосибирского Государственного университета, "Теория алгоритмов" Алма-тинского Государственного университета, " Математическая логика" Восточно-Казахстанского технического университета.

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

Глава 1

Е- нумерация и Е- определимость в наследственно конечном допустимом множестве

Ю.Л.Ершовым в [4] введено понятие Е- определимости модели Ш в допустимом множестве 21 и найден критерий [7] Е-определимости несчетной модели Ш в допустимом множестве ЯР(£) над плотным линейным порядком Ь без концов. В данной главе введено понятие Е- нумерации модели 91 и для модели 91, допускающую такую нумерацию, получен критерий Е- определимости счетной модели Ш в допустимом множестве ЯР(91) над моделью 91. Отсюда следует, что для Е- нумерованной модели 91 справедливы:

1. Модель Е- определима в ЯР(91) тогда и только тогда, когда она определима в ЯР(91);

2. Если абелева р-группа(булева ал�