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



УРАЛЬСКИЙ ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ООУЯАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. А.М.ГОРЬКОГО

- 8 МАЙ 1995

УДК 512.577

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

БУЛАТОВ Андрей Арнольдович

Алгебраические свойства решетки клонов

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

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

кандидат физико-математических наук, доцент Е.И.Клейман

Московский университет

государственный

Защита диссертации состоится 1995 года в 15 ча-

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

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

Автореферат разослан «Л? » <•'<-А. 19ШГг.

Ученый секретарь диссертационного совета

д.ф.-м.н., профессор А. С. Кондратье)

Клоном функции на (конечном) множестве А называется класс функций на Л, замкнутый относительно суперпозиции, а также содержащий все функции вида е'п{х\,... = Все клоны функций на А с отношением включения образуют решетку, обозначаемую С а или Ск: где к = | А|. Беря свое начало в работах А.Поста первой трети нашего века, теория клонов плодотворно развивалась и к настоящему времени обрела четкие контуры, собственную богатую проблематику п содержит большое число результатов.

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

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

После работ Янова, Мучника и Марчевского, показавших существование клонов без конечного порождающего множества., а также континуальность решетки Си для к > 3, практически не осталось надежд па получение сколь-нпбудь полного описания решеток Си при к > 3. сравнимого с постовским описанием Сп. Тем более важным представляется изучение различных частных свойств решетки клонов. Большую часть широкого спектра задач, возникающих при этом, можно сгруппировать в два направления.

Первое направление касается общих свойств решетки. Среди первостепенных задач этого типа задача нахождения класса подреше-ток решеток и тесно связанная с ней задача о выполнимости в решетках клопов нетривиальных тождеств и квазптождеств. До сих пор был известен лишь один абстрактный класс решеток, изоморфно вложнмых в С}:. к > 3. А именно, Хадцад и Розенберг нашли в Сз интервал, изоморфный булевой алгебре всех подмножеств счетного множества. Отсюда вытекает вложпмость в Сз любой счетной дпс-

трнбутнвной решетки. Кроме того, несложно проверяется, что любая конечная решетка вкладывается в Ск для подходящего к. Это влечет невыполнимость на классе всех решеток Ск никаких нетривиальных тождеств н квазптождеств. Нерешенным оставался вопрос о справедливости этого свойства для каждой из решеток Л > -3.

Ко второму направлению относятся задачи исследования и классификации клонов некоторых конкретных типов. Изучение клонов одного из таких типов, а именно, клонов полиномиальных функции конечного модуля — одна из наиболее старых областей теории клонов, она восходит к работам С.В.Яблонского, а также А.Саломаа, исследовавших замкнутый класс линейных функций над кольцом вычетов. Пусть М — конечный модуль над ассоциативно-коммутативным кольцом R с единицей. Через ¿д/ обозначается клон всех полиномов модуля М, гь через Sub Lm — решетка его подклонов. А.Сендрен и Д.Лау доказали, что Sub Lm не более чем счетна, при этом она конечна тогда и только тогда, когда R является прямой суммой полей. В последнем случае Sub Lm полностью описана. В случае, когда Sub ¿д/ бесконечна, известны лишь некоторые ее части (решетка клонов идемпотентных функций и решетка клонов, содержащих мальцевскую функцию х — у + г). В то же время, не имелось никакого целостного представления о решетке Sub Lm в общем случае.

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

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

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

доказано, что решетки Ск при к > 3 не удовлетворяют некакому нетривиальному тождеству, а при к >4' — квазитождеству;

найдены обширные классы решеток, вложпмых в решетки клонов; в частности, показано, что любая конечная решетка изоморфно вложима в С к для к > 4;

предложен новый подход к изучению решетки Sub £д/, основанный на разбиении ее на 4 класса, и указаны свойства трех из них, основываясь на этом разбиении, найдены все коатомы решетки Sub Lm ;

исследовано строение четвертой из указанных выше частей решетки Sub Lm, в частности, полностью описана некоторая ее ключевая подрешетка.

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

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

Основные результаты работы докладывались на III Международной конференции по алгебре (Красноярск, 1993 г.), Международной конференции по математической логике (Новосибирск, 1994 г.), а также па семинарах "Алгебра п логика" и "Алгебраические системы" Института математики СО РАН и Новосибирского государственного университета, семинаре "Дискретная математика" Московского государственного университета, семинаре "Алгебраические системы'" Уральского государственного университета. Они опубликованы в работах [6]—[11].

Диссертация состоит из введения, двух глав, разделенных на 8 параграфов и содержит 8 теорем. Общий объем диссертации составляет 104 страницы. Библиография содержит .37 наименований. Используется сквозная нумерация параграфов п утверждений.

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

свободная полугруппа со счетным множеством свободных порождающих и ее подполугрупповая решетка. В [1] показано, что Sub не удовлетворяет никаким нетривиальным решеточным тождествам. Учитывая этот факт, полный ответ на вопрос о выполнимости тождеств в решетках клонов дает первая часть следующего утверждения, доказываемого в первом параграфе.

Теорема 1 Решетка Sub изоморфно вложима в

(1) £3 при п = 1;

(2) С а при п = 2.

Следствие 1 Решетка £;., к > 3, не удовлетворяет никакому нетривиальному решеточному тождеству.

Часть (2) теоремы 1 дает, на самом деле, вложение в £4 всех решеток вида Sub Тп для п Е N п решетки Sub поскольку, как хорошо известно, Sub изоморфно вложима в Sub Т->. Семейство подрешеток из Sub исследовалось в ['2, 3]. В частности, там показано, что абсолютно свободная решетка счетного ранга вложима в Sub Тш н описан класс конечных подрешеток из Sub Поэтому по теореме 1 конечные решетки из этого класса и абсолютно свободная решетка счетного ранга изоморфно вложимы в £4.

Следующая теорема является центральным результатом первой главы. В частности, она максимально расширяет класс конечных решеток, вложпмых, согласно части (2) теоремы 1, в решетку £4. Доказательству теоремы 2 посвящены §2 и 53.

Теорема 2 Решетка, являющаяся не более чем счетным прямым произведением конечных решеток, изоморфно вложима с £4.

Приведем несколько следствий пз этой теоремы. Прежде всего, теорема '2 дает нам широкий класс континуальных подрешеток в £4. Однако, для него сложно указать характернзацшо в каких-либо привычных терминах. Если же мы ограничимся счетными решетками, то получим хорошо известный класс фшштно-аппрокснмпруемых решеток.

Следстпис 2 Любая счетная финитно-аппроксимируемая решетка изоморфно вложима в £к, к > 4.

Кроме того, можно указать серию конкретных весьма богатых решеток, вложпмых в решетки клонов. А именно, известно, что финитно-аппроксимируемой является решетка, свободная в многообразии решеток, порождаемом своими конечными членами. Отсюда мы получаем следующую серию примеров подрешеток в £4. Пусть X— многообразие решеток, порождаемое своими конечными членами. К числу таковых относится, например, любое локально-конечное многообразие.

Следствие 3 Свободная в X решетка счетного ранга изоморфно вложима в Ск, к > 4.

Отметим еще, что многообразие всех решеток порождается конечными решетками, а потому вложпмость в £4 абсолютно свободная решетки счетного ранга вытекает из следствия 3 без использования результатов ['2, 3].

Непосредственно из теоремы 2 вытекает и решение проблемы о конечных подрешетках решеток клонов.

Следствие 4 Любая конечная решетка изоморфно вложгша в Ск, к > 4.

Из этого утверждения непосредственно выводится и

Следствие 5 В Ск, к > 4, не выполняются никакие нетривиальные решеточные квазитоэкдестса.

Несмотря на широту класса решеток, указанных в теоремах 1 и 2, остаются пока нерешенными ряд вопросов, связанных с вложн-мостью. Их обсуждению посвящен параграф 4.

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

ассоциативно-коммутативным кольцом R с едшшцеП. В пятом параграфе мы определяем нижние границы частей, на которые разбп-ватся решетка Sub Ьм ■ С этой целью описываются атомы в Sub Ьм н некоторые ее элементы высоты 2. Введем необходимые обозначения. Через E(R) обозначается, как обычно, множество ндемпо-тентов кольца R. а через char R — его характеристику. Нетрудно проверить, что атомами решетки Sub Ьм являются в точности итеративные алгебры вида (гх + (1—£)Ь), гдег G E(R), h £ M. Здесь (F) обозначает итеративную алгебру, порожденную множеством функции F. При этом, если с = 1, то получается итеративная алгебра проекций, а если е = 0, то алгебра, порожденная одной константной функцией.

Среди итеративных алгебр, имеющих высоту 2 как элементы решетки Sub Ь м, важную роль играют покрывающие элементы алгебры проекций.

Предложение 1 Покрывающими элементами алгебры (е|) в Sub Ьм являются в точности следующие алгебры:

(i) {е}} v А, где А — атом в Sub Ьм, «с равный (cj);

(И) (ех 4(1- е)у>, где е € E(R)\{0,1};

(iii) (ах -f Ь), где

-о — обратимый элемент простого порядка р и Ь удовлетворяет условию ¿(1 + а + а- -(- • • ■ 4- ûp_1) — 0, или

-а = 1 и b имеет простой порядок по сложению;

(iv) (х — ру-\- рг), где р — нильпотептный элемент второй ступени, имеющий простой порядок по сложению;

(v) — у + z). если char (Л) — простое число.

В шестом параграфе вводится деление линейных функций на несколько типов н использующая это делению классификация итеративных алгебр. Назовем функцию примитивной, если в точности одни ее коэффициент является обратимым элементом кольца R, а остальные — нпльпотентнымн. Функцию, все коэффициенты которой суть нильпотентные элементы назовем нпльпотентной. Множество всех примитивных (нпльпотентных) функций обозначим через

LPm (соответственно LNл;). Пусть также Им — множество всех функций, коэффициенты которых принадлежат некоторому идеалу из R. Нетрудно проверить, что LPм, LNд/, 11м, а также мноясества LNPm = LP и U LN м, LIP м = IJ\j U LP д/, являются итеративными алгебрами.

Все алгебры линейных функций мы делим на 4 класса* исходя, с одной стороны, из того, какие атомы и покрывающие элементы алгебры проекций в них содержатся, а с другой, — пз функций какого типа, эти алгебры состоят. Мы выделяем следующие блоки решетки Sub L]\f:

(1) объединение интервалов вида [С, £д/], где С = (<f.r + (1 — е)у)

— покрывающий элемент алгебры проекций типа (ii);

(2) объединение интервалов вида [D, Ьщ], где D = (г.т + (1 — е)Ь)

— атом и £ € £(Я)\{0,1};

(3) решетка Sub ШРц\

(4) интервал [{ж — у + ;), Ьд/] (эту часть мы выделяем лишь в случае, когда char R — степень простого числа.

Эти части и образуют деление решетки Sub Лд/, упоминавшееся выше. -

Пересечение частей (1) и (2), а также (4) с частями (1)-(3) непусто, однако, указанное деление можно превратить в разбиение (ограничив, например, интервалы из (2) до интервалов [D,LIPm]). Части (1)-(4) обладают различными свойствами и должны, видимо, изучаться различными методами. Например, интервал (4) (т.е. [(я — y + z), Lm}) полностью описан в [4]. Это описание нам потребуется в дальнейшем, поэтому мы приведем его здесь. Каждая алгебра из [(ж — у + z), Lm] единственным образом представима в виде

п п

Km(R,JI) = {^Q-ii-i+a I и > i,Q-i, ...,«„

1=1 1=1

где R — унитарное подкольцо в Я, а М — подмодуль в Ях М, рассматриваемом как Д-модуль.

Свойства частей (1)-(4) тесно связаны со строением кольца R. Проследим эту зависимость на примере мощности. Если R имеет

хотя бы один ненулевой ннльпотентный элемент (т.е. не является прямой суммой конечных полей), то часть (3) счетна. (В противном случае вся решетка Sub конечна.) При этом условии части (1) II (2) бесконечны тогда п только тогда, когда R имеет пдемпотент, отличный от 0 н 1. Наконец, часть (4) конечна всегда.

Две следующие теоремы проясняют строение частей (1) п (2). В формулировках теорем использованы конструкции прямого произведения и гомоморфизма итеративных алгебр, уже возникавшие ранее в литературе (см., например, [5]). Через (F)b обозначается итеративная алгебра функций на В, порожденная множеством F С Pjj.

Теорема 3 Пусть £ 6 E(R). Тогда

(1) если итеративная алгебра L С Ьм содержит операцию ех+ +(1 — е)у, то L = LiX L2, где L\, L2 — подалгебры в Ьсм и ¿^-£г)л/> соответственно.

(2) [(ex- + (1 - е)у), Ьм] = [(e\)cM,LsM] х [(е11}(1_£)м, L(i-c)M-

Теорема 4 Пусть £ € £"(й)\{0, 1} и b G М.

(1) Если итеративная алгебра L содержит операцию £х + Ь, то отображение ь: L — L', где ~ipz j(/) = sf, является гомоморфизмом на подалгебру L' из Lchj.

(2) Отображение ~ipc ъ:\{ех + (1 — £)Ъ),Ьм] — \{е\)ем, Ьем], где lp£ b(L) = {г/ | / € L) для всех Ь € [(еж + (1 — £)Ь), Ьм], является сюръективнъш решеточным гоморфизмом.

Используя установленные в теоремах 3,4 свойства решетки Sub Ьм мы находим все ее коатомы.

Тебрема 5 Коатомами решетки Sub Ь\ц являются в точности следующие итеративные алгебры:

(1) црш х ¿(1_£)М, е 6 ВД\{0};

(2) KcM(R',R' х еМ) х £( 1_г)м, г 6 E{R)\{0}, где R' — максимальное унитарное нодколъио из £R, не содержащее идемпотен-тов;

(3) Ktju(£R,M')xL( 1_£)д/, где г € £'(Л)\{0} минимальный идемпотент и М' — максимальный подмодуль модуля £R х еА1.

В параграфах 7,8 изучается оставшаяся из выделенных нами частей решетки Sub Ьм — решетка Sub LNP^f. С этой целью в параграфе 7 перечисляются все итеративные алгебры примитивных функций. Мы поставим в соответствие каждой примитивной алгебре пару, состоящую из подкольца кольца Nil R всех ннльпотент-ных элементов из R, и подалгебры некоторой специальной конечной алгебры, близкой к модулю. Из этого описания будет следовать, в частности, что существует лишь конечное число примитивных алгебр.

Пусть S — подкольцо из Nil R. Через Ur(S) обозначим множество обратимых элементов а таких, что aS С S. Легко проверяется, что Ur (S) — подгруппа группы обратимых элементов R. Через Gs обозначим алгебру с носителем (Ur(S) — 1) х М и сигнатурными операциями:

о •' (Ol,/?l) о(а2,/32) = (»1 + Q'l Or 2 + ft-2,/?i -f Cl'x/?2 + P'l)',

: (oi,/?i) (q-2,/32) = (Q'l + £?c+9^2), Для каждого £>65.

Операции вида *е можнорассматривать для любого £> £ R. Операция

будучи ограниченной на первой компоненте, совпадает с присоединенным умножением кольца R и превращает множество Ur(S) — 1 в абелеву групп}'.

Далее, через Vyj обозначим множество пар (S, G), где S — подкольцо в Nil R, G — подалгебра в Gs- Через G будем обозначать носитель алгебры G. Введем на Тм частичный порядок покомпонентного включения, т.е. (5i,G'i) < (-S^G't) тогДа 11 только тогда, когда Si С Sn и G'i С GV Оказывается, что этот частичный порядок является решеточным и, более того, справедливо следующее утверждение.

Теорема G [{e\),LPAI} = ?м-

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

\(2>, LNPм) является теоретико-множественным объединением примитивной н ннльпотентной алгебры, а сама решетка [0,LNP,\j] — подмножеством прямого произведения [0,LNm] и [0,ЬРщ]. К сожалению, это подмножество не является подрешеткон. В §8 исследуются классы алгебр из [0. LNP\;}. имеющих одно и то же множество примитивных функций.

Пусть Р — примитивная алгебра. Через CN(Р) обозначим множество всех алгебр F С ЬАгРщ таких, что / П LPm = Р, я через jCNA'(P) — множество всех инльпотентных алгебр N, для которых N U Р G CN(P). Множества £N(P) и 0 G £NN(P).

Теорема 7 Пусть Р — примитивная алгебра.

(1) Решетки LN(P) и CNN(P) изоморфны.

(2) CN(P) является интервалом е Sub LN Рм-

(3) CNN(P) является полной О-подрешеткой б Sub LNл/.

Таким образом, решетка Sub LNPm распадается на интервалы CN(P), где Р пробегает множество примитивных алгебр. Для прояснения строения каждого из этих интервалов необходима информация о решетке ннльпотентиых алгебр (бесконечной во всех нетривиальных случаях), однако, в §8 вычисляются решеточные операции в Sub LNPm с точностью до интервала вида CN(P).

Мы находим также все алгебры из интервала £N(P) в случае когда он конечен. Обозначим Nil Р множество всех коэффициентов функций из примитивной алгебры Р, являющихся нильпотентными элементами. Это подкольцо. Обозначим также <х(/) сумму коэффициентов функции / без единицы.

Предложение 2 Пусть Р — примитивная алгебра, S = Nil Р. Тогда, если выполнены условия

а) идсализатор S в кольце Nil R пе совпадает с S;

б) найдется (а,Ь). а + 1 содержится в иде.ализаторе S, b G М такая, что для любого g £ 5 найдется f(xi,..., .тп) = а,-.г-,- -\-а из Р для которой <т(/) = да и а = gb;

то интервал САГ(Р) счетен.

Следующая теорема дает описание интервала £N(P) в случае, когда он конечен, т.е. не выполняются условия предложения 2. Пусть S — подкольцо из Nil R, G — подалгебра из G.s- Через Hs,g обозначим множество всех пар (а,/3) из (S — 1) х М, удовлетворяющих условию: для каждого д Е S пара {¿>а. п[3) содержится в G. Будем рассматривать H.s.G как алгебру с множеством сигнатурных опраций {*с | q £ 5}. Решетку всех подалгебр Н из #s,g таких, что для любых (а,0) € Л, (а', /?') € G, п Е S справедливы включения (а,/?)*£,(а',/?') £ Я и (а',/?')о(а,0) £ Я, обозначим через Subi Hs,g-

Теорема 8 Пусть Р — примитивная алгебра, S = Nil Р. G = {(а-, Ь) | сг(/) = a, b — свободный член /, f € Р} и идеализа-тор S в Nil R равен S. Тогда САТ(Р) изоморфна решетке Subi Hs,g-

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

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

Литература

[1] Репницкий В.В., Кацман СЛ. Коммутативные полугруппы, решетка подполугрупп которых удовлетворяет нетривиальному тождеству.// Мат. сборник, 1988, т. 137, N.4, с.300-315.

[2] Repnitskii V.B. On sublattices of semigroup lattices.// Order (submitted).

[3] Repnitskii V.B. On lattices which are embeddable in subsemigroups lattices. - Semigroup Forum, 1993, v.46, p.388-397.

[4] Szendrei A. Clones of linear operations on finite sets. - In: Finite algebra and multiple-valued logic. (Proc. Conf. Szeged (Hungary), 1979), Colloquia math. soc. J.Bolyai, v.28, p.693-738.

[5] Poschel R., Kaluznin L.A. Funktionen- und Relationenalgebren.- Ein ICapitel der diskreten Mathematik, Berlin: VEB DVW, 1979.

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

[G] Булатов A.A. Тождества в решетках клонов. - В кн.: II Между-нар. конф. по алгебре памяти А.И.Ширшова. Тезисы докл. Барнаул, 1991. с.'22.

[7] Булатов A.A. Тождества в решетках замкнутых классов. - Дискретная математика, 1992, т.4, N.4, с.140-148.

[S] Булатов A.A. Конечные подрешеткн решеток клонов. - В кн.: III Междунар. конф. по алгебре памяти М.И.Каргополова. Тезнсы докл. Красноярск, 1993, с.55-56.

[9] Булатов A.A. Полиномиальные редукты модулей. - В кн.: Третья Суслинская конф. Тезисы докл. Саратов, 1994, с.44.

[10] Булатов A.A. Конечные подрешеткн в решетке клонов. - Алгебра и логика, 1994, т.ЗЗ, N.5, с.514-549.

[11] Булатов A.A. Решетка замкнутых классов линейных функций к-значной логики. - В кн.: Междунар. конф. по мат. логике. Тезисы докл. Новосибирск, 1994, с.33-34,