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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

A B C α ⊆ A × B β ⊆ B × C
α ¦ β α β
a ∈ A, c ∈ C
a(α ¦ β)c ⇔
∃
B
b (aαb N bβc).
¦ α ¦ β αβ
α(βγ) = (αβ)γ ,
(αβ)
]
= β
]
α
]
,
½
α ⊆ β
γ ⊆ δ
⇒ αγ ⊆ βδ ,
α(β ∪ γ) = αβ ∪ αγ (α ∪ β)γ = αγ ∪ βγ ,
(α ∪ β)(γ ∪ δ) = αγ ∪ αδ ∪ βγ ∪ βδ ,
α(β ∩ γ) ⊆ αβ ∩ αγ (α ∩ β)γ ⊆ αγ ∩ βγ .
N
(αβ)
]
= β
]
α
]
a c
c(αβ)
]
a = a(αβ)c = ∃b (aαb N bβc ) = ∃b
¡
cβ
]
b N bα
]
a
¢
= c(β
]
α
]
)a.
a c
a(αγ)c = ∃ b ( aαb N bγc ) ⇒ ∃b ( aβb N bδc ) = a(βδ)c .
(α∩β)γ ⊆ αγ∩βγ
a c
a[(α ∩ β)γ]c = ∃ b ( a(α ∩ β)b N bγc ) = ∃ b ( aαb N aβb N bγc ) =
= ∃ b ( (aαb N bγc) N (aβb N bγc) ) ⇒ ∃ b ( aαb N bγc ) N ∃ b ( aβb N bγc ) =
= a(αγ)c N a(βγ)c = a(αγ ∩ βγ)c .
⇒ ⇔ b
aαb N bγc aβb N bγc
α(β ∩ γ) ⊆ αβ ∩ αγ
ρ A = {a
1
, . . . , a
m
} B = {b
1
, . . . , b
n
}
A B
M(ρ) ρ m × n r
ij
1 a
i
ρb
j
0
m×n M
m×n
1
20                                                    Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Îïðåäåëåíèå 2.4. Ïóñòü A , B è C  íåïóñòûå ìíîæåñòâà, α ⊆ A × B è β ⊆ B × C .
Òîãäà ïðîèçâåäåíèå èëè óìíîæåíèå α ¦ β ñîîòâåòñòâèé α è β îïðåäåëÿåòñÿ äëÿ ïðîèç-
âîëüíûõ a ∈ A, c ∈ C êàê

                                  a(α ¦ β)c ⇔ ∃ b (aαb N bβc).
                                               B

×àñòî çíàê ¦ îïóñêàþò è âìåñòî α ¦ β ïèøóò αβ .

   Ïîíÿòíî, ÷òî â îáùåì ñëó÷àå ïðîèçâåäåíèå ñîîòâåòñòâèé ìîæåò è íå ñóùåñòâîâàòü.
B ñëó÷àå æå ñóùåñòâîâàíèÿ îíî îáëàäàåò ñëåäóþùèìè ñâîéñòâàìè:


              α(βγ) = (αβ)γ       (àññîöèàòèâíîñòü ïðîèçâåäåíèÿ ñîîòâåòñòâèé ),
                   ]      ]   ]
              (αβ) = β α ,
        ½
            α⊆β
                       ⇒ αγ ⊆ βδ    (ìîíîòîííîñòü óìíîæåíèÿ ñîîòâåòñòâèé ),
            γ⊆δ
            α(β ∪ γ) = αβ ∪ αγ      è (α ∪ β)γ = αγ ∪ βγ ,       îòêóäà
                       (α ∪ β)(γ ∪ δ) = αγ ∪ αδ ∪ βγ ∪ βδ ,
            α(β ∩ γ) ⊆ αβ ∩ αγ      è (α ∩ β)γ ⊆ αγ ∩ βγ .

   Àññîöèàòèâíîñòü ïðîèçâåäåíèÿ ñîîòâåòñòâèé ñëåäóåò èç àññîöèàòèâíîñòè ëîãè÷åñêîé
îïåðàöèè N è ïðàâèë å¼ âçàèìîäåéñòâèÿ ñ êâàíòîðîì ñóùåñòâîâàíèÿ. Äîêàæåì ñïðàâåä-
ëèâîñòü ïðàâèëà (αβ)] = β ] α] : äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ a è c ñîîòâåòñòâóþùèõ
ìíîæåñòâ èìååì
                                                  ¡             ¢
         c(αβ)] a = a(αβ)c = ∃b (aαb N bβc ) = ∃b cβ ] b N bα] a = c(β ] α] )a.

   Ïîêàæåì ñïðàâåäëèâîñòü ñâîéñòâà ìîíîòîííîñòè óìíîæåíèÿ ñîîòâåòñòâèé. Äåéñòâè-
òåëüíî, äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ a è c ñîîòâåòñòâóþùèõ ìíîæåñòâ èìååì

                 a(αγ)c = ∃ b ( aαb N bγc ) ⇒ ∃b ( aβb N bδc ) = a(βδ)c .

   Äîêàæåì òåïåðü, ÷òî (α∩β)γ ⊆ αγ ∩βγ . Äåéñòâèòåëüíî, äëÿ ïðîèçâîëüíûõ ýëåìåíòîâ
a è c ñîîòâåòñòâóþùèõ ìíîæåñòâ áóäåì èìåòü

 a[(α ∩ β)γ]c = ∃ b ( a(α ∩ β)b N bγc ) = ∃ b ( aαb N aβb N bγc ) =
       = ∃ b ( (aαb N bγc) N (aβb N bγc) ) ⇒ ∃ b ( aαb N bγc ) N ∃ b ( aβb N bγc ) =
                                                     = a(αγ)c N a(βγ)c = a(αγ ∩ βγ)c .

 ïðèâåä¼ííîì âûâîäå çàìåíèòü ( ⇒ ) íà ( ⇔ ) íåëüçÿ, ïîñêîëüêó ýëåìåíòû b, îáåñïå÷è-
âàþùèå ñïðàâåäëèâîñòü aαb N bγc è aβb N bγc ìîãóò áûòü ðàçëè÷íûìè. Ñîîòíîøåíèå
α(β ∩ γ) ⊆ αβ ∩ αγ äîêàçûâàåòñÿ àíàëîãè÷íî.
    Ñóùåñòâóåò óäîáíûé ñïîñîá ïðåäñòàâëåíèÿ ñîîòâåòñòâèé êîíå÷íûõ ìíîæåñòâ â âèäå
(0,1)-ìàòðèö. Ïóñòü ρ  ñîîòâåòñòâèå ìåæäó A = {a1 , . . . , am } è B = {b1 , . . . , bn }.
Çàôèêñèðóåì óêàçàííûé ïîðÿäîê ñëåäîâàíèÿ ýëåìåíòîâ â ìíîæåñòâàõ A è B . Òîãäà
ìàòðèöà M (ρ) îòíîøåíèÿ ρ èìååò ðàçìåðû m × n è å¼ ýëåìåíò rij ðàâåí 1, åñëè ai ρbj
è 0 èíà÷å.
    Ìíîæåñòâî âñåõ (0,1)-ìàòðèö ðàçìåðà m×n áóäåì îáîçíà÷àòü Mm×n , îïóñêàÿ èíäåêñ,
êîãäà ñîîòâåòñòâóþùèé ðàçìåð ïîäðàçóìåâàåòñÿ. Âî ââåä¼ííîì ìíîæåñòâå âûäåëÿþòñÿ
ìàòðèöà, ó êîòîðîé âñ¼ ýëåìåíòû ðàâíû 1 è ìàòðèöà, ó êîòîðîé âñ¼ ýëåìåíòû ðàâíû

Страницы