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

РГБ ОД

РОССИЙСКАЯ АКАДЕМИЯ НАУК 7 2 ^¡¡д

УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

Сафин Константин Леонидович

Идеалы итеративных алгебр

01.01.06 — математическая логика, алгебра и теория чисел

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург, 2000

Работа выполнена на кафедре алгебры и дискретной математики Уральского государственного университета, в г.Екатеринбурге.

Научный руководитель:

Защита диссертации состоится 19 декабря 2000 года в 16 часов на заседании д иссертационного совета Д 002.07.03 при Институте математики и механики УрО РАН по адресу: 620219, г.Екатеринбург, ул.Софьи Ковалевской, 16.

С диссертацией можно ознакомиться в библиотеке Института математики и механики УрО РАН.

Автореферат разослав 19 ноября 2000 г.

Ученый секретарь

кандидат физико-математических наук, доцент Е.В.Суханов

Официальные оппоненты:

доктор физико-математических наук, профессор В.Б.Репницкий

доктор физико-математических наук, профессор Д.А.Бредихин

Ведущая организация:

Институт математики СО РАН

диссертационного совета к.ф.-м.н.

В Ш, £ оз

Общая характеристика работы

Тема данной диссертации относится к теории замкнутых классов функций А-значной логики (также позываемой "теорией клопов" и "теорией итеративных алгебр"). Эта теория берет свое начало в работах Э.Поста, которые были написаны в 20-40-х годах XX века. К настоящему времени она имеет собственную богатую проблематику и содержит большое число глубоких результатов. В Уральском государственном университете работы по изучению решетки замкнутых классов ведутся с начала 90-х годов. Обзору полученных за это время результатов посвящены работы [3,9].

Итеративной алгеброй на конечном множестве X называется совокупность всех конечноместных функций на X, замкнутая относительно суперпозиции функций, перестановок, отождествлений переменных функции и добавлений фиктивных переменных (см. [2]). Если итеративная алгебра содержит проекции, т.е. функции вида е'„(х1, ■■., г») = г/, то она называется клоном. Для алгебр, не удовлетворяющих этому условию, мы будем использовать термин "алгебра без проекций". Так как пересечение любого числа итеративных алгебр является итеративной алгеброй, то все они образуют полную решетку, которую мы будем обозначать через Сх- То же самое можно сказать и про множество всех клонов, подрешетку которых мы будем обозначать через Ссх. К сожалению, множество всех алгебр без проекций не образует решетку. Частично упорядоченное множество всех алгебр без проекций мы будем обозначать через

Поскольку операция суперпозиции является ассоциативной, на итеративную алгебру удобно смотреть как на полугруппу, наделенную дополнительными унарными операциями. Суперпозиция функций в дальнейшем обозначается через *.

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

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

тельными. ^ ----

Введем основное определение.

Определение 4 Подмножество Г С А мы называем идеалом итеративной алгебры А, если

1)1 — подалгебра в А;

2) I — идеал полугруппы {Л; *).

Оказывается, что собственные идеалы итеративной алгебры являются алгебрами без проекций. В связи с этим рассмотрению таких алгебр в дальнейшем отведено особое место.

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

Онределепяе 5 Итеративная алгебра А называется идеально простой, если она не содержит нетривиальные идеалов, т.е. из того, что I — идеал в А следует 1=0 или I — А.

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

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

В диссертации получены следующие теоретические результаты:

1) установлена связь между идеалами итеративных алгебр и алгебрами пар отношений определенного вида;

2) получено описание решеток идеалов некоторых известных классов итеративных алгебр;

3) доказано, что любая итеративная алгебра из некоторого класса является максимальной итеративной алгеброй без проекций;

4) установлена связь максимальных идеально простых итеративных алгебр с группами перестановок;

5) получено полное описание максимальных идеально простых итеративных алгебр функций ¿-значной логики при к <4.

Все перечисленные результаты являются новыми.

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

Основные результаты диссертации были представлены на Международной конференции по математической логике (Новосибирск, 1994 г.), Международной алгебраической конференции памяти Д.К.Фаддеева (Санкт-Петербург, 1997 г.), Международной математической конференции "Упорядоченные множества" (Варшава, 1999 г.), а также на семинарах Московского государственного университета н Новосибирского государственного университета, семинарах "Алгебраические системы" и "Дискретная математика" Уральского государственного университета. Они опубликованы в работах [4, 5, 6, 7, 8, 9]. Из совместной обзорной работы [9] в текст данной диссертации включены только результаты автора.

Диссертация состоит из двух глав, каждая из которых разбита на 4 параграфа. Основные результаты сформулированы в виде теорем 1-10. Общий объем диссертации составляет 81 страницу. Библиография содержит 39 наименований. Используется сквозная нумерация утверждений.

Краткое изложение основных результатов

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

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

В §1 рассмотрен вопрос о том, какую мощность может иметь решетка идеалов итеративной алгебры. Известно, что решетка подалгебр любой ктсративцой_алгебры имеет не более чем континуальную мощность, а значит, этим же свойством обладает и решетка-идеалов.—Следующее утверждение говорит о том, что решетка идеалов может иметь любую из возможных бесконечных мощностей.

Предложение 1

1) Существует алгебра, имеющая счетную решетку идеалов.

2) Существует алгебра, имеющая континуальную решетку идеалов.

Имеется соответствие Галуа между итеративными алгебрами и объектами, названными в диссертационной работе алгебрами пар отношений. Это соответствие является мощным инструментом при решении различных задач, связанных с итеративными алгебрами. В связи с этим можно рассмотреть вопрос о том, какие алгебры пар отношений при этом соответствии отвечают идеалам. Ответ на этот вопрос содержится в формулировке теоремы 1.

Пусть А — некоторая итеративная алгебра и — некоторое частично упорядоченное множество. Через /¿¡(Л) мы будем обозначать решетку идеалов алгебры А, а через ОЫ{0) — решетку порядковых идеалов множества

В §2 рассматриваются классы алгебр, часто возникающие естественным образом в исследованиях по данной тематике. Следующее предложение описывает решетку идеалов алгебры Рх всех функций на X. Пусть Т(Х) — множество всех непустых подмножеств основного множества X, упорядоченное по включению.

Предложение 2 Для алгебры Рх выполняется И1{Рх) = 01(1(Т(Х)).

Далее рассматриваются алгебры, состоящие из функций, предепши-мых полиномами определенного вида. Наделим множество X структурой ассоциативного кольца с единицей, это кольцо мы будем обозначать символом Л. Пусть Ьх — алгебра функций, представимых линейными полиномами над Я, т.е. полиномами вида а\Х1 + ... + а„х„ + во> где все а,- £ Л. Пусть также — множество всех смежных классов по всем правым идеалам кольца Л, упорядоченное по включению, т.е. <2л = {а + /|а 6 Л и / — правый идеал в Л}.

Теорема 2 Для алгебры Ьх выполняется 1<11{Ьх) == С>1<1((3д).

Пусть теперь множество X наделено структурой коммутативного моноида с единицей е. Через Мх обозначим алгебру функций, предсгави-мых мопомами над X, т.е. полиномами вида г"1... х"*, где все а,- > 0. Рассмотрим множество Т(Х) всем преобразований множества АГ. Зададим на Т{Х) структуру коммутативного моноида, определив для любых элементов / и д их произведение поточечно: (/ • д)(а) = /(а) • <?(а), где • — умножение в X, и а — произвольный элемент из X. Тогда единицей будет константное преобразование е(а) = е. Пусть М(Х) — моноид, порожденный в 7~(Х) тождественным преобразованием х, т.е. Л1(Х) = {ж0 = е, х, г2,..., х',..., х'-1}, где х' = х* для некоторых 1,з > 0 я з > I. Через ЭиЬ(М(Х)) обозначим множество подмонои-дов из М(Х), упорядоченное по включению. Справедлива следующая теорема.

Теорема 3 Для алгебры Мх выполняется 1с11(Мх) = 01с1(БиЬ(М(Х))).

Перейдем к изложению результатов §3. Он посвящен выяснению строения решеток идеалов алгебр вида Ро1(П), состоящих из функций, сохраняющих некоторое отношение К. Пусть V С X. Унарное отношение, соответствующее подмножеству и, мы также будем обозначать через и. Рассмотрим множество С^и = {(-¿г, Аг)\ 0 Ф А* С С X, А! С С и}, естественным образом упорядоченное отношением покомпонентного включения: (Л1( А2) < (А\, А'г) Ах С А\ и Л С А,.

Теорема 4 Для алгебры Ро1{1}) выполняется Ш(Ро1(и)) = ОЫ(С}и).

Пусть теперь а = {(ах,... ,о,)} — одноэлементное д - арное отношение на X. Рассмотрим множество = {А С Х|{а1,... С А}, упорядоченное по включению.

Теорема 5 Для алгебры Ро1(а) выполняется 1<&{Ро1(а)) ~ СН'<£(фв).

Пусть, наконец, /3 — отношение эквивалентности на X, не являющееся тотальным, и Вх и... и Вт — X — соответствующее ему разбиение. Рассмотрим множество

— {(/!,..., /га)|/, — порядковый идеал в и найдется ф

ф 0} = (о.а(р(в1)) X... х о^(7>(вт))) \ {0},

где 0 , 0) ^- шшменьп1ИЙ элемент декартова произведения. Это множество упорядочено как подмножестБо прямого^роизведенм упорядоченных множеств.

Теорема в Для алгебры Ро1(0) выполняется 1в.1(Ро1{Р)) 5= ОЫ(С}р).

В §4 приведены результаты, относящиеся к изучению итеративных алгебр без проекций. Для их изложения нам понадобится понятие стабилизатора. Пусть 5 — произвольная полугруппа преобразований на X. Стабилизатор полугруппы 5 — это множество Б^Б) = {/ € € N

и для любых 8х,...,5„ таких, что 8j € 5 или «¡(г) = х выполняется /(*!(*),...,*„(*)) 6 5}.

Предложение 3

1) Множество всех итеративных алгебр без. проекций образует в решетке ¿¿х порядковый идеал, не являющийся подрешеткой.

2) Каждая алгебра без проекций содержится в некоторой максимальной алгебре без проекций.

3) Каждая максимальная алгебра без проекций имеет вид 54(5), где Б — полугруппа несюреективных преобразований на X.

Затем в §4 доказывается предложение, утверждающее, что решетка клонов и множество алгебр без проекций устроены, в некотором смысле, "одинаково сложно".

Предложение 4 В частично упорядоченном множестве при т > > к существует интервал, изоморфный Си (а значит, существует также интервал, изоморфный С%).

Результаты, изложенные далее, посвящены алгебрам без проекций, являющимся аналогами максимальных клонов, и решению вопроса об их максимальности. Пусть на X определен частичный порядок. Полутруппу несюръективных преобразований, монотонных относительно этого порядка, будем обозначать через МТх• Тогда БЬ(МТх) — алгебра без проекций, являющаяся аналогом алгебры всех функций, монотонных относительно рассматриваемого порядка на X.

Предложение 5 ДуСТПг> трехэлементное множество X = {0,1,2} упорядочение естественным образом. Тогда алгебра без проекций БЬ{МТх) не является максимальной.

Пусть теперь 0 ^ II С X а — полугруппа, состоящая из всех песюръективных преобразований, сохраняющих множество и. Тогда З^Бх) — алгебра без проекций, являющаяся аналогом клона всех функций, сохраняющих множество и. Рассмотрим также алгебру А\{и) всех несюръективных функций, сохраняющих множество 17, алгебру А3(и) всех функций, которые сохраняют и и ограничения которых на ¿7 не-сюр-ьективны, и алгебру А(11) = А%(11) и А^(и).

Теорема 7

1) Если > 1, то ЗЬ^Б^) — максимальная алгебра без проекций и

2) Если \и\ = I, то 54(5^) — алгебра без проекций, не являющаяся максимальной.

В главе 2 основное внимание уделено изучению идеально простых итеративных алгебр- Далее ради краткости изложения мы в основном будем говорить "простая" вместо "идеально простая".

В §5 исследуются свойства простых алгебр, являющиеся основными для дальнейшего изложения.

Предложение 6 Алгебра А проста тогда и только тогда, когда для любых функций /, <7 € А выполняется равенство 1т/ = 7тд.

Эта теорема имеет два важных следствия.

Следствие 1 Для любой алгебры С эквивалентны следующие условия:

1) С — простой клон;

2) для любой функции / ЕС выполняется равенство 1т/ = X;

3) СМ — группа перестановок на X.

Следствие 2 Множество всех простых алгебр

1) является порядковым, идеалам в Сх;

2) удовлетворяет условию леммы Дорна.

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

--Введоасобозначения, необходимые для формулировки следующего

предложения. А ииенно7если ^^^т1одмножсство ьшожества_х, и Р— подмножество в Ро1(р), то через мы будем обозначать подмножество {/¡и | / £ множества Рц. Если й — множество функций из Ри, то через [С] здесь обозначается множество {<? 6 Рх 15(1/ € С?}-

Предложение 7

1) Пусть I/ С X и С — максимальный простой клон в Ри. Тогда [С] — максимальная простая алгебра.

£) Обратно, если А — максимальная простая алгебра в Рх и II = — 1т,А, то А = и А[и — максимальный простой клон в Рц.

Отсюда следует, что дая нахождения всех максимальных простых алгебр в Рх достаточно найти все максимальные простые клоны в Ри, где и С X.

В §6 исследуются свойства простых клонов и устанавливается тесная связь между этими свойствами и свойствами групп перестановок на X. В связи с этим нам потребуются обозначения для некоторых групп перестановок. Пусть X = {а!,..., а*} — некоторое перечисление элементов множества X. Введем обозначения:

5х или Б/, — для группы всех перестановок на множестве X, Ак — для знакопеременной группы на множестве X, С к — ((а1,..., сц)) — для циклической подгруппы группы Бь, порожденной циклом длины к,

Зъ — для единичной подгруппы в В случае к — А:

V — {¿¿Х1(а1аа)(а»а4),(а1а5)(а2а4),(а1а4)(агвз)} — четверная группа Клейна,

= {¿¿хДсцва), (в1а4), (а1а2)(аза4), (о1а3)(а3а4), (о1а4)(огоз), (а^з

ва<ь4), (ахсцагаз)} — сплетение группы 5г при помощи группы 32.

Нетрудно понять, что все максимальные простые клоны в Рх имеют вид БЬ{С), где й — некоторая подгруппа в Бх- Такие подгруппы й мы будем называть подходящими. Пусть X — Х\ и ... и Хт — разбиение основного множества X на непустые подмножества.

Предложение В Пусть О,- — группы перестановок, транзитиано действующие на X,-, где г = 1,..., т. Прямое произведение С? 1... (7ГО является подходящей группой тогда и только тогда, когда таковой является каждая из подгрупп С?,-.

Предложение 9 Пусть С — максимальная подгруппа в 5х- Группа С? является подходящей тогда и только тогда, когда она несмсимающая.

Предложение 10 Если группа перестановок С регулярна, то она является подходящей.

Определения сжимающей и регулярной групп приведены в диссертационной работе на с.59 и с.61 соответственно.

Далее в §7 приводится полное описание подходящих подгрупп в случае к < 4.

Теорема, 8 Подходящими подгруппами в 3] являются в точности группы Зг и 5а.

Теорема 9 Подходящими подгруппами в З3 являются в точности группы вида /з, 5^52, С\ и Бг.

Теорема 10 Подходящими подгруппами в являются в точности группы вида Л, 515152, 5гС3, V, 323,, С4, 5^3, } 54.

Эти теоремы позволяют получить полное перечисление максимальных простых алгебр для случая к <4.

Наконец, в §8 приводятся некоторые заключительные замечания и формулировки вопросов, относящиеся к проблематике идеалов итеративных алгебр.

Таковы основные результаты диссертации.

Работа выполнена под руководством доцента Евгения Витальевича Суханова, которому автор очень признателен за постоянное внимание и всестороннюю поддержку.

Литература

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

[2] Мальцев А.И. Итеративные алгебры Поста, Новосибирск, 19767"

[3] 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.Lüders), Heldermann Verlag, Berlin, 1995, 27-34.

Работы автора по теме диссертации

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

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

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

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

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

[9] Bulatov A.A., Krokhin A.A., Safin K.L., Semigrodskikh A.P., Sukhanov E.V. On the structure of clone lattices II, Multipli-Valued Logic (принята к печати)

Содержание.

Введение.

Глава 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 приведены некоторые соображения по развитию данной проблематики и поставлены вопросы, нахождение ответов на которые представляется автору небезынтересным.

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.