Лекции по упорядоченным множествам и универсальной алгебре. Гуров С.И. - 51 стр.

UptoLike

ВУЗ: 

МГУ | Москва

Составители: 

Рубрика: 

◦
◦
. . .
◦ ◦
. . .
2
◦ ◦ ◦
. . .
1
◦ ◦ ◦ ◦
0
◦
a) b)
6 P
P
h P, 6 i
< n
n v
1
< . . . < v
n
[ v
1
, . . . , v
n
]
n n − 1
h N, | i M ⊆ N
{ 2
n
| n ∈ M } M = N
P n h(P ) = n
P n + 1
v h(v)
[ v
0
, . . . , v ] v
A P
3.1. Ïðåäïîðÿäêè è ïîðÿäêè                                                              51




                                                        hh [[
                                                        ◦

                                                      h       [
                                                 hhh              ◦

                                               h
                     ...
                                             hh         ◦         ◦   ...
                                          hh
                      2
                                       hhh   ◦          ◦         ◦   ...

                                     hh
                                   hh
                      1        ◦             ◦   [[     ◦
                                                            A A   ◦

                                                   [ AAA A
                                                     AA
                      0                                 ◦


                     a)                                 b)


                 Ðèñ. 3.3: Äèàãðàììû Õàññå áåñêîíå÷íûõ ÷.ó. ìíîæåñòâ

ýëåìåíò åñòü îäíîâðåìåííî è åäèíñòâåííûé ìàêñèìàëüíûé [ ìèíèìàëüíûé ]. Ñ äðóãîé
ñòîðîíû, ìàêñèìàëüíûõ èëè ìèíèìàëüíûõ ýëåìåíòîâ ìîæåò áûòü íåñêîëüêî, à ìîæåò è
íå áûòü ñîâñåì. Íàïðèìåð, ÷.ó. ìíîæåñòâî, èçîáðàæ¼ííîå íà ðèñ. 3.4 èìååò îäèí íàè-
ìåíüøèé (îí æå ìèíèìàëüíûé) è 3 ìàêñèìàëüíûõ ýëåìåíòà. Çàìåòèì, ÷òî â ïðèëîæåíèÿõ
ñîâîêóïíîñòü ìàêñèìàëüíûõ ýëåìåíòîâ ÷.ó. ìíîæåñòâà íàçûâàþò ìíîæåñòâîì Ïàðåòî.

Îïðåäåëåíèå 3.5. ×àñòè÷íûé ïîðÿäîê 6 íà íååäèíè÷íîì ìíîæåñòâå P íàçûâàåòñÿ
ëèíåéíûì, åñëè ëþáûå äâà ýëåìåíòà èç P ñðàâíèìû.  ýòîì ñëó÷àå ÷.ó. ìíîæåñòâî
h P, 6 i íàçûâàåòñÿ ëèíåéíî óïîðÿäî÷åííûì èëè öåïüþ.

   Äëÿ ñòðîãîãî ëèíåéíîãî ïîðÿäêà áóäåì îáû÷íî ïîëüçîâàòüñÿ îáîçíà÷åíèåì < . n-
ýëåìåíòíàÿ öåïü îáîçíà÷àåòñÿ n èëè, ïðè v1 < . . . < vn ,  [ v1 , . . . , vn ]. Äëèíà öåïè
n åñòü íàòóðàëüíîå ÷èñëî n − 1.
   Âñå íåòðèâèàëüíûå ÷.ó. ìíîæåñòâà ñîäåðæàò öåïè â êà÷åñòâå ïîäìíîæåñòâ (öåïÿìè
íàçûâàþò òàêæå ëèíåéíî óïîðÿäî÷åííûå ïîäìíîæåñòâà ÷.ó. ìíîæåñòâ). Öåïü â ÷.ó. ìíî-
æåñòâå íàçûâàåòñÿ ìàêñèìàëüíîé, åñëè å¼ îáúåäèíåíèå ñ ëþáûì íå ïðèíàäëåæàùèì åé
ýëåìåíòîì öåïüþ íå ÿâëÿåòñÿ. Â ÷.ó. ìíîæåñòâå h N, | i äëÿ ëþáîãî M ⊆ N öåïüþ ÿâëÿ-
åòñÿ, íàïðèìåð, ïîäìíîæåñòâî { 2n | n ∈ M }; ïðè M = N èìååì ìàêñèìàëüíóþ öåïü.
   Ãîâîðÿò, ÷òî âûñîòà ÷.ó. ìíîæåñòâà P ðàâíà n (ñèìâîëè÷åñêè h(P ) = n ) åñëè â
P ñóùåñòâóåò öåïü, ñîäåðæàùàÿ n + 1 ýëåìåíò, è íåò öåïåé, ñîäåðæàùèõ áîëüøåå ÷èñ-
ëî ýëåìåíòîâ. Âûñîòîé ýëåìåíòà v (ñèìâîëè÷åñêè h(v) ) â êîíå÷íîì óïîðÿäî÷åííîì
ìíîæåñòâå íàçûâàåòñÿ íàèáîëüøàÿ èç äëèí öåïåé [ v0 , . . . , v ], ãäå v  ìèíèìàëüíûé
ýëåìåíò. Ïîíÿòíî, ÷òî âñå ìèíèìàëüíûå ýëåìåíòû èìåþò âûñîòó 0.
   Àíòèöåïü (ñåìåéñòâî Øïåðíåðà ) åñòü íåïóñòîå ïîäìíîæåñòâî A ÷.ó. ìíîæåñòâà P ,
â êîòîðîì ëþáûå äâà ýëåìåíòà èëè ðàâíû, èëè íåñðàâíèìû. Íàïðèìåð, â ÷.ó. ìíîæåñòâå

Страницы