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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A
∼ A/∼
A a
b a ∼ b
A/∼
W u v u ∼ v
W/∼
|W/∼ | = 31
α β
α β
α β
α ∪ β α β
α ∪ β α ∪ β = αβ
(⇐) α β A
(α ∪ β)(a) ⊆ A a ∈ A
A
A
A
(⇒)
[a]
α
[b]
β
c
a ∈ [a]
α
r[b]
β
b ∈ [b]
β
r[a]
α
(a, c) (c, b)
α ∪ β
(a, b)
aαb aβb α ∪ β
2.3. Îòíîøåíèå ýêâèâàëåíòíîñòè                                                           27


   Ìíîæåñòâî, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ êëàññû ýêâèâàëåíòíîñòè ìíîæåñòâà A ïî
îòíîøåíèþ ýêâèâàëåíòíîñòè ∼ íàçûâàåòñÿ ôàêòîðìíîæåñòâîì è îáîçíà÷àåòñÿ A/ ∼.
Ïðèìåð 2.2.   1. Åñëè A  ìíîæåñòâî ç¼ðåí, íàñûïàííûõ â ìåøêè, è äëÿ ç¼ðåí a è
     b ïîëîæèòü a ∼ b, åñëè îíè ëåæàò â îäíîì ìåøêå, òî êëàññàìè ýêâèâàëåíòíîñòè
     ÿâëÿþòñÿ ìíîæåñòâà ç¼ðåí, ëåæàùèõ â îäíîì ìåøêå, à ôàêòîðìíîæåñòâîì A/ ∼ 
     ìíîæåñòâî ìåøêîâ.
  2. Åñëè W  ìíîæåñòâî ñëîâ ðóññêîãî ÿçûêà è äëÿ ñëîâ u è v ïîëîæèòü u ∼ v ,
     åñëè îíè íà÷èíàþòñÿ ñ îäíîé è òîé æå áóêâû (â ðóññêîì ÿçûêå 33 áóêâû), òî
     êëàññàìè ýêâèâàëåíòíîñòè áóäóò ìíîæåñòâà ñëîâ, íà÷èíàþùèõñÿ íà äàííóþ áóê-
     âó, à ôàêòîðìíîæåñòâîì W/∼  ìíîæåñòâî ñîîòâåòñòâóþùèõ áóêâ (çàìåòèì, ÷òî
     |W/∼ | = 31 ).

   Èññëåäóåì òåïåðü ñòàáèëüíîñòü ýêâèâàëåíòíîñòè. ßñíî, íàïðèìåð, ÷òî ýêâèâàëåíò-
íîñòü íå ñòàáèëüíà îòíîñèòåëüíî âçÿòèÿ äîïîëíåíèÿ, ïîñêîëüêó äîïîëíåíèå ýêâèâàëåíò-
íîñòè íå ñîäåðæèò äèàãîíàëüíîãî îòíîøåíèÿ. Ñ äðóãîé ñòîðîíû, ýêâèâàëåíòíîñòü ñòà-
áèëüíà îòíîñèòåëüíî îïåðàöèè ïåðåõîäà ê ïñåâäîîáðàòíîìó îòíîøåíèþ: êàê ñëåäóåò èç
òåîðåìû 2.4 î ñòàáèëüíîñòè ïîëîæèòåëüíûõ ñâîéñòâ îòíîøåíèé, îòíîøåíèå, ïñåâäîîá-
ðàòíîå ê ýêâèâàëåíòíîñòè åñòü ýêâèâàëåíòíîñòü. Èç ýòîé æå òåîðåìû âûòåêàåò

Òåîðåìà 2.7 (Ñòàáèëüíîñòü ïåðåñå÷åíèÿ ýêâèâàëåíòíîñòåé). Îòíîøåíèå ýêâèâà-
ëåíòíîñòè ñòàáèëüíî îòíîñèòåëüíî ïåðåñå÷åíèÿ.

   Îòñþäà â ñâîþ î÷åðåäü ñëåäóåò, ÷òî ïåðåñå÷åíèå ýêâèâàëåíòíîñòåé èç ïðîèçâîëüíîé
íåïóñòîé (âîçìîæíî áåñêîíå÷íîé) ñîâîêóïíîñòè åñòü ýêâèâàëåíòíîñòü.
   Ýêâèâàëåíòíîñòè α è β íà íåêîòîðîì ìíîæåñòâå íàçîâ¼ì êîãåðíòíûìè, åñëè äëÿ
ëþáîé ïàðû ñìåæíûõ êëàññîâ ïî α è ïî β ñîîòâåòñòâåííî ñïðàâåäëèâî óòâåðæäåíèå
¾ëèáî îäèí èç äàííûõ êëàññîâ ëåæèò â äðóãîì, ëèáî îíè íå ïåðåñåêàþòñÿ¿.

Òåîðåìà 2.8 (Î ñòàáèëüíîñòè îáúåäèíåíèÿ ýêâèâàëåíòíîñòåé). Ïóñòü α è β 
ýêâèâàëåíòíîñòè. Òîãäà

  1) îáúåäèíåíèå α ∪ β ÿâëÿåòñÿ ýêâèâàëåíòíîñòüþ åñëè è òîëüêî åñëè α è β êîãå-
     ðåíòíû;
  2) åñëè α ∪ β  ýêâèâàëåíòíîñòü, òî α ∪ β = αβ .

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

  1.  ñèëó òåîðåìû 2.4 äîñòàòî÷íî ïîêàçàòü óêàçàííûé êðèòåðèé îòíîñèòåëüíî òðàí-
     çèòèâíîñòè.
     (⇐) Ïóñòü α è β  êîãåðåíòíûå ýêâèâàëåíòíîñòè íà ìíîæåñòâå A. Ðàññìîòðèì
     âñåâîçìîæíûå îáðàçû (α ∪ β)(a) ⊆ A ïî âñåì ýëåìåíòàì a ∈ A . Ëåãêî âèäåòü,
     ÷òî ïðè óêàçàííîì óñëîâèè äàííûå ïîäìíîæåñòâà A ëèáî ñîâïàäàþò, ëèáî íå ïåðå-
     ñåêàþòñÿ è èõ îáúåäèíåíèå ñîâïàäàåò A. Òàêèì îáðàçîì, îíè îáðàçóþò ðàçáèåíèå
     ìíîæåñòâà A, çàäàâàÿ ýêâèâàëåíòíîñòü íå í¼ì.
     (⇒) Ïóñòü òåïåðü äàííûå ýêâèâàëåíòíîñòè íå êîãåðåíòíû, ò.å. íàéäóòñÿ ñìåæíûå
     êëàññû [a]α è [b]β íå ëåæàùèå îäèí â äðóãîì è ñîäåðæàùèå îáùèé ýëåìåíò c.
     Ìîæíî ñ÷èòàòü, ÷òî a ∈ [a]α r[b]β è b ∈ [b]β r[a]α (ñì. ðèñ. 2.2). Ïàðû (a, c) è (c, b)
     ñîäåðæàòñÿ â α ∪ β . Åñëè áû ýòî îòíîøåíèå áûëî ýêâèâàëåíòíîñòüþ, òî îíî, â ñèëó
     òðàíçèòèâíîñòè, ñîäåðæàëî áû è ïàðó (a, b). Ïîñëåäíåå îçíà÷àåò ñïðàâåäëèâîñòü
     ëèáî aαb, ëèáî aβb. Ýòî, îäíàêî, íå èìååò ìåñòà è, ñëåäîâàòåëüíî, α ∪ β  íå
     ýêâèâàëåíòíîñòü.

Страницы