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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A B
A B
ρ ⊆ A × B aρb (a, b) ∈ ρ
ρ Dom ρ Im ρ a ∈ A
ρ(a) = { b ∈ B | aρb } a ρ
∅ 6= X ⊆ A ρ(X) =
S
x∈X
ρ (x) X
ρ ρ
P(A × B)
α, β ⊆ A × B a ∈ A, b ∈ B
a(α ∪ β)b ⇔ aαb ∨ aβb ⇔ (a, b) ∈ α (a, b) ∈ β
a(α ∩ β)b ⇔ aαb N aβb ⇔ (a, b) ∈ α (a, b) ∈ β
aαb ⇔ ¬(aαb ) ⇔ (a, b) /∈ α
½
α ⊆ β
γ ⊆ δ
⇒
½
α ∪ γ ⊆ β ∪ δ ,
α ∩ γ ⊆ β ∩ δ
α, β, γ δ
ρ ρ
ρ ⊆ A × B
]
ρ
ρ
]
⊆ B × A bρ
]
a ⇔ aρb
a ∈ A, b ∈ B
ρ
−1
, ρ
0
, ρ
d
(ρ
]
)
]
= ρ ,
ρ
]
= (ρ)
]
,
α ⊆ β ⇒ α
]
⊆ β
]
,
(α ∪ β)
]
= α
]
∪ β
]
,
(α ∩ β)
]
= α
]
∩ β
]
.
a b
b(α ∩ β)
]
a = a(α ∩ β)b = aαb N aβb = bα
]
a N bβ
]
a = b(α
]
∩ β
]
)a .
ρ ⊆ A × B b ∈ B ρ
]
(b) = {a ∈ A | aρb}
b ρ Y ⊆ B ρ
]
(Y ) =
S
y∈Y
ρ
]
(y)
Y
2.1. Äåêàðòîâî ïðîèçâåäåíèå ìíîæåñòâ è îòíîøåíèÿ                                    19


   Óíàðíûå îòíîøåíèÿ íà íåêîòîðîì ìíîæåñòâå îïðåäåëÿþò òå èëè èíûå ñâîéñòâà
åãî ýëåìåíòîâ.
   Áèíàðíûå îòíîøåíèÿ íà äåêàðòîâîì ïðîèçâåäåíèè ìíîæåñòâ A è B íàçûâàþò
îòíîøåíèÿìè ìåæäó A è B èëè ñîîòâåòñòâèÿìè ìåæäó äàííûìè ìíîæåñòâàìè.
   Äëÿ ñîîòâåòñòâèÿ ρ ⊆ A × B óäîáíî ïîëüçîâàòüñÿ îáîçíà÷åíèåì aρb, åñëè (a, b) ∈ ρ.
Ïðè ýòîì ïåðâàÿ ïðîåêöèÿ ñîîòâåòñòâèÿ íàçûâàåòñÿ îáëàñòüþ îïðåäåëåíèÿ, à âòîðàÿ 
îáëàñòüþ çíà÷åíèé ρ, êîòîðûå îáîçíà÷àþòñÿ Dom ρ è Im ρ ñîîòâåòñòâåííî. Äëÿ a ∈ A
                                         S îáðàçîì ýëåìåíòà a ïðè ñîîòâåòñòâèè ρ.
ìíîæåñòâî ρ(a) = { b ∈ B | aρb } íàçûâàåòñÿ
Åñëè ∅ 6= X ⊆ A, òî ìíîæåñòâî ρ(X) =        ρ (x) íàçûâàåòñÿ îáðàçîì ìíîæåñòâà X
                                              x∈X
ïðè ñîîòâåòñòâèè ρ ïðè ñîîòâåòñòâèè ρ.
   Ïîñêîëüêó îòíîøåíèÿ ñóòü ïîäìíîæåñòâà, òî äëÿ áèíàðíûõ îòíîøåíèé îïðåäåëåíà
òîòàëüíàÿ àëãåáðà P(A × B) . ßñíî, ÷òî òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè, ïðèìåí¼í-
íûå ê ñîîòâåòñòâèÿì α, β ⊆ A × B , äëÿ a ∈ A, b ∈ B èìåþò ñëåäóþùèå ñâîéñòâà:
 1)   a(α ∪ β)b ⇔ aαb ∨ aβb ⇔ (a, b) ∈ α èëè (a, b) ∈ β ;
 2)   a(α ∩ β)b ⇔ aαb N aβb ⇔ (a, b) ∈ α è (a, b) ∈ β ;
 3)                         / α.
      aαb ⇔ ¬(aαb) ⇔ (a, b) ∈
   Ëåãêî ïîêàçûâàåòñÿ, ÷òî
                             ½                ½
                                  α⊆β             α∪γ ⊆ β ∪δ,
                                          ⇒
                                  γ⊆δ             α∩γ ⊆ β∩δ
( α, β, γ è δ ñóòü ñîîòâåòñòâèÿ îäíîé è òîé æå ïàðû ìíîæåñòâ).
    Îòíîøåíèå ρ íàçûâàþò äîïîëíèòåëüíûì ê ρ.
   Òåïåðü ìû ââåä¼ì äâå íîâûå îïåðàöèè äëÿ áèíàðíûõ îòíîøåíèé (ñîîòâåòñòâèé): óíàð-
íóþ ïñåâäîîáðàùåíèÿ è áèíàðíóþ ïðîèçâåäåíèÿ.
Îïðåäåëåíèå 2.3. Ïóñòü ρ ⊆ A × B . Îïåðàöèÿ      (ïñåâäîîáðàùåíèÿ ) ñîîòâåòñòâèÿ ρ
                                                       ]

çàäà¼ò ïñåâäîîáðàòíîå ê íåìó ñîîòâåòñòâèå ρ ⊆ B × A, îïðåäåëÿåìîå êàê bρ] a ⇔ aρb
                                                   ]

äëÿ ëþáûõ a ∈ A, b ∈ B .
   ßñíî, ÷òî ïñåâäîîáðàòíîå ê äàííîìó îòíîøåíèþ ñóùåñòâóåò âñåãäà. Äëÿ ïñåâäî-
îáðàùåíèÿ ÷àñòî óïîòðåáëÿþò òàêæå òåðìèíû îáðàòíîå, òðàíñïîíèðîâàííîå, èíâåðñ-
íîå, ñèììåòðè÷íîå èëè äóàëüíîå îòíîøåíèå è ïîëüçóþòñÿ îáîçíà÷åíèÿìè ρ−1 , ρ 0 , ρd
è äð. Ëåãêî óñòàíîâèòü ñëåäóþùèå ñâîéñòâà ïñåâäîîáðàùåíèÿ îòíîñèòåëüíî òåîðåòèêî-
ìíîæåñòâåííûõ îïåðàöèé è îòíîøåíèÿ âêëþ÷åíèÿ:
                     (ρ] )] = ρ (èíâîëþòèâíîñòü ïñåâäîîáðàùåíèÿ) ,
                       ρ] = (ρ)] ,
                   α ⊆ β ⇒ α] ⊆ β ]      (ìîíîòîííîñòü ïñåâäîîáðàùåíèÿ) ,
                         ]    ]      ]
                 (α ∪ β) = α ∪ β ,
                 (α ∩ β)] = α] ∩ β ] .
   Ïîêàæåì, íàïðèìåð, ñïðàâåäëèâîñòü ïîñëåäíåãî ðàâåíñòâà (a è b  ïðîèçâîëüíûå
ýëåìåíòû ñîîòâåòñòâóþùèõ ìíîæåñòâ):
           b(α ∩ β)] a = a(α ∩ β)b = aαb N aβb = bα] a N bβ ] a = b(α] ∩ β ] )a .

                                                                S ]ïðîîáðàçîì ýëå-
   Äëÿ ρ ⊆ A × B è b ∈ B ìíîæåñòâî ρ] (b) = {a ∈ A | aρb} íàçûâàåòñÿ
ìåíòà b ïðè ñîîòâåòñòâèè ρ. Åñëè Y ⊆ B , òî ìíîæåñòâî ρ] (Y ) =    ρ (y) íàçûâàåòñÿ
                                                                      y∈Y
ïðîîáðàçîì ìíîæåñòâà Y .

Страницы