XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

Поскольку для любого элемента х произвольного идемпотентного полукольца о = (Я, +,, О, 1) имеет место О+ х = х, то для любого х Е Я выполняется неравенство О < х, т.е. нуль идемпотентного полукольца есть наименьший элемент относительно естественного порядка идемпотентного полукольца. Объясним, как интерпретируется естественный порядок идемпотентных полуколец, рассмотренных в приведенных выше примерах.

Пример 3.4. В полукольце 6 (см. пример 3.2) выполняется равенство 0+1 = 1 и, следовательно, 0 < 1. В полукольце Я,+ (см. пример 3.1) х < у, если и только если шш(х, у) =у. Обозначим через ((и естественный числовой порядок на множестве действительных чисел. Тогда для произвольных элементов х, у полукольца К+ соотношение х < у означает, что х >и у, т.е. число х не меньше числа у относительно естественного числового порядка.

Таким образом, порядок в полукольце Я+ — зто двойственный порядок для отношения <и. В полукольце есть наименьший элемент относительно введенного порядка — элемент +со, поскольку для любого элемента х имеем ппп(х,+оо) = х. Существует и наибольший элеменш— единица полукольца, т.е. число О. Не следует путать число 0 с нулем данного полукольца, а именно с элементом +со. 3.1.

Полукольца. Оеиовиые примеры В полукольце 8л (см. пример 3.3.б) получаем в качестве отношения естественного порядка полукольца ошношемие включения С . Действительно, для любых двух множеств Х, У е 2л из Х О У = У вытекает Х С У и наоборот. Наименьшим элементом является нуль полукольца — И (пустое множество), а наибольшим — единица полукольца (множество А). В полукольце Кя (см. пример 3.3.в) отношение естественного порядка полукольца также совпадает с отношением включения для бинарных отношений. В этом полукольце существуют наименьший элемент — пустое отношение Я и наибольший элемент — универсальное отношение.

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

Если А — конечное подмножество (носителя) идемпотентного полукольца, то вирА относительно естественного порядка этого полукольца равен сумме всех элементов множества А. 1 Пусть А = [а~, ...,а„) и а =а~+...+оп. Для произвольного элемента а;, 1 = 1, и, в силу коммутативности и идемпотентности сложения имеем а; + а = а; + (а~ +... + а; +... + а„) = =а~+...+а;+а,+... +ап = =а~+...+а;+...+оп=а, т.е. цл < а, и поэтому а есть верхняя грань множества А. Покажем, что это точная верхняя грань ынохсесшеа.

Возьмем произвольную верхнюю грань 6 множества А и рассмотрим 182 3. ПОЛУКОЛЬЦА И БУЛЕВЫ АЛГЕБРЫ сумму Ь+ а. Так как для каждого 1 = 1, и имеет место а; ( 6, т.е. а; + Ь = Ь, то Ь+а= 6+(от+аз+...+а„) = = (6+ат)+(аз+... +а„) = 6+аз+...+а„= ... =Ь. Следовательно, а < Ь и поэтому а — точная верхняя грань множества А. ~ь 3.2. Замкнутые полукольца При изучении колец большое внимание было уделено полям. Связано зто прежде всего с тем, что в полях разработана техника решения систем линейных уравнений. Оказывается, можно выделить специальный класс идемпотпентпных полуколец, в которых также удается находить решения систем уравнений, рассматриваемых в качестве аналогов систем линейных алгебраических уравнений (ПЦ.

Определение 3.2, Полукольцо о = (о, +,, О, 1) называют эамкнутпььм, если: 1) оно идемпотентно; 2) любая последовательность элементов множества Я имеет тпочную верхнюю грань относительно естпестпвенного порядка < этого идемпотпентпного полукольца; 3) операция умножения полукольца 8 сохраняет тпочнме верхние грани последоватпельностпеа т.е.

для любого а Е Я и любой последовательности Х = (х„)„ги элементов множества Я авпрХ = впраХ, (впрХ)а = впр(Ха). Замечание 3.1. Условие 3 определения 3.2 можно сформулировать иначе и говорить о сохранении точной верхней грани любого не более чем счетного подмножества множества Я. Однако в дальнейшем такие подмножества часто будут строиттся как множества элементов некоторых последовательностей. 183 3.2. Звнввутые ловувовьлв Кроме того, нэ элементов не более чем счетного множества всегда можно образовать последовательность, используя неко- торую нумер~щи этого множества.

Теорема 3.2. Любое конечное идемпотентное полукольцо замкнуто. м Поскольку носитель Я идемпотентного полукольца о=(Я, +,, О, 1) есть конечное множество, то множество элементов любой последовательности в этом полукольце конечно. Для нахождения точной верхней грани такой последовательности нужно найти точную верхнюю грань множества Р = (рм ...,р,Д ее членов, т.е., согласно теореме 3.1, вычислить некоторую конечную сумму, которая всегда существует. Таким образом, в конечном идемпотентном полукольце любая последовательность имеет точную верхнюю грань. Условия сохранения точных верхних граней имеют вид а(р~ +... + р„) = ар~ +...

+ ар„, (рь+... +р„)а = р~а+... +р„а и выполняются в силу аксиом полркольна. Таким образом, полукольцо о замкнуто. ~ь 00 ~ х„= еир (х„: и Е Щ. (3.2) Мы доказали (см. 3.1), что в любом идемпотентном полукольце сумма произвольного конечного множества элементов является его точной верхней гранью. В силу этого в замкнутом полукольце естественно точную верхнюю грань посведовательности 1х„)„ен называть суммой элементное посмедоеапьемьностпн, полагая, по определению, 184 3.

ПОЛУКОЛЬЦА Н БУЛЕБЫ АЛГЕБРЫ Согласно условию 2 определения 3.2, всегда 2 х„есть элемент в=1 множества Я. Иногда, если это не приводит к недоразумению, „пределы суммирования" будем опускать и писать просто Е х„. Также будем испольэовать обозначение ~~т х„. Подвен черкивая, что в (3.2) множество элементов х„в общем случае бесконечно, будем сумму, стоящую в левой части (3.2), называть бесконечной суммой. Заметим, что в частных случаях бесконечная сумма может свестись к конечной (если множество всех элементов последовательности (х„) конечно).

Итак, согласно определению 3.2, замкнутое полукольцо является икдукктивным упорядоченным мноэеесктвом, в котором каимекьтаим элементном служит нуль полукольца,точной верхней гранью произвольной (в частности, неубывающей) последовательности (хв1„ек является бесконечная сумма ~;х„, причем операция умножения на произвольный фиксированный элемент а кеирерывка в смысле определения 1.5, поскольку, согласно определению 3.2, сохраняет точные верхние грани. Заметим, что это свойство умножения в замкнутом полукольце можно рассматривать как аналог дистарибутиивностаи (седьмой аксиомы полукольца, см.

определение 3.1) для бесконечной суммы: а~~ х„=~~т ах„и (~~т х„)а= ,'т х„а. Для бесконечной суммы также справедливы аналоги свойств идемпотентности и коммутативности. Действительно, для последовательности (х„)„еи,такой,что х„ = а для любого к Е г1, имеем 2 х„ = впр(а) = а, т.е. бесконечная сумма, все слагаемые которой одинаковы и равны некоторому а, равна а. В этом состоит свойство идемпотентности бесконечной суммы (или, как иногда говорят, свойство бесконечной идемпотентности).

Так как точная верхняя грань последовательности любого упорядоченного множества равна, по определению, точной 185 3.2. Замкнутые кааукольла верхней грани множества всех элементов этой последовательности, то при любом расположении слагаемых в бесконечной сумме мы получим один и тот же результат. Это свойство есть свойство бесконечной коммутативности, или коммутативности бесконечной суммы. Сложнее обстоит дело с аналогом ассоциативности для бесконечной суммы.

Такая ассоциативность означает, что результат не изменяетсл при произвольной группировке слагаемых бесконечной суммы. Для некоторой последовательности (хп)пен элементов замкнутого полукольца и произвольной последовательности (пв)вен натуральных чисел образуем последовательность (вь)вен, где В1 = Х1 +...

+ Хп„ 82 = хо~+1 +... + хп1+ве ~ вв — хпа 1+1+ "° + хпе 1+вы Тогда бесконечная ассоциативность состоит в выполнении для любой последовательности (х,Дпен равенства ~> ха=2 вв. вен ЙЕМ (3.3) Свойство бесконечной ассоциативности (3.3) удобнее не доказывать непосредственно, а вывести из более общих результатов. Один иэ них касается характеристики замкнутых полуколец в терминах точных верхних граней счетных подмножеств.

а впрХ =вар(а Х), (вирХ) а=вор(Х.а). Теорема 3.3. Идемпотентное полукольцо о = (Я,+,,0,1) замкнуто тогда и только тогда, когда любое счетное подмножество Х С Я имеет точную верхнюю грань и для любого а е Я верны равенства 186 а. пОлукОлъцА и БулеБы АлГеБРы ~ Справедливость утверждения теоремы немедленно вытекает из определения точной верхней грани последовательности эле- ментов упорядоченного множества как точной верхней грани множества этих элементов. ° Теорема 3.4. Пусть 8 = (8, +,, О, 1) — замкнутое полукольцо, Х вЂ” не более чем счетное подмножество множества Я, а (В,);ау — не более чем счетное семейство подмножеств множества Х, такое, что объединение семейства совпадает с Х, т.е. ( ) В; =Х. Тогда 1е7 лир Х = аир (аир В;, а Е 1).

(3.4) м Поскольку множества Х и 1 не более чем счетны, то, согласно определению 3.2, все точные верхние грани из (3.4) существуют и принадлежат 8. Обозначим левую часть равенства (3.4) через а, а правую — через Ь. Так как а есть точная верхняя грань множества Х, то для любого х Е Х справедливо неравенство х ( а (где (— естественный порядок идемпотентного полукольца 8). В частности, для любого подмножества В; и любого его элемента у получаем р ( а, откуда следует, что элемент а есть верхняя грань каждого подмножества В;.

Значит, этот элемент не меньше чем точная верхняя грань каждого из этих подмножеств, т.е. для любого а Е 1 а ) )аир В;. Последнее означает, что а есть верхняя грань множества всех точных верхних граней аирВ;, а Е 1, т.е. а > Ь. В то же время, поскольку объединение всех подмножеств В; равно Х, для любого х Е Х найдется такое а Е 1, что х Е В;.

Характеристики

Список файлов книги