Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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


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


[math]\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}[/math]


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


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


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


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


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

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




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


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


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


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


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


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


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


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

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


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

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




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


[math]\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}[/math]

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


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




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


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


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


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


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




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


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


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


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

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


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


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


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


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

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


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


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


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


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




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


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


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


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


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


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




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


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


[math]\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}[/math]

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


[math]\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}[/math]

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


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved