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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

K = { x, y }
K
K
1
, K
2
, . . . , K
m
τ
τ =
m
[
i=1
K
2
i
.
K
1
= { 1, 2 } K
2
= { 2, 3 }
K
2
1
= { (1, 1), (1, 2), (2, 1), (2, 2) } K
2
2
= { (2, 2), (2, 3), (3, 2), (3, 3) }
K
2
K
Ã
1 1 0
1 1 1
0 1 1
!
=
Ã
1 1 0
1 1 0
0 0 0
!
∨
Ã
0 0 0
0 1 1
0 1 1
!
.
x K(x)
h A, τ i x, y ∈ A
K(x) = K(y) ⇔ xτy .
(⇐) K(x) = K(y) xτz
K x z
K ∈ K(x) K ∈ K(y) yτz
zτy xτz x(Ker τ)y
(⇒) x(Ker τ)y K x
z ∈ K x y y ∈ K
K ∈ K(x) K(y) K(x) = K(y) ¤
A = { 1, . . . , 6 } τ
1
K
1
2 3
K
3
K
2
K
4
4 5 6
36                                                              Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


ò.å. ñîäåðæàùèå ïðåäêëàññ K = { x, y }. Ëþáàÿ öåïü âëîæåííûõ äðóã â äðóãà òàêèõ
ïðåäêëàññîâ, íà÷èíàþùàÿñÿ ñ K , áóäåò êîíå÷íîé. Çàêëþ÷èòåëüíûé ïðåäêëàññ áóäåò óæå
êëàññîì òîëåðàíòíîñòè.
    Ñëåäñòâèåì ðàññìîòðåííîé ëåììû ÿâëÿåòñÿ ñëåäóþùèå

Óòâåðæäåíèå 2.3. Åñëè K1 , K2 , . . . , Km  âñå êëàññû òîëåðàíòíîñòè τ , òî
                                                  m
                                                  [
                                            τ =         Ki2 .                                    (2.8)
                                                  i=1

Ïðèìåð 2.10. Ïðîäîëæåíèå ïðèìåðà 2.9. Ïîñêîëüêó äëÿ òîëåðàíòíîñòè, çàäàâàåìîé
ìàòðèöåé (2.4) êëàññû òîëåðàíòíîñòè ñóòü K1 = { 1, 2 } è K2 = { 2, 3 }, òî
K12 = { (1, 1), (1, 2), (2, 1), (2, 2) } è K22 = { (2, 2), (2, 3), (3, 2), (3, 3) }. Ïðè çàäàíèè (0,1)-
ìàòðèöàìè òîëåðàíòíîñòè è îòíîøåíèé K 2  ¾íàõîäèòüñÿ â îäíîì äàííîì êëàññå K ¿,
èìååì                    Ã             !    Ã           ! Ã                 !
                             1 1 0             1 1 0               0 0 0
                             1 1 1        =    1 1 0        ∨      0 1 1        .
                             0 1 1             0 0 0               0 1 1
   Ñîïîñòàâèì êàæäîìó ýëåìåíòó x ïðîñòðàíñòâà òîëåðàíòíîñòè ñîâîêóïíîñòü K(x)
ñîäåðæàùèõ åãî êëàññîâ. Íèæåñëåäóþùàÿ òåîðåìà óòâåðæäàåò ñïðàâåäëèâîñòü àíàëîãà
ñâîéñòâà (2.6) ôàêòîðìíîæåñòâà òîëåðàíòíîñòè ïî ÿäðó.

Òåîðåìà 2.14. Ïóñòü h A, τ i  ïðîñòðàíñòâî òîëåðàíòíîñòè è x, y ∈ A. Òîãäà
                                        K(x) = K(y) ⇔ xτ y .

Äîêàçàòåëüñòâî. (⇐) Ïóñòü K(x) = K(y) è xτ z . Òîãäà ïî ëåììå 3.2, ñóùåñòâóåò êëàññ
òîëåðàíòíîñòè K , ñîäåðæàùèé îäíîâðåìåííî x è z .
   ßñíî, ÷òî K ∈ K(x). Íî òîãäà ïî óñëîâèþ è K ∈ K(y) èëè yτ z . Àíàëîãè÷íî ïîêàçû-
âàåòñÿ, ÷òî èç zτ y ñëåäóåò xτ z , ò.å. x(Ker τ )y .
   (⇒) Ïóñòü x(Ker τ )y è K  êëàññ òîëåðàíòíîñòè, ñîäåðæàùèé x. Òàê êàê ëþáîé
z ∈ K òîëåðàíòåí ê x, òî îí òîëåðàíòåí è ê y . Ñëåäîâàòåëüíî, y ∈ K . Òàêèì îáðàçîì,
ëþáîé êëàññ K ∈ K(x) îäíîâðåìåííî âõîäèò â K(y) è íàîáîðîò, ò.å. K(x) = K(y).      ¤


   Ïðåäñòàâëåíèå (2.8) òîëåðàíòíîñòè â âèäå îáúåäèíåíèå äåêàðòîâûõ êâàäðàòîâ ñâîèõ
êëàññîâ íàçûâàåòñÿ ðàçëîæåíèåì íà êâàäðàòû. Ãîâîðÿò, ÷òî òàêîå ðàçëîæåíèå íåïðèâî-
äèìî, åñëè íè îäèí êâàäðàò íåëüçÿ èñêëþ÷èòü áåç íàðóøåíèÿ äàííîãî ðàâåíñòâà. Ýòî
îçíà÷àåò, ÷òî íå âñå êëàññû, à ëèøü íåêîòîðîå èç íèõ, à èìåííî îáðàçóþùèå íåïðèâîäè-
ìîå ðàçëîæåíèå, îáðàçóþò ïîêðûòèå (2.4) èñõîäíîãî ìíîæåñòâà.
Ïðèìåð 2.11. Ïóñòü íà ìíîæåñòâå A = { 1, . . . , 6 } çàäàíà òîëåðàíòíîñòü τ , ïðåäñòàâ-
ëåííàÿ â âèäå ãðàôà íà ðèñ. 2.5 Êëàññàìè òîëåðàíòíîñòè çäåñü áóäóò ìíîæåñòâà



                                                [[
                                                  1
                                                 K1
                                           2 [      3 [
                                              [
                                         K3 K2  K4 [
                                    4             5                 6


                                     Ðèñ. 2.5: Ê ïðèìåðó 2.11

Страницы