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

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

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

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


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

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


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


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


\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}


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


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


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


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


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

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




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


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


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


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


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


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


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


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

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


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

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




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


\begin{aligned}\mathit{Table~3.1}~&\\ \begin{array}{|c|c|c|} \hline +& 0& 1\\\hline 0& 0& 1\\\hline 1& 1& 1\\\hline \end{array}& \end{aligned} \qquad\qquad \begin{aligned}\mathit{Table~3.2}~&\\ \begin{array}{|c|c|c|} \hline \cdot & 0& 1\\\hline 0& 0& 0\\\hline 1& 0& 1\\\hline \end{array}& \end{aligned}

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


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




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


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


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


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


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




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


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


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


x\leqslant y\quad \Leftrightarrow\quad x+y=y.
(3.1)

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


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


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


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


x+z=x+(y+z)= (x+y)+z= y+z=z\,,

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


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


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


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


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




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


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


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


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


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


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




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


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


\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}

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


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

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

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"

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


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

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