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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    3.4. Âïîëíå óïîðÿäî÷åííûå ìíîæåñòâà è ñìåæíûå âîïðîñû                                71


ðàç, êàê è â ñëó÷àå ñ ìíîæåñòâîì Ðàññåëà, óáåæäàåìñÿ, ÷òî íå âñÿêîå ñâîéñòâî îïðåäåëÿåò
ìíîæåñòâî.
   Äàëåå â òåîðèè ìíîæåñòâ ïîêàçûâàåòñÿ, ÷òî ìíîæåñòâî êàðäèíàëüíûõ ÷èñåë âïîëíå
óïîðÿäî÷åíî, îòêóäà ïîëó÷àþò ìíîãî âàæíûõ è èíòåðåñíûõ ñëåäñòâèé.
   Óêàæåì, ÷òî íà âïîëíå óïîðÿäî÷åííûå ìíîæåñòâà ìîæíî îáîáùèòü ìåòîä ìàòåìàòè-
÷åñêîé èíäóêöèè.
Òåîðåìà 3.14 (Ïðèíöèï òðàíñôèíèòíîé èíäóêöèè). Ïóñòü P  âïîëíå óïîðÿäî-
÷åííîå ìíîæåñòâî ñ êàæäûì ýëåìåíòîì α êîòîðîãî ñâÿçàíî óòâåðæäåíèå Sα , îáðà-
çóþùèå ñîâîêóïíîñòü S . Òîãäà, åñëè èç ñïðàâåäëèâîñòè Sβ äëÿ âñåõ β ∈ [o, α) ñëåäóåò
ñïðàâåäëèâîñòü Sα , òî âåðíû âñå óòâåðæäåíèÿ èç S .
Äîêàçàòåëüñòâî. Ïóñòü ñðåäè S èìååòñÿ íåâåðíîå óòâåðæäåíèå. Òîãäà íåïóñòî ìíîæåñòâî
E íåâåðíûõ óòâåðæäåíèé. Ïóñòü α  íàèìåíüøèé ýëåìåíò E , êîòîðûé âñåãäà ñóùåñòâó-
åò â ñèëó ïîëíîãî ïîðÿäêà íà P . Íî òîãäà, ïîñêîëüêó Sβ ñïðàâåäëèâî äëÿ âñåõ β ∈ [o, α),
òî ñïðàâåäëèâî è Sα . Ïðîòèâîðå÷èå.
   Ïðè äîêàçàòåëüñòâå ñâîéñòâ ÷.ó. ìíîæåñòâ ìåòîä òðàíñôèíèòíîé èíäóêöèè ÿâëÿåòñÿ
àëüòåðíàòèâíûì èñïîëüçîâàíèþ ëåììû Êóðàòîâñêîãî-Öîðíà. Ñ åãî ïîìîùüþ äîêàæåì
òåîðåìó 2.13, óòâåðæäàþùóþ, ÷òî äëÿ âñÿêîãî ýëåìåíòà ïðîñòðàíñòâà òîëåðàíòíîñòè ñó-
ùåñòâóåò êëàññ òîëåðàíòíîñòè, åãî ñîäåðæàùèé. Ïðåäâàðèòåëüíî óäîñòîâåðèìñÿ â ñïðà-
âåäëèâîñòè ñëåäóþùåé ëåììû.
Ëåììà 3.1. Ïóñòü A,       ïðîñòðàíñòâî òîëåðàíòíîñòè, à C,      âïîëíå óïî-
ðÿäî÷åííîå ìíîæåñòâî, êàæäîìó ýëåìåíòó α êîòîðîãî ñîïîñòàâëåí ïðåäêëàññ òîëå-
ðàíòíîñòè Eα ⊆ A òàê, ÷òî èç α1 < α2 ñëåäóåò Eα1 ⊆ Eα2 . Òîãäà îáúåäèíåíèå
  Eα = E ÿâëÿåòñÿ ïðåäêëàññîì òîëåðàíòíîñòè â A.
Äîêàçàòåëüñòâî. Ïóñòü x, è y  ïðîèçâîëüíûå ýëåìåíòû ìíîæåñòâà E =            Eα . Îïðå-
äåëèì ïîäìíîæåñòâî C(x) ⊆ C ïðàâèëîì

                              C(x) = { ω ∈ C | x ∈ Eα } .

Î÷åâèäíî, ÷òî èç α ∈ C(x) è α < β ñëåäóåò β ∈ C(x).
   Îáîçíà÷èì ÷åðåç α(x) íàèìåíüøèé ýëåìåíò ìíîæåñòâà C(x). Ïóñòü äëÿ îïðåäåë¼í-
íîñòè α(y) α(x). Òàê êàê y ∈ Eα(y) , à Eα(y) ⊆ Eα(x) , òî y ∈ Eα(x) . Ñëåäîâàòåëüíî, x è
y âõîäÿò â îáùèé ïðåäêëàññ, à çíà÷èò x y .
Äîêàçàòåëüñòâî òåîðåìû 2.13 ïðîâåä¼ì ñ ïîìîùüþ òðàíñôèíèòíîé èíäóêöèè.
   1◦ . Áàçèñ èíäóêöèè. Âîçüì¼ì E1 = {x}.  ñèëó ðåôëåêñèâíîñòè , E1 åñòü ïðåä-
êëàññ. Åñëè íåò y = x òàêèõ, ÷òî x = y , òî E1 åñòü êëàññ òîëåðàíòíîñòè. Åñëè æå òàêîé
y ñóùåñòâóåò, òî âûïîëíÿåì øàã èíäóêöèè.
   2◦ . Øàã èíäóêöèè. Åñëè α íå ÿâëÿåòñÿ ïðåäåëüíûì ýëåìåíòîì C , òî, ïîñêîëüêó Eα−1
îïðåäåëåíî, ïîëó÷àåì, ÷òî ëèáî Eα−1 óæå åñòü êëàññ, ëèáî ñóùåñòâóåò y ∈ Eα−1 , òîëå-
ðàíòíûé êî âñåì x ∈ Eα−1 è òîãäà ïîëàãàåì Eα = Eα−1 ∪ {y}.
   Åñëè α  ïðåäåëüíûé ýëåìåíò C , òî, ïîñêîëüêó Eβ îïðåäåëåíû ïðè âñåõ β < α,
ïîëàãàåì Eα = β<α Eβ . Ñîãëàñíî ëåììå 3.1 Eα åñòü ïðåäêëàññ.
   Äëÿ çàâåðøåíèÿ äîêàçàòåëüñòâà äîñòàòî÷íî ïîëîæèòü K =           Eα , ãäå îáúåäèíåíèå
áåð¼òñÿ ïî âñåì òðàíñôèíèòàì α, äëÿ êîòîðûõ Eα îïðåäåëåíî. Î÷åâèäíî, K åñòü ìàê-
ñèìàëüíûé ïðåäêëàññ, ñîäåðæàùèé ýëåìåíò x.
   Èç ýòîãî äîêàçàòåëüñòâà âûâîäÿòñÿ äâå ëåììû.
Ëåììà 3.2. Äëÿ òîãî, ÷òîáû âûïîëíÿëîñü x    y , íåîáõîäèìî è äîñòàòî÷íî ñóùåñòâî-
âàíèå êëàññà òîëåðàíòíîñòè K , îäíîâðåìåííî ñîäåðæàùåãî x è y .


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


Äîêàçàòåëüñòâî. Äîñòàòî÷íîñòü ñëåäóåò èç îïðåäåëåíèÿ êëàññà, à íåîáõîäèìîñòü ïîëó÷à-
åòñÿ èç ïðèâåä¼ííîãî äîêàçàòåëüñòâà òåîðåìû 2.13, åñëè íà ýòàïå áàçèñà èíäóêöèè âçÿòü
ýëåìåíò x, à íà âòîðîì ïðèñîåäèíèòü y .

Ëåììà 3.3 (Î êëàññàõ òîëåðàíòíîñòè). Äëÿ âñÿêîãî ïðåäêëàññà ñóùåñòâóåò ñîäåð-
æàùèé åãî êëàññ.

Äîêàçàòåëüñòâî ñâîäèòñÿ ê çàìå÷àíèþ, ÷òî áàçèñ èíäóêöèè ìîæåò áûòü íà÷àò ñ ëþáîãî
êëàññà.


4.1. Ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà è ðåø¼òêè                                   73


Ãëàâà 4
Àëãåáðàè÷åñêèå ðåø¼òêè
   ¾Êðàñîòà òåîðèè ðåøåòîê îò÷àñòè îáúÿñíÿåòñÿ èñêëþ÷èòåëüíîé ïðîñòîòîé å¼ îñíîâ-
íûõ ïîíÿòèé: óïîðÿäî÷åíèÿ, òî÷íîé âåðõíåé è òî÷íîé íèæíåé ãðàíåé.  ýòîì îòíîøåíèè
îíà î÷åíü íàïîìèíàåò òåîðèþ ãðóïï. Òåîðåòèêî-ðåøåòî÷íûìè ïîíÿòèÿìè ïðîíèçàíà âñÿ
ñîâðåìåííàÿ àëãåáðà, õîòÿ âî ìíîãèõ ó÷åáíèêàõ ýòî îáñòîÿòåëüñòâî ÿâíûì îáðàçîì íå
îòìå÷àåòñÿ.¿ [2].


4.1 Ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà è ðåø¼òêè
Îïðåäåëåíèå 4.1. ×.ó. ìíîæåñòâî, â êîòîðîì äëÿ ëþáûõ ýëåìåíòîâ a è b ñóùåñòâóþò
inf {a, b} è sup {a, b} íàçûâàþò ðåø¼òî÷íî óïîðÿäî÷åííûì (ð.ó.) èëè áèíàïðàâëåííûì.

   ßñíî, ÷òî â ð.ó. ìíîæåñòâå òî÷íûå âåðõíèå è íèæíèå ãðàíè ñóùåñòâóþò äëÿ ëþáîãî
êîíå÷íîãî ïîäìíîæåñòâà ýëåìåíòîâ.
Ïðèìåð 4.1.    1. Ìîäåëè, èçîáðàæ¼ííûå íà ðèñ. 3.1 (ñì. c. 49) ñóòü ðåø¼òî÷íî óïîðÿäî-
     ÷åííûå ìíîæåñòâà.
  2. Ëþáàÿ öåïü ðåø¼òî÷íî óïîðÿäî÷åíà. Ìîäåëè R,            , N, | è P(A), ⊆ ñóòü
     ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà. Ñóïðåìóìû ïàðû ýëåìåíòîâ çäåñü äîñòàâ-
     ëÿþòñÿ ôóíêöèÿìè max, ÍÎÊ è ∪, à èíôèíóìû  ôóíêöèÿìè min, ÍÎÄ è ∩
     ñîîòâåòñòâåííî.
  3. Íà ðèñ. 4.1 ïðåäñòàâëåíû äâà ÷.ó. ìíîæåñòâà, ïðè÷åì ëèøü ïåðâîå èç íèõ ÿâëÿåòñÿ
     ðåø¼òî÷íî óïîðÿäî÷åííûì, ò.ê. âî âòîðîì íå ñóùåñòâóþò sup {a, b} è inf {c, d}.


                         ι   [[                          [[[
                                                          ι

                               [[                    
                                                     
                         [[ [[
                         a                         c
                                                              AA
                                                                 d

                        [
                           [
                               [[
                                                        AA
                                                           AA
                b [                                a[
                                                     AA
                    [[  AAAA
                             c    d                              b
                                                       [[      
                          A
                         AA                            [ 
                       o
                         A                                 o


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

   ×åòûð¼õýëåìåíòíîå ÷.ó. ìíîæåñòâî ñ äèàãðàììîé, èçîáðàæ¼ííîé íà ðèñ. 4.2.2 îáîçíà-
÷èì B (áàáî÷êà). Ïóñòü â íåêîòîðîì ÷.ó. ìíîæåñòâå ñ äèàãðàììîé H çà ýëåìåíòîì
a íåïîñðåäñòâåííî ñëåäóåò ýëåìåíò b. Ìîäèôèöèðóåì äàííîå ìíîæåñòâî, äîáàâèâ ìåæ-
äó ýëåìåíòàìè a è b öåïü èç íîâûõ ñëåäóþùèõ äðóã çà äðóãîì ýëåìåíòîâ a1 , . . . , ak ,
òàê ÷òî a    a1    ...   ak    b. Ïîëó÷åííîå ÷.ó. ìíîæåñòâî áóäåò èìåòü äèàãðàììó
H . Äèàãðàììû Õàññå H è H íàçûâàþò ãîìåîìîðôíûìè. Î÷åâèäíî äèàãðàììà H íå
îïðåäåëÿåò ðåø¼òêó, åñëè îíà ñîäåðæèò ïîääèàãðàììó, ãîìåîìîðôíóþ äèàãðàììå B .


74                                                 Ãëàâà 4. Àëãåáðàè÷åñêèå ðåø¼òêè



                                     ◦   [[ ◦
                                         [
                                     ◦       ◦


                                Ðèñ. 4.2: Áàáî÷êà B

   Ìû ââåëè ïîíÿòèå ð.ó. ìíîæåñòâà, îòòàëêèâàÿñü îò îòíîøåíèÿ ïîðÿäêà. Îäíàêî âîç-
ìîæåí äðóãîé, ýêâèâàëåíòíûé äàííîìó ïîäõîä, îïèðàþùèéñÿ íà àëãåáðàè÷åñêèå îïåðà-
öèè.
Îïðåäåëåíèå 4.2. (Àëãåáðàè÷åñêîé) ðåø¼òêîé L íàçûâàåòñÿ ìíîæåñòâî L ñ çàäàííûìè
íà í¼ì äâóìÿ áèíàðíûìè îïåðàöèÿìè:   (îáúåäèíåíèÿ ) è       (ïåðåñå÷åíèÿ ), ïîä÷èíÿþ-
ùèìèñÿ äâîéñòâåííûì ïàðàì çàêîíîâ Com, Ass, Id è Abs.
   Îòìåòèì, ÷òî ðàíüøå âìåñòî òåðìèíà ¾ðåø¼òêà¿ ÷àñòî óïîòðåáëÿëñÿ òåðìèí ñòðóê-
òóðà. Òåïåðü ïîä ñòðóêòóðîé îáû÷íî (êàê è ìû â äàííîì ïîñîáèè) ïîíèìàþò àëãåáðàè-
÷åñêóþ ñèñòåìó. Ïðè ýòîì ÷àñòî óäîáíî ñ÷èòàòü ðåø¼òêîé ïóñòîå ìíîæåñòâî.
   Ïðèâåä¼ííîå âûøå îïðåäåëåíèå óòâåðæäàåò, ÷òî àëãåáðàè÷åñêàÿ ðåø¼òêà åñòü AC
 L, ,    , äâóõìåñòíûå îïåðàöèè    è    êîòîðîé óäîâëåòâîðÿþò óêàçàííûì çàêîíàì.
Ðàíåå áûëî ïîêàçàíî, ÷òî çàêîíû èäåìïîòåíòíîñòè âûòåêàþò èç çàêîíîâ ïîãëîùåíèÿ,
è ïîýòîìó óêàçàííàÿ ñèñòåìà àêñèîì èçáûòî÷íà. Èñïîëüçîâàíèå èìåííî òàêîé ñèñòåìû
àêñèîì òðàäèöèîííî. Ñëåäñòâèåì å¼ äâîéñòâåííîñòè ÿâëÿåòñÿ
Ïðèíöèï äâîéñòâåííîñòè (äëÿ ðåø¼òîê). Ëþáîå óòâåðæäåíèå äëÿ ïðîèçâîëüíûõ ýëå-
ìåíòîâ, èñòèííîå â íåêîòîðîé ðåø¼òêå, îñòà¼òñÿ èñòèííûì, åñëè â í¼ì ïðîèçâåñòè
çàìåíû âñåõ ñèìâîëîâ ↔ .
   ßñíî, ÷òî áåñêîíå÷íàÿ ðåø¼òêà ìîæåò ñîäåðæàòü, à ìîæåò è íå ñîäåðæàòü óíèâåðñàëü-
íûå ãðàíè (à êîíå÷íàÿ ðåø¼òêà èõ îáÿçàòåëüíî ñîäåðæèò) è äëÿ óíèâåðñàëüíûõ ãðàíåé
o è ι ðåø¼òîê âûïîëíÿþòñÿ çàêîíû o è ι.
Ïðèìåð 4.2.     1. Î÷åâèäíî, ëþáàÿ áóëåâà àëãåáðà åñòü àëãåáðàè÷åñêàÿ ðåø¼òêà. Ñ äðó-
     ãîé ñòîðîíû, ëþáàÿ öåïü åñòü ðåø¼òêà, ÿâëÿÿñü áóëåâîé àëãåáðîé ëèøü ïðè ÷èñëå
     ýëåìåíòîâ, ðàâíîì 2.
  2. ×.ó. ìíîæåñòâî E(A), ⊆ âñåõ îòíîøåíèé ýêâèâàëåíòíîñòè íà ìíîæåñòâå A, ðàñ-
     ñìîòðåííîå â ïðèìåðå 3.4.3, åñòü ðåø¼òêà ñ óíèâåðñàëüíûìè ãðàíÿìè o = A è
     ι = A . Çäåñü äëÿ ýêâèâàëåíòíîñòåé α è β â êà÷åñòâå îáúåäèíåíèÿ âûñòóïàåò
     {α, β}e , à â êà÷åñòâå ïåðåñå÷åíèÿ  îáû÷íîå òåîðåòèêî-ìíîæåñòâåííîå ïåðåñå÷åíèå
     α ∩ β ∈ E(A). Ýòó ðåø¼òêó íàçûâàþò òàêæå ðåø¼òêîé âñåõ ðàçáèåíèé ìíîæåñòâà.
  3. Ìíîæåñòâî Sub G âñåõ ïîäãðóïï ãðóïïû G ñ îïåðàöèÿìè x y = x, y (ïîäãðóïïà
     ïîðîæäåííàÿ îáúåäèíåíèåì ïîäãðóïï x è y ) è x y = x ∩ y (ýòî ìíîæåñòâî, êàê
     èçâåñòíî, âñåãäà ÿâëÿåòñÿ ãðóïïîé) åñòü ðåø¼òêà. Çäåñü o = E (åäèíè÷íàÿ ãðóïïà)
     è ι = G.
   Íà ðèñ. 4.3 èçîáðàæåíû âñå, çà èñêëþ÷åíèåì ëèíåéíîãî ïîðÿäêà, ðåø¼òêè ñ ïÿòüþ
ýëåìåíòàìè. Ïîñëåäíèå ïåðâûå ðåø¼òêè áóäåì íàçûâàòü, ðàêåòêîé (ââåðõ) è ðàêåò-
êîé âíèç, îáîçíà÷àÿ ñîîòâåòñòâåííî, ñîîòâåòñòâåííî, R è R . Ïîñëåäíèå äâå ðåø¼òêè
òðàäèöèîííî íàçûâàþò ïÿòèóãîëüíèê è ðîìá è îáîçíà÷àþò ñîîòâåòñòâåííî N5 è M3 .
   Åñëè L è M  ðåø¼òêè, òî òàêîâûìè æå ÿâëÿþòñÿ L , L ⊕ M è L Ч M . Ïðè ýòîì
L + M íèêîãäà íå áóäåò ðåø¼òêîé, åñëè òîëüêî îäíî èç ìíîæåñòâ L è M íåïóñòî.
Îäíàêî, åñëè ê L + M äîáàâèòü óíèâåðñàëüíûå ãðàíè, òî ïîëó÷åííîå ìíîæåñòâî ñòàíåò
ðåø¼òêîé.


4.1. Ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà è ðåø¼òêè                          75




                      [[
                       ι                                ι

                          [
                c [
                                                       [[
                              b                         a
                    [[
                                                
                                                         [
                         
                          a                     b [          c
                                                    [[    
                                                        
                          o                             o


                         R                             R



                                                      [[
                          ι4                            ι

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


                         N5                            M3


          Ðèñ. 4.3: 5-ýëåìåíòíûå ðåø¼òêè  âñå, êðîìå ëèíåéíîãî ïîðÿäêà


76                                                                        Ãëàâà 4. Àëãåáðàè÷åñêèå ðåø¼òêè


   Ðàññìîòðèì ÷.ó. ìíîæåñòâî N, | .  í¼ì äëÿ ëþáîé ïàðû íàòóðàëüíûõ ÷èñåë m è
n ñóùåñòâóþò íàèìåíüøåå îáùåå êðàòíîå m ∨ n è íàèáîëüøèé îáùèé äåëèòåëü m ∧ n,
èç îïðåäåëåíèé êîòîðûõ ñëåäóåò, ÷òî m ∨ n = sup {m, n} è m ∧ n = inf {m, n}. Òàêèì
îáðàçîì, ðàññìàòðèâàåìîå ÷.ó. ìíîæåñòâî ðåø¼òî÷íî óïîðÿäî÷åííî. Ñ äðóãîé ñòîðîíû,
îïåðàöèè ∨ è ∧ óäîâëåòâîðÿþò çàêîíàì êîììóòàòèâíîñòè, àññîöèàòèâíîñòè, ïîãëîùå-
íèÿ è èäåìïîòåíòíîñòè, è ïîýòîìó N, ∨, ∧  àëãåáðàè÷åñêàÿ ðåø¼òêà. Íàêîíåö, åñëè
â äàííîé ðåø¼òêå ââåñòè îòíîøåíèå δ ïî ïðàâèëó mδn     m ∧ n = m, òî δ îêàçûâàåòñÿ
îòíîøåíèåì ¾äåëèò¿, è, òàêèì îáðàçîì, N, δ  ÷.ó. ìíîæåñòâî.
   Äàííîå ðàññìîòðåíèå íàâîäèò íà ìûñëü, ÷òî àëãåáðàè÷åñêèå ðåø¼òêè è ðåø¼òî÷íî
óïîðÿäî÷åííûå ìíîæåñòâà òåñíî ñâÿçàíû. Ýòî äåéñòâèòåëüíî òàê, è äàííàÿ ñâÿçü óñòà-
íàâëèâàåòñÿ íèæåñëåäóþùåé òåîðåìîé.
Òåîðåìà 4.1 (Ýêâèâàëåíòíîñòü ð.ó. ìíîæåñòâ è ðåø¼òîê).           1. Ïóñòü P,
        ðåø¼òî÷íî óïîðÿäî÷åííîå ìíîæåñòâî. Åñëè äëÿ ëþáûõ ýëåìåíòîâ x è y èç
       P ïîëîæèòü
                        x y     sup {x, y} , x y     inf {x, y},
       òî ñòðóêòóðà             P,       ,         áóäåò àëãåáðàè÷åñêîé ðåø¼òêîé.
     2. Ïóñòü L, ,                       àëãåáðàè÷åñêàÿ ðåø¼òêà. Åñëè äëÿ ëþáûõ ýëåìåíòîâ x è y
        èç L ïîëîæèòü

                                    x        y      x   y=x     (èëè x    y     x    y = y),                    (4.1)

       òî ñòðóêòóðà             L,               áóäåò ðåø¼òî÷íî óïîðÿäî÷åííûì ìíîæåñòâîì.

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

     1. Íåîáõîäèìî ïðîâåðèòü ñïðàâåäëèâîñòü àêñèîì ðåø¼òêè äëÿ ââåä¼ííûõ îïåðàöèé
        è    â ðåø¼òî÷íî óïîðÿäî÷åííîì ìíîæåñòâå P . Âûïîëíåíèå çàêîíîâ êîììóòàòèâ-
        íîñòè è àññîöèàòèâíîñòè î÷åâèäíî. Ïîêàæåì ñïðàâåäëèâîñòü çàêîíîâ ïîãëîùåíèÿ.
       Ïóñòü x è y  ïðîèçâîëüíûå ýëåìåíòû P .

       Abs1: x (x y) = inf {x, sup{x, y}}; èìååì x                              sup {x, y} = z è ïîýòîìó
           inf {x, z} = x.
       Abs2: Ïî äâîéñòâåííîñòè.

     2. Óäîñòîâåðèìñÿ â ñïðàâåäëèâîñòè ñâîéñòâ ðåôëåêñèâíîñòè, àíòèñèììåòðè÷íîñòè è
        òðàíçèòèâíîñòè ó ââåä¼ííîãî îòíîøåíèÿ    â ðåø¼òêå L. Äëÿ ïðîèçâîëüíûõ ýëå-
        ìåíòîâ x, y, z ∈ L èìååì

         R: x       x ⇔ x               x = x;
                x       y                 x       y=x
       AS:                      ⇔                         ⇔ x = y;
                y       x                 y       x=y
         T:
                        x       y                  x    y=y
                                         ⇔                      ⇔ x   y   z=y       z ⇔ x      (y    z) = z .
                        y       z                  y    z=z

       Òàêèì îáðàçîì, L,      åñòü ÷.ó. ìíîæåñòâî. Óáåäèìñÿ, ÷òî îíî ðåø¼òî÷íî óïîðÿ-
       äî÷åíî. Äëÿ x, y ∈ L ñîãëàñíî ââåä¼ííîìó îòíîøåíèþ ïîðÿäêà       ïîëó÷àåì, ÷òî
       x (x y) = x ðàâíîñèëüíî x         x y è àíàëîãè÷íî y     x y . Åñëè z ∈ L, òî

                    x       z
                                    ⇔ (x          y)    z = x   (y    z) = x   z = z ⇔ (x           y)   z.
                    y       z


4.1. Ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà è ðåø¼òêè                                    77


        Ïîýòîìó òî÷íàÿ âåðõíÿÿ ãðàíü ýëåìåíòîâ x è y ñóùåñòâóåò è sup{x, y} = x    y.
        Àíàëîãè÷íî ïîêàçûâàåòñÿ, ÷òî inf{x, y} = x   y . Ñëåäîâàòåëüíî,   L,    ðåø¼-
        òî÷íî óïîðÿäî÷åííîå ìíîæåñòâî.


    Òåîðåìà 4.1 óñòàíàâëèâàåò âçàèìíîîäíîçíà÷íîå ñîîòâåòñòâèå ìåæäó ðåø¼òî÷íî óïî-
ðÿäî÷åííûìè ìíîæåñòâàìè è àëãåáðàè÷åñêèìè ðåø¼òêàìè: èç îäíîé ÀÑ âñåãäà ìîæíî
ïîëó÷èòü äðóãóþ. Ïîýòîìó òåðìèí ¾ðåø¼òêà¿ ïðèìåíÿþò äëÿ îáîèõ ïîíÿòèé, èìåÿ â
âèäó, ÷òî ëþáóþ ðåø¼òêó ìîæíî ïðåäñòàâèòü ëèáî êàê ÷.ó. ìíîæåñòâî, ëèáî êàê àë-
ãåáðó. Íàïðèìåð, ðåø¼òî÷íî óïîðÿäî÷åííûå ìíîæåñòâà R,         , N, | è P(A), ⊆
ïðèìåðà 4.1 ìîæíî çàïèñàòü â âèäå àëãåáðàè÷åñêèõ ðåø¼òîê R, max, min , N, ∨, ∧
è P(A), ∪, ∩ ñîîòâåòñòâåííî. Âîçìîæíîñòü òàêîãî ðàññìîòðåíèÿ ðåø¼òîê ïîçâîëÿåò
ââîäèòü â íèõ êàê ïîðÿäêîâûå, òàê è àëãåáðàè÷åñêèå îïåðàöèè, ÷òî ïðèâîäèò ê áîãàòîé
è ìíîãîîáðàçíîé â ïðèëîæåíèÿõ òåîðèè.
    Àòîìû [ êîàòîìû ] ðåø¼òêè êàê ÷.ó. ìíîæåñòâà ÿâëÿþòñÿ íàçûâàþò àòîìàìè
[ êîàòîìàìè ] ðåø¼òêè.
    Ðåø¼òêà íàçûâàåòñÿ ïîëíîé , åñëè ëþáîå ïîäìíîæåñòâî å¼ ýëåìåíòîâ èìååò òî÷íûå
âåðõíþþ è íèæíþþ ãðàíè (ñð. ñ îïðåäåëåíèåì ïîëíîé áóëåâîé àëãåáðû íà ñ. 17). Íàïðè-
ìåð, îòðåçîê [ 0, 1 ] ñ îáû÷íûì ïîðÿäêîì è ïðîèçâîëüíàÿ òîòàëüíàÿ àëãåáðà ìíîæåñòâ
ÿâëÿþòñÿ ïîëíûìè ðåø¼òêàìè. Âñå ïîëíûå ðåø¼òêè, î÷åâèäíî, äîëæíû èìåòü óíèâåð-
ñàëüíûå ãðàíè, è ïîýòîìó, íàïðèìåð, ìíîæåñòâî âñåõ öåëûõ ÷èñåë ñ îáû÷íûì ïîðÿäêîì
íå ÿâëÿåòñÿ ïîëíîé ðåø¼òêîé.
    ×àñòî èñïîëüçóåòñÿ â ïðèëîæåíèÿõ ñëåäóþùàÿ
Òåîðåìà 4.2. ×àñòè÷íî óïîðÿäî÷åííîå ìíîæåñòâî          P,     ÿâëÿåòñÿ ïîëíîé ðåø¼ò-
êîé, åñëè è òîëüêî åñëè:
 1) îíî èìååò íàèáîëüøèé ýëåìåíò ι ;
 2) äëÿ ëþáîãî åãî íåïóñòîãî ïîäìíîæåñòâà A ñóùåñòâóåò òî÷íàÿ íèæíÿÿ ãðàíü
    inf A.

Äîêàçàòåëüñòâî. (⇐) Ïóñòü P,       ïîëíàÿ ðåø¼òêà. Òîãäà êàæäîå î íåïóñòîå ïîäìíî-
æåñòâî A ⊆ P èìååò è òî÷íóþ íèæíþþ ãðàíü inf A , è òî÷íóþ âåðõíþþ ãðàíü sup A.
 ÷àñòíîñòè, ñóùåñòâóåò sup P = ι.
   (⇒) Ïîêàæåì, ÷òî â óñëîâèÿõ òåîðåìû êàæäîå íåïóñòîå ïîäìíîæåñòâî A ⊆ P èìååò
òî÷íóþ âåðõíþþ ãðàíü. Ðàññìîòðèì A  ñîâîêóïíîñòü âñåõ âåðõíèõ ãðàíåé A.
   Î÷åâèäíî, ι ∈ A , òàê ÷òî A = ∅. Ïî óñëîâèþ ñóùåñòâóåò ýëåìåíò a0 = inf A .
Ýòîò ýëåìåíò è áóäåò òî÷íîé âåðõíåé ãðàíüþ ïîäìíîæåñòâà A.  ñàìîì äåëå, ïóñòü
x ∈ A. Òîãäà x     a äëÿ ëþáîãî a ∈ A . Ñëåäîâàòåëüíî, x ÿâëÿåòñÿ íèæíåé ãðàíüþ
ïîäìíîæåñòâà A . Íî a0  ýòî íàèáîëüøàÿ èç íèæíèõ ãðàíåé ýòîãî ïîäìíîæåñòâà.
Çíà÷èò, x    a0 äëÿ âñåõ ýëåìåíòîâ x ∈ A, ò.å. a0 ∈ A . Òàê êàê a0    a äëÿ ëþáîãî
a ∈ A , òî a0 ïðåäñòàâëÿåò ñîáîé íàèìåíüøèé ýëåìåíò ìíîæåñòâà A , ò.å. íàèìåíüøóþ
èç âåðõíèõ ãðàíåé ïîäìíîæåñòâà A.
   Èòàê, a0 = sup A, îòêóäà çàêëþ÷àåì, ÷òî P,        ïîëíàÿ ðåø¼òêà.
   Ïî äîêàçàííîé òåîðåìå, íàïðèìåð, âñÿêîå âïîëíå óïîðÿäî÷åííîå ìíîæåñòâî ñ íàè-
áîëüøèì ýëåìåíòîì ÿâëÿåòñÿ ïîëíîé ðåø¼òêîé.
Ñëåäñòâèå. Êîíå÷íîå óïîðÿäî÷åííîå ìíîæåñòâî ÿâëÿåòñÿ ðåø¼òêîé, åñëè è òîëüêî
åñëè:
 1) îíî èìååò íàèáîëüøèé ýëåìåíò;


78                                                                                             Ãëàâà 4. Àëãåáðàè÷åñêèå ðåø¼òêè


    2) äëÿ ëþáûõ äâóõ åãî ýëåìåíòîâ ñóùåñòâóåò òî÷íàÿ íèæíÿÿ ãðàíü (ïåðåñå÷åíèå).
     ïðàêòè÷åñêèõ ñèòóàöèÿõ ïðîâåðêà íàëè÷èÿ òî÷íûõ íèæíèõ ãðàíåé ó ïîäìíîæåñòâ
÷.ó. ìíîæåñòâà îáû÷íî íå âûçûâàåò çàòðóäíåíèé, â òî âðåìÿ êàê îòûñêàíèå òî÷íûõ âåðõ-
íèõ ãðàíåé, êàê ïðàâèëî, òðåáóåò çíà÷èòåëüíûõ óñèëèé. Òåîðåìà 4.2 è ñëåäñòâèå 4.1 ÿâ-
ëÿþòñÿ ýôôåêòèâíûìè êðèòåðèÿìè ðåø¼òî÷íîñòè ïîðÿäêîâ.


4.2 Îñíîâíûå ñâîéñòâà ðåø¼òîê. Ðåø¼òî÷íûå ãîìîìîðôèçìû,
    èäåàëû è ôèëüòðû
   Ëåãêî ïîêàçûâàåòñÿ ñïðàâåäëèâîñòü íèæåñëåäóþùåãî óòâåðæäåíèÿ (ôàêòè÷åñêè ìû
óæå ïîêàçûâàëè ñïðàâåäëèâîñòü ñîîòâåòñòâóþùèõ ñîîòíîøåíèé è ïîëüçîâàëèñü èìè ïðè
äîêàçàòåëüñòâå òåîðåìû 4.1).
Óòâåðæäåíèå 4.1. Ýëåìåíòû x, y, u è v ëþáîé ðåø¼òêè L, ,                                                              óäîâëåòâîðÿþò ñëå-
äóþùèì ñîîòíîøåíèÿì:
    1)          x       y   x         x       y;
    2)
                                                       x        y                (x    u) = (y            v)
                                                                        ⇒                                    ;
                                                       u        v                (y    u) = (y            v)
    3)
                                                                             (x       u)       (y     u)
                                                    x        y ⇒                                         .
                                                                             (x       u)       (y     u)

   Ïîíÿòíî òàêæå, ÷òî â ðåø¼òêå                                 L, ,             èç x      z = y          z (è/èëè x       z = y   z ) íå
ñëåäóåò x = y .
Òåîðåìà 4.3. Ýëåìåíòû x, y è z ëþáîé ðåø¼òêè óäîâëåòâîðÿþò ñëåäóþùèì íåðà-
âåíñòâàì ïîëóäèñòðèáóòèâíîñòè
         Dtr1       : (x    y)        z        (x          z)       (y       z);
         Dtr2       : (x    y)        z        (x          z)       (y       z)
è ïîëóìîäóëÿðíîñòè
         M od       :   x   y ⇒ x             (y        z)          y       (x     z) = (x          y)    (x     z);
         M od       :   x   y ⇒ x             (y        z)          y       (x     z) = (x          y)    (x     z).

Äîêàçàòåëüñòâî. Äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ x, y è z ðåø¼òêè èìååì
                                  x       z         x           x       y
                                                                                 ⇒ x       z        (x     y)    z
                                  x       z         z
è
                                 y        z        y            x   y
                                                                                 ⇒ y       x        (x    y)     z.
                                 y        z        z
Òàêèì îáðàçîì, (x                y)       z åñòü âåðõíÿÿ ãðàíü äëÿ x                                z è y       z . Ýòî îçíà÷àåò, ÷òî
                                               (x          z)       (y      z)        (x       y)    z,
è ñëåäîâàíèå Dtr1     äîêàçàíî. Âòîðîå íåðàâåíñòâî ïîëóäèñòðèáóòèâíîñòè ñëåäóåò èç
òîëüêî ÷òî äîêàçàííîãî ïî ïðèíöèïó äâîéñòâåííîñòè.
   Íåðàâåíñòâà ïîëóìîäóëÿðíîñòè åñòü ÷àñòíûé ñëó÷àé íåðàâåíñòâ ïîëóäèñòðèáóòèâíî-
ñòè.


4.2. Ðåø¼òî÷íûå ãîìîìîðôèçìû, èäåàëû è ôèëüòðû                                             79


Îïðåäåëåíèå 4.3. Îòîáðàæåíèå ϕ ðåø¼òêè L â ðåø¼òêó L íàçûâàåòñÿ àëãåáðàè÷å-
ñêèì èëè ðåø¼òî÷íûì ãîìîìîðôèçìîì, åñëè äëÿ ëþáûõ x, y ∈ L ñïðàâåäëèâû ðàâåí-
ñòâà
              ϕ(x y) = ϕ(x) ϕ(y)     è    ϕ(x y) = ϕ(x) ϕ(y).
   Áèåêòèâíûé ðåø¼òî÷íûé ãîìîìîðôèçì åñòü ðåø¼òî÷íûé èçîìîðôèçì. Èçîìîðôèçì
ðåø¼òêè â ñåáÿ íàçûâàåòñÿ àâòîìîðôèçìîì.
   Èíúåêòèâíûå è ñþðúåêòèâíûå ðåø¼òî÷íûå ãîìîìîðôèçìû íàçûâàþò ðåø¼òî÷íû-
ìè (èëè àëãåáðàè÷åñêèìè ) ìîíîìîðôèçìàìè (âëîæåíèÿìè ) è ýïèìîðôèçìàìè ñîîòâåò-
ñòâåííî.
   Ïîðÿäêîâûå ãîìîìîðôèçìû ðåø¼òîê êàê ÷.ó. ìíîæåñòâ, âîîáùå ãîâîðÿ, íå ÿâëÿþòñÿ
àëãåáðàè÷åñêèìè: îòîáðàæåíèå ϕ : P0 (M ) → N0 , ϕ(X) = |X|, X ⊆ M ÿâëÿÿñü èçîòîí-
íûì, íå ñîõðàíÿåò íè îäíó èç ðåø¼òî÷íûõ îïåðàöèé. Íàïðîòèâ, ëþáîå îòîáðàæåíèå îäíîé
ðåø¼òêè íà äðóãóþ, ñîõðàíÿþùåå õîòÿ áû îäíó èç ðåø¼òî÷íûõ îïåðàöèé, èçîòîííî, ò.å.
ÿâëÿåòñÿ ïîðÿäêîâûì ãîìîìîðôèçìîì.
   Äåéñòâèòåëüíî, åñëè ϕ ñîõðàíÿåò ïåðåñå÷åíèå, òî äëÿ ëþáûõ x, y ∈ L èìååì
                     (∗)
 x   y ⇔ x=x      y ⇒
                                 ⇒ ϕ(x) = ϕ(x    y) = ϕ(x)       ϕ(y) ⇔ ϕ(x)   ϕ(y), (4.2)
è, çíà÷èò, ϕ èçîòîííî. Àíàëîãè÷íî èçîòîííîñòü ϕ ñëåäóåò è èç ñîõðàíåíèÿ îáúåäèíåíèÿ.
ßñíî, ÷òî àëãåáðàè÷åñêèé ãîìîìîðôèçì ðåø¼òîê è ïîäàâíî áóäåò èõ ïîðÿäêîâûì ãîìî-
ìîðôèçìîì. Ïîýòîìó ìîæíî ñêàçàòü, ÷òî àëãåáðàè÷åñêèé ãîìîìîðôèçì ðåø¼òîê ñèëü-
íåå ïîðÿäêîâîãî.
     ñëó÷àå èçîìîðôèçìà ïðîáëåìû ñíèìàþòñÿ.
Òåîðåìà 4.4 (Îá ýêâèâàëåíòíîñòè äâóõ âèäîâ èçîìîðôèçìà ðåø¼òîê). Äâå ðå-
ø¼òêè àëãåáðàè÷åñêè èçîìîðôíû, åñëè è òîëüêî åñëè îíè èçîìîðôíû êàê ÷.ó. ìíîæå-
ñòâà.
Äîêàçàòåëüñòâî. (⇐) Ïóñòü ϕ  àëãåáðàè÷åñêèé èçîìîðôèçì ðåø¼òêè L íà íåêîòîðóþ
äðóãóþ ðåø¼òêó. Òàê êàê îòîáðàæåíèå ϕ âçàèìíîîäíîçíà÷íî è èçîòîííî, îñòà¼òñÿ óáå-
                                                                                     (∗)
äèòñÿ â åãî îáðàòíîé èçîòîííîñòè. Ýòî óñòàíàâëèâàåòñÿ îáðàùåíèåì ñëåäîâàíèÿ ⇒ â
(4.2), ÷òî ìîæíî ñäåëàòü â ñèëó âçàèìíîîäíîçíà÷íîñòè ϕ.
    (⇒) Ïóñòü L1 è L2  äâå ðåø¼òêè, èçîìîðôíûå êàê ïîðÿäêè. Äîêàæåì
ñîãëàñîâàííîñòü îïåðàöèè        îòíîñèòåëüíî ïîðÿäêîâîãî èçîìîðôèçìà ϕ, ò.å. ÷òî
ϕ(x y) = ϕ(x) ϕ(y) ïðè óñëîâèè x y ⇔ ϕ(x) ϕ(y) è áèåêòèâíîñòè ϕ.
    Äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ x, y ∈ L1 â ñèëó èçîòîííîñòè ϕ â ðåø¼òêå L2 ýëåìåíò
ϕ(x y) áóäåò íèæíåé ãðàíüþ è ýëåìåíòà ϕ(x), è ýëåìåíòà ϕ(y) : ϕ(x y)        ϕ(x) è
ϕ(x y) ϕ(y). Ïóñòü b òàêæå åñòü íèæíÿÿ ãðàíü ýòèõ ýëåìåíòîâ â L2 . Òîãäà, â ñèëó
ñþðúåêòèâíîñòè ϕ, â L1 íàéäåòñÿ ïðîîáðàç b  ýëåìåíò a è
                               b = ϕ(a)   ϕ(x)        a    x
                                                 ⇔           .
                               b = ϕ(a)   ϕ(y)        a    y
Îòñþäà äàëåå èìååì
                           a    x   y ⇔ b = ϕ(a)     ϕ(x   y).
Òàêèì îáðàçîì, ϕ(x y) áóäåò íàèáîëüøåé íèæíåé ãðàíüþ äëÿ { ϕ(x), ϕ(y) }, èëè, ÷òî
òî æå, ϕ(x y) = ϕ(x) ϕ(y).
   Ñîãëàñîâàííîñòü îïåðàöèè  îòíîñèòåëüíî ϕ ñïðàâåäëèâà ïî äâîéñòâåííîñòè.
   Äàííàÿ òåîðåìà ïîçâîëÿåò íå ðàçëè÷àòü òèïû èçîìîðôèçìà ðåø¼òîê è èñïîëüçîâàòü
                               ϕ
äëÿ íèõ åäèíûé ñèìâîë ∼ (èëè ∼, êîãäà íàäî óêàçàòü èçîìîðôèçì).
                      =        =


80                                                      Ãëàâà 4. Àëãåáðàè÷åñêèå ðåø¼òêè


Òåîðåìà 4.5 (Î íåïîäâèæíîé òî÷êå). Åñëè ϕ  àâòîìîðôèçì ïîëíîé ðåø¼òêè
 L, ,    , òî ϕ(x) = x äëÿ íåêîòîðîãî x ∈ L.
Äîêàçàòåëüñòâî. Ïóñòü Y  ìíîæåñòâî âñåõ òàêèõ ýëåìåíòîâ y ∈ L, ÷òî y ϕ(y). ßñíî,
÷òî Y = ∅, ïîñêîëüêó Y ñîäåðæèò, íàïðèìåð, íóëü ðåø¼òêè x ∈ L. Òîãäà ñóùåñòâóåò
ýëåìåíò x = sup Y è äëÿ âñÿêîãî y ∈ Y èìååì y         ϕ(y)    ϕ(x), îòêóäà x    ϕ(x).
Íî òîãäà ϕ(x)     ϕ(ϕ(x)), ÷òî âëå÷¼ò ϕ(x) ∈ Y , è çíà÷èò, ϕ(x)    x = sup Y . Òàêèì
îáðàçîì, x ϕ(x) x, ò.å. ϕ(x) = x.
   Äîêàçàííàÿ òåîðåìà íå äîïóñêàåò îáðàùåíèÿ: ÷.ó. ìíîæåñòâî Z3 íå ÿâëÿåòñÿ íå òîëü-
êî ïîëíîé ðåø¼òêîé, íî äàæå è ïðîñòî ðåø¼òêîé, îäíàêî âñå åãî àâòîìîðôèçìû, î÷åâèäíî
èìåþò íåïîäâèæíóþ òî÷êó.
   Ñëåäóþùàÿ òåîðåìà ïîêàçûâàåò, êàê ïîïîëíèòü ïðîèçâîëüíîå ÷.ó. ìíîæåñòâî äî (ïîë-
íîé) ðåø¼òêè.
Òåîðåìà 4.6 (Ìàêíèë). Âñÿêîå ÷.ó. ìíîæåñòâî ìîæíî âëîæèòü â ïîäõîäÿùóþ ïîë-
íóþ ðåø¼òêó ñ ñîõðàíåíèåì âñåõ òî÷íûõ ãðàíåé.
Äîêàçàòåëüñòâî. Äëÿ ïðîèçâîëüíîãî ÷.ó. ìíîæåñòâ R, åñëè îíî íå èìååò ìàêñèìàëüíîãî
è/èëè ìèíèìàëüíîãî ýëåìåíòà, äîáàâèì èõ ê R, îáîçíà÷èâ ïîëó÷åííîå ÷.ó. ìíîæåñòâî
R.
   Ïóñòü äàíî ÷.ó. ìíîæåñòâî P . Äëÿ ïîäìíîæåñòâ X ÷.ó. ìíîæåñòâà P îáðàçóåì ìíî-
æåñòâà G(X) = X è L(X) = X ýëåìåíòîâ P . ßñíî, ÷òî îíè íåïóñòû, åñëè X = ∅.
Îáðàçóåì ìíîæåñòâî Q = { L(G(X)) | X ∈ P ∗ (P ) } ñ ïîðÿäêîì ïî âêëþ÷åíèþ. Íåòðóäíî
óñòàíîâèòü, ÷òî Q åñòü èñêîìàÿ ðåø¼òêà.
   Ïðè ïîñòðîåíèè ðåø¼òêè Q ñ óêàçàííûì ñâîéñòâîì ïî äàííîìó ÷.ó. ìíîæåñòâó P ãî-
âîðÿò, ÷òî ïîñëåäíåå ïîïîëíÿåòñÿ ñå÷åíèÿìè Ìàêíèëà , à Q ÿâëÿåòñÿ çàìûêàíèåì (Ìàê-
íèëà) ÷.ó. ìíîæåñòâà P (ñèìâîëè÷åñêè Q = comp(P ) ). Ïðèìåð çàìûêàíèÿ ïîêàçàí íà
ðèñ. 4.4 è 4.5. Íà ïîñëåäíåé äèàãðàììå óíèâåðñàëüíûå ãðàíè è ýëåìåíòû, îòìå÷åííûå
çíàêîì • ñóòü ñå÷åíèÿ Ìàêíèëà.


                    a   [[
                        hh
                                   [[ '''' c [[
                                          b
                                             
                                      ''
                             hh

                          [ '''''[ 
                               hh
                          [           [ 
                                     hh
                                        hh          [
                                                    [
                              ' '             hh
                                                h

                                                   AA
                            d           e             f

                                             A AAA
                                        g AA          h


                                  Ðèñ. 4.4: ×.ó. ìíîæåñòâî P

   Òåîðåìà 4.9 ïîêàçûâàåò, ÷òî çíàìåíèòîå ïîñòðîåíèå Ð. Äåäåêèíäîì äåéñòâèòåëüíûõ
÷èñåë ¾ñå÷åíèÿìè¿ íà ñàìîì äåëå ïðèìåíèìî äëÿ ëþáîãî ÷.ó. ìíîæåñòâà.
Îïðåäåëåíèå 4.4. Íåïóñòîå ïîäìíîæåñòâî L ðåø¼òêè              L, ,     íàçûâàåòñÿ ïîäðå-
ø¼òêîé ðåø¼òêè L (ñèìâîëè÷åñêè L              L), åñëè L óñòîé÷èâî îòíîñèòåëüíî ñóæåíèé
  è .
   Èç îïðåäåëåíèÿ ñëåäóåò, ÷òî ïîäìíîæåñòâî ýëåìåíòîâ ðåø¼òêè L ìîæåò áûòü ðåø¼ò-
êîé îòíîñèòåëüíî ÷àñòè÷íîãî ïîðÿäêà íà L, íî íå ïîäðåø¼òêîé L.



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