AR - алгебры подстановок и их применение

• Автор: Вышенский, Владимир Андреевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Киев
• Количество страниц: 103 c. : ил

Глава I. Алгебры антирефлексивных отношений (е#/£- алгебры)
§ I. Определение и простейшие свойства с#/2-алгебр •
§ 2. Подалгебры и фактор-алгебры
§ 3. Связь с алгебрами Краснера
Глава II. Соответствие Галуа между-алгебрами и группами подстановок
§ 4. Категория групповых действий и категория групп подстановок
§ 5. Соответствие Галуа между с#£-алгебрами и группами
подстановок на конечном множестве
§ 6. Нормальные объекты соответствия Галуа между (^^-алгебрами и группами подстановок. оУ^/2 -алгебры фактордействий
Глава III. Некоторые црименения
§ 7. Свойства групп подстановок на языкес^/?-алгебр . . . § 8. Действия симметрических групп на разбиениях. . . . . § 9. Орбитыс^/2-алгебры классической мономиальной группы и проблема классификации функций многозначной логики относительно группы переименований
§ 10. 0 каталогизации циклических р^-верпганных графов. • Литература

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

сивным, если оно состоит из размещений длины к над оА1
На множестве <ЛЬЯе£ (оМ) всевозможных антирефлексивных отношений различных арностей естественно вводятся операции объединения, пересечения, дополнения, проектирования по (последней) координате, перестановки координат (транспозиция последних двух) координат всех к -точек из отношения и их циклический сдвиг) и приписывание еще одной координаты с сохранением свойства антирефлексивности. Возникающую при этом алгебру мы называем полной оЛЯ -алгеброй над множеством оМ , а ее подалгебры -<ц#72-алгеб-рами над этим множеством.
Диссертационная работа состоит из трех глав, разбитых на 10 параграфов. В первой главе изучаются необходимые свойства оЛ Я -алгебр. В § I вводится понятие с#£*далгебры, проведено исследование на независимость системы операций из сигнатуры о#£-алгебр, изучены свойства минимальных отношений изс#£~алгебр и их системы порождающих. В частности, оказывается, что каждая оЛЯ -алгебра является моногенной. При рассмотрениисЛЯ-алгебр удобно рассматривать еще одну бинарную операцию над антирефлек-сивными отношениями - аналог их декартова произведения. В этом же параграфе изучаются свойства такой операции и устанавливается, что множество отношений замкнуто относительно операций оЛЯ-алгебры тогда и только тогда, когда оно замкнуто относительно этой операции и всех операцийоЛЯ -алгебры, кроме приписывания. Поэтому получаемые в результате такой замены алгебры мы также называем оЛЯ -алгебрами. В § 2 устанавливается, когда система разбиений полных антирефлексивных отношений оЛ1 , к =1,1ЛИ/ является системой минимальных отношений всех арностей для неко-

1.3 инвариантными относительно О- будут также минимальные отношения из VI меньших арностей.
Следовательно, произвольные отношения из 1Л также инвариантны относительно От , как. объединения минимальных. Таким образом, & <Л-иЖ VI . с другой стороны, если некоторая подстановка^ в ^ (Л/) сохраняет все отношения из VI »то она сохраняет также и минимальное И -арное отношение, содержащее У1-точку (1,2 П. ), то есть содержится в &
Теорема 5.2. Для соответствия Галуа^ ^ (<Л1) Еа-луа-замыканием любого множества подстановок 'Те ^ (Л1)является группа подстановок, порожденная множеством т, а Галуа-замыканием произвольного семейства отношений 1Л е^р(л/)тт ется -алгебра, порожденная этим семейством.
Доказательство. Согласно лемме 5.2 семейство отношений
^(Т)~^шуТявляется -алгеброй, а по лемме 5.6 сг(Зга/Т7)-
груша, определяемая минимальным У1 -арным отношением этой алгебры. Подстановки из Т , очевидно, содержатся в этой группе. Если бы они порождали меньшую группу, то в-алгебре
содержалось бы меньшее И -арное отношение - график этой группы, что невозможно. Таким образом, (СШ'Т) -группа, порожденная множеством Т •
По определению отображения $ имеем, что-^-(1Х - группа. Согласно лемме 5.2^(1Я) -алгебра, которая, очевидно, содерзкит все отношения из 1Л . Покажем теперь, что /Щ -алгебра ^(Ш) порождается семейством отношений /Щ . Пусть 7Х
порождает <Л~(1 -алгебру VI • Тогда Л-и-Ь 1Л — Л-ЫгЬ 1Л . Но ми по лемме 5.6 определяется минимальным -арным