Содержание к диссертации
Введение
1. Предварительные сведения 17
1.1. Сведение произвольной конечной сигнатуры к сигнатуре графов 17
1.2. Расширения Маркера 18
1.3. Челночные отношения для линейных порядков 20
1.4. Простые булевы алгебры 22
2. Автоустойчивые относительно сильных конструктивизаций разрешимые и вычислимые модели 28
2.1. Разрешимые модели автоустойчивые относительно сильных конструктивизаций 28
2.2. Вычислимые модели автоустойчивые относительно сильных конструктивизаций 35
3. Автоустойчивые относительно сильных конструктивизаций модели естественных классов 65
3.1. Линейные порядки автоустойчивые относительно сильных конструктивизаций 65
3.2. Булевы алгебры автоустойчивые относительно сильных конструктивизаций 70
3.3. Структуры с двумя отношениями эквивалентности автоустойчивые относительно сильных конструктивизаций 81
Заключение 87
Список литературы
- Челночные отношения для линейных порядков
- Простые булевы алгебры
- Вычислимые модели автоустойчивые относительно сильных конструктивизаций
- Структуры с двумя отношениями эквивалентности автоустойчивые относительно сильных конструктивизаций
Челночные отношения для линейных порядков
В данной главе мы рассмотрим метод, позволяющий понижать сложность модели, сохраняя при этом необходимые теоретико-модельные свойства.
Метод понижения сложности моделей, описанный Е. Б. Фокиной в [38], основан на идеях С. С. Гончарова и Б. Х. Хусаинова [15] и использует понятия расширения предикатов и моделей, введeнные Д. Маркером в [62], и специального S—представления множеств.
Пусть о — конечная сигнатура, не содержащий функциональных символов, ШТ = (DT, Ро, , РтГ) — некоторая структура сигнатуры о. Предполагаем, что для каждого предиката Р этой структуры оба множества Р и DTS \ Р бесконечны, где s— местность предиката Р.
Определение 1.2.1. Пусть X — бесконечное множество, не пересекающееся с ШТ. 3-расширение Маркера этого предиката Р со спутником X, обозначаемое Рэх, определяется следующим образом. Предикат Р х имеет местность (s + 1) и удовлетворяет следующим условиям:
Теорема 1.2.2 ( [38]). Пусть d — произвольная арифметическая тъюрингова степень. Пусть ШТо, 9Лг,... — вычислимая последовательность о1!-вычислимых моделей сигнатуры а и а С а, такие, что носители 9Jfy моделей Dfy равномерно вычислимы, и все предикаты из а" = о \ о1 во всех моделях ШТг равномерно d-вычислимы. Пусть в каждой из ШТг для каждого Р Є о1 существует бесконечное вычислимое подмножество S p, равномерно вычислимое по I и Р , и каждый Р таков, что Р \ S p бесконечно. Тогда существует вычислимая последовательность ШТд,... 9Лг ,... d-вычислимых моделей, такая что каждая модель 9Лг d-вычислимо изоморфна ( Oli)a 3(a )y3, и для каждого I и для каждого R = Ру , где Р Є а , существует бесконечное вычислимое подмножество S R С R, равномерно вычислимое по I и R , и каждый R таков, что R \ S p бесконечно.
Теорема 1.2.3 ( [38]). Для каждой тъюринговой степени d, для произвольной модели 9JI (1)971 d-разрешима тогда и только тогда, когда ШСа \/ и (или) ШСа 3 d-разрешимы; (2) Т/г(9Я) =т ТЛ,(9Лз) =т Т7г(9Яу) 1.3. Челночные отношения для линейных порядков
Предварительные сведения о линейных порядках можно найти в [50,71]. Все рассматриваемые порядки являются линейными, поэтому будем иногда опускать слово линейный. Напомним, что запись х у означает, что х у и х ф у.
Пусть 21 — подпорядок линейного порядка 23. Говорят, что 21 является интервалом в 23, если для любых элементов аі, аг Є 21 и 6 Є 23 выполнено условие: если а\ b 0,2, то b Є 21. Пусть а и b — элементы 23 такие, что а Ь.Через [а, Ь[ обозначается интервал в 23, имеющий носитель {х Є 23 а х Ь}. Через {а} обозначаем одноэлементный интервал в 23, содержащий только элемент а. Если в 23 существует наименьший элемент, то будем обозначать его через О 8. Если {Ьп}пЄш — вычислимая последовательность линейных порядков, то всюду, где это имеет смысл, будем отождествлять сумму Ln с её естественным вычислимым представ-лением.
Если х,у — натуральные числа, то через {х,у) обозначается номер пары (х,у) в кан-торовской нумерации. Обозначение 3хір(х) понимается как “существует бесконечно много х таких, что р(х)”.
Для работы с вычислимыми ординалами, следуя [37, 11.7], вводим множество обозначений О с порядком о. Если а Є О, то через \а\о обозначается ординал, соответствующий обозначению а. Если а — вычислимый ординал, то, говоря о равномерной вычислимости по /3 а, будем считать, что зафиксировано некоторое а Є О, для которого \а\о = ex., и речь идет о равномерной вычислимости по Ь о CL.
Пусть а — счётный ординал. Для фиксированной счётной сигнатуры о определяем бесконечные Еа- и Па-формулы так же, как в [43, гл. 6]. Если о — вычислимая сигнатура, то также определяются вычислимые бесконечные формулы сигнатуры о. Строгое введение вычислимых бесконечных формул требует построения специальной системы обозначений, подобной системе обозначений для вычислимых ординалов. (Подробное изложение можно найти в [43, гл. 7].) Для каждого вычислимого ординала а можно построить множество обозначений и функцию, которая каждому обозначению сопоставляет Еа-формулу. Такие формулы образуют класс Е, вычислимых Еа-формул. Аналогичным образом строится класс Щ вычислимых Па-формул.
Если ШТ и 91 — модели сигнатуры а, то запись ШТ а 91 означает, что любое Па-пред-ложение, истинное в модели ШТ, является истинным и в 91. Формула 9Jt =а 91 означает, что 9Jt а 91 и 91 а ШТ. Если 91 — модель а, К — непустое семейство моделей с, то запись К а 91 означает, что любое Па-предложение, истинное во всех моделях из К, является истинным и в 91.
Простые булевы алгебры
Предложение 2.2.2. Пусть кп — вычислимая функция, и для последовательности ко-бесконечных множеств Ап С шкп, п Є ш эффективно по п строится Е2 -представление множества Ага и существует вычислимая последовательность вычислимых бесконечных множеств Sn С Ап, п Є ш, таких что Ап \ Sn бесконечно. Тогда существует вычислимая последовательность вычислимых бесконечных множеств Sn, п Є ш, и последовательность множеств Qn, п Є ш, таких что для любого п эффективно по п строится отношение Qn, котюрое задает однозначное Ъ2 -представление множества Ап и Ьп с_ ц/га, п Є ш, таких что Qn \ Sn бесконечно и для любого х из Sn набор (ж, 0, 0) лежит в Sn.
Доказательство. этого предложения аналогично доказательству леммы о представлении
Предложение 2.2.3. Пусть кп — вычислимая функция и для последовательности ко-бесконечных множеств Ап С ш п, п Є ш, равномерно по п строится вычислимая относительно оракула 0 п характеристическая функция множества Ап и существует вычислимая последовательность вычислимых бесконечных множеств Sn С Ап, п Є ш, а Ап \ Sn бесконечно. Тогда существуют последовательности множеств {Qn}neuj и {$п}пєш такие что {Sn}neuj — вычислимая последовательность вычислимых бесконечных множеств. Для любого п с условием f(n) 0 эффективно по п строится отношение Qn и вычислимая относительно 0 п 1 характеристическая функция для Qn, такая что т Є Є Ап =Ї (3x)(\/y)Qn(m,x,y); если же f(n) = 0, то Qn = Ап. Иными сло вами, для п, таких что Т\Щ U определяется Ъ2 -представление множества Ап, причём для таких п выполняются соотношения Sn С С Qn, п Є ш, Qn \ Sn бесконечно и для любого х Є Sn набор {х, 0, 0) лежит в Sn.
Приступим к доказательству основного результата о нижней оценке, построив требуемую вычислимую последовательность вычислимых моделей, из сводимости которой к универсальной нумерации получим точность установленной ранее оценки. При построении искомой вычислимой последовательности моделей будет использоваться идея конструкции понижения сложности арифметических отношений до вычислимых на основе метода из [15], но эта конструкция будет применяться внутри конструкции построения каждой искомой модели на каждом шаге её построения. Следуя [10,35] построим на множестве натуральных чисел структуру бинарного дерева и соответствующие функции и отношения: R(n) =; 2п + 2, L(n) =; 2п + 1; Н(п) = 0, если п = 0, Н(п) = [(п — 1)/2], если п 0, где [ж] обозначает целую часть числа ж; п — I, если п чётное, гг 0, Ь(п) ±=; и + 1, если п нечётное, п 0, 0, если гг = 0; /г(0) = 0, h(n + 1) = h(H(n + 1)) + 1; Еп =; {х I h(x) = n}; H(x, 0) = x, H(x, n + 1) = H(H(x, n)); /і(ж) x у ?=} II 1-й"(ж, гг) — y = 0. га=0 Нетрудно понять отношения между элементами с номерами, полученными с помощью определённых выше функций R(n), L(n), S(n), Н(п) и вершиной п: R(n) — номер вершины, лежащей справа и ниже вершины п при п 0; L(n) — номер вершины, лежащей слева и ниже вершины п при п 0; Н(п) — номер вершины, лежащей над вершиной с номером п при п 0, и i/(0) = 0; б (гг) — номер соседней вершины с вершиной с номером п под вершиной Н(п) при п 0. Функция /г(гг) вычисляет расстояние между вершинами п и 0, т. е. число предшествующих вершин в ветке над вершиной п. Из определения получаем, что множество Еп состоит из вершин на уровне п. Отношение х =4 у означает, что вершины хиу лежат в одной и той же ветке, а вершина х расположена под у. Определим теперь вычислимую функцию а, которая по элементам п множества натуральных чисел ш вычисляет номер а(п) вычислимой характеристической функции для бесконечного подмножества р(п) С N со следующими свойствами: (1) p(0) = ш, (2) (\/n 0)(n Є ш — ([((p(ri)U p(S(n)) = ip(H(n))] & [ip(n)r\ip(S(n)) = 0] & [ (ті) 0])). Потребуєм от этих разбиений, чтобы при любом п наименьший элемент из р(п) лежал в ip(L(n)), а следующий за наименьшим — в ip(R(n)). Это будет важно при построении искомых моделей. Заметим, что в этом случае множества р(п), п Є ш, порождают счётную безатомную булеву алгебру. Кроме того, если п =4 пг, то р(п) /?(m)) а если пит несравнимы относительно =4, то р(п) Л р(т) = 0.
Для дальнейших построений нам потребуются конструкции маркеровких расширений и понижения сложности арифметических отношений, описанные в главе 1.2. Для модели ШТ = (М, PQ,..., P m) сигнатуры а определим модель 3-расширения Маркера (У-расширения Маркера) предиката Pi со спутником Pi, равным X, которые обозначим через (3x)(Pi)0T ((Vx)(Pi)2t), взяв в качестве сигнатуры все константные и предикатные символы из о, кроме предиката Pi местности ПІ, и добавив вместо него одноместный новый предикатный символ А(РІ) И предикатный символ 3(Pj) (У(Pi)), соответственно определяющий 3-расширения Маркера (V-расширения Маркера); в качестве основного множества этой модели возьмём объединение основного множества модели ШТ с множеством X, а все предикаты и константы из о, кроме Pi, оставим теми же, что и в модели ШТ; в качестве предиката А(РІ) возьмём спутник Р для 3-расширения Маркера (V-расширения Маркера), т.е. множество X, а предикат 3(Pj) (У (Pi)) положим равным 3-расширению Маркера (V-расширению Маркера) для предиката Pi со спутником X.
Если а — слово в алфавите с двумя символами {V, 3} длины п, а А\, А2,..., Ап — бесконечные попарно непересекающиеся множества и не пересекающиеся с основным множеством модели 93, то определим преобразование модели с помощью маркеровских расширений, для пустого слова Л, пустого набора множеств 0 и предикатного символа Pi положив предикат (A(0))(Pj) Pj и модель (Л(0))(23, Pi), равной модели 93, а для слова а = Qf3, где Q Є {V, 3}, положив предикат (a(A\,A2,...,An))(Pi) =F± =F± QAU ((P)(AI, A2,..., An_i)(Pi)) и модель (a(A\, A2,..., An))(93, Pi), равной модели QA„((P)(A\, A2,..., An_i)(Pi))((f3(Ai, A2,..., An_i))(53, Pi)) 45 Построим искомую вычислимую последовательность моделей 530 551,..., 53га,... некоторой бесконечной сигнатуры а, для которой при каждом п выполняются следующие условия: если п Є А, то модель 53га сильно конструктивизируема, почти проста и автоустойчива относительно сильных конструктивизаций; если п ф. А, то модель 53га не является почти простой.
Зафиксируем вычислимую разнозначную нумерацию всех троек с3(п,х,у) из и3 на ш. Определим вычислимую последовательность бесконечных вычислимых множеств Вп, п Є ш, таких что для любого п выполняется (J (J Bc3(n,a;,2/) = OJ, а для любых различных пар (х,у), (x ,yf) множества Всз х и Д -ц/у) не пересекаются.
Для множества А из Пз(0ш) рассмотрим представление из леммы 2.2.3 со следующим свойством: существуют вычислимые функции р(п,х,у) и q(n,x,y), для которых п Є А тогда и только тогда, когда (Эх)(Эу)(р(п,х,у) Є 0ІУП Х У , причём если существует х, для которого (Эу)(р(п,х,у) Є 0ІУП Х У , то для всех х уЁ х не выполняется условие (Эу)(р(п,х ,у) Є 0іУп х У у Без ограничения общности можно считать, что при всех п,х,у выполняется неравенство q(n,x,y) q(n,x,y + 1).
Вычислимые модели автоустойчивые относительно сильных конструктивизаций
Для доказательства полноты полученной теории рассмотрим произвольные две её насыщенные модели ОТ, ОТ мощности ш\ и покажем, что они изоморфны. Изоморфизм между стандартными элементами автоматически устанавливается отображением константы с 0 Є ОТ в константу CQ Є 91", поскольку в каждой из моделей 91 и 91" элементы, выделенные предикатами М (х), с точностью до изоморфизма определяются связью с константами Q, предикатами Е(х,у) и E (x,y,z). Пусть т ,т Є М для некоторых i,j Є ш. В зависимости от действия предиката Е (х ,т ,т ) для различных х определяется точный вид цепочки из предикатов Е(х,у), в которой участвуют элементы из М, связанные с элементами т ,т . Элементы, выделенные формулой В(х), однозначно связаны с элементами из М(х) цепочкой конкретной длины, определённой предикатами Е(х, у). А нестандартные элементы образуют континуум бесконечных цепей. Могут появляться следующие нестандартные бесконечные цепочки (здесь для удобства будем использовать обозначение Е(а, b) =F± а — b и полагать т Є М, Lt-\-i Є В, і Є UJ):
Цепи вида (4) автоморфны в своих моделях, а значит можно произвольным образом отображать их друг в друга. То же верно для цепей вида (3а) и (3b). В цепях вида (1) и (2) присутствует элемент из М, который, в свою очередь, однозначно связан с нестандартным элементом из М предикатом Е\. При этом каждый нестандартный элемент из М связан предикатом Е\ c континуумом цепей как вида (1), так и вида (2). Таким образом, можно отображать нестандартные элементы из [М ]эт в нестандартные элементы из [М ]эт и соответствующие им цепи произвольным образом: цепи вида (1) в цепи вида (1), а цепи вида (2) в цепи вида (2). Кроме того, возможны нестандартные элементы пятого типа, представляющие собой бесконечные цепи из предикатов S2(х,у). Цепи такого вида автоморфны в своих моделях и могут произвольным образом отображаться друг в друга. Таким образом, Т)(У1 п) рекурсивно аксиоматизируема и полна, поэтому разрешима. Следовательно, в случае, когда исходная модель 9?tra сильно конструктивизируема, полученная из неё модель 9Тга также сильно конструтивизируема.
Опишем множество полных формул теории Th (91 , с), где с — конечный набор элементов из М . Для элементов, выделенных предикатом М , такими будут являться полные формулы Th (ШТП, с), переписанные в терминах новых предикатов, т.к. действия предикатов Е\,Е ,Е однозначно определяются действием предикатов Pi и Qj. Изоморфизм, установленный между любыми двумя кортежами, удовлетворяющими полной формуле теории Th(5Dtre,c), также установим на элементах из М теории ТЪ.(У1п,с). Элементы, выделенные предикатом М, с точностью до изоморфизма определяются элементами из М , с которыми они связаны предикатом Е\, длиной цепочки из предикатов Е, в которой они участвуют, элементом из М, с которым они связаны цепочкой из предикатов Е и константой, которой оканчивается цепочка. Таким образом, полные формулы для таких элементов могут быть получены из полных формул для элементов, выделенных предикатом М . К примеру, пусть ф(х,у) — полная формула теории Th (Уіп, с), истинная на элементах из М . Тогда для произвольного а, такого что 9Т„ = ЗЬМ (Ь) & М (а) & ф(а, Ь), можно выписать полную формулу для любого элемента а, такого что Уіп = М(а) &Еі(а,а) и а связан цепочкой из предикатов Е c элементом 6, для которого 9Тга = М(Ь) & М (Ь) & Ei(b, b) & ф(а, b).
Допустим, требуется выписать полную формулу для элементов, связанных с элементами а Є М и b Є М , из которых выходит цепь длины 2п + 3, оканчивающаяся константой 1. Тогда
Если модель (9Лга, с) является почти простой, то для всевозможных кортежей модели (9Тга,с), состоящих из элементов, выделенных предикатом М , существуют полные формулы, их реализующие. Таким образом, для любой пары элементов, выделенных предикатом М , существует полная формула в теории Th (9Тга, с). Переписав всевозможные двухместные полные формулы, как описано выше, для различных длин цепей из предикатов Е и различных констант, которыми оканчивается цепь, получим множество полных формул для всех элементов из М. Полные формулы для элементов, выделенных предикатом S(x), имеют следующий вид: ф(х) F± Зх\... 3xk & S(xi) & Six) & S(co, X\) & & S(xi,Xi+i) $z S(xk,x) — [lsCisifc IsCisCfc-l искомая для Ck+i. Полные формулы для констант имеют следующий вид: ф(х) F± (х = 1) — искомая для константы 1, и т. п. Остаются элементы, выделенные формулой В(х). Эти элементы с точностью до изоморфизма определяются местом и длиной цепочки, в которой они участвуют, элементами из М, с которыми они связаны этой цепочкой, а также константой, которой заканчивается цепь. Например, пусть элемент х, для которого (9Тга, с) = В(х), находится на к-м месте цепи длины 2гг + 3, оканчивающейся константой 1, и связан цепочкой с элементами из М, которые удовлетворяют полной формуле ф(х,у); полная формула для х имеет следующий вид: ф{х)
Структуры с двумя отношениями эквивалентности автоустойчивые относительно сильных конструктивизаций
Опишем вспомогательную конструкцию, построения модели (д по модели 21, такой что 21 = 2І. Носителем Лд является фактор множество 21 по Е0, \щ\ = \%І,\/Е0. Будем использовать обозначение [a] =F± а/Ео для элементов из %. Отношение на 21 задаётся следующим образом. a, b Є 21, 21 = [а] [Ь] - = 21 \= lE0(a,b)&3x3y3z[(y ф z)&E0(a, x)&E0(b, y)&E0(b, z)&Ei(x, y)&Ei(x, z)\.
Пусть 2І является насыщенной моделью мощности ш\ теории FD(f&z). Полагаем, что 2І = { іао! Ш\}. Построим по 2І структуру Ищ . 21 = FD(), в силу аксиомы 10 . Покажем, что 21 является насыщенной моделью теории FD(). Достаточно показать, что если тип р сигнатуры { } U С совместен с FD(), то он реализуется в 21 , где С - не более чем счётное подмножество І&д . Заметим, что для любых а Є и формулы ф, если = ф(а), то 2І = ф (а), где ф (х) получена из ф(х) способом, описанным в аксиоме 9. Тогда еслир(ж) совместен с FD(), тор (ж) совместен с Тщ , следовательно, р(х) реализуется в gi ,
Пусть 2І и 2І - две насыщенные модели мощности ш\ теории Т %. Построим по ним модели (д и 21 соответственно. 21 и 21 изоморфны, в силу того, что они являются насыщенными моделями мощности ш\ полной теории FD(). Рассмотрим изоморфизм / : 21 — 21 Построение изоморфизма между 21 и 21 осуществляется по шагам. Сначала опишем шаги построения, соответствующие непредельным ординалам. Полагаем, что /о = 0.
Допустим, что уже построен изоморфизм fa между X С 2ІІ и У С 2І . Опишем шаг а + 1, для чётного ординала а. Выбираем элемент а Є 21 \ X. В силу аксиом существуют единственная пара b,z Є 2І \ Y, b ф z, такая что 2l = Ei(a,b)&Ei(b,z). Для удобства будем полагать, что 2l = Eo(b,z)& lEo(a,b). Тогда 21 = [а] [Ь] и, следовательно, 21 = /([а]) /([6]). Значит в 21 лежат элементы а Є f([a]),b ,z Є f([b]), которые реализуют над Y тот же тип, что и a, b, z над X. Полагаем, что fa+i = /aU {(a, а ), (6, b ), {z, z )}. В случае, если а - нечётный, аналогичным образом переводим элементы из 2І \Ув 2ІІ \ X. Если 8 - предельный ординал, то полагаем, что fs = U fa. Ясно, что / = U fa является искомым изоморфизмом между 21 и 21 . Тогда Т% является полной теорией 2І, следовательно FDi z)- разрешима, как полная аксиоматизируемая теория.
Заметим, что если структура 21, изоморфная 2І, разрешима, тогда разрешимой является и структура (д. Таким образом можно установить, что сильно конструктивизируема тогда и только тогда, когда 2І сильно конструктивизируема.
Теперь покажем, что автоустойчива относительно сильных конструктивизаций тогда и только тогда, когда 2І автоустойчива относительно сильных конструктивизаций.
Пусть автоустойчива относительно сильных конструктивизаций и 211 = 2І2 — 2І, где 2li и 212 разрешимы. Тогда 1 и щ разрешимы, и существует вычислимый изоморфизм / : ХІ2і1 — д2. Построим / : 2li — 2І2 следующим образом. Пусть [а], [6] Є щ и 211 = ([а] [6]). Тогда элементы а ,Ь ,с Є 211 такие, что а Є [а], 6 , с Є [b], b1 ф d ж 211 = Еі(а , 6/)& і(Ь/, С ), переводим в элементы а",Ь",с" Є 2І2 такие, что а" Є /([а]), 6", с" Є /([6]), 6" т с" и 2І2 Н Е\(а", b")&Ei(b", с"). То есть полагаем, что f (a ) = a", fib1) = b", / (с ) = с". Полученное отображение / является вычислимым изоморфизмом, следовательно модель 2І автоустойчива относительно сильных конструктивизаций.
Теперь пусть 2І автоустойчива относительно сильных конструктивизаций и і = 2 — , где і и 2 разрешимы. Зафиксируем вычислимый изоморфизм д : 211 —) 2І2. Определим вычислимый изоморфизм д между і и 2. Для любых а Є 1, b Є г полагаем, что /(а) = 6 - = существует к Є ш, такой, что д({а,0)) = {b,k). Следовательно модель автоустойчива относительно сильных конструктивизаций.
Таким образом, можем построить по последовательности {І}ІЄШ, построенной в доказательстве теоремы 3.1.1, последовательность моделей {( ,)І}ІЄШ, такую, что для любого номера j Є ш модель j сильно конструктивизируема и автоустойчива относительно сильных конструктивизаций тогда и только тогда, когда i z)j сильно конструктивизируема и автоустойчива относительно сильных конструктивизаций.
Спектром степеней счётной модели ШТ вычислимого языка (DgSp(?Dl)) называется множество степеней представлений ШТ. Пусть d— тьюрингова степень. d-вычислимой размерностью вычислимо представимой структуры ШТ является количество вычислимых представлений структуры ШТ с точностью до d-вычислимого изоморфизма.
Следствие 3.3.1. Пусть -вычислимый линейный порядок. Для любой тъюринговой степени d, 2І имеет такую же d-вычислимую размерность, что и .
Доказательство. Пусть і, 2 – вычислимые представления . Покажем, что XIі =cd 2 = 2Іі — d 2І2. Пусть / : XIі — ХІ2 является d-вычислимым изоморфизмом. Определим отображение фо : — {{{Ь,і)\і Є о;}16 Є } так, что фо(а) = {{Ь,і)\і Є ш} - = = (а = 6). Построим отображение ф : 2ІХ — 2І2 следующим образом. Если а\,Ь\ Є і и 1 = (а\ b\). Тогда элементы Xi,yi,Zi Є 2ІХ такие, что Х\ Є "0о( і), Уъ zi Є фо(Ьі), У\ ф Z\ и 2ІХ = Е\(хі, уі)& і(жі, Zi), переводим в элементы Жг, 2/2,- 2 Є 2І2 такие, что Жг Є фо(/(а\)), У2,%2 Є фо(І(Ьі)),У2 Ф %2 и 2І2 = Еі(х2, У2)&Еі(х2, 2 2). То есть полагаем, что 0(Жі) = Ж2, ( (г/х) = у2, 0( і) = - 2. Полученное отображение 0 является d-вычислимым изоморфизмом. Получаем, что dimd(%l,) dimd(). Покажем, что 211 = 2t2 = Лі =d 212, где 2ti, 2І2 – вычислимые представления струк туры 21. Зафиксируем d-вычислимый изоморфизм g : 211 — 2І2. Построим d-вычислимый изоморфизм / между щ и (д2 следующим образом. Для любых [а] Є 2 , [b] Є д2 по лагаем, что (/([а]) = [Ь] - = существуют а Є [а], Ь Є [6], такие что д(а ) = Ь . Тогда, dimd(%l,) dimd() П Следствие 3.3.2. DgSp(2(.) = DgSp(). Доказательство. Структура 2І строится по структуре вычислимым образом, следовательно, для произвольного представления структуры , выполнено degi z ) deg( ). Заметим, что рассматриваемый линейный порядок является автоморфно нетривиальным, в силу того, что он бесконечен. В работе [59] доказано, что спектр степеней автоморфно нетривиальных структур замкнут вверх, следовательно, существует представление 21 структуры 2І, такое, что deg(%l ) = deg( ). Следовательно, DgSp(2t.) С DgSp().