Содержание к диссертации
Введение
1. Предварительные сведения 17
1.1. Теория вычислимых моделей 17
1.2. Счетные булевы алгебры 25
1.3. Булевы алгебры с выделенными эндоморфизмами 30
2. Уровни автоустойчивости булевых алгебр 32
2.1. Гиперарифметические уровни автоустойчивости для почти суператомных булевых алгебр 32
2.2. Степени категоричности суператомных булевых алгебр 41
2.3. Аз-категоричность булевых алгебр 46
3. Алгоритмические свойства булевых алгебр с выделенными эндоморфизмами 57
3.1. Конструктивизируемость булевой алгебры *8(о;) с выделенным автоморфизмом 57
3.2. Степени категоричности булевой алгебры 93(ш) с выделенным автоморфизмом 72
3.3. Вычислимые нумерации класса булевых алгебр с выделенными эндоморфизмами 77
Заключение 89
Список литературы 91
- Счетные булевы алгебры
- Булевы алгебры с выделенными эндоморфизмами
- Аз-категоричность булевых алгебр
- Степени категоричности булевой алгебры 93(ш) с выделенным автоморфизмом
Счетные булевы алгебры
Ишестно, что в 1900 году инженер Бертье Де Лачард из Франции привез в Ялту 2 куста фейхоа. Примерно в то же время она появилась в Сухуми (3. И КЬроткова, 1937).
Первое сообщение в литературе о фейхоа, кав: о ценном гоюдовом растении, подающем надежды на освоение в русских субтропиках, сделано было ботаником профессором Ю.Н Вороновым в 1903 году. К тому времени растения, произрастающие в Сухумском ботаническом саду, уже вступили в пору плодоношения. В эти годы другая партия саженцев фейхоа была получена АН Введенским из Германии и посажена в его саду в местности «Сїпюп» около Сухуми.
Первая плантация фейхоа, насчитывающая 121 куст была заложена в 1915 году в городе Сухуми инженером Грибоедовым (3. И КЬроткова, 1937).
Помимо Абхазии, позже фейхоа продвинулась в другие районы Черноморского побережья Кавказа и Крыма В субтропической зоне России первые посадки фейхоа были сделаны в 1930 году на территории Сочинской опытной станции субтропических и южных плодовых культур. Эти растения прекрасно сохранились до сегодняшнего дня и в возрасте более 70 лет дают регулярные урожаи (рис. 3).
Динамика пластических веществ в весенний и летний периоды носит иной характер. ГЪ данным Н.Н Полуниной (1958), ШКГолиадзе, Б.ДТутберидзе, КГ.Шжарадзе (1974), ММБабаева (1972), Т.ПБарбакадзе (1973), Мгалоблишвили (1986), содержание сахара и крахмала находится в черешках листьев в минимальном количестве или вовсе отсутствует в связи с тем, что они расходуются при весенней вегетации. ФЕЙХОА
Фейхоа - перекрестноопыляемое растение. Бутоны крупные, 15-17 мм диаметром Развитие их происходит медленно, в течение 1-1,5 месяцев. На Черноморском побережье Кавказа они появляются в середине или конце апреля, а иногда и в начале мая, развиваются в пазухах листьев на побегах весеннего прироста текущего года, иногда на пропшогодних ветках последнего прироста. (ВПГвасалия, 1968, ЕВ.Какабадзе, 1969).
Цветки крупные, одиночные, парные или собранные в соцветие до 30 штук, обоеполые, с 4-х членным кругом двойного околощетника Высота цветков 23-33 мм, диаметр 24-32 мм. Каждьш цветок имеет свою цветоножку серо-зеленого цвета длиной 12-20 мм. Чашечка состоит из 4-5-ти сросшихся лепестков, слегка опушенная, зеленая снаружи, внутри красновато-коричневая. Количество лепестков от 4-х до 8-ми. Мясистые лепестки снаружи белые, а внутри пурпурно-розовые, вогаутые чашеобразно, так что видна белая окраска нижней стороны лепестков. Цветки яркие и красивые (ВААлександрова, Л.ВВоейкова, I960; ШКГолиадзе, Б.ДТутберидзе, КГ.Нижарадзе, 1974).
Лепестки цветков содержат много сахара, благодаря чему привлекают насекомых, в том числе пчел, которые способствуют опылению (АНКоролев, 1936; ВПГвасалия, Н В. Коваленко, 1985; Byerson, 1927; Fraser, 1927; Schroeder, 1947).
Щетки с многочисленными тьминками (от 50 до 103) с прочными тычиночными нитями, в бутоне ярко-пурпуровыми, а в цветке — красновато-малиновыми, выступающими из него пучком в несколько рядов. 1Ъ данным Э.Б.Тодадзе (1977), высокая урожайность у фейхоа получается при опьшении цветков пыльцой из свежераскрьпых пыльников.
Плод фейхоа - крупная мясистая сочная ягода с одревесневшими чашелистиками. Семена окружены белой полупрозрачной кисло-сладкой п пульпой. По форме плоды бывают от уплиненно-овальной до широкоокруглой, реже встречаются бочковидные. Поверхность плода гладкая, морщинистая, покрыта матовым восковым налетом. Масса кожицы по отношению к самому плоду составляет 18,4-22,5%. Ее окраска темно- и светло-зеленая с сизым оттенком благодаря восковому налету, иногда с размытым румянцем. Перезрелые плоды приобретают желтовато-бурый цвет.
По данным исследователей (З.ИКЪроткова, 1935; ДМ Алиев, 1956; МС.Кварацхелия, 1960; НВКЪваленко, 1970; ВПГвасалия, 1974; ИИКЬваль, 1975) плоды фейхоа созревают в зависимости от сортов и форм со второй половины октября и до конца ноября.
avк общему выводу, что .пределом морозоустойчивости является последняя указанная температура
Булевы алгебры с выделенными эндоморфизмами
Данный параграф посвящен исследованию автоустойчивости относительно уровней гиперарифметической иерархии для почти суператомных булевых алгебр. Результаты данного параграфа опубликованы в [80].
Будем называть алгебру почти суператомной, если она изоморфна интервальной алгебре 23(и;а х (1+т/)) для некоторого ординала а. Нетрудно показать, что ранг Фреше алгебры В(ша х (1 + г])) равен а.
Замечание 2.1.1. Заметим, что для счётного ординала а интервальные алгебры 23(и;а х (1 + т/)) и 23(и;а х п) изоморфны. (Это следует из того, что обе алгебры являются а-атомными и их факторы по идеалу Fa изоморфны нетривиальной безатомной алгебре.) Поэтому далее мы отождествляем алгебры 93 (и/ х (1 + г/)) и 93 (и/ х п).
Лемма 2.1.1. Пусть 93 — почти суператомная булева алгебра, а — ранг Фреше 93. Алгебра 23 обладает вычислимым представлением в том и только том случае, когда а J{K.
Доказательство. Используя рассуждения, аналогичные приведённым в замечании 2.1.1, нетрудно показать, что алгебры 23 и 23(о;а х (1 + г/)) изоморфны.
Пусть а ufк. Для того, чтобы доказать конструктивизируемость алгебры 23, достаточно показать, что линейный порядок ша х (1 + г/) имеет вычислимое представление. Если а wfк, то нужное нам утверждение следует из того, что ша является вычислимым ординалом. Заметим, что шШі = wfк, а в работе [63] доказано, что линейный порядок ufK х (1 -\-rj) конструктивизируем.
Предположим теперь, что а wfк. Допустим, что — вычислимое представление
Выберем с Є , такое что алгебра с изоморфна 23(u;fA:). Тогда с? является вычислимой суператомной алгеброй, имеющей тип (u)fK, 1), что противоречит теореме 1.2.2. Лемма 2.1.1 доказана. Булевой алгеброй Харрисона называется почти суператомная алгебра 93(uji K х (1 + rj)). Далее будем обозначать булеву алгебру Харрисона через 93я Предложение 2.1.1 (К. Эш [35]). Существуют вычислимые представления 21 и алгебры &и, такие что не существует гиперарифметического изоморфизма /: 21 — t.
Булева алгебра 93 я не является / -категоричной ни для какого вычислимого ординала а. Далее в этом параграфе мы будем рассматривать только почти суператомные алгебры, имеющие вычислимый ранг Фреше.
Замечание 2.1.2. В [11] и [75] независимо доказано, что безатомная булева алгебра 53 (т/) является относительно Д -категоричной.
Основным результатом данного параграфа является следующая теорема, дающая (вместе со следствием 2.1.1 и замечанием 2.1.2) полное описание уровней А-категоричности для почти суператомных булевых алгебр.
Теорема 2.1.1. Пусть а — ненулевой вычислимый ординал. Булева алгебра 3(ша х п) является относительно /А\а+1-категоричной и не является / „-категоричной.
Доказательство теоремы 2.1.1 состоит из последовательности лемм. В лемме 2.1.2 доказывается относительная А2а+1-категоричность. Лемма 2.1.3 является вспомогательным утверждением, позволяющим дать описание стандартных челночных отношений для кортежей из алгебры 93(u;a х rj). В лемме 2.1.4 доказывается следующее: если а — ординал-последователь, то алгебра 93(и;а хп) не является А -категоричной. В лемме 2.1.5 аналогичный факт доказан для предельного ординала а.
Лемма 2.1.2. Пусть 5 — вычислимый предельный ординал или ноль, п Є ш и 5 + п I. Булева алгебра В(шЙ+п х rj) является относительно А+2п+1-категоричпой.
Доказательство. В силу теоремы 1.1.1, достаточно показать, что алгебра В(шЙ+п х rj) обладает формальным +2га+1-семейством Скотта.
В дальнейшем можно считать, что мы рассматриваем вычислимое представление В(шЙ+пхг]), в котором итерированные идеалы Фреше F равномерно вычислимы по /3 5 + п и множества At равномерно вычислимы по /3 5 + п. Будем обозначать это представление 23. (Такое представление нетрудно построить, опираясь на доказательство [39, предл. 15.15].)
Выберем некоторое а Є О, такое что \а\ = 5 + п. Пусть W {b \ b о а}. Известно, что W является вычислимо перечислимым множеством, и для любого /3 5 + п существует единственное Ъ Є W, такое что Ь = /3.
Пусть а = сії,..., as — кортеж из 23. Рассмотрим Ь\,... ,Ьт — все атомы подалгебры, порожденной а. Заметим, что bj = tj(a) при j = 1,..., га, где tj — некоторый терм языка LB А- Для каждого bj выполнен в точности один из следующих случаев.
Аз-категоричность булевых алгебр
Пусть фл = ф П (At(55) x At(55)). Из пунктов (l)-(3) замечания 3.1.3 следует, что фл является биекцией множества At(55) на себя. Ясно, что существует автоморфизм р булевой алгебры 55, удовлетворяющий условию tp \ At(55) = фл- Вследствие [10, Предл. 3.8.1], такой автоморфизм р единственен. Используя пункты (4)-(6) замечания 3.1.3 и лемму 3.1.6, легко показать, что р \ (1от(ф) = ф.
Покажем, что автоморфизм р является вычислимым. Опишем процедуру нахождения ip(а) для произвольного а Є 55, такого что а $. {0,1}. Если а Є B0l то легко понять, что а Є dom( 01) и р(а) = ф\(а). В дальнейшем будем считать, что а В0. Существует единственное s, такое что а Є Bs+\ \ Bs. Находим b\,... ,bn — попарно различные атомы 55s+i, такие, что а = bi V ... V bn. Тогда Ьь ..., Ъп Є ёош( +3) и (р{а) = ф3+з(Ьі) V ... V ф3+3(Ьп).
Полагаем 55 = (55,(/?). Легко заметить, что, если а ф 6, (а, а) Є Inft и (b,b) Є Infs для некоторых t и s, то а и Ъ лежат в различных бесконечных атомных орбитах 55 . Следовательно, в 55 бесконечно много бесконечных атомных орбит.
Определим функцию F: ш — ш + 1 так же, как в доказательстве леммы 3.1.1. Для доказательства леммы 3.1.5 осталось показать, что для любых п, к 1 включение (п,к) Є х(55 ) справедливо тогда и только тогда, когда к F(n).
Пусть (п,к) Є х(55 ), т.е. в 55 существует не менее к атомных орбит мощности п. Зафиксируем Ъ — элемент одной из таких орбит. Пусть Ъ Є Bso+i \ Bso. Легко понять, что найдется хъ Є dom( jfSo+i), такой, что множество элементов кортежа gSo+i(xb) в точности совпадает с орбитой Ъ в 55 . Согласно построению значение gs(xb) меняется только на тех шагах, на которых под каждым элементом д3(хь) добавляются новые элементы 55. Учитывая это, а также пункты (3) и (4) замечания 3.1.2, получаем: из того, что Ъ Є At(55), следует то, что lims f(xb, s) = п. Кроме того, заметим, что при выборе различных атомных орбит мощности п, применяя процедуру, описанную выше, мы будем получать разные хь, следовательно, F(n) к.
Предположим теперь, что для пары (п,к) выполняется 0 к F(n). Зафиксируем х, такой что ]imsf(x, s) = п, и щ, такое что (Vu uo)(f(x,u) = п). Положим so = 2(х,щ) + 2 и рассмотрим кортеж gso(x). Ясно, что множество всех элементов этого кортежа являет ся орбитой в 53 . Согласно пункту (4) замечания 3.1.2 и описанию конструкции, ни под одним элементом gso(x) после шага So не появится новых элементов 23, следовательно, мно жество элементов gSo(x) является атомной орбитой мощности п. Для того, чтобы доказать, что (п, к) Є х(53 ), осталось заметить, что, вследствие пункта (5) замечания 3.1.2, для произ вольных х ф у выполнено: для любых s\ и s2, если д31(х) = (а\,...,а ) и gS2(y) = Фг, ,h), то {а\,..., cik} П {&1,..., Ь{\ = 0. Лемма 3.1.5 доказана. Перейдём к рассмотрению случая Ai-алгебры с конечным характером.
Лемма 3.1.7. Пусть І а шиКСшхш— конечный характер. Тогда существует вычислимая Аі-алгебра 23 = (23, ф), такая что 23 = 23(ш), в 23 в точности а бесконечных атомных орбит, х( 8 ) = К и At(23) — вычислимое множество.
Доказательство. Приведём доказательство случая, при котором а = и и К ф 0. Остальные случаи рассматриваются аналогично. Пусть К = {{щ, кг) 1 г га, 1 кг 1г}1 где га 1, U 1 для любого г, щ ф rij при г ф j. Пусть N0 = О, N = Yl]=i njh Для 1 га. Зафиксируем вычислимую булеву алгебру Легко показать, что существует единственный автоморфизм р булевой алгебры 23, для которого ip \ At(53) = ф. Также ясно, что р является вычислимым автоморфизмом. Из определения ф очевидно, что 53 = (53, ф) является искомой -алгеброй. Лемма 3.1.7 доказана. Заметим, что леммы 3.1.5, 3.1.7 и замечание 1.3.1 полностью доказывают достаточность условий теоремы 3.1.1. Теорема 3.1.1 доказана.
Прежде чем приводить следствия теоремы 3.1.1, докажем вспомогательное утверждение о характере произвольной вычислимой Аі-алгебрьі. Замечание 3.1.4. Пусть а — тьюрингова степень. Характер К является в. п. относительно а в том и только том случае, когда функция FK а-предельно монотонна. Предложение 3.1.1. Пусть 25 = (25, /?) — вычислимая А\-алгебра. Тогда х( 8 ) является в. п. относительно At(55).
Доказательство. Без ограничения общности можно считать, что 55= (ш, V, Л, С, 0,1). Если At(25) — конечное множество, то очевидно, что х(25 ) конечно. В дальнейшем будем считать, что множество At(25) бесконечно.
Очевидно, что (Wx)(Ws)(f(x, s) f(x,s + 1)). Легко доказать, что для любых п, k 1 пара (п,к) лежит в х(23 ) тогда и только тогда, когда существует номер шага s, удовлетворяющий условию f(n, s) = к. Следовательно, (Vn) (Fx(!B )(n) = lims f(n, s)) , т. е. функция FX(SB ) является а-предельно монотонной. В силу замечания 3.1.4, х(55 ) в. п. относительно
Первым интересным следствием теоремы 3.1.1 является критерий существования вычислимого представления с вычислимым множеством атомов для -алгебры (53 (и;), ф).
Теорема 3.1.2. Пусть 53 = (53, ф) — Аі-алгебра, такая что 53 = 53 (w). Тогда 53 обладает вычислимым представлением с вычислимым множеством атомов в том и только том случае, когда х( 3 ) в- п- множество. В частности, Хс( В(ш)) Г\ТР1 = X Г\ YPV
Доказательство теоремы 3.1.2. Необходимость приведённого условия следует из предложения 3.1.1. Достаточность вытекает из замечания 1.3.1, леммы 3.1.7 и следующего вспомогательного утверждения.
Лемма 3.1.8. Пусть а ииКСихи — бесконечный в. п. характер. Тогда существует вычислимая А\-алгебра 53 = (53,(/?)7 такая что 53 = 53(о;)7 53 содержит в точности а бесконечных атомных орбит, х( 3 ) = К и At(53) — вычислимое множество.
Доказательство. Зафиксируем сильно вычислимую последовательность конечных множеств К0 С К1 С ..., удовлетворяющую условиям: \Jseuj Ks = К, К0 = 0 и Ks+l = KsU{(ns, ks)} для любого s, причём (ns, ks) $. Ks и либо ks = 1, либо ks 1 и (ns, ks — l) Є Ks. Определим вычислимую функцию JK -OJXUJ UJ следующим образом: . Очевидно, что функция JK удовлетворяет условиям леммы 3.1.5, следовательно, существует вычислимая -алгебра 53 = (53, с/?), такая что 53 = 53(ш), в 53 имеется в точности а бесконечных атомных орбит и х(53 ) = К.
Степени категоричности булевой алгебры 93(ш) с выделенным автоморфизмом
Кроме того, заметим, что элемент (0,6) лежит в идеале Фреше F(93) тогда и только тогда, когда имеет место р(0,Ь) Є F(93). Следовательно, для того, чтобы доказать, что tp является изоморфным вложением модели t в (t+i, достаточно проверить сохранение предикатов Qk только для элементов, имеющих вид (0, 6), где b Є F(93) и b ф 0.
Пусть с и d — ненулевые элементы из F(93). Предположим, что t \= Qk((0,c), (0,d)). Нетрудно понять, что найдутся попарно различные атомы р0,... ,pi алгебры 53, для которых с = ро \/ ... \/ pi и d = дк(ро) V ... V дк(рі). Непосредственно из определения ір следует, что +i h Qk(tp(Q,Pi), -P(Q,gk(Pi))) Для всех і и7 следовательно, tt+1 = Qk(ip(0, с), /?(0, d)).
Предположим, что tt+i \= Qk((p(0,c),ip(0,d)) для некоторого к n{t). Ясно, что в этом случае найдутся атомы р0,... ,pi и q0,... ,qi алгебры 53, такие что pi ф Pj и ф qj при г ф j, с = ро V ... У pi, d = g0 V ... V ф и t+1 = Qfc( /?(0,pi), ір(0, %)) для всех і В частности, элементы ір(0,рі) и /?((),$) лежат в одной и той же орбите Аі-алгебрьі (53,/і). Допустим, что для некоторого і PiU qi лежат в разных орбитах -алгебры (53, д). Тогда для некоторых 1итвС( выполнено Qi((0,Pi), (0,а0)) & Qm((0,bo), (0, )). Отсюда получаем, что в tt+i истинно Qn(t)-\-i-\-m-\-i((p(0,pi),(p(0,qi)), что приводит к противоречию. Следовательно, для всех г орбиты ОтЬд{рі) и Orhg(qi) совпадают. Отсюда получаем, что t \= Qk((Q,Pi), (0, qi)) H t=Qfc((0,c),(0,d)).
Для того, чтобы завершить доказательство, осталось заметить, что элементы (0, а) и (0, Ъ) лежат в различных орбитах -алгебры (53, fi) и для некоторого к имеет место /?(0, Ь) = /і (ір(0, а)), поэтому выполнено +! h к Ы(0,а),(0,Ь)), t+i Н- & 0,( (0, а), (0,6)). Предложение 3.3.4 доказано. Пусть теперь К є {А, 4.А}- Допустим, что отображение v является Д -вычислимой нумерацией Кс/ 0. Рассмотрим класс К0 = {WI \ %Л Є К} моделей языка V. Определим отображение ц следующим образом: //(е) = (и(е)) . Вследствие леммы 3.3.1, ц является Д вычислимой нумерацией -К"о/= с чт0 невозможно в силу предложений 3.3.4 и 3.3.3. Теоремі ма 3.3.1 доказана. Заключение
В диссертации исследовались автоустойчивость относительно тьюринговых степеней и автоустойчивость относительно уровней гиперарифметической иерархии для класса булевых алгебр. Получены следующие результаты об уровнях автоустойчивости для булевых алгебр.
1. Получено описание уровней Д -категоричности для почти суператомных булевых алгебр (т.е. булевых алгебр вида (аУ3 х rj)).
2. Доказано, что любая вычислимая суператомная булева алгебра обладает сильной степенью категоричности. Этот результат даёт полное описание спектров категоричности для суператомных булевых алгебр.
3. Доказано, что для булевых алгебр понятия Д -категоричности и относительной Д-категоричности совпадают. В качестве следствия этого факта получено, что никакая тьюрингова степень d, удовлетворяющая условиям 0 d 0 , не может быть степенью категоричности булевой алгебры.
Также в диссертации исследовались алгоритмические свойства различных классов булевых алгебр с конечным числом выделенных эндоморфизмов. В рамках этой темы получены следующие результаты.
1. Получен критерий конструктивизируемости для булевой алгебры 93 (ш) с выделенным автоморфизмом.
2. Доказано, что любая 2-вычислимо перечислимая тьюрингова степень d является степенью категоричности некоторой вычислимой булевой алгебры с выделенным автоморфизмом. Этот результат показывает существенное различие между возможными спектрами категоричности для класса булевых алгебр и класса булевых алгебр с выделенным автоморфизмом.
3. Для класса всех вычислимых булевых алгебр с п выделенными эндоморфизмами (где О п ш) дана оценка гиперарифметической сложности для нумераций с точностью до вычислимого изоморфизма и для фридберговых нумераций с точностью до Д-вы-числимого изоморфизма. Одной из основных рекомендаций дальнейшего развития результатов диссертации является продолжение исследования спектров категоричности для булевых алгебр и булевых алгебр с выделенными эндоморфизмами. В рамках этой темы можно выделить следующие задачи. 1. Описание спектров категоричности для различных классов булевых алгебр (в частности, для класса почти суператомных булевых алгебр). 2. Построение новых примеров спектров категоричности. 3. Исследование спектров автоустойчивости относительно сильных конструктивизаций (это понятие введено в работе [9]). Результаты диссертационного исследования могут использоваться в образовательном процессе при организации спецкурсов по теории вычислимых моделей и теории счётных булевых алгебр, предназначенных для студентов, магистрантов и аспирантов высших учебных заведений.