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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

M C
M X Y ⊆ M
X ⊆ C(X)
X ⊆ Y ⇒ C(X) ⊆ C(Y )
C(C(X)) = C(X)
X C(X) = X
ρ
t
ρ
ρ ρ
e
ρ ρ
ρ
t
ρ
e
ρ
+
=
∞
S
n=1
ρ
n
aρ
+
b
x
0
= a x
1
, . . . x
n
= b
x
0
ρx
1
N . . . N x
n−1
ρx
n
ρ
+
ρ = ρ
+
ρ
α ⊆ β ⇒ α
+
⊆ β
+
ρ α β
ρ ρ
t
= ρ
+
ρ ⊆ ρ
t
⊆ ρ
+
ρ
+
⊆ ρ
t
⊆ ρ
+
ρ
t
= ρ
+
¤
ρ ρ
e
= (M ∪ρ ∪ ρ
]
)
t
σ = (ρ ∪ ρ
]
∪ M) ρ
e
ρ
M ρ
]
σ ⊆ ρ
e
ρ
e
σ
t
⊆ ρ
e
σ
t
ε ρ
ρ ⊆ ε ⇒ ρ
]
⊆ ε
]
= ε ⇒ σ ⊆ ε ⇒ σ
n
⊆ ε
n
⊆ ε ⇒
∞
[
n=1
σ
n
⊆ ε ⇔ σ
t
⊆ ε .
¤
R R
e
=
¡
M ∪
S
ρ∈R
ρ ∪
S
ρ∈R
ρ
]
¢
t
2.3. Îòíîøåíèå ýêâèâàëåíòíîñòè                                                        29


Òåîðåìà 2.10 (Î ïðîèçâåäåíèè ïåðåñòàíîâî÷íûõ ýêâèâàëåíòíîñòåé). Äëÿ ïå-
ðåñòàíîâî÷íûõ ýêâèâàëåíòíîñòåé ïðîèçâåäåíèå ÿâëÿåòñÿ íàèìåíüøåé ýêâèâàëåíòíî-
ñòüþ, èõ ñîäåðæàùåé.

   Íèæå ìû óêàæåì ñïîñîá ïîñòðîåíèÿ íàèìåíüøåé ýêâèâàëåíòíîñòè, ñîäåðæàùåé äàí-
íîå îòíîøåíèå. Îíî èñïîëüçóåò ïîíÿòèå çàìûêàíèÿ, â äàííîì ñëó÷àå  çàìûêàíèÿ îò-
íîøåíèÿ. Âîîáùå, ïîíÿòèå çàìûêàíèÿ (íåôîðìàëüíî  ïðèñîåäèíåíèÿ íåêîòîðîãî ìèíè-
ìàëüíî íåîáõîäèìîãî êîëè÷åñòâà íîâûõ îáúåêòîâ ê äàííîìó) ÿâëÿåòñÿ ôóíäàìåíòàëüíûì
è ÷àñòî èñïîëüçóåòñÿ â ðàçëè÷íûõ îáëàñòÿõ ìàòåìàòèêè.
   Îïåðàòîðîì çàìûêàíèÿ íà íåïóñòîì ìíîæåñòâå M íàçûâàþò îòîáðàæåíèå C ìíî-
æåñòâà âñåõ ïîäìíîæåñòâ M â ñåáÿ, îáëàäàþùåå äëÿ âñåõ X , Y ⊆ M ñëåäóþùèìè
ñâîéñòâàìè:

  1. X ⊆ C(X)  ðåôëåêñèâíîñòü,
  2. X ⊆ Y ⇒ C(X) ⊆ C(Y )  ìîíîòîííîñòü,
  3. C(C(X)) = C(X)  èäåìïîòåíòíîñòü.

Ìíîæåñòâî X íàçûâàåòñÿ çàìêíóòûì, åñëè C(X) = X .

Îïðåäåëåíèå 2.7. Íàèìåíüøåå òðàíçèòèâíîå îòíîøåíèå ρ t , ñîäåðæàùåå îòíîøåíèå ρ,
íàçûâàåòñÿ òðàíçèòèâíûì çàìûêàíèåì ρ. Íàèìåíüøàÿ ýêâèâàëåíòíîñòü ρ e , ñîäåðæà-
ùàÿ îòíîøåíèå ρ, íàçûâàåòñÿ ýêâèâàëåíòíûì çàìûêàíèåì ρ.
   Çàìûêàíèå ñîâîêóïíîñòè îòíîøåíèé åñòü çàìûêàíèå èõ îáúåäèíåíèÿ.

   Ëåãêî ïðîâåðèòü, ÷òî ïîëó÷åíèå ρ t è ρ e ìîæíî ïðåäñòàâèòü êàê ðåçóëüòàò äåéñòâèÿ
ñîîòâåòñòâóþùèõ îïåðàòîðîâ çàìûêàíèÿ.
   Òðàíçèòèâíîå çàìûêàíèå äàííîãî îòíîøåíèÿ ëåãêî ñòðîèòñÿ. Ââåä¼ì îáîçíà÷åíèå
       S
       ∞
ρ+ =      ρn . Ïî îïðåäåëåíèþ ïðîèçâåäåíèÿ îòíîøåíèé ñïðàâåäëèâîñòü aρ+ b îçíà÷àåò
      n=1
ñóùåñòâîâàíèå òàêèõ ýëåìåíòîâ x0 = a, x1 , . . ., xn = b ñîîòâåòñòâóþùåãî ìíîæåñòâà,
÷òî x0 ρx1 N . . . N xn−1 ρxn . ßñíî, ÷òî ρ+ òðàíçèòèâíî, ρ = ρ+ , åñëè òðàíçèòèâíî ρ è
α ⊆ β ⇒ α+ ⊆ β + äëÿ îäíîðîäíûõ îòíîøåíèé ρ, α è β .
Óòâåðæäåíèå 2.1. Åñëè ρ  îäíîðîäíîå îòíîøåíèå, òî ρ t = ρ+ .
Äîêàçàòåëüñòâî. Èìååì ρ ⊆ ρt ⊆ ρ+ , îòêóäà ρ+ ⊆ ρt ⊆ ρ+ , ò.å. ρ t = ρ+ .             ¤

   Òåïåðü ìîæíî êîíñòðóêòèâíî îïðåäåëèòü ýêâèâàëåíòíîå çàìûêàíèå îòíîøåíèÿ.

Óòâåðæäåíèå 2.2. Åñëè ρ  îäíîðîäíîå îòíîøåíèå, òî ρe = (M ∪ρ ∪ ρ] )t .
Äîêàçàòåëüñòâî. Îáîçíà÷èì σ = (ρ ∪ ρ] ∪ M). Îòíîøåíèå ρe äîëæíî, êðîìå ρ, ñîäåðæàòü
M è ρ] , ïîýòîìó σ ⊆ ρe . Â ñèëó òðàíçèòèâíîñòè ρe èìååì σ t ⊆ ρe , îòêóäà σ t ÿâëÿåòñÿ
ýêâèâàëåíòíîñòüþ.
   Ïóñòü òåïåðü ε  íåêîòîðàÿ ýêâèâàëåíòíîñòü, ñîäåðæàùàÿ ρ. Òîãäà
                                                            ∞
                                                            [
                   ]    ]                    n    n
         ρ⊆ε ⇒ ρ ⊆ε = ε ⇒ σ⊆ε ⇒ σ ⊆ε ⊆ε ⇒                         σn ⊆ ε ⇔ σt ⊆ ε .
                                                            n=1

                                                                                      ¤
                                                                   ¡     S    ¢t  S
   Ïîíÿòíî, ÷òî åñëè R  ñîâîêóïíîñòü îòíîøåíèé, òî Re = M ∪ ρ∈R ρ ∪ ρ∈R ρ] .
Çäåñü âàæíûì ÷àñòíûì ñëó÷àåì ÿâëÿåòñÿ ýêâèâàëåíòíîå çàìûêàíèå ñîâîêóïíîñòè ýêâè-
âàëåíòíîñòåé.

Страницы