XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 30
Текст из файла (страница 30)
Поэтому х ( аирВ; ( Ь, это означает, что элемент Ь является верхней гранью множества Х, и тогда Ь > а, так как а есть точная верхняя грань Х. Итак, а > Ь и Ь > а, откуда о = Ь, и равенство (3.4) доказано. ° 187 3.2. Заиккутые поауаольпа Следствие 3.1. Если семейство подмножеств иэ теоремы 3.4 (Ве);е1 конечно, т.е. 1 = (1, 2,..., и), то еирХ = ~> зир В,. М1 Следствие 3.2. Пусть (хо)оси — произвольная последоватекьность элементов замкнутого полукольца и (Ф;);е1— не более чем счетное семейство подмножеств 1Ч, такое, что Ц Л~е = И.
ТогДа ае1 (3.5) «е1 гдеа;= ,'1 х,„. теФ; В частности, из следствия 3.2 при условии, что множества Ф;, 1 Е 1, попарно не пересекаются, получаем свойство ассоциативности бесконечной суммы 13.3). Отсюда же при Ф1 = (Ц, Из = (1, 2) и т.д., т.е. при определении для любого натурального М множества Ла в виде Жь = Фь 111 (к), получаем равенство ~~> Хо=~~1 (Х1+...+Ха), оеи вел (3.6) 'Такую последоватеаькость квзывают проввведевиеы Коши исходкьпс посеедоватеаькостей ~ Щ.
т.е. точная верхняя грань последовательности (хе)пен равна точной верхней грани поскедовательности часетьичыьсх сумм (ав)ЬЕН~ ГДЕ Вь = Х1+... + Ха. Пуетв (Хо)вяи И (Уш)тяи ПРОИЗВОЛЬНЫЕ ПОСдвдозатЕЛЬ ности в замкнутом полукольце 8. Образуем посяедовательность, членами которой являются все произведения херш при независимом пробегании индексами и и тп множества натуральных чисел'. Эту последовательность будем записывать 188 3. ПОЛУКОЛЪЦА И БУЛЕБЫ АЛГЕБРЫ Теорема 3.5. В любом замкнутом полукольце верно то- ждество *врт = (,'~„*в) (',~ Ут). в,тЕМ вЕМ тЕМ (3."7) т Ввиду непрерывности умножения в замкнутом полукольце правую часть тождества (3.7) можно переписать в виде (~ Жв) (~~~ ут) = ~~~ (,~~ хв)ут. вЕМ твЕН тЕМ вЕМ Еще рзз используя непрерывность умножения и внося сомножитель у,„под знак внутренней суммы, получаем (,~ хв) У1в — ~~~ (~~ хвУт) ° тЕМ вЕМ язЕМ вЕМ В правой части последнего равенства каждое слагаемое внешней суммы (по яь) есть точнал верхняя грань подпоследовательности (хву„,)вем при фиксированном тв.
Поскольку все зти подпоследовательности в совокупности дают всю последовательность (хвут)в,тем, то, согласно следствию 3.2, получаем (~~ рвут) = ~~~ хвут1 тЕМ вЕМ в,тЕМ что и доказывает тождество (3.7). т Следующая теорема устанавливает связь между конечной и бесконечной суммами. Пусть (яв)вем и (ув)вем — произвольные последовательности в замкнутом полукольце 8. Образуем последовательность (Хв + Ув)вЕМ, НаЗЫВаЕМУЮ СУММОЙ ИСХОДНЫХ ПОСЛЕДОВатЕЛЬНО- стей.
КаК (Хвут)в,тЕМ, а ЕЕ тОЧНуЮ ВЕРХНЮЮ ГраНЬ ОбОЗНаЧИМ КаК хвут. в,тЕМ 189 3.2. Замквутые воаукольяа Теорема 8.6. В любом замкнутом полукольце точная верхняя грань суммы двух произвольных последовательностей равна сумме точных верхних граней этих последовательностей, т.е. ~~~ (хо+рп) =~ хо+~1,9о. (3.8) м Обозначим через Х множество всех членов последователь- ности (хо)„ен, а через У вЂ” множество всех членов последова- тельности (у,Д„ен. В силу следствия 3.2 вар(ХОУ) =впрХ+вирУ =~~~ х„+~~> у„.
Осталось тогда доказать, что ,'> (х„+у„) =вар(ХОУ). (3.9) Если в (3.8) р„= а для всех и, то получаем следствие. Следствие З.З. Для любой последовательности (х„)„ен элементов замкнутого полукольца и любого элемента а этого полукольца выполняется равенство а+ ~~ х„= ,') (а+х„). (3.10) Обозначим через а левую, а через Ь правую часть доказываемого равенства (3.9).
Для любого натурального и имеем а > х„+ у„. Согласно теореме 3.1, х„+ у„) х„и хо + ро ) ро. Следовательно, для любого и выполняются неравенства а ) х„и а ) у„, т.е. а > и для любого и Е ХОУ. Таким образом, элемент а является- верхней гранью множества Х 0 У, откуда а > 6. В то же время элемент Ь не меньше любого из элементов множества Х ОУ, и, стало быть, для'любого натурального и имеет место 6) х„и Ь > 9„, т.е. Ь Ъ вор(х„,уо) = х„+р„.
Это значит, что 6 есть верхняя грань последовательности (хо+ ро)оеи, а потому Ь Р а. Итак, а = 6, и равенство (3.9) доказано. ~ 190 з. полукольца и кулккы ллгккры Тождество (3.10) можно рассматривать как свойство непрерывности операции сложения в замкнутом полукольце. Это свойство совершенно аналогично свойству непрерывности операции умножения, которое имеет место по определению. Одним из важнейших понятий в замкнутых полукольцах является понятие игперацпи (или замыкания) э вемектла замкнутого полукольца.
Итерация я' элемента я определяется как точная верхняя грань последовательности всех сшепеией элемента я, т.е. пеа где, по определению, яо = 1, а я" = х" ~х,п= 1,2,... Пример 3.5. а. Из теоремы 3.2 сразу получаем, что идемпотентное полукольцо 6 (см. пример 3.2) замкнуто, причем точная верхняя грань любой последовательности элементов этого полукольца равна 1, если хотя бы один ее член равен 1, и равна 0 в противном случае. В частности, итерация любого элемента полукольца В равна 1. Для 1* это очевидно, а для О" имеем 0' =0 +О +...+О" +... =1+0+... +О+... =1. б.
В идемпотентном полукольце К+ (см. пример 3.1) любая последовательность есть последовательность неотрицательных действительных чисел. Такая последовательность ограничена снизу и, как известно из курса математического анализа, имеет точную нижнюю грань относительно естественного числового порядка Щ, которая, согласно примеру 3.4, представляет собой точную верхнюю грань относительно естественного порядка идемпотентного полукольца К+. Напомним, что этот порядок является двойсшвеиным к естественному числовому порядку. Итак, для любой последовательности я„элементов полукольца К+ точная верхняя грань существует.
Непрерывность операции умножения в этом полукольце также можно доказать, 191 З.а Занккугыеполукольца опираясь на естественный числовой порядок, для которого она эквивалентна выполнению равенства а+ АХ = шГХе, где а — неотрицательное действительное число, а Х (соответственно Х„) — множество элементов последовательности х„ (соответственно х„+ а). Равенство (3.11) следует из известных результатов математического анализа. Таким образом, рассматриваемое идемпотентное полукольцо Е+ является замкнутым.
Итерация х* элемента х в полукольце К+ есть точная верхняя грань последовательности степеней элемента х. Поскольку в этом полукольце операция умножения определена как операнда сложения действительных чисел, то хе = О, так как число О есть единица полукольца К+. Далее, хз = х+ х = 2х, ..., х" = нх. Очевидно, что для каждого н > О выполняется неравенство х" ) О в смысле естественного числового порядка. Таким образом, число О есть наименьший в смысле естественного числового порядка член последовательности (х")„ен и, следовательно, шах")„ен = О. Переходя к двойственному порядку — естественному порядку полукольца К+, получим, что число О является точной верхней гранью последовательности (х")„ен, т.е. х* = О. Таким образом, в полукольце К+ итерация произвольного элемента также равна единице полукольца, т.е.
числу О. в. Замкнутость идемпотентного полукольца Вл (см. пример 3.3.6) можно обосновать следующим образом. Отношение естественного порядка этого полукольца — это ошношение включения (см. пример ЗА). Рассмотрим произвольную последовательность подмножеств Вм ..., В„, ... множества А. В данном полукольце бесконечная сумма есть объединение последовательности подмножеств множества А. Докажем, что объединение В = ( ) В„и есть впрВ„. Очеаеи видно, что для каждого 1 справедливо включение В; С В, т.е.
192 3. ПОЛУКОЛЬЦА И БУЛЕБЫ АЛГЕБРЫ объединение есть верхняя грань последовательности (Вв)вен. Покажем, что В будет точной верхней гранью. Рассмотрим произвольную верхнюю грань С последовательности Вв. Тогда В„С С для каждого н 611 (см. 1.5) и поэтому сов=сочв„) = Ц(сов„)=с, веи вен т.е. В С С.
Следовательно, В = Ц Вв = япр Вв. вен Непрерывность умножения полукольца ЮА, в качестве которого взято пересечение множеств, эквивалентна тождеству СГУБЯ в„) = Ц(сив„) вен вен (дистрибутивности пересечения относительно произвольного объединения, см. 1.5). В этом полукольце умножение — это пересечение множеств. Поэтому любая положительная степень множества Х есть само Х. Нулевая же степень Хо равна единице полукольца, т.е. множеству А. Поэтому итерация Х' равна Хо Х Хв Хо т.е. также равна единице полукольца. г.
Рассмотрим идемпотентное полукольцо 1сА (см. пример 3.3.в) бинарных отношений на множестве А. Можно доказать, что точной верхней гранью любой последовательности отношений, как и в полукольце 8А, служит объединение элементов этой последовательности (см. пример 3.4). Аналогично доказательству дистрибутивности композиции бинарных отношений на множестве относительно конечного объединения (см. 1.4) можно доказать, что для любых бинар- 193 3.2. Замквутне яаюуяольлв ных отношений р и ив на множестве А справедливы тождества 0"= 0(Р. -) в)1 в)1 (~ а„) вр= Ц(овр).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
