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

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

Голосов: 0

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

Приведенный ниже текст получен путем автоматического извлечения из оригинального PDF-документа и предназначен для предварительного просмотра.
Изображения (картинки, формулы, графики) отсутствуют.
    2.4. Ïðîñòðàíñòâà òîëåðàíòíîñòè                                                                 31


äëÿ a1 , a2 ∈ A. Äâîéñòâåííî, êîÿäðî ñîîòâåòñòâèÿ ρ ýòî îòíîøåíèå CoKer ρ ∈ E(B),
îïðåäåëÿåìîå ñîîòíîøåíèåì
                                  CoKer ρ   Ker ρ .
   Êëàññû ýêâèâàëåíòíîñòè Ker ρ è CoKer ρ íàçûâàþòñÿ ÿäðàìè è êîÿäðàìè ñîîòâåò-
ñòâåííî3 . ßäðî, ñîäåðæàùåå ýëåìåíò a ∈ A áóäåì îáîçíà÷àòü Core(a); ñîîòâåòñòâåííî,
CoCore(b)  êîÿäðî, ñîäåðæàùåå ýëåìåíò b ∈ B .

   Òàêèì îáðàçîì, äâà ýëåìåíòà A íàõîäÿòñÿ â îòíîøåíèè Ker ρ, åñëè ñîâïàäàþò èõ
îáðàçû, à äâà ýëåìåíòà B â îòíîøåíèè CoKer ρ,  åñëè ñîâïàäàþò èõ ïðîîáðàçû. ßñíî,
÷òî ââåä¼ííûå îòíîøåíèÿ äåéñòâèòåëüíî ñóòü ýêâèâàëåíòíîñòè  èõ ñâîéñòâà ðåôëåê-
ñèâíîñòè, ñèììåòðè÷íîñòè è òðàíçèòèâíîñòè î÷åâèäíû. Ïîýòîìó Ker ρ ÷àñòî íàçûâàþò
ÿäåðíîé ýêâèâàëåíòíîñòüþ.
   Åñëè îòíîøåíèå ρ çàäàíî (0,1)-ìàòðèöåé M (ρ), òî ýêâèâàëåíòíûìè ïî Ker ρ îêàçû-
âàþòñÿ ýëåìåíòû A, êîòîðûì ñîîòâåòñòâóþò îäèíàêîâûå ñòðîêè, à ýêâèâàëåíòíûìè ïî
CoKer ρ  ýëåìåíòû B , êîòîðûì ñîîòâåòñòâóþò îäèíàêîâûå ñòîëáöû M (ρ).
   Ïîíÿòèå ÿäåðíîé ýêâèâàëåíòíîñòè è ÿäðà ÷àñòî èñïîëüçóþò äëÿ îäíîðîäíîãî îòíî-
øåíèÿ (÷àñòíûé ñëó÷àé áèíàðíîãî). Òàê, åñëè ρ ∈ R(A), òî äâà ýëåìåíòà íàõîäÿòñÿ â
îòíîøåíèè Ker ρ, åñëè îíè ñâÿçàíû èñõîäíûì îòíîøåíèåì ρ â òî÷íîñòè ñ îäíèìè è òåìè
æå ýëåìåíòàìè A:
                            x(Ker ρ) y = ∀z ( xρz = yρz ) .                   (2.5)
   ßäðîì îòíîøåíèÿ ýêâèâàëåíòíîñòè, î÷åâèäíî, ÿâëÿåòñÿ îíî ñàìî.


2.4 Ïðîñòðàíñòâà òîëåðàíòíîñòè
Îïðåäåëåíèå 2.9. Îäíîðîäíûå ðåôëåêñèâíûå è ñèììåòðè÷íûå îòíîøåíèÿ íàçûâàþò
îòíîøåíèÿìè òîëåðàíòíîñòè.

   Îòíîøåíèå òîëåðàíòíîñòè áóäåì, êàê ïðàâèëî, îáîçíà÷àòü    èëè τ . Ñîãëàñíî îïðå-
äåëåíèþ äëÿ ïðîèçâîëüíîãî îòíîøåíèÿ òîëåðàíòíîñòè     ñïðàâåäëèâî

                                            ⊆     =     .

   Ââåä¼ííîå îòíîøåíèå òîëåðàíòíñòè  ìàòåìàòè÷åñêîå óòî÷íåíèå ïîíÿòèå ñõîäñòâà,
áëèçîñòè, íåðàçëè÷èìîñòè. Íàïðèìåð, ïîíÿòèå áëèçîñòè îáúåêòîâ, èñïîëüçóåìîå â òåî-
ðèè ðàñïîçíàâàíèÿ îáðàçîâ, åñòü îòíîøåíèå òîëåðàíòíîñòè ìåæäó íèìè. Îòíîøåíèÿ òî-
ëåðàíòíîñòè ÷àñòî íàçûâàþò ïðîñòî òîëåðàíòíîñòÿìè4 , à ïàðó ýëåìåíòîâ, ñâÿçàííûõ óêà-
çàííûì îòíîøåíèåì  òîëåðàíòíûìè.
Ïðèìåð 2.6. Îïèñàííûå íèæå îòíîøåíèÿ τ ñóòü òîëåðàíòíîñòè.
  1. A è B  òî÷êè åâêëèäîâà ïðîñòðàíñòâà è Aτ B ⇔ |A − B| < r, ãäå r  ïðîèç-
     âîëüíîå ïîëîæèòåëüíîå ÷èñëî.
  2. Ñëîâà ðóññêîãî ÿçûêà íàõîäÿòñÿ â îòíîøåíèè τ , åñëè îíè îòëè÷àþòñÿ ðîâíî íà
     îïðåäåë¼ííîå êîëè÷åñòâî áóêâ (íàïðèìåð, íà îäíó).
  3 Èòàê, ÿäðî ñîîòâåòñòâèÿ  ýòî îòíîøåíèå ýêâèâàëåíòíîñòè, à (ïðîñòî) ÿäðà  ñìåæíûå êëàññû ýòîãî
îòíîøåíèÿ.
   4 Îò ëàò. toleratia  òåðïåíèå. Óïîòðåáëåíèå äàííîãî òåðìèíà ïîÿñíÿåòñÿ ñâîéñòâàìè êëàññîâ òîëå-
ðàíòíîñòè îáðàçîâûâàòü íå ðàçáèåíèå, êàê ó ýêâèâàëåíòíîñòè, à ïîêðûòèå èñõîäíîãî ìíîæåñòâà (ñì.
íèæå).
  Ïðèâåä¼ííóþ àêñèîìàòèçàöèþ ïîíÿòèÿ ñõîäñòâà è ðîäñòâåííîãî åìó ïîíÿòèÿ íåðàçëè÷èìîñòè ââ¼ë
àíãëèéñêèé ìàòåìàòèê Ý. 3èìàíí (ñì., íàïðèìåð, Ý. 3èìàíí, Î. Áüþíåìàí. Òîëåðàíòíûå ïðîñòðàíñòâà
è ìîçã. / Íà ïóòè ê òåîðåòè÷åñêîé áèîëîãèè.  Ì.: Ìèð, 1970).


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


     3. Äëÿ ýëåìåíòîâ x è y íåêîòîðîãî êîëüöà xτ y ⇔ ¾ýëåìåíò x − y íåîáðàòèì ¿.
Îïðåäåëåíèå 2.10. Ïàðó T = A, , ãäå A  íåïóñòîå ìíîæåñòâî, à                 òîëåðàíò-
íîñòü íà í¼ì, íàçûâàþò ïðîñòðàíñòâîì òîëåðàíòíîñòè.
Ïðèìåð 2.7. Ïóñòü A  íåïóñòîå ìíîæåñòâî è P ∗ (A)  ñîâîêóïíîñòü âñåõ åãî íåïóñòûõ
ïîäìíîæåñòâ. Äëÿ ïðîèçâîëüíûõ X, Y ∈ P ∗ (A) ïîëîæèì X Y = (X ∩ Y = ∅). Òîãäà
 P ∗ (A),    ïðîñòðàíñòâî òîëåðàíòíîñòè.
   Ìíîæåñòâî P ∗ (A) ïðè A = { 1, . . . , n } áóäåì îáîçíà÷àòü S n . Åãî íàçûâàþò (n − 1)-
ìåðíûì ñèìïëåêñîì. Ýòî ïîíÿòèå îáîáùàåò ïîíÿòèÿ îòðåçêà, òðåóãîëüíèêà, òåòðàýäðà íà
ìíîãîìåðíûé ñëó÷àé. ×èñëà 1, . . . , n èíòåðïðåòèðóþòñÿ êàê âåðøèíû ñèìïëåêñà. Äâóõ-
ýëåìåíòíûå ïîäìíîæåñòâà  êàê ð¼áðà, òð¼õýëåìåíòíûå  êàê ïëîñêèå (äâóìåðíûå) ãðà-
íè, è âîîáùå, k -ýëåìåíòíûå ïîäìíîæåñòâà  êàê (k − 1)-ìåðíûå ãðàíè. Íà ðèñ. 2.3 èçîá-
ðàæåí ñèìïëåêñ S4 . Òîëåðàíòíîñòü ãðàíåé ñèìïëåêñà S n îçíà÷àåò èõ ãåîìåòðè÷åñêóþ



                                             [
                                             4
                                            [
                                         1 [     w3
                                            [ 
                                                2


                                 Ðèñ. 2.3: Ñèìïëåêñ S 4

èíöèäåíòíîñòü  íàëè÷èå îáùèõ âåðøèí. ×èñëî âñåõ ýëåìåíòîâ S n ðàâíî, ðàçóìååòñÿ,
2n − 1.
   Íà êîíå÷íîì ìíîæåñòâå òîëåðàíòíîñòü ìîæíî, êàê è ëþáîå îòíîøåíèå, çàäàâàòü (0,1)-
ìàòðèöåé. ßñíî, ÷òî ñîîòâåòñòâóþùàÿ ìàòðèöà áóäåò ñèììåòðè÷íà è ñîäåðæàòü 1 íà ãëàâ-
íîé äèàãîíàëè, à ëþáàÿ òàêàÿ ìàòðèöà  çàäàâàòü òîëåðàíòíîñòü. Òàêæå òîëåðàíòíîñòü,
êàê è ëþáîå îòíîøåíèå, çàäàþò â âèäå ãðàôà. Ïðè ýòîì âåðøèíû ãðàôà, ñîîòâåòñòâó-
þùèõ, íàïîìíèì, ýëåìåíòàì ìíîæåñòâà, ñîåäèíÿþò íåîðèåíòèðîâàííûìè ð¼áðàìè (ñèì-
ìåòðè÷íîñòü), à ïåòëè â êàæäîé âåðøèíå (ðåôëåêñèâíîñòü) îïóñêàþò. Òàê, ïðîñòðàíñòâî
òîëåðàíòíîñòè, ñîîòâåòñòâóþùåå ìàòðèöå (2.4)
                                               
                                         1 1 0
                                 M =  1 1 1 ,
                                         0 1 1
çàäà¼òñÿ ãðàôîì, ïîêàçàííûì íà ðèñ. 2.4



                                            [[
                                           x2

                                         
                                    x1              x3


                 Ðèñ. 2.4: Ãðàô òîëåðàíòíîñòè, çàäàííîé ìàòðèöåé (2.4)

   Ðàññìîòðèì òåïåðü àëãåáðàè÷åñêèå ñâîéñòâà îïåðàöèé íàä òîëåðàíòíîñòÿìè. ßñíî,
íàïðèìåð, ÷òî òðàíçèòèâíîå çàìûêàíèå òîëåðàíòíîñòè åñòü ýêâèâàëåíòíîñòü. Òàê, äëÿ
òîëåðàíòíîñòè , çàäàííîé âûøåïðèâåä¼ííîé ìàòðèöåé M       t
                                                            åñòü àìîðôíàÿ ýêâèâà-
ëåíòíîñòü.


2.4. Ïðîñòðàíñòâà òîëåðàíòíîñòè                                                    33


Ëåììà 2.1. Åñëè       òîëåðàíòíîñòü, à ∼  ýêâèâàëåíòíîñòü íà íåêîòîðîì ìíî-
æåñòâå òàêèå, ÷òî     ⊆ ∼, òî t ⊆ ∼.

Äîêàçàòåëüñòâî ïîëó÷àåòñÿ ïðèìåíåíèåì îïåðàöèè òðàíçèòèâíîãî çàìûêàíèÿ ê îáåèì
÷àñòÿì âêëþ÷åíèÿ   ⊆ ∼.

Ñëåäñòâèå. Òðàíçèòèâíîå çàìûêàíèå îòíîøåíèÿ òîëåðàíòíîñòè åñòü ìèíèìàëüíàÿ
ýêâèâàëåíòíîñòü, âêëþ÷àþùàÿ ýòó òîëåðàíòíîñòè.

   Ââåä¼ì åù¼ îäíó áèíàðíóþ îïåðàöèþ ( ◦ ) íàä îäíîðîäíûìè îòíîøåíèÿìè α è β 
ñèììåòðèçîâàííîå ïðîèçâåäåíèå :

                                  α◦β     αβ ∪ βα .

Òåîðåìà 2.12 (Î ñâîéñòâàõ òîëåðàíòíîñòè).
  1. Òîëåðàíòíîñòü ñòàáèëüíà îòíîñèòåëüíî ∪, ∩, , à îòíîñèòåëüíî        åñëè è
     òîëüêî åñëè òîëåðàíòíîñòè ïåðåñòàíîâî÷íû (è â ýòîì ñëó÷àå α β = α ◦ β ).
  2. Ñèììåòðèçîâàííîå ïðîèçâåäåíèå òîëåðàíòíîñòåé âñåãäà òîëåðàíòíîñòü.
  3. Åñëè τ  òîëåðàíòíîñòü, òî è τ ∪    òîëåðàíòíîñòü.
  4. Åñëè α ðåôëåêñèâíî, òî îòíîøåíèÿ α ∪ α , α ∩ α è α ◦ α ñóòü òîëåðàíòíîñòè.

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

  1. Âñå óòâåðæäåíèÿ ñëåäóþò èç ï. 1) è 2) òåîðåìû 2.4 î ñòàáèëüíîñòè ïîëîæèòåëüíûõ
     ñâîéñòâ îäíîðîäíûõ îòíîøåíèé.

  2. Ïóñòü α è β  òîëåðàíòíîñòè. Òîãäà

       R: ðåôëåêñèâíîñòü α ◦ β ñëåäóåò èç ï. 1) òåîðåìû 2.4;
       S:

           (α ◦ β) = (αβ ∪ βα) = (αβ) ∪ (βα) = β α ∪ α β =
                                                          = βα ∪ αβ = α ◦ β .

  3. Óòâåðæäåíèå ñëåäóåò èç òîãî, ÷òî äîïîëíåíèå ñîõðàíÿåò ñâîéñòâî ñèììåòðè÷íîñòè,
     íî ïðåâðàùàåò ðåôëåêñèâíîå îòíîøåíèå àíòèðåôëåêñèâíîå.

  4. Ëåãêî âèäåòü, ÷òî îòíîøåíèÿ, ÿâëÿþùèåñÿ ðåçóëüòàòàìè óêàçàííûõ îïåðàöèé íà-
     ñëåäóþò ðåôëåêñèâíîñòü α è ïðèîáðåòàþò ñâîéñòâî ñèììåòðè÷íîñòè (äëÿ ◦ 
     ñëåäñòâèå ï. 2) ).



   Çàìåòèì, ÷òî åñëè âçÿòü äðóãîé âàðèàíò ñèììåòðèçîâàííîãî ïðîèçâåäåíèÿ è ââåñòè
áèíàðíóþ îïåðàöèþ ( ∗ ) íàä îäíîðîäíûìè îòíîøåíèÿìè α è β ïî ïðàâèëó

                                  α∗β     αβ ∩ βα ,

òî α ∗ β áóäåò òîëåðàíòíîñòüþ, åñëè α è β  òîëåðàíòíîñòè, ò.å. èõ ïåðåñòàíîâî÷íîñòè
òðåáîâàòüñÿ íå áóäåò.


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


   Äëÿ ïðîñòðàíñòâà òîëåðàíòíîñòè A, τ îïðåäåëÿþò ïî (2.5) ÿäðî Ker τ òîëåðàíò-
íîñòè τ (äâà ýëåìåíòà ïðèíàäëåæàò ÿäðó, åñëè îíè òîëåðàíòíû îäíèì è òåì æå îáúåê-
òàì). Íàïðèìåð, äëÿ òîëåðàíòíîñòè, çàäàâàåìîé ìàòðèöåé (2.4)
                                                
                                          1 1 0
                              M (τ ) =  1 1 1  ,
                                          0 1 1

ÿäðà ñóòü {1}, {2} è {3}. Òîëåðàíòíîñòü, ó êîòîðîé âñå ÿäðà, êàê ó ðàññìîòðåííîé,
îäíîýëåìåíòíû, áóäåì íàçûâàòü ïðîñòîé.
   Ôàêòîðìíîæåñòâî A∗ = A/ Ker τ ïðîñòðàíñòâà A, τ ñîñòîèò èç åãî ÿäåð. Íàçî-
â¼ì A∗ ôàêòîðìíîæåñòâîì ïðîñòðàíñòâà òîëåðàíòíîñòè ïî åãî ÿäðó. Ââåä¼ì íà A∗
îòíîøåíèå τ ∗ ïî ïðàâèëó
                            Core(x) τ ∗ Core(y) ⇔ xτ y .
Ëåãêî ïðîâåðÿåòñÿ êîððåêòíîñòü äàííîãî îïðåäåëåíèÿ, ò.å. åãî íåçàâèñèìîñòü îò âûáîðà
ïðåäñòàâèòåëÿ â ÿäðå. Îòñþäà âûòåêàåò, ÷òî îòîáðàæåíèå

                         ϕ : A → A/ Ker τ ,   ϕ(x) = Core(x)

ñòàâÿùåå â ñîîòâåòñòâèå êàæäîìó ýëåìåíòó åãî ÿäðî, îáëàäàåò ñâîéñòâîì

                                 xτ y ≡ ϕ(x) τ ∗ ϕ(y) .                           (2.6)

    òàêèõ ñëó÷àÿõ áóäåì ãîâîðèòü, îòîáðàæåíèå ÷òî ϕ òîæäåñòâåííî ñîãëàñîâàííî ñ
ïàðîé îòíîøåíèé τ è τ ∗ íà ìíîæåñòâàõ A è A/ Ker τ ñîîòâåòñòâåííî. Òàêèì îáðàçîì,
 A/ Ker τ, τ ∗  ïðîñòðàíñòâî òîëåðàíòíîñòè. Èç îïðåäåëåíèÿ ÿäðà è îòíîøåíèÿ τ ∗
ñëåäóåò, ÷òî îíî ïðîñòî. Äëÿ ðàññìàòðèâàåìîé òîëåðàíòíîñòè, çàäàâàåìîé ìàòðèöåé (2.4)
áóäåì, î÷åâèäíî, èìåòü M (τ ∗ ) = M (τ ).
Ïðèìåð 2.8. Ïóñòü òîëåðàíòíîñòü τ íà ìíîæåñòâå A = { 1, . . . , 9 } çàäàíà ìàòðèöåé
                                                         
                                    1 1 1 1 1 1 1 1 1
                                   1 1 1 1 1 1 1 1 1 
                                   1 1 1 1 1 1 1 0 1 
                                                         
                                   1 1 1 1 0 1 0 0 0 
                                                         
                         M (τ ) =  1 1 1 0 1 0 1 1 1  .
                                                                                (2.7)
                                   1 1 1 1 0 1 0 0 0 
                                                         
                                   1 1 1 0 1 0 1 0 1 
                                   1 1 0 0 1 0 0 1 0 
                                   1 1 1 0 1 0 1 0 1
ßäðà τ ñóòü
                   C1 = Core(1) = { 1, 2 },   C2 = Core(3) = { 3 },
                   C3 = Core(4) = { 4, 6 },   C4 = Core(5) = { 5 },
                   C5 = Core(7) = { 7, 9 },   C6 = Core(8) = { 8 }.
   Ìàòðèöà òîëåðàíòíîñòè τ ∗ íà ôàêòîðìíîæåñòâå A∗ = A/ Ker τ = { C1 , . . . , C6 }
åñòü                                         
                                1 1 1 1 1 1
                              1 1 1 1 1 0 
                                             
                              1 1 1 0 0 0 
                              1 1 0 1 1 1 .
                                             
                              1 1 0 1 1 0 
                                1 0 0 1 0 1


2.4. Ïðîñòðàíñòâà òîëåðàíòíîñòè                                                    35


   ßñíî, ÷òî â ÷àñòíîì ñëó÷àå, êîãäà òîëåðàíòíîñòü îêàçûâàåòñÿ ýêâèâàëåíòíîñòüþ, ïî-
íÿòèå ôàêòîðìíîæåñòâà òîëåðàíòíîñòè ïî ÿäðó ñîâïàäàåò ñ ïîíÿòèåì ôàêòîðìíîæåñòâà
ïî ýêâèâàëåíòíîñòè (ñì. ï. (2.3) ).
   Âàæíîé îñîáåííîñòüþ ïðîñòðàíñòâ òîëåðàíòíîñòè ÿâëÿåòñÿ òî, ÷òî íà íèõ óäà¼òñÿ
îïðåäåëèòü îñîáûå ïîäìíîæåñòâà ýëåìåíòîâ  êëàññû è ïðåäêëàññû, îáëàäàþùèå ðÿäîì
èíòåðåñíûõ ñâîéñòâ è îêàçûâàþùèåñÿ ïîäîáíûìè ÿäðàì.
Îïðåäåëåíèå 2.11. Ïóñòü A, τ  ïðîñòðàíñòâî òîëåðàíòíîñòè. Ïîäìíîæåñòâî
K ⊆ A íàçûâàþò ïðåäêëàññîì òîëåðàíòíîñòè â A èëè τ -ïðåäêëàññîì, åñëè â í¼ì âñå
ïàðû ýëåìåíòîâ òîëåðàíòíû. Ìàêñèìàëüíûé ïðåäêëàññ íàçûâàþò êëàññîì òîëåðàíòíî-
ñòè â A èëè τ -êëàññîì.
   Äëÿ êðàòêîñòè, ðàññìàòðèâàÿ ïðîñòðàíñòâà òîëåðàíòíîñòè ÷àñòî áóäåì ãîâîðèòü ïðî-
ñòî ¾êëàññ¿ è ¾ïðåäêëàññ¿, èìåÿ ââèäó êëàññû è ïðåäêëàññû òîëåðàíòíîñòè. Òðèâèàëü-
íûì ïðèìåðîì ïðåäêëàññà ÿâëÿåòñÿ ëþáîå îäíîýëåìåíòíîå ìíîæåñòâî ïðîñòðàíñòâà òî-
ëåðàíòíîñòè.
Ïðèìåð 2.9.    1. Äëÿ òîëåðàíòíîñòè, çàäàâàåìîé ìàòðèöåé (2.4) êëàññû òîëåðàíòíîñòè
     ñóòü K1 = { 1, 2 } è K2 = { 2, 3 }.
  2. Ðàññìîòðèì ïðîñòðàíñòâî òîëåðàíòíîñòè S n ,    . Îáîçíà÷èì ÷åðåç Ki ìíîæåñòâî
     âñåõ ãðàíåé, ñîäåðæàùèõ ýëåìåíò i, 1     i  n. Òàê, äëÿ S 3 ïîëó÷èì, íàïðèìåð,
     K1 = { {1}, {1, 2}, {1, 3}, {1, 2, 3} }.
     Ïîíÿòíî, ÷òî Ki  ïðåäêëàññ. Ïóñòü òåïåðü z ∈ {S n Ki }, è x = {i} ∈ Ki . ßñíî,
     ÷òî x    z , ïîñêîëüêó i ∈ z , íî i ∈ x. Çíà÷èò, ïðåäêëàññ íåðàñøèðÿåì, è Ki 
     êëàññ òîëåðàíòíîñòè â S n .
   Ãîâîðÿò, ÷òî ñîâîêóïíîñòü C íåïóñòûõ ïîäìíîæåñòâ ìíîæåñòâà A îáðàçóåò åãî ïî-
êðûòèå, åñëè îáúåäèíåíèå âñåõ ïîäìíîæåñòâ èç C ñîâïàäàåò ñ A.  îòëè÷èå îò ðàçáèåíèÿ,
ïîäìíîæåñòâà èç C ìîãóò èìåòü íåïóñòûå ïîïàðíûå ïåðåñå÷åíèÿ.
   ßñíî, ÷òî ñîâîêóïíîñòü A1 , A2 , . . . âñåõ ïðåäêëàññîâ òîëåðàíòíîñòè ïðîñòðàíñòâà
 A,    îáðàçóåò ïîêðûòèå ìíîæåñòâà A

                                  A = A1 ∪ A2 ∪ . . . ,

ò.ê. îáúåäèíåíèå âñåõ îäíîýëåìåíòíûõ ïðåäêëàññîâ óæå îáðàçóåò ïîêðûòèå (òî÷íåå, ðàç-
áèåíèå) A. Ñ äðóãîé ñòîðîíû, åñëè çàäàíû íåêîòîðîå íåïóñòîå ìíîæåñòâî A è ïîêðûòèå
åãî ïîäìíîæåñòâàìè, òî òåì ñàìûì çàäàíà è òîëåðàíòíîñòü      íà A, åñëè ñ÷èòàòü òîëå-
ðàíòíûìè ëþáóþ ïàðó ýëåìåíòîâ A, ïðèíàäëåæàùèõ îäíîìó èç ïîäìíîæåñòâ ïîêðûòèÿ.
Ïðè ýòîì äàííûå ïîäìíîæåñòâà áóäóò -ïðåäêëàññàìè (ñð. ñ òåîðåìîé (2.6) î êëàññàõ
ýêâèâàëåíòíîñòè).
    Îñîáûé èíòåðåñ ïðåäñòàâëÿþò êëàññû òîëåðàíòíîñòè.
Òåîðåìà 2.13. Äëÿ âñÿêîãî ýëåìåíòà ïðîñòðàíñòâà òîëåðàíòíîñòè ñóùåñòâóåò êëàññ
òîëåðàíòíîñòè, åãî ñîäåðæàùèé.
   Ñïðàâåäëèâîñòü òåîðåìû ñëåäóåò èç äîêàçàííîé äàëåå (ï. 3.4, ñ. 72) ëåììû 3.3 óòâåð-
æäàþùåé, ÷òî äëÿ âñÿêîãî ïðåäêëàññà ñóùåñòâóåò ñîäåðæàùèé åãî êëàññ (äîñòàòî÷íî
ðàññìîòðåòü ïðåäêëàññ, ñîñòîÿùèé èç åäèíñòâåííîãî äàííîãî ýëåìåíòà). Òàì æå äîêàçà-
íà ëåììà 3.2 î òîì, ÷òî äëÿ ëþáûõ äâóõ òîëåðàíòíûõ ýëåìåíòîâ ñóùåñòâóåò õîòÿ áû îäèí
ñîäåðæàùèé èõ êëàññ.
    ÷àñòîì ñëó÷àå, êîãäà òîëåðàíòíîñòü çàäà¼òñÿ íà êîíå÷íîì ìíîæåñòâå, äîêàçàòåëü-
ñòâî ýòîãî óòâåðæäåíèÿ íå ïðåäñòàâëÿåò òðóäà. Äåéñòâèòåëüíî, ïóñòü (x, y) ∈ τ  ïðî-
èçâîëüíàÿ ïàðà ýëåìåíòîâ êîíå÷íîãî ìíîæåñòâà, íàõîäÿùèõñÿ â îòíîøåíèè òîëåðàíòíî-
ñòè τ . Ðàññìîòðèì âñåâîçìîæíûå τ -ïðåäêëàññû, ñîäåðæàùèå îáà óêàçàííûõ ýëåìåíòà,


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 }, òî
K1 = { (1, 1), (1, 2), (2, 1), (2, 2) } è K2 = { (2, 2), (2, 3), (3, 2), (3, 3) }. Ïðè çàäàíèè (0,1)-
  2                                        2

ìàòðèöàìè òîëåðàíòíîñòè è îòíîøåíèé 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. Ïóñòü A, τ             ïðîñòðàíñòâî òîëåðàíòíîñòè è 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 [
                                              [ K2  K4 [
                                                     3
                                         
                                         K3       [
                                    4             5                 6


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


2.4. Ïðîñòðàíñòâà òîëåðàíòíîñòè                                                   37


                          K1 = { 1, 2, 3 },              K2 = { 2, 3, 5 },
                          K3 = { 2, 4, 5 },              K4 = { 3, 5, 6 }.
                   2        2
Ðàçëîæåíèå τ = K1 ∪. . .∪K4 èçáûòî÷íî, ò.ê. ëþáàÿ ïàðà ýëåìåíòîâ, âõîäÿùàÿ â äåêàðòîâ
           2
êâàäðàò K2 , ñîäåðæèòñÿ â îäíîì èç îñòàëüíûõ êâàäðàòîâ. Â òîæå âðåìÿ, ðàçëîæåíèå
       2     2   2
τ = K1 ∪ K3 ∪ K4 óæå íåïðèâîäèìî: íàïðèìåð, ïàðà (1, 1) ñîäåðæèòñÿ òîëüêî â K1 ,    2

ïàðà (4, 4)  òîëüêî â K3 , à ïàðà (6, 6)  òîëüêî â K4 .
                         2                            2

   Ïðèâåä¼ì áåç äîêàçàòåëüñòâà ïðîñòóþ òåîðåìó.
Òåîðåìà 2.15. Ïóñòü íà íåïóñòîì ìíîæåñòâå A çàäàíî ïîêðûòèå. Òîãäà ëþáîé êëàññ
òîëåðàíòíîñòè, ïîðîæä¼ííûé ýòèì ïîêðûòèåì, âûðàæàåòñÿ ÷åðåç ýëåìåíòû ýòîãî
ïîêðûòèÿ ñ ïîìîùüþ îïåðàöèé ∪ è ∩.
Îïðåäåëåíèå 2.12. Áàçèñîì (òîëåðàíòíîñòè) íà êîíå÷íîì ìíîæåñòâå íàçûâàåòñÿ âñÿ-
êèé íàáîð êëàññîâ, îïðåäåëÿþùèé íåïðèâîäèìîå ðàçëîæåíèå äàííîé òîëåðàíòíîñòè íà
êâàäðàòû.
   Òàê, â ïðåäûäóùåì ïðèìåðå åäèíñòâåííûé áàçèñ òîëåðàíòíîñòè τ ñîñòîèò èç å¼ êëàñ-
ñîâ K1 , K3 è K4 . ßñíî, ÷òî ïðè óäàëåíèè èç áàçèñà ëþáîãî êëàññà îñòàâøèåñÿ ýëåìåíòû
óæå íå îáðàçóþò ïîêðûòèÿ èñõîäíîãî ìíîæåñòâà. Ìîæíî ïîêàçàòü, ÷òî òîëåðàíòíîñòü
ìîæåò èìåòü íåñêîëüêî áàçèñîâ ñ ðàçëè÷íûì ÷èñëîì âõîäÿùèõ â íèõ êëàññîâ.
Ïðèìåð 2.12. Ãðàô, ïðåäñòàâëåííûé íà ðèñ. 2.6 çàäà¼ò òîëåðàíòíîñòü íà âîñüìèýëåìåíò-
íîì ìíîæåñòâå. Ëåãêî âèäåòü, ÷òî êëàññû K1 K5 è K7 îáðàçóþò øåñòèýëåìåíòíûé, à


                                              [[ ◦   ◦
                                          
                                         K K [
                                       
                                                K              3
                                                 1         2

                                     ◦ [    ◦     ◦
                                      K
                                         [K K 
                                          [     K
                                                 5         6


                                              
                                         4                     7


                                     ◦               ◦             ◦


                                Ðèñ. 2.6: Ê ïðèìåðó 2.12

êëàññû K1 , K3 , K4 , K6 è K7  ïÿòèýëåìåíòíûé áàçèñû äàííîãî ïðîñòðàíñòâà òîëå-
ðàíòíîñòè.
    ßñíî, ÷òî â ÷àñòíîì ñëó÷àå, êîãäà òîëåðàíòíîñòü îêàçûâàåòñÿ ýêâèâàëåíòíîñòüþ, òî
å¼ áàçèñ åäèíñòâåíåí è åãî ñîñòàâëÿþò ñìåæíûå êëàññû.
    Ñ êàæäûì áàçèñîì B(τ ) ïðîñòðàíñòâà òîëåðàíòíîñòè A/B(τ ) ñâÿçàíî îòíîøåíèå
ýêâèâàëåíòíîñòè ∼B(τ ) , îïðåäåëÿåìîå ñîîòíîøåíèåì

                      a1 ∼B(τ ) a2           ∀ K ( a1 ∈ K ⇔ a2 ∈ K ) .
                                         B(τ )

Èíûìè ñëîâàìè, ýëåìåíòû a1 è a2 ñ÷èòàþòñÿ ýêâèâàëåíòíûìè, åñëè îíè âõîäÿò â îäíè
è òå æå êëàññû äàííîãî áàçèñà.
   Ïîíÿòíî, ÷òî òàê îïðåäåë¼ííîå îòíîøåíèå äåéñòâèòåëüíî áóäåò ýêâèâàëåíòíîñòüþ.
Åñëè ñ÷èòàòü, ÷òî êëàññû èç B(τ )  ýòî íåêîòîðûå ñâîéñòâà, ïî êîòîðûì âåä¼òñÿ êëàñ-
ñèôèêàöèÿ, òî ýêâèâàëåíòíîñòü ýëåìåíòîâ îçíà÷àåò, ÷òî îíè îáëàäàþò îäèíàêîâûì íà-
áîðîì ñâîéñòâ. Íàïðèìåð, äëÿ òîëåðàíòíîñòè, çàäàâàåìîé ìàòðèöåé (2.7) èç ïðèìåðà 2.8
áàçèñ åäèíñòâåíåí è ýêâèâàëåíòíîñòü ∼B(τ ) ñîâïàäàåò ñ Ker τ .


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


Îïðåäåëåíèå 2.13. Ïóñòü B(τ )  áàçèñ â ïðîñòðàíñòâå òîëåðàíòíîñòè    A, τ . Ôàê-
òîðìíîæåñòâîì ïðîñòðàíñòâà A ïî áàçèñó B(τ ) íàçûâàåòñÿ ìíîæåñòâî îáîçíà÷àåìîå
A/B(τ ), ýëåìåíòàìè êîòîðîãî ÿâëÿþòñÿ êëàññû èç B(τ ) è èõ âñåâîçìîæíûå (íå îáÿçà-
òåëüíî ïîïàðíûå) íåïóñòûå ïåðåñå÷åíèÿ.
   ßñíî, ÷òî â ÷àñòíîì ñëó÷àå, êîãäà òîëåðàíòíîñòü îêàçûâàåòñÿ ýêâèâàëåíòíîñòüþ, ïî-
íÿòèå ôàêòîðìíîæåñòâà òîëåðàíòíîñòè ñîâïàäàåò ñ ïîíÿòèåì ôàêòîðìíîæåñòâà ïî ýêâè-
âàëåíòíîñòè (ñì. ï. (2.3) ). Åñëè ïðîñòðàíñòâî òîëåðàíòíîñòè A, τ èìååò åäèíñòâåííûé
áàçèñ, òî âìåñòî A/B(τ ) áóäåì ïèñàòü A/τ .
Ïðèìåð 2.13.    1. Ïðîäîëæåíèå ïðèìåðà 2.9. Äëÿ ïðîñòðàíñòâà T = { 1, 2, 3 }, τ ,
     â êîòîðîì òîëåðàíòíîñòü çàäàíà ìàòðèöåé (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 . ßñíî,
÷òî A ρ = ρ = ρ B . Êðîìå òîãî, âñåãäà ñïðàâåäëèâî âêëþ÷åíèå ρ ⊆ ρρ ρ. Äåéñòâèòåëü-
íî, äëÿ ïðîèçâîëüíûõ a ∈ A è b ∈ B èìååì aρb = aρb bρ a 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 ρ) .


2.6. Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà                                                      39


Äîêàæåì ïîñëåäíèå äâà ñâîéñòâà. Çàïèøåì ïðîîáðàç C è îáðàç A ÷åðåç ïðîåêöèè ñî-
îòâåòñòâèé:
                       Dom σ = σ (C) è Im ρ = ρ(A),
Ïîëüçóÿñü ñâîéñòâàìè ñîîòâåòñòâèé è èõ ïñåâäîîáðàùåíèé ïîëó÷èì

              Dom (ρσ) = (ρσ) (C) = (σ ρ )(C) = ρ (σ (C)) = ρ (Dom σ) ;
                       Im (ρσ) = (ρσ)(A) = σ(ρ(A)) = σ(Im ρ) .

   Äîêàçàòåëüñòâî îñòàëüíûõ ñâîéñòâ ìîæíî íàéòè, íàïðèìåð, â [1].
   Âûäåëèì îñíîâíûå òèïû ñîîòâåòñòâèé, îáëàäàþùèå îñîáûìè ñâîéñòâàìè.
Îïðåäåëåíèå 2.14. Ñîîòâåòñòâèå ρ ìåæäó ìíîæåñòâàìè A è B íàçûâàåòñÿ
   ˆ ìíîãîçíà÷íûì îòîáðàæåíèåì èëè âñþäó îïðåäåë¼ííûì ñîîòâåòñòâèåì, åñëè
       A ⊆ ρρ (÷òî ýêâèâàëåíòíî Dom ρ = A );
   ˆ ÷àñòè÷íûì îòîáðàæåíèåì A â B , åñëè ρ ρ ⊆ B (÷òî ýêâèâàëåíòíî
     aρb1 aρb2 ⇒ b1 = b2 äëÿ a ∈ A, ïðè ýòîì Dom ρ ⊆ A );
   ˆ ôóíêöèîíàëüíûì èëè îòîáðàæåíèåì A â B , åñëè A ⊆ ρρ                  ρ ρ ⊆ B (÷òî ýê-
     âèâàëåíòíî ñóùåñòâîâàíèþ äëÿ ëþáîãî a ∈ A åäèíñòâåííîãî b ∈ B òàêîãî, ÷òî
     aρb );
   ˆ äèôóíêöèîíàëüíûì èëè êâàçèîäíîçíà÷íûì, åñëè ρρ ρ ⊆ ρ èëè, ñ ó÷¼òîì äîêàçàí-
     íîãî âûøå, ρρ ρ = ρ (÷òî ýêâèâàëåíòíî ρ(a1 ) ∩ ρ(a2 ) = ∅ ⇒ ρ(a1 ) = ρ(a2 ) äëÿ
     âñåõ a1 , a2 ∈ A èëè ρ (b1 ) ∩ ρ (b2 ) = ∅ ⇒ ρ (b1 ) = ρ (b2 ) äëÿ âñåõ b1 , b2 ∈ B ).
     Äàííûå ñîîòíîøåíèÿ óêàçûâàþò, ÷òî êàê îáðàçû, òàê è ïðîîáðàçû äèôóíêöèîíàëü-
     íûõ îòíîøåíèé ëèáî ñîâïàäàþò, ëèáî íå ïåðåñåêàþòñÿ. Ðàâíîñèëüíû ñëåäóþùèå
     ñâîéñòâà ñîîòâåòñòâèÿ ρ:
         ρ äèôóíêöèîíàëüíî;
         åñëè a , a ∈ A è ρ(a ) ∩ ρ(a ) = ∅, òî ρ(a ) = ρ(a );
         åñëè b , b ∈ B è ρ (b ) ∩ ρ (b ) = ∅, òî ρ (b ) = ρ (b ).

   Ôóíêöèîíàëüíûå îòîáðàæåíèÿ áóäóò ðàññìîòðåíû íèæå.  êà÷åñòâå èëëþñòðàöèè èñ-
ïîëüçîâàíèÿ ìíîãîçíà÷íûõ îòîáðàæåíèé ïðèâåä¼ì áåç äîêàçàòåëüñòâà (êîòîðîå ìîæåò
áûòü íàéäåíî â [16]) ñëåäóþùóþ òåîðåìó.
Òåîðåìà 2.16 (Êàëüìàð-ßêóáîâè÷). Ïðîèçâîëüíîå îòíîøåíèå òîëåðàíòíîñòè    íà
ìíîæåñòâå A ìîæåò áûòü çàäàíî ñ ïîìîùüþ ïîäõîäÿùåãî ìíîãîçíà÷íîãî îòîáðàæå-
íèÿ ϕ èç A íà ñîâîêóïíîñòü âñåâîçìîæíûõ êëàññîâ òîëåðàíòíîñòè êàê

                                 x    y ⇔ ϕ(x) ∩ ϕ(y) = ∅ .


2.6 Îòîáðàæåíèÿ è èõ îñíîâíûå ñâîéñòâà
   Øèðî÷àéøåå ïðèìåíåíèå íàõîäÿò ôóíêöèîíàëüíûå ñîîòâåòñòâèÿ (îòîáðàæåíèÿ). Ðàñ-
ñìîòðèì èõ ïîäðîáíåå.
   Îòîáðàæåíèå ϕ èç A â B áóäåì íàçûâàòü òàêæå ôóíêöèåé èç A â B èëè îïåðàöèåé
                                                        ϕ
íà A5 . Ïðè ýòîì èñïîëüçóþò îáîçíà÷åíèÿ ϕ : A → B èëè A → B . Òîò ôàêò, ÷òî aϕb
                                  ϕ
çàïèñûâàþò êàê ϕ(a) = b èëè a → b ; ïðè òåîðåòè÷åñêèõ âûêëàäêàõ óäîáíà çàïèñü
  5 Òàêèì îáðàçîì, ìû íå ðàçëè÷àåì ïîíÿòèÿ ôóíêöèîíàëüíîãî ñîîòâåòñòâèÿ (îòîáðàæåíèÿ) è ôóíêöèè,
õîòÿ îíè íå òîæäåñòâåííû äðóã äðóãó. Ïðèìåð äëÿ çíàêîìûõ ñ òåîðèåé àëãîðèòìîâ: íåâû÷èñëèìûå
ôóíêöèè, ñòðîãî ãîâîðÿ, ÿâëÿþòñÿ ëèøü ôóíêöèîíàëüíûìè ñîîòâåòñòâèÿìè, à íå ôóíêöèÿìè.


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


aϕ = b èëè äàæå aϕ = b. Ìíîæåñòâî âñåõ îòîáðàæåíèé A → B áóäåì îáîçíà÷àòü
F un (A, B). Ïðè A = B áóäåì ïîëüçîâàòüñÿ îáîçíà÷åíèåì F un (A).
    Â ñîîòâåòñòâèè ñ îïðåäåëåíèÿìè äëÿ ñîîòâåòñòâèé, åñëè ϕ : A → B , òî ýëåìåíò
b, b = ϕ(a) íàçûâàþò îáðàçîì ýëåìåíòà a, à ýëåìåíò a  ïðîîáðàçîì ýëåìåíòà b.
Ñîâîêóïíîñòü (âîçìîæíî ïóñòàÿ) âñåõ ïðîîáðàçîâ ýëåìåíòà b ∈ B íàçûâàåòñÿ ïîëíûì
ïðîîáðàçîì b. Åñëè A ⊂ A è ϕ : A → B , òî ïðî îòîáðàæåíèå ϕ : A → B , ãäå
ϕ(x) = ϕ (x) äëÿ âñåõ x ∈ A , ãîâîðÿò, ÷òî îíî ÿâëÿåòñÿ ñóæåíèåì èëè îãðàíè÷åíèåì
îòîáðàæåíèÿ ϕ íà A , à ïðî îòîáðàæåíèå ϕ  ÷òî îíî ÿâëÿåòñÿ ïðîäîëæåíèåì èëè
ðàñøèðåíèåì îòîáðàæåíèÿ ϕ .
    Ïîñêîëüêó îòîáðàæåíèÿ ÿâëÿþòñÿ îòíîøåíèÿìè, ê íèì ìîæíî ïîïûòàòüñÿ ïðèìå-
íÿòü òåîðåòèêî-ìíîæåñòâåííûå îïåðàöèè. Îäíàêî âî-ïåðâûõ, îòðèöàíèå îòîáðàæåíèÿ,
î÷åâèäíî, îòîáðàæåíèåì íå ÿâëÿåòñÿ, à âî-âòîðûõ  ñïðàâåäëèâà ñëåäóþùàÿ

Óòâåðæäåíèå 2.4. Îáúåäèíåíèå [ ïåðåñå÷åíèå ] äâóõ îòîáðàæåíèé ϕ : A → B è
ψ : A → B ÿâëÿåòñÿ îòîáðàæåíèåì, åñëè è òîëüêî åñëè ϕ = ψ .

Äîêàçàòåëüñòâî. Ïîñêîëüêó ϕ è ψ  îòîáðàæåíèÿ èç A â B , äëÿ êàæäîãî a ∈ A ϕ è
ψ ñîäåðæàò ëèøü ïî îäíîé ïàðå (a, b1 ) è (a, b2 ) ñîîòâåòñòâåííî, ãäå b1 , b2 ∈ B . Åñëè
ïðåäïîëîæèòü, ÷òî b1 = b2 , òî ϕ ∪ ψ ñîäåðæèò äâå ïàðû (a, b1 ) è (a, b2 ), à ϕ ∩ ψ íå
ñîäåðæèò íè îäíîé ïàðû ñ ïåðâûì ýëåìåíòîì, ðàâíûì a.
   Òàêèì îáðàçîì, ïðèìåíåíèå ê îòîáðàæåíèÿì îáû÷íûõ òåîðåòèêî-ìíîæåñòâåííûå îïå-
ðàöèé èíòåðåñà íå ïðåäñòàâëÿåò. Ðàññìîòðèì òåïåðü îïåðàöèþ ïðîèçâåäåíèÿ îòíîøåíèé,
ïðèìåí¼ííóþ ê îòîáðàæåíèÿì.

Òåîðåìà 2.17. Åñëè A, B è C  íåïóñòûå ìíîæåñòâà, ϕ  îòîáðàæåíèå èç A â
B , à ψ  îòîáðàæåíèå èç B â C , òî ϕψ  îòîáðàæåíèå èç A â C .

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

         A⊆  ϕϕ , ϕ ϕ ⊆   B
                              ⇒   A⊆   ϕϕ =
         B ⊆ ψψ , ψ ψ ⊆   C

                                       = ϕ    B   ϕ ⊆ ϕ(ψψ )ϕ = (ϕψ)(ψ ϕ ) = (ϕψ)(ϕψ) ,

ò.å.     A⊆   (ϕψ)(ϕψ) . Âêëþ÷åíèå (ϕψ) (ϕψ) ⊆      C   ïîêàçûâàåòñÿ àíàëîãè÷íî.
   Ïðîèçâåäåíèå ôóíêöèé êàê îòîáðàæåíèé ïðèíÿòî çàïèñûâàòü êàê èõ êîìïîçèöèþ ∗:
(ϕ ψ)(x) = (ϕ ∗ ψ)(x) = ψ(ϕ(x))6 .
   Ðàññìîòðèì ñïåöèàëüíûå âèäû îòîáðàæåíèé. Åäèíè÷íîå îòíîøåíèå A , ðàññìàòðè-
âàåìîå êàê îòîáðàæåíèå A íà ñåáÿ, íàçûâàþò òîæäåñòâåííûì. Äëÿ òîæäåñòâåííîãî
îòîáðàæåíèÿ áóäåì óïîòðåáëÿòü îáîçíà÷åíèå idA .

Îïðåäåëåíèå 2.15. Îòîáðàæåíèå ϕ : A → B íàçûâàåòñÿ
       ˆ ïîñòîÿííûì èëè êîíñòàíòîé, åñëè ϕϕ = A . Ëåãêî âèäåòü, ÷òî äàííîå ñîîòíî-
         øåíèå ýêâèâàëåíòíî ϕ(x) = b ∈ B äëÿ âñåõ x ∈ A.
       ˆ âëîæåíèåì èëè èíúåêòèâíûì îòîáðàæåíèåì A â B , åñëè idA = ϕϕ , ÷òî çàïè-
                       ϕ
         ñûâàþò êàê A → B .
        Åñëè A ⊆ B , òî ϕ(x) = x íàçûâàåòñÿ åñòåñòâåííûì âëîæåíèåì ìíîæåñòâà A â
        ìíîæåñòâî B .
  6 Çäåñü ñòàíîâèòñÿ î÷åâèäíûì óäîáñòâî çàïèñè ψ(ϕ(x)) = xϕψ .  ýòîì ñëó÷àå ïðèâåä¼ííîå ñîîòíî-
øåíèå çàïèñûâàåòñÿ â åñòåñòâåííîé ôîðìå xϕψ = x(ϕψ).



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