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

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

Определение 3.1. Полукольцо — это алгебра с двумя бинарными и двумя нульарными операциями [cbm]\mathcal{S}=(S,+,\cdot,\bold{0},\bold{1})[/cbm] , такая, что для произвольных элементов [cbm]a,\,b,\,c[/cbm] множества [cbm]S[/cbm] выполняются следующие равенства, называемые аксиомами полукольца:

[cbm]\begin{array}{ll}\mathsf{\scriptstyle{1)}}\quad a+(b+c)=(a+b)+c; &\qquad \mathsf{\scriptstyle{5)}}\quad a\cdot \bold{1}= \bold{1}\cdot a=a;\\[2pt] \mathsf{\scriptstyle{2)}}\quad a+b=b+a; &\qquad \mathsf{\scriptstyle{6)}}\quad a\cdot (b+c)=a\cdot b+a\cdot c;\\[2pt] \mathsf{\scriptstyle{3)}}\quad a+\bold{0}=a; &\qquad \mathsf{\scriptstyle{7)}}\quad (b+c)\cdot a=b\cdot a+ c\cdot a;\\[2pt] \mathsf{\scriptstyle{4)}}\quad a\cdot (b\cdot c)=(a\cdot b)\cdot c; &\qquad \mathsf{\scriptstyle{8)}}\quad a\cdot \bold{0}= \bold{0}\cdot a=\bold{0}. \end{array}[/cbm]

Первую операцию [cbm]{}+[/cbm] называют сложением полукольца, а вторую операцию [cbm]\cdot[/cbm] - умножением полукольца [cbm]S[/cbm] ; элементы [cbm]\bold{0}[/cbm] и [cbm]\bold{1}[/cbm] называют соответственно нулем и единицей полукольца [cbm]S[/cbm] .

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

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

Используя понятие моноида, определение 3.1 можно переформулировать так. Полукольцо [cbm]\mathcal{S}= (S,+,\cdot,\bold{0},\bold{1})[/cbm] — это алгебра с двумя бинарными и двумя нульарными операциями, такая, что:

1) алгебра [cbm](S,+,\bold{0})[/cbm] является коммутативным моноидом (его называют аддитивным моноидом полукольца);
2) алгебра [cbm](S,\cdot,\bold{0})[/cbm] является моноидом (его называют мультипликативным моноидом полукольца);
3) имеют место свойства (двусторонней) дистрибутивности операции сложения относительно операции умножения;
4) выполняется аннулирующее свойство нуля.

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


Виды полуколец

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

Пример 3.1. Рассмотрим алгебру [cbm]\mathcal{R}^{+}= (\mathbb{R}^{+}\cup \{+\infty\}, \min,+,+\infty,0)[/cbm] , где [cbm]\mathbb{R}^{+}[/cbm] — множество неотрицательных действительных чисел, [cbm]\min[/cbm] — операция взятия наименьшего из двух данных чисел, [cbm]{}+[/cbm] — операция сложения действительных чисел, [cbm]+\infty[/cbm] — "плюс бесконечность" (в том же смысле, что и в математическом анализе), 0 — число "нуль".

Эта алгебра — полукольцо, носителем которого является полуось [cbm]\mathbb{R}^{+}= \{x\colon\, x\geqslant 0\}[/cbm] , пополненная элементом [cbm]+\infty[/cbm] (множество всех неотрицательных действительных чисел вместе с "плюс бесконечностью").

Необычность полукольца [cbm]\mathcal{R}^{+}[/cbm] состоит в том, что в качестве его умножения взято сложение действительных чисел, тогда как в качестве сложения выбрана операция взятия наименьшего из двух чисел. Согласно сигнатуре, элемент [cbm]+\infty[/cbm] рассматривается как нуль полукольца. Действительно, [cbm]\min(x,+\infty)=x[/cbm] для любого [cbm]x\in \mathbb{R}^{+}\cup \{+\infty\}[/cbm] , т.е. элемент [cbm]+\infty[/cbm] есть нейтральный элемент относительно операции min (операции сложения в полукольце). Элемент [cbm]+\infty[/cbm] также обладает аннулирующим свойством относительно операции сложения чисел (операции умножения в полукольце): [cbm]x+(+\infty)=+\infty[/cbm] . Следовательно, выполняются аксиомы 3 и 8 полукольца.

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

Легко убедиться, что алгебра [cbm](\mathbb{R}^{+}\cup \{+\infty\}, \min,+\infty)[/cbm] — коммутативный моноид и алгебра [cbm](\mathbb{R}^{+}\cup \{+\infty\},+,0)[/cbm] — также коммутативный моноид. Проверим свойства дистрибутивности, которые в данном случае запишутся так:

[cbm]a+\min(b,c)= \min(a+b, a+c).[/cbm]

Имеем [cbm]a+\min(b,c)= \begin{cases}a+b,& b \leqslant c;\\ a+c,& b>c.\end{cases}[/cbm] В то же время [cbm]\min(a+b,a+c)= \begin{cases}a+b,& b \leqslant c;\\ a+c,& b>c.\end{cases}[/cbm] . Таким образом,

[cbm]a+\min(b,c)=\min(a+b,a+c).[/cbm]

Заметим, что в рассматриваемом полукольце умножение [cbm]{}+[/cbm] коммутативно, а сложение [cbm]\min[/cbm] идемпотентно. Следовательно, [cbm]\mathcal{R}^{+}[/cbm] — идемпотентное коммутативное полукольцо.


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

[cbm]\begin{array}{|c|c|c|} \multicolumn{3}{r}{\mathit{Table~3.1}} \\\hline +& 0& 1\\\hline 0& 0& 1\\\hline 1& 1& 1\\\hline \end{array} \qquad\qquad \begin{array}{|c|c|c|} \multicolumn{3}{r}{\mathit{Table~3.2}} \\\hline \cdot & 0& 1\\\hline 0& 0& 0\\\hline 1& 0& 1\\\hline \end{array}[/cbm]

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

Интересно то, что операции полукольца [cbm]\mathcal{B}[/cbm] можно трактовать как логические связки "или" и "и", а элементы 0 и 1 — как "ложь" и "истина" соответственно.


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

а. Алгебра [cbm]\mathcal{N}= (\mathbb{N}_0,+,\cdot,0,1)[/cbm] с носителем — множеством неотрицательных целых чисел и операциями сложения и умножения чисел есть коммутативное полукольцо. Оно не является идемпотентным.

б. Алгебра [cbm]\mathcal{S}_A=(2^A,\cup,\cap,\varnothing,A)[/cbm] с носителем — множеством всех подмножеств некоторого множества [cbm]A[/cbm] и операциями объединения и пересечения есть полукольцо. Оно является идемпотентным и коммутативным.

в. Алгебра [cbm]\mathcal{R}_{A}=(2^{A\times A},\cup,\circ,\varnothing,\operatorname{id}A)[/cbm] с носителем — множеством всех бинарных отношений на множестве [cbm]A[/cbm] — и операциями объединения и композиции отношений является полукольцом. Оно идемпотентное, но не коммутативное.

г. Алгебра [cbm]\mathcal{S}_{[a,b]}=([a,b],\max,\min,a,b)[/cbm] , носителем которой служит отрезок числовой прямой, с операциями взятия максимума и минимума из двух чисел есть идемпотентное и коммутативное полукольцо.


Отношение порядка идемпотентного полукольца

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

На носителе идемпотентного полукольца [cbm]\mathcal{S}=(S,+,\cdot,\bold{0}, \bold{1})[/cbm] может быть введено отношение порядка, которое, естественно, согласуется со свойствами операций полукольца: для произвольных [cbm]x,y\in S[/cbm] положим [cbm]x\leqslant y[/cbm] тогда и только тогда, когда [cbm]x+y=y[/cbm] , т.е.

[cbm]x\leqslant y\quad \Leftrightarrow\quad x+y=y.[/cbm]
(3.1)

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

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

Соотношения [cbm]x\leqslant y[/cbm] и [cbm]y\leqslant x[/cbm] означают, что [cbm]x+y=y[/cbm] и [cbm]y+x=x[/cbm] . Поскольку сложение коммутативно, то из этих равенств следует, что [cbm]x+y[/cbm] . Значит, рассматриваемое отношение антисимметрично.

Соотношения [cbm]x\leqslant y[/cbm] и [cbm]y\leqslant z[/cbm] означают, что [cbm]x+y=y[/cbm] и [cbm]y+z=z[/cbm] . Тогда

[cbm]x+z=x+(y+z)= (x+y)+z= y+z=z\,,[/cbm]

откуда следует, что [cbm]x\leqslant z[/cbm] . Таким образом, введенное отношение транзитивно.

Итак, отношение [cbm]\leqslant[/cbm] на носителе произвольного идемпотент-ного полукольца есть отношение порядка. Будем называть его естественным порядком идемпотентного полукольца и говорить, что он задан в этом полукольце.

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

Поскольку для любого элемента х произвольного идемпотентного полукольца [cbm]\mathcal{S}= (S,+,\cdot, \bold{0}, \bold{1})[/cbm] имеет место [cbm]\bold{0}+x=x[/cbm] , то для любого [cbm]x\in S[/cbm] выполняется неравенство [cbm]\bold{0}\leqslant x[/cbm] , т.е. нуль идемпотентного полукольца есть наименьший элемент относительно естественного порядка идемпотентного полукольца.

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


Пример 3.4. В полукольце [cbm]\mathcal{B}[/cbm] (см. пример 3.2) выполняется равенство [cbm]0+1=1[/cbm] и, следовательно, [cbm]0\leqslant1[/cbm] .

В полукольце [cbm]\mathbb{R}^{+}[/cbm] (см. пример 3.1) [cbm]x\leqslant y[/cbm] , если и только если [cbm]\min(x,y)=y[/cbm] .

Обозначим через [cbm]\leqslant_{\mathbb{R}}[/cbm] естественный числовой порядок на множестве действительных чисел. Тогда для произвольных элементов [cbm]x,y[/cbm] полукольца [cbm]\mathcal{R}^{+}[/cbm] соотношение [cbm]x\leqslant y[/cbm] означает, что [cbm]x \geqslant_{\mathbb{R}}y[/cbm] , т.е. число [cbm]x[/cbm] не меньше числа [cbm]y[/cbm] относительно естественного числового порядка. Таким образом, порядок в полукольце [cbm]\mathbb{R}^{+}[/cbm] — это двойственный порядок для отношения [cbm]\leqslant_{\mathbb{R}}[/cbm] . В полукольце есть наименьший элемент относительно введенного порядка — элемент [cbm]+\infty[/cbm] , поскольку для любого элемента [cbm]x[/cbm] имеем [cbm]\min(x,+\infty)=x[/cbm] . Существует и наибольший элемент — единица полукольца, т.е. число 0. Не следует путать число 0 с нулем данного полукольца, а именно с элементом [cbm]+\infty[/cbm] .

В полукольце [cbm]\mathcal{S}_A[/cbm] (см. пример 3.3,б) получаем в качестве отношения естественного порядка полукольца отношение включения [cbm]\subseteq[/cbm] . Действительно, для любых двух множеств [cbm]X,Y\in 2^{A}[/cbm] из [cbm]X\cup Y=Y[/cbm] вытекает [cbm]X\subseteq Y[/cbm] и наоборот. Наименьшим элементом является нуль полукольца — [cbm]\varnothing[/cbm] (пустое множество), а наибольшим — единица полукольца (множество [cbm]A[/cbm] ).

В полукольце [cbm]\mathcal{R}_A[/cbm] (см. пример 3.3,.в) отношение естественного порядка полукольца также совпадает с отношением включения для бинарных отношений. В этом полукольце существуют наименьший элемент — пустое отношение [cbm]\varnothing[/cbm] и наибольший элемент — универсальное отношение. Однако в отличие от полукольца [cbm]\mathcal{S}_A[/cbm] наибольший элемент не совпадает с единицей полукольца.

В полукольце [cbm]\mathcal{S}_{[a,b]}[/cbm] (см. пример 3.3,г) имеем естественный числовой порядок, определенный на множестве действительных чисел отрезка [cbm][a;b][/cbm] . Наименьшим элементом является число [cbm]a[/cbm] (нуль полукольца), а наибольшим — число [cbm]b[/cbm] (единица полукольца).


Теорема 3.1. Если [cbm]A[/cbm] — конечное подмножество (носителя) идемпотентного полукольца, то [cbm]\sup{A}[/cbm] относительно естественного порядка этого полукольца равен сумме всех элементов множества [cbm]A[/cbm] .

Пусть [cbm]A=\{a_1,\ldots,a_n\}[/cbm] и [cbm]a=a_1+\ldots+a_n[/cbm] . Для произвольного элемента [cbm]a_i,~ i=\overline{1,n}[/cbm] , в силу коммутативности и идемпотентности сложения имеем

[cbm]\begin{aligned}a_i+a&= a_i+(a_1+\ldots+a_i+\ldots+a_n)=\\[2pt] &=a_1+ \ldots+ a_i+ a_i+ \ldots+ a_n=\\[2pt] &= a_1+\ldots+a_i+\ldots+a_n, \end{aligned}[/cbm]

то есть [cbm]a_i\leqslant a[/cbm] , и поэтому [cbm]a[/cbm] есть верхняя грань множества [cbm]A[/cbm] . Покажем, что это точная верхняя грань множества. Возьмем произвольную верхнюю грань [cbm]b[/cbm] множества [cbm]A[/cbm] и рассмотрим сумму [cbm]b+a[/cbm] . Так как для каждого [cbm]i=\overline{1,n}[/cbm] имеет место [cbm]a_i\leqslant b[/cbm] , то есть [cbm]a_i+b=b[/cbm] , то

[cbm]\begin{aligned} b+a&= b+(a_1+a_2+\ldots+a_n)= (b+a_1)+(a_2+\ldots+a_n)=\\[2pt]
&=b+ a_2+\ldots+a_n=b.\end{aligned}[/cbm]

Следовательно, [cbm]a\leqslant b[/cbm] поэтому [cbm]a[/cbm] — точная верхняя грань множества [cbm]A[/cbm] .

Источник

Поделитесь с другими:

Если материал понравился Вам и оказался для Вас полезным, поделитесь им со своими друзьями!

Читать по теме:

Интересные статьи: