Частично упорядоченные множества (1127207), страница 2
Текст из файла (страница 2)
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó. ìíîæåñòâàìèÐàçäåëû1Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ2Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè3Ëèíåàðèçàöèÿ4Çàäà÷è c ðåøåíèÿìè5Ìîäåëè Êðèïêå22 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà23 / 85Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìèÏåðåñå÷åíèåh P, 61 i ∩ h P, 62 i = h P, 61 ∩ 62 i.cbad\bacd=cbadÑâîéñòâà ÷.ó. ìíîæåñòâ ìîãóò íå ñîõðàíÿþòñÿ ïðè ïåðåñå÷åíèè.Íàïðèìåð, ¾áûòü öåïüþ¿: åñëè P öåïü, òîãäà P d òàêæåöåïü, à P ∩ P d òðèâèàëüíî óïîðÿäî÷åííîå ìíîæåñòâî.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèÏðÿìàÿ ñóììàP = h P, 6P i è Q = h Q, 6Q i äâà ÷.ó. ìíîæåñòâà, ïðè÷¼ìP ∩ Q = ∅.P + Q = h P ∪ Q, 6P ∨ 6Q i.Ñïðàâåäëèâû ñîîòíîøåíèÿP +Q ∼= P +R ⇒ Q ∼= Rè(P + Q)d ∼= P d + Rd .nP ïðÿìàÿ ñóììà n ýêçåìïëÿðîâ P,n1 n-ýëåìåíòíàÿ àíòèöåïü.Äèàãðàììà ïðÿìîé ñóììû ñîñòîèò èç äâóõ äèàãðàììñîîòâåòñòâóþùèõ ÷.ó. ìíîæåñòâ, ðàññìàòðèâàåìûõ êàê åäèíàÿäèàãðàììà.×.ó. ìíîæåñòâî, íå ÿâëÿþùååñÿ ïðÿìîé ñóììîé íåêîòîðûõ äâóõäðóãèõ ÷.ó. ìíîæåñòâ, íàçûâàåòñÿ ñâÿçíûì.24 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó.
ìíîæåñòâàìèÏðÿìîå ïðîèçâåäåíèå: îïðåäåëåíèåèëè äåêàðòîâûì ïðîèçâåäåíèåì ÷.ó. ìíîæåñòâP = h P, 6P i è Q = h Q, 6Q i íàçûâàåòñÿ ìíîæåñòâîÏðÿìûìP × Q = h P × Q, 6 i,ãäå (p, q) 6 (p 0 , q 0 ) ⇔ (p 6P p 0 )N(q 6Q q 0 ).Pn ïðÿìîå ïðîèçâåäåíèå n ýêçåìïëÿðîâ P: B n = 2n .Åñëè P , Q ðàíæèðîâàíû è èõ ðàíãîâûå ôóíêöèè ñóòü ρP è ρQ ,òî P × Q òàêæå ðàíæèðîâàíî è ρ(x1 , x2 ) = ρP (x1 ) + ρQ (x2 );∼ Q×PÑïðàâåäëèâû ñîîòíîøåíèÿ P × Q =P ×R ∼= Q×R ⇒ P ∼= Q,Pn ∼= Qn ⇒ P ∼= Q.25 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà26 / 85Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìèÏðÿìîå ïðîèçâåäåíèå: ïðèìåð 1[[[(c, 1)cba×10=(b, 1)[[[[[[(a, 1)(a, 0)Ïðÿìîå ïðîèçâåäåíèå öåïåé 3 è 2(b, 0)(c, 0)ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó. ìíîæåñòâàìèÏðÿìîå ïðîèçâåäåíèå: ïðèìåð 2[[◦◦◦◦[[◦◦◦Çèãçàãè (èëè çàáîðû) Z3 è Z4◦ [AA ◦ AAA AAA [[ AAAA ◦ AA ◦ ◦ ◦ ◦◦ [[[AAAA AAAA [[[ AA AAAA◦◦◦◦Ïðÿìîå ïðîèçâåäåíèå Z3 × Z427 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàÎïåðàöèè íàä ÷.ó. ìíîæåñòâàìèÒåîðåìà ÎðåÒåîðåìàÊàæäûé ÷àñòè÷íûé ïîðÿäîê èçîìîðôåí íåêîòîðîìóïîäìíîæåñòâó äåêàðòîâà ïðîèçâåäåíèÿ öåïåé.ÎïðåäåëåíèåÌóëüòèïëèêàòèâíîé ðàçìåðíîñòüþ ÷.ó. ìíîæåñòâà Píàçûâàåòñÿ íàèìåíüøåå ÷èñëî k ëèíåéíûõ ïîðÿäêîâ Li òàêèõ,ñóùåñòâóåò âëîæåíèå P ,→ L1 × .
. . × Lk .28 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿÐàçäåëû1Îñíîâíûå ïîíÿòèÿ òåîðèè ÷.ó. ìíîæåñòâ2Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè3Ëèíåàðèçàöèÿ4Çàäà÷è c ðåøåíèÿìè5Ìîäåëè Êðèïêå29 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿÏðèíöèï ïðîäîëæåíèÿ ïîðÿäêàÒåîðåìà (Øïèëüðàéíà)1Ëþáîé ÷àñòè÷íûé ïîðÿäîê ìîæåò áûòü ïðîäîëæåí äîëèíåéíîãî íà òîì æå ìíîæåñòâå.2Êàæäûé ïîðÿäîê åñòü ïåðåñå÷åíèå âñåõ ñâîèõ ëèíåéíûõïðîäîëæåíèé (ëèíåàðèçàöèé).P → L,P = L1 ∩ .
. . ∩ Le(P) ,ãäå e(P) ÷èñëî âñåõ ëèíåàðèçàöèé ÷.ó. ìíîæåñòâà P.Äîêàçàòåëüñòâî (äëÿ êîíå÷íîãî ñëó÷àÿ, |P | = n)1ÅñëèP íå öåïü, òî âPíàéäóòñÿ íåñðàâíèìûå ýëåìåíòû;ïðîèçâîëüíî îïðåäåëèì ïîðÿäîê íà íèõ è ïðîäîëæèì åãî ïîòðàíçèòèâíîñòè. Åñëè ïîëó÷èâøèåñÿ ÷.ó. ìíîæåñòâî åù¼ íåöåïü, òî âûáåðåì íîâóþ ïàðó íåñðàâíèìûõ ýëåìåíòîâ èïîñòóïàåì, êàê óêàçàíî âûøå.×åðåç êîíå÷íîå ÷èñëî øàãîâ ïîëó÷àåì ëèíåéíûé ïîðÿäîê.30 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà31 / 85ËèíåàðèçàöèÿÏðèíöèï ïðîäîëæåíèÿ ïîðÿäêà...Äîêàçàòåëüñòâî (ïðîäîëæåíèå)1Ò.ê.
âîçìîæåí ðàçëè÷íûé âûáîð ïàð íåñðàâíèìûõ ýëåìåíòîâè ïðè êàæäîì âûáîðå ìîæíî ïîëàãàòü ëþáîé èõ ïîðÿäîê, òîìîæíî ïîëó÷èòü âñå âîçìîæíûå ëèíåéíûå ïðîäîëæåíèÿèñõîäíîãî ÷àñòè÷íîãî ïîðÿäêà.2Ïåðåñå÷åíèå âñåõ òàêèõ öåïåé äàñò èñõîäíîå ÷.ó. ìíîæåñòâî:åñëèx 6 y,òî àíàëîãè÷íîå ñëåäîâàíèå áóäåò è âî âñåõïîëó÷åííûõ ëèíåéíûõ ïîðÿäêàõ, à ïðèxyâñåãäà íàéä¼òñÿïàðà öåïåé ñ ïðîòèâîïîëîæíûì èõ ñëåäîâàíèåì, ÷òî âïåðåñå÷åíèè öåïåé è äàñò íåñðàâíèìîñòü ýòèõ ýëåìåíòîâ.Äëÿ êîíå÷íûõ ÷.ó.
ìíîæåñòâ çàäàííûõ ïàðàìè âèäà a l b, ïîèñêòàêîãî ëèíåéíîãî ïðîäîëæåíèÿ â òåîðåòè÷åñêîìïðîãðàììèðîâàíèè íàçûâàþò òîïîëîãè÷åñêîé ñîðòèðîâêîé.Çàäà÷à ðåøàåòñÿ çà ëèíåéíîå âðåìÿ.ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà32 / 85ËèíåàðèçàöèÿËèíåéíûå ïðîäîëæåíèÿ ÷.ó. ìíîæåñòâ: ïðèìåðû...bacPbbcacbcaae(P) = 3ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà33 / 85ËèíåàðèçàöèÿËèíåéíûå ïðîäîëæåíèÿ ÷.ó. ìíîæåñòâ: ïðèìåðû...c[[ d[abPdcdccdcdbbaaaabbe(P) = 5?ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà34 / 85ËèíåàðèçàöèÿËèíåéíûå ïðîäîëæåíèÿ ÷.ó. ìíîæåñòâ: ïðèìåðû...c[[ d[abPdcdcccdcdabbaadaabbbe(P) = 5ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà35 / 85ËèíåàðèçàöèÿÏðåäñòàâëåíèå ÷.ó. ìíîæåñòâà ïåðåñå÷åíèåì öåïåécd[[[ ba=dccdba∩baÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà36 / 85ËèíåàðèçàöèÿÍåêîòîðûå ÷.ó. ìíîæåñòâà◦◦...◦hhhh◦hhhh . . .hhh◦◦Ìàëàÿ êîðîíà sn['['hb 4[4'['hb 4[4 [[hb 4A4 [Ahb'4h'['[A4 Ah [A[4 h4 h ['hh44 [[[h'hA4[4'A'[A[[h'h4[4''[hh44h[A[A[4AhA[[[[[4 h'['[4h'['[4aaaaab144123452345Êîðîíà S5ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà37 / 85Ëèíåàðèçàöèÿ¾e(P)= ?¿ NP-ïîëíàÿ çàäà÷à, íî:n+me(P + Q) =e(P)e(Q),n 12ne(2 × n) = ÷èñëàn+1 nX e(Zn ) xnn>0n!çíà÷åíèÿ Zn ïðè ÷¼òíûõ n ÷èñëà òàíãåíñà;e(Sn ) = (n + 1)!(n − 1)! ;n = |P|, m = |Q|;Êàòàëàíà;= tg x + sec x ,÷èñëà ñåêàíñà,à ïðè íå÷¼òíûõ X e(sn )xxn =;n!cos2 xn>1log(e(B n ))n3= log− log e + o(1) .n2bn/2c2ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà38 / 85ËèíåàðèçàöèÿÂåðîÿòíîñòíîå ïðîñòðàíñòâî íà ëèíåàðåçàöèÿõÏðè äèñêðåòíûõ çàäà÷ ÷àñòî ðàññìàòðèâàþò ñâÿçàííîå ñ ÷.ó.ìíîæåñòâîì P âåðîÿòíîñòíîå ïðîñòðàíñòâî íà ìíîæåñòâå âñåõe(P ) åãî ëèíåàðèçàöèé, â êîòîðîì êàæäàÿ ëèíåàðèçàöèÿðàâíîâåðîÿòíà. ýòîì ïðîñòðàíñòâå äëÿ ýëåìåíòîâ x, y, z, .
. . ÷.ó. ìíîæåñòâàP ðàññìàòðèâàþò ñîáûòèÿ E âèäà x 6 y , (x 6 y) N (x 6 z) èò.ä.Âåðîÿòíîñòü Pr [E] òàêîãî ñîáûòèÿ:Pr [E] =÷èñëî ëèíåàðèçàöèé, â êîòîðûõ èìååò ìåñòîe(P)E.Òåîðåìà (XYZ-òåîðåìà)Ïóñòüh P, 6 i ÷.ó. ìíîæåñòâî èx, y, z ∈ P .ÒîãäàPr [ x 6 y ] · Pr [ x 6 z ] 6 Pr [ (x 6 y) N (x 6 z) ] .ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿÏðîáëåìà ñîðòèðîâêè è ¾1/3 2/3 ïðåäïîëîæåíèå¿ îïðåäåëèòü ëèíåéíûé ïîðÿäê L ñ ïîìîùüþ ìèíèìàëüíîãîêîëè÷åñòâà âîïðîñîâ ¾âåðíî ëè, ÷òî x < y â L?¿.Îáîáùåíèå: L çàôèêñèðîâàííàÿ, íî íåèçâåñòíàÿëèíåàðèçàöèÿ ÷.ó. ìíîæåñòâà P.Îïòèìàëüíàÿ ïðîöåäóðà ïîèñêà L âêëþ÷àåò â ñåáÿ íàõîæäåíèåýëåìåíòîâ x è y , äëÿ êîòîðûõ Pr [ x < y ] ≈ 12 .Ñ.Ñ. Êèñëèöûí (1968) âûñêàçàë ¾1/3 2/3 ïðåäïîëîæåíèå¿: ëþáîå íå ÿâëÿþùååñÿ öåïüþ ÷.ó.
ìíîæåñòâî ñîäåðæèò ïàðóíåñðàâíèìûõ ýëåìåíòîâ x è y , äëÿ êîòîðûõ126 Pr [ x 6 y ] 6”.33Ïîçäíåå ýòî óòâåðæäåíèå íåçàâèñèìî âûäâèíóëè àìåðèêàíñêèåèññëåäîâàòåëè Ì. Ôðåäìàí è Í. Ëèíàë.39 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿ1/3 2/3 ïðåäïîëîæåíèåÏðèìåð 2 + 1 ïîêàçûâàåò,÷òî óêàçàííûå ãðàíèöûíåñóæàåìû (èìååòñÿ è ïðèìåðäåñÿòèýëåìåíòíîãî ÷.ó. ìíîæåñòâàñî ñâÿçàííîé äèàãðàììîé Õàññå).Äàííîå ïðåäïîëîæåíèå äî ñèõ ïîð óñïåøíî ïðîòèâîñòîèò âñåìïîïûòêàì åãî äîêàçàòü è ïðåäñòàâëÿåò ñîáîé îäíó èç íàèáîëååèíòðèãóþùèõ ïðîáëåì êîìáèíàòîðíîé òåîðèè ÷.ó.
ìíîæåñòâ(Ñ. Ôåëñíåð è Ó.Ò. Òðîòòåð).Íà ñåãîäíÿøíèé äåíü íàèáîëåå ñèëüíûé ðåçóëüòàò:√√5+ 55− 56 Pr[x 6 y] 6≈ 0, 7236 .0, 2764 ≈101040 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿ×.ó. ìíîæåñòâà: ñïåêòðÎïðåäåëåíèå:Spec (P) = { Pr [ a 6 b ] | a, b ∈ P }ßñíî, ÷òîïîñêîëüêó Pr [ a 6 b ] = 1 − Pr [ b 6 a ], ñïåêòðñèììåòðè÷åí îòíîñèòåëüíî 12 ;äëÿ âñåõ íåîäíîýëåìåíòíûõòðèâèàëüíî óïîðÿäî÷åííûõ1ìíîæåñòâ Spec = 2 ; 1 0, 2 , 1 åäèíñòâåííûé òð¼õýëåìåíòíûé ñïåêòð;âñå ÷åòûð¼õýëåìåíòíûå ñïåêòðû äîëæíû èìåòü âèä{ 0, α, 1 − α, 1 }, ãäå 0 < α < 21 ;Ãèïîòåçà (2002): α = 13 .41 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿ×.ó.
ìíîæåñòâà: ðàçìåðíîñòüÏî òåîðåìå Øïèëüðàéíà ÷.ó. ìíîæåñòâî P ñîâïàäàåò ñïåðåñå÷åíèåì âñåõ e(P) ñâîèõ ëèíåàðèçàöèé, íî òîò æåðåçóëüòàò ìîæíî ïîëó÷èòü, âçÿâ çíà÷èòåëüíî ìåíüøåå ÷èñëîëèíåéíûõ ïðîäîëæåíèé.Íàïðèìåð, ÷.ó. ìíîæåñòâî Pbd[[ c[ aèìååò 6 ëèíåàðèçàöèé, íî P = [ a, b, c, d ] ∩ [ a, d, c, b ].Ïóñòü P ÷.ó. ìíîæåñòâî è R = { L1 , . . . , Lk } ñîâîêóïíîñòü öåïåé òàêàÿ, ÷òî P = L1 ∩ . . . ∩ Lk , òî ãîâîðÿò,÷òî R ðåàëèçóåò P.42 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ.
×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà43 / 85Ëèíåàðèçàöèÿ×.ó. ìíîæåñòâà: ðàçìåðíîñòü...ÎïðåäåëåíèåÍàèìåíüøåå ÷èñëî ëèíåéíûõ ïîðÿäêîâ, äàþùèõ â ïåðåñå÷åíèè äàííîå÷.ó. ìíîæåñòâî P íàçûâàåòñÿ åãî (ïîðÿäêîâîé) ðàçìåðíîñòüþ(ñèìâîëè÷åñêè dim(P )).Òåîðåìà (Îðå)Ïîðÿäêîâàÿ è ìóëüòèïëèêàòèâíàÿ ðàçìåðíîñòè ÷.ó. ìíîæåñòâàñîâïàäàþò.[ 1, 2, 3, 4, 5 ] ∩ [ 2, 4, 1, 3, 5 ]: [ a, b, c ] × [ d, e ]ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâàËèíåàðèçàöèÿdim(P) áîëåå òîíêàÿ îöåíêà ÷.ó. ìíîæåñòâà, ÷åì e(P)Ðàçìåðíîñòü ...
èìåþò:1 òîëüêî öåïè;2 òðèâèàëüíî óïîðÿäî÷åííûå ìíîæåñòâà(ò.å. ðàçìåðíîñòü íå ìîæåò èíòåðïðåòèðîâàòüñÿ êàê ìåðàîòëè÷èÿ äàííîãî ÷.ó. ìíîæåñòâà îò ëèíåéíîãî); Zn ; âñå îòëè÷íûå îò öåïåé ÷.ó. ìíîæåñòâ, ïðè |P | 6 6, êðîìå3 s3 , sh è shd (ñì. äèàãðàììû) :n Sn .44 / 85ÏÐÈÊËÀÄÍÀß ÀËÃÅÁÐÀ. ×àñòü IV: ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà45 / 85ËèíåàðèçàöèÿÎ ðàçìåðíîñòè ÷.ó.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
