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

UptoLike

ВУЗ: 

МГУ | Москва

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

Рубрика: 

α, β ∈ R(A) a, b ∈ A
a[(α ∩ β)(α ∩ β)]b = ∃ x [ a(α ∩ β)x N x(α ∩ β)b ] =
= ∃ x [ aαx N aβx N xαb N xβc ] ⇒ ∃ x [ aαx N xαb ] N ∃ x [ aβx N xβb ] =
= aα
2
b N aβ
2
b = a[α
2
∩ β
2
]b.
ι
α
= A
2
r { α ∪ α
]
} = α ∪ α
]
= α ∩ α
]
α ∈ R(A)
α = < N
α
]
: m <
]
n ⇔ n < m ⇔ m > n
ι
α
: ¬(m < n) N ¬(n < m) ⇔ n = m
α
2
: m <
2
n ⇔
∃
N
x ( m < x N x < n ) ⇔ m + 1 < n
m <
k
n ⇔ m + k − 1 < n k > 1
α ¦ α
]
: m(< ¦ >)n ⇔
∃
N
x ( m < x N x > n ) ⇔
∃
N
x ( x > max {m, n} ) ⇔ 1
< ¦ >
α
]
¦ α : m(> ¦ <)n ⇔
∃
N
x ( m > x N x < n ) ⇔
∃
N
x ( x < min {m, n} ) ⇔
½
1, min {m, n} > 1,
0, .
αβ 6= βα αβ = βα
A ρ
O ρ = A
2
∅ ρ = ∅
ρ ∅ ⊆ ρ ⊆ O
M xρy ⇔ x = y x y z
A
ρ ρ
0
= M
ρ = ρ M = M ρ
ρ ∪ ρ
]
= O xρy ∨ xρ
]
y A
ρ
M ⊆ ρ xρx
ρ ∩ M = ∅ x¯ρx)
ρ
]
⊆ ρ (ρ
]
)
]
= ρ
ρ
]
= ρ xρy = yρx )
ρ ∩ ρ
]
⊆ M xρy Nyρx ⇒ x = y
ρ ∩ ρ
]
= ∅ xρy ∨ yρx
ρ ρ
]
ρ
2
⊆ ρ, xρy N yρz ⇒ xρz)
ρ
2
⊆ ρ ⇒ ρ
3
⊆ ρ
2
⊆ ρ ρ
ρ
n
⊆ ρ n = 1, 2, . . .
22                                                 Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Äåéñòâèòåëüíî, åñëè α, β ∈ R(A), òî äëÿ ëþáûõ a, b ∈ A ïîëó÷èì

 a[(α ∩ β)(α ∩ β)]b = ∃ x [ a(α ∩ β)x N x(α ∩ β)b ] =
        = ∃ x [ aαx N aβx N xαb N xβc ] ⇒ ∃ x [ aαx N xαb ] N ∃ x [ aβx N xβb ] =
                                                        = aα2 b N aβ 2 b = a[α2 ∩ β 2 ]b.

   Îòíîøåíèå ια = A2 r { α ∪ α] } = α ∪ α] = α ∩ α] íàçûâàþò îòíîøåíèåì íåñðàâíè-
ìîñòè äëÿ îòíîøåíèÿ α ∈ R(A).
   Ïðîèëëþñòðèðóåì äåéñòâèå ââåä¼ííûõ îïåðàöèé íà îäíîðîäíûå îòíîøåíèÿ.
Ïðèìåð 2.1. Ðàññìîòðèì îòíîøåíèå α = < (ñòðîãî ìåíüøå) íà N.

α] :   Èìååì m < ] n ⇔ n < m ⇔ m > n . Òàêèì îáðàçîì, ïñåâäîîáðàùåíèåì îòíîøåíèÿ
     ¾ñòðîãî ìåíüøå¿ áóäåò îòíîøåíèå ¾ñòðîãî áîëüøå¿.
ια :  Ïîñêîëüêó ¬(m < n) N ¬(n < m) ⇔ n = m, òî îòíîøåíèåì íåñðàâíèìîñòè äëÿ
     îòíîøåíèÿ ¾ñòðîãî ìåíüøå¿ áóäåò îòíîøåíèå ðàâåíñòâà.
  2
α :    Èìååì m <2 n ⇔ ∃ x ( m < x N x < n ) ⇔ m + 1 < n. Ïîíÿòíî, ÷òî
                                 N
      m  1.
α ¦ α] :    Èìååì m(< ¦ >)n ⇔ ∃ x ( m < x N x > n ) ⇔ ∃ x ( x > max {m, n} ) ⇔ 1,
                                   N                        N
      ò.å. îòíîøåíèå < ¦ > íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë èñòèííî âñåãäà.
α] ¦ α :    Èìååì     m(>      ¦     <)n        ⇔      ∃ x (m > x N x < n)   ⇔
                                ½                       N
                                  1, åñëè min {m, n} > 1,
      ∃ x ( x < min {m, n} ) ⇔                             .
      N                           0, èíà÷å.

   Ìû âèäèì, ÷òî, âîîáùå ãîâîðÿ, αβ 6= βα. Ïðè αβ = βα ñîîòâåòñòâóþùèå îòíîøåíèÿ
íàçûâàþòñÿ ïåðåñòàíîâî÷íûìè.

Îïðåäåëåíèå 2.5. Îäíîðîäíîå íà ìíîæåñòâå A îòíîøåíèå ρ íàçûâàåòñÿ:
       (O) àìîðôíûì, åñëè ρ = A2 (ñì. ï. 2.1 ïðèìåðà 2.1).
       (∅) ïóñòûì, åñëè ρ = ∅.
        Àìîðôíîå îòíîøåíèå âìåñòå ñ ïóñòûì íàçûâàþò íåñîáñòâåííûìè îòíîøåíèÿìè íà
        äàííîì ìíîæåñòâå. ßñíî, ÷òî äëÿ ëþáîãî îòíîøåíèÿ ρ èìååò ìåñòî ∅ ⊆ ρ ⊆ O.
       (M) äèàãîíàëüíûì èëè åäèíè÷íûì, åñëè xρy ⇔ x = y . Çäåñü è äàëåå x, y è z 
        ïðîèçâîëüíûå ýëåìåíòû ìíîæåñòâà A.
        Ïî îïðåäåëåíèþ äëÿ ïðîèçâîëüíîãî îäíîðîäíîãî îòíîøåíèÿ ρ ïîëàãàþò ρ0 = M.
        Î÷åâèäíî ρ = ρ M = M ρ.
       (F) ïîëíûì, åñëè ρ ∪ ρ] = O (ò.å. xρy ∨ xρ] y , èëè èç ëþáûõ äâóõ ýëåìåíòîâ A ïî
        êðàéíåé ìåðå îäèí íàõîäÿòñÿ â îòíîøåíèè ρ ñ äðóãèì).
       (R) ðåôëåêñèâíûì, åñëè M ⊆ ρ (÷òî îçíà÷àåò xρx).
     (AR) àíòèðåôëåêñèâíûì, åñëè ρ ∩ M = ∅ (÷òî îçíà÷àåò xρ̄x).
       (S) ñèììåòðè÷íûì, åñëè ρ] ⊆ ρ. Èç (ρ] )] = ρ ñðàçó ñëåäóåò, ÷òî ñèììåòðè÷íîñòü
        îòíîøåíèÿ ìîæíî çàäàòü ðàâåíñòâîì ρ] = ρ (ò.å. xρy = yρx).
     (AS) àíòèñèììåòðè÷íûì, åñëè ρ ∩ ρ] ⊆ M, (ò.å. xρy N yρx ⇒ x = y ).
     (NS) àñèììåòðè÷íûì èëè íåñèììåòðè÷íûì, åñëè ρ ∩ ρ] = ∅ (ò.å. xρy ∨ yρx, èëè
        èç äâóõ ñîîòíîøåíèé ρ è ρ] õîòÿ áû îäíî íå âûïîëíåíî).
       (T) òðàíçèòèâíûì, åñëè ρ2 ⊆ ρ, (÷òî îçíà÷àåò xρy N yρz ⇒ xρz).
        Ïîñêîëüêó ρ2 ⊆ ρ ⇒ ρ3 ⊆ ρ2 ⊆ ρ, òî äëÿ òðàíçèòèâíîãî îòíîøåíèÿ ρ èìååì
        ρn ⊆ ρ, n = 1, 2, . . ..

Страницы