WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |   ...   | 29 |

1. Downey R. G. 144 11. Lerman M. 59 21. Sacks G.E. 2. Shore R.A. 103 12. Арсланов M.M. 56 22. Normann D. 3. Slaman T.A. 81 13. Nies A. 54 23. Kleene S.C. 4. Cooper S.B. 73 14. Lempp S. 52 24. McLaughlin T. 5. Ершов Ю. Л. 73 15. Remmel J.B. 47 25. Harrington L.A. 6. Soare R.I. 68 16. Lachlan A.H. 45 26. Simpson S.G. 7. Jockusch C.G.J 67 17. Дегтев А.Н. 45 27. Knight J.F. 8. Гончаров С.С. 66 18. Cholak P. 38 28. Бадаев С.А. 9. Ambos-Spies K. 65 19. Sorbi A. 37 29. Добрица В.П. 10. Селиванов В.Л. 60 20. Chong C.T. 36 30. Оманадзе Р.Ш. Мальцевские чтения 2009 Теория вычислимости Дадим краткую сводку известных математических журналов, в которых помещены работы, упомянутые в базе:

1. J. Symbolic Logic 2. Aлгe6pa и лoгикa 3. Z. Math. Logik und Grundl. Math. 4. Ann. Pure Appl. Logic 5. ДАН СССР (РАН) 6. Сибирск. матем. журнал 7. Trans. Amer. Math. Soc. 8. Proc. Amer. Math. Soc. 9. Arch. Math. Logik Grundl. Math. 10. Lect. Notes in Math. 11. Lect. Notes in Comput. Sci. 12. Maт. зaмeтки 13. Изв. Вузов 14. Theor. Comput. Sci. Институт системного программирования РАН, Москва E-mail:lavrov@ispras.ru Мальцевские чтения 2009 Теория вычислимости Разрешимость булевых алгебр элементарной характеристики (1,0,1) М. Н. Леонтьева Вычислимая булева алгебра называется n-вычислимой, если существует алгоритм, определяющий по конечной n-формуле и набору элементов, истинна ли эта формула на данном наборе. Сильно вычислимая модель — та, для которой подобный алгоритм существует для всех формул исчисления предикатов. Булева алгебра разрешима, если у неё существует сильно вычислимая изоморфная копия.

Для каждой булевой алгебры A обозначим через At(A) множество атомов, через Atm(A) —идеал атомных элементов, через Als(A) —идеал безатомных элементов.

Кроме того, будем использовать E(A) =Atm(A)+Als(A) —идеал Ершова — Тарского, F (A) —идеал Фреше.

Пусть A — вычислимая булева алгебра элементарной характеристики (1,0,1). То есть A/E — ненулевая безатомная булева алгебра. Пусть S — подмножество набора {At, Atm, Als, E}. Рассмотрим следующий вопрос: можем ли мы утверждать, что A разрешима, если все предикаты из S вычислимы в A Было доказано, что для S = {At, Als} ответ положительный, а для S = {At} и S = {Als, Atm, E} отрицательный.

Теоремы 1 и 3 завершают изучение данного вопроса.

Теорема 1. Пусть A — вычислимая булева алгебра элементарной характеристики (1,0,1). Если At(A) и Atm(A) вычислимы, то A разрешима.

Пусть {Ek}k — последовательность идеалов Ершова — Тарского, а Atmk(A) — идеал атомных элементов фактор-алгебры A/Ek. Теорема 1 обобщена на случай булевых алгебр характеристики (n, 0, 1) следующим образом.

Теорема 2. Пусть, A — вычислимая булева алгебра элементарной характеристики ( +1, 0, 1). Если A является (4 +1)-вычислимой и при этом вычислим идеал Atm(A), то A разрешима.

Теорема 3. Существует неразрешимая вычислимая булева алгебра A элементарной характеристики (1, 0, 1) с вычислимыми At(A) и E(A).

При доказательстве теоремы 3 было получено следующее описание 0-вычислимых булевых алгебр. Пусть T = (Atm F ) +Atm, где Atm F = {x|z x(z F z Atm)}.

Теорема 4. Следующие условия эквивалентны:

(а) A является 0-вычислимой булевой алгеброй;

(б) A является 0-вычислимой булевой алгеброй;

(в) существует вычислимая булева алгебра C элементарной характеристики (1,0,1) такая, что C/T A.

= Научный руководитель — д. ф.-м. н., доцент П. Е. Алаев.

Новосибирский Государственный Университет, Новосибирск E-mail:Margarita.Leontyeva@gmail.com Мальцевские чтения 2009 Теория вычислимости О сильной приводимости над недвукардинальной формулой.

А. Т. Нуртазин Как следует из синтаксического критерия М. Гэйфмана [1], недвукардинальность данной полной теории T над одноместным предикатом P на самом деле означает, что в этой теории существуют «сильные», даже в каком то смысле «формульные», связи между основным множеством любой модели этой теории и её ограничением на подмножество, выделяемой в ней этим предикатом. В то же время «сильная приводимость» T над этим предикатом гарантирует, что эта связь «заметным образом» отражается на структуре этого ограничения. Вышесказанное делает естественным предположение, что некоторые «регулярные» свойства ограничения T |P в этом случае гарантируют другие «хорошие» свойства самой теории T. Следующий список, по-видимому, не является окончательным.

10. Счётная категоричность ограничения T |P влечёт счётнуюкатегоричность исходной теории T.

20. Если T |P имеет три счётные модели, то число счётных моделей исходной теории T также конечно.

30. Если T |P имеет счётнуюнасыщеннуюмодель, то такуюже модель имеет и T.

40. Если T |P стабильна в мощности k, то такой же оказывается и исходная теория T.

Для формулировки следующих оценочных утверждений напомним, что недвукардинальность теории над формулой эквивалентна существованию в этой теории «замыкающей m - -P -формулы», где m = m1 + · · · + mk и для любого элемента a из произвольной модели A теории T можно последовательно подбирать m1 элементов b1 из подмножества P (A), затем n1 элементов из подмножества ¬P (A) (и эти эле менты зависят от кортежа b1, но не зависят от исходного элемента a). И так k раз.

В следующих двух свойствах предполагается существование в теории T «замыкающей m --P -формулы».

50. Если T |P тотально трансцендентна и имеет ранг Морли, то ранг Морли исходной теории T не превышает ординала m.

60. Если T |P суперстабильна и Deg(T |P ) =, то выполняется неравенство Deg(T |P ) m.

Список литературы [1] Gaifman H. On local and nonlocal properties. Proceedings of the Herbrand Symposium, Log. Colloquium’81, North-Holland Publ. Company, 1982, 105–135.

[2] Hodges W. Model theory. Camdridge Univ. Press, 1993.

КазНУ, Алматы E-mail:AbyzNurtazin@mail.ru Мальцевские чтения 2009 Теория вычислимости Некоторые свойства вычислимых нумераций различных классов иерархии Ершова С. С. Оспичев В работе рассматриваются вычислимые нумерации [3] семейств множеств из различных классов -1 иерархии Ершова [2].

n Мы будем рассматривать более сильное определение вычислимых нумераций семейств множеств из класса -1 иерархии Ершова.

Определение. Нумерация {n}n называется -вычислимой, если множество { m, n | m n} принадлежит классу -1 иерархии Ершова, где — вычислимый ординал.

Показано, что не существует вычислимой нумерации семейства всех множеств из класса -1 для любого вычислимого ординала.

В работе анонсирована Теорема. Существует минимальная нумерация семейства всех множеств из класса -1 иерархии Ершова.

n n Заметим, что в [4] доказано, что для конечных уровней иерархии Ершова -1 докаn зано, что семейства всех множеств из -1 имеет даже минимальную фридберговскую n нумерацию.

Список литературы [1] Арсланов М. М. Иерархия Ершова. Казань: Казанский государственный университет, 2007.

[2] Ершов Ю. Л. Об одной иерархии множеств III. Алгебра и логика, 9 (1970), N. 1, 34–51.

[3] Гончаров С. С., Сорби A. Обобщенные вычислимые нумерации и нетривиальные полурешетки Роджерса. Алгебра и логика, 36 (1997), N. 6, 621–641.

[4] Goncharov S. S. Lempp S., Solomon R. Friedberg numberings of families of n-computability enumerable sets.

Новосибирский государственный университет, Новосибирск E-mail:ospichev@gmail.com Мальцевские чтения 2009 Теория вычислимости Отношения на вычислимых линейных порядках и иерархия Ершова А. Н. Фролов Д. Хиршфельдт показал, что все конечные уровни иерархии Ершова реализуются спектром отношения на вычислимой структуре. Аименно, он построил для любого n вычислимую структуру A и отношение U такие, что DgSpA(U) =-1. Построенные n структура и отношение не являются естественными. Возникает вопрос — для каких естественных структур и отношений на них выполнено аналогичное свойство.

Теорема. Существует вычислимый линейный порядок L такой, что для любого n выполнено DgSpL(Sn) =-1, где n S0 = ;

S2n(x, y) (k {1,..., n})(|(x, y)L| =2k - 1) для n 1;

S2n+1(x, y) S2n(x, y) |(x, y)L| 2n +1;

(x, y)L = {z | x

В работе также изучаются различные свойства введенных отношений.

Казанский государственный университет, Казань E-mail:Andrey.Frolov@ksu.ru Мальцевские чтения 2009 Теория вычислимости -однородная алгебраическая система и универсальные функции А. Н. Хисамиев Одним из принципиальных результатов обычной теории вычислимости является существование универсальной частично вычислимой функции. Как известно (см. [1]) в любом допустимом множестве существует универсальный -предикат, но это не верно для -функций [2]. Поэтому представляет интерес нахождение условия на алгебраическую систему M для существования универсальной -функции в наследственно конечном допустимом множестве HF(M) над M. В [2, 3–8] для некоторых классов систем даны такие условия.

В данном сообщении введено понятие -однородной алгебраической системы M и получено необходимое и достаточное условие для существования универсальной функции в HF(M). Этот критерий применен для одного класса периодических абелевых групп.

Список литературы [1] Ершов Ю. Л. Определимость и вычислимость. Новосибирск: научная книга, 1996. (Сибирская школа алгебры и логики).

[2] Руднев В. А. Об универсальной рекурсивной функции на допустимых множествах. Алгебра и логика, 25 (1986), N. 4, 425–436.

[3] А. С. Морозов, В. Г. Пузаренко. О -подмножествах натуральных чисел. Алгебра и Логика, (2004), N. 3, 291–320.

[4] Калимулин И. Ш., Пузаренко В. Г. О вычислимости на структурах. Мататематические труды, 1, N. 2, 35–72.

[5] Пузаренко В. Г. К вычислимости на специальных моделях. Сиб. мат. журн., 46 (2005), N. 1, 185– 208.

[6] Хисамиев А. Н. О -подмножествах натуральных чисел над абелевыми группами. Сиб. мат. журн., 45 (2006), N. 3, 211–228.

[7] Хисамиев А. Н. -ограниченные алгебраические системы и универсальные функции I. Сиб. мат.

журн., принято к печати.

[8] Хисамиев А. Н. -ограниченные алгебраические системы и универсальные функции II. Сиб. мат.

журн., принято к печати.

ИМ СОРАН, Новосибирск E-mail:hisamiev@math.nsc.ru Мальцевские чтения 2009 Теория вычислимости О конструктивной нильпотентной группе, размерность коммутанта которой конечна Н. Г. Хисамиев В сообщении получен критерий конструктивизируемости нильпотентной группы ступени 2, указанной в заглавии. Размерностью dim(G) абелевой группы без кручения называется максимальное число линейно независимых ее элементов.

Лемма 1. Пусть G — нильпотентная группа без кручения, I(G ) — изолятор коммутанта, = G/I(G ). Если размерности групп и G соответственно бесконечна и конечна, то для любого конечного множества F G размерность факторгруппы C(F )/I(G ) централизатора C(F ) множества F по I(G ) бесконечна.

Теорема 1. Пусть G — нильпотентная группа без кручения ступени 2, размерность коммутанта которой конечна. Тогда существует нумерация µ группы G, для которой справедливы следующие свойства: 1) группа (G, µ) конструктивна; 2) изолятор коммутанта I(G ) вычислим в (G, µ); 3) существует такая вычислимо перечислимая система элементов {bi | i I} в (G, µ), что смежные классы {biI(G )} образуют базис фактор-группы G/A.

Пусть даны нумерованные полные абелевы группы без кручения (A, ) и (B, ), где dim(A) = r, r, и 2-х местная частично вычислимая функция n номера n такие, что: 10) A B =0; 20) в группе (B, ) имеется вычислимо перечислимый базис {bi | i < } для некоторого ; 30) область определения функции n содержит множество { i, j | i

r Через (Hn, n) обозначим центральное расширение группы A посредством (B, ) с определяющими соотношениями [bi, bj] =n(i, j), где n — естественная нумерация r группы Hn, определенная по и.

Теорема 2. Пусть G — нильпотентная группа без кручения ступени 2, размерность коммутанта которой конечна и равна r. Группа G конструктивизируема тогда и только тогда, когда она изоморфна вычислимо перечислимой подгруппе группы r (Hn, n) при некотором n.

Группа G называется упорядоченно конструктивизируемой, если существуют ее упорядочивание и нумерация µ такие, что система G, ·,, µ является конструктивной упорядоченной группой.

Следствие 1. Конструктивизируемая нильпотентная группа без кручения ступени 2, размерность коммутанта которой конечна, упорядоченно конструктивизируема.

Теорема 3. Для любого натурального числа r семейство всех конструктивизируемых нильпотентных групп без кручения ступени не более 2, размерность коммутантов которых не более r, вычислимо.

Восточно-Казахстанский государственный технический университет им. Д. Серикбаева, Усть-Каменогорск E-mail:hisamiev@mail.ru Мальцевские чтения 2009 Теория вычислимости Superlow sets and degrees M. Kh. Fazrahmanov Let J = {a b : a, b are superlow c.e. degrees}, and let C be the semilattice of all c.e.

degrees.

Theorem 1. For all superlow c.e. degrees a0, a1, a2 there are superlow c.e. degrees b0, b1, b2, such that a0 a1 a2 = b0 b1 = b0 b2 = b1 b2.

Corollary 2. J is an upper semilattice.

Theorem 3. There is a c.e. degree a such that for all c.e. degrees b0, b1, b2 if a = b0 b1 = b0 b2 = b1 bthen bi is not totally -c.e. for some i <3.

Corollary 4. The upper semilattices J and C are not elementary equivalent.

Theorem 5. For all notation a O there is a low 2-c.e. set D, such that for all 2-c.e.

sets E and F, if E -1, F -1, then D T E F.

a a Corollary 6. (Independently with M. Yamaleev). The low c.e. degrees and the low 2-c.e. degrees are not elementary equivalent.

Theorem 7. Let and µ be 0-computable numberings of some families of sets. Then the predicate P (e, i) (e) = µ(i) is a 0-predicate.

Corollary 8. The family of all superlow sets has a -1-computable numbering.

Kazan State University, Kazan E-mail:Marat.Faizrahmanov@ksu.ru Мальцевские чтения 2009 Теория вычислимости The effective theory of Borel equivalence relations E. B. Fokina, S.-D. Friedman, A. Trnquist In this talk we discuss the question of effectiveness of some well-known results in descriptive set theory. The study of Borel equivalence relations under Borel reducibility has developed into an important area of descriptive set theory. The dichotomies of Silver [3] and Harrington—Kechris—Louveau [1] show that with respect to Borel reducibility, any Borel equivalence relation strictly above equality on is above equality on P(), the power set of, and any Borel equivalence relation strictly above equality on the reals is above equality modulo finite on P().

We discuss the effective content of these and related results by studying 1 (hyperarithmetical) equivalence relations under 1 reducibility. The resulting structure is complex, even for equivalence relations with finitely many equivalence classes. However use of Kleene’s O as a parameter is sufficient to restore the picture from the noneffective setting.

A key lemma is the existence of two 1 sets of reals, neither of which contains the range of the other under any 1 function; the proof of this result applies Barwise compactness to a deep theorem of Harrington (see [2]) establishing for any recursive ordinal the existence of 0 singletons whose -jumps are Turing incomparable.

References [1] Harrington L., Kechris A., Louveau A. A Glimm—Efross dichotomy for Borel equivalence relations.

Journal of the American Mathematical Society, 3 (1990), N. 4, 903–928.

[2] Hjorth G. An argument due to Leo Harrington. Unpublished note,http://www.math.ucla.edu/greg/ harrington.dvi.

[3] Silver J. H., Counting the number of equivalence classes of Borel and coanalytic equivalence relations.

Annals of Mathematical Logic, 18 (1980), N. 18, 1–18.

Kurt Gdel Research Center for Mathematical Logic, University of Vienna, Vienna (Austria) E-mail:efokina@logic.univie.ac.at Мальцевские чтения 2009 Теория вычислимости Relations on computable linear orderings and Ershov hierarchy A. N. Frolov D. Hirschfildt showed that any finite level of Ershov hierarchy is realized by a spectrum of a relation on computable structure. Namely, he constructed for any n computable structure A and relation U such that DgSpA(U) =-1. These structure and relation are n not natural. What natural structures and relations satisfy similar property Theorem. There exists a computable linear ordering L such that for any n we have DgSpL(Sn) =-1, where n S0 = ;

S2n(x, y) (k {1,..., n})(|(x, y)L| =2k - 1) for n 1;

S2n+1(x, y) S2n(x, y) |(x, y)L| 2n +1;

(x, y)L = {z | x

Pages:     | 1 |   ...   | 22 | 23 || 25 | 26 |   ...   | 29 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.