1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 14
Текст из файла (страница 14)
Ясно,inf(A1, !.!) определяются по А, и !.! однозначно, есличтоонисуществуют.Определение. Частично упорядоченное множествозываетсярешеткой,еслидлялюбыха, Ь Е Ав!.!!.!=(А, И) насуществуютsup({a,b},I.!) и inf({a,b},1.!), которые будут обозначаться через aU 21 bи а n 21 Ь. Решетка !.! = (А, И) называется дистрибутивной, если длялюбых а, Ь, с Е А операции U21 и n21 удовлетворяют следующим условиям:D) а u21 (Ьn 21 с) = (а u 21 Ь) n21 (аu 21 с);D') а n21 (Ьu 21 с) = (а n 21 Ь) u21 (аn 21 с).Решетка!.!=(А, И) называется булевой решеткой, если!.!дистрибутивна, имеет наибольший элемент 121 , наименьший элемент 021 и длялюбого а Е А существует такой элемент а Е А, что а U 21 а = 121 иа 21 а = 021 • Элемент а, удовлетворяющий в решетке !.! с наибольшимэлементом 121 и наименьшим элементом 0 21 указанным условиям, наnзывается дополнением элемента а вПредложение2.2.1.трибутивной решетке!.!.а). Если дополнение а элемента а в дис\.! с наибольшим и наименьшим элементамисуществует, то оно единственно.б).
Если \.! = (А, И) - булева решетка, то для любых а, Ь, с Е Аоперации u 21 , n 21 , определенные выше, удовлетворяют следующимусловиям (для простоты индекс\.! у U21 и 21 опущен):аксиомы булевой алгебры= Ь U а,2) а n Ь = Ь n а,1)аUЬn6) (aub)nb=b,3) aU(bUc)=(aub)Uc,4) а n (Ь n с)= (а n Ь) n с,5) (anb)Ub=b,7) an(buc) = (cnb)u(anc),8) а U (Ь n с)= (а U Ь) n (а u с),9) ( а n а) u Ь = Ь,10) (а u а) n Ь = ь.в). Если на множестве А заданы три операции: U,-,удовлеутверждения б)(гдеЬ и а), то параU(a, Ь), n(a, Ь)и -(а) пишутся как а= { (а, Ь) J а n Ь = а} является булевой решеткой, причем aUb=sup({a,b},1.!), anb=inf({a,b},I.!), aUa= 121 ,!.! =(А, И) для И1)-1 О)U Ь, а nnитворяющие для любых а, Ь, с Е А условиямan а= 0 21 •§ 2.2.
Частично упорядоченные множествау67До к аз ат ель ст в о. а). Для простоты будем опускать индекс 1.2{и 0 21 . Если а u а 11 и а n а2 = О, то=u 21 , n 21 , 121Аналогично из ательно, а,=n а, = Ои а U а2= 1 получаем= а2 U а1,а2следоваа2.б). Свойства 1) и 2) очевидны. Так как авыполняются9)и10).Так какl.2tu а= 121 ,тодистрибутивна, то выполняютсяn а = 021и а7)и8).
В дальнейшем условие (а, Ь) Е И будем обозначать через а ~ Ь. Изопределения операций U21 и n21 получаем, что для любых d, т 1 , m 2 Е Авыполняются следующие соотношения:(1) d ~ т, n m2 {=} (d ~ т 1(2) т, U m2 ~ d {=} (m1 ~ d(3) т,, m2 ~ m, U m2,(4) т1и d ~ т 2 ),и m2 ~ d),n m2 ~ m1, m2.Пользуясь этими фактами, легко установить свойства3)-6).рим, например, свойствочитателю. Из(4) получаем (а U Ь)nЬоставляя проверку6),~ Ь, а из3)-5)(3) и (1) получаем Ь ~ (аследовательно, из антисимметричности И получаемв). Из условий5), 6), 1)а7)2)nЬ =аа{=}1аUЬ= Ь.(2.1)n Ь = а} -вместо Ь элемент а, а вместо спользовавшись условиямиИ рефлексивно.
Пусть а2), 1), 6)nЬ = аu Ь) n Ь,6).получаем= {(а, Ь)Покажем сначала, что ИПодставив виПровеи Ьи9),частичный порядок.-элемент а и восполучаем а= аn с = Ь.Изn а,значит,и2)Ь, тогда из2)(2.1 ), 7), 5), 1)получаемаn с= а n (Ь u с)=(аn Ь) u (а n с) = а u (а n с)= а,следовательно, И транзитивно. Пусть аполучаем а= Ь,nЬ=аи Ьnа=т. е. И антисимметрично. Для завершения доказательства нужно показать, что а U Ь= sup( {а, Ь}, 1.2t)и аn Ь = inf( {а, Ь}, 1.2t).Докажем первое из этих равенств, оставляя проверку второго читателю.
Изи аUЬа= Ь UаПусть с-n (а u Ь) = (а n а) u (а n Ь)получаем, что а= а U (аn Ь)= аверхняя грань множества {а, Ь}.n с= а и Ь n с= Ь. Тогда(а u Ь) n с= с n (а u Ь) = (с n а) u (с n Ь) = а u Ь,верхняя грань {а, Ь}, т. е. ат. е. (а U Ь, с} Е И.з•UЬ -о68Гл.Условия1)-10)2.Теория множествиз предложения2.2.1называются аксиомами булевых алгебр, а множество А вместе с определенными на нем операциямиn, U, -,удовлетворяющими аксиомамалгеброй. Если2t=(А,U, n, -)-1)-10),называется булевойбулева алгебра, то черезбудет:,,;;обозначаться частичный порядок на А, определенный условиемаИз предложенияотношениемПример:,,;;2.2.1:,,;;Ь ~ аn Ь = а.следует, что булева алгебра2tопределяетсяоднозначно.2.2.2.Если А ~ Р(В) и множество А замкнуто относительно операций объединения и пересечения, то легко проверить, что2(=(А,~). где ~ -отношение включения на А, является дистрибутивной решеткой, причем U21 иn21являются операциями объединенияи пересечения на А.Пример2.2.3.Если в примере2.2.2множество А замкнуто относительно операции взятия дополнения в В (т.
е. операции а= В\ а), то2t =(А,~) является булевой решеткой, а (А,рой, гдеU, n, --U, n, -)-булевой алгебоперации объединения, пересечения и дополненияв В. В частности, если А= Р(В),то (Р(В),U, n, -) будет называтьсябулевой алгеброй всех подмножеств В и для простоты будет иметьто же обозначение Р(В), что и множество всех подмножеств В.Определение. Частично упорядоченное множество (ч. у.
м.)(А, И)называется фундированным,подмножества А, ~ А ч. у. м. 2t1=если(А,, Идляn Ат)любого2t =непустогоимеет минимальныйэлемент.Если (А, И)-фундированное частично упорядоченное множество,В 2 ) также будет фундированным частичното очевидно, что (В, Иnупорядоченным множеством для любого В ~ А.На фундированное частично упорядоченное множество можно обобщить метод математической индукции.Предложение2t=(А, И)-2.2.4(принцип трансфинитной индукции).
Пустьфундированное частично упорядоченное множествои В~ А. Если для любого а Е А из {Ь Е А1(Ь,а) Е И,Ь-1-а}~ Вследует а ЕВ, то В= А.-1- А,До к аз ат ель ст в о. Предположим, что В(А\ В) 2 ).мальный элемент ч. у. м. (А\ В, ИЕ И, Ь-1- ао}nи пусть а 0 -Тогда {Ь Е Амини1(Ь, ао) Е~ В и по условию имеем ао ЕВ, что невозможно.D69Частично упорядоченные множества§ 2.2.21 =Определение. Пусть(А, И)линейно упорядоченное множе-ство. Множество Х ~ А будем называтьа) начальным отрезком21,если для любых а, Ь Е А из а Е Хи (Ь, а) Е И следует Ь Е Х (если Х-/=А, то начальный отрезок Хназывается собственным начальным отрезком21);б) замкнутым начальным отрезком, если для некоторого ао Е Амножество Х равно множеству О[ао,в)21] ={Ьоткрытым начальным отрезком,=О(ао,21)(О[ао,21]1(Ь, ао) Е И};если Хравно множеству{ао}) для некоторого ао Е А.\Часто, когда ясно, о какомО(а 0 ) вместо О[ао,21]и О(ао,21 идет речь, мы будем писать О[ао] и21) соответственно. Заметим, что пустоемножество 121 является начальным отрезком любого линейно упорядоченного множества.
Очевидно, что элемент ао в б) и в) предыдущегоопределения определен по Х однозначно.Примеры. ПустьG-отношение «меньше или равно,> на действительных числах (т. е. (а, Ь) Е С<;=}а~ Ь).1. В линейно упорядоченном множестве ((.,), G n (.,) 2 ) любой отличный отw начальный отрезок является одновременно и открытым, изамкнутым.2.В(R, G),отличный отRгдеR -множество всех действительных чисел, любойначальный отрезок является открытым или замкнутым,но никакой начальный отрезок(R, G)не является одновременно открытым и замкнутым.3.
В (Q, G n Q 2 ), где Q - множество всех рациональных чисел, начальный отрезок {r I r < J2} не является ни открытым, ни замкнутым.Предложение=(А, И)-2.2.5(свойства начальных отрезков). Пусть1). Если Х - начальный отрезок 21 и В ~ А, то Хначальный отрезок в (В, И n В 2 ).2).21 =линейное упорядоченное множество.Если Х1, Х2-начальные отрезки21,nВ-то либо Х1 ~ Х2, либоХ2~Х1.3). Если И - множество начальных отрезков 21, то21.UИи ПИ-начальные отрезкиХ4). Если Х - начальный отрезок 21, а Е А\ Х, то множествоU {а} тогда и только тогда является начальным отрезком 21,когда элемент а является наименьшим элементом в линейно упо(А\ Х) 2 ).рядоченном множестве (А\ Х, И5).nОткрытый начальный отрезок О(ао,только тогда, когда ао-21)наименьший элемент.равен 121 тогда иГл.702.Теория множествДоказательство. Утверждения пп.сразу следуют из1), 3), 5)определений.Для доказательства п.2) предположим, что существуют элеменai Е (Xi \ Хз-i), i Е {1, 2}.
Так как 21 - линейно упорядоченноемножество, то для некоторого i Е { 1, 2} мы имеем (ai, аз-i) Е И. Таккак Хз-i начальный отрезок и аз-i Е Хз-i, то ai Е Хз-i, чтопротиворечит условию ai (/:. Хз-i4). Пусть Х - начальный отрезок 21. Если для некоторых Ь, а (/:. Хвыполнено (Ь, а) Е И и Ь =j:. а, то (Х U {а}) не является начальнымтыотрезком. Пусть элемент а является наименьшим элементом в линейноупорядоченном множестве (А\ Х, И n (А\ Х)2). Тогда любой элемент Ьс условиями (Ь, а) Е И и ЬХначальный отрезок-зок=j:.а принадлежит Х. Учитывая то, чтополучаем, что Х U {а}21,начальный отре-О21.Определение.
Если 2t=(А, И) -ч. у. м., Х ~ А и Илинейный порядок на Х, то Х называется цепью в21.nХ2 -В частности,пустое множество является цепью в любом ч. у. м.В§ 2.1была сформулирована одна аксиома теории множеств, которой мы уже пользовались,-это аксиома экстенсиональности. Впредьмы будем использовать также аксиому выбора, утверждающую, чтодля любого непустого множества А существует такое отображение(функция выбора) h: (Р(А) \{0})--+А, что h(B) ЕВ для любогонепустого В ~ А.
Из этой аксиомы вытекают следующие два важныхпринципа.Теорема2.2.6(принцип максимума). Если в частично упорядоченном множестве21=(А, И) каждая цепь Х ~ А имеет верхнюю2tгрань, то существует максимальный вэлемент.До к аз ат ел ь ст в о. Рассмотрим множество Уцепь в21}и множества В(Х)для Х Е У.ложим, чтоS=По условию В(Х)Iа{а Е А=j:.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
