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

Введение.

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

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

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

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

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

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

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

§ 6. Нормальные объекты соответствия Галуа между <£#£-ал-гебрами и группами подстановок, -алгебры фактор-действий.

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

§ 7, Свойства групп подстановок на языкес^?-алгебр

§ 8. Действия симметрических групп на разбиениях,

§ 9. Орбиты^ £-алгебры классической мономиальной группы и проблема классификации функций многозначной логики относительно группы переименований.

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

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

В настоящей работе строится новое полное соответствие Галуа для груш подстановок. Объектами Галуа- двойственными группам подстановок при таком соответствии, являются так называемые оДЯ-алгебры (алгебр! антирефлексивных отношений). Отношение арности ^ над множеством оЛ1 , к мы называем антирефлексивным, если оно состоит из размещений даны к над сМ . На множестве (оМ) всевозможных антирефлексивных отношений различных арностей естественно вводятся операции объединения, пересечения, дополнения, проектирования по (последней) координате, перестановки координат (транспозиция последних двух) координат всех А -точек из отношения и их циклический сдвиг) и приписывание еще одной координаты с сохранением свойства антирефлексивности. Возникающую при этом алгебру мы называем полной -алгеброй над множеством оМ , а ее подалгебры -<^/2-алгеб-рами над этим множеством.

Диссертационная работа состоит из трех глав, разбитых на 10 параграфов. В первой главе изучаются необходимые свойства е4 £ -алгебр. В § I вводится понятиес#£~адгебры, проведено исследование на независимость системы операций из сигнатуры алгебр, изучены свойства минимальных отношений изс#£^алгебр и их системы порождающих. В частности, оказывается, что каждая

-алгебра является моногенной. При рассмотрении оА- &-алгебр удобно рассматривать еще одну бинарную операцию над антирефлексивными отношениями - аналог их декартова произведения. В этом же параграфе изучаются свойства також операции и устанавливается, что множество отношений замкнуто относительно операций с алгебры тогда и только тогда, когда оно замкнуто относительно этой операции и всех операций£ -алгебры, кроме приписывания. Поэтому получаемые в результате такой замены алгебры мы также называем -алгебрами. В § 2 устанавливается, когда система разбиений полных антирефлексивных отношений является системой минимальных отношений всех арностей для некоторой afiR- -алгебры, и вводится понятие фактор-алгебры алгебры над множеством gA¿ по некоторому отношению эквивалентности Hae/l¿. В третьем параграфе описываются конструкции, позволяющие осуществлять переход отс#£-алгебр к алгебрам Красне-ра и наоборот. В частности, для любого множества<¿M решетка алгебр Краснера над ним изоморфна решетке подалгебр полной алгебры Краснера.

Во второй главе изучается соответствие Галуа мевду ojhfcl-алгебрами над конечным множеством и группами подстановок на нем. § 4 носит вспомогательный характер. В нем излагаются необходимые сведения о категории групповых действий и категории групп подстановок. В § 5 строится соответствие Балуа между группами подстановок и с#£-палгебрами. Для любого набора отношений VI oJhR.et (е/и)обозначим символом oJfué VL группу всех подстановок множества oJM , сохраняющих каждое отношение из VL , а для любого множества TaSloflí) подстановок - символом ЗгигТ совокупность всех отношений из , инвариантных относительно Т . Пара отображений í > fy » определяемых равенствами

U)=JhdVL , 1Л c¡ (Т) = ¿Ino-T , Г<=5М) задает соответствие Галуа между упорядоченными по включению бу-леанами множеств и S (oJLLJ (теорема 5.1). Галуа-замкнутыми объектами этого соответствия являются с одной стороны -алгебры отношений надоAl и, с другой, группы подстановок на нем, причем ограничение этого соответствия нао#£-ал гебры и группы подстановок является полным соответствием Галуа (теоремы 5.3 и 5*4).

Б § 6 исследуются нормальные объекты построенного полного соответствия Галуа, то есть такие пары cdbR, -алгебр /VL (Vl^-'Vf0), для которых aJbi-b V3 < dVoi Vt . Их характеризация дается в терминах А -орбит cJbfi-алгебр /Vt . А именно, оАЯ-алгебра U над множеством dl1 будет нормальной в-алгебре над тем же множеством тогда и только тогда, когда для произвольного k^ k^Uiil, совокупность h -орбит алгебры "У/3 является разбиением оJIL в области импримитивности группы подстановок . В заключение параграфа устанавливается связь между фактор-алгебрами -алгебры по отношению эквивалентности и группами подстановок, оцределяемыми действиями группы автоморфизмов этой алгебры на фактор-множествах.

В третьей главе рассмотрены некоторые применения -алгебр . В § 7 описываются свойства -алгебр, отвечающие основным свойствам групп подстановок: транзитивности, полурегулярности, сильной А. -кратно-транзитивности, ^ -однородности та А -замкнутости. В § 8 изучается строение двух конкретных е#/£-ал-гебр, соответствующих действиям симметрической группы S (dll) на множествах упорядоченных разбиений oJli на части фиксированных мощностей и неупорядоченных разбиений оМ на части одинаковой мощности. В силу результатов ш.1 этио#/2 -алгебры характер! -зуются наборами своих ^ -орбит. В § 9 описывается строение орбит классической мономиальной группы, т.е.группы мономиальных матриц, ненулевые элементы которых являются корнями фиксированной степени из I, при ее действии на множестве векторов, координаты которых являются корнями из I. Эта группа подстановок, как легко видеть, подобна экспоненцированию циклической группы, действующей регулярно, и симметрической группы,соответствущей степени. Учитывая его, описание ^ -орбит классической моно -миальной группы сводится к описанию Ь. -орбит симметрической группы, действующей на упорядоченных разбиениях, В этом же параграфе показано, как задача описания к -орбит может быть применена при решении задачи классификации функций многозначной логики относительно группы переименований переменных, которая является индуцированием классической мономиальной группы.

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

1. Калужнин Л.А., Клин M.X. 0 некоторых макс шальных подгруппах симметрических и знакопеременных групп. Мат.сб., 1972, 87, » I, с.91 - 121.

2. Жепкт L.}cJHonk , Ou final Все ûlaeLvab, P-I, dknxi&'tdam — London ; h/crthfi -Holland puMl. aomp

3. Букур И#, Деляну А. Введение в теораю категорий и функторов: М., "Мир", 1972, 257 с.

4. Айгнер М. Комбинаторная теория. М. "Шр", 1982, 556 с.

5. Калужнин Л.А., Клин М.Х. О некоторых числовых инвариантах групп подстановок. Латвийский математический ежегодник, Рига, 1976, 18, с.81 ~ 99.

6. Перечислительные задачи комбинаторного анализа, об.перево-дов под ред.Г.П.Гаврилова. М.: "Мир", 1979, 362 с.

7. Харрари Ф., Палмер Э. Перечисление графов. М.; "Мир", 1977, 324 с.

8. Калужн1н Л.А., Сущансъкий В.1. Про нестандартн1 в1нцев1 до-бутки груп. В1сник КЦУ, сер.матем.та мех., 1983, 25 ,с.82-91.

9. Калужнин Л.А., Клин М.Х., Сущанский В.И. Операция экспонен-цирования групп подстановок. I. Изв.вузов. Сер.мат.,1979, 207, В 8, с.26 - 33.

10. Поваров Г.Н. 0 групповой инвариантности булевых функций. -в кн.: Применение логики в науке и технике. М.: Изд-во АН СССР, 1960,-с.263 341.

11. Сущанский В.И., Устименко-Бакумовский В.А. Характеризация тшов булевых функщй. В кн.: Вычисления в алгебре, теории чисел и комбинаторике. Киев: ИК АН УССР, 1980,с.47-59.1УЧ9 /\/*5, -О.З^-ЗЗЗ

12. Клин М.Х. О числе графов, для которых данная группа является группой автоморфизмов. Кибернетика, 1970, 6, с.131

13. Вышенский В.А. Нормальные объекты соответствия Галуа для групп подстановок. В кн.ХУЛ Всесоюзная алгебраическая конференция. Минск: ИМ АН БССР, 1983, с.49.

14. Вышенский В.А., Действия симметрических групп на разбиениях. В кн.;с4&-алгеб1ы групп подстановок, Препринт ИМ АН УССР, 84.3, с.45 53.

15. Вышенский В.А., Сущанский В.И. Соответствие Галуа между-алгебрами и группами подстановок на конечном множестве. В кн.; -алгебры групп подстановок. Препринт ИМ АН УССР, Л 84.3, с.3-44.