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

• Автор: Крохин, Андрей Анатольевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1998
• Место защиты: Екатеринбург
• Количество страниц: 80 с.

Содержание
Содержание
Введение
§1. Конечные и счетные моноидальные интервалы
§2. Моноидальные интервалы и отношения квазипорядка
§3. Моноидальные интервалы и отношения
эквивалентности
§4. Моноидальные интервалы и центральные отношения
§5. Моноидальные интервалы и максимальные клоны
на трехэлементном множестве
§6. Моноидальные интервалы и константные функции
§7. Заключительные замечания
Литература
Указатель обозначений

ВВЕДЕНИЕ
1° Теория клонов находится на стыке трех дисциплин: математической логики, универсальной алгебры и математической кибернетики. Понятие “клон” (и близкие к нему понятия “замкнутый класс” и “итеративная алгебра”) возникает естественным образом как обобщение понятия “моноид (полугруппа) преобразований” на случай функций многих переменных при изучении операции суперпозиции функций, заданных на некотором множестве. Так, многие свойства (универсальной) алгебры зависят не от выбора основных операций, а от того, какие функции могут быть получены из них при помощи суперпозиции. В кибернетике суперпозиции соответствует конструирование сложных устройств из более простых. Наконец в математической логике важную роль играет суперпозиция истинностных функций.
Специалистом именно по математической логике Э.Постом были написаны в 20-40-х годах нашего века работы ['26, 27], считающиеся одними из первых публикаций по теории клонов. С тех пор теория клопов плодотворно развивалась и к настоящему времени обрела четкие контуры, собственную богатую проблематику и содержит большое число результатов. Имеющаяся литература весьма обширна, поэтому упомянем здесь лишь несколько работ обзорного характера и монографий
[6. 9, 12, '25, 35].
Как и многие другие конкретные объекты, изучаемые в обшей алгебре (например, многообразия групп, полугрупп или колец), клоны на фиксированном множестве удобно классифицировать при помощи решетки, которую они образуют. Таким образом, исследование решеток клонов является одним из важнейших направлений в теории клонов.
Полностью описать решетку клонов на конечном множестве (т.е. построить ее диаграмму) удалось лишь в одном простейшем нетривиальном случае, и это описание было потом использовано при решений многих (не только алгебраических) задач. В остальных нетривиальных случаях подобное описание вряд ли возможно в силу некоторых утверждений, которые будут сформулированы ниже.
Поскольку практически во всех случаях решетку клонов нельзя описать “глобально”, возникает задача “локального” описания этой решет-

ки, т.е. описания (или характеризации) ее интервалов. Этому направлению в изучении решеток клонов и посвящена данная диссертация.
2° Введем некоторые обозначения и определения. Пусть А — конечное множество, |А| > 2. Через О а обозначается множество всех конечноместных функций (или операций) на А. Если К С О а и в 6 К, то через Р‘п> обозначается система всех п-местных функций из П. Множество С С О а называется клоном на А, если для любых / € С(п дъ
Говорят, что функция / £ О а сохраняет отношение р С Ат (для удобства договоримся записывать элементы отношений в столбик; символ Т обозначает транспонирование), если для любой матрицы Т — (ву)тх„, столбцы которой принадлежат р, столбец
/(-? ) — (/(а1Ь 1 ] /(ат17 - 1 П?пп))
построчных значений функции / также принадлежит р. Через Ро1р обозначается совокупность всех функций, сохраняющих отношение р, а через Рокр — совокупность всех таких унарных функций. Мы используем обозначение Ро1р (а не (Ро1ррг'), потому что оно общепринято в соответствующей литературе. Мы будем говорить, что множество функций К С О а сохраняет множество 5 отношений на А, если каждая функция из К сохраняет каждое отношение из 5.
При А = 2 решетка полностью описана в [26, 27], она оказалась счетной. Таким образом, любой вопрос относительно интервалов этой решетки может быть решен при помощи этого описания. Всюду далее мы будем предполагать, что |А| > 2.
Известно, что в этом случае решетка С а континуальна [10] и удовлетворяет лишь тривиальным решеточным тождествам [1]. Кроме того,

Из равенств (4) и (5) следует, что если то удовлетворяет условию (ml) или условию (m2), то для всех п, I верно
umfn,i{x1
а если те удовлетворяет условию (m3), то для всех п, I
ит/хг
Таким образом, при подстановках функций из С0э в функции из С М мы можем ограничиться рассмотрением подстановок только проекций и константных функций а0 и b (сама функция Ь может и не принадлежать моноиду М).
Пусть / € Соо. Обозначим через Т(/) множество всех таких функций 9 Е Соо, что д может быть получена из / отождествлением и перестановкой аргументов и подстановками «о и 4 вместо некоторых аргументов. Положим
Tm[jT(fnJ).

Тогда любая функция из Соо М, существенно зависящая от всех своих аргументов, имеет вид тд, где то £ М, д Е Т. Из (6) и (7) вытекает также, что для любых клонов С, С2 Е [{М); Соо] мы имеем
. Сг V С2 = С, U С2. (8)
Покажем, что Сх Е IntM. Возьмем произвольную функцию fn.i и mi
В силу (8) МЫ имеем Со = М) | / £ Соо и Vu, / fnJ $ (f,M)},
а отсюда следует, ЧТО Со = {/ £ Соо I Уп,1 /„,( (f,M)}. Очевидно, что Со Е IntM (т.к. Со Е [(М);Соо]) Таким образом, мы доказали, что интервал [Со; С«,] лежит в интервале IntM. Отметим также, что для любых п, I мы имеем fng tjL Со-
Этап 2. Обозначим через М множество {то £ М | 3то £ М со свойством тта(аг) = а,- при г = 0,1}. Преобразование то назовем {ao,«i}~ обратным к то.