1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 16
Текст из файла (страница 16)
В силу предложеf <;;; g, либо g <;;; f. Поэтомуf будет изоморфизмом начального отрезка Х вполне упорядо-f ЕРченного множества ~ на начальный отрезок У вполне упорядоченногомножества~. Если Х=Аили У= В, то все доказано. Предположим,2.2.8 имеем Х = О(а 0 , ~) иF U { (ао, Ьо)} будет тогда изоморфизмомчто это не так. Тогда по предложениюУ= О(Ьо,~).Очевидно, чтоначального отрезка О[ао,тельно,F U { (ао, Ьо)}75Фильтры булевой алгебры§ 2.3.на начальный отрезок О[Ьо,2t)123],следова~ F, что невозможно.ОУпражнения1.=Показать, что если 2((А, И)ч. у. м. с наименьшим элемен-том, А конечно и для любых а, Ь Е А существуетто 2( -2.sup( {а, Ь }, ~).решетка.=Пусть 2((А,U, n, -) -булева алгебра и А содержит болееодного элемента.
ОтображениеIмножестваFформул ИВ в А.обладающее свойствами:1) 1 (Ф V Ф)= 1 (Ф) U 1 (Ф),3) 1 (Ф---+ Ф)4),(~Ф)= ,(Ф) U 1 (Ф),= 1 (Ф),называется интерпретацией ИВ в Qt. Показать, что доказуемыеИВ формулы -это в точности такие Ф, что ,(Ф)любой интерпретацииустановить 1 ( Ф)= 1Q1IИВ в(Указание.2t.= lQiдляВ одну сторонудля аксиом ИВ 1 и проверить, что правилоИВ1 сохраняет это свойство, в другую сторону воспользоватьсятем, на множестве { 1Q1, О~} операции U,же, как на множестве3.{1, О}nи - определяются такопределяются операцииV, /\и~.)Показать, что ч. у. м. (А, И) тогда и только тогда не является фундированным,когдасуществуетпоследовательностьао,... , an, ...попарно различных элементов А, для которой (ап+I, ап) Е И,nЕw.§ 2.3.Фильтры булевой алгебрыПусть на протяжении этого параграфагебра.
Как показано в предложенииа ~ Ь определяется равенством а123 =2.2.1, 123*nЬ =(В,n, U, -) -булева ал=(В,~). где отношениеа, является булевой решеткойи для любых а, Ь Е В выполняются условия:(1) aUb=sup({a,b},123*), aПb=inf({a,b},123*);(2) а U а= 1 - наибольший элемент 123*;(3) а n а = О - наименьший элемент 123*;(4) а является единственным элементом В, для которого выполняются условия аuа = 1 иаnа =О.Отметим еще некоторые свойства булевых операций.Леммавами:2.3.1.Булевы алгебры обладают следующими свойст-а) О= 1, Т= О;г) а= а;n Ь = au Ь;а u Ь = а n Ь;б) ОО, Од) ав)а,е)nа =1 n а=ж) аu а = а;1 u а= 1;nЬ=а{::::::}аU Ь = Ь.76Гл.До к аз ат ел ь ст в о.Теория множеств2.Свойствоа)непосредственно вытекает из(1)-(4).
Свойства 6), в) следуют из (1)-(3), а г)а U а= а U а= 1 и а n а= а n а= О. Свойствокак аnЬ = а{=>следует из(4),ж) следует изтак кактак(l),а~ Ь. Для доказательства д) в силу (4) достаточнопоказать, что(а n ь) u (а u Ь)=lЭти равенства следуют из аксиом(а n Ь)n (а u Ь) =((аи(а n ь) n (а u Ь)1)-6)=о.булевых алгебр, например,n Ь) n а) u ((а n Ь) n Ь) =(О n Ь)u (О n а)=о.Проверка другого равенства, а также доказательство свойства е), проводятся аналогично.ОЧасто для простоты обозначений мы будем отождествлять ~* с~-Пусть далее В неодноэлементно.Определение. Множествоалгебры1) Оi~.D <;;;В называется фильтром булевойесли выполняются следующие условия:D;2) если а, Ь Е D, то а n Ь Е D;3) если а Е D и а ~ Ь, то Ь Е D.МножествоDD <;;;Р(Х) называется фильтром на множестве Х, еслиявляется фильтром булевой алгебры (Р(Х),Примеры.U, n, -)иD -=f. 0.{ l} является фильтром булевой алгеб3) вытекает, что l Е D для любогонепустого фильтра D в булевой алгебре ~2.
Если ао Е В, ао -=f. О, то множество {Ь I Ь Е В, ао ~ Ь} будетфильтром алгебры ~3. Множество {У <;;; Х I Х \ У - конечное множество} является1.Множестворы~- С другой стороны, из условияфильтром на бесконечном множестве Х, который иногда называютфильтром Фр еше на Х.Так как операцииUмам коммутативностииnбулевой алгебры ~ удовлетворяют аксио1), 2)и аксиомам ассоциативности3), 4),томожно говорить об объединении (пересечении) в ~ конечного множества элементов а1,(а,n ... n an)....
, anЕ В и обозначать его так: а1U ... U anИндукцией по п легко устанавливаются следующиеобобщенные законы дистрибутивности:Ь U (а1n ... n an) =Ь П ( а I U ... Uan)(Ь U а1)n ... n (Ь U an),= (Ь П а 1) U ... U ( Ь П an),§ 2.3.Фильтры булевой алгебрыа также обобщения свойств д), е) леммыа1 П...Пап =а1772.3.1:U ... Uan,Определение. а). Множество У~ В называется центрированнымв булевой алгебре ~в, если пересечение в 11, любого конечного множества элементов из У не равно О. Центрированное в (Р(Х),U, n, -)множество (т. е. такое множество У ~ Р(Х), у которого любое конечное подмножество имеет непустое пересечение) будем просто называтьцентрированным.6).Фильтр булевой алгебры !В, не содержащийся ни в каком отличном от него фильтре алгебры !В, называется ультрафильтром.Ясно, что любой фильтр булевой алгебры 11, будет центрированнымв11, множеством.Предложение2.3.2.Каждое центрированное в булевой алгебре11, множество У содержится в некотором ультрафильтре алгебры !В.До к аз ат ель ст в о.
Рассмотрим множество И= {ХIХцен-трированное в 11, множество и У ~ Х}. Так как У Е И, то И# 125.Очевидно, что в ч. у. м. (И,~) объединение любой цепи являетсяэлементом И. По теореме2.2.6в (И,~) имеется максимальный элементХо. Достаточно показать, что Хо является фильтром. УсловиеХо тривиально выполнено. Для проверки условия2)и3)1)дляв силумаксимальности Хо достаточно показать, что если а, Ь Е Хо и ато ХоХоU {аU {а nn Ь}и Хо:( с,U {с} центрированы в !В. ЦентрированностьЬ} очевидна.Предположим, что а1некоторых а1, ... , an Е Хо. Тогда из равенства сО= Оn а=(а 1n ... n an n с =nа = аО дляполучаемn ...
n an n с) n а== (а1 П ... Пап) П (с Па)= а1 П ... П an Па,что противоречит центрированности Хо.Предложение2.3.3.DДля того чтобы фильтрбулевой алгебDры 11, был ультрафильтром, необходимо и достаточно, чтобы длялюбого Ь ЕВ было либо Ь Е D, либо Ь Е D.До к аз ат ель ст в о. В силу предложенияства2.3.2для доказательнеобходимости нужно лишь показать, что длялюбогоЬ Е Влибо D U {Ь}, либо D U {Ь} является центрированным в 11, множеством.Предположим, что это не так. Тогда Ь1n ...
n Ьп n Ь =О78Гл.и Ьп+In ... n Ьп+m n ь =свойстваU,n, -2)фильтраDТеория множеств2.о для некоторых ь,,можно считать п=т=... 'Ьп+m1.Е D. в силуИз свойств операцийв булевой алгебре SВ получаемь, П Ь2=ь, П Ь2 П (Ь U Ь)=(Ь, П Ь2 П Ь) U (Ь1 П Ь2 П Ь)=что противоречит свойствам1), 2)(ОП Ь2)фильтра=U (Ь1ПО)= 0 U O = О,D.D* 2 D и элемент Ь Е(J. D, так как в противном случае О = Ь n Ь Е D*, чтоДостаточность. Если существует фильтрЕ D* \ D, то Ьневозможно.ООпределение.
ФильтрD булевойD, чтоалгебры SВ называется главным,если существует такой ао ЕD={Ь ЕВI ао ~ Ь}.Элемент а ЕВ называется атомом булевой алгебры SВ, если а-/= О иЬ ~а==} (Ь = а или Ь = О).Ясно, что если аатом SВ, то Ь-nаравно а или О для любогоЬЕ В.Лемма2.3.4.ЕслиD= {Ь ЕВ I ао ~ Ь}Ьо-/=-/=D -главный ультрафильтр алгебры SВ, тодля некоторого атома ао алгебры SВ.D =Доказательство.
ПустьО. Предположим, что Ьо-{Ь ЕВI Ьо~ Ь} для некоторогоне атом. Тогда существует Ь1 ~ Ьо,Ь1Ьо, Ь1 -/= О. Так как Ь, (J. D, то по предложению 2.3.3 выполняетсяЬ1 Е D, откуда Ьо ~ Ь1, т. е. Ьо n Ь1 = Ьо. Следовательно,ополучили противоречие.Предложение2.3.5.Следующие условия для булевой алгебры SВэквивалентны:1) В - конечное множество;2) все непустые фильтры SВ главные;3)все ультрафильтры SВ главные.До к аз ат ель ст в о.D= {Ь1, ... , Ьп} -принадлежитDУтверждение1)==}2).Если В-конечное множество ифильтр алгебры SВ, то пересечение аои ао ~ Ьi для2)==?3)i=1, ... , п.тривиально.= Ь1 n ...
n Ьп§ 2.3. Фильтры булевой алгебрыДокажем3)==?1).Пусть выполняетсяство всех атомов алгебры3).79Пусть Ао<;;;Рассмотрим множество А,113.В-множе= {а I а Е Ао}.Покажем, что А, не центрированное. В самом деле, если А, центрированное, то по предложению2.3.2трафильтраи леммыD.Из условия3)имеем А,такой ао Е Ао, что ао ~ Ь для всех Ь Еао=аоn ао = О,Так как А,В частности, ао ~ ао, т. е.что противоречит условию ане центрированное, то а1а1, ... , an Е Ао.
Из леммыl = 0 = а1 ППусть ЬD.=f.О для атомов а Е Ао.n ... n an =О для некоторыхтогда получаем2.3. l... П anдля некоторого уль<;;; Dполучаем, что существует2.3.4а1 U ... U an== а1U ... U an,произвольный элемент В. Тогда-= Ь n l = Ь n (а,ЬТак как Ьn ai,U ... U an)=(Ьnа1) U ... U (Ьn an),равно ai или О, то Ь равно О или объединению некоторых элементов множества{ а1,... , an}, Следовательно, В-конечноемножество.ОПредложениежествеI,тоD2.3.6.ЕслиD -= {Х <;;; I I io Е Х}главный ультрафильтр на мнодля некоторого io Е J.До к аз ат ель ст в о. Следует из леммычто вP(I)2.3.4,так как очевидно,атомами являются одноэлементные множества.ОУпражнения1.ПустьD -непустой фильтр булевой аЕгебрыНа множестве В определим отношениеaDb{==}D113= (B,u,n, -).следующим образом:(anb)u(bna) Е D,где D равно {d I d Е D}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
