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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

Q ⊆ P dim(h Q, v|
Q
i) 6 dim(h P, v i)
dim(P ) 6
|P |
2
|P | > 4
dim(P + Q) = max{ dim(P ), dim(Q) }
dim(P + Q) = 2
dim(P × Q) 6 dim(P ) + dim(Q) dim(2
n
) = n
n > 3 S
n
2n S
n
= A ∪ B A = { a
1
, . . . , a
n
}
B = { b
1
, . . . , b
n
} v S
n
a
i
∈ A b
i
∈ B a
i
v b
j
i 6= j i, j = 1, . . . , n v
S
5
b
1
b
2
b
3
b
4
b
5
a
1
a
2
a
3
a
4
a
5
S
5
P d d > 2
dim(P ) = d dim(P
0
) < d P
0
⊂ P
S
n
n > 3
n
d
d > 2
d n d > 4
n − d
P
P
66                                                  Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


     ˆ åñëè Q ⊆ P , òî dim(h Q, v|Q i) 6 dim(h P, v i)                         (ìîíîòîííîñòü ðàçìåðíîñòè ïî
       ìîùíîñòè ìíîæåñòâà);
     ˆ ïðè óäàëåíèè èç ÷.ó. ìíîæåñòâà îäíîãî ýëåìåíòà, ðàçìåðíîñòü åãî óìåíüøàåòñÿ íå
       áîëåå, ÷åì íà 1;
                  |P |
     ˆ dim(P ) 6        ïðè |P | > 4;
                   2
     ˆ dim(P + Q) = max{ dim(P ), dim(Q) }, åñëè õîòÿ áû îäíî èç ìíîæåñòâ íå ÿâëÿåòñÿ
       öåïüþ è dim(P + Q) = 2, èíà÷å;
     ˆ dim(P × Q) 6 dim(P ) + dim(Q), ïðè÷¼ì dim(2n ) = n.

   Ñòàíäàðòíûì ïðèìåðîì ÷.ó. ìíîæåñòâà ðàçìåðíîñòè n > 3 ÿâëÿåòñÿ êîðîíà Sn .
Ýòî 2n -ýëåìåíòíîå äâóäîëüíîå ÷.ó. ìíîæåñòâî, ò.å. Sn = A ∪ B , A = { a1 , . . . , an },
B = { b1 , . . . , bn }. Ïîðÿäîê v íà Sn çàäà¼òñÿ ñëåäóþùèì îáðàçîì: äëÿ ýëåìåíòîâ
ai ∈ A è bi ∈ B ai v bj , åñëè òîëüêî i 6= j , i, j = 1, . . . , n (è v ðåôëåêñèâíî).
Íà ðèñ. 3.14 èçîáðàæåíà êîðîíà S5 .


                             b1    '' b2 4['' b3 4[[ b4 4A[A b5
                                  4[
                                   4 [h''4 [h'['[4 [Ah [                A[4 h
                                     4 h [ '4 h[[ A'4Ah[[ 4 h
                                   hhh444[[A[h[hA[['A44'[A'[h[h[['44''h[h [44
                                            h4 [ h4 [ h4
                                        A[A [ '' ''
                               h[A[ h[[ h                          h
                             a1     a    a  2            3         a4          a5


                                      Ðèñ. 3.14: Êîðîíà S5

   ×.ó. ìíîæåñòâî P íàçûâàåòñÿ d-íåïðèâîäèìûì äëÿ íåêîòîðîãî d > 2, åñëè
dim(P ) = d è dim(P 0 ) < d äëÿ ëþáîãî ñîáñòâåííîãî ÷.ó. ïîäìíîæåñòâà P 0 ⊂ P .
Åäèíñòâåííîå 2-íåïðèâîäèìîå ìíîæåñòâî åñòü äâóõýëåìåíòíàÿ àíòèöåïü. ×.ó. ìíîæåñòâà,
ïðåäñòàâëåííûå íà ðèñ. 3.13 ÿâëÿþòñÿ 3-íåïðèâîäèìûìè (îíè äàëåêî íå èñ÷åðïûâàþò
âñåõ 3-íåïðèâîäèìûõ ìíîæåñòâ, êîòîðûå ïîëíîñòüþ îïèñàíû). Âñå êîðîíû Sn ( n > 3)
n-íåïðèâîäèìû.

Óòâåðæäåíèå 3.2. Åñëè ÷.ó. ìíîæåñòâî ÿâëÿåòñÿ d-íåïðèâîäèìûì äëÿ íåêîòîðîãî
d > 2, òî îíî íåðàçëîæèìî â ëåêñèêîãðàôè÷åñêóþ ñóììó.

   Çàìåòèì, ÷òî âàæíàÿ äëÿ ïðèëîæåíèé çàäà÷à íàõîæäåíèÿ íàèáîëüøåãî çíà÷åíèÿ
ìîùíîñòè Ïàðåòî d-íåñâîäèìîãî ÷.ó. ìíîæåñòâà ñ ÷èñëîì ýëåìåíòîâ n ïðè d > 4 ÿâëÿ-
åòñÿ îòêðûòîé ïðîáëåìîé. Ïîêàçàíî òîëüêî, ÷òî äàííîå ÷èñëî íå ïðåâîñõîäèò n − d.


3.4 Âïîëíå óïîðÿäî÷åííûå ìíîæåñòâà è ñìåæíûå âîïðîñû
     Â õîäå èññëåäîâàíèé ÷.ó. ìíîæåñòâ áûëè ñôîðìóëèðîâàíû ñëåäóþùèå óòâåðæäåíèÿ.

Ëåììà Êóðàòîâñêîãî-Öîðíà. Åñëè â ÷.ó. ìíîæåñòâå P âñå öåïè èìååò âåðõíèå ãðàíè,
    òî êàæäûé ýëåìåíò èç P ñîäåðæèòñÿ â íåêîòîðîì ìàêñèìàëüíîì.
Ïðèíöèï Õàóñäîðôà. Âñÿêàÿ öåïü ÷.ó. ìíîæåñòâà ìîæåò áûòü âëîæåíà â íåêîòîðóþ
    ìàêñèìàëüíóþ öåïü.

Страницы