Идеалы итеративных алгебр тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Сафин, Константин Леонидович

• Сафин, Константин Леонидович
• кандидат физико-математических наук
• 2000

Оглавление диссертации кандидат физико-математических наук Сафин, Константин Леонидович

Содержание.

Введение.

Глава 1. Идеалы итеративных алгебр и их основные свойства.:.

§1 Отношения Грина и идеалы итеративных алгебр.

§2 Идеалы алгебр, заданных описанием входящих в них функций

§3 Идеалы алгебр, заданных некоторыми отношениями

§4 Алгебры без проекций.

Глава 2. Итеративные алгебры с ограничениями на множество идеалов.

§5 Простые итеративные алгебры и их основные свойства —

§6 Связь простых итеративных алгебр с группами перестановок .•. —

6.1 Транзитивные группы перестановок.

6.2 Сжимающие группы перестановок.

6.3 Регулярные группы перестановок.

§7 Описание простых итеративных алгебр функций fc-значной логики при к < 4.

§8 Заключительные замечания.

Введение диссертации (часть автореферата) на тему «Идеалы итеративных алгебр»

1° Тема данной диссертации относится к теории замкнутых классов функций к-значной логики (также называемой "теорией клонов" и "теорией итеративных алгебр"). Эта теория берет свое начало в работах Э.Поста [28, 29], которые были написаны в 20-40-х годах XX века. К настоящему времени эта теория имеет собственную богатую проблематику и содержит большое число глубоких результатов. Имеющаяся литература весьма обширна, поэтому мы упомянем здесь лишь несколько книг обзорного характера [12, 20, 27, 31, 32].

Значительная часть работ в этой области посвящена изучению строения решетки, которую образуют замкнутые классы, а также ее отдельных частей. Это обусловлено тем, что многие задачи классификации замкнутых классов, а также многие вопросы, касающиеся их строения, можно сформулировать на языке свойств этой решетки. Так, например, замкнутый класс имеет конечный базис тогда и только тогда, когда каждый его подкласс содержится в некотором максимальном, и этих максимальных подклассов конечное число. Далее, подмножество конечно-порожденного замкнутого класса является его порождающим множеством в том и только в том случае, когда оно не содержится ни в каком максимальном подклассе этого класса.

В Уральском государственном университете работы по изучению решетки замкнутых классов ведутся с начала 90-х годов. Обзору полученных за это время результатов посвящены работы [19, 39]. Заметное внимание при этом уделялось замкнутым классам функций, представи-мых многочленами. Здесь стоит отметить диссертационную работу [4], часть которой посвящена классификации замкнутых классов функций, представимых линейными полиномами, а также работу [13], в которой было дано описание интервала в решетке замкнутых классов, образуемого классом всех линейных функций и классом всех многочленов над конечным полем. В этом же русле лежит и совместная работа [7].

Здесь, однако, сделана попытка взглянуть на теорию замкнутых классов с несколько иных позиций. Одной из дисциплин, с которой эта теория имеет глубокие взаимосвязи, является универсальная алгебра. Так, многие свойства алгебраической системы не зависят от выбора основных операций, а определяются ее клоном термальных операций. Этот подход является основопологающим в работах [20, 32]. Однако имеется и взаимосвязь иного рода между теорией замкнутых классов и универсальной алгеброй. Как было замечено А.И.Мальцевым в его работах [10,11], на множестве функций можно ввести несколько операций таким образом, что это множество будет замкнутым классом в точности тогда, когда оно будет замкнуто относительно этих операций. Это означает, что замкнутые классы, наделенные вышеупомянутыми операциями, естественно рассматривать как алгебры, которые были названы А.И.Мальцевым "итеративными алгебрами". К тому же, так как одной из этих операций является суперпозиция функций, обладающая свойством ассоциативности, а остальные связаны с различными преобразованиями переменных функции, и имеют вспомогательный, технический характер, то на итеративную алгебру естественно смотреть как на полугруппу с несколькими дополнительными операциями. Одним из достоинств такого подхода к понятию замкнутого класса стала возможность переформулировки достаточно сложных комбинаторных определений и утверждений в ясных алгебраических терминах, что и было сделано в [12].

Здесь будет уместным сказать, что теория полугрупп развивалась во второй половине XX века очень интенсивно и в исследованиях в этой области был накоплен обширный материал. Имеется несколько фундаментальных монографий, посвященных полугрупповой проблематике. Так, в монографии [б] основное внимание уделяется структурной теории полугрупп. В книге [9] рассматриваются различные полу групповые приложения в теории автоматов и формальных языков. Монография [16] посвящена изучению взаимосвязей теории полугрупп и теории решеток. Наконец, справочник [1] содержит современное изложение основных полугрупповых понятий и результатов.

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

2° Введем необходимые обозначения, определения и дадим некоторые комментарии к ним. Всюду в дальнейшем мы будем рассматривать некоторое фиксированное конечное множество X мощности к. Через Рх обозначается множество всех конечноместных функций (или операций) на X. Среди прочих функций мы будем особо выделять проекции, т.е. функции вида е{п(хх,. ,хп) = Х{. Множество всех проекций мы будем обозначать через Ех. Если F С Рх, то через F^ мы будем обозначать множество всех n-арных функций из F, и называть его n-м слоем множества F. Рассмотрим на множестве Рх операции т, Д, V и *, определенные следующим образом: для любых f{x 1,., хп),д(хi,., xm) € Рх полагаем

С/)(®1> ®2, ■ • ■ , хп) = Я3, . . • , хп, Да), (rf)(x 1,Х2,.,Хп) = f(x2,Xi,. .,£„), (Д/)(*1 О = /(жьЖ1,х2,.,а;„1), при п > 1 и С/ = т/ = А/ = / при n = 1, * ■ ■ * ? = f(9{x l,.,Xm), Xm+1, . . . Xm+„i).

Определение 1 Подмножество А С Px, замкнутое относительно операций С, г, А, V и *, называется итеративной алгеброй.

Эквивалентное определение можно дать следующим образом.

Определение 2 Множество А С Рх называется итеративной алгеброй, если для любой функции f(xi,., хп) из А и любых функций fi(xi,., хт),., fn{xi,. ,хт), каждая из которых является либо функцией из А, либо проекцией, выполняется условие f(fi(xi,. ,хт), ■ • ■ > fn(x 1,., хт)) £ А.

Если итеративная алгебра содержит проекции, то она называется клоном. Для алгебр, не удовлетворяющих этому условию, мы будем использовать термин " алгебра без проекций". Так как пересечение любого числа итеративных алгебр является итеративной алгеброй, то все они образуют полную решетку, которую мы будем обозначать через С х-То же самое можно сказать и про множество всех клонов, подрешетку которых мы будем обозначать через Ссх. В большом количестве работ по теории клонов эта решетка является основным объектом исследования. Среди наиболее ярких результатов можно отметить результат И.Розенберга, посвященный описанию всех коатомов решетки Ссх (см. [30]). К сожалению, множество всех алгебр без проекций не образует решетку. Частично упорядоченное множество всех алгебр без проекций мы будем обозначать через Сх. В тех случаях, когда нам не важно, из каких элементов состоит множество X, а важно лишь количество его элементов, наряду с обозначениями, в которых присутствует индекс X, мы также будем пользоваться обозначениями, в которых вместо этого индекса используется индекс к (Р^, Ck и пр.). Наименьшая алгебра, содержащая множество функций F С Рх, обозначается через (F). Через Im f мы будем обозначать образ функции /, а через NSx — множество всех несюръективных функций из Рх

Нам понадобится соответствие Галуа между итеративными алгебрами и объектами, которые будут введены далее. Это соответствие является мощным инструментом при решении различных задач, связанных с итеративными алгебрами. Например, с его помощью был получен вышеупомянутый известный результат И.Розенберга (см. [30]). В последнее время соответствие Галуа нашло неожиданное применение в исследованиях, посвященных анализу сложности алгоритмов (см. [25]). В работах [2, 3] такое соответствие было построено между множеством всех: клонов и множеством подходящих алгебр отношений. Затем, в работах [21, 22, 23] было дано обобщение на случай произвольных итеративных алгебр. Последний результат также был независимо получен автором (см. [38]) и использован при получении других результатов. Поэтому, для удобства дальнейшего изложения, будут приведены формулировки (без доказательств), использованные автором, хотя в некоторых местах они отличаются от данных в [21, 22, 23] незначительными техническими деталями. Вместе с тем, по мнению автора, эти изменения делают последующие рассуждения несколько более простыми.

Перечислим некоторые операции над отношениями, введенные в [2, 3], которые понадобятся нам для дальнейшего. Обозначения некоторых операций совпадают с обозначениями операций итеративных алгебр, но это не приведет к неоднозначности толкования, поскольку всегда ясно, к какому объекту (функции или отношению) применяется операция. Пусть R С Хп и Т С Хт — произвольные отношения на множестве X арностей пит соответственно.

Из всех возможных операций перестановки координат отношения удобно оставить операцию циклической перестановки и операцию транспозиции, которые мы будем обозначать через С и т соответственно. А именно, для любого набора а =

01 ^ ( °2 ^ ( а2 \

2 £ Хп положим (а = ; ах та = «п / \ «1 / \ ап У пр и п > 2 и

Сй = та = а при п — 1.

Через (R мы будем обозначать множество {С,а\а е R}, а через tR — множество {та\а € R}.

Из всех операций диагонализации удобно оставить диагонализацию по первой и второй координате, которую мы будем обозначать через А. А именно, через AR мы будем обозначать множество а = аг \ 02

G Я)а1 = при п > 2 и ап / само множество R при п = 1.

Из всех операций проектирования оставим операцию вычеркивания первой координаты, которую будем обозначать через рг. А именно, для любого набора л ач а =

Е Хп положим рга = ап ; рга ~ а при п = 1. 0,2 \ ап при п > 2 и

Через prR мы будем обозначать множество {pra\a € R}.

Операция декартова произведения, как обычно, будет обозначаться через х. Для любых наборов а = ai \ а2 ап / ехп иЪ = h\ h ьп ) Хт положим а х b — ах \

On h

Ьт )

6 хп+т.

Через RxT мы будем обозначать множество {о xb\a € R и b € Т}.

Из всех нульарных операций оставим операцию взятия унарного отношения X. Ее мы также будем обозначать через X.

Как было показано в [2, 3], с помощью операций С> r> A, W, х> X можно реализовать любые перестановки координат, диагонализации (отождествления координат), приписывания фиктивных координат, вычеркивания координат (проекции) и дублирования координат данного отношения, декартово произведение данных отношений, а также получить все диагонали из отношения X.

Перейдем к построению соответствия Галуа для итеративных алгебр и объектов, соответствующих итеративным алгебрам. Будем рассматривать пары отношений (R, R') одинаковой арности на множестве X, такие, что R 2 R'- Множество всех таких пар будем обозначать через Rx-Определим на множестве Rx операции С, r> A, pr, х и X, действующие на парах отношений покомпонентно (нульарной операции X соответствует нульарная операция Е — пара (X, X)). Нетрудно заметить, что перечисленные операции, определенные на отношениях, сохраняют включение, поэтому их действие на парах определено корректно. Кроме того, введем на множестве Rx отношение частичного порядка < следующим образом: (R, R') < (S, S') & R С S и R! D S'. Будем рассматривать систему (Rx : С,т, А,рг, х,Е;<).

Определение 3 Подмножество I множества Rx будем называть алгеброй пар отношений, если

1)1 — подалгебра алгебры (Rx : (,r,A,pr, х,Е);

2) I — порядковый идеал упорядоченного множества (Rx '■<)■

Рассмотрим произвольную п- арную функцию /, га-арное отношение R и матрицу

М = «и «21

12 «22

In \ «2я «ml агп2 г, любой столбец которой «1 * Л

2г \ «mi / является набором из отношения R (такие матрицы называются Д-матрицами). Определим образ матрицы М при действии функции /: f(M) = / «11 «12 ■ • ■ «In V ( /(«11, • ■ • j «In) \

21 «22 ••■ «2П /(«21, •■-,0,211) К «ml «щ2 • • • «mn / \ /(«ml, • • •, «тога) /

Будем говорить, что функция / сохраняет пару (R, R'), если образ любой R - матрицы при действии функции / является набором из R'. Отношение "функция сохраняет пару" порождает соответствие Галуа. При этом замкнутые множества в Рх, отвечающие подмножествам G С Rx, мы будем обозначать через Pol(G), а замкнутые множества в Rx, отвечающие подмножествам F С Рх, мы будем обозначать через Inv(F) (см. [32]). Справедливы следующие утверждения.

Подмножество А С Рх является замкнутым тогда и только тогда, когда оно является итеративной алгеброй.

Подмножество I С Rx является замкнутым тогда и только тогда, когда оно является алгеброй пар отнощений.

Рассмотрим пары вида (R,R). Пусть I — алгебра, состоящая лишь из пар такого вида. Тогда отображение (Я, Я) ь» Я переводит I в некоторое множество отношений. Нетрудно понять, что оно является алгеброй отношений в смысле [2, 3]. Имея в виду сказанное выше, далее вместо Pol((R, Я)) мы будем писать Pol(R).

Легко проверить, что для любой алгебры А множество всех ее одноместных функций il^ является полугруппой преобразований на X. Пусть S — произвольная полугруппа преобразований на X. Стабилизатор полугруппы S — это множество St(S) = {/ € Рх\п € N и для любых s'i,., sn таких, что Si € S или Sj(x) = х выполняется f(si(x),., sn(x)) е S}. Это понятие цод названием "нормализатор" было введено в [12] и достаточно подробно исследовалось в диссертационной работе [8]. Нетрудно проверить, что St(S) — итеративная алгебра, и что (S) С St{S). Хорошо известно, что для любой итеративной алгебры А равенство А& = S выполняется тогда и только тогда, когда (S) С А С St(S) (см. например [32], с.74).

3° Основное место в данной диссертации уделено понятию идеала. В главе 1 вводится это понятие, а также приводятся результаты, описывающие решетки идеалов для некоторых известных классов итеративных алгебр. При этом выясняется, что основную их часть составляют алгебры без проекций, в связи с чем в §4 приводятся некоторые утверждения о свойствах таких алгебр. В главе 2 основное внимание уделено изучению идеально простых итеративных алгебр, т.е. алгебр, не содержащих нетривиальных идеалов. В заключении, в §8 приведены некоторые соображения по развитию данной проблематики и поставлены вопросы, нахождение ответов на которые представляется автору небезынтересным.

Список литературы диссертационного исследования кандидат физико-математических наук Сафин, Константин Леонидович, 2000 год

1. Артамонов В.А., Салий В.Н., Скорняков Л.А., Шеврин Л.Н., Шуль-гейфер Е.Г. Общая алгебра, т.2 -М.: Наука, 1991.

2. Боднарчук В.Г., Калужнин JI.A., Котов В.Н., Ромов Б.А. Теория Галуа для итеративных алгебр Поста, I, Кибернетика 3, 1969, 1-10.

3. Боднарчук В.Г., Калужнин Л. А., Котов В.Н., Ромов Б.А. Теория Галуа для итеративных алгебр Поста, II, Кибернетика 5, 1969, 1-9.

4. Булатов А.А. Алгебраические свойства решетки клонов (диссертация), Екатеринбург, 1995.

5. Гретцер Г. Общая теория решеток, М.: Мир, 1982.

6. Клиффорд А., Престон Г. Алгебраическая теория полугрупп, т.1,И. -М.: Мир, 1972.

7. Крохин А.А., Сафин К.Л., Суханов Е.В. О строении решетки замкнутых классов полиномов, 9, 2, 1997, 24-39

8. Крохин А.А. Интервалы в решетках клонов (диссертация), Екатеринбург, 1998.

9. Лаллеман Ж. Полугруппы и комбинаторные приложения. -М.: Мир, 1985.

10. Мальцев А.И. Итеративные алгебры и многообразия Поста, Алгебра и логика, 5, 2, 1966, 3-9.

11. Мальцев А.И. Об одном усилении теорем Слупецкого и Яблонского, Алгебра и логика, 6, 3, 1967, 61-74.

12. Мальцев А.И. Итеративные алгебры Поста, Новосибирск, 1976.

13. Семигродских А.П., Суханов Е.В. О замкнутых классах полиномов над конечными полями, Дискретная математика, т.9, вып.4, 1997, 50-62.

14. Смирнов Д.М., Рейбольд А.В. Решетки конгруэнц-классов алгебр // Алгебра и логика, 23, 6, 1984, 684-701.

15. Смирнов Д.М. О вложении решеток в решетки блоков // Сиб. мат. журн., 33, 2, 1992, 128-134.

16. Шеврин JI.H., Овсянников А.Я. Полугруппы и их подполугруппо-вые решетки, Ч. 1,2, Свердловск, Издательство Уральского университета, 1990.

17. Яблонский С.В. Введение в дискретную математику, Изд. 2-е, пере-раб. и доп., М.: Наука, 1986.

18. Bulatov А.А. On the semigroup property of clones, Int. conf. "Semigroups and their applications, including semigroup rings" in honour of E.S.Ljapin, St.-Petersburg, Russia, 1995, 8-9.

19. Bulatov A.A., Krokhin A.A., Safin K.L., Sukhanov E.V. On the structure of clone lattices, General Algebra and Discrete Mathematics (eds: K.Denecke, O.Liiders), Heldermaim Verlag, Berlin, 1995, 27-34.

20. Denecke K. Preprimal Algebras, Akademie-Verlag, Berlin, 1982.

21. Harnau W. Ein verallgemeinerter Relationenbegriff fiir die Algebra der mehrwertigen Logik, Teil I (Grundlagen), Rostock. Math. Kolloq. 28, 1985,5-17.

22. Harnau W. Ein verallgemeinerter Relationenbegriff fiir die Algebra der , mehrwertigen Logik, Teil II (Relationenpaare), Rostock. Math. Kolloq.31, 1987, 11-20.

23. Harnau W. Ein verallgemeinerter Relationenbegriff fiir die Algebra der mehrwertigen Logik, Teil III (Beweis), Rostock. Math. Kolloq. 32, 1987, 15-24.

24. Ihringer Th. A remark on clones and permutation groups, Contributions to general algebra 7, Proc. Conf. Vienna, Wien, Verlag Holder-Pichler-Tempsky, 1990, 197-200.

25. Jeavons P. On the algebraic structure of combinatorial problems, Theor. Сотр. Sci., 200, 1998,185-204.

26. Palfy P.P., Szendrei A. Unary polinomials in algebras. II, Contributions to general algebra 2, Proc. Conf. Klagenfurt, Wien, Verlag Holder-Pichler-Tempsky, 1982, 273-290.

27. Poschel R., Kaluznin L.A. Funktionen- und Relationenalgebren, Ein Kapitel der diskreten Mathematik, Berlin: VEB DVW, 1979.

28. Post E. Introduction to a general theory of elementary propositions// Arner. J. Math., 1921, v.43, p.163-185.

29. Post E. Two-valued iterative systems of mathematical logic.- Ann. Math. Stidies 5, Princeton Univ. Press, 1941.

30. Rosenberg I.G. Uber die funktionale Vollstandigkeit in den mehrwertigen Logiken (Struktur der Funktionen von mehreren Veranderlichen auf endlichen Mengen), Rozpravy Ceskoslovenske Akad. Ved. Rada Mat. Pnrod. Ved., 80, 1970, 3-93.

31. Schweigert D. Hyperidentities, Universitat Kaiserslautern, Fachbereich Matematik Erwin-Schrodinger-Strabe 6750 Kaiserslautern, Mai 1992.

32. Szendrei A. Clones in universal algebra, Seminaire Math. Superieures 99, Les Presses de rUniversite de Montreal, 1986.

33. Zichwolff M. Darstellung symmetrischer Strukturen durch Transversale, Contributions to general algebra 7, Proc. Conf. Vienna, Wien, Verlag Holder-Pichler-Tempsky, 1990, 391-403.

34. Сафин К.JI. Идеалы итеративных алгебр, в кн: Междунар. конф. по математической логике. Тез.докл., Новосибирск, 1994, 89.

35. Сафин К.Л. Идеалы итеративных алгебр, Сиб.мат.журнал, 36, 6, 1995, 1384-1391.

36. Сафин К.Л. Об изоморфных вложениях решеток итеративных алгебр, в кн: IV Междунар. конф. по алгебре памяти Д.К.Фадцеева. Тез.докл., Санкт-Петербург, 1997, 274.

37. Сафин К.Л. Простые итеративные алгебры, Алгебра и логика, 37, 4, 1998, 460-477.

38. Сафин К.JI. Соответствие Галуа для итеративных алгебр, Между-нар. алгебр, конф. памяти А.Г.Куроша, Москва, 1998, 206-207.