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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

h P, v
P
i
p h Q
p
, v
p
i
Q
p
P F
P
P
Q
p
F = { h Q
p
, v
p
i | p ∈ P } h P, v
P
i
h R, v
R
i R = { (p, q) | p ∈ P, q ∈ Q
p
}
(p, q) v
R
(p
0
, q
0
) p @
P
p
0
p = p
0
q v
p
q
0
P
P
Q
p
P
P
x ∈ P Q
x
Q
x
Q
y
x y P
P = { a, b, c } F = { Q
a
, Q
b
, Q
c
}
P
F P
b
u v
y
by
a c w x z
bx
au av cz
aw
P
Q
a
Q
b
Q
c
X
P
Q
p
P F = {Q
a
, Q
b
, Q
c
}
P
P
P
Q
p
P
P
Q
p
P
F
P
P
Q
p
Q P
h P, v
P
i h Q, v
Q
i
P × Q
v (p, q) v (p
0
, q
0
) p v
P
p
0
q v
Q
q
0
60                                          Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


Ëåêñèêîãðàôè÷åñêàÿ ñóììà (ïîäñòàíîâêà ÷.ó. ìíîæåñòâ). Ïóñòü h P, vP i 
÷.ó. ìíîæåñòâî, êàæäîìó ýëåìåíòó p êîòîðîãî ñîïîñòàâëåíî ÷.ó. ìíîæåñòâî h Qp , vp i.
Ñåìåéñòâî âñåõ ÷.ó. ìíîæåñòâ Qp , èíäåêñèðîâàííûõ ýëåìåíòàìè P , îáîçíà÷èì F .
                                         P
    Ëåêñèêîãðàôè÷åñêîé     ñóììîé            P Qp      ñåìåéñòâà        ÷.ó.      ìíîæåñòâ
F = { h Qp , vp i | p ∈ P } íàä ÷.ó. ìíîæåñòâîì h P, vP i íàçûâàåòñÿ ÷.ó. ìíî-
æåñòâî h R, vR i, ñ íîñèòåëåì R = { (p, q) | p ∈ P, q ∈ Qp } è ïîðÿäêîì íà í¼ì,
çàäàâàåìûì ñîîòíîøåíèåì (p, q) vR (p 0 , q 0 ), åñëè ëèáî p @P p 0 , ëèáî p = p 0 è q vp q 0 .
                                                                          P
    Äëÿ òîãî, ÷òîáû ïîëó÷èòü äèàãðàììó ëåêñèêîãðàôè÷åñêîé ñóììû              P Qp

     1) ñòðîÿò äèàãðàììó ÷.ó. ìíîæåñòâà P ;
     2) îòáðàñûâàþò îòðåçêè ìåæäó ýëåìåíòàìè P ;
     3) çàìåíÿþò êàæäûé ýëåìåíò x ∈ P äèàãðàììîé Qx ;
     4) ñîåäèíÿþò îòðåçêàìè âñå ìàêñèìàëüíûå ýëåìåíòû Qx ñî âñåìè ìèíèìàëüíûìè ýëå-
        ìåíòàìè Qy , åñëè x íåïîñðåäñòâåííî ïðåäøåñòâóåò y â P .

Íà ðèñ. 3.8 ïðèâåäåíû ÷.ó. ìíîæåñòâî P = { a, b, c }, ñåìåéñòâî F = { Qa , Qb , Qc }
÷.ó. ìíîæåñòâ, èíäåñèðîâàííûõ ýëåìåíòàìè P è ëåêñèêîãðàôè÷åñêàÿ ñóììà ñåìåéñòâà
F íàä P .


                  b   [[ u [[ v               y                  by

                        [[   [[
                  a        c        w         x        z         bx   [[
                                                                         [[
                                                          
                                                       au [    av               cz
                                                            [[
                                                             [
                                                                 aw


                                                              X
                 P                 Qa         Qb       Qc             Qp
                                                                 P



Ðèñ. 3.8: ×.ó. ìíîæåñòâî P , ñåìåéñòâî ÷.ó. ìíîæåñòâ
                                              P      F = {Qa , Qb , Qc }, èíäåêñèðîâàííûõ
ýëåìåíòàìè P è ëåêñèêîãðàôè÷åñêàÿ ñóììà P Qp .

                               P
   Ëåêñèêîãðàôè÷åñêàÿ ñóììà      P Qp òðèâèàëüíà, åñëè ÷.ó. ìíîæåñòâî
                                                                  P P èëè âñå ìíî-
æåñòâà ñåìåéñòâà F îäíîýëåìåíòíû. Ïîíÿòíî, ÷òî â ýòîì ñëó÷àå        P Qp èçîìîðôíî
ëèáî Q, ëèáî P . ×.ó. ìíîæåñòâî ðàçëîæèìî â ëåêñèêîãðàôè÷åñêóþ ñóììó, åñëè îíî èçî-
ìîðôíî íåêîòîðîé íåòðèâèàëüíîé ëåêñèêîãðàôè÷åñêîé ñóììå, â ïðîòèâíîì ñëó÷àå îíî
íåðàçëîæèìî â ëåêñèêîãðàôè÷åñêóþ ñóììó.

Ïðÿìîå ïðîèçâåäåíèå. Åñëè h P, vP i è h Q, vQ i  äâà ÷.ó. ìíîæåñòâà, òî èõ ïðÿ-
ìûì èëè äåêàðòîâûì ïðîèçâåäåíèåì íàçûâàåòñÿ ìíîæåñòâî P × Q ñ ÷àñòè÷íûì ïîðÿä-
êîì v òàêèì, ÷òî (p, q) v (p 0 , q 0 ) òîëüêî êîãäà p vP p 0 è q vQ q 0 .

Страницы