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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    2.6. Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà                                                   41


   ˆ íàëîæåíèåì èëè ñþðúåêòèâíûì îòîáðàæåíèåì A â B , åñëè ϕ ϕ = idB . Ëåãêî
     âèäåòü, ÷òî ïðè íàëîæåíèè êàæäûé ýëåìåíò ìíîæåñòâà B èìååò ñâîé ïðîîáðàç.
   ˆ áèåêöèåé,      áèåêòèâíûì,       âçàèìíîîäíîçíà÷íûì     îòîáðàæåíèåì,     åñëè
     idA = ϕϕ       ϕ ϕ = idB , ò.å. îíî ÿâëÿåòñÿ îäíîâðåìåííî è âëîæåíèåì, è íàëî-
     æåíèåì. Ìíîæåñòâî âñåõ áèåêòèâíûõ îòîáðàæåíèé èç A â B áóäåì îáîçíà÷àòü
     Bij (A, B), à â ñëó÷àå A = B  ïîëüçîâàòüñÿ îáîçíà÷åíèåì Bij (A).

    Ëåãêî âèäåòü, ÷òî ïðè âëîæåíèè ðàçëè÷íûå ýëåìåíòû A ïåðåõîäÿò â ðàçëè÷íûå ýëå-
ìåíòû B è ïðîîáðàç ϕ (y) ýëåìåíòà y ∈ Y  íå áîëåå, ÷åì îäíîýëåìåíòíîå ìíîæå-
                                                                            πi
ñòâî. Òàêæå ÿñíî, ÷òî äëÿ A = A1 Ч . . . Ч An îòîáðàæåíèÿ A → Ai , îïðåäåëÿåìûå
                                    πi
êàê (a1 , . . . , ai , . . . , ak ) → ai , i = 1, n ñþðúåêòèâíû. Îíè íàçûâàþòñÿ îòîáðàæåíèÿìè
ïðîåêòèðîâàíèÿ.
    Ïñåâäîîáðàòíîå ê îòîáðàæåíèþ ϕ : A → B ñîîòâåòñòâèå ϕ , ïîíÿòíî, ìîæåò è íå
îêàçàòüñÿ îòîáðàæåíèåì èç B â A. Îòîáðàæåíèå ψ : B → A íàçûâàåòñÿ îáðàòíûì
îòîáðàæåíèþ ϕ : A → B , åñëè idA = ϕψ ψϕ = idB . ßñíî, ÷òî åñëè ϕ  áèåêöèÿ, òî
îäíîçíà÷íî îïðåäåëÿåìîå ïñåâäîîáðàòíîå ê íåé îòíîøåíèå ϕ ÿâëÿåòñÿ îòîáðàæåíèåì
è, áîëåå òîãî, áèåêöèåé. Òàêæå ëåãêî âèäåòü, ÷òî ýòèì ñëó÷àåì èñ÷åðïûâàþòñÿ âîçìîæ-
íîñòè îòîáðàæåíèÿ èìåòü îáðàòíîå. Äëÿ áèåêöèè, îáðàòíîé ê áèåêöèè ϕ åñòåñòâåííî
èñïîëüçîâàòü îáîçíà÷åíèå ϕ−1 , à íå ϕ .
    Ìîíîèä F un (A), ∗, idA íàçûâàþò ìîíîèäîì ýíäîìîðôèçìîâ ìíîæåñòâà A è îáî-
çíà÷àþò End A. Ñèììåòðè÷åñêóþ ãðóïïó SymmA = Bij (A), ∗, −1 , idA íàçûâàþò òàê-
æå ãðóïïîé àâòîìîðôèçìîâ ìíîæåñòâà A è îáîçíà÷àþò Aut A.
    Ðàññìîòðèì ïðèìåíåíèå ê îòîáðàæåíèÿì îïåðàöèè ïðîèçâåäåíèÿ (êîìïîçèöèè).
Íåòðóäíî ïîêàçàòü, ÷òî ïðîèçâåäåíèå äâóõ âëîæåíèé, íàëîæåíèé èëè áèåêöèé òàêæå
ÿâëÿåòñÿ, ñîîòâåòñòâåííî, âëîæåíèåì, íàëîæåíèåì èëè áèåêöèåé. Îòìåòèì, ÷òî äëÿ
êîíå÷íîãî ìíîæåñòâà A èíúåêòèâíîñòü, ñþðúåêòèâíîñòü è áèåêòèâíîñòü ôóíêöèé èç
F un (A)  ðàâíîñèëüíûå óñëîâèÿ.
    Ñëåäóþùèå äâå òåîðåìû õàðàêòåðèçóþò âëîæåíèå è íàëîæåíèå ÷åðåç ñâîéñòâà èõ
ïðîèçâåäåíèé (êîìïîçèöèé).
Òåîðåìà 2.18. Îòîáðàæåíèå f : X → Y  èíúåêöèÿ åñëè è òîëüêî åñëè äëÿ ëþáûõ
äâóõ îòîáðàæåíèé g1 , g2 èç íåêîòîðîãî ìíîæåñòâà Z â X

                                g1 f = g2 f ⇔ g1 = g2 .

Äîêàçàòåëüñòâî. (⇒) Ïóñòü f  èíúåêöèÿ èç ìíîæåñòâà X â Y è äëÿ ëþáûõ äâóõ
îòîáðàæåíèé g1 , g2 èç Z â X ñïðàâåäëèâî g1 f = g2 f . Íî òîãäà æå ñïðàâåäëèâî
g1 f f = g2 f f èëè g1 idX = g2 idX , îòêóäà g1 = g2 .
    (⇐) Ïóñòü äëÿ ëþáûõ äâóõ îòîáðàæåíèé g1 , g2 èç Z â X ñïðàâåäëèâà ðàâíîñèëü-
íîñòü g1 f = g2 f ⇔ g1 = g2 , íî f íå ÿâëÿåòñÿ âëîæåíèåì. Òîãäà íàéäóòñÿ x1 è x2
èç X , ÷òî x1 = x2 , íî f (x1 ) = f (x2 ). Âîçüì¼ì â êà÷åñòâå Z îäíîýëåìåíòíîå ìíîæåñòâî
{z0 } è ïîñòðîèì äâà îòîáðàæåíèÿ g1 , g2 èç Z â X òàêèå, ÷òî g1 (z0 ) = x1 , g2 (z0 ) = x2 .
Ïîñêîëüêó f (g1 (z0 )) = f (g2 (z0 )), à äðóãèõ çíà÷åíèé àðãóìåíòà íåò, òî g1 f = g2 f ,
g1 = g2 è x1 = x2 . Ïðîòèâîðå÷èå.

Òåîðåìà 2.19. Îòîáðàæåíèå f : X → Y  ñþðúåêöèÿ åñëè è òîëüêî åñëè äëÿ ëþáûõ
äâóõ îòîáðàæåíèé g1 , g2 èç Y â íåêîòîðîå ìíîæåñòâî Z

                                f   g1 = f   g2 ⇔ g1 = g2 .

Äîêàçàòåëüñòâî. (⇒) Ïóñòü f  ñþðúåêöèÿ èç ìíîæåñòâà X â Y è äëÿ ëþáûõ äâóõ
îòîáðàæåíèé g1 , g2 èç Y â Z ñïðàâåäëèâî f g1 = f g2 . Èç òîãî, ÷òî f  íàëîæåíèå


42                                                             Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


ñëåäóåò íåïóñòîòà f (y) äëÿ ëþáîãî y ∈ Y . Ïóñòü x ∈ f (y)7 . Òîãäà

                              g1 (y) = g1 (f (x)) = g2 (f (x)) = g2 (y) ,

÷òî â âèäó ïðîèçâîëüíîñòè ýëåìåíòà y âëå÷¼ò g1 = g2 .
    (⇐) Ïóñòü äëÿ ëþáûõ äâóõ îòîáðàæåíèé g1 , g2 èç Y â Z ñïðàâåäëèâà ðàâíîñèëü-
íîñòü f g1 = f g2 ⇔ g1 = g2 , íî f íå ÿâëÿåòñÿ íàëîæåíèåì. Òîãäà íàéä¼òñÿ ýëåìåíò
y èç îáëàñòè Y Im(f ). Çàôèêñèðóåì â Y ýëåìåíò y0 = Y è ðàññìîòðèì îòîáðàæåíèå
g2 : Y → Y , îïðåäåëÿåìîå óñëîâèåì

                                                   t      åñëè t = y
                                      g1 (t) =
                                                   y0     åñëè t = y,

ßñíî, ÷òî g1 = idY , â ñèëó ÷åãî f           g1 = f     idY . Îäíàêî äëÿ âñåõ x ∈ X èìååì

                                      g1 (f (x)) = f (x) = idY (f (x)).

Ïðîòèâîðå÷èå.
     Ñ ïîìîùüþ áèåêöèé îïèñûâàþòñÿ ôóíäàìåíòàëüíûå ñâîéñòâà ìíîæåñòâ.
Òåîðåìà 2.20 (Êàíòîðà-Øð¼äåðà-Áåðíøòåéíà8 ). Åñëè äëÿ äâóõ ìíîæåñòâ A è B
ñóùåñòâóþò áèåêöèè θ1 ìåæäó A è ïîäìíîæåñòâîì B è θ2 ìåæäó B è ïîäìíîæå-
ñòâîì A, òî ñóùåñòâóåò áèåêöèÿ ìåæäó A è B .
Äîêàçàòåëüñòâî. Îáîçíà÷èì A0 = A è Im(θ2 ) = A1 . ßñíî, ÷òî ìîæíî ñ÷èòàòü A0 ⊃ A1 è
Im(θ1 ) ⊂ B , èíà÷å òåîðåìà òðèâèàëüíî ñïðàâåäëèâà. Òàêæå ÿñíî, ÷òî â ýòîì ñëó÷àå A è
B  áåñêîíå÷íûå ìíîæåñòâà.
   Ïîñëåäîâàòåëüíîå ïðèìåíåíèå îòîáðàæåíèé, óêàçàííûõ â ôîðìóëèðîâêå òåîðåìû, äà-
¼ò âçàèìíî îäíîçíà÷íîå îòîáðàæåíèå θ = θ1 ∗ θ2 ìíîæåñòâà A0 íà ñâî¼ ïîäìíîæåñòâî
A2 è A1 ⊃ A2 . Îáîçíà÷èì θ(Ai ) = Ai+2 , i = 0, 1, 2 . . .. Ïîëó÷èì öåïî÷êó ñòðîãî ñîäåð-
æàùèõñÿ äðóã â äðóãå ïîäìíîæåñòâ A: A = A0 ⊃ A1 ⊃ A2 ⊃ . . ..
   Îáîçíà÷èì Ci = Ai          Ai+1 , i = 0, 1, 2 . . . è C =       i 0 Ai . Ïî ïîñòðîåíèþ
ìåæäó ìíîæåñòâàìè C0 , C2 , C4 , . . . ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå ñîîòâåòñòâèå θ:
C2i+2 = θ(A2i ) θ(A2i+1 ) = θ(C2i ).
   Ïîñòðîèì òåïåðü âçàèìíî îäíîçíà÷íîå îòîáðàæåíèå ϕ ìåæäó A0 è A1 . Ïîëîæèì

                              θ(x),     åñëè x ∈ C2i , i = 0, 1, . . .
                  ϕ(x) =                                                  (ñì. ðèñ. 2.7).
                              x,        èíà÷å

                                                                         −1   ϕ     θ−1
 Òàêèì îáðàçîì, èìååì âçàèìíî îäíîçíà÷íûå ñîîòâåòñòâèÿ A → A1 → B è ϕ ∗ θ2 
                                                              2


èñêîìàÿ áèåêöèÿ.
   Ïóñòü ∼  ýêâèâàëåíòíîñòü íà A. Òîãäà ñóùåñòâóåò ôóíêöèÿ π : A → A/∼, ñòàâÿ-
ùàÿ â ñîîòâåòñòâèå êàæäîìó ýëåìåíòó a ∈ A åãî êëàññ ýêâèâàëåíòíîñòè, ò.å. π(a) = [a]∼ .
Òàêîå îòîáðàæåíèå íàçûâàåòñÿ åñòåñòâåííûì (êàíîíè÷åñêèì, íàòóðàëüíûì). Êàíîíè-
÷åñêîå îòîáðàæåíèå ìû áóäåì îáîçíà÷àòü nat(A, ∼) èëè ïðîñòî nat(∼), åñëè ìíîæåñòâî
A ôèêñèðîâàíî ïðè äàííîì ðàññìîòðåíèè. Ïîíÿòíî, ÷òî nat(∼)  íàëîæåíèå.
Ïðèìåð 2.14. Äëÿ ïðèìåðà 2.2 èìååì:
     1. π(a)  ìåøîê, â êîòîðîì ëåæèò çåðíî a;
     7 Çàìåòèì, ÷òî âîçìîæíîñòü óêàçàíèÿ òàêîãî    x ýêâèâàëåíòíà ïðèíÿòèþ àêñèîìû âûáîðà (ñì. ï. 3.4).
     8 Òåîðåìà áûëà ïðèâåäåíà áåç äîêàçàòåëüñòâà   â ðàáîòå Êàíòîðà 1883 ã. è äîêàçàíà ïîçäíåå Øð¼äåðîì
è Áåðíøòåéíîì.


2.6. Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà                                                                          43



          A0    =       C0   +     C1
                                         u
                                                 +    C2   +   C3
                                                                 u
                                                                         +   C4   +      ...   +        Cu

                                                       ϕ
                                     u                               u                                    u
          A1    =                   C1           +    C2   +    C3       +   C4   +       ...   +        C


               Ðèñ. 2.7: Ñõåìà ñîîòâåòñòâèÿ ìåæäó ìíîæåñòâàìè A0 è A1

  2. π(u)  íà÷àëüíàÿ áóêâà ñëîâà u.
   Ïóñòü äàíî îòîáðàæåíèå ϕ : A → B . Åãî ÿäðîì íàçûâàåòñÿ îòíîøåíèå Ker ϕ ∈ R(A),
çàäàííîå êàê
                          a1 (Ker ϕ)a2 ⇔ ϕ(a1 ) = ϕ(a2 ).                     (2.9)
Ïîíÿòíî, ÷òî ÿäðî îòîáðàæåíèÿ åñòü ÷àñòíûé ñëó÷àé ïîíÿòèÿ ÿäðà ñîîòâåòñòâèÿ (2.5) è
ÿâëÿåòñÿ ÿäåðíîé ýêâèâàëåíòíîñòüþ.
   Ñ ÿäåðíîé ýêâèâàëåíòíîñòüþ îòîáðàæåíèÿ ϕ èç A ñâÿçàíî ôàêòîðìíîæå-
ñòâî A/ Ker ϕ è íàòóðàëüíîå îòîáðàæåíèå nat(A, Ker ϕ). Çàìåòèì, ÷òî îòîáðàæåíèÿ
ϕ : A → B è nat(A, Ker ϕ) èìåþò îáùóþ ÿäåðíóþ ýêâèâàëåíòíîñòü, íî îòîáðàæàþò
A â ðàçíûå ìíîæåñòâà: ñîîòâåòñòâåííî â B è â A/ Ker ϕ. Òàêæå íåòðóäíî âèäåòü, ÷òî
Ker ϕ = ϕϕ . ßñíî, ÷òî åñëè ÿäðî îòîáðàæåíèÿ ϕ èç A â B åñòü äèàãîíàëüíîå îòíîøå-
íèå íà A, òî ϕ  âëîæåíèå A â B .
   Äàëåå ìû áóäåì ïîëüçîâàòüñÿ ñëåäóþùèì óäîáíûì èçîáðàæåíèåì ñîîòâåòñòâèé. Åñëè
A, B, C, D  íåêîòîðûå ìíîæåñòâà è
                                 α : A → B, β : B → C, γ : A → C,
                                        δ : B → D, ε : C → D.
òî óêàçàííûå îòîáðàæåíèÿ íà íèõ íàãëÿäíî çàäàþò â âèäå äèàãðàìì, ïðèâåä¼ííûõ
íà ðèñ. 2.8.


                A   [[
                             α
                                      wB                                           A
                                                                                           α
                                                                                                wB
                         [ 
                         ] 
                         [                                                     γ                  δ
                    γ                        β
                                                                                      u          u
                             C                                                     C
                                                                                           ε
                                                                                                wD
                         Ðèñ. 2.8: Äèàãðàììû îòîáðàæåíèé ìíîæåñòâ

   Ãîâîðÿò, ÷òî ýòè äèàãðàììû êîììóòàòèâíû, åñëè γ = αβ è αδ = γε ñîîòâåòñòâåííî.
Àíàëîãè÷íî îïðåäåëÿåòñÿ êîììóòàòèâíîñòü è äëÿ áîëåå ñëîæíûõ äèàãðàìì. Áèåêòèâíûå
îòîáðàæåíèÿ áóäåì îáîçíà÷àòü íà äèàãðàììàõ äâóíàïðàâëåííûìè ñòðåëêàìè ↔.
   Ñôîðìóëèðóåì òåïåðü îñíîâíóþ òåîðåìó î ðàçëîæåíèè îòîáðàæåíèé.
Òåîðåìà 2.21 (Î ðàçëîæåíèè îòîáðàæåíèé). Ïóñòü äàíû íåïóñòûå ìíîæåñòâà A,
B è îòîáðàæåíèå ϕ : A → B . Òîãäà äëÿ îòîáðàæåíèÿ ϕ ñïðàâåäëèâî ðàçëîæåíèå
                                                     ϕ = π ∗ ϕ ∗ ё,                                           (2.10)
ãäå π = nat(Ker ϕ), ϕ  áèåêöèÿ ìåæäó A/ Ker ϕ è Im ϕ è ё  âëîæåíèå Im ϕ â
B.


44                                                         Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Äîêàçàòåëüñòâî. Óòâåðæäåíèå òåîðåìû áóäåò ñïðàâåäëèâî â ñëó÷àå êîììóòàòèâíîñòè äèà-
ãðàììû
                                 A
                                          ϕ
                                                  Bu
                                                            w
                                 π                              ё
                                     u
                              A/ Ker ϕ
                                                    ϕ
                                                           w Im ϕ
   ßñíî, ÷òî Im ϕ åñòü ïîäìíîæåñòâî B .  êà÷åñòâå ё âîçüì¼ì åñòåñòâåííîå âëîæåíèå.
Èç îïðåäåëåíèÿ Ker ϕ ñëåäóåò, ÷òî îòîáðàæåíèå ϕ : A/ Ker ϕ → Im ϕ áèåêòèâíî. Îòñþ-
äà ñëåäóåò ñïðàâåäëèâîñòü ðàçëîæåíèÿ (2.10 ), åñëè â êà÷åñòâå π âçÿòü nat(Ker ϕ). Ïðè
ýòîì âñå ýëåìåíòû ðàçëîæåíèÿ (2.10) îïðåäåëåíû îäíîçíà÷íî.
     Ñëåäóþùàÿ òåîðåìà ÿâëÿåòñÿ ñëåäñòâèåì òîëüêî ÷òî äîêàçàííîé.

Òåîðåìà 2.22 (Îñíîâíîå ñâîéñòâî îòîáðàæåíèé). Ïóñòü äàíû íåïóñòûå ìíîæå-
ñòâà A, B è îòîáðàæåíèå ϕ : A → B . Òîãäà èìååòñÿ åäèíñòâåííîå îòîáðàæåíèå
ψ : A/ Ker ϕ → B ÿâëÿþùååñÿ âëîæåíèåì, è òàêîå, ÷òî äèàãðàììà

                                A    ''
                                                ϕ
                                                            w
                                         )
                                         '                [B
                                                          ]
                             nat (Ker ϕ)                [[ψ
                                             A/Ker ϕ

êîììóòàòèâíà.

Äîêàçàòåëüñòâî. Ïîëîæèì â (2.10) ψ = ϕ ∗ё . Òîãäà ψ çàäàííîå êàê ψ([a]Ker ϕ ) = ϕ(a) 
îäíîçíà÷íî îïðåäåë¼ííîå âëîæåíèå Ker ϕ â B .
    Èç äàííîé òåîðåìû ñëåäóåò, ÷òî äëÿ ëþáîãî îòîáðàæåíèÿ ϕ : A → B ñïðàâåäëèâî
êàíîíè÷åñêîå ðàçëîæåíèå ϕ = π ∗ ψ , ãäå π = nat(A, Ker ϕ)  íàëîæåíèå, à ψ  âëî-
æåíèå. Òàêîå ðàçëîæåíèå, î÷åâèäíî, åäèíñòâåííî. Ýòî ñâîéñòâî è íàçûâàþò îñíîâíûì
ñâîéñòâîì îòîáðàæåíèé.
    Îñíîâíîå ñâîéñòâî îòîáðàæåíèé ìîæíî îáîáùèòü, åñëè çàìåòèòü, ÷òî äëÿ ïðîèçâîëü-
íîé ýêâèâàëåíòíîñòè ∼, ñîäåðæàùèéñÿ â Ker ϕ ñóùåñòâóåò åäèíñòâåííîå îòîáðàæåíèå
χ : A/ ∼ → B .

Òåîðåìà 2.23 (Î ôàêòîðìíîæåñòâàõ). Ïóñòü äàíû íåïóñòûå ìíîæåñòâà A, B ñ
îòîáðàæåíèåì ϕ : A → B è ýêâèâàëåíòíîñòü ∼ íà A òàêàÿ, ÷òî ∼ ⊆ Ker ϕ. Òîãäà
èìååòñÿ åäèíñòâåííîå îòîáðàæåíèå χ : A/∼ → B òàêîå, ÷òî äèàãðàììà

                                     A   [
                                                ϕ
                                                           wB
                                           [
                                           ]
                                           [             
                                                         
                                                         
                                 nat (∼)                χ
                                              A/ ∼

êîììóòàòèâíà.

Äîêàçàòåëüñòâî. Êîììóòàòèâíîñòü äèàãðàììû îáåñïå÷èâàåòñÿ ïðè çàäàíèè χ ïðàâèëîì
χ([a]∼ ) = ϕ(a), a ∈ A. Òàêîå çàäàíèå êîððåêòíî, ïîñêîëüêó, â ñèëó ∼ ⊆ Ker ϕ, âñåì
ýëåìåíòàì x èç [a]∼ ñîîòâåòñòâóåò åäèíñòâåííîå çíà÷åíèå χ(x) = ϕ(a). ßäåðíàÿ ýêâè-
âàëåíòíîñòü îòîáðàæåíèÿ χ  åäèíè÷íîå îòíîøåíèå íà A/ ∼ ëèøü ïðè ∼ = Ker ϕ, è
ïîýòîìó χ, âîîáùå ãîâîðÿ, íå åñòü âëîæåíèå. Åäèíñòâåííîñòü χ ñëåäóåò èç òåîðåìû î
êëàññàõ ýêâèâàëåíòíîñòè.


2.6. Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà                                            45


   Èç äàííîé òåîðåìû ñëåäóåò, ÷òî äëÿ ëþáîãî îòîáðàæåíèÿ ϕ : A → B è ýêâèâàëåíò-
íîñòè ∼ íà A òàêîé, ÷òî ∼ ⊆ Ker ϕ, ñïðàâåäëèâî îáîáù¼ííîå ðàçëîæåíèå ϕ = π ∗ χ,
ãäå π = nat(A, ∼)  íàëîæåíèå. Òàêîå ðàçëîæåíèå, âîîáùå ãîâîðÿ, íå åäèíñòâåííî, ïî-
ñêîëüêó âîçìîæíû ðàçëè÷íûå èçìåëü÷åíèÿ êëàññîâ ýêâèâàëåíòíîñòåé ïî Ker ϕ. Èíîãäà
äàííóþ òåîðåìó êîðîòêî ôîðìóëèðóþò êàê óòâåðæäåíèå î âîçìîæíîñòè ôàêòîðèçàöèè
ëþáîãî îòîáðàæåíèÿ ïî ýêâèâàëåíòíîñòè, ñîäåðæàùèéñÿ â åãî ÿäðå.
   Èç îñíîâíîãî ñâîéñòâà îòîáðàæåíèé âûòåêàåò
Òåîðåìà 2.24 (Î äðîáíûõ ýêâèâàëåíòíîñòÿõ). Ïóñòü äàíî ìíîæåñòâî A è ýê-
âèâàëåíòíîñòè α, β íà í¼ì òàêèå, ÷òî β ⊆ α. Òîãäà ñóùåñòâóþò îòîáðàæåíèå
ϕ : A/β → A/α è áèåêöèÿ ψ : (A/β)/(α/β) → A/α òàêèå, ÷òî äèàãðàììà


                                         [ A ''' α
                                     [[          '
                                 nat β
                                                  '
                                                  )
                                                nat

                                  [
                                  ^[
                            A/β
                                  ''
                                           ϕ
                                                    w A/α
                                       ''         ]
                                                  [
                             nat (α/β)  )      [[
                                              [ ψ
                                              ^
                                         (A/β)/(α/β)

êîììóòàòèâíà.

Äîêàçàòåëüñòâî. Çàäàäèì ôóíêöèþ ϕ ïðàâèëîì ϕ([a]β ) = [a]α . Íåòðóäíî âèäåòü, ÷òî
òàêîå çàäàíèå êîððåêòíî, ò.ê. êàæäîìó êëàññó ýêâèâàëåíòíîñòè [a]β ñîîòâåòñòâóåò åäèí-
ñòâåííûé êëàññ ýêâèâàëåíòíîñòè [a]α . Äàëåå ïðèìåíèì òåîðåìó 2.22 ê íèæíåé ÷àñòè äèà-
ãðàììû. Ïîñêîëüêó ϕ, êàê ëåãêî âèäåòü, íàêðûòèå, òî ψ([[a]β ]α/β ) = ϕ([a]β ) = [a]α 
áèåêöèÿ.


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


Ãëàâà 3
×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà
   ¾Ïîíÿòèå ÷àñòè÷íî óïîðÿäî÷åííîãî ìíîæåñòâà ÿâëÿåòñÿ ôóíäàìåíòàëüíûì äëÿ ñî-
âðåìåííîé òåîðåòèêî-ìíîæåñòâåííîé ìàòåìàòèêè è âñòðå÷àåòñÿ âî ìíîãèõ ïðèêëàäíûõ
âîïðîñàõ.¿ [ Ë.À. Ñêîðÿêîâ. Ïðåäèñëîâèå ðåäàêòîðà ðóññêîãî ïåðåâîäà êíèãå Ë. Áåð-
íà ¾Óïîðÿäî÷åííûå ìíîæåñòâà¿ ].


3.1 Ïðåäïîðÿäêè è ïîðÿäêè
Îïðåäåëåíèå 3.1. Ïðåäïîðÿäêàìè íàçûâàþò ðåôëåêñèâíûå è òðàíçèòèâíûå îäíîðîäíûå
îòíîøåíèÿ.
Ïðèìåð 3.1. Ïðåäïîðÿäêàìè, íàïðèìåð, ÿâëÿþòñÿ:
1) îòíîøåíèå äåëèìîñòè íà ìíîæåñòâå Z {0} ;
2) îòíîøåíèå ρ íà ìíîæåñòâå äåéñòâèòåëüíûõ ôóíêöèé, çàäàâàåìîå óñëîâèåì ¾f ρh ⇔
     ìíîæåñòâî íóëåé ôóíêöèè f ñîäåðæèòñÿ âî ìíîæåñòâå íóëåé ôóíêöèè h¿.
   Ïðåäïîðÿäêè èíîãäà íàçûâàþò êâàçèïîðÿäêàìè. Äëÿ ïðåäïîðÿäêà ρ ïî òåîðåìå 2.3
èìååì ρ = ρn , n ∈ N. Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî åñëè ρ  ïðåäïîðÿäîê, òî îäíîâðåìåí-
íàÿ ñïðàâåäëèâîñòü xρy è yρx ìîæåò áûòü êàê ïðè x = y , òàê è ïðè x = y . Èñêëþ÷èâ
ïîñëåäíèé ñëó÷àé, ïðèõîäèì ê ïîíÿòèþ ïîðÿäêà.
Îïðåäåëåíèå 3.2. Ðåôëåêñèâíûå, àíòèñèììåòðè÷íûå è òðàíçèòèâíûå áèíàðíûå îòíî-
øåíèÿ íàçûâàþò îòíîøåíèÿìè ÷àñòè÷íîãî ïîðÿäêà.
   Èíîãäà äëÿ ïðîñòîòû âìåñòî ¾÷àñòè÷íûé ïîðÿäîê¿ áóäåì ãîâîðèòü ïðîñòî ¾ïîðÿäîê¿.
Ïðèìåð 3.2.   1. Îáà ïðåäïîðÿäêà èç ïðèìåðà 3.1 íå ÿâëÿþòñÿ ÷àñòè÷íûìè ïîðÿäêàìè
     ââèäó îòñóòñòâèÿ ó íèõ ñâîéñòâà àíòèñèììåòðè÷íîñòè: (1) èç m | n è n | m ñëåäóåò
     íå m = n, à ëèøü |m| = |n|; (2) ñîâïàäåíèå ìíîæåñòâ íóëåé ôóíêöèé íå îçíà÷àåò
     ðàâåíñòâà ïîñëåäíèõ.
  2. Âàæíåéøèì ïðèìåðîì ÷àñòè÷íîãî ïîðÿäêà ÿâëÿåòñÿ îòíîøåíèå âêëþ÷åíèÿ íà ñî-
     âîêóïíîñòè ïîäìíîæåñòâ íåêîòîðîãî ìíîæåñòâà. Ïðè ýòîì ãîâîðÿò, ÷òî òàêàÿ ñîâî-
     êóïíîñòü óïîðÿäî÷åíà ïî âêëþ÷åíèþ.
   Äèàãîíàëüíîå îòíîøåíèå íà ïðîèçâîëüíîì ìíîæåñòâå ìîæíî ðàññìàòðèâàòü íå òîëü-
êî êàê ýêâèâàëåíòíîñòü, íî è êàê ÷àñòè÷íûé ïîðÿäîê. Ìíîæåñòâî ñ òàêèì ïîðÿäêîì
íàçûâàþò òðèâèàëüíî óïîðÿäî÷åííûì.
   Èç ïðåäïîðÿäêà ρ âñåãäà ìîæíî ïîñòðîèòü ïîðÿäîê, åñëè îòîæäåñòâèòü ýëåìåíòû, x
è y , äëÿ êîòîðûõ îäíîâðåìåííî xρy è yρx.
Òåîðåìà 3.1. Åñëè      ïðåäïîðÿäîê íà ìíîæåñòâå P , òî
 1) áèíàðíîå îòíîøåíèå ε íà P , îïðåäåëÿåìîå óñëîâèåì
                                   aεb ⇔ a      b    b   a
    ÿâëÿåòñÿ ýêâèâàëåíòíîñòüþ;
 2) áèíàðíîå îòíîøåíèå ≤ íà ôàêòîðìíîæåñòâå P/ε, îïðåäåëÿåìîå óñëîâèåì
                                   [ a ]ε ≤ [ b ]ε ⇔ a   b
     ÿâëÿåòñÿ ÷àñòè÷íûì ïîðÿäêîì.


3.1. Ïðåäïîðÿäêè è ïîðÿäêè                                                          47


Äîêàçàòåëüñòâî.
 1) Ñîãëàñíî ñâîåìó îïðåäåëåíèþ, îòíîøåíèå ε ïðèîáðåòàåò ñâîéñòâî ñèììåòðè÷íîñòè
    â äîïîëíåíèå ê ñâîéñòâàì ðåôëåêñèâíîñòè è òðàíçèòèâíîñòè, íàñëåäóåìûõ îò .
 2) Ñâîéñòâà ðåôëåêñèâíîñòè è òðàíçèòèâíîñòè ≤ íàñëåäóþòñÿ îò îòíîøåíèÿ         . Â ñè-
    ëó îïðåäåëåíèÿ îòíîøåíèÿ ≤ îíî îêàçûâàåòñÿ åù¼ è àíòèñèììåòðè÷íûì.


   Ñîãëàñíî (2.5), ÿäåðíîé ýêâèâàëåíòíîñòüþ Ker ρ ïðåäïîðÿäêà ρ áóäåò åãî ñèììåò-
ðè÷åñêàÿ ÷àñòü Ker ρ = ρ ∩ ρ . ßäåðíîé ýêâèâàëåíòíîñòüþ ÷àñòè÷íîãî ïîðÿäêà, â ñèëó
åãî àíòèñèììåòðè÷íîñòè, áóäåò äèàãîíàëüíîå îòíîøåíèå .
Ïðèìåð 3.3. Äëÿ ïðèìåðà 3.1 â îáîçíà÷åíèÿõ òåîðåìû 3.1 ïîëó÷èì:
1) [n]ε = {n, −n} è ≤ åñòü îòíîøåíèå äåëèìîñòè | íà ôàêòîðìíîæåñòâå
     {Z {0}}/ε = N ;
2) f εh ⇔ ìíîæåñòâî íóëåé ôóíêöèé f è h ñîâïàäàþò; [f ]ε ≤ [h]ε ⇔ ìíîæåñòâî íóëåé
     ëþáîé ôóíêöèè èç [f ]ε ñîäåðæèòñÿ âî ìíîæåñòâå íóëåé ëþáîé ôóíêöèè èç [h]ε .
   Îòíîøåíèÿ ÷àñòè÷íîãî ïîðÿäêà áóäåì, êàê ïðàâèëî, îáîçíà÷àòü , èíîãäà, âïðî÷åì,
óïîòðåáëÿÿ îáîçíà÷åíèÿ ,       è ò.ä. Êîãäà x  y è x = y , òî áóäåì ïèñàòü x   y è
ãîâîðèòü îá îòíîøåíèè ñòðîãîãî ïîðÿäêà. Ïîíÿòíî, ÷òî ñòðîãèé ïîðÿäîê òðàíçèòèâåí,
íî àíòèðåôëåêñèâåí (è íåñèììåòðè÷åí, ò.å.     ∩ = ∅). Èíîãäà, äîïóñêàÿ íåêîòîðóþ
âîëüíîñòü ðå÷è, î ôîðìóëàõ x y è x y ãîâîðÿò êàê î ¾íåðàâåíñòâàõ¿. ×àñòî óäîáíî
ðàññìàòðèâàòü äâîéñòâåííûå ÷àñòè÷íûå ïîðÿäêè:    = , ò.å. çàïèñü x y îçíà÷àåò, ÷òî
y x è àíàëîãè÷íî äëÿ ñòðîãîãî ïîðÿäêà.
   Ýëåìåíòû a è b ñðàâíèìû, åñëè ëèáî a b, ëèáî b a, è íåñðàâíèìû (ñèìâîëè÷å-
ñêè a b) â ïðîòèâíîì ñëó÷àå. Ïîíÿòíî, ÷òî îòíîøåíèå íåñðàâíèìîñòè äëÿ ÷àñòè÷íîãî
ïîðÿäêà åñòü ι , à äëÿ ñòðîãîãî  ι .
Óòâåðæäåíèå 3.1.       1. Îòíîøåíèå ñðàâíèìîñòè äëÿ ÷àñòè÷íîãî ïîðÿäêà åñòü ýêâè-
        âàëåíòíîñòü.
     2. Îòíîøåíèå íåñðàâíèìîñòè äëÿ ñòðîãîãî ÷àñòè÷íîãî ïîðÿäêà åñòü îòíîøåíèå òî-
        ëåðàíòíîñòè.
Äîêàçàòåëüñòâî.
     1. Îòíîøåíèå ñðàâíèìîñòè äëÿ ÷àñòè÷íîãî ïîðÿäêà, î÷åâèäíî, ðåôëåêñèâíî, ñèììåò-
        ðè÷íî è òðàíçèòèâíî.
     2. Ðåôëåêñèâíîñòü íåñðàâíèìîñòè äëÿ ñòðîãîãî ïîðÿäêà ñëåäóåò èç àíòèðåôëåêñèâíî-
        ñòè ïîñëåäíåãî. Ñèììåòðè÷íîñòü ι äîêàçûâàåòñÿ ñëåäóþùèì âûâîäîì:

         xι y = x(   ∩   )y = ¬(x   y)   ¬(x y) =
                                           = ¬(y x)   ¬(y    x) = y( ∩    )x = yι x.


     Åñëè a b, òî ãîâîðÿò, ÷òî a ïðåäøåñòâóåò b èëè b ñëåäóåò çà a èëè ñîäåðæèò
a. Ìíîæåñòâî { x | a x x b } íàçûâàþò èíòåðâàëîì è îáîçíà÷àþò [ a, b ]. Èíòåðâàë
[ a, b ] íåïóñò, åñëè a  b. Åñëè [ a, b ] = { a, b }, òî ãîâîðÿò, ÷òî a íåïîñðåäñòâåííî
ïðåäøåñòâóåò b è ÷òî b íåïîñðåäñòâåííî ñëåäóåò çà a.
     Âûÿñíèì ñòàáèëüíîñòü ïîðÿäêîâ îòíîñèòåëüíî òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé è
ñïåöèàëüíûõ îïåðàöèé íàä îòíîøåíèÿìè. Èç òåîðåì 2.4 è 2.5 ñëåäóåò, ÷òî åñëè α è β 
ïîðÿäêè, òî α è α∩β  òàêæå ïîðÿäêè, à ïðîèçâåäåíèå αβ , âîîáùå ãîâîðÿ, íå ÿâëÿåòñÿ
ïîðÿäêîì. Îòíîñèòåëüíî îáúåäèíåíèÿ ïîðÿäêîâ èìååò ìåñòî


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


Òåîðåìà 3.2. Îáúåäèíåíèå α ∪ β ÷àñòè÷íûõ ïîðÿäêîâ α è β åñòü ÷àñòè÷íûé ïîðÿäîê,
åñëè è òîëüêî åñëè
                                     αβ ∪ βα ⊆ α ∪ β,
                                                                                      (3.1)
                                     α∩β = .
Äîêàçàòåëüñòâî. Ðàññìîòðèì ïðîèçâîëüíûå ÷àñòè÷íûå ïîðÿäêè α è β íà íåêîòîðîì ìíî-
æåñòâå.
   (⇐) Ïóñòü óñëîâèÿ (3.1) âûïîëíåíû.

       R: Ðåôëåêñèâíîñòü îáúåäèíåíèÿ α ∪ β ñëåäóåò èç ðåôëåêñèâíîñòè êàæäîãî èç ïî-
        ðÿäêîâ.

     AS: Âòîðîå ñâîéñòâî èç (3.1) îáåñïå÷èâàåò ðàâåíñòâà

                                                Dtr
         (α ∪ β) ∩ (α ∪ β) = (α ∪ β) ∩ (α ∪ β ) =
                           = (α ∩ α ) ∪ (β ∩ β ) ∪ (β ∩ α ) ∪ (α ∩ β ) =
                                                  =   ∪    ∪(α ∩ β ) ∪ (α ∩ β ) =   . (3.2)

       T: Ðåôëåêñèâíîñòü è ñèììåòðè÷íîñòü ïîðÿäêîâ âëå÷¼ò α2 = α è β 2 = β . Ñ ó÷¼òîì
        ïåðâîãî ñâîéñòâà èç (3.1) èìååì

         (α ∪ β)2 = (α ∪ β)(α ∪ β) = α2 ∪ αβ ∪ βα ∪ β 2 =
                                                   = (α ∪ β) ∪ (αβ ∪ βα) ⊆ α ∪ β. (3.3)

   (⇒) Ïóñòü α∪β  ÷àñòè÷íûé ïîðÿäîê. Òîãäà, â ñèëó åãî òðàíçèòèâíîñòè, ñïðàâåäëèâî
óñëîâèå (3.3), îòêóäà αβ ∪ βα ⊆ α ∪ β .
   Ïîñêîëüêó α ∪ β àíòèñèììåòðè÷íî, èç (3.2) ñëåäóåò, ÷òî α ∩ β ⊆ . Íî α ∩ β 
÷àñòè÷íûé ïîðÿäîê, è ïîýòîìó ⊆ α ∩ β , îòêóäà ñëåäóåò α ∩ β = .

Îïðåäåëåíèå 3.3. Ïàðó P =    P,   , ãäå P  íåïóñòîå ìíîæåñòâî, à  ÷àñòè÷-
íûé ïîðÿäîê íà í¼ì, íàçûâàþò ÷àñòè÷íî óïîðÿäî÷åííûì ìíîæåñòâîì (ñîêðàù¼ííî
¾÷.ó. ìíîæåñòâîì ¿).

    çàâèñèìîñòè îò ìîùíîñòè P ðàçëè÷àþò êîíå÷íûå è áåñêîíå÷íûå ÷.ó. ìíîæåñòâà.
×àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî, âñå èíòåðâàëû êîòîðîãî êîíå÷íû, íàçûâàåòñÿ ëî-
êàëüíî êîíå÷íûì.
   ×.ó. ìíîæåñòâî ïðåäñòàâëÿåò ñîáîé ïðèìåð íîâîãî òèïà àëãåáðàè÷åñêîé ñèñòåìû, à
èìåííî ìîäåëè. ÀÑ ÿâëÿåòñÿ ìîäåëüþ, åñëè â íåé îòñóòñòâóþò îïåðàöèè íà íîñèòåëå, íî
èìåþòñÿ îòíîøåíèÿ íà í¼ì. Ëþáîå ìíîæåñòâî ìîæíî ïðåâðàòèòü â ÷àñòè÷íî óïîðÿäî÷åí-
íîå, çàäàâ íà í¼ì íåêîòîðûé ïîðÿäîê. Íàïðèìåð, íà äâóõýëåìåíòíîì ìíîæåñòâå ìîæíî
ïîñòðîèòü 3 ðàçëè÷íûõ ïîðÿäêà: òðèâèàëüíûé, x y è y x.
Ïðèìåð 3.4.   1. Ìîäåëè R,     , N,     , N, | , 2n ,   è P(M ), ⊆ ñóòü ÷.ó. ìíî-
     æåñòâà, ïðè÷¼ì ïîñëåäíåå ñ÷èòàåòñÿ êëàññè÷åñêèì ïðèìåðîì ýòîãî ïîíÿòèÿ.
  2. Ñîâîêóïíîñòü ëó÷åé íà ïðÿìîé ñ îòíîøåíèåì âêëþ÷åíèÿ  ÷.ó. ìíîæåñòâî.
  3. Ïóñòü A = ∅. Ìîäåëü E(A), ⊆ åñòü ÷.ó. ìíîæåñòâî, ñîñòîÿùåå èç ðàçáèåíèé
     ìíîæåñòâà A, óïîðÿäî÷åííûõ ïî èçìåëü÷åíèþ.
   ßñíî, ÷òî åñëè P,      ÷.ó. ìíîæåñòâî, Q ⊆ P è |Q  ñóæåíèå îòíîøåíèÿ    íà
Q, òî è Q, |Q  ÷.ó. ìíîæåñòâî.  ýòîì ñëó÷àå Q íàçûâàåì ÷.ó. ïîäìíîæåñòâîì
P è, äîïóñêàÿ íåêîòîðóþ âîëüíîñòü, ïîðÿäîê íà P è åãî ñóæåíèå íà Q áóäåì èíîãäà
îáîçíà÷àòü îäíèì è òåì æå ñèìâîëîì.


3.1. Ïðåäïîðÿäêè è ïîðÿäêè                                                                    49


   Åñëè íà ìíîæåñòâå P çàäàíû ïîðÿäêè 1 è 2 è 1 ⊆ 2 (èç x 1 y ñëåäóåò x 2 y
äëÿ âñåõ x, y ∈ P ), òî ãîâîðÿò, ÷òî ïîðÿäîê 1 ñîäåðæèòñÿ â ïîðÿäêå 2 . Ïðè ïîñòðîå-
íèè ïîðÿäêà, ñîäåðæàùåãî äàííûé, ãîâîðÿò î ïðîäîëæåíèè ïîñëåäíåãî. Íàïðèìåð, òðè-
âèàëüíûé ïîðÿäîê íà íåîäíîýëåìåíòíîì ìíîæåñòâå ñîäåðæèòñÿ â ëþáîì äðóãîì è ìîæåò
áûòü ïðîäîëæåí äî íåãî.
   Äëÿ íàãëÿäíîãî ïðåäñòàâëåíèÿ êîíå÷íûõ ÷.ó. ìíîæåñòâ, èìåþùèõ íåáîëüøîå ÷èñëî
ýëåìåíòîâ, èñïîëüçóþò äèàãðàììû (Õàññå) 1 . Íà íèõ èçîáðàæàþò ýëåìåíòû ÷.ó. ìíîæåñòâ,
ïðè÷¼ì åñëè ýëåìåíò a ïðåäøåñòâóåò ýëåìåíòó b, òî a ðèñóþò íèæå b è ñîåäèíÿþò èõ
îòðåçêîì, åñëè ýòî ïðåäøåñòâîâàíèå íåïîñðåäñòâåííîå.
   Ñëåäóåò îòëè÷àòü äèàãðàììû Õàññå îò ïðåäñòàâëåíèÿ ÷.ó. ìíîæåñòâà â âèäå ãðàôà:
äëÿ ïîñëåäíèõ òðåáóåòñÿ ñîåäèíÿòü äóãîé (èëè ðåáðîì) ëþáóþ ïàðó ýëåìåíòîâ, óäîâëå-
òâîðÿþùóþ äàííîìó îòíîøåíèþ, â òî âðåìÿ êàê äëÿ ïåðâûõ ïðåäïîëàãàåòñÿ îòñóòñòâèå
ïåòåëü ó âåðøèí, òðàíçèòèâíîñòü ð¼áåðíûõ ñâÿçåé è îòîáðàæåíèå íàïðàâëåííîñòè ð¼áåð
âçàèìíûì ðàñïîëîæåíèåì âåðøèí (âûøå èëè íèæå îäíà äðóãîé).
   Íà ðèñ. 3.1 ïðèâåäåíû äèàãðàììû Õàññå: íà a)  ÷åòûð¼õýëåìåíòîíîé öåïè (ñì. íèæå),
à íà b) è c)  áóëåàí òð¼õýëåìåíòíîãî ìíîæåñòâà (èëè B 3 ). Ïîñëåäíèå äâå èçîáðàæåíèÿ



         3
                                       [[
                               {1, 2, 3}
                                                                            [[
                                                                    {1, 2, 3}


                                 [[                                      [[
                                                             
         2
                        [[ {1, 3}[[ {2, 3}
                   {1, 2}
                                                              [[ {1, 3}[AA{1, 2}
                                                         {2, 3}
                                                                         [[
                          [ [
                            [       [                             [ AAA[
                                                                  [A
                                                              A
                                                                AA      
         1          {1}
                          [[     {2}         {3}          {1}
                                                              [[ {2}         {3}

                               [[                              [[
                                                                         
                                                                      
         0                        ∅                                    ∅




         a)                       b)                                   c)


                                 Ðèñ. 3.1: Äèàãðàììû Õàññå

ïîêàçûâàþò, ÷òî äàííîãî ÷.ó. ìíîæåñòâà ìîæíî ïîñòðîèòü ìíîãî âèçóàëüíî îòëè÷àþùèõ-
ñÿ äðóã îò äðóãà äèàãðàìì. Ïî âîçìîæíîñòè, èõ ñòàðàþòñÿ ðèñîâàòü áåç ñàìîïåðåñå÷åíèé.
Íà ðèñ. 3.1c) ïðèâåäåíî íåñòàíäàðòíîå èçîáðàæåíèå áóëåâîé àëãåáðû B 3 , èçîìîðôíîå â
òåîðåòèêî-ãðàôîâîì ñìûñëå èçîáðàæ¼ííîìó íà b).
    Ïóñòü h(n)  ÷èñëî íåèçîìîðôíûõ êàê ãðàôîâ äèàãðàìì n-ýëåìåíòíûõ ÷.ó. ìíî-
æåñòâ. ßñíî, íàïðèìåð, ÷òî h(1) = 1, h(2) = 2 è h(3) = 5 (äèàãðàììû òðèâèàëüíî
óïîðÿäî÷åííîãî ìíîæåñòâà è èçîáðàæ¼ííûå íà ðèñ. 3.2).
   1 Õåëüìóò Õàññå (Helmut Hasse, 18981979)  íåìåöêèé ìàòåìàòèê, àâòîð ôóíäàìåíòàëüíûõ ðàáîò ïî
àëãåáðå è òåîðèè ÷èñåë.


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



                                         ◦


                               ◦         ◦          ◦   [[                       ◦

                                                          [                
                    ◦          ◦         ◦          ◦         ◦        ◦         ◦


            Ðèñ. 3.2: Äèàãðàììû íåòðèâèàëüíûõ òð¼õýëåìåíòíûõ ÷.ó. ìíîæåñòâ

   Çíà÷åíèÿ h(n) è, äëÿ ñðàâíåíèÿ, ÷èñëà u(n) óïîðÿäî÷åíèé n-ýëåìåíòíîãî ìíîæåñòâà
äëÿ n 7 ïðèâåäåíû â íèæåñëåäóþùåé òàáëèöå.

                         n     1   2      3    4      5          6        7
                        h(n)   1   2      5    16    63         318     2045
                        u(n)   1   3     19   219   4231      130023   6129856

Êîìïàêòíûõ (íå ïîäðàçóìåâàþùèõ ïåðåáîðà âñåõ èëè ïî÷òè âñåõ ýëåìåíòîâ) ôîðìóë
äëÿ h(n) è u(n) íåèçâåñòíî, è âðÿä ëè îíè ñóùåñòâóþò. Â ïåðâîì ïðèáëèæåíèè ñïðà-
âåäëèâà àñèìïòîòèêà
                                             n2
                                  ln h(n) ∼     ln 2
                                             4
(çäåñü g(n) ∼ f (n) îçíà÷àåò lim g(n)/f (n) = 1).
                                   n→∞
   Èíîãäà äèàãðàììû Õàññå ðèñóþò è äëÿ áåñêîíå÷íûõ ÷.ó. ìíîæåñòâ. Êîíå÷íî, âñå ýëå-
ìåíòû òàêîãî ìíîæåñòâà èçîáðàçèòü íåâîçìîæíî, íî ïîëó÷àþùèåñÿ ðèñóíêè äàþò ÿñíîå
ïðåäñòàâëåíèå îá åãî óñòðîéñòâå. Íà ðèñ. 3.3.a) ïðåäñòàâëåíà áåñêîíå÷íàÿ öåïü N0 , ,
à íà ðèñ. 3.3.b)  áåñêîíå÷íîå ÷.ó. ìíîæåñòâî, âñå öåïè êîòîðîãî êîíå÷íû. Íåêîòîðûå
äèàãðàììû èìåþò ñâîè òðàäèöèîííûå íàçâàíèÿ. Ýòèìè æå èìåíàìè ìû áóäåì ïîëüçî-
âàòüñÿ è äëÿ îáîçíà÷åíèÿ ñîîòâåòñòâóþùèõ ÷.ó. ìíîæåñòâ. È âîîáùå, êîãäà ýòî íå ïðè-
âîäèò ê äâóñìûñëåííîñòè, ìû íå áóäåì ðàçëè÷àòü ÷.ó. ìíîæåñòâî è åãî äèàãðàììó.
     Â ÷.ó. ìíîæåñòâàõ âûäåëÿþò îñîáûå ýëåìåíòû.
Îïðåäåëåíèå 3.4. Ýëåìåíò u ∈ P ÷.ó. ìíîæåñòâà P,                       íàçûâàþò:
     ˆ   ìàêñèìàëüíûì, åñëè u x ⇒ u = x,
     ˆ   ìèíèìàëüíûì, åñëè u x ⇒ u = x,
     ˆ   íàèáîëüøèì, åñëè x u,
     ˆ   íàèìåíüøèì, åñëè x u
äëÿ ëþáûõ x ∈ P .

   Èç îïðåäåëåíèé ÿñíî, ÷òî ýëåìåíò íàèáîëüøèé, åñëè âñå äðóãèå ýëåìåíòû ñîäåðæàòüñÿ
â í¼ì, è îí ìàêñèìàëüíûé, åñëè íåò ýëåìåíòîâ, ñîäåðæàùèõ åãî (àíàëîãè÷íî äëÿ íàè-
ìåíüøåãî è ìèíèìàëüíîãî ýëåìåíòîâ).
   Ëåãêî âèäåòü, ÷òî ÷.ó. ìíîæåñòâî ìîæåò èìåòü íå áîëåå, ÷åì ïî îäíîìó íàèáîëüøåìó è
íàèìåíüøåìó ýëåìåíòó. Èõ íàçûâàþò ñîîòâåòñòâåííî åäèíèöåé è íóë¼ì, à òàêæå óíèâåð-
ñàëüíûìè ãðàíÿìè äàííîãî ÷.ó. ìíîæåñòâà. Äëÿ íèõ ìû áóäåì èñïîëüçîâàòü îáîçíà÷åíèÿ
ι è o. ×.ó. ìíîæåñòâî ñ óíèâåðñàëüíûìè ãðàíÿìè íàçûâàåòñÿ îãðàíè÷åííûì ÷.ó. ìíîæå-
ñòâîì, èëè, êîðî÷å, îãðàíè÷åííûì ïîðÿäêîì. Ïîíÿòíî, ÷òî íàèáîëüøèé [ íàèìåíüøèé ]



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