Полукольца. Основные примеры

Определение 3.1. Полукольцо — это алгебра с двумя бинарными и двумя нульарными операциями

S = (S,+,⋅,0, 1),

такая, что для произвольных элементов а, b, с множества S выполняются следующие равенства, называемые аксиомами полукольца:

1. a + (b + c) = (a + b) +c;
2. a + b = b + a;
3. a + 0 = a;
4. a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c;
5. a ⋅ 1 = 1 ⋅a = a
6. a ⋅ (b + c) = a ⋅ b + a ⋅ c;
7. (b + c) ⋅ b ⋅ a + c ⋅ a;
8. a ⋅ 0 = 0 ⋅ a = 0.

Первую операцию + называют сложением полукольца, а вторую операцию - умножением полукольца S; элементы 0 и 1 называют соответственно нулем и единицей полукольца S.

Аксиомы полукольца называют также основными ждествами полукольца.

Таким образом, из определения следует, что операция сложения полукольца ассоциативна и коммутативна, а нуль полукольца является нейтральным элементом относительно операции сложения; операция умножения полукольца ассоциативна и единица полукольца является нейтральным элементом относительно операции умножения. Кроме этого имеет место свойство дистрибутивности (двусторонней) операции умножения относительно сложения полукольца. Аксиому 8 полукольца называют аннулирующим свойством нуля в полукольце.

Используя понятие моноида, определение 3.1 можно переформулировать так. Полукольцо S = (S, +, ⋅, 0, 1) — это алгебра с двумя бинарными и двумя нульарными операциями, такая, что:

1. алгебра (S, +, 0) является коммутативным моноидом (его называют аддитивным моноидом полукольца);
2. алгебра (S, ⋅, 1) является моноидом (его называют мультипликативным моноидом полукольца);
3. имеют место свойства (двусторонней) дистрибутивности операции сложения относительно операции умножения;
4. выполняется аннулирующее свойство нуля.

Сравнивая определение полукольца с определением 2.5 кольца, мы видим, что кольцо есть частный случай полукольца: если кольцо по сложению является абелевой группой, то полукольцо — лишь коммутативный моноид.

Выделим два вида полуколец: коммутативное полукольцо с коммутативной операцией умножения и тное полукольцо с идемпотентной операцией сложения.

Пример 3.1. Рассмотрим алгебру

R⁺ = (ℝ⁺ ∪{+∞}, min, +, +∞, 0),

где ℝ⁺ — множество неотрицательных действительных чисел, min — операция взятия наименьшего из двух данных чисел, + — операция сложения действительных чисел, +∞ — „плюс бесконечность" (в том же смысле, что и в математическом анализе), 0 — число „нуль".

Эта алгебра — полукольцо, носителем которого является полуось ℝ⁺ = {х: х ≥ 0}, пополненная элементом +∞ (множество всех неотрицательных действительных чисел вместе с плюс бесконечностью").

Необычность полукольца R⁺ состоит в том, что в качестве его умножения взято сложение действительных чисел, тогда как в качестве сложения выбрана операция взятия наименьшего из двух чисел. Согласно сигнатуре, элемент +∞ рассматривается как нуль полукольца. Действительно, min(x, +∞) = х для любого x ∈ ℝ⁺U {+∞}, т.е. элемент +∞ есть нейтральный элемент относительно операции min (операции сложения в полукольце). Элемент +∞ также обладает аннулирующим свойством относительно операции сложения чисел (операции умножения в полукольце): х + (+∞) = +∞. Следовательно, выполняются аксиомы 3 и 8 полукольца.

Остальные аксиомы полукольца также выполнены. Легко убедиться, что алгебра (ℝ⁺ U {+∞}, min, +∞) — коммутативный моноид и алгебра (ℝ⁺ U {+∞}, +, 0) — также коммутативный моноид. Проверим свойства дистрибутивности, которые в данном случае запишутся так:

a + min (b, c) = min (a + b, a + c).

Имеем

В то же время

Таким образом,

a + min(b, c) = min (a + b, a + c).

Заметим, что в рассматриваемом полукольце умножение + коммутативно, а сложение min идемпотентно. Следовательно, R⁺ — идемпотентное коммутативное полукольцо.

Пример 3.2. Рассмотрим алгебру B = ({0,1}, +, ⋅, 0, 1), в которой операции + и ⋅ заданы таблицами Кэли (табл. 3.1 и 3.2).

Таблица 3.1, Таблица 3.2

+ 0 1 0 0 1 1 1 1

⋅ 0 1 0 0 0 1 0 1

Проверка аксиом полукольца основана на этих таблицах и легко выполняется. Обратим внимание, что два элемента О и 1, из которых в данном случае состоит носитель полуколь- полукольца, одновременно являются соответственно нулем и единицей данного полукольца. Легко видеть, что рассматриваемое полу- полукольцо коммутативное и идемпотентное.

Интересно то, что операции полукольца В можно трактовать как логические связки „или" и „и", а элементы 0 и 1 — как „ложь" и „истина" соответственно.

Пример 3.3. Рассмотрим еще несколько различных алгебр, являющихся полукольцами. Выполнение аксиом полукольца для всех приведенных алгебр легко проверяется.

а. Алгебра N = (ℕ₀, +, ⋅, 0, 1) с носителем — множеством неотрицательных целых чисел и операциями сложения и умножения чисел есть коммутативное полукольцо. Оно не является идемпотентным.

б. Алгебра S_A = (2^A, ∪, ∩, ∅, А) с носителем — множеством всех подмножеств некоторого множества А и операциями объединения и пересечения есть полукольцо. Оно является идемпотентным и коммутативным.

в. Алгебра R_A = (2^АхА, ∪, ॰, ∅, id_A) с носителем — множеством всех бинарных отношений на множестве А — и операциями объединения и композиции отношений является полукольцом. Оно идемпотентное, но не коммутативное.

г. Алгебра S_[a,b] = ([а, b],max, min, а, b), носителем которой служит отрезок числовой прямой, с операциями взятия максимума и минимума из двух чисел есть идемпотентное и коммутативное полукольцо. #

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

На носителе идемпотентного полукольца S = (S, +, ⋅, 0, 1) может быть введено отношение порядка, которое, естественно, согласуется со свойствами операций полукольца: для произвольных x, у ∈ S положим х ≤ у тогда и только тогда, когда x + y = y, т.е. x ≤ y ↔ x + y = y.   (3.1)

Проверим, что таким образом действительно определено отношение порядка. Для этого нужно показать, что введенное бинарное отношение рефлексивно, антисимметрично и зитивно.

Поскольку для любого х в силу идемпотентности сложения имеет место равенство х + х = x, то, согласно (3.1), имеем х ≤ x, т.е. введенное отношение рефлексивно.

Соотношения х ≤ у и у ≤ х означают, что х + у = у и у + х = = х. Поскольку сложение коммутативно, то из этих равенств следует, что x = у. Значит, рассматриваемое отношение антисимметрично.

Соотношения х ≤ у и у ≤ z означают, что х + у = у и у + z = z.

Тогда x + z = x + (y +z) + z = y + z = z, откуда следует, что х ≤ z. Таким образом, введенное отношение транзитивно.

Итак, отношение ≤ на носителе произвольного идемпотентного полукольца есть отношение порядка. Будем называть его естественным порядком идемпотентного полукольца и говорить, что он задан в этом полукольце.

Мы установили очень важный факт: всякое идемпотентное полукольцо можно рассматривать как упорядоченное множество, причем отношение порядка определяется через сложение этого полукольца согласно C.1). Введенное отношение порядка можно интерпретировать так: „большее при сложении поглощает меньшее" (как, скажем, при объединении множества и некоторого его подмножества).

Поскольку для любого элемента х произвольного идемпотентного полукольца S = S, +, ⋅, 0, 1) имеет место 0 + х = x, то для любого х ∈ S выполняется неравенство 0 ≤ x, т.е. нуль идемпотентного полукольца есть наименьший элемент относительно естественного порядка идемпотентного полукольца.

Объясним, как интерпретируется естественный порядок идемпотентных полуколец, рассмотренных в приведенных выше примерах.

Пример 3.4. В полукольце В (см. пример 3.2) выполняется равенство 0 + 1 = 1 и, следовательно, 0≤1.

В полукольце R⁺ (см. пример 3.1) х ≤ у, если и только если min (x, y) = y.

Обозначим через ≤_ℝ естественный числовой порядок на множестве действительных чисел. Тогда для произвольных элементов x, у полукольца R⁺ соотношение х ≤ у означает, что х ≥_ℝу, т.е. число х не меньше числа у относительно естественного числового порядка. Таким образом, порядок в полукольце R⁺ — это двойственный порядок для отношения ≥_ℝ. В полукольце есть наименьший элемент относительно введенного порядка — элемент +∞, поскольку для любого элемента х имеем min(x, +∞) = х. Существует и наибольший элемент — единица полукольца, т.е. число 0. Не следует путать число 0 с нулем данного полукольца, а именно с элементом +∞.

В полукольце S_A (см. пример З.З.б) получаем в качестве отношения естественного порядка полукольца отношение включения С . Действительно, для любых двух множеств X, У ∈ 2^A из X U Y = Y вытекает X ⊆ Y и наоборот. Наименьшим элементом является нуль полукольца — 0 (пустое множество), а наибольшим — единица полукольца (множество А).

В полукольце R_A (см. пример З.З.в) отношение естественного порядка полукольца также совпадает с отношением - включения для бинарных отношений. В этом полукольце существуют наименьший элемент — пустое отношение 0 и наибольший элемент — универсальное отношение. Однако в отличие от полукольца S_A наибольший элемент не совпадает с единицей полукольца.

В полукольце S_[а,b] (см. пример З.З.г) имеем естественный числовой порядок, определенный на множестве действительных чисел отрезка [а, b]. Наименьшим элементом является число а (нуль полукольца), а наибольшим — число b (единица полукольца).

Теорема 3.1. Если А — конечное подмножество (носителя) идемпотентного полукольца, то sup Л относительно естественного порядка этого полукольца равен сумме всех элементов множества А.

◀Пусть А = {ai,..., an} и а = а₁ +... + аn. Для произвольного элемента a_i, i = 1,n , в силу коммутативности и идемпотентности сложения имеем

а_i + а = a_i + (а₁ +... + a_i+...+a_n) =

= а1 +... + a_i + a_i +... + a_n =

= а₁ +... + a_i +... + a_n = a,

т.е. a_i ≤ a, и поэтому а есть верхняя грань множества А. Покажем, что это точная верхняя грань множества. Возьмем произвольную верхнюю грань b множества А и рассмотрим сумму b + а. Так как для каждого i = 1,n имеет место a_i ≤ b, т.е. a_i + b = b, то b + а = b + (а₁ + а₂ +... + аа_n) = (b + а₁) + (а₂ + ... + а_n) = b + а₂ + ... + а_{n = ... = b}

Следовательно, а ≤ b и поэтому а — тонная верхняя грань множества А. ▶