Единое окно доступа к образовательным ресурсам

Лекции по упорядоченным множествам и универсальной алгебре: Учебно-методическое пособие

Голосов: 0

В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам pi решёткам. Изучаются свойства модулярных, дистрибутивных решёток и решёток с дополнениями. Указанным разделам посвящены первые главы. В последней главе рассматриваются универсальные алгебры. Вводится понятие алгебраической системы, рассматриваются различные типы таких систем и доказываются основные теоремы об их изоморфизме и гомоморфизме. Вводимые понятия и доказанные утверждения иллюстрируются большим количеством примеров. Пособие предназначено для студентов, изучающих соответствующие разделы алгебры и может быть использовано при самообразовании. Электронная версия пособия размещена на сайте факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова <a href="http://www.cs.msu.su" target="_blank">(www.cs.msu.su)</a>.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    3.1. Ïðåäïîðÿäêè è ïîðÿäêè                                                              51




                                                          h [[
                                                         ◦

                                                       hh      [
                                                  h hh             ◦

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

                                     hh
                                   hh
                                                  [[
                                                           AAAA
                      1        ◦              ◦          ◦         ◦

                                                     [ AA
                                                       A
                                                       A
                      0                                  ◦


                     a)                                  b)


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

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

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

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


52                                           Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


 N, | àíòèöåïüþ ÿâëÿåòñÿ ïðîèçâîëüíîå ïîäìíîæåñòâî ïîïàðíî íåêðàòíûõ ÷èñåë, à â
ìíîæåñòâå 2n ,        ñîâîêóïíîñòè âåðõíèõ íóëåé ëèáî íèæíèõ åäèíèö íåêîòîðîé (íå
òîæäåñòâåííîé êîíñòàíòàì) ìîíîòîííîé áóëåâîé ôóíêöèè. Îäíîýëåìåíòíîå ïîäìíîæå-
ñòâî ÷.ó. ìíîæåñòâà íàçûâàþò òðèâèàëüíîé àíòèöåïüþ.
    Ãîâîðÿò, ÷òî øèðèíà ÷.ó. ìíîæåñòâà P ðàâíà n (ñèìâîëè÷åñêè w(P ) = n ) åñëè â P
ñóùåñòâóåò àíòèöåïü, ñîäåðæàùàÿ n ýëåìåíòîâ, è íåò àíòèöåïåé, ñîäåðæàùèõ áîëüøåå
÷èñëî ýëåìåíòîâ.
    Åñëè êàæäàÿ ìàêñèìàëüíàÿ öåïü â P èìååò îäíó è òó æå äëèíó n, òî ãîâîðÿò, ÷òî
äàííîå ÷.ó. ìíîæåñòâî  ãðàäóèðîâàííîå (ðàíæèðîâàííîå) ðàíãà n.  ýòîì ñëó÷àå ñóùå-
ñòâóåò åäèíñòâåííàÿ ðàíãîâàÿ ôóíêöèÿ ρ : P → { 0, 1, . . . , n } òàêàÿ, ÷òî ρ(x) = 0, åñëè
x  ìèíèìàëüíûé ýëåìåíò P è ρ(y) = ρ(x) + 1, åñëè y íåïîñðåäñòâåííî ñëåäóåò çà
x. Íàïðèìåð, öåïü è áóëåàí, èçîáðàæ¼ííûå íà ðèñ. 3.1, ñóòü ãðàäóèðîâàííûå ìíîæåñòâà
ðàíãà 3, âåñ ïåðâîãî åñòü 1, à âòîðîãî  3. Åñëè ρ(x) = k , òî ãîâîðÿò, ÷òî ýëåìåíò x
èìååò ðàíã k . Ýëåìåíòû îäíîãî ðàíãà îáðàçóþò ñëîé ñîîòâåòñòâóþùåãî ãðàäóèðîâàííîãî
÷.ó. ìíîæåñòâà; ÷èñëî ýëåìåíòîâ â k -ì ñëîå ÷.ó. ìíîæåñòâà P îáîçíà÷èì Wk (P ).
    ßñíî, ÷òî ñëîé ÷.ó. ìíîæåñòâà åñòü àíòèöåïü. Îäíàêî íå âñÿêàÿ àíòèöåïü åñòü ñëîé:
íà ðèñ. 3.4 ïðåäñòàâëåíî ãðàäóèðîâàííîå ÷.ó. ìíîæåñòâî, ó êîòîðîãî ýëåìåíòû ìàêñè-
ìàëüíîé àíòèöåïè, îáîçíà÷åííûå •, íå ïðèíàäëåæàò êàêîìó-òî îäíîìó ñëîþ.


                                •   [[ •          ◦   [[
                                      [                 [
                                         ◦   [[ •    •

                                               [ 
                                                  ◦


             Ðèñ. 3.4: ×.ó. ìíîæåñòâî, íå îáëàäàþùåå ñâîéñòâîì Øïåðíåðà

   Ãîâîðÿò, ÷òî êîíå÷íîå ãðàäóèðîâàííîå ÷.ó. ìíîæåñòâî P îáëàäàåò ñâîéñòâîì Øïåð-
íåðà, åñëè
                                max Wk (P ) = w(P ) .
                                     k

×.ó. ìíîæåñòâî, èçîáðàæ¼ííîå íà ðèñ. 3.4 íå îáëàäàåò ñâîéñòâîì Øïåðíåðà, ò.ê. ó íåãî
max Wk (P ) = 3, à w(P ) = 4. Ïðè ýòîì ÿñíî, ÷òî âñåãäà max Wk (P ) w(P ).
 k                                                           k

Òåîðåìà 3.3.  êîíå÷íîì ÷.ó. ìíîæåñòâå êàæäûé ýëåìåíò ñîäåðæèòñÿ â íåêîòîðîì
ìàêñèìàëüíîì ýëåìåíòå è ñîäåðæèò íåêîòîðûé ìèíèìàëüíûé ýëåìåíò.

Äîêàçàòåëüñòâî. Ïóñòü x  ïðîèçâîëüíûé ýëåìåíò ÷.ó. ìíîæåñòâà P,        . Åñëè x íå
ìàêñèìàëåí, òî íàéä¼òñÿ òàêîé ýëåìåíò x1 ∈ P , ÷òî x     x1 . Ïîâòîðÿÿ ðàññóæäåíèÿ
äëÿ íîâûõ ýëåìåíòîâ, ïîëó÷àåì âîçðàñòàþùóþ öåïü x x1 . . .. Ïîñêîëüêó ìíîæåñòâî
P êîíå÷íî, òî è äàííàÿ öåïü êîíå÷íà. ż ïîñëåäíèé ýëåìåíò xn , ïî îïðåäåëåíèþ áóäåò
ìàêñèìàëüíûì ýëåìåíòîì P è x xn .
   Äëÿ íàõîæäåíèÿ ìèíèìàëüíîãî ýëåìåíòà ðàññóæäåíèÿ àíàëîãè÷íû, ïðè ýòîì ñòðîèò-
ñÿ óáûâàþùàÿ öåïü.

Ïðèìåð 3.5.                                 1
             1. Ðàññìîòðèì ÷.ó. ìíîæåñòâî Nf ,                1
                                                    , ãäå Nf  ìíîæåñòâî åäèíè÷íûõ
    íàáîðîâ ìîíîòîííîé áóëåâîé ôóíêöèè f (x1 , x2 , x3 , x4 , x5 ) = x1 ∨ x2 x3 ∨ x3 x4 x5 .


3.2. Èçîòîííûå îòîáðàæåíèÿ è ïîðÿäêîâûå èäåàëû                                     53

           1
     Äëÿ Nf íèæíèå åäèíèöû (10000), (01100) è (00111) ôóíêöèè f áóäóò ìèíè-
     ìàëüíûìè ýëåìåíòàìè, 1 = (11111)  ìàêñèìàëüíûì è íàèáîëüøèì ýëåìåíòîì, à
                            1
     íàèìåíüøèé ýëåìåíò â Nf îòñóòñòâóåò.
  2. ×.ó. ìíîæåñòâî   {1, 2, 3, 4, 5, 6}, |   èìååò ñëåäóþùóþ äèàãðàììó:

                         4   [[           [[[
                                                 6

                                [[            [
                                    
                                  2 [
                                                      AA
                                                  3      5
                                      [         
                                        [[      AAAA
                                              A
                                             AA
                                             A
                                           1

     Çäåñü 1  íàèìåíüøèé ýëåìåíò, 4, 5 è 6  ìàêñèìàëüíûå, à íàèáîëüøåãî ýëåìåíòà
     íåò.
  3.  îãðàíè÷åííîì ÷.ó. ìíîæåñòâå P(A), ⊆ íàèìåíüøèì ýëåìåíòîì ÿâëÿåòñÿ ïóñòîå
     ìíîæåñòâî ∅, à íàèáîëüøèì  ñàìî ìíîæåñòâî A.
     Â ÷.ó. ìíîæåñòâå P ∗ (A), ⊆ ïðè |A| > 1 íåò íàèìåíüøåãî ýëåìåíòà, à ìèíèìàëü-
     íûìè ÿâëÿþòñÿ âñå îäíîýëåìåíòíûå ïîäìíîæåñòâà.
     Áóäåì îáîçíà÷àòü ÷åðåç P0 (A) ñîâîêóïíîñòü âñåõ êîíå÷íûõ ïîäìíîæåñòâ áåñêî-
     íå÷íîãî ìíîæåñòâà A.  ÷.ó. ìíîæåñòâå P0 (A), ⊆ íàèìåíüøèì ýëåìåíòîì áóäåò
     ïóñòîå ïîäìíîæåñòâî, à ìàêñèìàëüíûõ (ñëåäîâàòåëüíî, è íàèáîëüøåãî) ýëåìåíòîâ
     íåò.

   Ñå÷åíèåì öåïè C,       íàçûâàþò ðàçáèåíèå å¼ íà äâà ïîäìíîæåñòâà A (íèæíèé
êëàññ ñå÷åíèÿ) è B (âåðõíèé êëàññ ñå÷åíèÿ) òàê, ÷òî a < b äëÿ ëþáûõ a ∈ A è b ∈ B .
Ðàçëè÷àþò ñëåäóþùèå âèäû ñå÷åíèé:

   ˆ ñêà÷îê  â íèæíåì êëàññå èìååòñÿ íàèáîëüøèé ýëåìåíò, à â âåðõíåì êëàññå 
     íàèìåíüøèé;
   ˆ äåäåêèíäîâî ñå÷åíèå  â íèæíåì [ âåðõíåì ] êëàññå èìååòñÿ íàèáîëüøèé
     [ íàèìåíüøèé ] ýëåìåíò, à â âåðõíåì [ íèæíåì ] êëàññå íàèìåíüøåãî [ íàèáîëüøåãî ]
     ýëåìåíòà íåò;
   ˆ ùåëü  â íèæíåì êëàññå íåò íàèáîëüøåãî ýëåìåíòà, à â âåðõíåì  íàèìåíüøåãî.

Öåïü íàçûâàåòñÿ íåïðåðûâíîé, åñëè âñå å¼ ñå÷åíèÿ äåäåêèíäîâû.
   Åñëè ÷.ó. ìíîæåñòâî èìååò íàèìåíüøèé ýëåìåíò, òî ýëåìåíòû, íåïîñðåäñòâåííî ñëå-
äóþùèå çà íèì, íàçûâàþò àòîìàìè. Ïîíÿòíî, ÷òî òàêîâûõ ìîæåò è íå îêàçàòüñÿ. Ëåãêî
ïîêàçûâàåòñÿ, ÷òî äàííîå îïðåäåëåíèå àòîìà ÷.ó. ìíîæåñòâà ñîâïàäàåò ñ îïðåäåëåíèåì 1.4
àòîìà áóëåâîé àëãåáðû, åñëè â íåé ïðèíÿòü x y ⇔ x = x y (ñì. óòâåðæäåíèå 5.6).
   Äâîéñòâåííî îïðåäåëÿþòñÿ äóàëüíûå àòîìû èëè êîàòîìû èëè àíòèàòîìû : ýòî ýëå-
ìåíòû, íåïîñðåäñòâåííî ïðåäøåñòâóþùèå íàèáîëüøåìó ýëåìåíòó (â ïðåäïîëîæåíèè, ÷òî
òàêîâîé ñóùåñòâóåò).
Ïðèìåð 3.6.   1. Êîíå÷íàÿ íåòðèâèàëüíàÿ öåïü ñîäåðæèò åäèíñòâåííûå àòîì è êîàòîì.
  2. Ïîëîæèì, ÷òî 0|0. Òîãäà â ÷.ó. ìíîæåñòâå N0 , | íàèìåíüøèì ýëåìåíòîì ÿâëÿåòñÿ
     1, íàèáîëüøèì  0, àòîìû ñóòü ïðîñòûå ÷èñëà, à êîàòîìû îòñóòñòâóþò.


54                                                        Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


3.2 Èçîòîííûå îòîáðàæåíèÿ è ïîðÿäêîâûå èäåàëû
Îïðåäåëåíèå 3.6. Ïóñòü P,                          ÷.ó. ìíîæåñòâî è ∅ = A ⊆ P . Ìíîæåñòâà A            è A
îïðåäåëÿåìûå óñëîâèÿìè

                 A    =    x ∈ P | ∀a ( a           x)      è   A    =   x ∈ P | ∀a ( x   a)
                                    A                                            A

íàçûâàþòñÿ âåðõíèì è íèæíèì êîíóñàìè ìíîæåñòâà A , à èõ ýëåìåíòû  âåðõíèìè
è íèæíèìè ãðàíÿìè ìíîæåñòâà A ñîîòâåòñòâåííî. Âåðõíèé [ íèæíèé ] êîíóñ îäíîýëå-
ìåíòíîãî ìíîæåñòâà A = {a} îáîçíà÷àþò a [ a ].
   Âåðõíèì è íèæíèì êîíóñàìè ïóñòîãî ïîäìíîæåñòâà ýëåìåíòîâ P ñ÷èòàþò ñàìî ìíî-
æåñòâî P .

Òåîðåìà 3.4 (Îñíîâíûå ñâîéñòâà âåðõíåãî è íèæíåãî êîíóñîâ). Ïóñòü                                  P,     
÷.ó. ìíîæåñòâî, A, B ⊆ P è x, y ∈ P . Òîãäà

     1) A ⊆ B ⇒ B ⊆ A               è B ⊆A               (àíòèìîíîòîííîñòü êîíóñîâ ïîäìíîæåñòâ ïî
        âêëþ÷åíèþ);
     2) A ⊆ A         ∩A    ;
     3) A       = A    ;
     4) A       = A    ;
     5) (A ∪ B)       = A ∩B ;
     6) (A ∪ B)       = A ∩B ;
     7) x       y ⇔ x ⊆y        è y ⊆x .

Äîêàçàòåëüñòâî.

1) Ýòî ñâîéñòâî (àíòèìîíîòîííîñòü îïåðàöèé ïåðåõîäà ê âåðõíåìó è íèæíåìó êîíóñàì
    ïî âêëþ÷åíèþ ìíîæåñòâ) âûòåêàåò íåïîñðåäñòâåííî èç îïðåäåëåíèÿ.
2) Òàê êàê äëÿ ëþáûõ x ∈ A è y ∈ A ñïðàâåäëèâî x                              y , òî A ⊆ A     . Àíàëîãè÷íî
    ïîêàçûâàåòñÿ A ⊆ A , îòêóäà è ñëåäóåò òðåáóåìîå.
                (2)                         (1)
3), 4)      A    ⊆ (A )     = (A        )   ⊆ A         è àíàëîãè÷íî äëÿ (4).
5), 6) Âêëþ÷åíèå (A ∪ B) ⊆ A ∩ B âûòåêàåò èç (1). Åñëè æå x ∈ A ∩ B , òî y                                x
      äëÿ âñåõ y ∈ A è y ∈ B , îòêóäà ñëåäóåò ñïðàâåäëèâîñòü ñâîéñòâà (5).
         Àíàëîãè÷íî äëÿ (6). Èëëþñòðàöèåé ê äàííûì ñâîéñòâàì ñëóæèò ñëåäóþùàÿ ñõåìà

                                    A                      A ∩B
                                                                      AAA        B
                                                                                      AAA
                                                                    A               A
                                                            AAA                 AAA
                                                         AA                  AA
                                       A            A
                                                                AA
                                                                         B

                                AA AAA                      A AA
                           AA
                           A        A
                                                      A A
                                                     A AA       ∩B               B

7) Ñâîéñòâî (ìîíîòîííîñòü è àíòèìîíîòîííîñòü îïåðàöèé âçÿòèÿ ñîîòâåòñòâåííî ãëàâíî-
    ãî èäåàëà è ãëàâíîãî ôèëüòðà) ñðàçó ñëåäóåò èç îïðåäåëåíèé. Èëëþñòðàöèåé çäåñü


3.2. Èçîòîííûå îòîáðàæåíèÿ è ïîðÿäêîâûå èäåàëû                                           55


     ñëóæèò ñõåìà
                                                                         y
                                                                               A AAA
                                                  A AAA
                                               y A
                                 x
                                            AA AAAAA
                                       A AAAAAA
                                  AAA A x A          y
                                    A A
                              AA AA
                        AA          x



Îïðåäåëåíèå 3.7. Åñëè â A ñóùåñòâóåò íàèìåíüøèé ýëåìåíò, òî îí íàçûâàåòñÿ òî÷íîé
âåðõíåé ãðàíüþ ìíîæåñòâà A è îáîçíà÷àåòñÿ sup A. Åñëè â A ñóùåñòâóåò íàèáîëüøèé
ýëåìåíò, òî îí íàçûâàåòñÿ òî÷íîé íèæíåé ãðàíüþ ìíîæåñòâà A è îáîçíà÷àåòñÿ inf A.

   ÷àñòíîñòè, òî÷íîé âåðõíåé [ íèæíåé ] ãðàíüþ ïóñòîãî ìíîæåñòâà ÿâëÿåòñÿ íàèìåíü-
øèé [ íàèáîëüøèé ] ýëåìåíò ÷.ó. ìíîæåñòâà.
Ïðèìåð 3.7. 1. Ïóñòü P = {a, b, c, d} è äâà ðàçëè÷íûõ ïîðÿäêà íà P çàäàþòñÿ ñëå-
    äóþùèìè äèàãðàììàìè:

                                    d4                                    d4

                                  hh 44                                   hh 44
                                          4                                  4
                                hh c [ 44                               hh c [ 44
                              hh [[44
                             h
                                                                      hh [[44
                                                                     h
                            h                                      h
                        a                          b            a                   b

     Äëÿ A = {a, b} èìååì A = {c, d} â îáîèõ ñëó÷àÿõ, íî â ïåðâîì ñëó÷àå sup A
     îòñóòñòâóåò, à âî âòîðîì sup A = c (ñòðîãî ãîâîðÿ, âòîðàÿ äèàãðàììà íå åñòü äèà-
     ãðàììà Õàññå: ëèíèè, ñîåäèíÿþùèå d ñ a è b çäåñü èçëèøíè).
  2. Äëÿ ýëåìåíòà α ÷.ó. ìíîæåñòâà 2n ,
                    ˜                         èìååì

                    α
                    ˜       = [ α, 1 ],
                                ˜             α
                                              ˜   = [ 0, α ];
                                                         ˜          sup α = inf α = α.
                                                                        ˜       ˜   ˜

  3. Ïóñòü P,         ÷.ó. ìíîæåñòâî è A ⊆ B ⊆ P . Åñëè ñóùåñòâóþò sup A è sup B
     ( inf A è inf B ), òî sup A sup B (inf A inf B ).
  4. Åñëè S  ñîâîêóïíîñòü ïîäìíîæåñòâ íåêîòîðîãî ìíîæåñòâà, òî, ïî âêëþ÷åíèþ,
     sup S ñîâïàäàåò ñ îáúåäèíåíèåì, à inf S  ñ ïåðåñå÷åíèåì âñåõ ïîäìíîæåñòâ èç
     ñîâîêóïíîñòè S .
Îïðåäåëåíèå 3.8. Ïóñòü P è P  ÷.ó. ìíîæåñòâà è x, y  ïðîèçâîëüíûå ýëåìåíòû
èç P . Îòîáðàæåíèå ϕ : P → P íàçûâàåòñÿ ñîîòâåòñòâåííî
   ˆ èçîòîííûì îòîáðàæåíèåì, åñëè x    y ⇒ ϕ(x)   ϕ(y), èçîòîííûå îòîáðàæåíèÿ
     íàçûâàþò òàêæå ìîíîòîííûìè èëè ïîðÿäêîâûìè ãîìîìîðôèçìàìè ;
   ˆ îáðàòíî èçîòîííûì îòîáðàæåíèåì, åñëè ϕ(x) ϕ(y) ⇒ x y ;
   ˆ àíòèèçîòîííûì, åñëè x y ⇒ ϕ(x) ϕ(y).


56                                       Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


   Åñëè ϕ èçîòîííî, îáðàòíî èçîòîííî è èíúåêòèâíî, òî åãî íàçûâàþò âëîæåíèåì èëè
(ïîðÿäêîâûì) ìîíîìîðôèçìîì ÷.ó. ìíîæåñòâà P â ÷.ó. ìíîæåñòâî P , ÷òî îáîçíà÷àþò
   ϕ
P → P .
   Ñþðúåêòèâíûé ìîíîìîðôèçì ÷.ó. ìíîæåñòâ íàçûâàþò (ïîðÿäêîâûì) èçîìîðôèçìîì
                                                            ϕ
(ñèìâîëè÷åñêè P ∼ P èëè, ñ óêàçàíèåì íà îòîáðàæåíèå  P ∼ P ).
                =                                           =
    Ëåãêî ïîêàçàòü, ÷òî êîìïîçèöèÿ èçîòîííûõ [îáðàòíî èçîòîííûõ] îòîáðàæåíèé èçî-
òîííà [îáðàòíî èçîòîííà]. Ïîíÿòíî òàêæå, ÷òî äëÿ ÷.ó. ìíîæåñòâ P è P îòîáðàæåíèå
ϕ : P → P åñòü ïîðÿäêîâûé èçîìîðôèçì, åñëè è òîëüêî åñëè P  èçîòîííàÿ è îáðàòíî
èçîòîííàÿ áèåêöèÿ, ò.å. äëÿ ëþáûõ x, y ∈ P ñïðàâåäëèâî x y ⇔ ϕ(x) ϕ(y). Çàìåòèì,
÷òî áèåêòèâíîñòü ϕ ìîæåò áûòü âûâåäåíà èç ïîñëåäíåãî óñëîâèÿ.
Ïðèìåð 3.8.    1. ×.ó. ìíîæåñòâî a), èçîáðàæ¼ííîå íà ðèñ. 3.1 ÿâëÿåòñÿ èçîòîííûì îá-
     ðàçîì ÷.ó. ìíîæåñòâà b), åñëè â êà÷åñòâå îòîáðàæåíèÿ âçÿòü ôóíêöèþ ϕ(x) = |x|.
     Ýòî îòîáðàæåíèå íå èíúåêòèâíî è, ñëåäîâàòåëüíî, âëîæåíèåì íå ÿâëÿåòñÿ.
  2. Òîæäåñòâåííîå îòîáðàæåíèå ÷.ó. ìíîæåñòâà N, | âî ìíîæåñòâî íàòóðàëüíûõ ÷è-
     ñåë ñ åñòåñòâåííûì ïîðÿäêîì èçîòîííî, íî íå îáðàòíî èçîòîííî è, ñëåäîâàòåëüíî,
     âëîæåíèåì òàêæå íå ÿâëÿåòñÿ.
  3. Ïðè ïðîäîëæåíèè ëþáîãî ÷àñòè÷íîãî ïîðÿäêà        íà äî ëèíåéíîãî    åñòåñòâåííîå
     âëîæåíèå id : M,       → M,        èçîòîííî è âçàèìíîîäíîçíà÷íî, íî íå ÿâëÿåòñÿ
     ìîíîìîðôèçìîì èç-çà îòñóòñòâèÿ îáðàòíîé èçîòîííîñòè è, òåì áîëåå, íå ÿâëÿåòñÿ
     èçîìîðôèçìîì.
         ÷àñòíîñòè, åñëè Q  íåîäíîýëåìåíòíîå ÷.ó. ìíîæåñòâî ñ òðèâèàëüíûì ïîðÿäêîì,
        à Q  òî æå ñàìîå ìíîæåñòâî ñ ïðîèçâîëüíûì íåòðèâèàëüíûì ïîðÿäêîì, òî òîæ-
        äåñòâåííîå îòîáðàæåíèå Q íà ñåáÿ ÿâëÿåòñÿ èçîòîííûì è âçàèìíîîäíîçíà÷íûì, íî
        íå îáðàòíî èçîòîííûì.
     4. Åñòåñòâåííîå âëîæåíèå nZ â Z äëÿ íàòóðàëüíîãî n åñòü ìîíîìîðôèçì.
     5. Îòîáðàæåíèå ϕ áóëåàíà íåïóñòîãî ìíîæåñòâà X â ñåáÿ òàêîå, ÷òî ϕ(A) = A äëÿ
        A ⊆ X , åñòü àíòèèçîòîííîå îòîáðàæåíèå.
Òåîðåìà 3.5 ([10]). Êàæäûé ÷àñòè÷íûé ïîðÿäîê èçîìîðôåí íåêîòîðîìó ïîäìíîæåñòâó
äåêàðòîâà ïðîèçâåäåíèÿ öåïåé.
Îïðåäåëåíèå 3.9. Ìóëüòèïëèêàòèâíîé ðàçìåðíîñòüþ ÷.ó. ìíîæåñòâà P íàçû-
âàåòñÿ íàèìåíüøåå ÷èñëî k ëèíåéíûõ ïîðÿäêîâ Ci òàêèõ, ñóùåñòâóåò âëîæåíèå
P → C1 Ч . . . Ч Ck .


Îïðåäåëåíèå 3.10. Ïóñòü P,          ÷.ó. ìíîæåñòâî. Ïîäìíîæåñòâî I ýëåìåíòîâ P
íàçûâàåòñÿ åãî ïîðÿäêîâûì èäåàëîì, åñëè

                                     x∈I
                                         ⇒ y ∈ I.
                                     y x

Ïîäìíîæåñòâî F ýëåìåíòîâ P íàçûâàåòñÿ åãî ïîðÿäêîâûì ôèëüòðîì, åñëè

                                     x∈F
                                         ⇒ y ∈ F.
                                     x y

    Òàêèì îáðàçîì, ïîðÿäêîâûå èäåàëû ÷.ó. ìíîæåñòâà ñóòü òàêèå åãî ïîäìíîæåñòâà, êî-
òîðûå âìåñòå ñ êàæäûì ñâîèì ýëåìåíòîì ñîäåðæàò âñå ýëåìåíòû, ïðåäøåñòâóþùèå åìó.
Ñîãëàñíî îïðåäåëåíèþ, ïóñòîå ìíîæåñòâî òàêæå ÿâëÿåòñÿ ïîðÿäêîâûì èäåàëîì ëþáîãî
÷.ó. ìíîæåñòâà. Äâîéñòâåííî, ïîðÿäêîâûå ôèëüòðû ÷.ó. ìíîæåñòâà ñóòü òàêèå åãî ïîäìíî-
æåñòâà, êîòîðûå âìåñòå ñ êàæäûì ñâîèì ýëåìåíòîì ñîäåðæàò âñå ýëåìåíòû, ñëåäóþùèå


3.3. Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè. Ðàçìåðíîñòü                                       57


çà íèì. Ïîðÿäêîâûå èäåàëû [ ôèëüòðû ] íàçûâàþò òàêæå ïîëóèäåàëàìè èëè íèæíèìè
ìíîæåñòâàìè [ ïîëóôèëüòðàìè, âåðõíèìè ìíîæåñòâàìè ].
   ßñíî, ÷òî îáúåäèíåíèå è ïåðåñå÷åíèå ïîðÿäêîâûõ èäåàëîâ åñòü ïîðÿäêîâûé èäåàë.
Î÷åâèäíî, x è x äëÿ ëþáîãî ýëåìåíòà x ÷.ó. ìíîæåñòâà P ÿâëÿþòñÿ ïîðÿäêîâû-
ìè èäåàëîì è ôèëüòðîì ñîîòâåòñòâåííî. Òàêèå èäåàëû è ôèëüòðû íàçûâàþò ãëàâíûìè.
Äàëåå èñïîëüçóåòñÿ îáîçíà÷åíèå J(x) = x .
   Ìíîæåñòâî âñåõ ïîðÿäêîâûõ èäåàëîâ ÷.ó. ìíîæåñòâà P , óïîðÿäî÷åííîå ïî âêëþ÷åíèþ,
îáðàçóåò ÷.ó. ìíîæåñòâî, êîòîðîå ìû áóäåì îáîçíà÷àòü J(P ). Íàïðèìåð, åñëè P = n 
n-ýëåìåíòíàÿ öåïü, òî J(n) ∼ n + 1.  äðóãîì êðàéíåì ñëó÷àå, åñëè P  n-ýëåìåíòíàÿ
                            =
àíòèöåïü, òî ëþáîå ïîäìíîæåñòâî â P åñòü åãî ïîðÿäêîâûé èäåàë, J(P ) áóäåò áóëåàíîì
P è J(P ) ∼ 2n .
          =
   Ñîâîêóïíîñòü x∈P J(x) âñåõ ãëàâíûõ ïîðÿäêîâûõ èäåàëîâ ÷.ó. ìíîæåñòâà P , óïî-
ðÿäî÷åííîå ïî âêëþ÷åíèþ, â ñâîþ î÷åðåäü îáðàçóåò ÷.ó. ìíîæåñòâî, êîòîðîå ìû áóäåì
îáîçíà÷àòü J0 (P ). Ïîíÿòíî, ÷òî J0 (P ) îáðàçóåò ÷.ó. ïîäìíîæåñòâî J(P ).
Òåîðåìà 3.6 (Î ïðåäñòàâëåíèè ÷.ó. ìíîæåñòâ). Ëþáîå ÷.ó. ìíîæåñòâî ìîæåò
áûòü âëîæåíî â áóëåàí ïîäõîäÿùåãî ìíîæåñòâà, óïîðÿäî÷åííûé ïî âêëþ÷åíèþ.
Äîêàçàòåëüñòâî. Ïóñòü P,      ÷.ó. ìíîæåñòâî. Äîêàæåì, ÷òî ϕ(x) = x          áóäåò èçî-
ìîðôèçìîì ìåæäó P è J0 (P ).
   Ïîêàæåì ñíà÷àëà, ÷òî ϕ  áèåêöèÿ. Äåéñòâèòåëüíî,

 ϕ(x) = ϕ(y) ⇔ (x = y ) ⇔ (x ∈ y )         (y ∈ x ) ⇔
                                                        ⇔ (x    y)   (y   x) ⇔ x = y ,

ò.å. ϕ  âëîæåíèå. Òàêæå î÷åâèäíî, ÷òî êàæäîìó ãëàâíîìó èäåàëó x ñîîòâåòñòâóåò
ïîðîæäàþùèé åãî ýëåìåíò x è ïîýòîìó ϕ  íàëîæåíèå.
    Èçîòîííîñòü è îáðàòíàÿ èçîòîííîñòü ϕ óñòàíàâëèâàåòñÿ ï. 7) òåîðåìû 3.4:

                          x    y ⇔ x ⊆y      ⇔ ϕ(x) ⊆ ϕ(y) .

Òàêèì îáðàçîì, P ∼ J0 (P ) → J(P ) → P(P ) (îáà ïîñëåäíèõ âëîæåíèÿ  åñòåñòâåííûå).
                 =

                                                ϕ
   Çàìåòèì, ÷òî óñòàíîâëåííûé èçîìîðôèçì P ∼ J0 (P ) , ϕ(x) = x ÷àñòî èñïîëüçóåòñÿ
                                                  =
ïðè äîêàçàòåëüñòâàõ ðàçëè÷íûõ ñâîéñòâ ÷.ó. ìíîæåñòââ.
   Ïîä÷åðêí¼ì âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó åãî àíèòöåïÿìè è ïîðÿäêîâûìè
èäåàëàìè êîíå÷íîãî ÷.ó. ìíîæåñòâà. Äåéñòâèòåëüíî, ñ îäíîé ñòîðîíû, ìíîæåñòâî M
ìàêñèìàëüíûõ ýëåìåíòîâ èäåàëà I åñòü àíòèöåïü (âîçìîæíî, òðèâèàëüíàÿ), à ñ äðóãîé 
I = a∈M a . Åñëè íåêîòîðîå ïîäìíîæåñòâî A ÷.ó. ìíîæåñòâà è åãî èäåàë I ñâÿçàíû
òàêèì ñîîòíîøåíèåì, òî ãîâîðÿò, ÷òî A ïîðîæäàåò I .  ñëó÷àå A = {a1 , . . . , ak } ïèøóò
I = a1 , . . . , ak è ãîâîðÿò, ÷òî èäåàë I êîíå÷íîïîðîæä¼ííûé. ßñíî, ÷òî J(a) = a .
Ïðèìåð 3.9. Íà ðèñ. 3.5 ïîêàçàíû äèàãðàììû ÷åòûð¼õýëåìåíòíîãî ÷.ó. ìíîæåñòâà P è
ìíîæåñòâà åãî ïîðÿäêîâûõ èäåàëîâ J(P ). Ìíîæåñòâî J0 (P ) âûäåëåíî æèðíûì øðèô-
òîì. Î÷åâèäíî P ∼ J0 (P ). Êàæäîìó ïîðÿäêîâîìó èäåàëó èç J(P ) ñîîòâåòñòâóåò àíòè-
                      =
öåïü P , åãî ïîðîæäàþùàÿ.


3.3 Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè. Ðàçìåðíîñòü
   Äëÿ ÷.ó. ìíîæåñòâ ìîæíî îïðåäåëèòü ðàçëè÷íûå îïåðàöèè. Ðàññìîòðèì íåêîòîðûå èç
íèõ.


58                                                      Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà



                                                                                   d




                                                                              
                                                                                  a, c
                                                                                         [[
                                                                                         [
                                     [[
                                                                 [[[
                                 d                               a, b                           c
                             h
                          hh
                                          [[                                           
                        h
                     hh                                      [[
                                               c         a                         b
                                                                              
                  hhh                                          [ 
              a                                b                    ∅



                                 P                                       J(P ) è J0 (P )


          Ðèñ. 3.5: ×.ó. ìíîæåñòâà P è J(P ) (ïîäìíîæåñòâî J0 (P ) âûäåëåíî)

Äâîéñòâåííîñòü. Åñëè P  ÷.ó. ìíîæåñòâî ñ ïîðÿäêîì     , òî ÷.ó. ìíîæåñòâî ñ òåì æå
íîñèòåëåì è ïîðÿäêîì     íàçîâ¼ì äóàëüíûì èëè äâîéñòâåííûì ê P è îáîçíà÷èì P .
Åñëè P ∼ P , òî ÷.ó. ìíîæåñòâî P íàçûâàþò ñàìîäâîéñòâåííûì.
        =
   Äèàãðàììà Õàññå ìíîæåñòâà P åñòü äèàãðàììà ÷.ó. ìíîæåñòâà P ïåðåâ¼ðíó-
òàÿ ââåðõ íîãàìè, ïðè ýòîì äèàãðàììû ñàìîäâîéñòâåííûõ ìíîæåñòâ íå èçìåíÿòñÿ.
Íà ðèñ. 3.6 ïîêàçàíû äèàãðàììû Õàññå ÷.ó. ìíîæåñòâ, êîòîðûå áóäåì íàçûâàòü çèã-
çàãàìè, ïðè÷¼ì äâà ïåðâûå ÷.ó. ìíîæåñòâà äâîéñòâåííû äðóã äðóãó, à ïîñëåäíåå  ñà-
ìîäâîéñòâåííî.



                      [[[                              [[                                    [[ y4
                            x2                     x1                    x3              y2


                  
                                                          [
                                                                                             [
             x1                           x3                  x2                         y1         y3



                            Z3                                Z3                         Z4


                                     Ðèñ. 3.6: Äèàãðàììû Õàññå çèãçàãîâ

     ßñíî, ÷òî ê ÷.ó. ìíîæåñòâàì ïðèìåíèì ñëåäóþùèé
Ïðèíöèï äâîéñòâåííîñòè (äëÿ ÷àñòè÷íî óïîðÿäî÷åííûõ ìíîæåñòâ). Ëþáîå
óòâåðæäåíèå, èñòèííîå â ÷.ó. ìíîæåñòâå, îñòà¼òñÿ èñòèííûì â ÷.ó. ìíîæåñòâå,
äóàëüíîì ê íåìó.


3.3. Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè. Ðàçìåðíîñòü                                  59


Ïðÿìàÿ ñóììà. Åñëè P,        P  è Q, Q  äâà ÷.ó. ìíîæåñòâà ñ íåïåðåñåêàþùèìèñÿ
íîñèòåëÿìè, òî èõ ïðÿìîé èëè êàðäèíàëüíîé ñóììîé P +Q íàçûâàåòñÿ ìíîæåñòâî P ∪Q
ñ ÷àñòè÷íûì ïîðÿäêîì     òàêèì, ÷òî x y êîãäà ëèáî x P y , ëèáî x Q y .
   Ñïðàâåäëèâî ñîîòíîøåíèå

                            P +Q ∼ P +R ⇒ Q ∼ R.
                                 =          =

   Ïðÿìàÿ ñóììà n ÷.ó. ìíîæåñòâ P îáîçíà÷àåòñÿ nP . n-ýëåìåíòíàÿ àíòèöåïü èçî-
ìîðôíà n1.
   Äèàãðàììà ïðÿìîé ñóììû ñîñòîèò èç äâóõ äèàãðàìì ñîîòâåòñòâóþùèõ ÷.ó. ìíîæåñòâ,
ðàññìàòðèâàåìûõ êàê åäèíàÿ äèàãðàììà. ×.ó. ìíîæåñòâî, íå ÿâëÿþùååñÿ ïðÿìîé ñóììîé
íåêîòîðûõ äâóõ äðóãèõ ÷.ó. ìíîæåñòâ, íàçûâàåòñÿ ñâÿçíûì.


Ïîðÿäêîâàÿ ñóììà. Åñëè P,        P     è Q, Q  òàêæå äâà ÷.ó. ìíîæåñòâà ñ íåïåðå-
ñåêàþùèìèñÿ íîñèòåëÿìè, òî èõ ïîðÿäêîâîé èëè îðäèíàëüíîé ñóììîé P ⊕ Q íàçûâàåòñÿ
ìíîæåñòâî P ∪ Q ñ ÷àñòè÷íûì ïîðÿäêîì       òàêèì, ÷òî x y êîãäà ëèáî x P y , ëèáî
x Q y , ëèáî x ∈ P è y ∈ Q.
   Ïîíÿòíî, ÷òî îïåðàöèÿ ïîðÿäêîâîé ñóììû àññîöèàòèâíà, íî íå êîììóòàòèâíà. Îáû÷-
íûì îáðàçîì ââîäèòñÿ ïîíÿòèå íàòóðàëüíîé ñòåïåíè P n ÷.ó. ìíîæåñòâà P . n-ýëåìåíòíàÿ
öåïü èçîìîðôíà 1 ⊕ . . . ⊕ 1 ( n ðàç).
   Äèàãðàììà ïîðÿäêîâîé ñóììû P ⊕Q ñîñòîèò èç äèàãðàìì ñîîòâåòñòâóþùèõ ÷.ó. ìíî-
æåñòâ, ïðè÷¼ì äèàãðàììà P ðàñïîëàãàåòñÿ ïîä äèàãðàììîé Q, è â êîòîðîé äîáàâëå-
íû îòðåçêè, ñîåäèíÿþùèå ìàêñèìàëüíûå ýëåìåíòû P ñ ìèíèìàëüíûìè ýëåìåíòàìè Q.
Íà ðèñ. 3.7 ïîêàçàíà ïîðÿäêîâàÿ ñóììà äâóõ çèãçàãîâ ïîðÿäêîâ 3 è 4.




                                           [[[
                                            ◦

                                       
                                               AA
                                     ◦            ◦
                                            AA
                                       A
                                       A AA
                                     ◦            ◦


                                     ◦              ◦


                        Ðèñ. 3.7: Ïîðÿäêîâàÿ ñóììà Z4 ⊕ Z3

   ×.ó. ìíîæåñòâî, íå ïðåäñòàâèìîå â âèäå êàðäèíàëüíîé [ îðäèíàëüíîé ] ñóììû ñâîèõ
ïîäìíîæåñòâ, íàçûâàåòñÿ êàðäèíàëüíî [ îðäèíàëüíî ] íåðàçëîæèìûì.

Òåîðåìà 3.7. Âñÿêîå ÷.ó. ìíîæåñòâî ÿâëÿåòñÿ êàðäèíàëüíîé ñóììîé ñâîèõ êàðäèíàëü-
íî íåðàçëîæèìûõ ïîäìíîæåñòâ.

   Âåðíà òàêæå àíàëîãè÷íàÿ òåîðåìà äëÿ îðäèíàëüíîé ñóììû. Äîêàçàòåëüñòâî îáåèõ
òåîðåì èìååòñÿ â [13].


60                                          Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà


Ëåêñèêîãðàôè÷åñêàÿ ñóììà (ïîäñòàíîâêà ÷.ó. ìíîæåñòâ). Ïóñòü                P, P 
÷.ó. ìíîæåñòâî, êàæäîìó ýëåìåíòó p êîòîðîãî ñîïîñòàâëåíî ÷.ó. ìíîæåñòâî Qp , p .
Ñåìåéñòâî âñåõ ÷.ó. ìíîæåñòâ Qp , èíäåêñèðîâàííûõ ýëåìåíòàìè P , îáîçíà÷èì F .
    Ëåêñèêîãðàôè÷åñêîé     ñóììîé         P Qp    ñåìåéñòâà      ÷.ó.      ìíîæåñòâ
F = { Qp , p | p ∈ P } íàä ÷.ó. ìíîæåñòâîì P, P íàçûâàåòñÿ ÷.ó. ìíî-
æåñòâî R, R , ñ íîñèòåëåì R = { (p, q) | p ∈ P, q ∈ Qp } è ïîðÿäêîì íà í¼ì,
çàäàâàåìûì ñîîòíîøåíèåì (p, q) R (p , q ), åñëè ëèáî p P p , ëèáî p = p è q p q .
    Äëÿ òîãî, ÷òîáû ïîëó÷èòü äèàãðàììó ëåêñèêîãðàôè÷åñêîé ñóììû       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



                 P                Qa          Qb     Qc             Qp
                                                               P



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

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

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



    
Яндекс цитирования Яндекс.Метрика