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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

M 6
1
, . . . , 6
n
M
v
x v y ⇔
n
i=1
(x 6
i
y)
x, y ∈ M h M, v i = h M,
n
T
i=1
6
i
i
v
v
P
P
P P
0
⊂ P
P e(P )
P e(n1) = n! e(C) = 1
C e(·)
e(P ⊕ Q) = e(P ) e(Q), e(P + Q) =
µ
m + n
m
e(P ) e(Q)
P Q m n
e(2 × n) =
1
n + 1
µ
2n
n
Z
n
X
n>0
e(Z
n
)x
n
n!
= tg x + sec x ,
e(Z
n
) n
tg x sec x
x
e(P )
P = { v
1
, . . . , v
n
} h P, v i n
R
n
P
P = { (x
1
, . . . , x
n
) ∈ R
n
| 0 6 x
i
6 1, v
i
v v
j
⇒ x
i
6 x
j
} .
e(P ) = n! vol(P) vol (P) P
3.3. Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè. Ðàçìåðíîñòü                                                             63


   Äëÿ ñ÷åòíîãî áåñêîíå÷íîãî óïîðÿäî÷åííîãî ìíîæåñòâà äîêàçàòåëüñòâî ïðîâîäèòñÿ ìå-
òîäîì ìàòåìàòè÷åñêîé èíäóêöèè. Î îáùåì ñëó÷àå äîêàçàòåëüñòâî ïåðâîãî óòâåðæäåíèÿ2
îïèðàåòñÿ íà ëåììó Êóðàòîâñêîãî-Öîðíà (ñì. ï. 3.4).
   Äàëåå â ýòîì ðàçäåëå áóäóò ðàññìàòðèâàòüñÿ òîëüêî êîíå÷íûå ÷.ó. ìíîæåñòâà.
   Ïóñòü M  íåïóñòîå ìíîæåñòâî è 61 , . . . , 6n  ðàçëè÷íûå ëèíåéíûå ïîðÿäêè íà í¼ì
(ðàññìîòðèì äëÿ ïðîñòîòû ñëó÷àé êîíå÷íîãî ÷èñëà ïîðÿäêîâ). Òîãäà íà M îïðåäåë¼í
÷àñòè÷íûé ïîðÿäîê v ïî ïðàâèëó
                                                       n
                                          xvy ⇔       & (x 6i y)
                                                      i=1

                                                                              T
                                                                              n
äëÿ ïðîèçâîëüíûõ x, y ∈ M . Ïîíÿòíî, ÷òî h M, v i = h M,                            6i i.
                                                                              i=1
   Ëèíåéíûé ïîðÿäîê, âêëþ÷àþùèé â ñåáÿ äàííûé ÷àñòè÷íûé ïîðÿäîê v íà íåêîòîðîì
ìíîæåñòâå íàçûâàþò ëèàíåðèçàöèåé èñõîäíîãî ïîðÿäêà v. Èç äîêàçàííîé òåîðåìû ñëå-
äóåò ïðîñòîé àëãîðèòì ïîñòðîåíèÿ íåêîòîðîé ëèàíåðèçàöèè êîíå÷íîãî ÷.ó. ìíîæåñòâà P :
âûäåëÿåì ìíîæåñòâî ìèíèìàëüíûõ ýëåìåíòîâ P è ëèíåéíî óïîðÿäî÷èâàåì åãî ïðîèç-
âîëüíîì îáðàçîì, èñêëþ÷àåì ýòî ìíîæåñòâî èç P , îáðàçóÿ ÷.ó. ïîäìíîæåñòâî P 0 ⊂ P , â
êîòîðîì âíîâü âûäåëÿåì ìèíèìàëüíûå ýëåìåíòû, ëèíåéíî óïîðÿäî÷èâàåì èõ è ò.ä. ×èñëî
âñåâîçìîæíûõ ëèàíåðèçàöèé ÷.ó. ìíîæåñòâà P îáîçíà÷àþò e(P ). Îíî ìîæåò èíòåðïðå-
òèðîâàòüñÿ êàê íåêîòîðàÿ îöåíêà ñëîæíîñòè P . Ïîíÿòíî, ÷òî e(n1) = n! è e(C) = 1
äëÿ öåïè C (î÷åâèäíî, ýòî ìàêñèìàëüíî è ìèíèìàëüíî âîçìîæíûå çíà÷åíèÿ e(·) ). Ëåãêî
ïîêàçûâàåòñÿ ñïðàâåäëèâîñòü ôîðìóë
                                                  µ      ¶
                                                    m+n
                e(P ⊕ Q) = e(P ) e(Q), e(P + Q) =           e(P ) e(Q)
                                                     m

äëÿ ïðîèçâîëüíûõ ÷.ó. ìíîæåñòâ P è Q (äëÿ âòîðîé ôîðìóëû  ìîùíîñòåé m è n
ñîîòâåòñòâåííî). Òàêæå óñòàíîâëåíî, ÷òî
                      µ ¶
                   1    2n
   ˆ e(2 × n) =              ÷èñëà Êàòàëàíà;
                 n+1 n
   ˆ äëÿ çèãçàãîâ Zn ñïðàâåäëèâî ðàçëîæåíèå
                                         X e(Zn )xn
                                                           = tg x + sec x ,                              (3.4)
                                         n>0
                                                 n!

     ïðè ýòîì çíà÷åíèÿ e(Zn ) ïðè ÷¼òíûõ n íàçûâàþò ÷èñëàìè ñåêàíñà, à ïðè íå÷¼ò-
     íûõ  ÷èñëàìè òàíãåíñà (íàïîìíèì, ÷òî êîýôôèöèåíòû ðàçëîæåíèÿ tg x è sec x
     ïî ñòåïåíÿì x îïðåäåëÿþòñÿ ÷åðåç êîìáèíàòîðíûå ÷èñëà Áåðíóëëè è Ýéëåðà ñîîò-
     âåòñòâåííî).

    îáùåì ñëó÷àå âû÷èñëåíèå çíà÷åíèÿ e(P )  ñëîæíàÿ êîìáèíàòîðíàÿ (NP-
ïîëíàÿ) çàäà÷à. Ñóùåñòâóåò, îäíàêî, èíòåðåñíûé ïîäõîä ê å¼ ðåøåíèþ. Ïóñòü
P = { v1 , . . . , vn }  íîñèòåëü ÷.ó. ìíîæåñòâà h P, v i. Â n-ìåðíîì åâêëèäîâîì ïðî-
ñòðàíñòâå Rn îïðåäåëèì ìíîãîãðàííèê P :

                 P = { (x1 , . . . , xn ) ∈ Rn | 0 6 xi 6 1, vi v vj ⇒ xi 6 xj } .

Ïîêàçàíî, ÷òî e(P ) = n! vol(P), ãäå vol(P)  îáú¼ì ìíîãîãðàííèêà P .
  2 B.Dushnik,E.W.Miller.   Partially ordered sets. Amer. J. Math., v. 70, (1948), pp. 507520; ñì. òàêæå [10].

Страницы