§ 6. Замкнутые полукольца

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

Определение. Замкнутым полукольцом называет­ся множество S с двумя бинарными операциями и такими, что

а) ассоциативна;

б) существует единичный элемент по отношению к , который будем обозначать символом 0;

в) ассоциативна;

г) существует единичный элемент по отношению к , который будем обозначать символом 1;

д) для всех x ∊ S

х 0 = 0 = 0 х;

е) коммутативна:

x y = y x для всех х, у ∊ S;

ж) идемпотентна:

x x = x для всех x ∊ S;

з) дистрибутивна относительно :

х (у z) = (х у) (х z) для всех x, y, z ∊ S,

(x y) * z = (x z) (y z) для всех x, y, z ∊ S,

и) сумма счетного числа элементов из S существует и единственна, т. е. не зависит от порядка суммирования;

к) дистрибутивна относительно бесконечных счетных сумм, т. е.

Эта достаточно странная структура часто использует­ся в алгоритмах замыкания для графов (гл. 7 и 8). Что­бы проиллюстрировать результаты, которые могут быть получены в замкнутых полукольцах, сравним системы (Z₂, +, *) и (Z₂, ∧, ∨). где операции определены табл. 5.9:

Т аблица 5.9

Рассмотрим определение операции замыкания. Резуль­тат а* применения этой операции к элементу а записы­ваем в виде

а* =

а⁰ = 1, а¹ = а, а² = а * а и а¹ = а^i-1 * a

(в (Z₂, ∧, ∨) сложением является ∨, а умножением ∧). В замкнутом полукольце (Z₂, ∧, ∨) такое определение имеет смысл и допустимо. В частности,

1* = 1⁰∨1¹∨1²∨...=1∨1∨1∨...=1

(в силу аксиом ж) и и)). Однако если мы попытаемся те же самые вычисления произвести в поле (Z₂, *, +), то получим

Э ту сумму можно вычислить следующим способом:

и ли же

т. е. значение суммы не определено. Следовательно, по­нятие такого рода замыкания не имеет смысла, если его применять к полю Z₂ (которое запрещает аксиомы ж) и и) полукольца).

Упражнение 5.6. Проверить, что ({ E}, ∩, ∪) является замкнутым полукольцом.

Глава 6. Матрицы

Наше изложение теории конечных матриц (множества матриц) является более общим, чем принятое в большин­стве книг, в которых матрицы обычно определяют как линейные преобразования на векторных пространствах, используя знакомство с координатной геометрией. Хотя иногда мы будем возвращаться (§ 3) к этой интерпрета­ции, в основном будем придерживаться точки зрения, что матрицы являются реализациями абстрактных алгебраи­ческих структур в вычислительных целях. Тогда алгебра абстрактных структур определяет способы, как надо ком­бинировать матрицы.

Сначала мы определим (§ 1) матричное представление бинарных отношений над конечными множествами. Затем последует более общее рассмотрение требуемых свойств абстрактной системы для того, чтобы матричная реализа­ция была разумной. А в завершение, используя резуль­таты предыдущих исследований, будет рассмотрен важ­ный случай векторного пространства над R.