WWW.DISSERS.RU

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

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


Pages:     | 1 |   ...   | 21 | 22 || 24 | 25 |   ...   | 29 |

Институт проблем информатики и управления, Алматы E-mail:kbsh@ipic.kz Мальцевские чтения 2009 Теория моделей Непрерывность и теоретико-множественные модели теории лямбда А. А. Лялецкий Изначально построенное Алонзо Черчем в 1930-х годах лямбда-исчисление более лет не имело никакой своей разумной семантики в теоретико-множественных терминах. Только в конце 1960-х годов Дана Скотт предложил ограничиться рассмотрением так называемых топологических моделей, построенных на его определении непрерывной функции над полными решетками и приведших к определенному соответствию между синтаксисом лямбда-подобных исчислений и семантикой Скотта.

Модели Скотта были приняты за ”канонические” для лямбда-исчисления; также были построены другие интенсиональные модели лямбда-подобных исчислений, базирующихся на конструкциях, которые использовал Д. Скотт. Однако, фактически открытым остался следующий вопрос: можно ли ввести такие понятия непрерывной функции, которые, с одной стороны, определяют классы непрерывных функций, отличные от классов функций, непрерывных по Скотту, а с другой стороны, также приводят к теоретико-множественным моделям лямбда-подобных исчислений.

В данном сообщении дается возможное решение этой проблемы на базе новых понятий непрерывных функций над частично упорядоченными множествами и введенных автором с помощью новых определения сходимостей направленностей (над частично упорядоченными множествами) с “достаточным числом” инфимумов и супремумов.

Исходя из установленных свойств пределов направленностей, удается дать абстрактную теоретико-множественную характеризацию новых понятий непрерывности, что служит основой для проведения сравнительного анализа соответствующих классов непрерывных (в новом смысле) функций с хорошо известными классами непрерывных функций, такими, как топологически- и (о)-непрерывные функции, а также с классом функций, непрерывных по Скотту. Это приводит к возможности построения, на основе новых понятий непрерывности, теорий лямбда по методу Скотта — Койманса.

Показывается, что одно из новых понятий непрерывности функции, равно как и классическое понятие (о)-непрерывности, не может привести по методу Скотта — Койманса к построению лямбда-алгебры, отличной от вырожденной. Другие же понятия непрерывности приводят к лямбда-моделям, которые не изоморфны ни одной лямбда-модели Скотта, что, в частности, влечет то, что теоретико-множественные модели теории лямбда не исчерпываются с точность до алгебраического изоморфизма лямбда-моделями Скотта.

Киевский национальный университет им. Тараса Шевченко, Киев E-mail:foraal@mail.ru Мальцевские чтения 2009 Теория моделей Класс и множество как понятия формальной логики В. А. Одинцов Пусть L — язык, содержащий бинарные функциональные символы f и g, и пусть V — универсум языка L.

Определение 1. Язык L называется языком теории классов, а V называется формальным классом, если формулы (x)(y)(z)[f(x, y) =z x = y], (1) (x)(y)[x = y & g(x, y) =y &(z)(g(f(x, y), z) =f(x, y) z = f(x, y))] (2) являются нелогическими аксиомами L.

Определение 2. Язык L называется языком теории множеств, а V называется формальным множеством, если хотя бы одна из формул (x)(y)(z)[f(x, y) =z & x = y], (x)(y)[x = y], (x)(y)[g(x, y) = y], (x)(y)(z)[g(f(x, y), z) =f(x, y) &z = f(x, y)] является нелогической аксиомой L.

Теорема 1. Если V — формальный класс, то V содержит не менее трёх членов;

если V — формальное множество, то V содержит хотя бы один элемент.

Примеры формальных множеств приведены в следующей теореме.

Теорема 2. Если T формализует классическую систему аксиом для натуральных чисел (или аксиоматическую систему для полугрупп), то L(T ) — язык теории множеств.

Замечание 1. В случае полугрупп f = g.

Пусть C — универсум Кантора за вычетом пустого множества. Члены C — множества вида {a, b, c,...} — мы интерпретируем как неупорядоченные алфавиты, состоящие из попарно различных знаков a, b, c,... произвольного вида. Алфавиты вида {a} называются синглетами. Знак {a, b, c,...} называется метазнаком алфавита {a, b, c,...}.

Теорема 3. Если {a, b, c,...} {a, b, c,...} для всех алфавитов {a, b, c,...} и при этом f и g символизируют симметрическую разность и объединение в C, то формулы (1), (2) истинны в ;,.

Замечание 2. Левое {a, b, c,...} в теореме 3 понимается автонимно (как знак).

Язык L теории классов можно дополнить определёнными нелогическими аксиомами, в которых кванторы действуют по определённым подмножествам функций, отображающих класс V в себя, и которые истинны в модели ;,, дополненной соответствующими отображениями. Гипотеза континуума в расширенном языке будет теоремой.

Новоуральский государственный технологический институт, г.Новоуральск E-mail:odintzov@e1.ru Мальцевские чтения 2009 Теория моделей Сильно абелевы группоиды А. А. Степанова, Н. В. Трикашная В работе изучаются сильно абелевы группоиды. Напомним, что алгебра называется абелевой [1], если для любого терма t(x, y1,..., yn) и любых элементов a, b, c1,..., cn, d1,..., dn алгебры из равенства t(a, c1,..., cn) =t(a, d1,..., dn) следует t(b, c1,..., cn) = t(b, d1,..., dn). Алгебра называется сильно абелевой [1], если для любого терма t(x, y1,..., yn) и любых элементов a, b, e, c1,..., cn, d1,..., dn алгебры из равенства t(a, c1,..., cn) =t(b, d1,..., dn) следует t(e, c1,..., cn) =t(e, d1,..., dn). Ясно, что сильно абелева алгебра является абелевой. Одноэлементный группоид называется тривиальным.

В [2] описываются абелевы группоиды с единицей, абелевы конечные квазигруппы и полугруппы.

Непосредственно из определения сильно абелевой алгебры получаем следующие утверждения.

Утверждение 1. Не существует нетривиального сильно абелевого группоида с единицей.

Утверждение 2. Не существует нетривиальной сильно абелевой квазигруппы.

Напомним, что полугруппа A, · называется прямоугольной связкой [3], если A = {ei | i I, } и ei · ejµ = eiµ для любых i I,, µ. Полугруппа A, · называется раздуванием подполугруппы B, · [3], если существует разбиение {Xa | a B} множества A такое, что a Xa и x · y = a · b для любых a, b B, x Xa, y Xb.

Теорема. Полугруппа A, · является сильно абелевой алгеброй тогда и только тогда, когда A, · – раздувание прямоугольной связки.

Работа поддержана грантом ведущих научных школ РФ (грант НШ-2810.2008.1) и грантом Российского фонда фундаментальных исследований (проект 09-01-00336-а) Список литературы [1] Kiss E. W., Valeriote M. A. Abelian algebras and the Hamiltonian property. J. Pure Appl. Algebra, 87 (1993), N 1, 37–49.

[2] Степанова А. А., Трикашная Н. В. Абелевы и гамильтоновы группоиды. Фундаментальная и прикладная математика, в печати.

[3] Клиффорд А., Престон Г. Алгебраическая теория полугрупп, Т. 1,2. 1972.

ДВГУ, Владивосток E-mail:trik74@mail.ru Мальцевские чтения 2009 Теория моделей Naming an indiscernible set B. S. Bazhanov, J. T. Baldwin Let M be a stable structure in a language L and form an L(P ) =L-structure (M, A) by interpreting a new predicate P as the set A. When is the new structure stable Many people have used variants of the Hrushovski construction to find specific examples where the stability condition is preserved. But another line beginning with Poizat’s work on beautiful pairs goes in the direction of finding sufficient conditions on A for preservation. In [1], we considered subsets A of stable theories and introduced the notion of a pair being locally homogeneous or benign. We concentrate on naming a set of indiscernibles but greatly relaxing the conditions on M.

Definition (1) If I is an infinite set of indiscernibles in M such that for some infinite J M, I J is a set of indiscernibles, we say I has infinite codimension (in M); otherwise I has finite codimension.

(2) The pair (M, A) is small if for every finite sequence M, every L-type over A is realized in M.

(3) (M, A) is locally saturated if for any b M, for any L-formula ( y, ), any x, ( y, b)-type over A is realized in M.

x, Theorem 1. Suppose (M, I) is L(P ) - -saturated. The following are equivalent.

(1) (M, I) is locally saturated;

(2) I has infinite codimension;

(3) I is small.

It then follows easily from [2]:

Theorem 2. If M is stable, I is an infinite set of indiscernibles in M with infinite codimension then (M, I) is stable.

Theorem 3. Let I M be an indiscernible set and M be stable. Suppose (M, I) is -saturated in L(P ). The following are equivalent:

(1) I has finite codimension;

(2) For some, a canonically defined equivalence relation E has less than N classes that do not intersect I.

References [1] Baizhanov B., Baldwin J. Local Homogeneity. The Journal of Symbolic Logic, 69 (2004), N. 4, 1243– 1260.

[2] Baldwin J., Benedikt M. Stability theory, permutations of indiscernibles, and embedded finite models.

Transactions of The American Mathematical Society, 352 (2000), 4937–4969.

Institute of mathematics, informatics and mechanics, Almaty (Kazakhstan) Department of Mathematics, Statistics and Computer Science E-mail:baizhanov@hotmail.com University of Illinois at Chicago (USA) VI. Секция «Теория вычислимости» Мальцевские чтения 2009 Теория вычислимости Автоустойчивые булевы алгебры в атомно-идеальных обогащениях П. Е. Алаев Вычислимая структура A называется автоустойчивой (вычислимо категоричной), если для каждого её вычислимого представления B найдётся вычислимый изоморфизм f : A B. В докладе предлагается алгебраический критерий автоустойчивости для структур вида A =(A, I1,..., I, AtI,..., AtI ), 1 µ где A — булева алгебра, I1,..., I — предикаты для некоторых идеалов в A и AtI — j предикаты для множеств {x A | x/Ij — атом алгебры A/Ij}. Будем называть их I,µ-алгебрами. Ранее некоторое описание было найдено для ряда частных случаев I,µ-алгебр.

Для каждых, µ, где µ, определим конечное семейство I,µ-алгебр A1,..., An, которые назовём устойчивыми, так, что выполняется следующая Теорема. Вычислимая I,µ-алгебра автоустойчива тогда и только тогда, когда она изоморфна конечному прямому произведениюустойчивых алгебр.

Определение устойчивой I,µ-алгебры A требует нескольких промежуточных понятий. Пусть x A. Определим его характеристику Px : {1,..., } {0, 1, 2}:

0, если x Ij, Px(j) = 1, если x AtI и j µ, j 2, если x Ij, AtI.

j Скажем, что Px Py если Px(j) Py(j) для всех j. Элемент x разложим, если x = 0 или x = x1 +...+xn, где Px

i I,µ-алгебра A устойчива если верно следующее:

(1) 1 — неразложимый элемент в A;

(2) для каждой характеристики P верен один из случаев:

(i) каждый элемент характеристики P разложим в A;

(ii) каждый ненулевой элемент характеристики P неразложим в A;

(iii) P1 = P и 1/LP — атом.

(3) если P, Q — две характеристики такие, что P + Q = Q, и A содержит неразложимые элементы характеристики P, то под каждым неразложимым элементом характеристики Q найдётся неразложимый элемент характеристики P.

(4) если P — такая характеристика, что P + P = P, то верно одно из условий:

(i) x/LP — безатомный элемент для любого элемента x характеристики P ;

(ii) P1 = P и 1/LP — атом.

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

ИМ СО РАН, НГУ, Новосибирск E-mail:alaev@math.nsc.ru Мальцевские чтения 2009 Теория вычислимости Предельно монотонные функции и -представления M. В. Зубков Бесконечное множество A = {a0, a1, a2... } называется -представимым, если существует вычислимый линейный порядок L типа + a0 + + a1 + + a2 + +....

Если a0 a1 a2..., то A называется -представимым по неубыванию. Если же a0 < a1 < a2..., то A называется сильно -представимым. Функция F называется X-предельно монотонной, если существует X-вычислимая функция f(x, s) такая, что (x)(s)[f(x, s) f(x, s +1)] и (x)[F (x) = lim f(x, s)]. К. Харрис [1] доказал, что s множество является -представимым тогда и только тогда, когда оно является множеством значений некоторой 0 -предельно монотонной функции. С другой стороны, он же построил пример сильно -представимого множества, которое не является областью значений никакой возрастающей 0 -предельно монотонной функции, определeнной на. В работе А. Каца и Д. Турецкого [2] было предложено рассматривать псевдовозрастающие функции — функции, определенные на множестве рациональных чисел и возрастающие не на всей области определения, a на своем носителе.

Теорема 1. Если A сильно -представимое множество, то существует такая 0 предельно монотонная псевдовозрастающая функция H, что rang(H) T A.

Таким образом, тьюринговая степень -представима тогда и только тогда, когда она содержит множество, являющееся рангом некоторой 0 -предельно монотонной псевдовозрастающей функции.

Теорема 2. Каждое таблично сводящееся к 0 множество m-эквивалентно некоторому сильно -представимому множеству.

Теорема 3. Множество -представимо по неубыванию тогда и только тогда, когда оно 0 и -представимо.

Список литературы [1] Harris K. -Represetation of Sets and Degrees. Journal of Symbolic Logic, 73 (2008), 1097–1121.

[2] Kach A. M., Turetsky D. Limitwise Monotonic Functions, Sets and Degrees on Computable Domaine.

Journal of Symbolic Logic, принято к печати.

Казанский Государственный Университет, Казань E-mail:Maxim.Zubkov@ksu.ru Мальцевские чтения 2009 Теория вычислимости Создание базы данных по общей теории вычислимости И. А. Лавров Современная теория вычислимости включает в себя достаточно большое число направлений как по абстрактным, так и прикладным аспектам. Число научной литературы по Теории вычислимости (монографий и статей) постоянно растет. Ориентироваться в этой массе довольно затруднительно.

В настоящее время существуют различные варианты подобных баз, в основном на иностранных языках. Отметим некоторые из них:

• MathSciNet (выход только для членов AMS; российские ученые могут выходить лишь через некоторые институты РАН);

• CiteSeer (цитирования);

•http://nd.edu/cholak/computability/bib/bib.html;

•http://www.dblp.uni-trier.de(здесь имеются каталоги журналов) и др.

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

Отсутствуют и многие иностранные работы.

Цель создания данной базы состоит в том, чтобы специалисты в различных направлениях теории вычислимости имели достаточно полное на данный момент представление о многообразии научных исследований в этой непрерывно развивающейся области теории алгоритмов.

В настоящее время база размещена на сайте http://ispras.ru/ru/mathbibилиhttp://ispras.ru/publications.php.

В базу включены более 3200 известных составителю научных монографий и статей по теории рекурсии, степеням неразрешимости, элементарным теориям, иерархиям сложностей, обобщенным вычислениям и их приложениям. В меньшей степени указаны работы по вероятностным алгоритмам, реверсивной математике, полиномиальным алгоритмам, ряду обобщений вычислимости и приложениям в конкретных математических направлениях. В базе имеется более 850 работ, напечатанных на русском языке, 200 авторов. А также более 2350 работ, напечатанных на иностранных языках, 600 авторов. Автор не включал в базу, за редким исключением, неопубликованные работы и частные сообщения. Предполагается, что в базу будут вноситься необходимые коррективы и дополнения по мере их поступления. Автор будет признателен за все замечания и предложения, которые можно ему сообщать по адресу:

lavrov@ispras.ru.

По запросу поисковая система выдает список фамилий авторов, список работ конкретного автора, место и время опубликования, номер реферата в РЖ «Математика» или «Вычислительные науки», наличие ссылок в известных книгах Роджерса Х., Ершова Ю. Л., Odifreddi P., Соара Р. И. и Гончарова С. С., Ершова Ю. Л. Интересную статистику можно извлечь из данной базы. Например, вот список авторов по числу работ, включенных в базу (от 29 работ):

Pages:     | 1 |   ...   | 21 | 22 || 24 | 25 |   ...   | 29 |






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

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