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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    3.3. Îïåðàöèè íàä ÷.ó. ìíîæåñòâàìè. Ðàçìåðíîñòü                                      61


   Ïðÿìîå ïðîèçâåäåíèå n ýêçåìïëÿðîâ ÷.ó. ìíîæåñòâ P îáîçíà÷àþò P n . Ñïðàâåäëèâî
ñîîòíîøåíèå

             P ЧQ ∼ P ЧR ⇒ Q ∼ R,
                  =          =               îòêóäà P n ∼ Qn ⇒ P ∼ Q .
                                                        =        =

   Äëÿ òîãî, ÷òîáû ïîëó÷èòü äèàãðàììó ïðÿìîãî ïðîèçâåäåíèÿ ÷.ó. ìíîæåñòâ P è Q

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

Íà ðèñ. 3.9 ïîêàçàíî ïðÿìîå ïðîèçâåäåíèå òð¼õ- è ÷åòûð¼õýëåìåíòíîãî çèãçàãîâ.


                                  ◦[
                              AA AAAA
                                        ◦
                                     [[
                          AAA AA
                      ◦[
                        AA ◦ A ◦
                        A     A
                              AA AAA
                         [[ AA A
                                        ◦                   ◦   [[ ◦
                          A     A                                 [
                      ◦
                        AA ◦ AA
                        A     A                             ◦      ◦


                        Ðèñ. 3.9: Ïðÿìîå ïðîèçâåäåíèå Z3 Ч Z4



Ñòåïåíü. Åñëè       P, P è Q, Q  äâà ÷.ó. ìíîæåñòâà, òî îáîçíà÷èì ÷åðåç QP
ìíîæåñòâî âñåõ èçîòîííûõ îòîáðàæåíèé èç P â Q. Ââåä¼ì íà QP ïîðÿäîê , ïîëîæèâ
f    g äëÿ f, g ∈ QP , åñëè f (x) Q g(x) äëÿ âñåõ x ∈ P . Òàêèì îáðàçîì, QP ,  åñòü
÷.ó. ìíîæåñòâî.
    Ïåðâîå èç íèæåñëåäóþùèõ ñîîòíîøåíèé î÷åâèäíî, à âòîðîå ëåãêî äîêàçûâàåòñÿ:

                                  1P ∼ 1 ,
                                     =       2n ∼ n + 1 .
                                                =
                                          Z
Íà ðèñ. 3.10 ïîêàçàíî ÷.ó. ìíîæåñòâî Z4 3 , ãäå âûäåëåííîìó ýëåìåíòó • ñîîòâåòñòâóåò
îòîáðàæåíèå f : Z3 → Z4 òàêîå, ÷òî f (x1 ) = f (x3 ) = y3 , f (x2 ) = y4 (ñì. ðèñ. 3.6).
   Ìîæíî óáåäèòüñÿ, ÷òî äëÿ ââåä¼ííûõ âûøå îïåðàöèé +, Ч íàä ÷.ó. ìíîæåñòâàìè
âûïîëíÿþòñÿ çàêîíû àññîöèàòèâíîñòè, êîììóòàòèâíîñòè (äëÿ Ч  ñ òî÷íîñòüþ äî èçî-
ìîðôèçìà), ïåðâûé äèñòðèáóòèâíûé çàêîí

                           P Ч (Q + R) ∼ (P Ч Q) + (P Ч R)
                                       =

è äëÿ ñòåïåíè  ñîîòíîøåíèÿ

              RP +Q ∼ RP Ч RQ ,
                    =              (P Q )R ∼ P QЧR ,
                                           =           (P Ч Q)R ∼ P R Ч QR .
                                                                =

Çäåñü P, Q è R  ÷.ó. ìíîæåñòâà è ïðåäïîëàãàåòñÿ, ÷òî ñîîòâåòñòâóþùèå ïðÿìûå ñóì-
ìû. Óêàçàííûå ñîîòíîøåíèÿ, âìåñòå ñ ïðèâåä¼ííûìè âûøå ïðè îïðåäåëåíèè îïåðàöèé,


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




                     AA [[                                    [[[
                         ◦                                   ◦
                       
                 AAA      [                              
             ◦
               AA ◦ 
               A             ◦ [    ◦                   ◦ [        ◦

                              [[                        [[ 
                                                                 
             ◦                                 ◦
                                                             A •
                                                        A AA
             ◦                                 ◦
                                                 A A
                                                 AA

                                                  Z
                              Ðèñ. 3.10: Ñòåïåíü Z4 3


íàçûâàþòñÿ ïðàâèëàìè àðèôìåòèêè îðäèíàëîâ.  ÷àñòíîñòè, ñïðàâåäëèâî âàæíîå äëÿ
ïðàêòè÷åñêèõ ïðèëîæåíèé ñîîòíîøåíèå
                                         P
                             nP ∼ 2n−1
                                =            ∼ 2P Ч(n−1) .
                                             =

    Çàìåòèì, ÷òî äèàãðàììû ñîîòâåòñòâóþùèõ èçîìîðôíûõ ìíîæåñòâ îáû÷íî âûãëÿ-
äÿò ñîâåðøåííî íå ïîõîæèìè äðóã íà äðóãà (äàæå äëÿ çàêîíà êîììóòàòèâíîñòè
P Ч Q ∼ Q Ч P ).
       =
    Ñëåäóåò ñêàçàòü, ÷òî êëàññ âñåõ íåðàçëîæèìûõ â ïðÿìóþ ñóììó èëè ïðîèçâåäåíèå
÷.ó. ìíîæåñòââ òàêæå íåîáîçðèì, êàê è âñåõ èñõîäíûõ. Ïîýòîìó ïðåäñòàâëåíèå ñîâîêóï-
íîñòè ÷.ó. ìíîæåñòââ â âèäå ÀÑ ñ îïåðàöèÿìè + è Ч íå ðåøàåò ïðîáëåìû èõ ¾õîðîøåãî¿
îïèñàíèÿ. Ýòè è ïðî÷èå îïèñàííûå îïåðàöèè ïîëåçíû ïðè ïîñòðîåíèè ÷.ó. ìíîæåñòâ ñî
ñïåöèàëüíûìè ñâîéñòâàìè.
   Ðàññìîòðèì òåïåðü ïðåäñòàâëåíèå ÷àñòè÷íûõ ïîðÿäêîâ â âèäå ïåðåñå÷åíèÿ öåïåé. Îñ-
íîâíîé çäåñü ÿâëÿåòñÿ

Òåîðåìà 3.8 (Øïèëüðàéíà-Äàøíèêà-Ìèëëåðà). Ëþáîé ÷àñòè÷íûé ïîðÿäîê ìî-
æåò áûòü ïðîäîëæåí äî ëèíåéíîãî íà òîì æå ìíîæåñòâå. Êàæäûé ïîðÿäîê åñòü
ïåðåñå÷åíèå ñâîèõ ëèíåéíûõ ïðîäîëæåíèé.

Äîêàçàòåëüñòâî (äëÿ êîíå÷íîãî ñëó÷àÿ). Ïóñòü M,           ÷.ó. ìíîæåñòâî. Ïîñòðîèì
ëèíåéíûé ïîðÿäîê , ñîäåðæàùèé äàííûé ÷àñòè÷íûé.
   Ïî óñëîâèþ M  íå öåïü, è çíà÷èò â M íàéäóòñÿ íåñðàâíèìûå ýëåìåíòû a è b.
Ïðîèçâîëüíî îïðåäåëèì ïîðÿäîê íà íèõ. Äëÿ îïðåäåë¼ííîñòè ïîëîæèì, íàïðèìåð, a b.
Äàëåå äëÿ âñåõ x a è b y ïîëàãàåì x y . Åñëè M,              åù¼ íå öåïü, òî âûáåðåì
íîâóþ ïàðó íåñðàâíèìûõ ýëåìåíòîâ è ïîñòóïàåì, êàê óêàçàíî âûøå. ×åðåç êîíå÷íîå
÷èñëî øàãîâ ïîëó÷àåì ëèíåéíûé ïîðÿäîê.
   Ïîñêîëüêó âîçìîæåí ðàçëè÷íûé âûáîð ïàð íåñðàâíèìûõ ýëåìåíòîâ a è b è ïðè
êàæäîì âûáîðå ìîæíî ïîëàãàòü êàê a b, òàê è b a, òî äåéñòâóÿ óêàçàííûì îáðàçîì
ìîæíî ïîëó÷èòü ðàçëè÷íûå âîçìîæíûå ïðîäîëæåíèÿ èñõîäíîãî ÷àñòè÷íîãî ïîðÿäêà
äî ëèíåéíîãî      (ò.å. åñëè x y , òî è x y ).
   Ïåðåñå÷åíèå âñåõ òàêèõ öåïåé äàñò èñõîäíîå ÷.ó. ìíîæåñòâî. Äåéñòâèòåëüíî, åñëè
x    y , òî àíàëîãè÷íîå ñëåäîâàíèå áóäåò è âî âñåõ ïîëó÷åííûõ ëèíåéíûõ ïîðÿäêàõ, à
ïðè íåñðàâíèìûõ x è y âñåãäà íàéä¼òñÿ ïàðà öåïåé ñ ïðîòèâîïîëîæíûì èõ ñëåäîâàíè-
åì, ÷òî â ïåðåñå÷åíèè öåïåé è äàñò íåñðàâíèìîñòü ýòèõ ýëåìåíòîâ.


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


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

                                                                              n
äëÿ ïðîèçâîëüíûõ x, y ∈ M . Ïîíÿòíî, ÷òî                M,         =     M,         i   .
                                                                              i=1
   Ëèíåéíûé ïîðÿäîê, âêëþ÷àþùèé â ñåáÿ äàííûé ÷àñòè÷íûé ïîðÿäîê        íà íåêîòîðîì
ìíîæåñòâå íàçûâàþò ëèàíåðèçàöèåé èñõîäíîãî ïîðÿäêà . Èç äîêàçàííîé òåîðåìû ñëå-
äóåò ïðîñòîé àëãîðèòì ïîñòðîåíèÿ íåêîòîðîé ëèàíåðèçàöèè êîíå÷íîãî ÷.ó. ìíîæåñòâà P :
âûäåëÿåì ìíîæåñòâî ìèíèìàëüíûõ ýëåìåíòîâ P è ëèíåéíî óïîðÿäî÷èâàåì åãî ïðîèç-
âîëüíîì îáðàçîì, èñêëþ÷àåì ýòî ìíîæåñòâî èç P , îáðàçóÿ ÷.ó. ïîäìíîæåñòâî P ⊂ 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 ñïðàâåäëèâî ðàçëîæåíèå

                                               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 }  íîñèòåëü ÷.ó. ìíîæåñòâà P, . Â n-ìåðíîì åâêëèäîâîì ïðî-
ñòðàíñòâå Rn îïðåäåëèì ìíîãîãðàííèê P :

                 P = { (x1 , . . . , xn ) ∈ Rn | 0      xi    1, vi      v j ⇒ xi           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].


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


Ïðèìåð 3.10. Ðàññìîòðèì ÷.ó. ìíîæåñòâî P = { v1 , v2 , v3 } ∼ Z3 â êîòîðîì v1
                                                                         =         v2 ,
v1    v3 è v2   v3 . Òîãäà âûøåîïðåäåë¼ííûé ìíîãîãðàííèê P åñòü ÷åòûð¼õóãîëüíàÿ
ïèðàìèäà, îñíîâàíèåì êîòîðîé ñëóæèò êâàäðàò (000), (001), (011), (010), âåðøèíîé 
òî÷êà (111), à âûñîòà ñîâïàäàåò ñ áîêîâûì ðåáðîì (111) − (011) (ñì. ðèñ. 3.11). Òàêèì
îáðàçîì, vol(P) = 3 . Îòñþäà e(P ) = 3! = 2 è ìíîæåñòâî ëèíåéíûõ ïðîäîëæåíèé P
                     1
                                              3
ñîñòîèò èç äâóõ öåïåé [v1 , v2 , v3 ] è [v1 , v3 , v2 ] (ñì. ðèñ. 3.12).


                                             x3
                                              u




                                         (001)
                                                  [[               (011)


                                                 [[        
                                                           
                              ◦   \\                   (111)
                                                            [[
                                     \  \                      [[
                                         (000)
                                                  \\               (010)        w x2
                                                 \\    
                                                      
                              ◦                          ◦

                      
                    
                    
                    
               x1


                                  Ðèñ. 3.11: Ìíîãîãðàííèê P(Z3 )




                                                              v3           v2


                        v2
                             [[      v3                       v2           v3

                               [ 
                                   v1                         v1           v1


                    Ðèñ. 3.12: ×.ó. ìíîæåñòâî Z3 è åãî ëèíåàðèçàöèè)

   Ïîíÿòíî, ÷òî â îáùåì ñëó÷àå P åñòü ìíîãîãðàííîå ìíîæåñòâî â Rn , îãðàíè÷åííîå
ãèïåðïëîñêîñòÿìè âèäà xi = xj (äëÿ êàæäûõ i, j òàêèõ, ÷òî vi íåïîñðåäñòâåííî ïðåä-
øåñòâóåò vj èëè íàîáîðîò) è çàêëþ÷¼ííîå â åäèíè÷íûé êóá. Çàäà÷à, òàêèì îáðàçîì,


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


ñâîäèòñÿ ê âû÷èñëåíèþ îáú¼ìà óêàçàííîãî ìíîãîãðàííèêà3 .
   ßñíî, ÷òî ÷.ó. ìíîæåñòâî P ñîâïàäàåò ñ ïåðåñå÷åíèåì âñåõ e(P ) ñâîèõ âîçìîæíûõ
ëèàíåðèçàöèé. Îäíàêî, òîò æå ðåçóëüòàò ìîæíî ïîëó÷èòü, âçÿâ çíà÷èòåëüíî ìåíüøåå
÷èñëî ëèíåéíûõ ïðîäîëæåíèé.
Ïðèìåð 3.11. ×.ó. ìíîæåñòâî
                                b       c     [[d
                                                [ 
                                                     a
ìîæåò áûòü ïðåäñòàâëåíî è êàê ïåðåñå÷åíèå òð¼õ öåïåé
                   A = [ a, b, c, d ],       B = [ a, c, d, b ],   C = [ a, d, b, c ]
è êàê ïåðåñå÷åíèå äâóõ  A è D = [ a, d, c, b ].
Îïðåäåëåíèå 3.11. Íàèìåíüøåå ÷èñëî ëèíåéíûõ ïîðÿäêîâ, äàþùåå â ïåðåñå÷åíèè äàí-
íîå ÷.ó. ìíîæåñòâî P íàçûâàåòñÿ (ïîðÿäêîâîé) ðàçìåðíîñòüþ ïîñëåäíåãî è îáîçíà÷àåòñÿ
dim(P ).
   Ñïðàâåäëèâà
Òåîðåìà 3.9 (Îðå [10]). Ïîðÿäêîâàÿ è ìóëüòèïëèêàòèâíàÿ ðàçìåðíîñòè ÷.ó. ìíîæå-
ñòâà ñîâïàäàþò.
   Äàííàÿ òåîðåìà ïîçâîëÿåò íå ðàçëè÷àòü óêàçàííûå âèäû ðàçìåðíîñòè è ïîëüçîâàòüñÿ
äëÿ å¼ îáîçíà÷åíèÿ åäèíûì ñèìâîëîì dim(P ). Çíà÷åíèå dim(P ) ÿâëÿåòñÿ áîëåå òîíêîé
îöåíêîé ñëîæíîñòè ÷.ó. ìíîæåñòâà P , ÷åì e(P ).
   Ðàçìåðíîñòü 1 èìåþò òîëüêî öåïè. Ëåãêî ïîêàçûâàåòñÿ, ÷òî ðàçìåðíîñòü òðèâèàëüíî
óïîðÿäî÷åííûõ ìíîæåñòâ è âñåõ, îòëè÷íûõ îò öåïåé ÷.ó. ìíîæåñòâ, èìåþùèõ íå áîëåå,
÷åì 5 ýëåìåíòîâ, ðàâíà 2. Ðàçìåðíîñòü 2 èìåþò è âñå 6-ýëåìåíòíûå ìíîæåñòâà, êðîìå
öåïè 6 è ò.í. êîðîíû S3 , øåâðîíà C è C (ñì. ðèñ. 3.13), èìåþùèå ðàçìåðíîñòü 3.


                                                               ◦ [[      
                                                                           ◦

                                                                    [ 
                                                                       
                  d   [[  e [[ f                              ◦ [   ◦
                                                                   [[ 
                                                                           ◦

                        [ [  
                      
                             [                                       
                                                                       
                  a          b           c                                ◦


                       Êîðîíà S3                                    Øåâðîí C


                  Ðèñ. 3.13: 6-ýëåìåíòíûå ÷.ó. ìíîæåñòâà ðàçìåðíîñòè 3

Ïðèâåä¼ì ðàçëîæåíèå S3 â ïåðåñå÷åíèå öåïåé:
                S3 = [ a, b, d, c, e, f ] ∩ [ c, a, e, b, f, d ] ∩ [ c, b, f, a, e, d ].

   Óñòàíîâëåíî, ÷òî äëÿ ÷.ó. ìíîæåñòâ P è Q ñïðàâåäëèâû ñëåäóþùèå ñîîòíîøåíèÿ:
   3 Äëÿ ýòîãî âîçìîæíî ïðèìåíåíèå ìåòîäà Ìîíòå-Êàðëî ñ ïîëó÷åíèåì îöåíîê vol(P) âåðîÿòíîñòíîãî
òèïà.


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


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

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



                                    ' '
                                   4[ ' b2 4[ ' b3 4[[ b4 4A[ b5
                                               [[ [4[h[ 4A
                              b1
                                    4 [h''4 h''4 A[[ hA4
                                      4 h [ 4 h[[AAh[
                                             'h4' A ['  h4h
                                                     'h4 [
                                           [ 4 [
                                       h4 [h[A'[ h 4 ' h 4
                                     h4[A[[['[[ '[[4
                                    h A4A h A[ h' 4 h'
                                         [ 4  '
                                h[ h[ h
                                 [ a [ a              '  h
                              a1
                                 A       2      3       a4       a5


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

   ×.ó. ìíîæåñòâî P íàçûâàåòñÿ d-íåïðèâîäèìûì äëÿ íåêîòîðîãî d              2, åñëè
dim(P ) = d è dim(P ) < d äëÿ ëþáîãî ñîáñòâåííîãî ÷.ó. ïîäìíîæåñòâà P ⊂ 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 ñîäåðæèòñÿ â íåêîòîðîì ìàêñèìàëüíîì.
Ïðèíöèï Õàóñäîðôà. Âñÿêàÿ öåïü ÷.ó. ìíîæåñòâà ìîæåò áûòü âëîæåíà â íåêîòîðóþ
    ìàêñèìàëüíóþ öåïü.


3.4. Âïîëíå óïîðÿäî÷åííûå ìíîæåñòâà è ñìåæíûå âîïðîñû                                            67


   Äàííûå óòâåðæäåíèÿ ÷àñòî ïðèìåíÿþò ïðè äîêàçàòåëüñòâå ñâîéñòâ ÷.ó. ìíîæåñòâ.
Íàïðèìåð, äëÿ äîêàçàòåëüñòâà òåîðåìû Øïèëüðàéíà (3.8) äëÿ ñ÷åòíîãî áåñêîíå÷íîãî
óïîðÿäî÷åííîãî ìíîæåñòâà äîêàçàòåëüñòâî àíàëîãè÷íî.
   Îêàçàëîñü, ÷òî ýòè óòâåðæäåíèÿ ýêâèâàëåíòíû. Áîëåå òîãî, îíè òàêæå ýêâèâàëåíòíû
ôóíäàìåíòàëüíûì òåîðåòèêî-ìíîæåñòâåííûì àêñèîìàì âûáîðà è î ïîëíîì óïîðÿäî÷å-
íèè.

Àêñèîìà âûáîðà (AC). Äëÿ ëþáîãî ìíîæåñòâà A = ∅ ñóùåñòâóåò îòîáðàæåíèå fA ,
     ñîïîñòàâëÿþùåå êàæäîìó íåïóñòîìó ïîäìíîæåñòâó B ìíîæåñòâà A ýëåìåíò èç B :
     fA (B) ∈ B äëÿ ëþáîãî B ∈ P ∗ (A).

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

   Ìíîæåñòâî P áóäåò âïîëíå óïîðÿäî÷åííûì òîãäà è òîëüêî òîãäà, êîãäà îíî óäîâëåòâî-
ðÿåò óñëîâèþ ìèíèìàëüíîñòè, ò.å. êîãäà íå ñóùåñòâóåò áåñêîíå÷íûõ ñòðîãî óáûâàþùèõ
ïîñëåäîâàòåëüíîñòåé ýëåìåíòîâ èç P .
   Òðàíñôèíèòû òðàäèöèîííî îáîçíà÷àþò ñòðî÷íûìè ãðå÷åñêèìè áóëàâàìè α, β, . . ..
ßñíî, ÷òî âïîëíå óïîðÿäî÷åííîå ìíîæåñòâî âñåãäà ñîäåðæèò íàèìåíüøèé ýëåìåíò (o).
Âî âïîëíå óïîðÿäî÷åííîì ìíîæåñòâå êàæäûé ýëåìåíò α , åñëè òîëüêî îí íå ÿâëÿåòñÿ
íàèáîëüøèì, èìååò åäèíñòâåííûé íåïîñðåäñòâåííî ñëåäóþùèé, îáîçíà÷àåìûé α + 1 è
ìîæåò èìåòü íå áîëåå îäíîãî íåïîñðåäñòâåííî ïðåäøåñòâóþùåãî (ýòè ñâîéñòâà ëåãêî ïà-
êàçûâàþòñÿ). Ýëåìåíò âïîëíå óïîðÿäî÷åííîãî ìíîæåñòâà íå èìåþùèé íåïîñðåäñòâåííî
ïðåäøåñòâóþùåãî, åñëè òîëüêî îí íå ÿâëÿåòñÿ íàèìåíüøèì, íàçûâàåòñÿ ïðåäåëüíûì.
Ïðèìåð 3.12.   1. Î÷åâèäíî, âïîëíå óïîðÿäî÷åíû âñå êîíå÷íûå öåïè, à òàê æå öåïü N
    ñ åñòåñòâåííûì ïîðÿäêîì. Â ýòèõ öåïÿõ íåò ïðåäåëüíûõ ýëåìåíòîâ.
     Ìíîæåñòâî öåëûõ ÷èñåë Z íå ÿâëÿåòñÿ âïîëíå óïîðÿäî÷åííûì îòíîñèòåëüíî åñòå-
     ñòâåííîãî ïîðÿäêà, ïîñêîëüêó îíî íå èìååò íàèìåíüøåãî ýëåìåíòà. Èíòåðâàë [ 0, 1 ]
     äåéñòâèòåëüíûõ ÷èñåë ñ îáû÷íûì ïîðÿäêîì  òàêæå íå åñòü âïîëíå óïîðÿäî÷åííîå
     ìíîæåñòâî.
  2. Ìíîæåñòâî

                          1 2 3                1     2                1     2
                     0,    , , , . . . , 1, 1 + , 1 + , . . . , m, m + , m + , . . .
                          2 3 4                2     3                2     3

     ñ åñòåñòâåííûì ïîðÿäêîì ÿâëÿåòñÿ âïîëíå óïîðÿäî÷åííûì. Åãî ïðåäåëüíûå ýëåìåí-
     òû ñóòü íàòóðàëüíûå ÷èñëà.

Àêñèîìà î ïîëíîì óïîðÿäî÷åíèè (òåîðåìà Öåðìåëî). Ëþáîå íåïóñòîå ìíîæåñòâî
     ìîæíî âïîëíå óïîðÿäî÷èòü.

Ïðèìåð 3.13. Ìíîæåñòâî öåëûõ ÷èñåë Z ìîæíî âïîëíå óïîðÿäî÷èòü ñ÷èòàÿ, íàïðèìåð,
÷òî
        0 < 1 < −1 < 2 < −2 < 3 . . . èëè 1 < 2 < . . . < 0 < −1 < −2 < . . .
(â ïîñëåäíåì ñëó÷àå 0  ïðåäåëüíûé ýëåìåíò).
  4 Îáùåïðèíÿòîå   îáîçíà÷åíèå ÀÑ äëÿ íå¼ åñòü àááðåâèàòóðà àíãëèéñêîãî òåðìèíà ¾axiom of choice¿.


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


   Ïîêàæåì, ê ïðèìåðó, êàê àêñèîìó âûáîðà ìîæíî ïîëó÷èòü èç àêñèîìû î ïîëíîì
óïîðÿäî÷åíèè. Ïóñòü A  íåïóñòîå ìíîæåñòâî; ïî àêñèîìå î ïîëíîì óïîðÿäî÷åíèè åãî
ìîæíî ñ÷èòàòü âïîëíå óïîðÿäî÷åííûì. Òîãäà â îïðåäåëåíî îòîáðàæåíèå, ñòàâÿùåå â ñî-
îòâåòñòâèå êàæäîìó íåïóñòîìó ïîäìíîæåñòâó A åãî ýëåìåíò, à èìåííî  íàèìåíüøèé.
   Îòìåòèì, ÷òî èçâåñòíû è äðóãèå óòâåðæäåíèÿ, ýêâèâàëåíòíûå ïðèâåä¼ííûì: íàïðè-
ìåð, î ðàâíîìîùíîñòè ìíîæåñòâ X è X Ч X èëè î íåïóñòîòå äåêàðòîâà ïðîèçâåäåíèÿ
ïðîèçâîëüíîé ñîâîêóïíîñòè íåïóñòûõ ìíîæåñòâ. Äîêàçàòåëüñòâî ýêâèâàëåíòíîñòè óïî-
ìÿíóòûõ óòâåðæäåíèé ìîæíî íàéòè, íàïðèìåð, â [13].
   Òàêèì îáðàçîì, èñòèííûìè èëè ëîæíûìè âñå ýòè óòâåðæäåíèÿ ìîãóò áûòü òîëüêî
îäíîâðåìåííî. ×òî æå èìååò ìåñòî â äåéñòâèòåëüíîñòè? Îòâåò íà ïîñòàâëåííûé âîïðîñ
çàâèñèò îò òîãî, êàêèìè ñâîéñòâàìè ìû íàäåëÿåì ïîíÿòèå ìíîæåñòâà. Â íàèáîëåå îáùåé
ôîðìå ïðîáëåìà âûðàæåíà â àêñèîìå âûáîðà, ïðåäëîæåííîé Ý. Öåðìåëî â 1904 ã. ïðè
ðàçðàáîòêå àêñèîìàòè÷åñêîé òåîðèè ìíîæåñòâ. Äëÿ êîíå÷íûõ ìíîæåñòâ å¼ ñïðàâåä-
ëèâîñòü î÷åâèäíà. Îäíàêî ïðè ðàññìîòðåíèè áåñêîíå÷íûõ ñîâîêóïíîñòåé áåñêîíå÷íûõ
ìíîæåñòâ ýòà î÷åâèäíîñòü òåðÿåòñÿ. Âñå æå ïîïûòêè ñâåñòè AC ê äðóãèì ôóíäàìåíòàëü-
íûì ïðèíöèïàì îêàçàëèñü áåçóñïåøíûìè: â àêñèîìàòèêå ZF Öåðìåëî-Ôðåíêåëÿ òåîðèè
ìíîæåñòâ5 íå âûâîäèìû íè îòðèöàíèå àêñèîìû âûáîðà (Ê. üäåëü, 1939), íè îíà ñàìà
(Ï. Êîýí, 1963). Òàêèì îáðàçîì, AC ÿâëÿåòñÿ íåçàâèñèìûì îò ZF óòâåðæäåíèåì, è äî-
áàâëåíèå ê ZF êàê ñàìîé ýòîé àêñèîìû, òàê è å¼ îòðèöàíèÿ ïîðîæäàåò äâå ðàâíîïðàâíûå
íåïðîòèâîðå÷èâûå àêñèîìàòèêè òåîðèè ìíîæåñòâ (åñòåñòâåííî, ïðè óñëîâèè íåïðîòèâî-
ðå÷èâîñòè ñàìîé ñèñòåìû ZF , ÷òî, êàê èçâåñòíî, ÿâëÿåòñÿ îòêðûòûì âîïðîñîì). Ïîýòîìó
ïðè ïðàêòè÷åñêèõ, íå ñâÿçàííûõ ñ âîïðîñàìè îñíîâàíèé ìàòåìàòèêè è òåîðèè ìíîæåñòâ
èññëåäîâàíèÿõ ìîæíî êàê ïðèíÿòü àêñèîìó âûáîðà, òàê è îòêàçàòüñÿ îò íå¼. Ïîñëåäñòâèÿ
æå òàêîãî ðåøåíèÿ ñóòü ñëåäóþùèå.
   Îòêëîíåíèå àêñèîìû âûáîðà îáåäíÿåò ñîäåðæàíèå êîíêðåòíûõ ìàòåìàòè÷åñêèõ òåî-
ðèé. Íàïðèìåð, áåç ïðèâëå÷åíèÿ ÀÑ, êðîìå óïîìÿíóòûõ ïîëåçíûõ óñëîâèé ñóùåñòâîâà-
íèÿ ýêñòðåìàëüíûõ ýëåìåíòîâ ÷.ó. ìíîæåñòâ, íå óäàåòñÿ äîêàçàòü íè íàëè÷èå áàçèñà ó
ïðîèçâîëüíîãî âåêòîðíîãî ïðîñòðàíñòâà, íè ýêâèâàëåíòíîñòè äâóõ îïðåäåëåíèé íåïðå-
ðûâíîñòè ôóíêöèè â òî÷êå (íà ÿçûêå εδ è ÷åðåç ïðåäåëû ïîñëåäîâàòåëüíîñòåé), íè
íåêîòîðûõ äðóãèõ âàæíûõ è ïðèâû÷íûõ ñâîéñòâ ðàçëè÷íûõ ìàòåìàòè÷åñêèõ îáúåêòîâ.
   Ïðèíÿòèå àêñèîìû âûáîðà èìååò ñâîè îòðèöàòåëüíûå ïîñëåäñòâèÿ â âèäå ñóùåñòâî-
âàíèÿ îáúåêòîâ ñ ïàðàäîêñàëüíûìè ñâîéñòâàìè: íåèçìåðèìîãî ïî Ëåáåãó ìíîæåñòâà äåé-
ñòâèòåëüíûõ ÷èñåë; òàêîãî ðàçáèåíèÿ øàðà íà ÷åòûðå ÷àñòè, ÷òî èç íèõ äâèæåíèÿìè â
ïðîñòðàíñòâå îêàçûâàåòñÿ âîçìîæíûì ñîñòàâèòü äâà òàêèõ æå øàðà è äð. Îäíàêî âñå ýòè
îáúåêòû íåêîíñòðóêòèâíû è îáîñíîâûâàþòñÿ òåîðåìàìè ÷èñòîãî ñóùåñòâîâàíèÿ6 . Êðî-
ìå òîãî, çà ïðèíÿòèå àêñèîìû âûáîðà ãîâîðèò è ñëåäóþùèé, âåñüìà ñèëüíûé, àðãóìåíò.
Êàê îòìå÷àëîñü âûøå, üäåëü ïîêàçàë, ÷òî ïðèñîåäèíåíèå àêñèîìû âûáîðà ê ñèñòåìå ZF
íå óâåëè÷èâàåò îïàñíîñòè âïàñòü â ïðîòèâîðå÷èå, ò.å. åñëè â ïîëó÷åííîé ñèñòåìå âñòðå-
òèëîñü ïðîòèâîðå÷èå, òî ïðè÷èíà åãî â ZF , à íå â àêñèîìå âûáîðà. Èç ðåçóëüòàòà üäåëÿ
òàêæå âûòåêàåò, ÷òî âñÿêîå ñâîéñòâî íàòóðàëüíûõ ÷èñåë, äîêàçûâàåìîå ñ ïîìîùüþ àê-
ñèîìû âûáîðà, ìîæåò áûòü äîêàçàíî è áåç íå¼. Â ñèëó ýòîãî, ïî êðàéíåé ìåðå â òåîðèè
íàòóðàëüíûõ ÷èñåë, àêñèîìó âûáîðà ìîæíî ðàññìàòðèâàòü ëèøü êàê âñïîìîãàòåëüíîå
ñðåäñòâî, íóæíîå ëèøü äëÿ óïðîùåíèÿ äîêàçàòåëüñòâ.
   Ïîñëåäíèå ñîîáðàæåíèÿ îáû÷íî ïåðåâåøèâàþò, è ïðè êîíêðåòíûõ ìàòåìàòè÷åñêèõ
èññëåäîâàíèÿõ àêñèîìó âûáîðà, êàê ïðàâèëî, ïðèíèìàþò7 . Ïðè ýòîì äîêàçàòåëüñòâà, íå
     5 Ñì., íàïðèìåð, À. Ôðåíêåëü, È. Áàð-Õèëëåë. Îñíîâàíèÿ òåîðèè ìíîæåñòâ.  Ì.: Ìèð, 1966.
     6 Îáû÷íî èñïîëüçóåìîå âûðàæåíèå ¾÷èñòàÿ òåîðåìà ñóùåñòâîâàíèÿ¿ ÿâëÿåòñÿ íåòî÷íûì ïåðåâîäîìñ
íåìåöêîãî.
   7 Ä. Ãèëüáåðò â 1923 ã. íàçâàë àêñèîìó âûáîðà îáùèì, íåîáõîäèìûì è íåîöåíèìûì äëÿ ìàòåìàòèêè
ïðèíöèïîì. Ñ äðóãîé ñòîðîíû, å¼ ïðèìåíåíèå âûçâàëî íåãîäîâàíèå ìíîãèõ âåäóùèõ ìàòåìàòèêîâ íà÷àëà


3.4. Âïîëíå óïîðÿäî÷åííûå ìíîæåñòâà è ñìåæíûå âîïðîñû                                            69


èñïîëüçóþùèå àêñèîìó âûáîðà èëè ýêâèâàëåíòíûå åé óòâåðæäåíèÿ íàçûâàþò ýôôåêòèâ-
íûìè.
   Çàìåòèì, ÷òî äàííîå ïîñîáèå îñòà¼òñÿ â ðàìêàõ ò.í. íàèâíîé òåîðèè ìíîæåñòâ, êîòî-
ðàÿ ïîçâîëÿåò ðàññìàòðèâàòü ìíîæåñòâà, çàäàâàåìûå ïðîèçâîëüíûì ñâîéñòâîì. Íåîãðà-
íè÷åííîå ïðèìåíåíèå ýòîãî ïðèíöèïà, êàê èçâåñòíî, ìîæåò ïðèâåñòè ê ïðîòèâîðå÷èÿì
(ïàðàäîêñàì). Ïðèâåä¼ì çäåñü ïàðàäîêñ Ðàññåëà 8 : ìíîæåñòâî Ðàññåëà R = { x | x ∈ x },
êîððåêòíî çàäàííîå â ðàìêàõ íàèâíîé òåîðèè ìíîæåñòâ, õàðàêòåðèçóåòñÿ ñïðàâåäëèâî-
ñòüþ ñîîòíîøåíèÿ z ∈ R ⇔ z ∈ z äëÿ ëþáîãî ìíîæåñòâà z , ÷òî ïðè z = R ïðèâîäèò
ê ïðîòèâîðå÷èþ R ∈ R ⇔ R ∈ R.  àêñèîìàòè÷åñêîé òåîðèè ìíîæåñòâ ZF (êàê è
â äðóãèõ íå ýêçîòè÷åñêèõ òåîðèÿõ) íè R, íè ìíîæåñòâî, ñîäåðæàùåå ñåáÿ â êà÷åñòâå
ñâîåãî ýëåìåíòà, íå ìîãóò áûòü ïîñòðîåíû9 .
   Äëÿ âïîëíå óïîðÿäî÷åííîãî ìíîæåñòâà îïðåäåëÿþò ìíîæåñòâî [ o, α )       α     {α},
êîòîðîå íàçûâàþò íà÷àëüíûì îòðåçêîì α. Ñèìâîë [ o, o ) ïîíèìàåòñÿ êàê ïóñòîå ìíîæå-
ñòâî. Ïðåäåëüíûé ýëåìåíò α âïîëíå óïîðÿäî÷åííîãî ìíîæåñòâà C,           îïðåäåëÿåòñÿ
óñëîâèÿìè α = o è îòñóòñòâèåì â [ o, α ) íàèáîëüøåãî ýëåìåíòà. Ñëåäóþùèé çà α ýëå-
ìåíò α + 1  íàèìåíüøèé âî ìíîæåñòâå α        {α}.
   Îòìåòèì âàæíåéøèå ñâîéñòâà âïîëíå óïîðÿäî÷åííûõ ìíîæåñòâ C,          .
Òåîðåìà 3.10. Ïóñòü C  âïîëíå óïîðÿäî÷åííîå ìíîæåñòâî. Òîãäà
 1) åñëè C òàêæå âïîëíå óïîðÿäî÷åíî, òî C  êîíå÷íàÿ öåïü.
 2) åñëè α  ïðåäåëüíûé òðàíñôèíèò, òî

                                         [ o, α ) =     [ o, β ) .
                                                      β<α



Äîêàçàòåëüñòâî.
 1) Ïîñêîëüêó C è C âïîëíå óïîðÿäî÷åíû, òî C ñîäåðæèò óíèâåðñàëüíûå ãðàíè o
    è ι , êàæäûé å¼ ýëåìåíò, îòëè÷íûé îò ι èìååò ïîñëåäóþùèé, à êàæäûé ýëåìåíò,
    îòëè÷íûé îò o  ïðåäøåñòâóþùèé. Òàêèì îáðàçîì, â C îòñóòñòâóþò ïðåäåëüíûå
    ýëåìåíòû, âñå å¼ ñå÷åíèÿ  ñêà÷êè, ÷òî âìåñòå ñ íàëè÷èåì óíèâåðñàëüíûõ ãðàíåé
    îçíà÷àåò êîíå÷íîñòü C .
 2) Åñëè γ ∈ [ o, α ), òî ïîñêîëüêó ìåæäó γ è γ + 1 ýëåìåíòîâ íåò, γ + 1                α.
    Îäíàêî, â ñèëó ïðåäåëüíîñòè α, ðàâåíñòâî íåâîçìîæíî. Òàêèì îáðàçîì,
    γ ∈ [ o, γ + 1 ) ⊆ β<α [ o, β ), ò.å. [ o, α ) ⊆ β<α [ o, β ). Îáðàòíîå âêëþ÷åíèå î÷å-
    âèäíî.


   Ðåøàþùèì ìîìåíòîì, îáåñïå÷èâàþùèì âîçìîæíîñòü ñðàâíèâàòü ïðîèçâîëüíûå ìíî-
æåñòâ ÿâëÿåòñÿ
Òåîðåìà 3.11 (Î ñðàâíåíèè âïîëíå óïîðÿäî÷åííûõ ìíîæåñòâ). Ïóñòü A è B 
äâà âïîëíå óïîðÿäî÷åííûõ ìíîæåñòâà. Òîãäà èìååòñÿ ëèøü îäíà èç ñëåäóþùèõ âîç-
ìîæíîñòåé:
XX âåêà.
   8 Ïàðàäîêñ áûë îáíàðóæåí Á. Ðàññåëîì è ñîîáù¼í â 1902 ã. â ïèñüìå ê ìàòåìàòèêó è ëîãèêó Ã. Ôðåãå,
÷òî ïðèâåëî ïîñëåäíåãî ê óìñòâåííîìó ðàññòðîéñòâó. Îäíà èç íåôîðìàëüíûõ èíòåðïðåòàöèé ïàðàäîê-
ñà Ðàññåëà: ¾Â îäíîé ñòðàíå âûøåë óêàç: Ìýðû âñåõ ãîðîäîâ äîëæíû æèòü íå â ñâîåì ãîðîäå, à â
ñïåöèàëüíîì Ãîðîäå ìýðîâ; ñïðàøèâàåòñÿ, ãäå äîëæåí æèòü ìýð Ãîðîäà ìýðîâ?¿.
   9 Ïðèâåä¼ì ïðèìåð ìíîæåñòâà, ñîäåðæàùåãî ñåáÿ. Çàôèêñèðóåì íåêîòîðûé îáúåêò a è ðàññìîòðèì
ñîâîêóïíîñòü Na âñåõ ìíîæåñòâ, íå ñîäåðæàùèõ a. Äëÿ íåãî èìååì Na ∈ Na .


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


 1)   A    ∼ B;
           =
 2)   A    èçîìîðôíî íà÷àëüíîìó îòðåçêó B ;
 3)   B    èçîìîðôíî íà÷àëüíîìó îòðåçêó A.

   Äîêàçàòåëüñòâî ýòîé òåîðåìû èìååòñÿ, íàïðèìåð, â [14].
   Ìíîæåñòâà A è B íàçîâ¼ì ðàâíîìîùíûìè , ÷òî áóäåì îáîçíà÷àòü êàê A = B , åñëè
ìåæäó A è B ñóùåñòâóåò áèåêòèâíîå îòîáðàæåíèå.  ïðîòèâíîì ñëó÷àå áóäåì ãîâîðèòü,
÷òî îíè íåðàâíîìîùíû è ïèñàòü A = B . Çäåñü ïîä X ïîíèìàåòñÿ íîâûé îáúåêò, ñâÿçàí-
íûé ñ ìíîæåñòâîì X , íàçûâàåìûé êàðäèíàëüíûì ÷èñëîì X èëè êàðäèíàëîì. Îïðå-
äåëåíèå òàêîãî îáúåêòà âîçìîæíî ïî ïðèíöèïó àáñòðàêöèè, ñîãëàñíî êîòîðîìó ýêâèâà-
ëåíòíûì ìíîæåñòâàì ìîæíî ñîïîñòàâèòü íåêîòîðûé àáñòðàêòíûé îáúåêò (êàðäèíàëüíîå
÷èñëî)  òî îáùåå, ÷òî äåëàåò èõ ýêâèâàëåíòíûìè10 .

Òåîðåìà 3.12 (Çàêîí òðèõîòîìèè). Äëÿ ëþáûõ ìíîæåñòâ A è B èìååòñÿ ëèøü
îäíà èç ñëåäóþùèõ âîçìîæíîñòåé:

 1) A = B ;
 2) A = B äëÿ íåêîòîðîãî B ⊆ B , íî A = B äëÿ ëþáîãî A ⊆ A;
 3)   B = A äëÿ íåêîòîðîãî A ⊆ A, íî B = A äëÿ ëþáîãî B ⊆ B .

Äîêàçàòåëüñòâî. Îòìåòèì, ÷òî óòâåðæäåíèÿ òåîðåìû ïîïàðíî íåñîâìåñòèìû. Äàëåå, èñ-
ïîëüçóÿ àêñèîìó î ïîëíîì óïîðÿäî÷åíèè çàêëþ÷àåì, ÷òî äëÿ A è B ñïðàâåäëèâà òåî-
ðåìà 3.11. Îòñþäà ëèáî ñïðàâåäëèâû óòâåðæäåíèÿ 2)3) äàííîé òåîðåìû, ëèáî âûïîëíÿ-
þòñÿ óñëîâèÿ òåîðåìû 2.20 Êàíòîðà-Øð¼äåðà-Áåðíøòåéíà. Ïîñëåäíåå æå âëå÷¼ò âûïîë-
íåíèå óñëîâèÿ 1).
   Äàííàÿ òåîðåìà ëåæèò â îñíîâå ó÷åíèÿ î ìîùíîñòè ìíîæåñòâ. Îíà ïîçâîëÿåò ââåñòè
ïîðÿäîê íà ìíîæåñòâå êàðäèíàëüíûõ ÷èñåë, à èìåííî ñ÷èòàòü, ÷òî A < B è A > B
ñîîòâåòñòâåííî â ñëó÷àÿõ 2) è 3) äàííîé òåîðåìû (ïîíÿòíî, ÷òî åñëè A ⊆ B , òî A B ,
ïðè ýòîì âîçìîæåí ñëó÷àé A = B ).

Òåîðåìà 3.13 (Êàíòîð). A < P(A).
Äîêàçàòåëüñòâî. Ñîïîñòàâèâ êàæäîìó ýëåìåíòó a ∈ A îäíîýëåìåíòíîå ïîäìíîæåñòâî {a}
ìíîæåñòâà A, ïîëó÷èì âëîæåíèå A â P(A), è ïîýòîìó A       P(A).
   Äîïóñòèì òåïåðü, ÷òî ñóùåñòâóåò âçàèìíî îäíîçíà÷íîå îòîáðàæåíèå ϕ ìíîæåñòâà A
â P(A). Âî ìíîæåñòâå A îïðåäåëèì ïîäìíîæåñòâî M :

                                 M = {a ∈ A | a ∈ ϕ(a)} ∈ P(A).

Ïî îïðåäåëåíèþ ϕ, äîëæåí ñóùåñòâîâàòü ýëåìåíò m ∈ A òàêîé, ÷òî ϕ(m) = M . Ïðè
ïîïûòêå âûÿñíèòü, ïðèíàäëåæèò ëè äàííûé ýëåìåíò ìíîæåñòâó M , ïîëó÷àåì ïðîòè-
âîðå÷èå. Äåéñòâèòåëüíî, åñëè m ∈ M , òî m ∈ ϕ(m) = M , à åñëè m ∈ M , èìååì
m ∈ ϕ(m) = M .
   Çàìåòèì, ÷òî èç òåîðåìû Êàíòîðà ñðàçó ñëåäóåò ïàðàäîêñ Êàíòîðà, ïîêàçûâàþùèé,
÷òî ìíîæåñòâà âñåõ ìíîæåñòâ íå ñóùåñòâóåò. Äåéñòâèòåëüíî, äëÿ ìíîæåñòâà âñåõ ìíî-
æåñòâ V ñïðàâåäëèâî P(V ) ⊆ V è, ñëåäîâàòåëüíî, P(V ) V , ÷òî ïðîòèâîðå÷èò òåîðåìå
Êàíòîðà. Ìíîæåñòâî V ìîæíî ôîðìàëüíî îïðåäåëèòü êàê V = {x | x = x}, è ìû åù¼
 10 Ñð.   ñ ïðèíöèïîì àáñòðàêöèè îòîæäåñòâëåíèÿ íà ñ. 26



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