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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

K
1
= { 1, 2, 3 }, K
2
= { 2, 3, 5 },
K
3
= { 2, 4, 5 }, K
4
= { 3, 5, 6 }.
τ = K
2
1
∪. . .∪K
2
4
K
2
2
τ = K
2
1
∪ K
2
3
∪ K
2
4
(1, 1) K
2
1
(4, 4) K
2
3
(6, 6) K
2
4
A
∪ ∩
τ
K
1
K
3
K
4
K
1
K
5
K
7
◦ ◦
◦ ◦ ◦
◦ ◦ ◦
K
1
K
2
K
3
K
4
K
5
K
6
K
7
K
1
K
3
K
4
K
6
K
7
B(τ) A/B(τ)
∼
B(τ )
a
1
∼
B(τ )
a
2
,
∀
B(τ )
K ( a
1
∈ K ⇔ a
2
∈ K ) .
a
1
a
2
B(τ)
∼
B(τ )
Ker τ
2.4. Ïðîñòðàíñòâà òîëåðàíòíîñòè                                                     37


                           K1 = { 1, 2, 3 },            K2 = { 2, 3, 5 },
                           K3 = { 2, 4, 5 },            K4 = { 3, 5, 6 }.

Ðàçëîæåíèå τ = K12 ∪. . .∪K42 èçáûòî÷íî, ò.ê. ëþáàÿ ïàðà ýëåìåíòîâ, âõîäÿùàÿ â äåêàðòîâ
êâàäðàò K22 , ñîäåðæèòñÿ â îäíîì èç îñòàëüíûõ êâàäðàòîâ. Â òîæå âðåìÿ, ðàçëîæåíèå
τ = K12 ∪ K32 ∪ K42 óæå íåïðèâîäèìî: íàïðèìåð, ïàðà (1, 1) ñîäåðæèòñÿ òîëüêî â K12 ,
ïàðà (4, 4)  òîëüêî â K32 , à ïàðà (6, 6)  òîëüêî â K42 .
   Ïðèâåä¼ì áåç äîêàçàòåëüñòâà ïðîñòóþ òåîðåìó.
Òåîðåìà 2.15. Ïóñòü íà íåïóñòîì ìíîæåñòâå A çàäàíî ïîêðûòèå. Òîãäà ëþáîé êëàññ
òîëåðàíòíîñòè, ïîðîæä¼ííûé ýòèì ïîêðûòèåì, âûðàæàåòñÿ ÷åðåç ýëåìåíòû ýòîãî
ïîêðûòèÿ ñ ïîìîùüþ îïåðàöèé ∪ è ∩.
Îïðåäåëåíèå 2.12. Áàçèñîì (òîëåðàíòíîñòè) íà êîíå÷íîì ìíîæåñòâå íàçûâàåòñÿ âñÿ-
êèé íàáîð êëàññîâ, îïðåäåëÿþùèé íåïðèâîäèìîå ðàçëîæåíèå äàííîé òîëåðàíòíîñòè íà
êâàäðàòû.
   Òàê, â ïðåäûäóùåì ïðèìåðå åäèíñòâåííûé áàçèñ òîëåðàíòíîñòè τ ñîñòîèò èç å¼ êëàñ-
ñîâ K1 , K3 è K4 . ßñíî, ÷òî ïðè óäàëåíèè èç áàçèñà ëþáîãî êëàññà îñòàâøèåñÿ ýëåìåíòû
óæå íå îáðàçóþò ïîêðûòèÿ èñõîäíîãî ìíîæåñòâà. Ìîæíî ïîêàçàòü, ÷òî òîëåðàíòíîñòü
ìîæåò èìåòü íåñêîëüêî áàçèñîâ ñ ðàçëè÷íûì ÷èñëîì âõîäÿùèõ â íèõ êëàññîâ.
Ïðèìåð 2.12. Ãðàô, ïðåäñòàâëåííûé íà ðèñ. 2.6 çàäà¼ò òîëåðàíòíîñòü íà âîñüìèýëåìåíò-
íîì ìíîæåñòâå. Ëåãêî âèäåòü, ÷òî êëàññû K1 K5 è K7 îáðàçóþò øåñòèýëåìåíòíûé, à


                                             [[ ◦   ◦
                                         
                                     K K [
                                              K              3
                                                1         2

                                   ◦ [     ◦     ◦
                                    K
                                       [K[ K K5         6


                                             
                                        4                     7


                                   ◦                ◦             ◦


                                Ðèñ. 2.6: Ê ïðèìåðó 2.12

êëàññû K1 , K3 , K4 , K6 è K7  ïÿòèýëåìåíòíûé áàçèñû äàííîãî ïðîñòðàíñòâà òîëå-
ðàíòíîñòè.
    ßñíî, ÷òî â ÷àñòíîì ñëó÷àå, êîãäà òîëåðàíòíîñòü îêàçûâàåòñÿ ýêâèâàëåíòíîñòüþ, òî
å¼ áàçèñ åäèíñòâåíåí è åãî ñîñòàâëÿþò ñìåæíûå êëàññû.
    Ñ êàæäûì áàçèñîì B(τ ) ïðîñòðàíñòâà òîëåðàíòíîñòè A/B(τ ) ñâÿçàíî îòíîøåíèå
ýêâèâàëåíòíîñòè ∼B(τ ) , îïðåäåëÿåìîå ñîîòíîøåíèåì

                       a1 ∼B(τ ) a2 ,       ∀ K ( a1 ∈ K ⇔ a2 ∈ K ) .
                                        B(τ )

Èíûìè ñëîâàìè, ýëåìåíòû a1 è a2 ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îíè âõîäÿò â îäíè
è òå æå êëàññû äàííîãî áàçèñà.
   Ïîíÿòíî, ÷òî òàê îïðåäåë¼ííîå îòíîøåíèå äåéñòâèòåëüíî áóäåò ýêâèâàëåíòíîñòüþ.
Åñëè ñ÷èòàòü, ÷òî êëàññû èç B(τ )  ýòî íåêîòîðûå ñâîéñòâà, ïî êîòîðûì âåä¼òñÿ êëàñ-
ñèôèêàöèÿ, òî ýêâèâàëåíòíîñòü ýëåìåíòîâ îçíà÷àåò, ÷òî îíè îáëàäàþò îäèíàêîâûì íà-
áîðîì ñâîéñòâ. Íàïðèìåð, äëÿ òîëåðàíòíîñòè, çàäàâàåìîé ìàòðèöåé (2.7) èç ïðèìåðà 2.8
áàçèñ åäèíñòâåíåí è ýêâèâàëåíòíîñòü ∼B(τ ) ñîâïàäàåò ñ Ker τ .

Страницы