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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

ϕ L L
0
x, y ∈ L
ϕ(x t y) = ϕ(x) t ϕ(y) ϕ(x u y) = ϕ(x) u ϕ(y).
ϕ : P
0
(M) → N
0
, ϕ(X) = |X| X ⊆ M
ϕ x, y ∈ L
x v y ⇔ x = x u y
(∗)
⇒
⇒ ϕ(x) = ϕ(x u y) = ϕ(x) u ϕ(y) ⇔ ϕ(x) v ϕ(y),
ϕ ϕ
(⇐) ϕ L
ϕ
(∗)
⇒
ϕ
(⇒) L
1
L
2
u ϕ
ϕ(x u y) = ϕ(x) u ϕ(y) x v y ⇔ ϕ(x) v ϕ(y) ϕ
x, y ∈ L
1
ϕ L
2
ϕ(x u y) ϕ(x) ϕ(y) ϕ(x u y ) v ϕ(x)
ϕ(x u y) v ϕ(y) b L
2
ϕ L
1
b a
½
b = ϕ(a) v ϕ(x)
b = ϕ(a) v ϕ(y)
⇔
½
a v x
a v y
.
a v x u y ⇔ b = ϕ(a) v ϕ(x u y).
ϕ(x u y) { ϕ(x), ϕ(y) }
ϕ(x u y) = ϕ(x) u ϕ(y)
t ϕ ¤
∼
=
ϕ
∼
=
4.2. Ðåø¼òî÷íûå ãîìîìîðôèçìû, èäåàëû è ôèëüòðû                                       79


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

   Äàííàÿ òåîðåìà ïîçâîëÿåò íå ðàçëè÷àòü òèïû èçîìîðôèçìà ðåø¼òîê è èñïîëüçîâàòü
                               ϕ
                      = (èëè ∼
äëÿ íèõ åäèíûé ñèìâîë ∼        =, êîãäà íàäî óêàçàòü èçîìîðôèçì).

Страницы