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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

C A
Dom σ = σ
]
(C) Im ρ = ρ(A),
Dom (ρσ) = (ρσ)
]
(C) = (σ
]
ρ
]
)(C) = ρ
]
(σ
]
(C)) = ρ
]
(Dom σ) ;
Im (ρσ) = (ρσ)(A) = σ(ρ(A)) = σ(Im ρ) .
ρ A B
M
A
⊆ ρρ
]
Dom ρ = A
A B ρ
]
ρ ⊆M
B
aρb
1
N aρb
2
⇒ b
1
= b
2
a ∈ A Dom ρ ⊆ A
A B M
A
⊆ ρρ
]
N ρ
]
ρ ⊆M
B
a ∈ A b ∈ B
aρb
ρρ
]
ρ ⊆ ρ
ρρ
]
ρ = ρ ρ(a
1
) ∩ ρ(a
2
) 6= ∅ ⇒ ρ(a
1
) = ρ(a
2
)
a
1
, a
2
∈ A ρ
]
(b
1
) ∩ ρ
]
(b
2
) 6= ∅ ⇒ ρ
]
(b
1
) = ρ
]
(b
2
) b
1
, b
2
∈ B
ρ
ρ
a
0
, a
00
∈ A ρ(a
0
) ∩ ρ(a
00
) 6= ∅ ρ(a
0
) = ρ(a
00
)
b
0
, b
00
∈ B ρ
]
(b
0
) ∩ ρ
]
(b
00
) 6= ∅ ρ
]
(b
0
) = ρ
]
(b
00
)
'
A
ϕ A
x ' y ⇔ ϕ(x) ∩ ϕ(y) 6= ∅ .
ϕ A B A B
A ϕ : A → B A
ϕ
→ B aϕb
ϕ(a) = b a
ϕ
7→ b
2.6. Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà                                                      39


Äîêàæåì ïîñëåäíèå äâà ñâîéñòâà. Çàïèøåì ïðîîáðàç C è îáðàç A ÷åðåç ïðîåêöèè ñî-
îòâåòñòâèé:
                       Dom σ = σ ] (C) è Im ρ = ρ(A),
Ïîëüçóÿñü ñâîéñòâàìè ñîîòâåòñòâèé è èõ ïñåâäîîáðàùåíèé ïîëó÷èì

               Dom (ρσ) = (ρσ)] (C) = (σ ] ρ] )(C) = ρ] (σ ] (C)) = ρ] (Dom σ) ;
                        Im (ρσ) = (ρσ)(A) = σ(ρ(A)) = σ(Im ρ) .

   Äîêàçàòåëüñòâî îñòàëüíûõ ñâîéñòâ ìîæíî íàéòè, íàïðèìåð, â [1].
   Âûäåëèì îñíîâíûå òèïû ñîîòâåòñòâèé, îáëàäàþùèå îñîáûìè ñâîéñòâàìè.
Îïðåäåëåíèå 2.14. Ñîîòâåòñòâèå ρ ìåæäó ìíîæåñòâàìè A è B íàçûâàåòñÿ
   ˆ ìíîãîçíà÷íûì îòîáðàæåíèåì èëè âñþäó îïðåäåë¼ííûì ñîîòâåòñòâèåì, åñëè
     MA ⊆ ρρ] (÷òî ýêâèâàëåíòíî Dom ρ = A );
   ˆ ÷àñòè÷íûì îòîáðàæåíèåì A â B , åñëè ρ] ρ ⊆MB (÷òî ýêâèâàëåíòíî
     aρb1 N aρb2 ⇒ b1 = b2 äëÿ a ∈ A, ïðè ýòîì Dom ρ ⊆ A );
   ˆ ôóíêöèîíàëüíûì èëè îòîáðàæåíèåì A â B , åñëè MA ⊆ ρρ] N ρ] ρ ⊆MB (÷òî ýê-
     âèâàëåíòíî ñóùåñòâîâàíèþ äëÿ ëþáîãî a ∈ A åäèíñòâåííîãî b ∈ B òàêîãî, ÷òî
     aρb );
   ˆ äèôóíêöèîíàëüíûì èëè êâàçèîäíîçíà÷íûì, åñëè ρρ] ρ ⊆ ρ èëè, ñ ó÷¼òîì äîêàçàí-
     íîãî âûøå, ρρ] ρ = ρ (÷òî ýêâèâàëåíòíî ρ(a1 ) ∩ ρ(a2 ) 6= ∅ ⇒ ρ(a1 ) = ρ(a2 ) äëÿ
     âñåõ a1 , a2 ∈ A èëè ρ] (b1 ) ∩ ρ] (b2 ) 6= ∅ ⇒ ρ] (b1 ) = ρ] (b2 ) äëÿ âñåõ b1 , b2 ∈ B ).
     Äàííûå ñîîòíîøåíèÿ óêàçûâàþò, ÷òî êàê îáðàçû, òàê è ïðîîáðàçû äèôóíêöèîíàëü-
     íûõ îòíîøåíèé ëèáî ñîâïàäàþò, ëèáî íå ïåðåñåêàþòñÿ. Ðàâíîñèëüíû ñëåäóþùèå
     ñâîéñòâà ñîîòâåòñòâèÿ ρ:
         ρ äèôóíêöèîíàëüíî;
         åñëè a0 , a00 ∈ A è ρ(a0 ) ∩ ρ(a00 ) 6= ∅, òî ρ(a0 ) = ρ(a00 );
         åñëè b0 , b00 ∈ B è ρ] (b0 ) ∩ ρ] (b00 ) 6= ∅, òî ρ] (b0 ) = ρ] (b00 ).

   Ôóíêöèîíàëüíûå îòîáðàæåíèÿ áóäóò ðàññìîòðåíû íèæå.  êà÷åñòâå èëëþñòðàöèè èñ-
ïîëüçîâàíèÿ ìíîãîçíà÷íûõ îòîáðàæåíèé ïðèâåä¼ì áåç äîêàçàòåëüñòâà (êîòîðîå ìîæåò
áûòü íàéäåíî â [16]) ñëåäóþùóþ òåîðåìó.
Òåîðåìà 2.16 (Êàëüìàð-ßêóáîâè÷). Ïðîèçâîëüíîå îòíîøåíèå òîëåðàíòíîñòè ' íà
ìíîæåñòâå A ìîæåò áûòü çàäàíî ñ ïîìîùüþ ïîäõîäÿùåãî ìíîãîçíà÷íîãî îòîáðàæå-
íèÿ ϕ èç A íà ñîâîêóïíîñòü âñåâîçìîæíûõ êëàññîâ òîëåðàíòíîñòè êàê

                                     x ' y ⇔ ϕ(x) ∩ ϕ(y) 6= ∅ .


2.6 Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà
   Øèðî÷àéøåå ïðèìåíåíèå íàõîäÿò ôóíêöèîíàëüíûå ñîîòâåòñòâèÿ (îòîáðàæåíèÿ). Ðàñ-
ñìîòðèì èõ ïîäðîáíåå.
   Îòîáðàæåíèå ϕ èç A â B áóäåì íàçûâàòü òàêæå ôóíêöèåé èç A â B èëè îïåðàöèåé
                                                        ϕ
íà A5 . Ïðè ýòîì èñïîëüçóþò îáîçíà÷åíèÿ ϕ : A → B èëè A → B . Òîò ôàêò, ÷òî aϕb
                                  ϕ
çàïèñûâàþò êàê ϕ(a) = b èëè a 7→ b ; ïðè òåîðåòè÷åñêèõ âûêëàäêàõ óäîáíà çàïèñü
  5 Òàêèì îáðàçîì, ìû íå ðàçëè÷àåì ïîíÿòèÿ ôóíêöèîíàëüíîãî ñîîòâåòñòâèÿ (îòîáðàæåíèÿ) è ôóíêöèè,
õîòÿ îíè íå òîæäåñòâåííû äðóã äðóãó. Ïðèìåð äëÿ çíàêîìûõ ñ òåîðèåé àëãîðèòìîâ: íåâû÷èñëèìûå
ôóíêöèè, ñòðîãî ãîâîðÿ, ÿâëÿþòñÿ ëèøü ôóíêöèîíàëüíûìè ñîîòâåòñòâèÿìè, à íå ôóíêöèÿìè.

Страницы