AR - алгебры подстановок и их применение Вышенский, Владимир Андреевич

Содержание к диссертации

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

Глава I» Алгебры антирефлексивных отношений (е#- ал
гебры).

I. Определение и простейшие свойствас#-алгебр . . . .

2. Подалгебры и фактор-алгебры* . .

3. Связь с алгебрами Краснера ......

Глава П. Соответствие Галуа междуoftfl-^алгебрами и груп
пами подстановок. . .

4. Категория групповых действий и категория групп под
становок.

5. Соответствие Галуа между с#-алгебрами и группами

подстановок на конечном множестве ..... ..

6. Нормальные объекты соответствия Галуа между с#~ал-гебрами и группами подстановок. ?J\-& -алгебры фактор-действий. ........................

Глава Ш. Некоторые применения

7. Свойства групп подстановок на языкес^с?-алгебр . . .
8. Действия симметрических групп на разбиениях.
9. Орбитые^¹/?-алгебры классической мономиальной группы
и проблема классификации функций многозначной логики от
носительно группы переименований.

10. 0 каталогизации циклических р^-вершинных графов.
Литература.

Введение к работе

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

кольца групп подстановок [і] , их V -кольца [2J ,/?.Х-іалгебрьі [з] , алгебры Краснера [4] и некоторые другие* Связь между указанными объектами и группами подстановок носит характер соот -ветствия Галуа. В случае алгебр Краснера это соответствие будет полным, для других же из указанных алгебраических образований оно не полно. Каждое соответствие типа Галуа для групп подстановок удобно использовать при решении определенного круга задач, Поэтому естественной является задача построения новых соответствий Галуа для групп подстановок, особенно таких, что являются полными. Отмеченное выше полное соответствие Галуа между группами подстановок на некотором множестве и алгебрами Краснера над ним имеет тот недостаток, что все алгебры Краснера - бесконечные объекты, то есть при таком соответствии конечным объектам - группам подстановок на конечном множестве - отвечают бесконечные объекты - алгебры Краснера над ним. Это существенно усложняет использование алгебр Краснера при исследовании групп подстановок.

В настоящей работе строится новое полное соответствие Галуа для групп подстановок. Объектами Галуа- двойственными группам подстановок при таком соответствии, являются так называемые оДЯ-алгебры (алгебрі антирефлексивных отношений). Отношение арности k над множеством оМ , L ^=Iмы называем антирефлек-

сивным, если оно состоит из размещений длины k над оД^ * На множестве всевозможных антирефлексивных отношений различных арностей естественно вводятся операции объединения, пересечения, дополнения, проектирования по (последней) координате, перестановки координат (транспозиция последних двух) координат всех Я -точек из отношения и их циклический сдвиг) и приписывание еще одной координаты с сохранением свойства антирефлексивности. Возншсащую при этом алгебру мы называем полной

ъДЯ-алгеброй над множеством оМ , а ее подалгебры -<^/2-алгеб-рами над этим множеством.

Диссертационная работа состоит из трех глав, разбитых на 10 параграфов. В первой главе изучаются необходимые свойства

е# -алгебр. В I вводится понятиес#-алгебры, проведено исследование на независимость системы операций из сигнатуры о#/2-алгебр, изучены свойства минимальных отношений изс#^алгебр и их системы порождающих. В частности, оказывается, что каждая qAR, -алгебра является моногенной. При рассмотрении оА- & -алгебр удобно рассматривать еще одну бинарную операцию над антирефлексивными отношениями - аналог их декартова произведения. В этом же параграфе изучаются свойства також операции и устанавливается, что множество отношений замкнуто относительно операцийс#/2-алгебры тогда и только тогда, когда оно замкнуто относительно этой операции и всех операцийс#R. -алгебры, кроме приписывания. Поэтому получаемые в результате такой замены алгебры мы также называем ofl-R, -алгебрами. В 2 устанавливается, когда система разбиений полных антирефлексивных отношений оАІ , &= і,,..„,/oiU/

является системой минимальных отношений всех арностей для неко-

торой aJfR- -алгебры, и вводится понятие фактор-алгебры с# -алгебры над множеством q/U- по некоторому отношению эквивалентности нас/И. В третьем параграфе описываются конструкции, позволяющие осуществлять переход отс#-алгебр к алгебрам Краснера и наоборот. В частности, для любого множества<М решетка алгебр Краснера над ним изоморфна решетке подалгебр полной алгебры Краснера.

Во второй главе изучается соответствие Галуа между о#/2-
алгебрами над конечным множеством и группами подстановок на нем.
4 носит вспомогательный характер. В нем излагаются необходи
мые сведения о категории групповых действий и категории групп
подстановок. В 5 строится соответствие Галуа между группами
подстановок и с#-алтебраміи Для любого набора отношений
У1^о&&е[(рМ)обозпачшА символом tzfkli VL группу всех под
становок множества oJVi , сохраняющих каждое отношение из иЬ ,
а для любого множества7^c^S(g/^)подстановок - символом ЗгигТ
совокупность всех отношений из , инвариантных отно-

сительно Т . Пара отображений $ , a , определяемых равенствами

задает соответствие Галуа между упорядоченными по включению бу-
леанами множеств (теорема 5.1). Галуа-

замкнутыми объектами этого соответствия являются с одной стороннее -алгебры отношений над оЛ/ и, с другой, группы подстановок на нем, причем ограничение этого соответствия нас>#-ал -

гебры и группы подстановок является полным соответствием Галуа (теоремы 5.3 и 5*4).

Б 6 исследуются нормальные объекты построенного полного соответствия Галуа, то есть такие пары cd/г -алгебр

для которых . Их характеризация

дается в терминах К -орбит ofrR,-алгебр ^/Ц1 ,\Р А именно,

c^-R-алгебра ^/\]І над множеством d\l будет нормальной -ал-

гебре 'УР над тем же множеством тогда и только тогда, когда для произвольного к_у 1 k^kJlil, совокупность к -орбит алгебры "V/⁰ является разбиением оУЦ в области импримитивности группы подстановок (oA-uhVl^dli ) В заключение параграфа устанавливается связь между фактор-алгебрами <#& -алгебры по отношению эквивалентности и группами подстановок, определяемыми действиями группы автоморфизмов этой алгебры на фактор-множествах.

В третьей главе рассмотрены некоторые применения -алгебр. В 7 описываются свойства *$&-алгебр, отвечающие основным свойствам групп подстановок: транзитивности, полурегулярности, сильной ті -кратно-транзитивности, я -однородности и п. - замкнутости. В 8 изучается строение двух конкретных е#/-ал-гебр, соответствующих действиям симметрической группы S (efli) на множествах упорядоченных разбиений оЛІ на части фиксированных мощностей и неупорядоченных разбиений оМ на части одинаковой мощности. В силу результатов гл.1 этис# -алгебры характери -зуются наборами своих « -орбит. В 9 описывается строение -орбит классической мономиальнои группы, т.е.группы мономиальных матриц, ненулевые элементы которых являются корнями фиксированной степени из I, при ее действии на множестве векторов, коор-

динаты которых являются корнями из I. Эта группа подстановок, как легко видеть, подобна экспоненцированию циклической группы, действующей регулярно, и симметрической группы,соответствующей степени. Учитывая его, описание я -орбит классической моно -миальной группы сводится к описанию к, -орбит симметрической группы, действующей на упорядоченных разбиениях. В этом же параграфе показано, как задача описания Я -орбит может быть применена при решении задачи классификации функций глногозначной логики относительно группы переименований переменных, которая является индуцированием классической мономиальной группы.

В последнем параграфе описываются алгоритм счета и результаты вычислительного эксперимента, проведенного нами совместно с М.Х.КПИНОМ и Н.И.Чередниченко, по перечислению всех неизоморфных циклических р -вершинных графов при р ^ 5 ипг^5, Случай Р = 5 иш=3 ранее не рассматривался. Анализ результатов позволил выдвинуть общую гипотезу, которая впоследствии подтвердилась.