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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

B(τ) h A, τ i
A B(τ)
A/B(τ) B(τ)
h A, τ i
A/B(τ) A/τ
T = h { 1, 2, 3 }, τ i
τ K
1
= { 1, 2 }
K
2
= { 2, 3 } T
K
3
= K
1
∩ K
2
= { 2 }
A/' = { K
1
, K
2
, K
3
} A/τ = A/ Ker τ
τ A = { 1, . . . , 9 }
τ
K
1
= { 1, 2, 3, 4, 6 }, K
2
= { 1, 2, 3, 5, 7, 9 }, K
3
= { 1, 2, 5, 8 }.
K
1
∩ K
2
= { 1, 2, 3} = K
4
,
K
1
∩ K
3
= { 1, 2 } = K
1
∩ K
2
∩ K
3
= K
5
,
K
2
∩ K
3
= { 1, 2, 5} = K
6
.
A/τ
{ 1, 2 }
A/ Ker τ
ρ ⊆ A × B A B
M
A
ρ = ρ = ρ M
B
ρ ⊆ ρρ
]
ρ
a ∈ A b ∈ B aρb = aρb N bρ
]
a N aρb ⇒ a(ρρ
]
ρ)b
ρ, α, β ⊆ A × B σ ⊆ B × C X, Y ⊆ A
ρ(A) = Im ρ, ρ
]
(B) = Dom ρ;
X ⊆ Y ⇒ ρ(X) ⊆ ρ(Y ); α ⊆ β ⇒ α(X) ⊆ β(X);
α ⊆ β ⇒
½
Dom α ⊆ Dom β
Im α ⊆ Im β
;
Dom ρ
]
= Im ρ, Im ρ
]
= Dom ρ;
ρ(X ∪ Y ) = ρ(X) ∪ ρ(Y ); ρ(X ∩ Y ) ⊆ ρ(X) ∩ ρ(Y );
(α ∪ β)(X) = α(X) ∪ β(X); (α ∩ β)(X) ⊆ α(X) ∩ β(X);
(ρ ¦ σ)(X) = σ(ρ(X));
Dom (ρσ) = ρ
]
(Dom σ) , Im (ρσ) = σ(Im ρ) .
38                                                       Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Îïðåäåëåíèå 2.13. Ïóñòü B(τ )  áàçèñ â ïðîñòðàíñòâå òîëåðàíòíîñòè h A, τ i. Ôàê-
òîðìíîæåñòâîì ïðîñòðàíñòâà A ïî áàçèñó B(τ ) íàçûâàåòñÿ ìíîæåñòâî îáîçíà÷àåìîå
A/B(τ ), ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ êëàññû èç B(τ ) è èõ âñåâîçìîæíûå (íå îáÿçà-
òåëüíî ïîïàðíûå) íåïóñòûå ïåðåñå÷åíèÿ.
   ßñíî, ÷òî â ÷àñòíîì ñëó÷àå, êîãäà òîëåðàíòíîñòü îêàçûâàåòñÿ ýêâèâàëåíòíîñòüþ, ïî-
íÿòèå ôàêòîðìíîæåñòâà òîëåðàíòíîñòè ñîâïàäàåò ñ ïîíÿòèåì ôàêòîðìíîæåñòâà ïî ýêâè-
âàëåíòíîñòè (ñì. ï. (2.3) ). Åñëè ïðîñòðàíñòâî òîëåðàíòíîñòè h A, τ i èìååò åäèíñòâåííûé
áàçèñ, òî âìåñòî A/B(τ ) áóäåì ïèñàòü A/τ .
Ïðèìåð 2.13.    1. Ïðîäîëæåíèå ïðèìåðà 2.9. Äëÿ ïðîñòðàíñòâà T = h { 1, 2, 3 }, τ i,
     â êîòîðîì òîëåðàíòíîñòü çàäàíà ìàòðèöåé (2.4), τ -êëàññû ñóòü K1 = { 1, 2 }
     è K2 = { 2, 3 }; îíè è ñîñòàâëÿþò åäèíñòâåííûé áàçèñ T. Äîáàâèâ ê ýòèì
     êëàññàì ìíîæåñòâî K3 = K1 ∩ K2 = { 2 } , ïîëó÷èì ôàêòîðìíîæåñòâî
     A/' = { K1 , K2 , K3 }. Çàìåòèì, ÷òî â äàííîì ñëó÷àå A/τ = A/ Ker τ .
     2. Ïóñòü òîëåðàíòíîñòü τ íà ìíîæåñòâå A = { 1, . . . , 9 } çàäàíà ìàòðèöåé 2.7. Åäèí-
        ñòâåííûì áàçèñîì òîëåðàíòíîñòè τ ÿâëÿåòñÿ ñîâîêóïíîñòü ïîäìíîæåñòâ
               K1 = { 1, 2, 3, 4, 6 },   K2 = { 1, 2, 3, 5, 7, 9 },   K3 = { 1, 2, 5, 8 }.
       Íàõîäèì ïåðåñå÷åíèÿ íåïóñòûå íåïàðíûå ïåðåñå÷åíèÿ äàííûõ êëàññîâ:
                             K1 ∩ K2 = { 1, 2, 3} = K4 ,
                             K1 ∩ K3 = { 1, 2 } = K1 ∩ K2 ∩ K3 = K5 ,
                             K2 ∩ K3 = { 1, 2, 5} = K6 .
     Ôàêòîðìíîæåñòâî ïî áàçèñó A/τ ñîñòîèò èç óêàçàííûõ øåñòè ýëåìåíòîâ. Çàìåòèì,
     ÷òî îíî èìååò ëèøü äèí îáùèé ýëåìåíò { 1, 2 } ñ òàêæå ôàêòîðìíîæåñòâîì ïî ÿäðó
     A/ Ker τ .
   Ïîíÿòèå ôàêòîðìíîæåñòâà ïî áàçèñó òîëåðàíòíîñòè îêàçûâàåòñÿ îñîáåííî ïîëåçíîì
â ñëó÷àÿõ, êîäà áàçèñ ñîäåðæèò íåáîëüøîå ìíîæåñòâî ýëåìåíòîâ. Îíî èñïîëüçóåòñÿ, â
÷àñòíîñòè, ïðè ìèíèìèçàöèè êîíå÷íûõ àâòîìàòîâ.


2.5 Îñíîâíûå ñâîéñòâà è òèïû ñîîòâåòñòâèé
    Ðàññìîòðèì ñîîòâåòñòâèå ρ ⊆ A × B ìåæäó íåïóñòûìè ìíîæåñòâàìè A è B . ßñíî,
÷òî MA ρ = ρ = ρ MB . Êðîìå òîãî, âñåãäà ñïðàâåäëèâî âêëþ÷åíèå ρ ⊆ ρρ] ρ. Äåéñòâèòåëü-
íî, äëÿ ïðîèçâîëüíûõ a ∈ A è b ∈ B èìååì aρb = aρb N bρ] a N aρb ⇒ a(ρρ] ρ)b.
    Äëÿ ëþáûõ îòíîøåíèé ρ, α, β ⊆ A × B è σ ⊆ B × C è ïîäìíîæåñòâ X, Y ⊆ A
ñïðàâåäëèâû ñëåäóþùèå óòâåðæäåíèÿ.
                            ρ(A) = Im ρ, ρ] (B) = Dom ρ;
                     X ⊆ Y ⇒ ρ(X) ⊆ ρ(Y ); α ⊆ β ⇒ α(X) ⊆ β(X);
                                     ½
                                        Dom α ⊆ Dom β
                            α⊆β ⇒                      ;
                                        Im α ⊆ Im β
                              Dom ρ] = Im ρ,       Im ρ] = Dom ρ;
Ýòè ñâîéñòâà âïîëíå î÷åâèäíû. Äàëåå, ñïðàâåäëèâû ñîîòíîøåíèÿ
                   ρ(X ∪ Y ) = ρ(X) ∪ ρ(Y ); ρ(X ∩ Y ) ⊆ ρ(X) ∩ ρ(Y );
                 (α ∪ β)(X) = α(X) ∪ β(X); (α ∩ β)(X) ⊆ α(X) ∩ β(X);
                                 (ρ ¦ σ)(X) = σ(ρ(X));
                        Dom (ρσ) = ρ] (Dom σ) ,      Im (ρσ) = σ(Im ρ) .

Страницы