Полукольца: определение, аксиомы, примеры
Полукольцо является одной из важнейших алгебр в современной дискретной математике. Эта глава посвящена рассмотрению полуколец и булевых алгебр. Изучаемые здесь методы, прежде всего метод решения систем линейных уравнений в полукольцах, имеют первостепенное значение для теории графов, булевых функций и теории формальных языков.
Определение 3.1. Полукольцо — это алгебра с двумя бинарными и двумя нульарными операциями , такая, что для произвольных элементов множества выполняются следующие равенства, называемые аксиомами полукольца:
Первую операцию называют сложением полукольца, а вторую операцию - умножением полукольца ; элементы и называют соответственно нулем и единицей полукольца .
Аксиомы полукольца называют также основными тождествами полукольца.
Таким образом, из определения следует, что операция сложения полукольца ассоциативна и коммутативна, а нуль полукольца является нейтральным элементом относительно операции сложения; операция умножения полукольца ассоциативна и единица полукольца является нейтральным элементом относительно операции умножения. Кроме этого имеет место свойство дистрибутивности (двусторонней) операции умножения относительно сложения полукольца. Аксиому 8 полукольца называют аннулирующим свойством нуля в полукольце.
Используя понятие моноида, определение 3.1 можно переформулировать так. Полукольцо — это алгебра с двумя бинарными и двумя нульарными операциями, такая, что:
1) алгебра является коммутативным моноидом (его называют аддитивным моноидом полукольца); 2) алгебра является моноидом (его называют мультипликативным моноидом полукольца); 3) имеют место свойства (двусторонней) дистрибутивности операции сложения относительно операции умножения; 4) выполняется аннулирующее свойство нуля.
Сравнивая определение полукольца с определением 2.5 кольца, мы видим, что кольцо есть частный случай полукольца: если кольцо по сложению является абелевой группой, то полукольцо — лишь коммутативный моноид.
Виды полуколец
Выделим два вида полуколец: коммутативное полукольцо с коммутативной операцией умножения и идемпотентное полукольцо с идемпотентной операцией сложения.
Пример 3.1. Рассмотрим алгебру , где — множество неотрицательных действительных чисел, — операция взятия наименьшего из двух данных чисел, — операция сложения действительных чисел, — "плюс бесконечность" (в том же смысле, что и в математическом анализе), 0 — число "нуль".
Эта алгебра — полукольцо, носителем которого является полуось , пополненная элементом (множество всех неотрицательных действительных чисел вместе с "плюс бесконечностью").
Необычность полукольца состоит в том, что в качестве его умножения взято сложение действительных чисел, тогда как в качестве сложения выбрана операция взятия наименьшего из двух чисел. Согласно сигнатуре, элемент рассматривается как нуль полукольца. Действительно, для любого , т.е. элемент есть нейтральный элемент относительно операции min (операции сложения в полукольце). Элемент также обладает аннулирующим свойством относительно операции сложения чисел (операции умножения в полукольце): . Следовательно, выполняются аксиомы 3 и 8 полукольца.
Остальные аксиомы полукольца также выполнены.
Легко убедиться, что алгебра — коммутативный моноид и алгебра — также коммутативный моноид. Проверим свойства дистрибутивности, которые в данном случае запишутся так:
Имеем В то же время . Таким образом,
Заметим, что в рассматриваемом полукольце умножение коммутативно, а сложение идемпотентно. Следовательно, — идемпотентное коммутативное полукольцо.
Пример 3.2. Рассмотрим алгебру , в которой операции и заданы таблицами Кэли (табл. 3.1 и 3.2).
Проверка аксиом полукольца основана на этих таблицах и легко выполняется. Обратим внимание, что два элемента 0 и 1, из которых в данном случае состоит носитель полукольца, одновременно являются соответственно нулем и единицей данного полукольца. Легко видеть, что рассматриваемое полукольцо коммутативное и идемпотентное.
Интересно то, что операции полукольца можно трактовать как логические связки "или" и "и", а элементы 0 и 1 — как "ложь" и "истина" соответственно.
Пример 3.3. Рассмотрим еще несколько различных алгебр, являющихся полукольцами. Выполнение аксиом полукольца для всех приведенных алгебр легко проверяется.
а. Алгебра с носителем — множеством неотрицательных целых чисел и операциями сложения и умножения чисел есть коммутативное полукольцо. Оно не является идемпотентным.
б. Алгебра с носителем — множеством всех подмножеств некоторого множества и операциями объединения и пересечения есть полукольцо. Оно является идемпотентным и коммутативным.
в. Алгебра с носителем — множеством всех бинарных отношений на множестве — и операциями объединения и композиции отношений является полукольцом. Оно идемпотентное, но не коммутативное.
г. Алгебра , носителем которой служит отрезок числовой прямой, с операциями взятия максимума и минимума из двух чисел есть идемпотентное и коммутативное полукольцо.
Отношение порядка идемпотентного полукольца
В дальнейшем нас будут интересовать только идемпотентные полукольца, поскольку именно на их основе разрабатываются алгебраические методы анализа ориентированных графов и конечных автоматов.
На носителе идемпотентного полукольца может быть введено отношение порядка, которое, естественно, согласуется со свойствами операций полукольца: для произвольных положим тогда и только тогда, когда , т.е.
(3.1)
Проверим, что таким образом действительно определено отношение порядка. Для этого нужно показать, что введенное бинарное отношение рефлексивно, антисимметрично и транзитивно.
Поскольку для любого в силу идемпотентности сложения имеет место равенство , то, согласно (3.1), имеем , т.е. введенное отношение рефлексивно.
Соотношения и означают, что и . Поскольку сложение коммутативно, то из этих равенств следует, что . Значит, рассматриваемое отношение антисимметрично.
Соотношения и означают, что и . Тогда
откуда следует, что . Таким образом, введенное отношение транзитивно.
Итак, отношение на носителе произвольного идемпотент-ного полукольца есть отношение порядка. Будем называть его естественным порядком идемпотентного полукольца и говорить, что он задан в этом полукольце.
Мы установили очень важный факт: всякое идемпотентное полукольцо можно рассматривать как упорядоченное множество, причем отношение порядка определяется через сложение этого полукольца согласно (3.1). Введенное отношение порядка можно интерпретировать так: "большее при сложении поглощает меньшее" (как, скажем, при объединении множества и некоторого его подмножества).
Поскольку для любого элемента х произвольного идемпотентного полукольца имеет место , то для любого выполняется неравенство , т.е. нуль идемпотентного полукольца есть наименьший элемент относительно естественного порядка идемпотентного полукольца.
Объясним, как интерпретируется естественный порядок идемпотентных полуколец, рассмотренных в приведенных выше примерах.
Пример 3.4. В полукольце (см. пример 3.2) выполняется равенство и, следовательно, .
В полукольце (см. пример 3.1) , если и только если .
Обозначим через естественный числовой порядок на множестве действительных чисел. Тогда для произвольных элементов полукольца соотношение означает, что , т.е. число не меньше числа относительно естественного числового порядка. Таким образом, порядок в полукольце — это двойственный порядок для отношения . В полукольце есть наименьший элемент относительно введенного порядка — элемент , поскольку для любого элемента имеем . Существует и наибольший элемент — единица полукольца, т.е. число 0. Не следует путать число 0 с нулем данного полукольца, а именно с элементом .
В полукольце (см. пример 3.3,б) получаем в качестве отношения естественного порядка полукольца отношение включения . Действительно, для любых двух множеств из вытекает и наоборот. Наименьшим элементом является нуль полукольца — (пустое множество), а наибольшим — единица полукольца (множество ).
В полукольце (см. пример 3.3,.в) отношение естественного порядка полукольца также совпадает с отношением включения для бинарных отношений. В этом полукольце существуют наименьший элемент — пустое отношение и наибольший элемент — универсальное отношение. Однако в отличие от полукольца наибольший элемент не совпадает с единицей полукольца.
В полукольце (см. пример 3.3,г) имеем естественный числовой порядок, определенный на множестве действительных чисел отрезка . Наименьшим элементом является число (нуль полукольца), а наибольшим — число (единица полукольца).
Теорема 3.1. Если — конечное подмножество (носителя) идемпотентного полукольца, то относительно естественного порядка этого полукольца равен сумме всех элементов множества .
Пусть и . Для произвольного элемента , в силу коммутативности и идемпотентности сложения имеем
то есть , и поэтому есть верхняя грань множества . Покажем, что это точная верхняя грань множества. Возьмем произвольную верхнюю грань множества и рассмотрим сумму . Так как для каждого имеет место , то есть , то
Следовательно, поэтому — точная верхняя грань множества .
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|