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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

R E
∼ R
∼ ⊆ E
E ⊆ ∼ ¤
{α, β}
e
= (α ∪ β)
e
=
∞
[
n=1
(α ∪ β)
n
α β
αβ, βα, αβα, βαβ . . .
α β
{α, β}
e
= (α ∪ β)
e
= α ∪ β = αβ
ρ
∗
ρ M ∪ρ
+
ρ
∗
=
∞
S
n=0
ρ
n
α
m α n , m + 1 = n α
t
= < α
∗
= 6
A = {1, 2, 3, 4, 5, 6, 7, 8}
α β {1, 2}, {3, 4}, {5, 6, 7}, {8}
{1, 4}, {2, 3}, {5, 6}, {7}, {8} (α ∪ β)
e
{1, 2, 3, 4} { 5, 6, 7} {8}
A = {a, b, c, d, e, f} α β
{a, b}, {c}, {d}, {e, f} {a}, {b, c}, {d, e}, {f}
(a, c) ∈ αβ (c, a) 6∈ αβ (c, a) ∈ βα (a, c) 6∈ βα
α β αβ βα
{α, β}
e
αβ ∪ βα
{a, b, c} {d, e, f}
α β A β ⊆ α
β
α A β
α β
α A/β
α/β
[x]
β
(α/β) [y]
β
, [x]
α
= [y]
α
x, y ∈ A β
α/β α xαy
A B ρ ∈ A × B
ρ Ker ρ ∈ E(A)
a
1
(Ker ρ) a
2
,
∀
B
b ( a
1
ρb = a
2
ρb )
30                                                     Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Òåîðåìà 2.11. Ýêâèâàëåíòíîå çàìûêàíèå ñîâîêóïíîñòè ýêâèâàëåíòíîñòåé ñîâïàäàåò
ñ îáúåäèíåíèåì âñåâîçìîæíûõ ïðîèçâåäåíèé ýòèõ ýêâèâàëåíòíîñòåé.
Äîêàçàòåëüñòâî. Ïóñòü R  ñîâîêóïíîñòü ýêâèâàëåíòíîñòåé è E  îáúåäèíåíèå âñå-
âîçìîæíûõ èõ ïðîèçâåäåíèé. Òîãäà äëÿ ëþáîé ýêâèâàëåíòíîñòè ∼ èç R ñîãëàñíî ï. 1
òåîðåìû 2.3 î ñâîéñòâàõ ïðîèçâåäåíèÿ îòíîøåíèé èìååì ∼ ⊆ E , à ñîãëàñíî å¼ ï. 3 
E ⊆ ∼, îòêóäà è ñëåäóåò òðåáóåìîå.                                              ¤


Ñëåäñòâèÿ.      1. Ýêâèâàëåíòíîå çàìûêàíèå
                                                        ∞
                                                        [
                                      e            e
                               {α, β} = (α ∪ β) =           (α ∪ β)n
                                                        n=1

       äâóõ ýêâèâàëåíòíîñòåé α è β ñîâïàäàåò ñ îáúåäèíåíèåì âñåâîçìîæíûõ ïðîèçâå-
       äåíèé âèäà αβ, βα, αβα, βαβ . . ..
     2. Åñëè     α     è   β       ïåðåñòàíîâî÷íûå     ýêâèâàëåíòíîñòè,  òî
        {α, β}e = (α ∪ β)e = α ∪ β = αβ (ïîñëåäíåå ðàâåíñòâî åñòü óòâåðæäåíèå
        òåîðåìû 2.10).

   Ðåôëåêñèâíûì (òî÷íåå  ðåôëåêñèâíî-òðàíçèòèâíûì) çàìûêàíèåì ρ∗ îäíîðîäíîãî
                                                         S
                                                         ∞
îòíîøåíèÿ ρ íàçûâàþò îòíîøåíèå M ∪ρ+ ; ïîíÿòíî, ÷òî ρ∗ =   ρn .
                                                                    n=0
Ïðèìåð 2.5.     1. Åñëè α  îòíîøåíèå íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë, îïðåäåëÿåìîå
     ïðàâèëîì m α n , m + 1 = n, òî αt = < è α∗ = 6.
  2. Ïóñòü íà ìíîæåñòâå A = {1, 2, 3, 4, 5, 6, 7, 8} çàäàíû ýêâèâàëåíòíîñòè
     α è β ñî ñìåæíûìè êëàññàìè ñîîòâåòñòâåííî {1, 2}, {3, 4}, {5, 6, 7}, {8} è
     {1, 4}, {2, 3}, {5, 6}, {7}, {8}. Òîãäà ýêâèâàëåíòíîñòü (α ∪ β)e ïîðîæäàåò ñìåæíûå
     êëàññû {1, 2, 3, 4}, {5, 6, 7} è {8}.
  3. Ïóñòü íà ìíîæåñòâå A = {a, b, c, d, e, f } çàäàíû ýêâèâàëåíòíîñòè α è β ñî ñìåæ-
     íûìè êëàññàìè {a, b}, {c}, {d}, {e, f } è {a}, {b, c}, {d, e}, {f } ñîîòâåòñòâåííî. Òî-
     ãäà (a, c) ∈ αβ , íî (c, a) 6∈ αβ è (c, a) ∈ βα, íî (a, c) 6∈ βα. Òàêèì îáðàçîì,
     ýêâèâàëåíòíîñòè α è β íå ïåðåñòàíîâî÷íû è íè αβ , íè βα ýêâèâàëåíòíîñòÿìè
     íå ÿâëÿþòñÿ. Ýêâèâàëåíòíîå çàìûêàíèå {α, β}e (ñîâïàäàþùåå ñ αβ ∪ βα ) èìååò
     ñìåæíûå êëàññû {a, b, c} è {d, e, f }.
   Ïóñòü α è β  äâå ýêâèâàëåíòíîñòè íà ìíîæåñòâå A. Îòíîøåíèå âêëþ÷åíèÿ β ⊆ α
äëÿ íèõ îçíà÷àåò, ÷òî ëþáîé ñìåæíûé êëàññ ïî β ëåæèò â íåêîòîðîì ñìåæíîì êëàññå ïî
α. Èíûìè ñëîâàìè, ðàçáèåíèå ìíîæåñòâà A íà ñìåæíûå êëàññû ïî β åñòü ïîäðàçáèåíèå
åãî ðàçáèåíèÿ íà ñìåæíûå êëàññû ïî α. Ãîâîðÿò òàêæå, ÷òî ðàçáèåíèå ïî β åñòü èçìåëü-
÷åíèå ðàçáèåíèÿ ïî α. Äëÿ òàêèõ ýêâèâàëåíòíîñòåé îïðåäåëèì íà ôàêòîðìíîæåñòâå A/β
äðîáíóþ ýêâèâàëåíòíîñòü α/β ïî ïðàâèëó

                               [x]β (α/β) [y]β , [x]α = [y]α

äëÿ ïðîèçâîëüíûõ x, y ∈ A. Òàêèì îáðàçîì, äâà ñìåæíûõ êëàññà ïî β ýêâèâàëåíòíû ïî
α/β , åñëè îíè íàõîäÿòñÿ â îäíîì ñìåæíîì êëàññå ïî ýêâèâàëåíòíîñòè α (èëè xαy ).
     Ââåä¼ì òåïåðü âàæíûå ïîíÿòèÿ ÿäðà è êîÿäðà áèíàðíîãî îòíîøåíèÿ.
Îïðåäåëåíèå 2.8. Ïóñòü A è B  íåïóñòûå ìíîæåñòâà è ρ ∈ A × B  ñîîòâåòñòâèå
ìåæäó íèìè. Òîãäà ÿäðîì ñîîòâåòñòâèÿ ρ íàçûâàåòñÿ îòíîøåíèå Ker ρ ∈ E(A), îïðå-
äåëÿåìîå ñîîòíîøåíèåì
                            a1 (Ker ρ) a2 , ∀ b ( a1 ρb = a2 ρb )
                                             B

Страницы