Тема данной диссертации относится к теории замкнутых классов функций к-значной логики (также называемой "теорией клонов” и "теорией итеративных алгебр”). Эта теория берет свое начало в работах Э.Поста, которые были написаны в 20-40-х годах XX века. К настоящему времени она имеет собственную богатую проблематику и содержит большое число глубоких результатов. В Уральском государственном университете работы по изучению решетки замкнутых классов ведутся с начала 90-х годов. Обзору полученных за это время результатов посвящены работы [3,9].
Итеративной алгеброй на конечном множестве X называется совокупность всех конечноместных функций на X, замкнутая относительно суперпозиции функций, перестановок, отождествлений переменных функции и добавлений фиктивных переменных (см. [2]). Если итеративная алгебра содержит проекции, т.е. функции вида ей(®1, • ■ ■, = х,-,
то она называется клоном. Для алгебр, не удовлетворяющих этому условию, мы будем использовать термин "алгебра без проекций”. Так как пересечение любого числа итеративных алгебр является итеративной алгеброй, то все они образуют полную решетку, которую мы будем обозначать через £%. То же самое можно сказать и про множество всех клонов, подрешетку которых мы будем обозначать через £х. К сожалению, множество всех алгебр без проекций не образует решетку. Частично упорядоченное множество всех алгебр без проекций мы будем обозначать через £'х>.
Поскольку операция суперпозиции является ассоциативной, на итеративную алгебру удобно смотреть как на полугруппу, наделенную дополнительными унарными операциями. Суперпозиция функций в дальнейшем обозначается через ♦.
В теории полугрупп в числе главных вводятся такие важные понятия, как отношения Грина и идеалы (см. [1]). Эти понятия полезны тем, что они являются мощными инструментами при решении различных полугрупповых проблем. Поэтому можно попытаться перенести эти понятия и связанные с ними утверждения в теорию итеративных алгебр для того, чтобы использовать полученные результаты при решении проблем из этой области. На этом пути возникают некоторые трудности. Наличие дополнительных операций не позволяет просто применять
полугрупповые определения к итеративным алгебрам, эти определения требуется соответствующим образом модернизировать. Также эти понятия целесообразно использовать лишь в том случае, если они имеют для итеративных алгебр ясный смысл и являются достаточно содержа-тельными.
Введем основное определение.
Определение 4 Подмножество I С А мы называем идеалом итеративной алгебры А, если
1) 1 — подалгебра в А;
2) I — идеал полугруппы {А; *}.
Оказывается, что собственные идеалы итеративной алгебры являются алгебрами без проекций. В связи с этим рассмотрению таких алгебр в дальнейшем отведено особое место.
Также представляется интересным изучение итеративных алгебр, множество идеалов которых удовлетворяет некоторым естественно возникающим ограничениям. Среди таких алгебр наибольшее внимание уделяется идеально простым алгебрам.
Определение 5 Итеративная алгебра А называется идеально простой, если она не содержит нетривиальных идеалов, т.е. из того, что 1 — идеал в А следует 7 = 0 или I = А.
Исследования, результаты которых представлены в данной диссертации, в основном направлены на изучение понятия идеала итеративной алгебры и свойств простых алгебр.
В работе используются методы, конструкции и результаты теории итеративных алгебр и теории полугрупп.
В диссертации получены следующие теоретические результаты:
1) установлена связь между идеалами итеративных алгебр и алгебрами пар отношений определенного вида;
2) получено описание решеток идеалов некоторых известных классов итеративных алгебр;
3) доказано, что любая итеративная алгебра из некоторого класса является максимальной итеративной алгеброй без проекций;
4) установлена связь максимальных идеально простых итеративных алгебр с группами перестановок;
5) получено полное описание максимальных идеально простых итеративных алгебр функций к-значной логики при к< 4.
Все перечисленные результаты являются новыми.
Диссертационная работа носит теоретический характер. Полученные результаты могут использоваться в теории итеративных алгебр и в универсальной алгебре, а также при чтении специальных курсов по алгебре и дискретной математики.
Основные результаты диссертации были представлены на Международной конференции по математической логике (Новосибирск, 1994 г.), Международной алгебраической конференции памяти Д.К.Фаддеева (Санкт-Петербург, 1997 г.), Международной математической конференции ’’Упорядоченные множества” (Варшава, 1999 г.), а также на семинарах Московского государственного университета и Новосибирского государственного университета, семинарах "Алгебраические системы” и "Дискретная математика” Уральского государственного университета. Они опубликованы в работах [4, 5, 6, 7, 8, 9]. Из совместной обзорной работы [9] в текст данной диссертации включены только результаты автора.
Диссертация состоит из двух глав, каждая из которых разбита на 4 параграфа. Основные результаты сформулированы в виде теорем 1-10. Общий объем диссертации составляет 81 страницу. Библиография содержит 39 наименований. Используется сквозная нумерация утверждений.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
