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

• Крохин, Андрей Анатольевич
• кандидат физико-математических наук
• 1998

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

Содержание

Содержание

Введение

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

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

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

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

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

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

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

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

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

Литература

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

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

ВВЕДЕНИЕ

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 мы имеем равенство \IntM\ =

Пусть теперь \А\ = 2т (|А| = 2тр\ ■ ■ -рк)- Если т = 4, то в качестве Я можно взять кольцо GF(4)[х]/(.т2) (®ZPl ф ■ • • ф ZPk), где GF(4)[x}/(x2) есть фактор-кольцо кольца многочленов от одной переменной над полем GF(4) по идеалу, порожденному многочленом х2. Опять же непосредственно проверяется, что кольцо Я не является полупростым, и что среди его гомоморфных образов нет двухэлементного поля. Значит, как и в предыдущей ситуации, \IntMn\ = Если же т. > 5, то положим я = GF(A)[x}/(x2)®GF(2т~4) (OZPie- ■ -®ZPk) и, рассуждая аналогично предыдущему случаю, получаем, что \IntMji\ = Ко-

Итак, остается неизвестным, существуют ли счетные моноид ал ьные интервалы в Ca, если |А| = 2п, где п — нечетное число, большее 1, или если |А| = 2тп, где п — нечетное число, свободное от квадратов, а т G {0,2,3,5}.

Приведем теперь конкретные примеры счетных моноидальных интервалов. Пусть Я = Zp2, где р — нечетное простое число. Тогда непосредственно проверяется, что интервал IntMr = [(Mz 2); Lzp2] есть цепь типа и; + 3

(.MZp2) С Ci С С2 С • • • С Соо С С' С Lzp2, где Сп = (Mz 2) U {а0 + а,грхг|s < п,а0,аг £ Zp2}, С^ = U^i Сп, a

клон С' состоит из всех функций / £ Lz 2 таких, что все коэффициенты при переменных в /, быть может, кроме одного, делятся на р.

Перейдем к изучению конечных моноидальных интервалов. Из теоремы 1 следует, что если кольцо R есть прямая сумма конечного числа конечных полей, R = Fi © • • • © Fn, таких, что \Ft\ > 2 при 1 < г < п, то интервал ItlIMr конечен. Мы уточним строение таких интервалов.

Теорема 2 Пусть R = Fi © • • • © Fn, где Fi — произвольные конечные поля, каждое из которых содержит более двух элементов. Тогда

(1) интервал IntMn имеет атомов;

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

(3) при п > 3 интервал IntMn немодулярен.

Итак, как следует из теоремы 2, любая конечная дистрибутивная решетка изоморфно вложима в подходящий конечный моноидальный интервал, который может быть даже не модулярным. В §5 будет приведен еще один пример конечного немодулярного моноидального интервала при |А| = 3.

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

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

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

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

(ml) т(Ао) С A0jm(Ai) С Ах; (т2) т(А) С А0;

(тЗ) т(А) С Аг.

Функцию и(х) €Е Ро1\ц назовем характеристической для разбиения 7г, если найдутся а0, аг £ Л0, а0 ф а1} такие, что и(х) = а0 для всех ж € А0 и м(ж) = <21 для всех х £ А\.

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

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

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

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

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

В изучении строения конечных (универсальных) алгебр важную роль играют так называемые минимальные и Е-минимальные алгебры (см. [8]). Напомним определения этих понятий. Пусть А = (А,Р) - конечная алгебра. Через Р(А) обозначим клон полиномиальных операций алгебры А (т.е. клон, порожденный множеством функций Р и всеми константными функциями), а через Р\{А) - множество унарных функций из Р(А). Алгебра А называется минимальной, если всякая неконстантная операция из Р\{А) является перестановкой на множестве А. Через Е(А) обозначается множество идемпотентов моноида Р\{А) (т.е. множество таких е £ Р\{А), что е о е = е). Конечная алгебра А называется Е-минимальной, если Е(А) состоит из всех константных операций

и тождественного преобразования id. В частности, всякая минимальная алгебра будет Е-минимальной, а всякая двухэлементная алгебра -минимальна и Е-минимальна. Конечные алгебры с общим носителем называются полиномиально эквивалентными, если они имеют одинаковые клоны полиномиальных операций. Известно [26], что существует только семь попарно полиномиально неэквивалентных двухэлементных алгебр. Вопрос о числе попарно полиномиально неэквивалентных алгебр на конечном более чем двухэлементном множестве был известен как вопрос Маккензи. В работе [11] найдено континуальное число попарно полиномиально неэквивалентных алгебр, но все они не являются Е-минимальными. П.П.Палфи доказал [23], что полиномиально неэквивалентных минимальных алгебр на конечном более чем двухэлементном множестве - конечное число, а именно, это (с точностью до полиномиальной эквивалентности) конечные векторные пространства над конечным полем и алгебры вида (Л,С), где G - группа перестановок, действующих на А. Ввиду близости определений минимальности и Е-минимальности алгебр представляет интерес вопрос о числе полиномиально неэквивалентных Е-минимальных алгебр на более чем двухэлементном множестве.

Следствие 4 На конечном множестве А, содержащем более двух элементов, существует 2К° попарно полиномиально неэквивалентных Е-минимальных алгебр.

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

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

{m G Pol\e\m(A) Ç {a, b} и если(х,у) G е, то т(х) = т(у)} U {id}.

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

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

При изучении счетных и конечных моноидальных интервалов мы рассматривали моноиды вида Мд, и находили мощности интервалов IntMp, при условии I(R) = 0. Пусть теперь I(R) П J(R) ф 0, где через J(R) обозначается, как обычно, радикал Джекобсона кольца R. Тогда, как будет доказано в §3, во множестве I(R) П J(R) найдется элемент г, отличный от 0, такой, что для всех х G R выполнено условие гх G {0, г}.

Следствие 6 Пусть I{R) П J(R) ф 0. Если моноид M состоит из полиномиальных функций кольца R и содержит функции гх и гх + г, где r G R — такой, как указано выше, то в интервале IntM найдется подинтервал, изоморфный булеану на счетном множестве.

В частности, при I(R) П J(R) ф 0, мы имеем \IntMn\ = 2N°.

Моноидальные интервалы можно изучать, отталкиваясь не только от свойств моноида преобразований M, но и от свойств его стабилизатора StM. Как было сказано ранее, всякий максимальный клон С. за исключением клона Слупецкого 57, представим в виде С — St(C^). Для дальнейшего изложения нам потребуется формулировка теоремы Розенберга о полноте. Мы приведем ее, предварив необходимыми определениями.

Отношение р С Ah, 1 < h < |А|, называется центральным, если оно вполне рефлексивно (т.е. если |{жь . . •, х^} \ < h, то (xi,...,x^)T G р), вполне симметрично (т.е. если {х\,. . ., ж/г)т G р и 7Г — произвольная перестановка на множестве {1,. . ., h}, то (ж^а),.. ., x7r(h))T é /)), и имеет непустой центр с(р), где с(р) = {a G А|{а} X Ah~l С р}. Отметим, что любое непустое собственное подмножество В из А считается одноместным центральным отношением.

Пусть т>1иЗ</г<|Л|. Семейство отношений эквивалентности W = {01 ,...,вт} на А называется h-регулярным, если при 1 < г < m 6i имеет h классов, и если pi^Li В{ ф 0 для произвольных классов Д-отношений 9г (1 < г < т). Отношение Xw-, определяемое семейством W, состоит из всех столбцов (xj,... ,хь)Т таких, что при любом 1 <

I < то найдутся различные i,j (зависящие от I) такие, что (x{,xj) Е 9¡. Отношения вида А(у называются регулярными.

Согласно теореме Розенберга [28] максимальные клоны на А — это в точности клоны вида Polp, где р — отношение одного из следующих типов:

(Ö) ограниченный частичный порядок;

(V) {(х,д(х))т\х Е А}, где д — перестановка простого порядка без неподвижных точек;

(Л) {(ж, у, z. г;)т|ж у = z + v}, где (А, +) = Z™, р — простое число;

(£) нетривиальное отношение эквивалентности;

(С) центральное отношение;

(1Z) регулярное отношение.

В [13] доказано, что любой максимальный клон, кроме клонов типа (Л), имеет континуум подклонов. Решетка подклонов максимального клона типа (Л) конечна, если \А\ — простое число [30], и счетна в противном случае [20]. Если мы хотим выяснить, каково число подклонов данного максимального клона С, содержащих множество то, за

исключением случая клона SI, мы должны найти мощность интервала IntC(1).

Из результатов работы [33] следует, что если М = Polip, где р — отношение типа (V), причем |А| — простое число, то IntM — трехэлементная цепь.

Пусть теперь М = Ро1^р7 где р — аффинное отношение, т.е. отношение типа (Л). Тогда клон StM состоит из всех функций вида J2 гг(жг) + а, где А рассматривается как n-мерное векторное пространство над простым полем Zp, а 6 A, a r¿ — линейные преобразования этого векторного пространства. В работе [31] доказано, что в этом случае IntM есть (п + 1)-элементная цепь (М) С К\ С К2 С • • • С Кп = StM, где Ki (1 < I < п) состоит из всех функций, принадлежащих клону (М), и всех функций вида J2i=iri(xi) + а таких, что k > 1, а Е А и сумма Im(ri) + ••• + Im(rk) образов преобразований гг есть не более чем /-мерное подпространство в векторном пространстве А над полем Zp.

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

Следствие 7 (1) Если С — максимальный клон типа (£), то верно равенство \1пЮ^\ =

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

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

Теорема 5 Если С — максимальный клон типа (С), то \1п1С^\ — 2Н°.

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

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

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

Известно, что число клонов на А, содержащих все унарные функции / такие, что \Imf\ < |А| — 1, или содержащих все перестановки, т.е. унарные функции / такие, что Imf = А, конечно (см. соотв. [35] с.72 и [17]). С другой стороны, как доказано в [11], множество всех клонов на А, содержащих все константные функции, континуально.

Принимая во внимание все эти утверждения, естественно поставить вопрос о числе клонов на А, содержащих все унарные функции / со свойством \Imf\ < |А| — 2. Однако если а — (|А| — 1)-местное центральное отношение, то {/ £ О^ '■ \Tmf\ < \А\ — 2} С Ро1ха. Таким образом, из теоремы 5 следует, что на конечном множестве А таком, что |А| > 2, существует 2^° клонов, содержащих все унарные функции со свойством \Irnf\ < |А| —2. Используя конструкции, приведенные в §4, мы докажем более общее утверждение.

Предложение 5 На конечном множестве А таком, что \А\ > 2, существует 2^° клонов, содержащих все функции / £ О а со свойством \Imf\<\A\-2.

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

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

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

1. Три клона Pol {а}, где а £ А;

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

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

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

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

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

8. L = {J2aixi + a0(mod3)\a0, аг £ А}.

Из вышесказанного следует, что если С — максимальный клон типа 1-4 из списка Яблонского, то \IntC'^\ = 2N°, и что IntSl^ является 4-элементной, IntPolitp — 3-элементной, а

IntLW — 2-элементной цепью. Неисследованными остались только интервалы IntPoli <. Без ограничения общности определим порядок < следующим образом: 0 < 1 < 2. В работе [22] найден полный список из 13 максимальных подклонов клона Pol <. Приведем этот список.

1. Два клона Pol < Г\Ро1{а}, где а Е {0, 2};

2. три клона Ро1< Г)Ро1{а, 6}, где a, fe £ А;

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

4. два клона Pol< DPole, где е — одна из двух нетривиальных кон-груэнций решетки (A,min,max);

5. Pol< nSl;

6. (Poli <, max)]

7. (Poli <, min).

Непосредственно проверяется, что лишь три последние клона из этого списка принадлежат интервалу Int Pol i<. Оказывается, что остальные клоны из IntPoh < (кроме Ро1<) представимы в виде пересечений этих клонов.

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

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

РоК

Рис.2

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

максимальный клон С

Ро1{а}

Ро1{а,Ь) 2К°

Pola

Pole 2«о

Pol< 7 (см. Рис.2)

SI 4 (цепь)

Poltp 3 (цепь)

L 2 (цепь)

Таблица 2

В §6 мы изучаем интервалы 1п1М, где М С С а- Клон С принадлежит такому моноидальному интервалу, только если все унарные функции из С, отличные от тождественного преобразования, суть константы. Пусть моноид М состоит из тождественного преобразования и / константных функций, где I < |А|. Если I — |А|, то М — С а- и, как видно из таблицы 1, имеет хместо равенство \1пЬМ\ = 1. Если / < |А| — 2, то, как непосредственно следует из теоремы 6, мы имеем |/п£М| = 2К°.

Значит, нам осталось разобрать случай, когда / = |Л| — 1. Опять же, без ограничения общности можно считать, что А = {0,1,. .., к — 1} и М = {id,0A,...,k -2}.

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

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

(V,A,0,1)

(М)

Рис.3

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

Теорема 9 Если \А \ > 3 и М = 0,1,2...., к - 2], то \ШМ\ = 1.

Таковы основные результаты диссертации. Они опубликованы в работах [38, 39, 40, 41, 42, 43, 44, 45, 46] и докладывались на III Международной конференции по алгебре (Красноярск, 1993 г.), Международной конференции по математической логике (Новосибирск, 1994 г.), 52-й конференции по общей алгебре и дискретной математике (Потсдам, Германия, 1996 г.), на семинарах "Алгебра и логика" и "Алгебраические системы" Института математики СО РАН и Новосибирского государственного университета, семинаре "Алгебра" Технического университета г.Дрездена (Германия), семинарах "Дискретная математика" и "Алгебраические системы" Уральского государственного университета.

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

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

Основным результатом этого параграфа является утверждение о существовании большого класса счетных моноидальных интервалов

Определим на множестве А структуру ассоциативного кольца Я с единицей 1. Зачастую, если это не приводит к недоразумению, в этом параграфе мы будем отождествлять А и Я.

Пусть 1(Я) = {г £ Я\г(х2 — х) = 0 для всех х £ Я}. Это множество играет важную роль в наших исследованиях счетных и конечных моноидальных интервалов.

Лемма 1 Множество 1(Я) является двусторонним идеалом кольца Я. ДОКАЗАТЕЛЬСТВО.

Ясно, что 1(Я) является левым идеалом в Я. Возьмем г Е 1(Я), з € Я и покажем, что г в £ 1{Я), т.е. что условие гз(х2 — х) — 0 выполнено для всех х Е Я. Мы имеем г ((ж + у)2 — (х + у)) = 0 для всех х,у £ Я. Поскольку г(х2 — х) = 0 и г(у2 — у) = 0, получаем гху + гух = 0, в частности, (если у = 1) 2гх = 0. Следовательно, гх = — тх и гху = гух. Подставляя теперь в последнем равенстве з вместо х и х2 — х вместо у, мы получаем гй(х2 — х) = г(х2 — = 0. Итак, идеал 1(Я) — двусторонний. □

Обозначим через Кц множество всех полиномов / кольца Я таких, что всякий нелинейный одночлен в / имеет коэффициент из 1(Я) (мы рассматриваем свободный член как линейный). Следующее утверждение является ключом к исследованию интервалов 1п1Мц.

Предложение 1 (1) Если М С Мц, то вЬМ С Кн;

(2) 5ШЛ = К к-ДОКАЗАТЕЛЬСТВО.

Докажем сначала первое из утверждений предложения при помощи индукции по числу переменных функций. База индукции очевидна, так как МСМдС (Кц)(1). Пусть п > 1, (б'Ш)^ С (Ая)(п). Возьмем функцию /(ж1;...,жп+1) £ и покажем, что / £ (А'й)(п+1).

Зафиксируем произвольные х\,...,хп 6 Я. Ввиду того, что С а С М, мы получаем равенство

/(жх, . . . , Хп, Ж„_|_х) = г(жх, . . . , Хп)хп+1 -+" ..., ж„), (1)

где г(жх,..., хп) и з(жх,... , ж„) — элементы из Я, зависящие от ж1?..., хп. Таким образом, г из являются п-арными функциями на Я. Заменив в (1) жп+1 на ноль, мы получаем /(жх,..., жп, 0) = з(жх,. .., хп). По предположению индукции з(жх,. . ., хп) — это многочлен и, более того, он принадлежит множеству Кц. Заменив в (1) жп+1 на 1, мы получим

г( Х-[. . . . , Хп) = /(жх,.--,Жп,1) — 5(ж1,...,жга).

Таким образом, г (ж 1}. . ., ж п) и . . ., ж„+1) являются многочлена-

ми, и, поскольку сумма многочленов из Кц есть снова многочлен из К к, мы имеем г(жь ... ,хп) £ Кя. Пусть г(х1, ... ,хп) = /х(жх,..., хп) + Тя=\агхг + ао, где все коэффициенты в /1 принадлежат идеалу 1(Я). Тогда

п

/(ж'1, . . ., хп+1) = ... ,хп) • жп+1 + ^ а{хгхп-!г1 а0хп+х + .§(жх ,...,!;„).

¿=1

Зафиксируем число г такое, что 1 < г < п. Отождествляя хг и жп+1 с ж и подставляя 0 вместо остальных переменных, мы получим /(О,. . . , ж, . . ., 0, ж) = агх2 + Ьх + с для некоторых 6, с £ Я. Эта функция принадлежит моноиду М. Поскольку тх + т2 £ Мд при т^тг £ Мд, получаем а,ж2 + Ьх + с + ( —Ьж — с) = агж2 £ Мл. Тогда агх2 = Ь\ж + для некоторых 61, £ Я. Легко убедиться, что в этом случае С\ = 0 и Ьх = аг-. Отсюда а,ж2 = агж и а,- € 1(Я) Для всех 1 < г < п. Таким образом, функция /(ж17 • . . ,жп+х) принадлежит множеству А'д как сумма полиномов из К л, и первое утверждение предложения 1 доказано.

Для доказательства второго утверждения достаточно показать, что Кл С БШц. Покажем это. Любой нелинейный одночлен в произвольном многочлене / £ К л имеет вид гжг • • -жп, где г £ 1(1%), поскольку, как вытекает из определения множества Кц и доказательства леммы 1, для всех г £ -/(Я), х,у £ Я справедливо г ж2 = га и гху = гуж. В силу этих равенств и леммы 1 для любых аг,. . . , ап, Ьх,,. . ., Ъп £ Я мы имеем г (ах ж + Ьх)'' • + Ь„) £ Мд, откуда непосредственно следует, что / £ 5Шд. □

Следствие 1(1) Если 1(Я) = 0 и СА С М С Мн, то 5Ш С

(%) = Ьп тогда и только тогда, когда 1(Я) = О.

Таким образом, в случае, когда 1(Я) = 0 и Сл С М С Мя, интервал /п^М целиком содержится в решетке впЬЕц.

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

ДОКАЗАТЕЛЬСТВО.

По следствию 1 мы имеем /п^Мя = [(Мя); ¿я]- Напомним, что имеет место неравенство |[(Мя);£я]| < К0.

Пусть кольцо Я не является полупростым, т.е. -1(Я) ф 0, где через ■1(Я) обозначается, как обычно, радикал Джекобсона кольца Я. Возьмем г £ ^{Я))п., г ф 0, где п таково, что (.1(Я))п ф 0, но (,1(Я))п+1 = 0,

ш

и рассмотрим последовательность клонов Ст = (Мя, гхг)7 то > 2. Яс-

г = 1

но, что Ст £ 1гЛМц для каждого то. Нетрудно показать, что каждая функция из Ст, имеющая более одной существенной переменной, имеет вид згх/г + а, где к < т и 6 (</(7?))™ для всех 1 < г < к. Число существенных переменных не может быть увеличено, поскольку для любых г, 5 £ (3(Я))п мы имеем гз = 0. Поэтому последовательность Сг С Сз С • • • С Ст С • • • является бесконечной возрастающей цепью в интервале 1п1Мп. Итак, в случае ф 0 интервал 1пИИц счетен.

Пусть теперь кольцо Я полупросто. Мы докажем, что тогда каждый клон С £ 1п1Мц представим в виде С = (Мя, /!,...,/„), где функции /!,...,/„ выбираются из некоторого конечного множества и (Я) С Ьд. Отсюда непосредственно следует, что интервал 1п1М конечен.

По классической теореме Веддербарна кольцо Я изоморфно прямой сумме полных матричных колец над конечными полями. Мы будем использовать тот факт, что каждый правый идеал Т в Я обладает левой единицей е? Е Т. Обозначим через и (Я) множество всех функций / £ Ьц таких, что все коэффициенты в / суть идемпотен-ты кольца Я (т.е. е £ Я такие, что е2 = е), ни один из идемпотен-тов не встречается в / более двух раз, и / не имеет свободного члена. Очевидно, что множество и (Я) конечно. Мы покажем, что для любой функции д £ Ьп найдется функция / £ и (Я) со свойством

(д,Мя) = (f,MR). Пусть д = Е ггХг- Так как для любого а £ R

¿=1

функция х + а принадлежит моноиду Мл, мы можем считать, что д не имеет свободного члена. Обозначим через Т{ = rzR правый идеал кольца R, порожденный элементом гг-, а через ег- £ Тг — левую единицу идеала Тг-. Тогда е,- = r{Si для некоторого Si £ R. Поэтому

п п

/х(ж!,..., хп) = д(з1хъ ... , snxn) = £ TiSiXi = Е eixt £ (д, Мл). Некото-

г=1 i=1

рые идемпотенты могут встречаться в fx более двух раз. Подставим нули вместо некоторых переменных функции /х, чтобы удалить "лишние" вхождения таких идемпотентов, и обозначим получившийся многочлен через /. Если идемпотент е входил в /а один раз, то он входит один раз ив/. Если е входил в более одного раза, то он входит в / в точности дважды. По построению мы получили / £ U(R) и / £ (д,Мл)■ Для того, чтобы доказать равенство (д,Мл) = {/,Мл), мы должны показать, что д £ (/, Мл). Докажем сначала, что /i £ {/, Мл). Мы должны "воспроизвести" в нужном количестве те идемпотенты, которые встечаются в /i более двух раз. Предположим, что / = е\Х\ + ехх2 + Е с-%хг. Подста-

г> 3

вляя 0 в / вместо переменных Хз,. . . , хп, получим е\Х\ + eix2 £ (/, Мл)-

71—1 П-\-1

Заметим, что для п > 2 мы имеем Е е1хг' + (eia^ -f ei.Tn+1) = Е £

f = l ¿=1 (/, Мд). Допустим, что ej встречается пг > 3 раз среди коэффициента!

тов многочлена /х . Подставляя Е eiVi вместо х2 в /, мы получаем

i=2

eiXx + exyz + ••• + eii/щ + Е eixi G (f,MR)- Проделав ту же проце-

?:> з

дуру для всех идемпотентов ег входящих в /i более двух раз, и переименовав затем переменные подходящим способом, мы показываем, что

fi(x 1, . . . , £n) £ (/, Мд). А так как ег- является левой единицей для гг, поп п

лучаем /а(ггжь . . .,rnxn) = Е егггжг = Е = • . . ,х„) £ (/, Мд).

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

Литература

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

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

[3] Бурле Г.А. Классы fc-значной логики, содержащие все функции одной переменной, Дискр.ан., 10, 1967, 3-7.

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

[5] Кузнецов A.B. О проблемах тождества и функциональной полноты алгебраических систем, Тр. III Всесоюзн.мат.сьезда, Москва, АН СССР, 1956, 145-146.

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

[7] Мальцев И.А. Некоторые свойства клеточных подалгебр Поста и их основных клеток, Алгебра и логика, 11,6, 1972, 571-587.

[8] Хобби Д., Маккензи Р. Строение конечных алгебр,-М.:Мир. 1993.

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

[10] Янов Ю.И., Мучник A.A. О существовании ¿-значных замкнутых классов, не имеющих конечного базиса, ДАН СССР, 127, 1, 1959, 44-46.

[11] 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.

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

13] Demetrovics J., Hannak L. The number of reducts of a preprimal algebra, Algebra Universalis, 16, 1983, 178-185.

14] Demetrovics J., Hannak L. Construction of large sets of clones, Z.Math.Logik Grundlag.Math., 33, 1987, 127-133.

15] Grabowski J.-U. Binary operations suffice to test collapsing of monoidal intervals, Algebra Universalis, в печати.

16] Haddad L., Rosenberg I.G. Un intervalle Booleen de clones sur un univers fini, Ann. Sei. Math., Quebec, 12, 2, 1988, 211-231.

17] Haddad L., Rosenberg I.G. Finite clones containing all permutations, С an. J.Math., 46, 5, 1994, 951-970.

18] Ihringer T. A remark on clones and permutation groups Contributions to General Algebra 7, Proc. Conf. Wien, Verlag Hölder-Pichler-Tempsky, Wien, 1990, 197-200.

19] Ihringer Т., Pöschel R. Collapsing clones, Acta Sei. Math. (Szeged) 58, No.1-4, 1993, 99 - ИЗ.

20] Lau D. Uber die Anzahl von abgeschlossenen Mengen linearer Funktionen der n-wertigen Logik, EIK, 14, 1978, 567-569.

21] Lau D. Bestimmung der Ordnung maximaler Klassen von Funktionen der ¿-wertigen Logik, Z.Math.Logik Grundlag.Math., 24, 1978, 79-96.

22] Machida H. On closed sets of three-valued monotone logical functions Finite Algebra and Multiple-valued logic, Proc.Conf. Szeged, 1979, Colloq.Math.Soc.Sci.J.Bolyai, 28, 1981, 441-467.

23] Pälfy P.P. Unary polynomials in algebras, I, Algebra universalis, 18, 1984, 262-273.

24] Palfy P.P., Szendrei A. Unary polynomials in algebras, II, in: Contributions to General Algebra,2 (Proc. Conf. Klagenfurt, 1982), 1983, 273-290.

25] Pöschel R., Kaluznin L.A. Funktionen- und Relationenalgebren, Ein Kapitel der diskreten Mathematik, Berlin: VEB DVW, 1979.

[26] Post E. Introduction to a general theory of elementary propositions, Amer. J. Math., 43, 1921, 163-185.

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

[28] Rosenberg I.G. Uber die funktionale Vollständigkeit in den mehrwertigen Logiken (Struktur der Funktionen von mehreren Veränderlichen auf endlichen Mengen), Rozpravy Ceskoslovenske Akad. Vëd. Rada Mat. Prirod. Vëd., 80, 1970, 3-93.

[29] Rousseau G. Completeness in finite algebras with a single operation, Proc. Amer.Math.Soc., 18, 1967, 1009-1013.

[30] Salomaa A.A. On infinitely generated sets of operations in finite algebras, Ann.Univ.Turku., Ser.AI 74, 1964, 1-12.

[-31] Szabo L., Szendrei A. Slupecki-type criteria for quasilinear functions over a finite dimensional vector space, EIK, 17, 1981, 601-611.

[32] Szendrei A. Clones of linear operations on finite sets, in: Finite algebra and multiple-valued logic, Proc. Conf. Szeged, 1979, Colloq.Math.Soc.J.Bolyai, 28, 1981, 693-738.

[33] Szendrei A. Algebras of prime cardinality with cyclic automorphism, Arch. Math. (Basel), 39, 1982, 417-427.

[34] Szendrei A. Short maximal chains in the lattice of clones over a finite set, Math.Nachr., 110, 1983, 43-58.

[35] Szendrei A. Clones in universal algebra, Séminaire Math. Supérieures 99, Les Presses de l'Université de Montreal, 1986.

[36] Szendrei Â. Term minimal algebras, Algebra Universalis, 32, 4, 1994, 439-477.

[37] Tardos G. A maximal clone of monotone operations which is not finitely generated, Order, 3, 1986, 211-218.

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

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

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

[41] Krokhin A.A. it 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.

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

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

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

[45] Krokhin A.A. On clones, transformation monoids, and associative rings, Algebra Universalis, Ъ^А. 52 ».

[46] Krokhin A.A. Boolean lattices as intervals in clone lattices, Int.J. Multiple-Valued Logic t {$67, Z€3~2Jfd.

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

аг(/) 44 Сл ю

Соо 34 с(р) 15

/)(/) 43 ¿гп 5 Рп 51

Е(Л) 13 еж 48

1п,1 34 , Р 34

р(п) 4 /(Г) 4

гсЦ, гс1 4 /ш/ 4

ШМ 5 /(Л) 10

15 Ая 10

¿л 4 ЦС) 40

¿я Ю М,ш 35

Мл 10 1% 33

С л 4 Р(Л),Р!(Д) 13

Ро1Р,Ро11Р 4 5/ 9

5Ш 5 Та 5

Г(Л),Та(Л) 6 Т(/) 35

£/(Я) 24 Гг,дг(У) 28