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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

ρ
3
⊆ ρ ρ
n
⊆ ρ
n = 1, 3, 4, . . .
O
A
M
A
h R(A), ¦, M
A
i
∅ 6= B ⊆ A
ρ ∈ R(A) ρ
ρ |
B
A
A
ρ A
P r
1
ρ = A x y xρy
yρx x
∃y (xρy Nyρx) ⇔ xρ
2
x ⇒ xρx ,
M⊆ ρ ¤
P r
1
ρ = A P r
2
ρ = A
α, β γ
β α ⊆ αβ α ⊆ βα M⊆ α
n
α
n = 0, 1, 2, . . .
α α
n
= α n = 1, 2, . . .
α, β ⊆ γ γ αβ ⊆ γ
β α = α M ⊆ αβ
α = β
α
2
⊆ α α α ⊆ α
2
α = α
2
γ αβ ⊆ γγ = γ
2
⊆ γ
¤
∪ ∩
]
¦
ρρ
]
ρ
]
ρ
ρ
]
2.2. Îäíîðîäíûå îòíîøåíèÿ                                                                      23


  (WT) ñëàáî òðàíçèòèâíûì, åñëè ρ3 ⊆ ρ. Ïîíÿòíî, ÷òî òîãäà ρn ⊆ ρ äëÿ
    n = 1, 3, 4, . . ..
    îáîçíà÷åíèÿõ îäíîðîäíûõ îòíîøåíèé, êîãäà ýòî íåîáõîäèìî, ïîäñòðî÷íûì ñèìâî-
ëîì óêàçûâàþò ìíîæåñòâî, íà êîòîðîì îíè îïðåäåëåíû (íàïðèìåð, OA ). ßñíî, ÷òî MA 
åäèíèöà â ïîëóãðóïïå îäíîðîäíûõ îòíîøåíèé è ÀÑ h R(A), ¦, MA i åñòü ìîíîèä1 .
   Ïî÷òè î÷åâèäíà ñëåäóþùàÿ
Òåîðåìà 2.1 (Î ñîõðàíåíèè ñâîéñòâ îòíîøåíèÿ ïðè ñóæåíèÿ). Ïóñòü ∅ 6= B ⊆ A
è ρ ∈ R(A). Òîãäà, åñëè ρ îáëàäàåò îäíèì èç ñëåäóþùèõ ñâîéñòâ: (F), (R), (AR), (S),
(AS), (T),  ýòî ñâîéñòâî âûïîëíÿåòñÿ è äëÿ ñóæåíèÿ ρ |B .
   Î÷åâèäíî, ïîëíîå îòíîøåíèå ðåôëåêñèâíî.
Òåîðåìà 2.2. Ñèììåòðè÷íîå è òðàíçèòèâíîå îòíîøåíèå íà ìíîæåñòâå A, ïåðâàÿ
ïðîåêöèÿ êîòîðîãî ñîâïàäàåò ñ A, ðåôëåêñèâíî.
Äîêàçàòåëüñòâî. Ïóñòü ρ  îäíîðîäíîå íà A îòíîøåíèå, îáëàäàþùåå óêàçàííûìè ñâîé-
ñòâàìè. P r1 ρ = A îçíà÷àåò ñóùåñòâîâàíèå äëÿ ëþáîãî x òàêîãî y , ÷òî xρy , îòêóäà ïî
ñèììåòðè÷íîñòè è yρx. Òàêèì îáðàçîì, äëÿ ïðîèçâîëüíîãî x ñïðàâåäëèâî

                               ∃y (xρy N yρx) ⇔ xρ2 x ⇒ xρx ,

÷òî è îçíà÷àåò M⊆ ρ.                                                                            ¤

Çàìå÷àíèå.  ñèëó ñèììåòðè÷íîñòè P r1 ρ = A ýêâèâàëåíòíî P r2 ρ = A.
Òåîðåìà 2.3 (Ñâîéñòâà ïðîèçâåäåíèÿ îòíîøåíèé). Ïóñòü α, β è γ  îäíîðîäíûå
îòíîøåíèÿ. Òîãäà ñïðàâåäëèâû ñëåäóþùèå óòâåðæäåíèÿ.
  1. Åñëè β ðåôëåêñèâíî, òî α ⊆ αβ è α ⊆ βα. Îòñþäà M⊆ αn äëÿ ðåôëåêñèâíîãî α,
     n = 0, 1, 2, . . ..
  2. Åñëè α ðåôëåêñèâíî è òðàíçèòèâíî, òî αn = α, n = 1, 2, . . ..
  3. Åñëè α, β ⊆ γ è γ òðàíçèòèâíî, òî αβ ⊆ γ .
Äîêàçàòåëüñòâî.

  1. Åñëè β ðåôëåêñèâíî, òî α = α M ⊆ αβ è àíàëîãè÷íî äëÿ äðóãîãî âêëþ÷åíèÿ.
     Âòîðîå óòâåðæäåíèå ñëåäóåò èç ïåðâîãî ïðè α = β ïî ìîíîòîííîñòè ïðîèçâåäåíèÿ
     ñîîòâåòñòâèé.
  2. Åñëè α2 ⊆ α è α ðåôëåêñèâíî, òî èç ïðåäûäóùåãî α ⊆ α2 , ò.å. α = α2 , îòêóäà è
     ñëåäóåò òðåáóåìîå.
  3. Äëÿ òðàíçèòèâíîãî γ èìååì αβ ⊆ γγ = γ 2 ⊆ γ .
                                                                                                ¤

   Áóäåì ãîâîðèòü, ÷òî äàííîå ñâîéñòâî îòíîøåíèÿ ñòàáèëüíî îòíîñèòåëüíî íåêîòîðîé
îïåðàöèè íàä îòíîøåíèÿìè, åñëè ïðè óñëîâèè, ÷òî îòíîøåíèÿ-îïåðàíäû îáëàäàþò äàí-
íûì ñâîéñòâîì, òî èì îáëàäàåò è ðåçóëüòàò îïåðàöèè. Ðàññìîòðèì ñòàáèëüíîñòü ïîëî-
æèòåëüíûõ è îòðèöàòåëüíûõ ñâîéñòâ îòíîøåíèé.
Òåîðåìà 2.4 (Ñòàáèëüíîñòü ïîëîæèòåëüíûõ ñâîéñòâ îäíîðîäíûõ îòíîøåíèé).
Äëÿ îäíîðîäíûõ îòíîøåíèé
  1) ðåôëåêñèâíîñòü ñòàáèëüíà îòíîñèòåëüíî ∪, ∩,             ]
                                                                 è ¦;
   1 Ïîíÿòíî, ÷òî íè îòíîøåíèå ρρ] , íè ρ] ρ ìîãóò íå áûòü ðàâíûìè åäèíè÷íîìó. Ýòî îáúÿñíÿåò âûáîð
òåðìèíà ïñåâäîîáðàòíîå äëÿ îòíîøåíèÿ ρ] .

Страницы