Единое окно доступа к образовательным ресурсам

Лекции по упорядоченным множествам и универсальной алгебре: Учебно-методическое пособие

Голосов: 0

В пособии рассмотрены основные понятия и теоремы булевой алгебры, отношений множеств, причем особое внимание уделено частично упорядоченным множествам pi решёткам. Изучаются свойства модулярных, дистрибутивных решёток и решёток с дополнениями. Указанным разделам посвящены первые главы. В последней главе рассматриваются универсальные алгебры. Вводится понятие алгебраической системы, рассматриваются различные типы таких систем и доказываются основные теоремы об их изоморфизме и гомоморфизме. Вводимые понятия и доказанные утверждения иллюстрируются большим количеством примеров. Пособие предназначено для студентов, изучающих соответствующие разделы алгебры и может быть использовано при самообразовании. Электронная версия пособия размещена на сайте факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова <a href="http://www.cs.msu.su" target="_blank">(www.cs.msu.su)</a>.

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    2.2. Îäíîðîäíûå îòíîøåíèÿ                                                           21


0. Èõ íàçûâàþò óíèâåðñàëüíîé è íóëü-ìàòðèöåé è îáîçíà÷àþò I è O ñîîòâåòñòâåííî.
Ê ëþáîé ìàòðèöå èç M ìîæíî ïîýëåìåíòíî ïðèìåíèòü ëîãè÷åñêóþ îïåðàöèþ ¬ , à ê
ìàòðèöàì îäèíàêîâîãî ðàçìåðà  ëîãè÷åñêèå îïåðàöèè ∨ è      ïî ïðàâèëàì àëãåáðû
2 (ïîëàãàÿ 1 = 1 è 0 = 0). Ëåãêî âèäåòü, ÷òî ÀÑ MmЧn , ∨, , ¬, O, I ÿâëÿåòñÿ
áóëåâîé àëãåáðîé, èçîìîðôíîé òîòàëüíîé àëãåáðå P(A Ч B), ∪, ∩, − , ∅, A Ч B . Èçî-
ìîðôèçì ñëåäóåò èç ñëåäóþùèõ ðàâåíñòâ:

        M (α ∪ β) = M (α) ∨ M (β); M (α ∩ β) = M (α) M (β); M (α) = ¬ M (α).

   Ïîíÿòíî, ÷òî ìàòðèöà M (α ) ∈ MnЧm ïîëó÷àåòñÿ èç ìàòðèöû M (α) ∈ MmЧn òðàíñ-
ïîíèðîâàíèåì.
   Ïóñòü M1 ∈ MmЧn , M2 ∈ MnЧk . Îïðåäåëèì ïðîèçâåäåíèå M1 · M2 ∈ MmЧk äàííûõ
ìàòðèö êàê îáû÷íîå ìàòðè÷íîå ïðîèçâåäåíèå ñ çàìåíîé îïåðàöèè ñóììèðîâàíèÿ íà ∨,
à îïåðàöèè óìíîæåíèÿ  íà . Îáû÷íûì îáðàçîì ââîäèòüñÿ íàòóðàëüíàÿ ñòåïåíü M n
ìàòðèöû M êàê ðåçóëüòàò ïåðåìíîæåíèÿ n ∈ N ýêçåìïëÿðîâ äàííîé ìàòðèöû. Ëåãêî
ïîêàçûâàåòñÿ, ÷òî åñëè α ⊆ A Ч B è β ⊆ B Ч C , ãäå A, B, C  êîíå÷íûå ìíîæåñòâà,
òî ñïðàâåäëèâî ðàâåíñòâî
                             M (α β) = M (α) · M (β)
è ïîýòîìó, â ÷àñòíîñòè, M (α2 ) = M 2 (α).


2.2 Îäíîðîäíûå îòíîøåíèÿ
   Îòíîøåíèå ρ ⊆ A2 íàçûâàåòñÿ áèíàðíûì íà A èëè îäíîðîäíûì. Ìíîæåñòâî âñåõ
áèíàðíûõ íà A îòíîøåíèé îáîçíà÷èì R(A).
    ñëó÷àå, êîãäà A  êîíå÷íîå ìíîæåñòâî íåáîëüøîé ìîùíîñòè, îäíîðîäíûå îòíî-
øåíèÿ ρ ∈ R(A) óäîáíî èçîáðàæàòü â âèäå îðèåíòèðîâàííîãî ãðàôà. Âåðøèíàì ýòîãî
ãðàôà ñîîòâåòñòâóþò ýëåìåíòû A, à äóãà âåä¼ò èç x â y , åñëè xρy . Íà ðèñ. 2.1 ïî-
êàçàíû ïðèìåðû òàêèõ ãðàôîâ ñîîòâåòñòâåííî äëÿ îòíîøåíèé α = { (a, c), (a, d) } è
β = α ∪ { (d, b) } íà ÷åòûð¼õýëåìåíòíîì ìíîæåñòâå { a, b, c, d }. Åñëè xρx, òî ó âåðøè-


                          a   [[    b                  a    [[     bu

                                [
                                ]                              [
                                                               ]
                          u                            u
                          c         d                  c           d


                         Ðèñ. 2.1: Ãðàôû áèíàðíûõ îòíîøåíèé

íû x ðèñóþò ïåòëþ.
   Ïîñêîëüêó â R(A) ïðîèçâåäåíèå âñåãäà îïðåäåëåíî, òî â ñèëó àññîöèàòèâíîñòè ïðîèç-
âåäåíèÿ ñîîòâåòñòâèé àëãåáðà R(A),     åñòü ïîëóãðóïïà. Åñëè ρ ∈ R(A) è ∅ = B ⊆ A,
òî îòíîøåíèå ρ ∩ B íàçûâàþò ñóæåíèåì èëè îãðàíè÷åíèåì îòíîøåíèÿ ρ íà ïîäìíî-
                   2

æåñòâî B è îáîçíà÷àþò ρ |B .
   Äëÿ íàòóðàëüíîãî k ââîäÿò åñòåñòâåííîå îáîçíà÷åíèå αk = α . . . α ( k ðàç, α1 = α ).
Ðàçóìååòñÿ,
                          α ⊆ β ⇒ αk ⊆ β k , k = 1, 2, . . . .
   Ïîêàæåì, ÷òî
                                    (α ∩ β)2 ⊆ α2 ∩ β 2 .                         (2.1)


22                                                     Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


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

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

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

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

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

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


2.2. Îäíîðîäíûå îòíîøåíèÿ                                                                    23


  (WT) ñëàáî òðàíçèòèâíûì, åñëè ρ3 ⊆ ρ. Ïîíÿòíî, ÷òî òîãäà ρn ⊆ ρ äëÿ
    n = 1, 3, 4, . . ..
    îáîçíà÷åíèÿõ îäíîðîäíûõ îòíîøåíèé, êîãäà ýòî íåîáõîäèìî, ïîäñòðî÷íûì ñèìâî-
ëîì óêàçûâàþò ìíîæåñòâî, íà êîòîðîì îíè îïðåäåëåíû (íàïðèìåð, A ). ßñíî, ÷òî A 
åäèíèöà â ïîëóãðóïïå îäíîðîäíûõ îòíîøåíèé è ÀÑ R(A), , A åñòü ìîíîèä1 .
   Ïî÷òè î÷åâèäíà ñëåäóþùàÿ
Òåîðåìà 2.1 (Î ñîõðàíåíèè ñâîéñòâ îòíîøåíèÿ ïðè ñóæåíèÿ). Ïóñòü ∅ = 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    yρx) ⇔ xρ2 x ⇒ xρx ,

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

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

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


24                                                  Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


 2) ñèììåòðè÷íîñòü ñòàáèëüíà îòíîñèòåëüíî ∪, ∩ è , à îòíîñèòåëüíî    åñëè
    è òîëüêî åñëè îòíîøåíèÿ ïåðåñòàíîâî÷íû;
 3) òðàíçèòèâíîñòü ñòàáèëüíà îòíîñèòåëüíî ∩ è , à îòíîñèòåëüíî   åñëè îò-
    íîøåíèÿ ïåðåñòàíîâî÷íû.

Äîêàçàòåëüñòâî.

     1. Ïåðâûå òðè ñâîéñòâà î÷åâèäíû. Ñòàáèëüíîñòü ðåôëåêñèâíîñòè îòíîøåíèé îòíîñè-
        òåëüíî ïðîèçâåäåíèÿ ñëåäóåò èç ï. 1 òåîðåìû 2.3 î ñâîéñòâàõ ïðîèçâåäåíèÿ îòíîøå-
        íèé.
     2. Ïóñòü α, β  îäíîðîäíûå îòíîøåíèÿ è α = α, β = β . Äëÿ îáúåäèíåíèÿ è ïåðå-
        ñå÷åíèÿ èìååì

                  (α ∪ β) = α ∪ β = α ∪ β      è   α ∩ β) = α ∩ β = α ∩ β.

       Ñèììåòðè÷íîñòü îòíîøåíèÿ îçíà÷àåò åãî ñòàáèëüíîñòü îòíîñèòåëüíî îïåðàöèè
       ïñåâäîîáðàùåíèÿ.
       Äëÿ ïðîèçâåäåíèÿ äàííûõ îòíîøåíèé èìååì:

          ˆ åñëè åù¼ è αβ = βα, òî (αβ) = β α = βα = αβ ;
          ˆ åñëè αβ åù¼ è ñèììåòðè÷íî, òî αβ = (αβ) = β α = βα.

     3. Ïóñòü α, β  îäíîðîäíûå îòíîøåíèÿ è α2 ⊆ α, β 2 ⊆ β .
       Ñðàçó èìååì α2 ∩ β 2 ⊆ α ∩ β , à (2.1) îáåñïå÷èâàåò (α ∩ β)2 ⊆ α2 ∩ β 2 , îòêóäà
       (α ∩ β)2 ⊆ α ∩ β .
       Äëÿ ïñåâäîîáðàùåíèÿ èìååì

                     α2 = αα ⊆ α ⇔ (αα) ⊆ α ⇔ α α ⊆ α ⇔ (α )2 ⊆ α .

       Äëÿ ïðîèçâåäåíèÿ îòíîøåíèé, åñëè åù¼ è αβ = βα, òî

                            (αβ)2 = αβαβ = ααββ = α2 β 2 = αβ.



Òåîðåìà 2.5 (Ñòàáèëüíîñòü îòðèöàòåëüíûõ ñâîéñòâ îäíîðîäíûõ îòíîøåíèé).
Äëÿ îäíîðîäíûõ îòíîøåíèé α è β
 1) àíòèðåôëåêñèâíîñòü ñòàáèëüíà îòíîñèòåëüíî ∪, ∩ è ; à îòíîñèòåëüíî ïðîèç-
    âåäåíèÿ αβ  åñëè è òîëüêî åñëè α ∩ β = ∅ .
 2) àíòèñèììåòðè÷íîñòü ñòàáèëüíà îòíîñèòåëüíî ∩ è .
 3) àñèììåòðè÷íîñòü ñòàáèëüíà îòíîñèòåëüíî ∩ è ; à îòíîñèòåëüíî ∪  åñëè è
    òîëüêî åñëè α ∩ β = α ∩ β = ∅.

Äîêàçàòåëüñòâî.

     1. Àíòèðåôëåêñèâíîñòü îòíîñèòåëüíî ∪, ∩,      î÷åâèäíà.
       Àíòèðåôëåêñèâíîñòü ïðîèçâåäåíèÿ αβ îòíîøåíèé α è β îçíà÷àåò, ÷òî íè äëÿ
       îäíîãî ýëåìåíòà a íå íàéä¼òñÿ ýëåìåíòà b ñ îäíîâðåìåííîé ñïðàâåäëèâîñòüþ aαb
       è bβa . Íî ýòî îçíà÷àåò ëîæíîñòü a(α ∩ β )b äëÿ âñåõ a è b , ÷òî ýêâèâàëåíòíî
       òðåáóåìîìó.


2.3. Îòíîøåíèå ýêâèâàëåíòíîñòè                                                         25


  2. Ñòàáèëüíîñòü àíòèñèììåòðè÷íîñòè ( α∩α = ) îòíîñèòåëüíî ïñåâäîîáðàùåíèÿ î÷å-
     âèäíà, à îòíîñèòåëüíî ïåðåñå÷åíèÿ å¼ äîêàçûâàþò ðàâåíñòâà

           (α ∩ β) ∩ (α ∩ β) = α ∩ β ∩ α ∩ β = (α ∩ α ) ∩ (β ∩ β ) ⊆     ∩     =   .

  3. Ñòàáèëüíîñòü àñèììåòðè÷íîñòè ( ρ ∩ ρ = ∅ ) îòíîñèòåëüíî       î÷åâèäíà.
     Äëÿ ïåðåñå÷åíèÿ èìååì

               (α ∩ β) ∩ (α ∩ β) = α ∩ β ∩ α ∩ β = (α ∩ α ) ∩ (β ∩ β ) = ∅ .

     Äëÿ îáúåäèíåíèÿ:

       (α ∪ β) ∩ (α ∪ β) = (α ∪ β) ∩ (α ∪ β ) =
                        = (α ∩ α ) ∪ (β ∩ β ) ∪ (α ∩ β ) ∪ (β ∩ α ) =
                                                                 = (α ∩ β ) ∪ (β ∩ α ) .

     Ýòî âûðàæåíèå áóäåò ðàâíî ∅ åñëè è òîëüêî åñëè α ∩ β = α ∩ β = ∅.


   Ðàçëè÷íûå âñòðå÷àþùèåñÿ â ïðèëîæåíèÿõ îòíîøåíèÿ îáëàäàþò òåìè èëè èíûìè èç
óêàçàííûõ âûøå ýëåìåíòàðíûõ ñâîéñòâ. Íàïðèìåð, îäíîðîäíîå àíòèðåôëåêñèâíîå è àí-
òèñèììåòðè÷íîå îòíîøåíèå íàçûâàþò îòíîøåíèåì ïðåäïî÷òåíèÿ (èíîãäà ïðåäïîëàãàÿ
ó íåãî è íàëè÷èå ñâîéñòâà òðàíçèòèâíîñòè); îíî èãðàåò âàæíóþ ðîëü â òåîðèÿõ âûáî-
ðà, ñòàòèñòè÷åñêèõ ðåøåíèé, ñòðàòåãè÷åñêèõ èãð è äð. Íèæå â ï. 2.4 áóäåò ðàññìîòðåíî
îòíîøåíèå òîëåðàíòíîñòè, îáëàäàþùåå ñâîéñòâàìè ðåôëåêñèâíîñòè è àíòèñèììåòðè÷íî-
ñòè è èñïîëüçóþùèåñÿ, íàïðèìåð, â òåîðèè ðàñïîçíàâàíèÿ îáðàçîâ, ãäå îíî íàçûâàåòñÿ
áëèçîñòüþ.
   Èñêëþ÷èòåëüíóþ ðîëü â ìàòåìàòèêå è ïðèëîæåíèÿõ èãðàåò îòíîøåíèå ýêâèâàëåíò-
íîñòè.


2.3 Îòíîøåíèå ýêâèâàëåíòíîñòè
Îïðåäåëåíèå 2.6. Îäíîðîäíûå ðåôëåêñèâíûå, ñèììåòðè÷íûå è òðàíçèòèâíûå îòíîøå-
íèÿ íàçûâàþò îòíîøåíèÿìè ýêâèâàëåíòíîñòè.

Çàìå÷àíèå. Èç òåîðåìû 2.2 ñëåäóåò, ÷òî óñëîâèå ðåôëåêñèâíîñòè â îïðåäåëåíèè ýêâèâà-
ëåíòíîñòè ìîæíî îñëàáèòü, ïîòðåáîâàâ ëèøü ñîâïàäåíèÿ ëþáîé èç ïðîåêöèé îòíîøåíèÿ
ñî âñåì ìíîæåñòâîì ñâîåãî çàäàíèÿ. Ïðèâåä¼ííîå îïðåäåëåíèå òðàäèöèîííî.
    Îòíîøåíèå ýêâèâàëåíòíîñòè ÷àñòî îáîçíà÷àþò çíàêîì ∼. Ñîãëàñíî îïðåäåëåíèþ è
ï. 2 òåîðåìû 2.3 î ñâîéñòâàõ ïðîèçâåäåíèÿ îòíîøåíèé, äëÿ ïðîèçâîëüíîé ýêâèâàëåíòíî-
ñòè ∼ ñïðàâåäëèâî
                                    ⊆ ∼ = ∼ = ∼2 .                             (2.2)
Îòíîøåíèÿ ýêâèâàëåíòíîñòè ÷àñòî íàçûâàþò ïðîñòî ýêâèâàëåíòíîñòüþ.
   ßñíî, ÷òî ýêâèâàëåíòíîñòü ýëåìåíòîâ êàêîãî-ëèáî ìíîæåñòâà, âîîáùå ãîâîðÿ, íå îçíà-
÷àåò èõ òîæäåñòâà. Ýêâèâàëåíòíîñòÿìè ÿâëÿþòñÿ, íàïðèìåð, îòíîøåíèå ïàðàëëåëüíîñòè
íà ìíîæåñòâå ïðÿìûõ îáû÷íîãî ïðîñòðàíñòâà (åñëè ñ÷èòàòü ïðÿìóþ ïàðàëëåëüíîé ñà-
ìîé ñåáå), îòíîøåíèå ïîäîáèÿ ãåîìåòðè÷åñêèõ ôèãóð, îòíîøåíèå ðàâåíñòâà ïî ìîäóëþ
n öåëûõ ÷èñåë è äð.


26                                                  Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


   Ìíîæåñòâî âñåõ ýêâèâàëåíòíîñòåé íà (íåïóñòîì) ìíîæåñòâå A áóäåì îáîçíà÷àòü
E(A). Î÷åâèäíî, ëþáàÿ ýêâèâàëåíòíîñòü íà A ñîäåðæèò A è ñîäåðæèòñÿ â A . Ïî-
ñëåäíåå îòíîøåíèå íàçûâàþò èíîãäà àìîðôíîé ýêâèâàëåíòíîñòüþ.
   Äëÿ äàííîé ýêâèâàëåíòíîñòè ∼ íà ìíîæåñòâå A êàæäîìó a ∈ A ìîæíî ñîïîñòàâèòü
ìíîæåñòâî [a]∼ ýêâèâàëåíòíûõ åìó ýëåìåíòîâ  êëàññîâ ýêâèâàëåíòíîñòè èëè ñìåæíûõ
êëàññîâ : [a]∼ = {x ∈ A | x ∼ a}. Åñëè ýêâèâàëåíòíîñòü ôèêñèðîâàíà, òî ñìåæíûé êëàññ
ýëåìåíòà a îáîçíà÷àåì [a].
   Ôîðìèðîâàíèå ñìåæíûõ êëàññîâ ïðîèñõîäèò â õîäå âûïîëíåíèÿ ò.í. îïåðàöèè àá-
ñòðàêöèè îòîæäåñòâëåíèÿ ïî äàííîé ýêâèâàëåíòíîñòè, ïðè êîòîðîé îòâëåêàþòñÿ îò
èíäèâèäóàëüíûõ õàðàêòåðèñòèê ýëåìåíòîâ, âûäåëÿÿ ëèøü èõ îáùíîñòü. Ïîíÿòíî, ÷òî
ïðè ýòîì êàæäûé x ∈ A ïîïàäàåò â îäèí è òîëüêî îäèí êëàññ ýêâèâàëåíòíîñòè, è êëàñ-
ñû ýêâèâàëåíòíîñòè èëè ñîâïàäàþò, èëè íå ïåðåñåêàþòñÿ, íàêðûâàÿ â ñîâîêóïíîñòè âñ¼
ìíîæåñòâî A.
   Ãîâîðÿò, ÷òî ñîâîêóïíîñòü D = { A1 , A2 , . . . } íåïóñòûõ ïîäìíîæåñòâ ìíîæåñòâà A
îáðàçóåò åãî ðàçáèåíèå, åñëè îáúåäèíåíèå âñåõ ïîäìíîæåñòâ èç D ñîâïàäàåò ñ A è âñå
îíè ïîïàðíî íå ïåðåñåêàþòñÿ:

                     A = A1 + A2 + . . . ,    Ai ∩ Aj = ∅ ïðè i = j                   (2.3)

(èñïîëüçîâàíèå çíàêà + âìåñòî ∪ ïîä÷¼ðêèâàåò, ÷òî ðàññìàòðèâàåòñÿ èìåííî ðàçáèåíèå
ìíîæåñòâà). Ýëåìåíòû A1 , A2 , . . . ðàçáèåíèÿ D íàçûâàþò áëîêàìè.
   Ïóñòü çàäàíî ðàçáèåíèå ìíîæåñòâà A. Òîãäà ìîæíî îïðåäåëèòü îòíîøåíèå ýêâèâà-
ëåíòíîñòè íà A òàê, ÷òî ýëåìåíòû ðàçáèåíèÿ A áóäóò ñìåæíûìè êëàññàìè äàííîé ýê-
âèâàëåíòíîñòè. ßñíî, ÷òî òàêàÿ ýêâèâàëåíòíîñòü åäèíñòâåííà. Òàêèì îáðàçîì, ìåæäó
îòíîøåíèåì ýêâèâàëåíòíîñòè è ðàçáèåíèÿìè ñóùåñòâóåò âçàèìíîîäíîçíà÷íîå ñîîòâåò-
ñòâèå.
   Ïðèâåä¼ííûå ðàññóæäåíèÿ ìîæíî îôîðìèòü â âèäå ïðîñòîé, íî î÷åíü âàæíîé òåîðå-
ìû.
Òåîðåìà 2.6 (Î êëàññàõ ýêâèâàëåíòíîñòè). Ïóñòü A  íåïóñòîå ìíîæåñòâî. Åñ-
ëè íà A çàäàíà ýêâèâàëåíòíîñòü, òî ìíîæåñòâî êëàññîâ ýêâèâàëåíòíîñòè îáðàçóåò
ðàçáèåíèå A. È îáðàòíî, åñëè çàäàíî ðàçáèåíèå A íà êëàññû, òî ìîæíî åäèíñòâåííûì
îáðàçîì îïðåäåëèòü ýêâèâàëåíòíîñòü ∼ íà A òàê, ÷òî äëÿ ëþáîé ïàðû a, b ýëåìåí-
òîâ A a ∼ b ⇔ ¾a è b íàõîäÿòñÿ â îäíîì êëàññå ðàçáèåíèÿ¿.
   ¾Òåîðåìà î êëàññàõ ýêâèâàëåíòíîñòè íàõîäèò â ìàòåìàòèêå øèðî÷àéøåå ïðèìåíåíèå,
è å¼ ïî ïðàâó ìîæíî ñ÷èòàòü îäíîé èç ãëàâíûõ (à òî è ñàìîé ãëàâíîé) òåîðåìîé¿2 .
   Ïóñòü äàíî ðàçáèåíèå D íåïóñòîãî ìíîæåñòâà A íà êëàññû {A1 , A2 , . . .}. Çàìêí¼ì
D îòíîñèòåëüíî îñíîâíûõ òåîðåòèêî-ìíîæåñòâåííûõ îïåðàöèé, ò.å. ïîñòðîèì ìíîæåñòâî
S = [D]{∪, ∩, − } òàêîå, ÷òî îïåðàöèè ∪, ∩, − óñòîé÷èâû íà S . Òîãäà S áóäåò àëãåáðîé
ïîäìíîæåñòâ ìíîæåñòâà A, ïðè÷¼ì å¼ àòîìàìè áóäóò A1 , A2 , . . ..
   Ýêâèâàëåíòíîñòü íà êîíå÷íîì ìíîæåñòâå ìîæíî çàäàâàòü (0,1)-ìàòðèöåé (ñì. ï. 2.1).
ßñíî, ÷òî ñîîòâåòñòâóþùàÿ ìàòðèöà áóäåò ñèììåòðè÷íà è ñîäåðæàòü 1 íà ãëàâíîé äèà-
ãîíàëè. Îäíàêî, íå êàæäàÿ òàêàÿ ìàòðèöà çàäà¼ò ýêâèâàëåíòíîñòü  íàïðèìåð, íèæå-
ïðèâåä¼ííàÿ ìàòðèöà                               
                                            1 1 0
                                   M =  1 1 1 ,                                (2.4)
                                            0 1 1
ïîñêîëüêó M 2 = I = M , ýêâèâàëåíòíîñòè íå çàäà¼ò.
  2 Â.À. Óñïåíñêèé. ×òî òàêîå àêñèîìàòè÷åñêèé ìåòîä?  Èæåâñê: Èçäàòåëüñêèé äîì ¾Óäìóðòñêèé
óíèâåðñèòåò¿, 2000.


2.3. Îòíîøåíèå ýêâèâàëåíòíîñòè                                                         27


   Ìíîæåñòâî, ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ êëàññû ýêâèâàëåíòíîñòè ìíîæåñòâà A ïî
îòíîøåíèþ ýêâèâàëåíòíîñòè ∼ íàçûâàåòñÿ ôàêòîðìíîæåñòâîì è îáîçíà÷àåòñÿ A/ ∼.
Ïðèìåð 2.2.   1. Åñëè A  ìíîæåñòâî ç¼ðåí, íàñûïàííûõ â ìåøêè, è äëÿ ç¼ðåí a è
     b ïîëîæèòü a ∼ b, åñëè îíè ëåæàò â îäíîì ìåøêå, òî êëàññàìè ýêâèâàëåíòíîñòè
     ÿâëÿþòñÿ ìíîæåñòâà ç¼ðåí, ëåæàùèõ â îäíîì ìåøêå, à ôàêòîðìíîæåñòâîì A/ ∼ 
     ìíîæåñòâî ìåøêîâ.
  2. Åñëè W  ìíîæåñòâî ñëîâ ðóññêîãî ÿçûêà è äëÿ ñëîâ u è v ïîëîæèòü u ∼ v ,
     åñëè îíè íà÷èíàþòñÿ ñ îäíîé è òîé æå áóêâû (â ðóññêîì ÿçûêå 33 áóêâû), òî
     êëàññàìè ýêâèâàëåíòíîñòè áóäóò ìíîæåñòâà ñëîâ, íà÷èíàþùèõñÿ íà äàííóþ áóê-
     âó, à ôàêòîðìíîæåñòâîì W/∼  ìíîæåñòâî ñîîòâåòñòâóþùèõ áóêâ (çàìåòèì, ÷òî
     |W/∼ | = 31 ).

   Èññëåäóåì òåïåðü ñòàáèëüíîñòü ýêâèâàëåíòíîñòè. ßñíî, íàïðèìåð, ÷òî ýêâèâàëåíò-
íîñòü íå ñòàáèëüíà îòíîñèòåëüíî âçÿòèÿ äîïîëíåíèÿ, ïîñêîëüêó äîïîëíåíèå ýêâèâàëåíò-
íîñòè íå ñîäåðæèò äèàãîíàëüíîãî îòíîøåíèÿ. Ñ äðóãîé ñòîðîíû, ýêâèâàëåíòíîñòü ñòà-
áèëüíà îòíîñèòåëüíî îïåðàöèè ïåðåõîäà ê ïñåâäîîáðàòíîìó îòíîøåíèþ: êàê ñëåäóåò èç
òåîðåìû 2.4 î ñòàáèëüíîñòè ïîëîæèòåëüíûõ ñâîéñòâ îòíîøåíèé, îòíîøåíèå, ïñåâäîîá-
ðàòíîå ê ýêâèâàëåíòíîñòè åñòü ýêâèâàëåíòíîñòü. Èç ýòîé æå òåîðåìû âûòåêàåò

Òåîðåìà 2.7 (Ñòàáèëüíîñòü ïåðåñå÷åíèÿ ýêâèâàëåíòíîñòåé). Îòíîøåíèå ýêâèâà-
ëåíòíîñòè ñòàáèëüíî îòíîñèòåëüíî ïåðåñå÷åíèÿ.

   Îòñþäà â ñâîþ î÷åðåäü ñëåäóåò, ÷òî ïåðåñå÷åíèå ýêâèâàëåíòíîñòåé èç ïðîèçâîëüíîé
íåïóñòîé (âîçìîæíî áåñêîíå÷íîé) ñîâîêóïíîñòè åñòü ýêâèâàëåíòíîñòü.
   Ýêâèâàëåíòíîñòè α è β íà íåêîòîðîì ìíîæåñòâå íàçîâ¼ì êîãåðíòíûìè, åñëè äëÿ
ëþáîé ïàðû ñìåæíûõ êëàññîâ ïî α è ïî β ñîîòâåòñòâåííî ñïðàâåäëèâî óòâåðæäåíèå
¾ëèáî îäèí èç äàííûõ êëàññîâ ëåæèò â äðóãîì, ëèáî îíè íå ïåðåñåêàþòñÿ¿.

Òåîðåìà 2.8 (Î ñòàáèëüíîñòè îáúåäèíåíèÿ ýêâèâàëåíòíîñòåé). Ïóñòü α è β 
ýêâèâàëåíòíîñòè. Òîãäà

  1) îáúåäèíåíèå α ∪ β ÿâëÿåòñÿ ýêâèâàëåíòíîñòüþ åñëè è òîëüêî åñëè α è β êîãå-
     ðåíòíû;
  2) åñëè α ∪ β  ýêâèâàëåíòíîñòü, òî α ∪ β = αβ .

Äîêàçàòåëüñòâî.

  1.  ñèëó òåîðåìû 2.4 äîñòàòî÷íî ïîêàçàòü óêàçàííûé êðèòåðèé îòíîñèòåëüíî òðàí-
     çèòèâíîñòè.
     (⇐) Ïóñòü α è β  êîãåðåíòíûå ýêâèâàëåíòíîñòè íà ìíîæåñòâå A. Ðàññìîòðèì
     âñåâîçìîæíûå îáðàçû (α ∪ β)(a) ⊆ A ïî âñåì ýëåìåíòàì a ∈ A . Ëåãêî âèäåòü,
     ÷òî ïðè óêàçàííîì óñëîâèè äàííûå ïîäìíîæåñòâà A ëèáî ñîâïàäàþò, ëèáî íå ïåðå-
     ñåêàþòñÿ è èõ îáúåäèíåíèå ñîâïàäàåò A. Òàêèì îáðàçîì, îíè îáðàçóþò ðàçáèåíèå
     ìíîæåñòâà A, çàäàâàÿ ýêâèâàëåíòíîñòü íå í¼ì.
     (⇒) Ïóñòü òåïåðü äàííûå ýêâèâàëåíòíîñòè íå êîãåðåíòíû, ò.å. íàéäóòñÿ ñìåæíûå
     êëàññû [a]α è [b]β íå ëåæàùèå îäèí â äðóãîì è ñîäåðæàùèå îáùèé ýëåìåíò c.
     Ìîæíî ñ÷èòàòü, ÷òî a ∈ [a]α [b]β è b ∈ [b]β [a]α (ñì. ðèñ. 2.2). Ïàðû (a, c) è (c, b)
     ñîäåðæàòñÿ â α ∪ β . Åñëè áû ýòî îòíîøåíèå áûëî ýêâèâàëåíòíîñòüþ, òî îíî, â ñèëó
     òðàíçèòèâíîñòè, ñîäåðæàëî áû è ïàðó (a, b). Ïîñëåäíåå îçíà÷àåò ñïðàâåäëèâîñòü
     ëèáî aαb, ëèáî aβb. Ýòî, îäíàêî, íå èìååò ìåñòà è, ñëåäîâàòåëüíî, α ∪ β  íå
     ýêâèâàëåíòíîñòü.


28                                                   Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.



                                   [a]α '$ β
                                          [b]
                                         '$

                                         a   c   b
                                       &%
                                        &%
                                                      A

                          Ðèñ. 2.2: Ê äîêàçàòåëüñòâó òåîðåìû 2.8

     2. Ïóñòü α, β è α ∪ β  ýêâèâàëåíòíîñòè. Òîãäà ïî òåîðåìå 2.3 î ñâîéñòâàõ ïðîèçâå-
        äåíèÿ îòíîøåíèé ïîëó÷èì:

       èç ï. 1)  ïîñêîëüêó α è β ðåôëåêñèâíû, òî α ⊆ αβ è β ⊆ αβ , îòêóäà α∪β ⊆ αβ
            ïî ìîíîòîííîñòè îáúåäèíåíèÿ;
       èç ï. 3)  ò.ê. α ⊆ α ∪ β è β ⊆ α ∪ β , à α ∪ β òðàíçèòèâíî, òî αβ ⊆ α ∪ β .

       Ñëåäîâàòåëüíî, α ∪ β = αβ .

Ïðèìåð 2.3. Ïóñòü α è β  ýêâèâàëåíòíîñòè íà ìíîæåñòâå A = {a, b, c, d} ñî ñìåæíûìè
êëàññàìè A/α = {{a}, {b}, {c, d}} è A/β = {{a, b}, {c}, {d}}.

     1. Òîãäà α ∪ β åñòü ýêâèâàëåíòíîñòü è A/(α ∪ β) = {{a, b}, {c, d}}.
     2. Âîçüì¼ì äâà ýëåìåíòà èç îäíîãî êëàññà ýêâèâàëåíòíîñòè ïî α ∪ β , íàïðèìåð, a è
        b. Òîãäà ñïðàâåäëèâî a(αβ)b, ïîñêîëüêó ñïðàâåäëèâû îòíîøåíèÿ aαb è bβb.
       Òåïåðü âîçüì¼ì äâà ýëåìåíòà èç ðàçíûõ êëàññîâ ýêâèâàëåíòíîñòè ïî α ∪ β , íà-
       ïðèìåð, a è c. Òîãäà a(αβ)c íåñïðàâåäëèâî, ïîñêîëüêó íå ñóùåñòâóåò ýëåìåíòà x
       òàêîãî, ÷òî îòíîøåíèÿ aαx è xβc ñïðàâåäëèâû îäíîâðåìåííî.

  Ìû óæå îòìå÷àëè, ÷òî îòíîøåíèÿ ìîãóò áûòü, à ìîãóò è íå áûòü ïåðåñòàíîâî÷íûìè.
Ïîêàæåì, ýòî îñòà¼òñÿ ñïðàâåäëèâûì è äëÿ ýêâèâàëåíòíîñòåé.
Ïðèìåð 2.4. 1. Ïóñòü α è β  ýêâèâàëåíòíîñòè íà ìíîæåñòâå A = {a, b, c, d} ñî
    ñìåæíûìè êëàññàìè {a, b}, {c, d} è {a, c}, {b, d} ñîîòâåòñòâåííî. Òîãäà αβ è
    βα  àìîðôíûå ýêâèâàëåíòíîñòè íà A è, çíà÷èò, α è β ïåðåñòàíîâî÷íû.

     2. Ïóñòü α è β  ýêâèâàëåíòíîñòè íà ìíîæåñòâå A = {a, b, c} ñî ñìåæíûìè êëàññàìè
        {a, b}, {c} è {a}, {b, c} ñîîòâåòñòâåííî. Òîãäà a(αβ)c, íî íåâåðíî, ÷òî a(βα)c, è
        äàííûå ýêâèâàëåíòíîñòè íå ïåðåñòàíîâî÷íû. Îòìåòèì, ÷òî ïðè ýòîì íè αβ , íè βα
        íå ÿâëÿþòñÿ ýêâèâàëåíòíîñòÿìè.
     Ñëåäñòâèåì òåîðåìû òåîðåìû 2.3 ÿâëÿåòñÿ

Òåîðåìà 2.9 (Î ñòàáèëüíîñòè ïðîèçâåäåíèÿ ýêâèâàëåíòíîñòåé). Ïðîèçâåäåíèå ýê-
âèâàëåíòíîñòåé áóäåò ýêâèâàëåíòíîñòüþ, åñëè è òîëüêî åñëè îíè ïåðåñòàíîâî÷íû.

   Åñëè S  íåêîòîðîå ñâîéñòâî ýëåìåíòîâ ìíîæåñòâà A, òî íàèìåíüøèì ïîäìíîæå-
ñòâîì ìíîæåñòâà A, îáëàäàþùèì ñâîéñòâîì S íàçûâàåòñÿ ïåðåñå÷åíèå âñåõ ïîäìíî-
æåñòâ A, ýëåìåíòû êîòîðûõ îáëàäàþò ýòèì ñâîéñòâîì.
   Îáúåäèíÿÿ óòâåðæäåíèÿ äàííîé òåîðåìû è òåîðåìû 2.8 (îá îáúåäèíåíèè ýêâèâàëåíò-
íîñòåé) äëÿ ïåðåñòàíîâî÷íûõ ýêâèâàëåíòíîñòåé α è β è çàìå÷àÿ, ÷òî îáúåäèíåíèå äâóõ
ìíîæåñòâ åñòü íàèìåíüøåå ìíîæåñòâî èõ ñîäåðæàùåå, ïîëó÷àåì, ÷òî α ∪ β = αβ , ò.å.
ñïðàâåäëèâà


2.3. Îòíîøåíèå ýêâèâàëåíòíîñòè                                                        29


Òåîðåìà 2.10 (Î ïðîèçâåäåíèè ïåðåñòàíîâî÷íûõ ýêâèâàëåíòíîñòåé). Äëÿ ïå-
ðåñòàíîâî÷íûõ ýêâèâàëåíòíîñòåé ïðîèçâåäåíèå ÿâëÿåòñÿ íàèìåíüøåé ýêâèâàëåíòíî-
ñòüþ, èõ ñîäåðæàùåé.

   Íèæå ìû óêàæåì ñïîñîá ïîñòðîåíèÿ íàèìåíüøåé ýêâèâàëåíòíîñòè, ñîäåðæàùåé äàí-
íîå îòíîøåíèå. Îíî èñïîëüçóåò ïîíÿòèå çàìûêàíèÿ, â äàííîì ñëó÷àå  çàìûêàíèÿ îò-
íîøåíèÿ. Âîîáùå, ïîíÿòèå çàìûêàíèÿ (íåôîðìàëüíî  ïðèñîåäèíåíèÿ íåêîòîðîãî ìèíè-
ìàëüíî íåîáõîäèìîãî êîëè÷åñòâà íîâûõ îáúåêòîâ ê äàííîìó) ÿâëÿåòñÿ ôóíäàìåíòàëüíûì
è ÷àñòî èñïîëüçóåòñÿ â ðàçëè÷íûõ îáëàñòÿõ ìàòåìàòèêè.
   Îïåðàòîðîì çàìûêàíèÿ íà íåïóñòîì ìíîæåñòâå M íàçûâàþò îòîáðàæåíèå C ìíî-
æåñòâà âñåõ ïîäìíîæåñòâ M â ñåáÿ, îáëàäàþùåå äëÿ âñåõ X , Y ⊆ M ñëåäóþùèìè
ñâîéñòâàìè:

  1. X ⊆ C(X)  ðåôëåêñèâíîñòü,
  2. X ⊆ Y ⇒ C(X) ⊆ C(Y )  ìîíîòîííîñòü,
  3. C(C(X)) = C(X)  èäåìïîòåíòíîñòü.

Ìíîæåñòâî X íàçûâàåòñÿ çàìêíóòûì, åñëè C(X) = X .

Îïðåäåëåíèå 2.7. Íàèìåíüøåå òðàíçèòèâíîå îòíîøåíèå ρ t , ñîäåðæàùåå îòíîøåíèå ρ,
íàçûâàåòñÿ òðàíçèòèâíûì çàìûêàíèåì ρ. Íàèìåíüøàÿ ýêâèâàëåíòíîñòü ρ e , ñîäåðæà-
ùàÿ îòíîøåíèå ρ, íàçûâàåòñÿ ýêâèâàëåíòíûì çàìûêàíèåì ρ.
   Çàìûêàíèå ñîâîêóïíîñòè îòíîøåíèé åñòü çàìûêàíèå èõ îáúåäèíåíèÿ.

   Ëåãêî ïðîâåðèòü, ÷òî ïîëó÷åíèå ρ t è ρ e ìîæíî ïðåäñòàâèòü êàê ðåçóëüòàò äåéñòâèÿ
ñîîòâåòñòâóþùèõ îïåðàòîðîâ çàìûêàíèÿ.
   Òðàíçèòèâíîå çàìûêàíèå äàííîãî îòíîøåíèÿ ëåãêî ñòðîèòñÿ. Ââåä¼ì îáîçíà÷åíèå
       ∞
ρ+ =         ρn . Ïî îïðåäåëåíèþ ïðîèçâåäåíèÿ îòíîøåíèé ñïðàâåäëèâîñòü aρ+ b îçíà÷àåò
       n=1
ñóùåñòâîâàíèå òàêèõ ýëåìåíòîâ x0 = a, x1 , . . ., xn = b ñîîòâåòñòâóþùåãî ìíîæåñòâà,
÷òî x0 ρx1 . . . xn−1 ρxn . ßñíî, ÷òî ρ+ òðàíçèòèâíî, ρ = ρ+ , åñëè òðàíçèòèâíî ρ è
α ⊆ β ⇒ α+ ⊆ β + äëÿ îäíîðîäíûõ îòíîøåíèé ρ, α è β .
Óòâåðæäåíèå 2.1. Åñëè ρ  îäíîðîäíîå îòíîøåíèå, òî ρ t = ρ+ .
Äîêàçàòåëüñòâî. Èìååì ρ ⊆ ρt ⊆ ρ+ , îòêóäà ρ+ ⊆ ρt ⊆ ρ+ , ò.å. ρ t = ρ+ .
   Òåïåðü ìîæíî êîíñòðóêòèâíî îïðåäåëèòü ýêâèâàëåíòíîå çàìûêàíèå îòíîøåíèÿ.

Óòâåðæäåíèå 2.2. Åñëè ρ  îäíîðîäíîå îòíîøåíèå, òî ρe = ( ∪ρ ∪ ρ )t .
Äîêàçàòåëüñòâî. Îáîçíà÷èì σ = (ρ ∪ ρ ∪ ). Îòíîøåíèå ρe äîëæíî, êðîìå ρ, ñîäåðæàòü
   è ρ , ïîýòîìó σ ⊆ ρe . Â ñèëó òðàíçèòèâíîñòè ρe èìååì σ t ⊆ ρe , îòêóäà σ t ÿâëÿåòñÿ
ýêâèâàëåíòíîñòüþ.
   Ïóñòü òåïåðü ε  íåêîòîðàÿ ýêâèâàëåíòíîñòü, ñîäåðæàùàÿ ρ. Òîãäà
                                                            ∞
                                             n    n
         ρ⊆ε ⇒ ρ ⊆ε = ε ⇒ σ⊆ε ⇒ σ ⊆ε ⊆ε ⇒                         σn ⊆ ε ⇔ σt ⊆ ε .
                                                            n=1



                                                                                      t
   Ïîíÿòíî, ÷òî åñëè R  ñîâîêóïíîñòü îòíîøåíèé, òî Re =     ∪ ρ∈R ρ ∪ ρ∈R ρ .
Çäåñü âàæíûì ÷àñòíûì ñëó÷àåì ÿâëÿåòñÿ ýêâèâàëåíòíîå çàìûêàíèå ñîâîêóïíîñòè ýêâè-
âàëåíòíîñòåé.


30                                                      Ãëàâà 2. Îòíîøåíèÿ è ñîîòâåòñòâèÿ.


Òåîðåìà 2.11. Ýêâèâàëåíòíîå çàìûêàíèå ñîâîêóïíîñòè ýêâèâàëåíòíîñòåé ñîâïàäàåò
ñ îáúåäèíåíèåì âñåâîçìîæíûõ ïðîèçâåäåíèé ýòèõ ýêâèâàëåíòíîñòåé.
Äîêàçàòåëüñòâî. Ïóñòü R  ñîâîêóïíîñòü ýêâèâàëåíòíîñòåé è E  îáúåäèíåíèå âñå-
âîçìîæíûõ èõ ïðîèçâåäåíèé. Òîãäà äëÿ ëþáîé ýêâèâàëåíòíîñòè ∼ èç R ñîãëàñíî ï. 1
òåîðåìû 2.3 î ñâîéñòâàõ ïðîèçâåäåíèÿ îòíîøåíèé èìååì ∼ ⊆ E , à ñîãëàñíî å¼ ï. 3 
E ⊆ ∼, îòêóäà è ñëåäóåò òðåáóåìîå.

Ñëåäñòâèÿ.      1. Ýêâèâàëåíòíîå çàìûêàíèå
                                                          ∞
                                      e             e
                               {α, β} = (α ∪ β) =             (α ∪ β)n
                                                         n=1

       äâóõ ýêâèâàëåíòíîñòåé α è β ñîâïàäàåò ñ îáúåäèíåíèåì âñåâîçìîæíûõ ïðîèçâå-
       äåíèé âèäà αβ, βα, αβα, βαβ . . ..
     2. Åñëè     α     è   β       ïåðåñòàíîâî÷íûå     ýêâèâàëåíòíîñòè,  òî
        {α, β}e = (α ∪ β)e = α ∪ β = αβ (ïîñëåäíåå ðàâåíñòâî åñòü óòâåðæäåíèå
        òåîðåìû 2.10).

     Ðåôëåêñèâíûì (òî÷íåå  ðåôëåêñèâíî-òðàíçèòèâíûì) çàìûêàíèåì ρ∗ îäíîðîäíîãî
                                                                         ∞
îòíîøåíèÿ ρ íàçûâàþò îòíîøåíèå            ∪ρ+ ; ïîíÿòíî, ÷òî ρ∗ =            ρn .
                                                                      n=0
Ïðèìåð 2.5.     1. Åñëè α  îòíîøåíèå íà ìíîæåñòâå íàòóðàëüíûõ ÷èñåë, îïðåäåëÿåìîå
     ïðàâèëîì m α n         m + 1 = n, òî αt = < è α∗ = .
  2. Ïóñòü íà ìíîæåñòâå A = {1, 2, 3, 4, 5, 6, 7, 8} çàäàíû ýêâèâàëåíòíîñòè
     α è β ñî ñìåæíûìè êëàññàìè ñîîòâåòñòâåííî {1, 2}, {3, 4}, {5, 6, 7}, {8} è
     {1, 4}, {2, 3}, {5, 6}, {7}, {8}. Òîãäà ýêâèâàëåíòíîñòü (α ∪ β)e ïîðîæäàåò ñìåæíûå
     êëàññû {1, 2, 3, 4}, {5, 6, 7} è {8}.
  3. Ïóñòü íà ìíîæåñòâå A = {a, b, c, d, e, f } çàäàíû ýêâèâàëåíòíîñòè α è β ñî ñìåæ-
     íûìè êëàññàìè {a, b}, {c}, {d}, {e, f } è {a}, {b, c}, {d, e}, {f } ñîîòâåòñòâåííî. Òî-
     ãäà (a, c) ∈ αβ , íî (c, a) ∈ αβ è (c, a) ∈ βα, íî (a, c) ∈ βα. Òàêèì îáðàçîì,
     ýêâèâàëåíòíîñòè α è β íå ïåðåñòàíîâî÷íû è íè αβ , íè βα ýêâèâàëåíòíîñòÿìè
     íå ÿâëÿþòñÿ. Ýêâèâàëåíòíîå çàìûêàíèå {α, β}e (ñîâïàäàþùåå ñ αβ ∪ βα ) èìååò
     ñìåæíûå êëàññû {a, b, c} è {d, e, f }.
   Ïóñòü α è β  äâå ýêâèâàëåíòíîñòè íà ìíîæåñòâå A. Îòíîøåíèå âêëþ÷åíèÿ β ⊆ α
äëÿ íèõ îçíà÷àåò, ÷òî ëþáîé ñìåæíûé êëàññ ïî β ëåæèò â íåêîòîðîì ñìåæíîì êëàññå ïî
α. Èíûìè ñëîâàìè, ðàçáèåíèå ìíîæåñòâà A íà ñìåæíûå êëàññû ïî β åñòü ïîäðàçáèåíèå
åãî ðàçáèåíèÿ íà ñìåæíûå êëàññû ïî α. Ãîâîðÿò òàêæå, ÷òî ðàçáèåíèå ïî β åñòü èçìåëü-
÷åíèå ðàçáèåíèÿ ïî α. Äëÿ òàêèõ ýêâèâàëåíòíîñòåé îïðåäåëèì íà ôàêòîðìíîæåñòâå A/β
äðîáíóþ ýêâèâàëåíòíîñòü α/β ïî ïðàâèëó

                               [x]β (α/β) [y]β     [x]α = [y]α

äëÿ ïðîèçâîëüíûõ x, y ∈ A. Òàêèì îáðàçîì, äâà ñìåæíûõ êëàññà ïî β ýêâèâàëåíòíû ïî
α/β , åñëè îíè íàõîäÿòñÿ â îäíîì ñìåæíîì êëàññå ïî ýêâèâàëåíòíîñòè α (èëè xαy ).
     Ââåä¼ì òåïåðü âàæíûå ïîíÿòèÿ ÿäðà è êîÿäðà áèíàðíîãî îòíîøåíèÿ.
Îïðåäåëåíèå 2.8. Ïóñòü A è B  íåïóñòûå ìíîæåñòâà è ρ ∈ A Ч B  ñîîòâåòñòâèå
ìåæäó íèìè. Òîãäà ÿäðîì ñîîòâåòñòâèÿ ρ íàçûâàåòñÿ îòíîøåíèå Ker ρ ∈ E(A), îïðå-
äåëÿåìîå ñîîòíîøåíèåì
                            a1 (Ker ρ) a2     ∀ b ( a1 ρb = a2 ρb )
                                              B



    
Яндекс цитирования Яндекс.Метрика