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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

◦
◦ ◦ ◦ ◦
◦ ◦ ◦ ◦ ◦ ◦ ◦
h(n) u(n) n
n 6 7
n
h(n)
u(n)
h(n) u(n)
ln h(n) ∼
n
2
4
ln 2
g(n) ∼ f(n) lim
n→∞
g(n)/f(n) = 1
h N
0
, 6 i
u ∈ P h P, v i
u v x ⇒ u = x
u w x ⇒ u = x
x v u
x w u
x
∈
P
ι o
50                                              Ãëàâà 3. ×àñòè÷íî óïîðÿäî÷åííûå ìíîæåñòâà



                                         ◦


                               ◦         ◦          ◦   [[                   
                                                                                 ◦

                                                          [                
                    ◦          ◦         ◦          ◦         ◦        ◦         ◦


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

   Çíà÷åíèÿ h(n) è, äëÿ ñðàâíåíèÿ, ÷èñëà u(n) óïîðÿäî÷åíèé n-ýëåìåíòíîãî ìíîæåñòâà
äëÿ n 6 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) ïðåäñòàâëåíà áåñêîíå÷íàÿ öåïü h N0 , 6 i,
à íà ðèñ. 3.3.b)  áåñêîíå÷íîå ÷.ó. ìíîæåñòâî, âñå öåïè êîòîðîãî êîíå÷íû. Íåêîòîðûå
äèàãðàììû èìåþò ñâîè òðàäèöèîííûå íàçâàíèÿ. Ýòèìè æå èìåíàìè ìû áóäåì ïîëüçî-
âàòüñÿ è äëÿ îáîçíà÷åíèÿ ñîîòâåòñòâóþùèõ ÷.ó. ìíîæåñòâ. È âîîáùå, êîãäà ýòî íå ïðè-
âîäèò ê äâóñìûñëåííîñòè, ìû íå áóäåì ðàçëè÷àòü ÷.ó. ìíîæåñòâî è åãî äèàãðàììó.
     Â ÷.ó. ìíîæåñòâàõ âûäåëÿþò îñîáûå ýëåìåíòû.
Îïðåäåëåíèå 3.4. Ýëåìåíò u ∈ P ÷.ó. ìíîæåñòâà h P, v i íàçûâàþò:
     ˆ   ìàêñèìàëüíûì, åñëè u v x ⇒ u = x,
     ˆ   ìèíèìàëüíûì, åñëè u w x ⇒ u = x,
     ˆ   íàèáîëüøèì, åñëè x v u,
     ˆ   íàèìåíüøèì, åñëè x w u
äëÿ ëþáûõ x ∈ P .

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

Страницы