Содержание к диссертации
Введение
1 Клетки и клеточные алгебры 1
1.1 Итеративные алгебры 1
1.2 Транзитивные полугруппы 7
1.3 Структурные свойства 12
1.4 Свойства базисов 20
1.5 Максимальные подалгебры 26
1.6 Число подалгебр 35
2 Решетка подклонов клона Бурле 42
2.1 Строение нижней части решетки 42
2.2 Решетка подклонов клона ZQ 53
2.3 Клоны типов *ТС, 2/С, 2*К, *К при К, < Z0 80
2.4 Другие подклоны клона Z0UZ2, порождаемые с помощью унарных функций из . 92
2.5 Подклоны клона ZQ U ZI, порождаемые с помощью много местных функций И3^2 104
3 Гомоморфизмы 112
3.1 Конгруэнции на клетках 112
3.2 Конгруэнции на некоторых подалгебрах клеток . 120
3.3 Гомоморфизмы итеративных алгебр и свойства оснований этих алгебр 127
3.4 Конгруэнции на клеточных подалгебрах 136
3.5 Гомоморфизмы вполне ограниченных расширений итеративных алгебр 144
3.6 Автоморфизмы 155
3.7 Инварианты 157
4 Гипертождества 165
4.1 О разделении клонов гипертождествами 165
4.2 Гиперподстановки 173
4.3 Некоторые приложения 181
4.4 Выделение гипертождествами квазиклеток 185
5 Согласованные произведения 201
5.1 Транзитивные полугруппы в произведениях итеративных алгебр 201
5.2 Теорема Слупецкого 215
Литература 230
Предметный указатель 243
Оглавление З
Список обозначений 246
Указатель имен 249
- Транзитивные полугруппы
- Максимальные подалгебры
- Другие подклоны клона Z0UZ2, порождаемые с помощью унарных функций из .
- Гомоморфизмы вполне ограниченных расширений итеративных алгебр
Введение к работе
Суперпозиция, то есть замена одной из переменных функции также функцией, является одним из простых и естественных способов получения новых функций из уже имеющихся. Возникающая в результате суперпозиций функция называется сложной. Одни свойства исходных функций наследуются сложной функцией, другие же не сохраняются. Например, при суперпозиции возрастающих функций получается также возрастающая функция. Закономерный интерес вызывает вопрос, можно ли всякую функцию, обладающую каким-то заданным свойством, получить при помощи суперпозиций из функций, обладающих тем же свойством, но зависящих от меньшего числа переменных. В качестве свойства обычно выбирается непрерывность, дифференцируемость и т. п.
Упомянем лишь некоторые результаты в указанном направлении, полученные отечественными математиками А. Г. Витушкиным, А. Н. Колмогоровым и В. И. Арнольдом. Если натуральные числа га, п, гаї, п\ удовлетворяют неравенству то, как доказал А. Г. Витушкин [9], существует зависящая от га пере Введение ii менных п раз дифференцируемая функция, которую нельзя получить суперпозициями из п\ раз дифференцируемых функций, зависящих от mi переменных. А. Н. Колмогоров [32] и В. И. Арнольд [1] доказали, что каждая вещественная непрерывная функция представима в виде суперпозиции непрерывных функций, зависящих от двух переменных. Любую непрерывную функцию от нескольких переменных можно получить при помощи суперпозиций из функции г + 2/и непрерывных функций, зависящих от одного аргумента (Колмогоров, [33]).
В приведенных выше примерах решаемые задачи можно сформулировать следующим образом.
Каким-то способом заданы два множества функций М\ и Мг- Можно ли каждую функцию из множества М\ получить суперпозициями функций, принадлежащих множеству Мг К этой задаче близка следующая.
Задан класс функций К. Описать все функции, которые можно получить суперпозициями функций, принадлежащих К.
Функции, получаемые при помощи суперпозиции из функций класса К, образуют множество [К], называемое замыканием класса К. Класс К называется порождающим для своего замыкания. Если К = [К], то класс [К] называется замкнутым. Описание множества [Мг] ведет к решению первой из указанных выше задач: функции из множества Mi можно получить суперпозициями функций, принадлежащих множеству Mi тогда и только тогда, когда множество М\ является подмножеством замыкания множества Мг. Однако решение первой задачи может и не зависеть от решения второй. Рис. 1. Решетка Поста.
Задача описания замыкания множества функций М имеет смысл только при существенных ограничениях на входящие в М функции. Одним из таких ограничений является фиксирование числа элементов в множестве, на котором определены функции из М. Э. Постом [60, 61] описаны все замкнутые классы функций, определенных на множестве из двух элементов. По включению эти классы образуют решетку, изображенную на рисунке 1, называемую решеткой Поста.
На множестве из трех элементов имеется континуум замкнутых классов ([97]), образующие решетку очень сложного строения, поэтому при ходится дополнительно ограничивать множество изучаемых классов.
Замкнутые классы функций и свойства порождающих их систем изучались во многих работах по математической логике, поскольку операции, определенные на конечном множестве, используются при интерпретации связок в различных исчислениях. Формулам при таких интерпретациях отвечают сложные функции, принадлежащие замкнутым классам, порождаемым этими операциями. Особое внимание привлекала проблема полноты: найти условия, необходимые и достаточные для того, чтобы система функций, определенных на конечном множестве, порождала замкнутый класс, содержащий все функции, определенные на этом множестве. Как уже говорилось, проблема полноты в классе всех функций, определенных на множестве из двух элементов, была решена Э. Постом. Задача оказалась намного сложнее в случае, когда функции определены на множестве, содержащем более двух элементов. Одну из первых работ в этом направлении опубликовал в 1939 г. Я. Слупецкий [83]. Он доказал, что каждая полная система функций должна содержать существенно многоместную функцию, принимающую все возможные значения. Такую функцию принято называть функцией Слупецкого. В 1954 г. С. В. Яблонский [92, 93] решил проблему полноты для случая, когда функции определены на множестве из трех элементов. Затем в течение 10 лет появилось много работ, в которых указывались достаточные условия полноты системы функций. Окончательно проблема полноты была решена И. Розенбергом [66] в 1965 году.
Стоит отметить, что упомянутую ранее теорему А. Н. Колмогорова [33] о том, что функция х + у вместе со всеми непрерывными одно местными функциями порождает все непрерывные функции, можно рассматривать в качестве аналога теоремы Слупецкого. Определенные топологические аналоги теоремы Колмогорова были позже найдены А. А. Мальцевым [39.
В теории универсальных алгебр важную роль играют классы функций, замкнутых относительно суперпозиций и содержащие все проекции, то есть функции вида е] (х\,..., х„) = Х\. Эти классы называются клопами. Две алгебры Ai = (М; F\) и А2 = (М; /) с одинаковыми носителями называются рационально эквивалентными, если множества их основных операций порождают один и тот же клон. Ввиду этого описание с точностью до рациональной эквивалентности различных универсальных алгебр, определенных на каком-то множестве, сводится к описанию всех клонов на этом множестве.
Клоны можно рассматривать как алгебры, например, как содержащие функцию e\{xi,X2) иредитеративные алгебры, введенные А. И. Мальцевым 41. Предитеративными алгебрами называются подалгебры ирсОи-теративной алгебры Поста О А = (Ол;, т, А, ) типа (1,1,1.2), в которой ОА - множество всех операций, определенных на множестве А. Определения операций , т, А, приведены в разделе 1.1. В совокупности они заменяют суперпозицию, которая не является алгебраической операцией. Поскольку элементами носителей иредитеративных алгебр являются функции, гомоморфизмы таких алгебр бывают двух видов: сохраняющие арность функций и не сохраняющие арности. Отвечающие им конгруэнции соответственно называются подарностными и енеарност-ными. Сохраняющий арность гомоморфизм клона, отображающий каждую проекцию е" одного клона в такую же проекцию е" другого клона называется клоповым.
Обозначим через Т(А) клон, порождаемый основными операциями алгебры А, а через Var А многообразие, порождаемое алгеброй А. Взаимосвязь между клоновыми изоморфизмами клонов Т(А) и Т(В) и строением многообразий Var А и Var В найдена А. И. Мальцевым [41]. Фактически им была доказана более сильная теорема, так как утверждение остается верным, если в формулировке и в доказательстве вместо изоморфизмов говорить о клоновых гомоморфизмах. Эта теорема осталась незамеченной и затем была заново открыта в работах ряда авторов (см., например, [71], иное доказательство приведено в [23]). Утверждение, о котором идет речь, можно сформулировать следующим образом.
Возьмем два непустых множества А и А . Пусть А = (А; {// }ге/) — некоторая алгебра, а С — какой-то клон функций, определенных на множестве А . Клоповый гомоморфизм кр : Т(А) —» С, отображающий Т( А) на С, существует тогда и только тогда, когда существует такое отображение р : Т(А) — С, что алгебра A = (Af; ((p (f )iei) принадлежит многообразию Var А (и С = Т(А )).
Отсюда легко заключить, что решетка подарностных конгруэнции клона изоморфна решетке всех подмногообразий многообразия, порождаемого алгеброй, основные операции которой порождают этот клон.
Тождество t t называется гипертождеством алгебры А, если t = t тождественно выполняется в А при любой замене символов one раций, входящих в термы t и , термальными функциями алгебры А соответствующей арности. Тождества в клонах называются клоповыми тождествами. Клоновые тождества алгебры Т(А) соответствуют гипертождествам алгебры А [84].
Следующие примеры [24] показывают, что тождества и гипертождества могут применяться в теории логических сетей. Изобразим логический элемент с двумя входами и одним выходом, реализующий конъюнкцию, следующим образом: & Тогда сложная составная переключающая схема & к і— к 1 может быть заменена этим элементом в любом месте сети, так как xh{xh{xhy)) = xSzy тождественно выполняется в двухэлементной булевой алгебре (0,1; &, N) (а потому и в любой булевой алгебре). Если g является произвольным переключающим элементом с двумя входами и одним выходом, реализующим какую-то бинарную булеву функцию д(х,у), то составную переключающую схему g g г- 1 g можно заменить элементом g какой бы не была функция д, поскольку F(x,F(x,F(x,y)))ttF(x,y) является гипертождеством алгебры (0,1;&, N). Гипертождества позволяют кратко формулировать признаки полноты системы функций. Например, система булевых функций S полна тогда и только тогда, когда равенство F(F(x, у), F(x,у))) « F(F(ar,х), F(y, у)) не является гипертождеством алгебры (0,1; S). 0.2 Обзор основных результатов Для любого множества функций F С. Ok через F n\ п Є N„ обозначим множество всех функций из F, зависящих ровно от п переменных, через F ) — множество всех функций из F, принимающих не более п значений, через F l — множество всех функций из F, принимающих ровно п значений. Отметим, что множество Л относительно операции является полугруппой. Порождаемую множеством подалгебру ал гебры VAI образованную всеми существенно одноместными функциями из Л, обозначим через .4 v. Полугруппа одноместных функций называется s раз транзитивной, если для любых попарно различных чисел ai,..., ая и любых чисел Ъ\,..., bs в ней найдется такая функция /, что /(а,) = 6/, г = М.
Итеративная алгебра называется клеточной (А. И. Мальцев 43), если она состоит из всех существенно одноместных функций и всех существенно многоместных функций, принимающих не более s значений. Клеточная алгебра имеет вид Р U V s и далее часто будет обозначаться через /s. Подалгебра "Р , образованная всеми функциями, принимающих не более s значений,называется ее основной клеткой.
А. И. Мальцевым [41] доказана структурная теорема, обобщающая известные теоремы Слупецкого [83] и С. В. Яблонского [93. Опуская особые случаи, ее можно сформулировать следующим образом.
Итеративная алгебра, пороэюдаемая функциями из s раз транзитивной полугруппы вместе с существенно .миоголіестной функцией f, принимающей га значений, содержит клетку V " и все функции, значения которых принадлежат множеству значений функции /, сели 2 т s+l.
В диссертации изучаются итеративные алгебры с s раз транзитивными основаниями, и обобщения таких алгебр. Однако в ряде случаев, например в четвертой главе, исследование выходит за указанные границы, поскольку некоторые утверждения носят общий характер.
Глава 1. Первые два параграфа носят вводный характер. В нем приводятся определения, соглашения и точные формулировки утверждений из работ других авторов, необходимые в дальнейшем. Многие из них уже приведены выше. Далее нам потребуется следующие определения.
Функции, представимые в виде /о(/і(#і)ф.. .Ф/М(х„)), где п 1, значения одноместных функций /i,...,/rt принадлежат множеству {0,1}, сложение ведется по модулю 2, а одноместная функция /() может принимать любые значения, называются квазилинейными. Итеративная алгебра, состоящая из квазилинейных функций, будет обозначаться через С. Ввиду ее свойств она также считается клеточной. Ее основной клеткой является алгебра С 2 .
Параграф 1.3 содержит ряд структурных теорем и следствия из них. Утверждение 1.3.1 дополняет приведенную выше теорему А. И. Мальцева следующим образом.
Если Л содержит два раза транзитивную полугруппу Q и не квази /01 линейную функцию, принимающую два значения, то Л Э Vk .
Если алгебра Л при к 3 содержит полугруппу Vk , а также существенно многоместную квазилинейную функцию, то Л Э С .
Известная теорема Саломаа [79] утверждает, что при к 4 множество функций Vk вместе с любой существенно многоместной функцией, принимающей к значений, порождает Vk- Систему порождающих какой итеративной алгебры мы получим, присоединив к функциям из Vk существенно многоместную функцию, принимающую менее к значений?
Теорема 1.3.9 утверждает, что если к 3 и добавляемая функция не квазилинейная, то при получится система порождающих некоторой клеточной подалгебры.
В четвертом параграфе доказывается, что все клетки и клеточные? алгебры имеют конечные базисы. Доказательство конструктивное в том смысле, что для каждого случая указывается базис. Находятся также минимальные длины базисов и порядки этих алгебр, то есть минимальное число переменных, от которых должна зависеть хотя бы одна функция, входящая в базис.
В параграфе 1.5 рассматриваются максимальные подалгебры клеток и клеточных алгебр. Теорема 1.5.1 показывает, что задача описания всех максимальных подалгебр алгебр , Ы2, • • •, Wk-i сводится к задаче описания всех максимальных подгрупп симметрической группы о (группы, образованной функциями из 7 l относительно операции ). Например, при 2 5 к — 1 максимальными подалгебрами алгебры Us являются лишь следующие алгебры: W.-1, vls]uvll){k-2]vu Z, v{ks]wpl1){k-1]vuM? (іeh), где AiJ — максимальная подгруппа группы Jk,. В качестве следствия из этой теоремы получаем описание подалгебр Фраттини алгебр С, Ыч, .... 14к-\- Так, подалгеброй Фраттини указанной выше алгебры Ыя является алгебра SUVJf UVk , где S — селекторная подалгебра алгебры Vk (подалгебра, порождаемая функцией еЦх, у) = х). Затем описывается два класса максимальных подалгебр клеток алгебры Vk, причем оказывается, что пересечение построенных максимальных подалгебр алгебры Vl при 2 s к пусто. Доказывается, что подалгеброй Фраттипи алгебры С является алгебра Vk .
Пример, построенный Ю. И. Яновым и А. А. Мучником [97, показывает, что уже у алгебры V имеется континуум подалгебр, а потому столько же подалгебр есть у каждой клеточной подалгебры, отличной от С. В разделе 1.6 доказывается, что мощность множества всех подалгебр алгебры С счётна. В алгебре С имеются бесконечнопорожденные подалгебры но нет подалгебр с бесконечным базисом.
Глава 2. Эта глава целиком посвящена описанию подклонов клопа Бурле над множеством из трех элементов. Этот клон состоит из существенно одноместных функций и функций вида
/о(/і(а?і)Є... $/„( „)),
где значения одноместных функций /i,...,/n принадлежат множеству {0,1}, сложение ведется по модулю 2, а функция /о может принимать любые значения. Клон Бурле является наименьшим среди клонов, ось держащих все одноместные функции и хотя бы одну существенно многоместную функцию. Хотя он содержит счетное число подклонов, образуемая этими подклонами решетка значительно сложнее решетки Поста. Здесь исследованы лишь подклоны, состоящие из функций, значения которых принадлежат либо множеству {0,1}, либо множеству {0,2}. Удалось нарисовать граф решетки подклонов клона Z$, образованного функциями со значениями в множестве {0,1}. Приводятся таблицы с указанием состава клонов, системы порождающих. Многочисленные рисунки помогают уяснить взаимное расположение клонов в решетке всех подклонов клона Бурле. Исследование выполнено совместно с Я. Демет-ровичем [14] - [19].
Глава 3. Конгруэнции на подалгебрах алгебр Поста впервые изучались А. И. Мальцевым в работе [41]. Им было отмечено, что, если исключить тривиальные случаи, на каждой подалгебре алгебры Vk имеется три конгруэнции: ко, совпадающая с отношением равенства, /q, совпадающая с тождественно истинным отношением, и ка, определяемая следующим образом: функции j\ и f-2 тогда и только тогда «„-конгруэнтны., когда они зависят от одинакового числа переменных. В дальнейшем эти три конгруэнции будут называться тривиальными.В той же работе найдено достаточное условие того, что все конгруэнции на какой-либо подалгебре алгебры Vk тривиальны; в частности, оказалось, что тривиальными являются все конгруэнции на самой алгебре Vk Упомянутое условие не выполняется ни для клеток алгебры Vki ни для клеточных подалгебр. В параграфе 3.1 доказывается, что при к 2 на подалгебрах Vk ,..., Vk имеются лишь тривиальные конгруэнции, а на С есть лишь одна нетривиальная конгруэнция, В разделе 3.2 показывается,что тривиальными являются также все конгруэнции на любой подалгебре Л алгебры Vk, удовлетворяющей условию Vk 2 Л Э S , где некоторая специальная подалгебра алгебры Vk- В параграфе 2.3 указывается достаточное условие, при котором решетка конгруэнции на подалгебре v, содержащей лишь существенно одноместные функции, легко строится, если известна решетка конгруэнции на полугруппе Q. Этому условию удовлетворяют основания всех клеточных подалгебр. Затем, используя описание решетки конгруэнции на полугруппе Vk , приведенное в [40], строятся решетки конгруэнции на подалгебрах , 1І2, • • • , Uk-\. Пусть D С A, D ф 0. Алгебру /Ср, образованную всеми функциями из VA, значения которых принадлежат D, назовём простой, или элементарной квазиклеткой над множеством D; множество D назовем определяющим для )CD- Квазиклеткой называется подалгебра алгебры VA, являющаяся объединением произвольного множества простых квазиклеток. Клетки являются частным случаем квазиклеток. Изучение свойств квазиклеток и их подалгебр проводится в параграфе 3.5. Оказывается, что эти свойства можно увязать с изоморфными вложениями алгебры VA В VB, описанными А. И. Мальцевым [41]. Ранее свойства простых квазиклеток конечного ранга исследовались Д. Лау [36]. Она нашла все конгруэнции на подалгебрах простых квазиклеток. Часть этих конгруэнции имеет весьма регулярное строение. Назовем их S-конгруэнциями.
Пусть а — взаимно однозначное отображение множества А в множество В, С — образ множества А, (3 — отображение множества В на С, оставляющее элементы множества С неподвижными. Каждой функции /(xi,... ,хп) из подалгебры А алгебры VA сопоставим функцию /а/з(2/1). • , Уп) из VB следующим образом: /a(a(zi),... , а(хп)) = а(/(хъ ... , хп)), /а/?(У1,... ,Уп) = /a(/%l),.-- ,/%п)). Отображения a : f — /a и 7 : / - fap являются изоморфизмами алгебры А в алгебры Vc и VB соответственно. Обозначим через С и Б образы алгебры А при этих изоморфизмах. Алгебра Б называется проективным расширением алгебры С.
Пусть D С А, В — подалгебра алгебры VD И К-D квазиклетка алгебры VA, имеющая определяющее множество D. Подалгебру алгебры К, , образованную такими функциями fa из VA, что / \ D Є В, назовём вполне ограниченным расширением алгебры В в VA- Будем писать А В, если А является вполне ограниченным расширением алгебры В.
Обозначим через И.(Л) объединение множеств значений всех функций, принадлежащих подалгебре А итеративной алгебры VA- Алгебру А Г А(А) назовём ядром алгебры А. Ядро алгебры А назовём отделимым, если оно не совпадает с А. Мощность множества А \ Л{А) назовём индексом алгебры А.
В параграфе 3.5 описан ряд свойств й -конгруэнций. Центральным результатом является следующая теорема.
Пусть подалгебра А алгебры VA является вполне ограниченным расширением алгебры В, S = {А{\г Є /} —совокупность попарно различных подмножеств множества А \ А(А), Ds = Ui iAi, HS — S-конгруэнция на А. Алгебра A/ HS изоморфна такой подалгебре С алгебры А, которая является проективным расширением алгебры С В. Если множество А конечно, то индекс алгебры С строго меньше индекса алгебры А. Если каж,дое множество АІ содержит лишь один элемент, то алгебра С имеет индекс \А \ {А{А) U Ds)\.
В разделе 3.6 рассматриваются итеративные алгебры произвольного ранга. А. И. Мальцев [41] разделил все автоморфизмы таких алгебр на внутренние и внешние. Он установил, что внутренними являются все автоморфизмы любой итеративной алгебры, содержащей все функции, принимающие некоторое фиксированное значение и, как только значение любой ее переменной равно и, и потому группа автоморфизмов такой алгебры вложима в группу о - В параграфе 3.6 доказывается, что внутренними являются все автоморфизмы итеративной алгебры, содержащей все константы, и потому ее группа автоморфизмов также вложима в о . Это в частности означает, что внутренними являются все автоморфизмы клеток и клеточных алгебр.
В параграфе 3.7 устанавливаются некоторые связи между квазиклетками и универсальными алгебрами, у которых клон, порождаемый основными операциями, получается пополнением квазиклетки всеми проекциями. Описываются многообразия, порождаемые такими алгебрами. Тем самым обобщаются результаты, полученные ранее Б. Венглоржем [8] и И. Розенбергом [69].
Глава 4. Тождества алгебр функций являются формулами языка второго порядка (гипертождествами). Естественным образом возникает следующий вопрос: верно ли, что клоны однозначно определяются множествами своих гипертождеств? Обсуждению этой проблемы посвящены три параграфа этой главы.
Если рассматривать клоны функций, определенных на множестве, содержащем более двух элементов, то ответ в общем случае будет отрицательным. Однако булевы клоны однозначно (с точностью до изоморфизмов) определяются множествами своих гипертождеств, так как справедлива следующая теорема.
Пусть С и С — два таких булевых клона, что С не изоморфен никакому подклону клона С. Тогда С моенсно отделить от С гиперто:нс тождествами.
В этом смысле булевы клоны можно разделить гипертождествами. Доказательство указанного выше утверждения приведено в разделе 4.3. Оно опубликовано в работе [23], написанной совместно с К. Денеке. Отметим, что в статье [24], написанной в соавторстве с К. Денеке и М. Решке, приведено конструктивное доказательство с указанием разделяющих гипертождеств.
В этих результатах, сформулированных на языке гипертождеств, отражается существенное различие между булевыми клонами и клонами функций, определенных на множестве более чем с двумя элементами.
В последнем параграфе исследуется следующая проблема: можно ли отделить квазиклетки от других подалгебр алгебры V A при помощи гипертождеств? Для А = 3 положительный ответ был найден совместно с Д. Швайгертом [50]. Точнее говоря, сформулированы условия, необходимые и достаточные для того, чтобы подалгебра алгебры Vz являлась квазиклеткой. Ниже указаны такие условия для одного из рассмотренных случаев. Пусть через Л обозначено функциональное тождество Л(Л(Л(Л(х, а;)), \(\(х, х), \(х, х))), А(А(А(у, у), А(у, у)), А(А(у, у), А(у, у)))) = = А(А(А(А( ,:г)),А(А(у,у),А(у,у))), А(А(А(х, х), Х(х,х)), А(А(у, у), А(у, у)))). Подалгебра Л V совпадает с квазиклеткой /С{од} U fC{o,2} з тогда и только тогда, когда одновременно выполняются следующие условия:
1)У/€Л(/№)2{1,2});
2) Л И= (7 Л = 7 7) V yr/V = P7V )/
3) Л л.
Глава 5. Пусть Пс- 4. = - l х • • х 4т —- множество всевозможных последовательностей (/lfci, . .. ,zn),..., (fm(xi,... ,хг,)), в которых /І Є Рдг Каждую такую последовательность можно рассматривать как функцию f{x\,...,xn), определенную на множестве А = А\ х ... х Ат. Очевидным образом на Y[c РАІ МОЖНО определить операции , т, Д, V, . Например, (С/)( ь • • •, хп) = ((С/ООп,..., хп),..., (C/m)(zi, - - •, а;„)). Алгебра 7-% Ат = (Пс- ;С Г» А, V, ) называется согласованным (с числом переменных у функций, принадлежащих носителям сомножителей) произведением алгебр VA{- В универсальной алгебре этому понятию соответствует определенное В. Наркевичем [12] неиндексированное произведение алгебр. Различные свойства согласованных произведений исследовались Б. А. Ромовым [73] - [77], В. А. Таймаиовым [86, С. С. Мар-чемковым [56, 57].
Пятая глава диссертации делится на два параграфа. Параграф 5.1 содержит теорему, обобщающую структурная теорему А. И. Мальцева [42 (с дополнениями, описанными в первой главе) на произведения итеративных алгебр. Она опубликована в статье [53], написанной совместно с Б. Г. Тугылбаевой. Результаты параграфа 5.2 опубликованы в [54].
Введение хіх
Пусть kj 3 при і = l,m, Si Є N, S{ 2, Л — подалгебра алгебры Vkx km, содержащая такую функцию f = (/і,... , fm), что // для любого і = 1,га является существенно многоместной функцией, принимающей либо si, либо Si + 1 значение, ТІ - множество всех функций из Pf.{, все .значения которых содержатся в множестве fi(Ekt). Пусть далее НІ — Sj. раз транзитивная подполугруппа полугруппы Р , если Sj. 4, либо полугруппы Р , есливі € {2,3} и /,; — не квазилинейная функция, и Hi = Pk , если функция fi € Р\. квазилинейная. Если Л содержит все функции из множества Н = Ні х ... х Нт, то Л принадлежат все функции из произведения В\ х ... х Вт, где ВІ молсет совпадать либо с ТІ, если fi принимает, S{ -+-1 значение и НІ содержит тождественную функцию е\(х) = х, либо с С 2\ если fi Є {2}, либо с Pk{ i}, если fi 2 .
В приведенной выше теореме существенную роль играют произведения Н\ х ... х Нт транзитивных полугрупп Щ. Поскольку существенные переменные в разных сомножителях могут иметь различные индексы, такие произведения следует считать существенно многоместными функциями. Такая точка зрения подтверждается например утверждением 5.2.3, доказываемым в параграфе 5.2. Существенно одноместными являются произведения одноместных функций, у которых индексы существенных переменных, если таковые имеются, совпадают. В связи с этим случай, когда известно, что алгебра содержит все такие произведения и еще какую-либо функцию, не совпадает с уже рассмотренным, и является интересным. Теорема 5.2.4 также является аналогом упоминавшейся выше структурной теоремы А. И. Мальцева, хотя требования, накладываемые
Введение XX на множества одноместных функций в сомножителях, приближают ее к теоремам Слупецкого и С. В. Яблонского.
Если подалгебра Л алгебры Vku...,km содержит все функции, принадлежащие Ыкх кт, и такую функцию / = (/і, •. •, /m) чт-о лл каждого і = 1,га функция fi Є Рк принимает Z{ 2 значений, и ее единственная существенная переменная имеет индекс, отличающийся от индексов существенных переменных всех остальных проекций функции /, то Л содержит все функции из произведения
Напомним, что подалгебра Слупецкого является единственной максимальной подалгеброй алгебры Vk, содержащей все функции из Vk . Она образована всеми существенно одноместными функциями из Vk и всеми существенно многоместными функциями, принимающими не более к — \ значений. Следуя С. С. Марченкову [57], присвоим это название максимальным подалгебрам алгебры 7\...fcm, содержащим все функции из Ык к . Последняя теорема позволяет описать все подалгебры Слупецкого в произведениях итеративных алгебр.
Алгебра S = 1Zi U ... U IZm, где Ki = Vkl х...х\, x%xVki+1 х...хРкт, i = l,m и % — подалгебра Слупецкого алгебры Vki, является единственной подалгеброй Слупецкого алгебры Vkl...km сли ki 3 для каждого і Є {l,...,m}.
Все вошедшие в диссертацию результаты опубликованы в [14] - [54]. Они докладывались на семинарах в институте математики СО РАН, Новосибирском и Московском государственных универ Введение xxi ситетах, а также па международных конференциях в России, Австрии, Венгрии, Германии, Китае, Югославии и Японии. Статьи [14] - [19 написаны в неразделимом соавторстве с Я. Деметровичем, работа [23 в неразделимом соавторстве с К. Деиеке, работа [24] - в неразделимом соавторстве с К. Денеке и М. Решке, статья [50] - в неразделимом соавторстве с Д. Швайгертом, статья [53] - в неразделимом соавторстве с Б. Г. Тугылбасвой.
Транзитивные полугруппы
Для любого множества функций F С Ok через F n\ п Є N,, обо значим множество всех функций из F, зависящих ровно от п переменных (п-тый слой множества F), через F — множество всех функций из F, принимающих не более п значений, через FW — множество всех функций из F, принимающих ровно п значений. Мы не рассматриваем функции, зависящие от 0 переменных, так что функция, принимающая только одно значение а, зависит от п О переменных. Отметим, что из-за наличия среди основных операций алгебры Vk операции V множество Р 1 не образует подалгебру алгебры Vk ни при каком п, однако относительно операции множество Р образует полугруппу. Глава 1. Клетки и клеточные алгебры 8 1.2.4. Пусть Л — подалгебра алгебры VA- Порождаемую множеством Л подалгебру алгебры VA, образованную всеми существенно одноместными функциями из Л, обозначим через Л 1 . 1.2.5. ной тройкой значений функции f(x\,... , хп)из Ok, если существуют такие числа ац,... , a\n, 22i,... , a2n, что для некоторого і 21-1, ац, a2i+i,..., a2n) = 2 Следующее утверждение получено путем объединения леммы Яблон-ского-Саломаа из [42] и утверждения из [78]. Оно играет важную роль в дальнейших рассуждениях. 1.2.6. 1) Каждая существенно многоместная функция / Є Ok, прини мающая более двух значений, обладает по меньшей мере одной суще ственной тройкой значений. 2) Каждая функция, обладающая существенной тройкой значений, существенно многоместна, и любое ее значение входит в подходящую существенную тройку значений. 3) Для любой существенно многоместной функции / Є Ok , принимающей s 2 значений, и любого т, 2 т s, существуют такие множества Si С Ек, г = 1,п, содержащие не более чем по т — 1 значений, что /(Si,... , Sn) содержит т элементов. Во многих случаях важную роль играет то обстоятельство, что рас сматриваемая итеративная алгебра содержит особую подполугруппу одноместных функций, называемую к раз транзитивной. 1.2.7. Подполугруппа Ті полугруппы V\. называется m раз транзитивной, если для любых попарно различных чисел a\,... ,ат из Ек и любых чисел &i,... , 6т из Ек вИ. найдется такая функция f, что f(ai) = 6г, і = 1,га. Часто нам придется ссылаться на следующую важную структурную теорему А. И. Мальцева из статьи [42]. 1.2.8.
Пусть некоторая подалгебра Л алгебры Vk, где k 3, удовлетворяет одному из следующих условий: 1) Л содерэюит некоторую s раз транзитивную подполугруппу полугруппы Vk\ s 4, и Л содержит функцию f, принимающую любое значение из множества V = {VQ, VI, ... , vs}, содержащего в себе хотя бы одну существенную тройку значений функции f; 2) Л содержит некоторую s раз транзитивную подполугруппу полугруппы Vl , s = 3, и А содерэюит функцию /, принимающую все значения из множества V = {г?о, i i, , vs}, содержащего в себе существенную тройку значений функции f; 3) Л содерэюит s раз транзитивную подполугруппу полугруппы Vk s = 2, и Л содерэюит функцию f, принимающую только три значения, принадлеоюащих множеству V = { сь ъ з} и образующих существенную тройку значений функции /. Тогда Л содерэюит все функции из Ok, все значения которых содержатся в множестве V, а также все функции из О) . 1.2.9. Подалгебра Л итеративной алгебры В называется максималь ной, если любая подалгебра С, удовлетворяющая включениям Л С С С В, совпадает либо с Л, либо с В. Из теоремы 1.2.8 следует, что множество всех одноместных функций из Ok вместе с любой существенно многоместной функцией, принимающей 5 2 значений, порождает алгебру Vk U Vk . Это в частности означает, что алгебра Vk U Vk , где 2 s к — 1, является максимальной подалгеброй алгебры Vk U Vk , и потому в решетке всех подалгебр алгебры Vk подалгебры образуют цепь, заканчивающуюся алгеброй Vk- Остается лишь неясным, существуют ли собственные подалгебры алгебры Vk , содержащие алгебру Vk и отличные от нее. Упомянутую выше цепь независимо от А. И. Мальцева обнаружил Г. А. Бурле [6]. Он также выяснил, что есть только одна подалгебра, находящаяся между алгебрами Vk и . Чтобы ее описать, нам требуется следующее определение. где п 1, значения одноместных функций /i,... , fn принадлежат множеству {0,1}, сложение ведется по модулю 2, а одноместная функция /о может принимать любые значения, называются квазилинейными.
Максимальные подалгебры
Обозначим через М(Л) множество всех максимальных подалгебр алгебры Л. Пусть {МІ і Є Ik} — множество всех максимальных подгрупп симметрической группы Uk 1.5.1. При к 4 множество M{US), 2 s к — 1, содержит лишь ДОКАЗАТЕЛЬСТВО. Пусть Л — одна из подалгебр , U2,.. . ,4-2 алгебры Pjt и к 4. Учитывая замечания, сделанные при доказательстве теоремы 1.4.3, разобьём множество М(Л) на две группы. 1. Подалгебры, содержащие целиком симметрическую группу о - Лег-ко заметить, что такие подалгебры содержат целиком полугруппу Vk и потому эта алгебра содержит лишь подалгебры если A = US, (2 s к — 1), подалгебры если A = 11%, и подалгебры 2. Подалгебры, не содержащие целиком группу т&. Такие подалгебры должны содержать в себе подалгебры Vk и 7 , если A = Us (2 s к — 1), подалгебры С и Vk , если А = 2, подалгебры С и Vj. если Д = С, поэтому они имеют вид, указанный в теореме. Из теоремы 1.3.9 следует, что из подалгебр, входящих в M{Uk-i) при к 3 группу 7fc целиком содержит лишь подалгебра Ык-2- Легко заметить, что все остальные подалгебры из M(Uk-i) имеют вид Vk UAif, і Є Ік. Из теоремы 1.3.9 также следует, что при к = 3 из подалгебр, входящих в M(Uk-i), группу 7& целиком содержит лишь подалгебра V ; остальные подалгебры из М(С) имеют вид С U A4f. П Теорема 1.5.1 показывает, что решение проблема полноты для клеточных подалгебр С, U2,... Mk-і сводится к описанию всех максимальных подгрупп группы а к Как указывалось ранее, функции вида называются проекциями. Множество всех проекций образует подалгебру алгебры Vk, называющуюся селекторной подалгеброй. Очевидно, любая функция из Е порождает всю подалгебру S. Теорема 1.5.1 позволяет выяснить, какие функции не входят ни в один базис алгебр С,ЬІ2і... ,Uk-i- Как известно, множество элементов, не вхо Глава 1. Клетки и клеточные алгебры 29 дящих ни в один базис алгебры Л, образует подалгебру алгебры Л, называемую подалгеброй Фраттини. Эта подалгебра совпадает с пересечением всех максимальных подалгебр алгебры Л (в случае, когда алгебра Л конечнопорождённая). рой Фраттини алгебры С, алгебра \JC UV является подал геброй Фраттини алгебры 1І2, алгебра S U V/f U является подалгеброй Фраттини алгебры Us (2 s к — I). При к 3 ал гебра Є U V\ U г к является подалгеброй Фраттини алгебры Ык-\-
При к = 3 подалгеброй Фраттини алгебры С является подалгебра 5u7 (D{2}V П Перейдём к описанию некоторых классов максимальных подалгебр клеток алгебры Vk- Пусть Обозначим через A4(L) множество всех тех функций из множества Ок, множество значений которых принадлежит L, если значения аргументов выбраны в L, а через ЛЛ{Ь) подалгебру, порождаемую всеми функциями из С njVfc(L) вместе с функцией са{х), где a . L. Как известно [43], алгебра Afk(L) является максимальной подалгеброй алгебры Vk- Такие подалгебры называются константно максимальными. Напомним, что 1.5.3. Алгебра WfcW(L) максимальна VI тогда и только тогда, когда k \L\ к — s (2 s к). Алгебра Л4(Ь) максимальна в С тогда и только тогда, когда \L\ = к — 1. Глава 1. Клетки и клеточные алгебры 30 ДОКАЗАТЕЛЬСТВО. Пусть Л = Vk{s) и В = Як{з](Ь) или Л = С{2} и В = М. (L), и некоторая функция / принадлежит Л, но не принадлежит В. Обозначим через С алгебру, порождаемую всеми функциями из В вместе с функцией /. Если Л = V{ks) и f{Ek) Ek\L при \L\ k — s, то алгебра С не содержит функций из множества Vk, все значения которых принадлежат множеству Ek\L, и потому С ф Vk . Аналогично устанавливается необходимость условия \L\ к — 1 в случае Условие f : В означает, что в множестве L существуют такие числа 2i,... , ап, что /(fli,... , an) = а и а ф L. Для любого CLI из L множеству вы принадлежит функция cai(x) = щ, следовательно алгебре С принадлежит функция ca(x) = f(cai(x),... , cQn(x)), а вместе с ней и все функции из V\ . Заметим, что для любых чисел а\,... , a,Q (аі ог) из множества L, Ь из множества Ек \ L и с из множества Ек в В найдутся такие одноместные функции t\t t2, что поэтому полугруппа С при \L\ = к — 1 будет два раза транзитивной, если для некоторых чисел Сі, С2, сз (с\ т сг) из множества L и d Є Ek\L найдётся такая функция р(х), что Рассмотрим три случая. I. и h(xi,..., xm) — произвольная функция, принадлежащая алгебре Vk Введём функцию остальных случаях. Очевидно, Є Л/ (L). Однако поэтому И. Э Р . Заметим, что при L k — s для любого s множества N С Ек в ЛҐ (Ь) найдётся такая существенно многоместная функция и, что u(Ek) = N. Кроне того, Л D Vk , значит Л — V 2. Пусть Докажем, что полугруппа С два раза транзитивна. Алгебре В принадлежит функция Функция р(х) = /(cd(rr),rc) принадлежит С и удовлетворяет равенствам 1.5. Так как С содержит два раза транзитивную подполугруппу &1\ Л/ (L) содержит не квазилинейные функции и Л/ (L) С L, то С = V\ . 3. Пусть Глава 1. Клетки и клеточные алгебры 32 и ХІ — существенная переменная функции /. Алгебра ЛЛ содержит те и только те функции из 2\ которые при изменении переменных на множестве L либо сохраняют постоянное значение, либо принимают два значения и оба эти значения принадлежат L, поэтому существуют такие числа
Другие подклоны клона Z0UZ2, порождаемые с помощью унарных функций из .
Большое количество клонов, описанных в предыдущем параграфе, объясняется определенной "нейтральностью"функций 2, Р2 с2 по отношению к функциям из ZQ\ функции (f2, f 2, C L не меняют значения при изменении переменной на множестве {0,1}. Оставшиеся одноместные функции из 2 этим свойством не обладают, и потому число новых клонов, получаемых с их участием, невелико. В дальнейших построениях без ссылок используется информация о подклоиах клона ZQ, содержащаяся в таблицах 2.4 и 2.7. Для удобства читателя приводим также таблицу 2.8, содержащую результаты суперпозиций одноместных функций. Пусть /С — клон, порождаемый функциями UQ И 72- Очевидно, /С "D С . Так как у?о 72 = Со, то /С содержит все функции UQ, то есть /С С S . Очевидно, клон /С содержит также функции 72 UQ. Других функций в нем нет. Клон /С обозначим через 1S4 . Клон 7W порождается функциями 1+UQ, 72- Содержит функции UQk+1, 1 + «о , а потому и Клон 7«5 порождается функциями р%, 72 и потому S D Сф. Так как о 72 = VOJ ТО 7 Э , отсюда 75 Э и потому 75 Э су,/,. Этот клон содержит функции порождается также следующими системами: Так как клоны содержат ,/, и не содержатся в S /,, то при добавлении 72 к базису любого из этих клонов получается ZQ U 72 = 2b U 2 Клон, содержащий функции 1 + ipo -+- 70, 72, содержит C p+s, то есть функции а вместе с ними и все функции и потому совпадает с ZQ U Z2. Тот же результат получим, взяв функции 1 + 7о + 7о, 72- Таким образом, семейство функций из клона ZQ, содержащее существенно многоместную функцию, после добавления 72 может породить лишь один из четырех указанных выше клонов.
Клон Stp порождается функциями ujj, Ф2. Так как ф2 ро = 72, т0 он СОДерЖИТ 7су, ТО ЄСТЬ фуНКЦИИ 14Q, 72 WQ И "02 Клон Ыу порождается функциями 1 + и%, ф2. Содержит сро, а вместе с ней 72 и все функции из "TYy,, то есть Очевидно, этот же клон порождается функциями 1 + UQ, ф2. Клон, порождаемый функциями 7о + 7о "02 содержит 00 + 70 — (7о + 7о) "02? следовательно /?о и 72 и потому совпадает с 1S(pip. Тот же результат получим, взяв функции ро + 7о "Фг или 4J, PQ, ф2, так как «S U -02- Содержит функции PQ, ф2 PQ (n 0). 5 , = 5 U -02- Содержит функции Так как a Sip$ — максимальный подклон клона Zo, то все оставшиеся клоны, имеющие вид /С U -02, где /С ew,, совпадают с ZQL) Z2. Из рассмотренных клонов вида /С не содержат 72 клоны Добавляя 72 к порождающим каждого из них, получим 7«S в первых двух случаях, и ZQ U Z2 в остальных. Очевидно, описывая клоны вида /С U #2» где /С Zo, содержащие существенно многоместные функции, достаточно рассмотреть клоны вида /Ci U $2, ГДЄ Клон 7/у, уже содержит #2, поэтому 7/р U $2 = Ыф. Новым является клон «S , содержащий функции
Клон 53{(уф содержит функции и потому совпадает с ZQ\J Z2. Займемся клонами вида /С U 2 где Клон Sy порождается базисом , 2- Содержит функции Клон Сф = Ьф U V 2 состоит из функций plk+1, фо РІк+1, Фо РІк+1-Клон Sip = Sip U Ф2 образован функциями р%, о Ро о Ро Клон 5 , = S U ф2 состоит из функций Клон 7 S U -02 содержит функцию ( 2 = фг 72 и потому совпадает с ZQ U Я2. Клоны ф, ф, !ф не содержат (. Добавление к любому из них этой функции дает ZQ U -. Все вновь полученные клоны указаны в таблице 2.9. Теперь мы рассмотрим возможность порождения новых клонов путем добавления к функциям из подклонов клона ZQ существенно многоместных функций из Z2. Начать естественно с более простого случая — с тех подклонов клона ZQ, которые содержат только существенно одноместные функции. Легко однако заметить, что мы будем получать лишь подклоны, изоморфные уже описанным. Действительно, пусть клон К порождается унарными функциями р\,- , Ps из ZQ и функцией р Є Z2. Рассмотрим функции, Ao-двойственные указанным. Функции рх,... ,р принадлежат Z2, рх принадлежит 2о, и совместно они порождают клон, Ло-двойственный клону /С. Все клоны такого типа уже найдены выше. Видим, что нам осталось описать все клоны /С, порождаемые объединением базисов клонов К,\ ZQ и 1С2 і%, ПРИ условии, что эти клоны содержат существенно многоместные функции. Комбинации базисов, очевидным образом не порождающие новые клоны, рассматриваться не будут. Пусть К,2 порождается либо функцией либо функцией в первом случае и во втором. В таблице 2.12 приведены возможные варианты базиса клона /С. Все построения при этом базируются на результатах суперпозиции Р 72» гДе / Є /Сі- Ввиду тривиальности мы их опустим. Вместо функций и\ й\ в базисы включены функции и2,й2, поскольку на результат такая замена не влияет.
Гомоморфизмы вполне ограниченных расширений итеративных алгебр
Бблыпая часть утверждений из этого параграфа справедлива для итеративных алгебр произвольного ранга, но некоторые верны только для итеративных алгебр конечного ранга. 3.5.1. Пусть D С A, D 0. Алгебру JCD, образованную всеми функциями из VAI значения которых принадлежат D, назовём простой, или элементарной квазиклеткой над множеством D; множество D назовем определяющим для JCD- Квазиклеткой называется подалгебра алгебры VA, являющаяся объединением произвольного множества простых квазиклеток. 3.5.2. Обозначим через А{А) объединение множеств значений всех функций, принадлежащих подалгебре А итеративной алгебры VA- Алгебру А Г А{А) назовём ядром алгебры А. Ядро алгебры А назовём отделимым, если оно не совпадает с А. Мощность множества А \ А(А) назовём индексом алгебры А. 3.5.3. Пусть D С А, В — подалгебра алгебры VD И KD квазиклетка алгебры VA, имеющая определяющее множество D. Подалгебру алгебры JCD, образованную такими функциями fi из VA, ЧТО /г- Г D Є В, назовём вполне ограниченным расширением алгебры В в VA- Будем писать А В, если А является вполне ограниченным расширением алгебры В. 3.5.4. Пусть А — подалгебра алгебры VA, имеющая отделимое ядро, и S = {А{ г Є /} — произвольная совокупность попарно различных подмножеств множества А \ А{А). Определим на А отношение эквивалентности Hs: Легко проверить, что cs — конгруэнция на А. Конгруэнции такого вида назовём S-конгруэнциями, а отвечающие им гомоморфизмы S-гомо-морфизмами. Отметим, что некоторые 5-конгруэнции могут оказаться тривиальными. В статье [36] Д. Лау доказала, что если А является подалгеброй итеративной алгебры Поста конечного ранга, А В и В содержит функцию е\(х) = х, то каждый гомоморфизм алгебры А является либо S-гомоморфизмом, либо композицией гомоморфизма алгебры А на алгебру В и гомоморфизма алгебры В. Ниже доказывается, что это справедливо для вполне ограниченных расширений любых подалгебр алгебры Vk и что класс вполне ограниченных расширений любой подалгебры алгебры VA замкнут относительно . -гомоморфизмов. ранга, А В и индекс алгебры
А равен I 0. Решётка S-конгруэнции на А изоморфна свободной дистрибутивной решётке с I порождающими. ДОКАЗАТЕЛЬСТВО. Пусть csx и — S-конгруэнции на Л, Будем писать S\ Ц .%, если Si С 52 и для каждого A2iG . в S\ найдётся такое A\j, что A\j С А%1. Из определения S-конгруэнции непосредственно следует, что если Si С і%, то xsi = s2 поэтому можно рассматривать только такие множества 5, которые вместе с АІ содержат все надмножества множества Аі] такие множества называются I-замкнутыми. Очевидно, что если S\ % S2 и 5г % S\, то xsl ф xs2i и что если &і и 2 являются /-замкнутыми, то из S\ С ,% следует HS1 С Х52, поэтому существует изоморфизм между решёткой б -конгруэнций на А и решёткой /-замкнутых множеств над Ek \ Л(Л). Последняя изоморфна свободной дистрибутивной решётке с I порождающими (Г. Биркгоф, [5]). В [41, 43] А. И. Мальцев описал два класса гомоморфизмов итеративных алгебр. гомоморфизмов 7г : Л — VBi, (г Є /), ш Каждой функции /(xi,... ,rcn) из Л сопоставим функцию р из VB, определённую следующим образом. Если gi,... ,gn произвольные элементы множества В и для любого і Є I справедливо то /7(#i,... ,gn) — g- Легко убедиться в том, что отображение 7 f — Р — гомоморфизм алгебры Л в VB- Поскольку 7 полностью определяется семейством 7г, то будем писать задано семейство гомоморфизмов 7г Л — VBH где і Є I, и Глава 3. Гомоморфизмы 148 — гомоморфизм алгебры А на подалгебру В алгебры VB- Если один из гомоморфизмов 7г является изоморфизмом, то алгебры Л и В изоморфны. ДОКАЗАТЕЛЬСТВО. ИЗ определения гомоморфизма 7 и условий леммы 3.5.7 непосредственно видно, что если функции / и g из А различны, то и функции р и 77 также различны, поэтому отображение 7 взаимно однозначное. 3.5.8. [41] Пусть а — взаимно однозначное отображение множества А в множество В, С — образ множества А, (3 — отображение множества В на С, оставляющее элементы множества С неподвижными. Каждой функции f(xiy... ,хп) из подалгебры А алгебры VA сопоставим функ цию /а/з (l/i,... ,Уп) из VB следующим образом:
