Частично упорядоченные множества

ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà×àñòü IV×àñòè÷íî óïîðÿäî÷åííûåìíîæåñòâà1 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÐàçäåëû1Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ2Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè3Ëèíåàðèçàöèÿ4Çàäà÷è c ðåøåíèÿìè5Ìîäåëè Êðèïêå2 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà3 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà: îïðåäåëåíèå è ïðèìåðûÎïðåäåëåíèåÏàðó P = h P, 6 i, ãäå P íåïóñòîå ìíîæåñòâî, à 6 ðåôëåêñèâíîå, àíòèñèììåòðè÷íîå è òðàíçèòèâíîå áèíàðíîåîòíîøåíèå íà í¼ì, íàçûâàþò ÷àñòè÷íî óïîðÿäî÷åííûììíîæåñòâîì (ñîêðàù¼ííî ÷.ó. ìíîæåñòâîì, àíãë.

poset).Ðåôëåêñèâíîñòü (R): x 6 x;Àíòèñèììåòðè÷íîñòü (AS): (x 6 y) N (y 6 x) ⇒ x = y ;Òðàíçèòèâíîñòü (T): (x 6 y) N (y 6 z) ⇒ x 6 z .Ïðèìåðûh P(M ), ⊆ i êëàññè÷åñêèé ïðèìåð ÷.ó. ìíîæåñòâà(óïîðÿäî÷èâàíèå ìíîæåñòâ ïî âêëþ÷åíèþ, M 6= ∅);h N, 6 i è h N, | i äâà óïîðÿäî÷èâàíèÿ îäíîãî ìíîæåñòâà.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà4 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÏðåäïîðÿäêèÂîïðîñÏóñòü M ìíîæåñòâî ëþäåé, h(x) ðîñò, à w(x) âåñ÷åëîâåêà x.Îïðåäåëèì íà îòíîøåíèå ρ íà M :xρy ⇒ (h(x) 6 h(y)) N (w(x) 6 w(y)).ßâëÿåòñÿ ëè ρ îòíîøåíèåì ÷àñòè÷íîãî ïîðÿäêà íà M ?Îòâåò. Íåò.

ρ ðåôëåêñèâíî è òðàíçèòèâíî, íî íå ÿâëÿåòñÿàíòèñèììåòðè÷íûì îòíîøåíèåì: xρy N yρx 6⇒ x = y (ìîãóòíàéòèñü äâà ÷åëîâåêà ñ îäèíàêîâûìè ðîñòîì è âåñîì).Îòíîøåíèÿ ñî ñâîéñòâàìè (R) è (T) íàçûâàþòdefïðåäïîðÿäêàìè.Ïîíÿòíîå îáîçíà÷åíèå: a < b = (a 6 b)N(a 6= b)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà5 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó.

ìíîæåñòâ×.ó. ìíîæåñòâî P = h P, 6 i îñíîâíûå ïîíÿòèÿ:åñëè (x 6 y) ∨ (y 6 x), òî x è yîíè íåñðàâíèìû (x y );ïîëíûé (ëèíåéíûé) ïîðÿäîê,ñðàâíèìû(x ∼ y ), èíà÷ååñëè ∀ x, y : x ∼ y ;åñëè â P íåò íè îäíîé ïàðû ðàçëè÷íûõ ñðàâíèìûõýëåìåíòîâ, òî ýòî òðèâèàëüíî óïîðÿäî÷åííîå ìíîæåñòâî;xy (y íåïîñðåäñòâåííîx), x l y , åñëè x 6 z 6 y ⇒ (z = x) ∨ (z = y);íåïîñðåäñòâåííî ïðåäøåñòâóåòñëåäóåò çà{x ∈ P | a 6 x 6 b} èíòåðâàë[ a, b ];defv1 < . . . < vn = [v1 , . .

. , vn ] öåïü n, à ñîâîêóïíîñòüïîïàðíî íåñðàâíèìûõ ýëåìåíòîâ àíòèöåïü â P;öåïü ìàêñèìàëüíàÿ (íàñûùåííàÿ), åñëè ïðè äîáàâëåíèè êíåé ëþáîãî ýëåìåíòà îíà ïåðåñòà¼ò áûòü öåïüþ;def> äâîéñòâåííûé ê 6 ïîðÿäîê: 6d = >.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà6 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÄèàãðàììû Õàññå◦◦◦◦◦◦◦◦[[[◦[[ ◦[◦Äèàãðàììû Õàññå ÷åòûð¼õ íåòðèâèàëüíûõ íåïîìå÷åííûõòð¼õýëåìåíòíûõ ÷.ó. ìíîæåñòâ.◦ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó.

ìíîæåñòâÄèàãðàììà Õàññå ÷.ó. ìíîæåñòâà h { 1, . . . , 18}, | i16[[ 12 [[ 8[[96 [4' 15 [AA '10''' 14'''[[[''A''A[''''A'A'''''A''3 hh 11 hhhh2 [[ 13 5 AAA '7''' 17hhhh[ AA''''hh A''A''1187 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà8 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÄèàãðàììû Õàññå: äà èëè íåòÂîïðîñ: ýòî äèàãðàììû Õàññå?A ◦ AAAA◦ [◦[◦◦ehh 444c hh AAA444 dhA A abÎòâåò. Íåò! Ïðàâèëüíî:A ◦ AAAA◦ [◦[◦◦df[[[[ cabÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó.

ìíîæåñòâÄèàãðàììû âñåõ 4-ýëåìåíòíûõ ÷.ó. ìíîæåñòâ9 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÄèàãðàììà D(180) âñåõ äåëèòåëåé ÷èñëà 180 = 22 32 5Îäíà èç ìàêñèìàëüíûõ öåïåé èèíòåðâàë [ 3, 60 ].×. ó. ìíîæåñòâî, âñå èíòåðâàëûêîòîðîãî êîíå÷íû ëîêàëüíî êîíå÷íîå10 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà11 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÇàäà÷àÏîñòðîèòü äèàãðàììó Õàññå âñåõ ïîäïîëåé ïîëÿGF 218,óïîðÿäî÷åííûõ ïî âêëþ÷åíèþ.Ðåøåíèå.

Fnp ⊆ Fkp ⇔ k | n. Âñå äåëèòåëè ÷èñëà 18 = 2 · 32 :D(18) = { 1, 2, 3, 6, 9, 18 }.GF 218GFGF[[[2''''2[[[2'''6GF 23[[[[GF (2)'''GF 29[[[ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ×.ó. ìíîæåñòâà: îñîáûå ýëåìåíòûÎïðåäåëåíèåÝëåìåíò u ∈ P ÷.ó. ìíîæåñòâà h P, 6 i íàçûâàþò:ìàêñèìàëüíûì,åñëè u 6 x ⇒ u = x,ìèíèìàëüíûì, åñëè u > x ⇒ u = x,íàèáîëüøèì, åñëè x 6 u,íàèìåíüøèì, åñëè x > uäëÿ ëþáûõ x ∈ P .Ýëåìåíòíàèáîëüøèé, åñëè âñå äðóãèå ýëåìåíòû ñîäåðæàòñÿ â í¼ì;ìàêñèìàëüíûé, åñëè íåò ýëåìåíòîâ, ñîäåðæàùèõ åãî(àíàëîãè÷íî äëÿ íàèìåíüøåãî è ìèíèìàëüíîãî ýëåìåíòîâ).12 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó.

ìíîæåñòâÎñîáûå ýëåìåíòû ÷.ó. ìíîæåñòâà: ïðèìåð• ìàêñèìàëüíûå ýëåìåíòû;• ìèíèìàëüíûé è íàèìåíüøèé ýëåìåíò;Íàèáîëüøèé (1) è íàèìåíüøèé (0) ãðàíè÷íûå ýëåìåíòû. êîíå÷íîì ÷.ó. ìíîæåñòâå èìååòñÿ êàê ìèíèìóì ïî îäíîìóìàêñèìàëüíîìó è ìèíèìàëüíîìó ýëåìåíòó.13 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ×.ó. ìíîæåñòâî h { 1, . . .

, 18}, | i16[[ 12 [[ 8[[96 [4' 15 [AA '10''' 14'''['A''[[''[A'''AA'A''13' ''3 hh 11 2 [57' 17Ahhhh [''A'hhhh[ AA'A'''hh 'A A''1181 íàèìåíüøèé ýëåìåíò, • ìàêñèìàëüíûå.14 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÐàíæèðîâàííûå ÷.ó. ìíîæåñòâàÖåïíîå óñëîâèå Æîðäàíà-ÄåäåêèíäàÂñå ìàêñèìàëüíûå öåïè ìåæäó ëþáûìè äâóìÿ ñðàâíèìûìèýëåìåíòàìè ýëåìåíòàìè ëîêàëüíî êîíå÷íîãî ÷.ó. ìíîæåñòâàèìåþò îäèíàêîâóþ äëèíó.Åñëè ÷.ó.

ìíîæåñòâî óäîâëåòâîðÿåò óñëîâèþÆîðäàíà-Äåäåêèíäà è èìååò íàèìåíüøèé ýëåìåíò 0, òî îíîðàíæèðóåìî, ò.å. íà í¼ì ìîæíî îïðåäåëèòü ôóíêöèþ ðàíãà ρ:12ρ(0) = 0;a l b ⇒ ρ(b) = ρ(a) + 1è òàêîå ìíîæåñòâî èìååòñëîè.Åñëè ìíîæåñòâî ðàíæèðóåìî, òî ëþáîéåãî ñëîé (íî íå òîëüêî!) ÿâëÿåòñÿ àíòèöåïüþ.15 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÏîðÿäêîâûå ãîìîìîðôèçìûÎïðåäåëåíèåÎòîáðàæåíèå ϕ : P → Pñîîòâåòñòâåííî0íîñèòåëåé ÷.ó.

ìíîæåñòâ íàçûâàåòñÿ(ìîíîòîííûì, ïîðÿäêîâûì ãîìîìîðôèçìîì),åñëè x 6 y ⇒ ϕ(x) 6 ϕ(y);îáðàòíî èçîòîííûì, åñëè ϕ(x) 6 ϕ(y) ⇒ x 6 y ;àíòèèçîòîííûì, åñëè x 6 y ⇒ ϕ(x) > ϕ(y).èçîòîííûìÅñëè ϕ èçîòîííî, îáðàòíî èçîòîííî è èíúåêòèâíî, òî ýòîϕ0âëîæåíèå èëè (ïîðÿäêîâûé) ìîíîìîðôèçì ( P ,→ P ).Ñþðúåêòèâíûé ìîíîìîðôèçì (ïîðÿäêîâûé) èçîìîðôèçìϕ(P ∼= P 0 èëè P ∼= P 0 ).Èçîìîðôèçì ÷.ó. ìíîæåñòâà â ñåáÿ àâòîìîðôèçì.(ïîðÿäêîâûé)16 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà17 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó.

ìíîæåñòâÈäåàëû è ôèëüòðû ÷.ó. ìíîæåñòâÎïðåäåëåíèåÏîäìíîæåñòâî J ýëåìåíòîâ ÷.ó. ìíîæåñòâà h P, 6 iíàçûâàåòñÿ åãî (ïîðÿäêîâûì) èäåàëîì, åñëè(x ∈ J) N (y 6 x) ⇒ y ∈ J.Ïîäìíîæåñòâî F ýëåìåíòîâ P íàçûâàåòñÿ åãîôèëüòðîì, åñëè(ïîðÿäêîâûì)(x ∈ F ) N (x 6 y) ⇒ y ∈ F .∅ è âñ¼ ÷.ó. ìíîæåñòâî P èäåàëû.íåñîáñòâåííûåïîðÿäêîâûåÂàæíîå ñâîéñòâî: îáúåäèíåíèå è ïåðåñå÷åíèå ïîðÿäêîâûõèäåàëîâ åñòü ïîðÿäêîâûé èäåàë.Îáîçíà÷åíèå: J(P ) ìíîæåñòâî âñåõ ïîðÿäêîâûõ èäåàëîâ ÷.ó.ìíîæåñòâà P .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà18 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÊîíóñûÎïðåäåëåíèåÏóñòü h P, 6 i ÷.ó.

ìíîæåñòâî è A ⊆ P . Ìíîæåñòâà AM è AOAM = x ∈ P | ∀ a ( a 6 x) è AO = x ∈ P | ∀ a ( x 6 a)AAíàçûâàþòñÿ âåðõíèì è íèæíèì êîíóñàìè ìíîæåñòâà A, à èõýëåìåíòû âåðõíèìè è íèæíèìè ãðàíÿìè ìíîæåñòâà Añîîòâåòñòâåííî.Äëÿ îäíîýëåìåíòíîãî ìíîæåñòâà A = {a} aM è aO .Ïîíÿòíî, ÷òî åñëè a 6 b, òî aM ∩ bO = [ a, b ].xO = hxi = J(x) èäåàë, à xM ôèëüòð P ;òàêèå èäåàëû è ôèëüòðû íàçûâàþò ãëàâíûìè.Êîíå÷íîïîðîæä¼ííûé èäåàë:k[defh a1 , . .

. , ak i =ai O , ai aj , i 6= j .i=1ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÊîíóñû: ïðèìåð16Âåðõíèé è íèæíèé êîíóñûìíîæåñòâà { 2, 3 }[[ 12 [[ 8[[96 [4' 15 [AA '10''' 14'''['A''[[''A['''A''''A''A''133 hh 11 2 [5717'Ahhhh [''Ahhhh[ AA'A''''hh 'A'A''11819 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà20 / 85Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÈäåàëû: ïðèìåð16Èäåàë h 6, 15 i[[ 12 [[ 8[[96 [4' 15 [AA '10''' 14'''[A''[['''A[''A'' ''A''A''133 hh 11 2 [5717'Ahhhh [''Ahhhh[ AA'A''''hh A''A''118ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.

×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâÒî÷íûå ãðàíèÎïðåäåëåíèåÏóñòü h P, 6 i ÷.ó. ìíîæåñòâî è A ⊆ P .Íàèìåíüøèé ýëåìåíò â AM íàçûâàåòñÿ òî÷íîé âåðõíåéãðàíüþ ìíîæåñòâà A (ñèìâîëè÷åñêè sup A).Íàèáîëüøèé ýëåìåíò â AO íàçûâàåòñÿ òî÷íîé íèæíåéãðàíüþ ìíîæåñòâà A (ñèìâîëè÷åñêè inf A).Ïðèìåð ( sup A è/èëè inf A ìîãóò è íå ñóùåñòâîâàòü){a, b}M = {c, d}, íî ìíîæåñòâî {c, d}íå èìååò èíôèìóìà ⇒ sup{a, b} îòñóòñòâóåò.Àíàëîãè÷íî, îòñóòñòâóåò inf{c, d}.21 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.