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

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

РГБ ОК

27

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

Крохин Андрей Анатольевич

Интервалы в решетках клонов

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

АВТОРЕФЕРАТ

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

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

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

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

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

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

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

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

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

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

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

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

Автореферат разослан

1998 г.

Ученый секретарь диссертационного совета, к.ф.-м.н.

В. В. Кабанов

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

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

Как и многие другие конкретные объекты, изучаемые в общей алгебре (например, многообразия групп, полугрупп или колец), клоны на фиксированном множестве удобно классифицировать при помощи решетки, которую они образуют. Таким образом, исследование решеток с_\ является одним из важнейших направлений в теории клонов.

Полностью описать решетку клонов на конечном множестве, т.е. построить ее диаграмму, удалось лишь в одном простейшем нетривиальном случае, при |Л| = 2 (результат принадлежит Э.Посту). Эта решетка оказалась счетной и ее описание было потом использовано при решений многих (не только алгебраических) задач. В случае \А\ > 3, как показали Ю.И.Янов и А.А.Мучник (и независимо еще целый ряд авторов), решетка с а континуальна. Исследуя сложность решеток клонов, А.А.Булатов доказал [1,2], что с а не удовлетворяет никакому нетривиальному решеточному тождеству при |Л| > 3, и содержит любую конечную решетку в качестве под-решетки при |Л| > 4. Таким образом, при \А\ > 3 описание решетки с а, подобное результату Э.Поста, вряд ли возможно.

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

Легко проверить, что для любого клона С на А множество С^ всех одноместных функций из С является подмоноидом моноида Та

всех преобразований на А. Пусть М — произвольный подмоноид из Та - Хорошо известно, что множество {С £ Са\С^ = М} является интервалом (возможно, одноэлементным) в решетке Ca - Интервалы такого вида будем называть моноидалъными и обозначать, следуя [9], через IntM. Итак, мы имеем разбиение решетки клонов на мо-ноидальные интервалы.

А. Сендреи поставила ([9], с.74) задачу определения мощностей моноидальных интервалов. Мы приведем формулировку этой задачи в несколько расширенном варианте.

Задача А. Сендреи. Охарактеризовать моноиды преобразований М такие, что

(1) \IntM\ — 2n°;

(2) \IntM\ = Н0;

(3) IntM конечен, но не одноэлементен;

(4) IntM одноэлементен.

Поскольку при |Л| = 2 решетка клонов известна полностью, всюду далее мы будем предполагать, что множество А конечно и |Л| > 3. Ранее в работах А.Сендреи, П.П.Палфи и ряда других авторов были найдены некоторые примеры конечных моноидальных интервалов, являющихся цепями (в том числе одноэлементными), а также континуальных интервалов. Отметим, что не было известно, существуют ли счетные моноидальные интервалы.

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

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

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

1) найден большой класс счетных моноидальных интервалов;

2) доказано, что любая конечная булева алгебра представима подинтервалом подходящего конечного моноидального интервала, который может быть даже не модулярным;

3) приведен большой класс континуальных моноидальных интервалов, содержащих в качестве подинтервала булеан на счетном множестве;

4) указан широкий класс дистрибутивных решеток, представи-мых интервалами в решетках клонов;

5) для двух типов максимальных клонов в общем случае, и для всех максимальных клонов при |А| = 3 решена задача о мощности моноидальных интервалов, содержащих максимальные клоны;

6) исследованы моноидальные интервалы, состоящие из клонов, , все унарные, отличные от тождественной, функции в которых суть, константы.

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

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

Основные результаты работы докладывались на III Международной конференции по алгебре (Красноярск, 1993 г.), Международной конференции по математической логике (Новосибирск, 1994 г.), 52 конференции по общей алгебре и дискретной математике (Потсдам, Германия, 1996 г.), 55 конференции по общей алгебре и дискретной математике (Дармштадт, Германия, 1997 г.), а также на семинарах "Алгебра и логика" и "Алгебраические системы" Института математики СО РАН и Новосибирского государственного университета, семинаре "Алгебра" технического университета г.Дрездена, семинарах "Алгебра и логика" университетов гг. Ростока и Кай-зерслаутерна (Германия), семинарах "Алгебраические системы" и "Дискретная математика" Уральского государственного университета. Они опубликованы в работах [10]-[18].

Диссертация состоит из введения и 7 параграфов и содержит 9 теорем. Общий объем диссертации составляет 80 страниц. Библиография содержит 46 наименований. Используется сквозная нумерация утверждений.

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

Введем на множестве А структуру ассоциативного кольца Я с единицей, и рассмотрим клон Ьц = {ао + аг^г|ао, а; £ Щ всех линейных над Я функций. Обозначим через Мц моноид =

{гж + в|г, з £ Я}, и пусть 1(Я) = {г € Л|г(х2 — а-) = 0 для всех ж € Я}. Следующая теорема является центральным результатом первого параграфа.

Теорема 1 Пусть 1(Я) = 0. Если кольцо Я полупросто, то интервал 1ЫМя конечен; в противном случае он счетен.

Через С а обозначется подмоноид из '1 \\, состоящий из тождественного преобразования гс? и всех константных функций.

Предложение 1 Пусть 1(Я) = 0 и Са С М С [Са и {гх|г £ Я}). Тогда \ШМ\ = 1.

Теперь, чтобы понять, насколько широки найденные нами классы моноидов, нужно выяснить, что означает условие /(Л) = 0.

Предложение 2 Если двухэлементное поле не является гомоморфным образом кольца Я, то 1{Я) = 0. Если кольцо Я коммутативно, то это достаточное условие является также и необходимым.

Пусть \А\ = 2тп, где т > 0, а п > 1 — нечетное число. Полученные результаты позволяют утверждать, что если т ф 1 и число п не свободно от квадратов, или если т = 4 или т > 5, то в решетке с а найдется счетный монондальный интервал.

Из теоремы 1 следует, что если кольцо Я есть прямая сумма конечного числа конечных полей, Я = 1\ ф ■ ■ ■ ф Еп, таких, что > 2 при 1 < г < тг, то интервал 1п1Мп конечен. Мы уточним строение таких интервалов.

Теорема 2 Пусть Я = ф • ■ ■ ф Рп, где Р{ — произвольные конечные поля, каждое из которых содержит более двух элементов. Тогда

(1) интервал 1п1Мд имеет п("2+1) атомов;

(2) подрешетка в 1п1Мц, порожденная всеми атомами, является интервалом, изоморфным булевой алгебре;

(3) при п > 3 интервал 1гЛМц немодулярен.

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

Можно ли выделить в классе всех моноидов преобразований конечных множеств моноиды М со свойством \IntM| < Ко при помощи каких-нибудь абстрактных условий? Отрицательный ответ на этот вопрос вытекает из следующего утверждения.

Предложение 3 Для любого (абстрактного) конечного моноида М найдутся конечное множество А и подмоноид М' из Та такие, что М £= М' и \IntM'\ = 2*4

9

В §2—§4 диссертации мы исследуем континуальные моноид ал ь-ные интервалы.

Говорят, что функция f(x 1,..., хп) сохраняет отношение р С Ат (для удобства договоримся записывать элементы отношений в столбик; символ Т обозначает транспонирование), если для любой матрицы Т = (aij)mxn, столбцы которой принадлежат р, столбец

f(T) = (/(aib---,ain),...,/(ami,...,amn))T

построчных значений функции / также принадлежит р. Через Polp обозначается клон всех функций, сохраняющих отношение р, а через Polip — моноид всех таких унарных функций.

Пусть 7Г - разбиение множества А на два непустых подмножества Ао и Л], причем |Ло| > 2. Обозначим через ц следующее отношение квазипорядка на множестве А: (Ло х Ло) U (Лц х А{) U (Лх. х Лх), и рассмотрим моноид Ро/щ. Непосредственно проверяется, что этот моноид состоит из всех унарных функций m £ Та, удовлетворяющих одному из следующих условий:

(ml) ш(Л0) С Ло, 'п(Лх) С Ai\

(m2) т(Л) С Л0;

(тЗ) т(А) С Ль

Функцию и(х) £ Poliß назовем характеристической для разбиения т, если найдутся ао, ах 6 Ло, аа ф такие что и(ж) = ао для всех х £ Л о и и(х) = ai для всех х 6 А\.

Теорема 3 Пусть M - подмопоид из Pol\¡j,, содержащий некотирую характеристическую функцию разбиения тт. Тогда о интервале IntM найдется подинтервал, изоморфный счетной прямой степени цепи типа и> + 1.

Следствие 1 В условиях теоремы 3 верно равенство \IntM\ — 2N°.

В [2] доказано, что любая решетка, являющаяся прямым произведением не более чем счетного числа конечных решеток, изоморфна подходящей подрешетке из при |А| > 3. В той же работе поставлен вопрос о том, останется ли это утверждение верным, если в нем слово "подрешетка" заменить на слово "интервал". Частичный ответ на этот вопрос дает следующее утверждение.

Следствие 2 Любая решетка, являющаяся прямым произведением не более чем счетного числа конечных цепей, изоморфна подходящему интервалу в Са при |А| > 3.

Отметим, что следствие 2 обобщает результат работы [6], где доказано, что булеан на счетном множестве (т.е. счетная прямая степень двухэлементной цепи) изоморфен подходящему интервалу в Са при |А| > 3.

Легко показать, что любой моноид, сохраняющий квазипорядок /i, сохраняет также ц отношение эквивалентности ц П р-1, единственными классами которого являются Ао и А\. Однако есть много важных с определенной точки зрения моноидов преобразований, которые не сохраняют ни один из квазипорядков вида fí, но сохраняют некоторое отношение эквивалентности.

Пусть е — нетривиальное отношение эквивалентности на множестве А. Тогда клон Pole состоит из всех функций / таких, что £ является конгруэнцией алгебры (А;/), а моноид Ро1\£ — из всех таких унарных функций. Зафиксируем различные элементы a,b £ А такие, что (а, 6) G е, и обозначим через Mo моноид

{m G Poli£\m(A) С {а,6} и если(а:,1/) G е, то т(х) = т(у)} U {id}.

Теорема 4 Пусть Mo CMC Pol\£. Тогда в интервале IntM найдется подинтервал, изоморфный булеану на счетном лшожестве.

Следствие 3 В условиях теоремы 4 верно равенство \IntM\ = 2No.

При изучении счетных и конечных моноидальных интервалов мы рассматривали моноиды вида Mr и исследовали интервалы IntMn при условии /(Я) = 0. Пусть теперь 1(Я)П J(R) ф 0, где через J(R) обозначается, как обычно, радикал Джекобсона кольца Я.

Следствие 4 Пусть l(R) П J(R) ф 0. Тогда в этом множестве найдется ненулевой элемент г такой, что гх £ {0,г} для любого х £ R и если моноид М состоит из полиномиальных функций кольца R и содержит функции гх и гх + г, где г 6 R — такой, как указано, то в интервале IntM найдется подинтервал, изоморфный булеану на счетном множестве.

В частности, при /(Я) П J (Я) ф 0, мы имеем \IntMR\ = 2*4

Через (F) обозначается клон, порожденный множеством функций F.

Известно, что решетка Са имеет лишь конечное число коатомов (так называемых "максимальных клонов"), и что всякий максимальный клон С, за исключением одного (клона Слупецкого1), является наибольшим элементом в содержахдем его монондальном интервале, т.е. IntC^ = [(С^); С].

Отношение р С Ah, 1 < h < \А\, называется центральным, если оно вполне рефлексивно (т.е. если ,..., х-/,}] < h, то (a?i,..., Xh)T 6 р), вполне симметрично (т.е. если (ri,... ,Xh)T брит — произвольная перестановка на множестве {1,..., Л}, то (iV(i),..., Хъ(ь,))Т £ р), и имеет непустой центр с(р), где с(р) = {о £ х Ah~1 С р].

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

По теореме Розенберга о полноте всякий максимальный клон имеет вид Polcr, где а — отношение одного из шести типов. В частности, из этой теоремы следует, что любой клон вида Pole, где е — нетривиальное отношение эквивалентности, и любой клон вида Polp, где р — центральное отношение, является максимальным в

СА-

^ клон Слупецкого состоит из всех несюръективных функций на А и всех функций, принадлежащих клопу (Тд)

Следствие 5 (1) Если С — максимальный клон вида Pole, то верно равенство = 2N°.

(2) Пусть В С А, |В| > 1. Тогда \IntPohB\ = 2N°.

В работе [3] для \А{ < 7 подсчитано число максимальных клонов каждого типа. Оказалось, что доля максимальных клонов, определяемых центральными отношениями, в общем числе максимальных клонов велика, и, более того, с ростом числа элементов в А она быстро увеличивается. Так, если при \А\ = 3 ровно половина из 18 максимальных клонов определяется центральными отношениями, то при = 7 всего максимальных клонов на А — 7848984, из них клонов, определяемых центральными отношениями, — 7758205. Поэтому исследуя моноидальные интервалы, содержащие максимальные клоны, в первую очередь следует обратить внимание на клоны, Определяемые центральными отношениями.

' Теорема 5 Если С — максимальный клон вида Polp, где р — центральное отношение, то = 2К°.

Важную роль во многих универсально-алгебраических исследованиях играют простые алгебры. Поэтому отметим, что в качестве следствия из теоремы 5 можно получить утверждение о числе попарно полиномиально неэквивалентных простых алгебр на конечном множестве А таком, что \А\ > 2, впервые доказанное А.А.Булатовым (неопубликовано).

Следствие 6 На конечном множестве А таком, что |Л| > 2, существует 2^° попарно полиномиально неэквивалентных простых алгебр, не имеющих собственных подалгебр и нетривиальных автоморфизмов.

Отметим, что, как доказал Руссо [8], для конечной алгебры (Л; /) с одной основной операцией условие быть простой и не иметь собственных подалгебр и нетривиальных автоморфизмов эквивалентно примальности.

Через 1т/ обозначается, как обычно, образ функции /. Известно (см. [9], с.72 и [7]), что число клонов на А, содержащих все унарные функции / такие, что \1т/\ < |Л| — 1, или содержащих все перестановки, т.е. унарные функции / такие, что 1т/ = А, конечно.

С другой стороны, множество всех клонов на А, содержащих все константные функции, континуально [5].

Принимая во внимание все эти утверждения, естественно поставить вопрос о числе клонов на А, содержащих все унарные функции f со свойством \Imf\ < |А| — 2.

Предложение 4 На конечном множестве А таком, что |А| > 2, существует клонов, содержащих все (не только унарные) функции / со свойством \Imf\ < |А| —2.

Выделим еще один важный тип моноидов, сохраняющих центральные отношения. Зафиксируем непустое подмножество В из А такое, что \В\ < |А| — 2, и обозначим через ВА совокупность всех функций / £ Тд таких, что Imf С В. Тогда моноид преобразований ВА U {¿d} сохраняет любое центральное отношение, центр которого содержит В, и любое h-местное центральное отношение такое, что h > \В\ + 1.

Теорема 6 Для любого подмоноида М из ВА U выполнено равенство \IntM\ = 2n°.

Пусть теперь |Л| = 3. Без ограничения общности можно считать, что А = {0,1,2}. В §5 диссертации мы указываем мощности всех моноидальных интервалов, содержащих максимальные клоны на А. Приведем полный список из 18 максимальных клонов на А, впервые указанный С.В.Яблонским [4].

1. Три клона Ро1{а), где а € А;

2. три клона Pol{a, Ь}, где а,Ь £ А;

3. три клона Pola, где а — двухместное центральное отношение;

4. три клона Pole, где е — нетривиальное отношение эквивалентности на Л;

5. три клона Pol <, где < — отношение линейного порядка2 на

Л;

6. клон Слупецкого SI;

2 Взаимно дуальные порядки определяют одинаковые клоны.

7. Pol<p, где y> = ° ^ , ^ g ) > ( о

8. L = {J2<iiXi + a0(mo<i3)|ao,ai G A}.

Если С — максимальный клоп типа 1-3 (соотв. 4) из списка Яблонского, то по теореме 5 (соотв. по следствию 5) мы имеем \IntC^\ = 2N°. Известно, что интервал IiitS№ является 4-элементной, IntPol\<p — З-элементной, а IntL^ — 2-элементной цепью. Неисследованными остались только интервалы IntPoli <. Без ограничения общности определим порядок < следующим образом: 0 < 1 < 2. Через min и тах обозначим двухместные операции взятия минимума и максимума относительно этого порядка.

Теорема 7 Интервал IntPoli < имеет вид, представленный па Рис.1.

Ро1<

{Poh <) Рис. 1

В §6 изучаются интервалы IntM, где М С С а- Клон С принадлежит такому моноидальному интервалу, только если все унарные функции из С, отличные от тождественного преобразования, суть константы. Пусть моноид М состоит из тождественного преобразования и I константных функций, где I < |/11. Если I = |,4|, то М = С а, и, как хорошо известно, имеет место равенство \IntM ¡ = 1. Если / < — 2, то, как непосредственно следует из теоремы 6, мы имеем \IntM\ = 2N°. Значит, нам осталось разобрать случай, когда / = |А| — 1. Опять же, без ограничения общности можно считать, что А = {0,1, ...,к- 1} и М = {id,0,1,. ,.,к- 2}.

Пусть = 3. Тогда М = {¿ci, 0,1}. Зафиксируем на А порядок О < 2 < 1, и обозначим через V и Л операции в соответствующей этому порядку трехэлементной решетке.

Теорема 8 Интервал IntM имеет вид, представленный на Рис.2.

(V,A,0,1)

<V,0,1)< > (Л, 0,1)

Рис.2

Таким образом, все клоны из интервала IntM, отличные от (М), — это клоны термальных операций трехэлементной ограниченной решетки и двух соответствующих ей ограниченных полурешеток.

Теорема 9 Если \А\ > 3 и M = {id, 0,1,2,..., к-2}, то \IntM\ = 1.

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

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

Литература

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

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

[3] Захарова Е.Ю., Кудрявцев В.Б., Яблонский C.B. О предполных классах в k-знанных логиках// ДАН СССР, 186, 1969, 509-512. (Поправка, ДАН СССР, 199, 1971, 90.)

[4] Яблонский C.B. Функциональные построения в k-значной логике// Тр. МИЛН СССР, 51, 1958, 5-142.

[5] Agoston I., Demetrovics J., Hannák L.On the number of clones containing all constants// Lectures in Universal Algebra, Coll.Math.Soc. J.Bolyai, 43, 1983, 21-25.

[6] Haddad L., Rosenberg I.G. Un intervalle Booléen de clones sur un univers fini// Ann. Soi. Math., Quebec, 12, 2, 1988, 211-231.

[7] Haddad L., Rosenberg I.G. Finite clones containing all permutations// Can.J.Math., 46, 5, 1994, 951-970.

[8] Rousseau G. Completeness infinite algebras with a single operation// Proc. Amer.Math.Soc., 18, 1967, 1009-1113.

[9] Szendrei A. Clones in universal ai<7e&ra//Séminaire Math. Supérieures 99, Les Presses de l'Université de Montreal, 1986.

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

[10] Крохин А.А. Мощности некоторых интервалов в решетках клонов// в кн.: III междунар. конф. по алгебре памяти М.И.Кар-гаполова. Тез.докл., Красноярск, 1993, 185.

[11] Крохин А.А. О счетных моноидалышх интервалах в решетках замкнутых классов// в кн: Междунар. конф. по математической логике. Тез.докл., Новосибирск, 1994, 58.

[12] Крохин, А.А. Мопоидалъные интервалы в решетках клонов// Алгебра и логика, 34, 3, 1995, 288-310.

[13] Krokhin A.A. Monoidal and distributive intervals in clone lattices// in: Algebra, Proceedings of the III Internat, conf. on Algebra held in Krasnoyarsk, 1993. Eds.: Yu.L.Ershov et al., Berlin, de Gruyter Verlag, 1996, 153-159.

[14] Krokhin A.A. Clones and covers of the monoid of all constant transformations// в кн.: Междунар. конф. "Полугруппы и их приложения, включая полугрупповые кольца". Тез.докл., С.-Петербург, 1996, 32.

[15] Krokhin A.A. Some intervals in clone lattices// in: Conf. on Universal Algebra and Lattice Theory, Abstracts, Szeged, Hungary, 1996, 30.

[16] Krokhin A.A. Maximal clones in monoidal intervals// в кн.: IV Междунар. конф. по алгебре памяти Д.К.Фаддеева. Тез.докл., С.Петербург, 1997, 72.

[17] Krokhin A.A. On clones, transformation monoids, and associative rings// Algebra Universalis, 37, 4, 1997, 527-540.

[18] Krokhin A.A. Boolean lattices as intervals in clone lattices// Int.J. Multiple-Valued Logic, 2, 3, 1997, 263-271.

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

УДК 512.577

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

КРОХИН Андрей Анатольевич

Интервалы в решетках клонов

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

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

Научный руководитель: кандидат физико-математических наук, доцент Е. В. Суханов

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

Содержание

Содержание.........................................................2

Введение.............................................................3

§1. Конечные и счетные моноидальные интервалы...........22

§2. Моноидальные интервалы и отношения квазипорядка ..33

§3. Моноидальные интервалы и отношения

эквивалентности ............................................. 43

§4. Моноидальные интервалы и центральные отношения ... 50

§5. Моноидальные интервалы и максимальные клоны

на трехэлементном множестве .............................62

§6. Моноидальные интервалы и константные функции .....68

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

Литература.........................................................76

Указатель обозначений...........................................80

ВВЕДЕНИЕ

1° Теория клонов находится на стыке трех дисциплин: математической логики, универсальной алгебры и математической кибернетики. Понятие "клон" (и близкие к нему понятия "замкнутый класс" и "итеративная алгебра") возникает естественным образом как обобщение понятия "моноид (полугруппа) преобразований" на случай функций многих переменных при изучении операции суперпозиции функций, заданных на некотором множестве. Так, многие свойства (универсальной) алгебры зависят не от выбора основных операций, а от того, какие функции могут быть получены из них при помощи суперпозиции. В кибернетике суперпозиции соответствует конструирование сложных устройств из более простых. Наконец в математической логике важную роль играет суперпозиция истинностных функций.

Специалистом именно по математической логике Э.Постом были написаны в 20-40-х годах нашего века работы [26, 27], считающиеся одними из первых публикаций по теории клонов. С тех пор теория клонов плодотворно развивалась и к настоящему времени обрела четкие контуры, собственную богатую проблематику и содержит большое число результатов. Имеющаяся литература весьма обширна, поэтому упомянем здесь лишь несколько работ обзорного характера и монографий [6, 9, 12, 25, 35].

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

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

Поскольку практически во всех случаях решетку клонов нельзя описать "глобально", возникает задача "локального" описания этой решет-

ки, т.е. описания (или характеризации) ее интервалов. Этому направлению в изучении решеток клонов и посвящена данная диссертация.

2° Введем некоторые обозначения и определения. Пусть А — конечное множество, \А\ > 2. Через О а обозначается множество всех конечноместных функций (или операций) на А. Если Р с О а и и £ то через обозначается система всех п-местных функций

из Р. Множество С С О а называется клоном на А, если для любых / € С(п\ д1,...,дп € С(т) функция ¡(дг,... ,дп){х1, .. . ,хт) = 1(дг{х1, ■ ■ ■ 5 хт), ■ ■ ■ , дп(% 1, ■ ■ ■ ■> хт)) также принадлежит С, и если С содержит все проекции (т.е. функции вида егп(х1,. . ., хп) = ж,-). Пересечение любого числа клонов снова является клоном. Таким образом, совокупность всех клонов на А образует решетку по включению, которая обозначается через £а, с наибольшим элементом О а и наименьшим элементом — клоном всех проекций на А. Наименьший клон, содержащий множество Р С О а, называется клоном, порожденным множеством Р, и обозначается через (Р). Всюду далее через 1т/ обозначается образ функции /, а через г б?а (или просто через гс1) — тождественное преобразование на множестве А.

Говорят, что функция / £ О^ сохраняет отношение р С Ат (для удобства договоримся записывать элементы отношений в столбик; символ Т обозначает транспонирование), если для любой матрицы Т — столбцы которой принадлежат р, столбец

= (/(°1Ь • • •) агп)) • • ■ 1 /(а™ь • • •; атп))Т

построчных значений функции / также принадлежит р. Через Ро1р обозначается совокупность всех функций, сохраняющих отношение /?, а через Ро1гр — совокупность всех таких унарных функций. Мы используем обозначение Ро1\р (а не (Ро//?)^1)), потому что оно общепринято в соответствующей литературе. Мы будем говорить, что множество функций Р С О а сохраняет множество 5" отношений на Л, если каждая функция из Р сохраняет каждое отношение из 5".

При |А| = 2 решетка С а полностью описана в [26, 27], она оказалась счетной. Таким образом, любой вопрос относительно интервалов этой решетки может быть решен при помощи этого описания. Всюду далее мы будем предполагать, что > 2.

Известно, что в этом случае решетка С а континуальна [10] и удовлетворяет лишь тривиальным решеточным тождествам [1]. Кроме того,

при |т4| > 3 любая решетка, являющаяся прямым произведением не более чем счетного числа конечных решеток, изоморфно вкладывается в С а [2]. Отсюда следует, что при |Л| > 2 полное описание решетки клонов на А вряд ли возможно. Поэтому мы сосредоточим наши усилия на исследовании интервалов в С а, в особенности некоторых естественно возникающих интервалов, тесно связанных с такими хорошо известными алгебраическими объектами, как моноиды преобразований. Эта тесная связь обусловлена как раз тем упомянутым в самом начале фактом, что "клон" есть обобщение "моноида преобразований".

Легко проверить, что для любого клона С на Л множество С^1) всех одноместных функций из С является подмоноидом моноида Та = О^ всех преобразований на А. Пусть М — произвольный подмоноид из Гд. Стабилизатор моноида М — это множество

БШ = {/ £ О^ | п > 0 и /(т1(ж),...,тп(ж)) £ М для произвольных Ш1,. .. , тп £ М}.

Отметим, что это понятие под названием "нормализатор" было введено в [6]. Нетрудно проверить, что ¿"¿М — клон, и что (М) С 57М. Интервал (возможно, одноэлементный) {{М)\ ¿ЧМ] в решетке С а обозначим через 1пЬМ. Интервалы такого вида будем называть моноидальными. Хорошо известно (см. напр. [35], с.71), что если С £ На, то = М тогда и только тогда, когда С € 1п1М. Итак, мы имеем разбиение решетки клонов на моноидальные интервалы (см. Рис.1 ниже).

А.Сендреи поставила ([35], с.74) задачу определения мощностей моноид альных интервалов. Мы приведем формулировку этой задачи в несколько расширенном варианте.

Задача А. Сендреи. Охарактеризовать моноиды преобразований М такие, что

(1) \IntMl = 2Ко;

(2) \ШМ\ = К0;

(3) 1пИМ конечен, но не одноэлемнтен;

(4) 1ЫМ одноэлементен, т.е. = (М).

Ca

/ StM / /

IntAf

I/

{Та)

<М> *

Рис.1

В случаях (2) и (3) можно также пытаться найти явное описание моноид ал ьных интервалов. В общем виде задача А. Сендреи представляется весьма сложной. Поэтому мы будем решать ее как для некоторых больших классов, так и для отдельных, важных по тем или иным причинам, моноидов.

Поставленную задачу можно переформулировать на языке универсальной алгебры. Пусть А = (А: F) — конечная (универсальная) алгебра. Клон Т(Л) = (F) называется клоном термальных операций алгебры Л. Алгебры А\ = {А, Fi) и *42 = (Л,^) называются термально эквивалентными, если Т{А\) = Г(Дг)- Термально эквивалентные алгебры имеют одинаковые подалгебры, эндоморфизмы, конгруэнции и т.д.. Поэтому алгебры часто классифицируют с точностью до термальной эквивалентности. Итак, задача Сендреи может быть неформально сформулирована следующим образом: насколько конечная универсальная алгебра определяется (с точностью до термальной эквивалентности) моноидом своих унарных термальных операций?

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

Строка клетки таблицы, в которой находится моноид М, указывает на мощность интервала /п^М.

\IntM\ Группы перест-к Остальные моноиды

\IntM\ = 2*° одноэлементная группа {ге?} [24] {.lg(x) = дх\д <= G где А = G0 - конечная группа с присоединенным нулем [36]

\IntM\ = Ко ? ?

\IntM\ < оо \IntM\ ф 1 Ор = {х + а\а £ А}, где (А, +, 0) — циклическая группа простого порядка 1пЮр ~ 3-эл. цепь [33] ТА-моноид всех преобразований множества А. IntTA-(|Л| + 1)-элементная цепь. [3]

Bi = {fGTA-.\f(A)\<l}U{id}, (2 < / < |А| - 1) IntBi - (1+1)-эл. цепь [7]

03 - простая регулярная группа составного порядка. 1п108 - двухэлементная цепь. [24] М - моноид всех линейных (аффинных) преобразований конечного n-мерного векторного пространства над конечным полем. IntM - (п + ^-элементная цепь. [31]

\IntM\ = 1 транзитивные нерегулярные группы, в которых каждая нетривиальная нормальная подгруппа транзитивна. [24] М состоит из тождественного преобразования id и всех константных функций [см. [35], с.73]

Таблица 1

Кроме упомянутых в таблице, заслуживают внимания следующие результаты:

1) Если М состоит из всех константных функций и некоторого числа перестановок, то \IntM] < 2, причем равенство выполняется тогда и только тогда, когда М — моноид всех унарных полиномиальных функций конечного векторного пространства над конечным полем [23]. Этот результат стал одним из базовых для теории ручных конгруэнций [8].

2) Моноид М называется сжимающим, если выполняется равенство (М) — Это равенство означает, что только один клон, а именно

(М), имеет своим первым слоем моноид М. Термин "сжимающий моноид" был введен в [24] для случая, когда М есть группа перестановок. Лемма 1.3.1 в [25] предоставляет критерии свойства "быть сжимающим" для моноидов преобразований и групп перестановок. Из этих критериев следует, в частности, что при п > 1 любая п раз транзитивная группа перестановок является сжимающей. Для групп перестановок в [18], а для общего случая в [19] имеются другие критерии того, что моноид — сжимающий. К сожалению, все эти критерии трудно применять практически.

В данной диссертации мы существенно дополним имеющуюся информацию о моноидальных интервалах. Кроме того, мы укажем широкий класс дистрибутивных решеток, представимых интервалами в решетках клонов, и ответим на несколько вопросов о числе клонов или универсальных алгебр, обладающих тем или иным важным свойством. Соответствующие результаты излагаются в § 1 §6 диссертации, §7 посвящен обсуждению тех вопросов, связанных с тематикой диссертации, которые пока остаются открытыми.

В первом параграфе диссертации положительно решается вопрос о существовании счетных моноидальных интервалов. Исследуя монои-дальные интервалы, определяемые моноидами линейных функций, мы найдем классы моноидов М таких, что 1п1М счетен. одноэлементен и конечен, но не одноэлементен. Как видно из таблицы 1, все ранее известные конечные моноидальные интервалы оказывались цепями. Мы докажем, что всякая конечная булева алгебра изоморфна некотором)' подинтервалу подходящего конечного моноидального интервала. Кроме того, мы приведем первые примеры немодулярных конечных моноидальных интервалов. Завершая §1, мы покажем, что абстрактная ха-рактеризация моноидов со счетными и/или конечными моноидальными интервалами невозможна.

Второй, третий и четвертый параграфы диссертации посвящены континуальным моноидальным интервалам. Так, во втором параграфе мы указываем для |А| > 2 широкий класс моноидов преобразований М, сохраняющих отношение квазипорядка определенного вида, таких, что решетка, являющаяся прямым произведением счетного числа цепей типа ш + 1, изоморфна подходящему подинтервалу в 1пЬМ. Используя результаты этого параграфа, мы укажем число попарно полиномиально неэквивалентных Е-минимальных алгебр на конечном множестве, со-

держащем более двух элементов.

Третий параграф диссертации посвящен моноидальным интервалам, связанным с отношениями эквивалентности. Мы докажем, что если моноид преобразований М сохраняет отношение эквивалентности и содержит определенные функции, то булеан на счетном множестве изоморфен подходящему подинтервалу в /п^М. Будут приведены важные примеры таких моноидов.

Прежде чем перейти к обсуждению §4, необходимо сделать небольшое отступление. Известно [5], что решетка С а коатомна и имеет лишь конечное число коатомов (так называемых "максимальных клонов"), и что каждый максимальный клон С (кроме одного — клона Слупецкого ¿7, состоящего из всех существенно унарных1 и всех несюръективных функций на А) представим в виде С — ¿"¿(С^), т.е. является наибольшим элементом в своем моноидальном интервале.

В четвертом параграфе диссертации мы найдем мощности интервалов /п^С^) = [(С^1)); С] для некоторого типа максимальных клонов С в С а- Не уточняя здесь, что это за тип, скажем лишь, что доля клонов этого типа во множестве всех максимальных клонов на А очень велика. Попутно мы получим утверждения о числе клонов на А, содержащих все функции / со свойством ¡/т/| < |А| — 1, и о числе попарно полиномиально неэквивалентных простых алгебр на А, не имеющих собственных подалгебр и нетривиальных автоморфизмов. Кроме того, в §4 мы найдем мощности интервалов 7п7М, если для любой функции / £ М\{гс1} выполнено условие 1т/ СйсА. где \В\ < |А| — 2.

Используя список максимальных клонов, полученный для ¡А| = 3 С.В.Яблонским [9], и результаты, приведенные в таблице 1, а также полученные в третьем и четвертом параграфах данной диссертации, мы можем при |А| = 3 указать мощности всех моноидальных интервалов, содержащих максимальные клоны, за исключением одного случая, когда максимальный клон состоит из всех функций, монотонных относительно некоторого линейного порядка. Разбору этого случая и посвящен §5, где мы полностью опишем соответствующий моноидальный

1 Говорят, что жг- — существенная переменная функции /, если найдутся аь . .., а,-_1, аг+ь . . ., ап и а,Ь, такие что /(аг,. . ., аг'_ь а, сц+ь . . . . ап) ф /(ах, .... аг_1, 6, аг+1, . . ., ап). В противном случае переменная жг- называется фиктивной. Функция называется существенно унарной, если она имеет не более одной существенной переменной.

интервал.

Обозначим через С а моноид, состоящий из всех одноместных константных функций и тождественного преобразования. Как видно из таблицы 1, интервал 1п1Са одноэлементен. А что можно сказать в смысле задачи Сендреи о подмоноидах из Сл? Оказывается, большая их часть изучена нами в §4. Оставшийся случай, когда моноид состоит из гс1 и (|А| — 1) константных функций, мы и разберем в §6.

3° Перейдем теперь к точным формулировкам результатов диссертации. Введем на множестве А структуру ассоциативного кольца И с единицей, и рассмотрим клон Ьц = {ао + а1х^ао, £ Щ всех линейных над Я функций. Через виЬЕя обозначим решетку всех подклонов из Ьр>. Известно [20], что \ЗиЬЬр>\ < и, более того, строгое неравенство имеет место тогда и только тогда, когда К есть прямая сумма конечных полей [32]. Рассмотрим моноид Мд = Ь$ = {гх + з|г,з £ Щ. В §1 мы изучаем интервалы 1п1М для некоторых подмоноидов М из Мя-

Очевидно, что Ьц С Выясним, когда же они совпадают. Пусть

/(/?) = {г 6 Щг(х2 — х) — 0 для всех г £ й}. Обозначим через А'д совокупность всех полиномов, рассматриваемых как функции, от конечного числа переменных над Д, в которых каждый нелинейный одночлен имеет коэффициент из 1(Н) (свободный член рассматривается как линейный).

Предложение 1 (1) Если С а ^ М С Мц, то 57М С А'я/ (2) БШп = Кп.

Следствие 1(1) Если 1(11) = 0 и СА С М С Мя, то 5Ш С Ья;

(2) ¿"¿Мд = Ьц тогда и только тогда, когда 1(Я) = 0.

Итак, если 1(В) = 0 и СА С М С Мя, то ШМ = [^^О^!] есть интервал в решетке БиЬЬц, т.е. \IntMl < Следующая теорема является центральным результатом первого параграфа.

Теорема 1 Пусть 1(Я) = 0. Если кольцо И полупросто, то интервал 1п1Мц конечен; в противном случае он счетен.

Предложение 2 Пусть 1(П) = 0. Если СА С М С (СА и {гх\г е Щ), то \IntM| = 1.

Теперь, чтобы понять, насколько широки найденные нами классы моноидов, нужно выяснить, что означает условие /(Я) = 0.

Предложение 3 Если двухэлементное поле Z2 не является гомоморфным образом кольца R, то /(Я) — 0. Если кольцо R коммутативно, то это достаточное условие является также и необходимым.

Выясним, для каких конечных множеств А мы можем указать в решетке Ca счетный моноид ал ьный интервал. Через Zn обозначается, как обычно, кольцо вычетов по модулю п. Пусть \А\ = 2mn, где т > 0, а п > 1 — нечетное число. Если т ф 1 и п = р"1 ■ ■ ■ р1к, где аг > 1 для некоторого 1 < г < то в качестве R можно выбрать кольцо

GF(2т) ф Z "1 Ф • ■ ■ ф Z <*к (если т = 0, то первое слагаемое отсут-1 ^ к

ствует). Ясно, что кольцо R коммутативно и среди его гомоморфных образов нет поля Z2l то есть I(R) = 0 по предложению 3. Кроме того, кольцо R не является полупростым. Значит, по теореме 1 мы