57. Обзор некоторых понятий, необходимых для введения понятия категории

Теория категорий позволяет выявить общую идею, лежащую в основе многих результатов, изложенных выше. Однако тем читателям, которые ранее не изучали эту теорию, нецелесообразно начинать знакомство с новым кругом идей без всякого перехода, не выработав предварительного представления о некоторых промежуточных понятиях, обзор которых мы сейчас и собираемся сделать в весьма дидактическом духе. В приводимых ниже примерах мы в основном будем иметь дело с конечными универсальными множествами, но определения без всяких дополнительных оговорок применимы и к бесконечным универсальным множествам.

Соответствие. Соответствие  между множествами  и  определено, если задан обычный граф . Тогда говорят, что  - граф соответствия ,  - область определения, а  - область значений .

Соответствие, обратное , обозначается , где  - область определения, а  - область значений .

Отображение. Отображением множества  во множество  называется такое соответствие, которое любому  сопоставляет по крайней мере один .

Тогда говорят, что элемент  - образ элемента , а  - переменная или аргумент.

Пример (см. рис. 57.1). Пусть

,                     (57.1)

.             (57.2)

Рис. 57.1. Отображение.

Имеем

, , , .                 (57.3)

 есть образ ,

 есть образ ,

 и  есть образы ,

 есть образ .

Сюръективное отображение или сюръекция. Отображение  на  называется сюръективным или сюръекцией, если любой  есть образ по крайней мере одного .

Пример (см. рис. 57.2). Пусть

,                     (57.4)

.             (57.5)

В каждый  входит по крайней мере одна дуга

Рис. 57.2. Сюръекция.

Имеем

   (57.6)

Это отображение действительно сюръекция, так как  непусто:

                       (57.7)

Как можно видеть, условие  для любого  характеризует сюръекцию.

Инъективное отображение или инъекция. Отображение  в  называется инъекцией, если каждый элемент  есть образ только одного элемента , либо вообще не имеет прообраза. В этом случае говорят, что  инъективно отображается в .

Пример (см. рис. 57.3). Пусть

,                     (57.8)

.                     (57.9)

В каждый  входит самое большее одна дуга

Рис. 57.3. Инъекция.

Имеем

                (57.10)

и

  (57.11)

Как можно видеть, если для любого , то отображение является инъекцией.

Биективное отображение или биекция. Если отображение одновременно сюръективно и инъективно, то оно называется биективным отображением или биекцией.

Пример (см. рис. 57.4). Пусть

,                     (57.12)

.                     (57.13)

В каждый  входит одна и только одна дуга

Рис. 57.4. Биекция.

Имеем

             (57.14)

и

  (57.15)

Как можно видеть, если для всех , то отображение биективно.

Функция. Отображение, такое, что

,               (57.16)

называется функцией.

Другими словами, функцией  в  называется такое отображение, которое каждому  сопоставляет один и только один .

Функция может быть сюръективной, инъективной или биективной. Некоторые примеры приведены на рис. 57.5-57.7.

Рис. 57.5. Сюръективная функция.

Рис. 57.6. Инъективная функция.

Рис. 57.7. Биективная функция.

Очевидно, что если функция  биективная, то  тоже биективная. В этом случае говорят о взаимно-однозначном соответствии между  и .

Замечание. Некоторые авторы определяют (в том числе и автор этой книги в нескольких своих работах, исходя из разных соображений) отображение как функцию, т. е. такое отображение, что . В настоящей работе мы предпочитаем следующие определения:

отображение: ,               (57.17)

функция: .                       (57.18)

Изотонные отображения упорядоченных множеств. Предположим, что множества  и  упорядочены отношением порядка, обозначенным . Отображение  в  называется изотопным, если оно сохраняет порядок, т. е. если

         (57.19)

Если порядок полный, то изотонное отображение будет называться монотонно неубывающим отображением.

Рассмотрим два примера.

Пример 1. На рис. 57.8 показаны два вполне упорядоченных множества  и , представленные соответствующими максимальными цепями. Непосредственно видно, что выполняется свойство изотонности, определенное в (57.19).

Рис. 57.8.

Рассмотрим, например, элементы  и . Имеем . С другой стороны,  и ; действительно имеем  и . Если провести проверку для других пар элементов , то удостоверимся, что здесь действительно имеет место монотонное неубывающее отображение  в .

Пример 2 (см. рис. 57.9). На этот раз конфигурации множеств  и  показывают, что множества  и  не наделены полным порядком. Максимальные цепи представлены соответствующими им диаграммами Хассе. В качестве упражнения выпишем все пары элементов, составляющие цепи:

                     (57.20)

Рис. 57.9.

Мы не проводим проверку изотонности для других упорядоченных пар ,  и т. д., поскольку очевидно, что изотонность транзитивна и поэтому ее достаточно проверить только для смежных элементов.

Антитонное отображение упорядоченных множеств. Рассмотрим свойство (57.19), но вместо  будем писать

;                     (57.21)

при этом условии говорят, что отображение антитонное.

В качестве упражнения читатель должен найти антитонное отображение  в  на рис. 57.9.

Морфизм упорядоченных множеств. Изотонное отображение  упорядоченного множества  в упорядоченное множество  называется морфизмом. На рис. 57.8 и 57.9 изображены морфизмы.

Эпиморфизм упорядоченных множеств - это морфизм, в котором отображение  множества  в множество  сюръективно.

Мономорфизм упорядоченных множеств. Мономорфизм - это морфизм, в котором отображение   в  инъективно. Если  - подмножество , в каждый из элементов которого входит точно одна дуга, то необходимо, чтобы отображение  было также изотонным относительно .

Изоморфизм упорядоченных множеств. Изоморфизм - это морфизм, который одновременно есть эпиморфизм и мономорфизм, т. е. это такой морфизм, что отображение  биективно, кроме того, как оно само, так и обратное к нему отображение  изотонны.

Чтобы лучше понять содержание этих определений, рассмотрим несколько примеров.

Пример 1 (см. рис. 57.10). Сначала проверим, что это морфизм. Рассмотрим все упорядоченные пары , , , которые составляют максимальные цепи:

                     (57.22)

Рис. 57.10. Морфизм, но не эпиморфизм и не мономорфизм.

Итак, мы убедились, что действительно имеем морфизм  в . Будет ли  эпиморфизмом? Априори нет, так как не во все  входит по крайней мере одна дуга (в  дуга не входит). Будет ли  мономорфизмом? Для этого необходимо проверить, изотонно ли обратное отображение  в .

Имеем

                               (57.23)

Это изучение бесполезно продолжать; отображение  не мономорфизм.

Пример 2 (см. рис. 57.11). Здесь те же упорядоченные множества, что и в предыдущем примере (см. рис. 57.10), но отображение другое. Сначала проверим, морфизм ли это отображение:

                   (57.24)

Рис. 57.11. Это отображение, но не морфизм.

Следовательно, это отображение не морфизм.

Пример 3 (см. рис. 57.12). Множества  и  те же, что на рис. 57.10 и 57.11, но  упорядочено по-другому.

Рис. 57.12. Эпиморфизм.

Проверим, морфизм ли это отображение:

                 (57.25)

Следовательно, данное отображение есть морфизм. Далее,  - эпиморфизм, так как это отображение сюръективно (в каждый элемент  входит по крайней мере одна дуга). Посмотрим, будет ли это отображение мономорфизмом. Определенно нет, потому что отображение не инъективно: имеется элемент , в который входит более одной дуги.

Пример 4 (см. рис. 57.13). Здесь мы имеем дело с другими множествами. Посмотрим, морфизм ли это отображение:

               (57.26)

Рис. 57.13. Другой эпиморфизм.

Это действительно морфизм. Кроме того, данное отображение есть эпиморфизм (в каждый элемент  входит по крайней мере одна дуга), но не мономорфизм (имеется по крайней мере один элемент , в который входит более одной дуги).

Пример 5 (см. рис. 57.14). Здесь

                      (57.27)

Рис. 57.14. Еще один эпиморфизм.

Действительно,  - морфизм, это также и эпиморфизм, но не мономорфизм.

Пример 6 (см. рис. 57.15). Здесь

                (57.28)

Рис. 57.15. Мономорфизм.

Действительно,  - морфизм, но не эпиморфизм (имеется по крайней мере один , в который не входит ни одна дуга). Проверим, будет ли это отображение мономорфизмом.

Первое условие выполняется: ни в один элемент  не входит более одной дуги, но необходимо, чтобы отображение  подмножества , где , было бы также изотонным относительно . Проверим это:

                    (57.29)

Таким образом, отображение  подмножества  в  действительно изотонно. Поэтому отображение  - мономорфизм.

Пример 7. (см. рис. 57.16). Здесь

                  (57.30)

Рис. 57.16. Изоморфизм.

Таким образом, отображение  - морфизм. Эпиморфизм ли оно? Да, так как в каждый элемент  входит по крайней мере одна дуга (фактически одна и только одна).

Посмотрим, мономорфизм ли отображение ? Первое условие (в каждый элемент  входит по крайней мере одна дуга) удовлетворяется, так как в каждый элемент  входит точно по одной дуге. Теперь рассмотрим упорядоченные пары, образующие максимальные цепи:

                    (57.31)

Таким образом, поскольку отображение  - эпиморфизм и мономорфизм, то оно изоморфизм. Если отождествить  и ,  и , то изоморфизм станет очевидным.

Пример 8 (см. рис. 57.17). Читатель может проверить, что это также изоморфизм. Это видно непосредственно из рисунка.

Рис. 57.17. Изоморфизм.

Эндоморфизм упорядоченного множества в себя. Морфизм упорядоченного множества  в себя называется эндоморфизмом.

Автоморфизм упорядоченного множества в себя. Изоморфизм  на себя называется автоморфизмом.

Двойственность двух упорядоченных множеств. Два упорядоченных множества  и  двойственны друг другу, если взаимно-обратные отображения  и  биективны и антитонны.

Пример 9 (см. рис. 57.18) на эндоморфизм: проверим, что это отображение действительно морфизм  в :

               (57.32)

Рис. 57.18. Эндоморфизм.

Таким образом, это отображение действительно морфизм и поэтому эндоморфизм  в .

Пример 10 (см. рис. 57.19) на автоморфизм: легко проверить, что отображение  есть изоморфизм и обратное отображение  - тоже изоморфизм. Отображение  есть автоморфизм  на себя.

Рис. 57.19. Автоморфизм.

Пример 11 (см. рис. 57.20) на двойственность: проверим антитонность:

            (57.33)

Рис. 57.20. Двойственность.

Это условие удовлетворяется. Для отображения  его можно проверить непосредственно, по симметрии. Таким образом, отображение биективно, а упорядоченные множества  и  - двойственны.

Морфизм структуризованного множества  в структуризованное множество . Мы рассмотрели понятие морфизма и другие понятия, связанные с упорядоченными множествами. Продолжим изучение этого понятия, но на этот раз каждое из двух множеств  и  будет обладать определенной структурой.

Пусть  и  - два множества, для которых определены законы внутренней композиции  и  соответственно, не обязательно определенные всюду.

Если

                     (57.34)

и если отображение  функциональное, т. е. функция, то говорят, что это отображение есть морфизм структуризованного множества  в структуризованное множество .

Отметим, что в проведенных рассмотрениях мы ограничились понятием морфизма для функциональных отображений, когда любому  сопоставлен один и только один .

Если отображение  инъективно, этот морфизм будет называться мономорфизмом.

Если отображение  сюръективно, этот морфизм будет называться эпиморфизмом.

Если отображение  биективно, этот морфизм будет называться изоморфизмом.

Когда  и , этот морфизм будет называться эндоморфизмом. В случае изоморфизма он будет называться автоморфизмом.

Как можно видеть, мы снова получили определения, касающиеся упорядоченных множеств, но условие изотонности здесь заменено условием (57.34), а отображение стало функциональным.

Пример 1. Рассмотрим множество , на котором определен внутренний закон  (рис. 57.21, слева), и множество , на котором определен закон (рис. 57.21, справа). В центре рис. 57.21 определяется морфизм  в .

Рис. 57.21.

В качестве упражнения проверим, что отображение  есть действительно морфизм  в . Имеем

                      (57.35)

Мы убедились, что для всех упорядоченных пар  условие (57.34) действительно удовлетворяется. Заметим, что пары , в которые входит хотя бы один элемент, отличный от ,  и , не влияют на отношение (57.35).

Пример 2. На рис. 57.22 представлен морфизм  в  . На рисунке показано, что отношение, связанное с одним из множеств, не обязательно нужно определять полностью, например, для внутреннего закона  в .

Рис. 57.22.

Пример 3. На рис. 57.23 представлен морфизм  в . Он соответствует морфизму на рис. 57.15 при условии, что проведены отождествления  и .

Рис. 57.23.

Пример 4. На рис. 57.24 представлен эпиморфизм  в . Он соответствует эпиморфизму на рис. 57.13 при условии, что  и .

Рис. 57.24.

Пример 5. На рис. 57.25 представлен изоморфизм  в . Он соответствует изоморфизму на рис. 57.17 при условии, что мы положили  и .

Рис. 57.25.

Пример 6. На рис. 57.26 представлен эндоморфизм  в .

Рис. 57.26.

Пример 7. На рис. 57.27 представлен автоморфизм  на . Он соответствует автоморфизму на рис. 57.19 при условии, что .

Рис. 57.27.

Пример 8. Автоморфизм  на  представлен на рис. 57.28, где слева имеем закон , а справа - закон . В действительности, обращаясь к рис. 57.20, мы видим, что  и , где морфизм  на  устанавливает двойственность для отношений порядка, отраженного на рис. 57.20.

Рис. 57.28.

Теперь рассмотрим несколько примеров, в которых структуры не соответствуют отношениям порядка.

Пример 9. На рис. 57.29 представлен мономорфизм группы  в группу .

Рис. 57.29.

Пример 10. На рис. 57.30 представлен эпиморфизм группы  на группу .

Рис. 57.30.

Пример 11. На рис. 57.31 представлен тривиальный автоморфизм (изоморфизм  в ). Можно показать, что существует только четыре конечные группы порядка 6 и только одна из этих четырех групп допускает нетривиальный автоморфизм (как на рис. 57.32, на котором изображена неабелева, т. е. некоммутативная, группа).

Рис. 57.31.

Пример 12. На рис. 57.32 представлен нетривиальный автоморфизм  в  (см. замечание, сделанное в примере 11 к рис. 57.31).

Рис. 57.32.

Замечание. Во всех примерах данного параграфа множества  конечные, однако все проведенные рассуждения применимы к произвольным множествам. Как обычно, примеры на конечных множествах мы рассматривали с дидактической целью.

Композиция двух обычных отношений. Пусть ,  и  - три множества; рассмотрим два обычных графа  и , с которыми свяжем обычные отношения  и  (можно также сказать, что  и  это соответствия, связанные с  и . Пусть  и ; составим упорядоченные пары , такие и только такие, что существует элемент , такой, что  и . Тогда множество упорядоченных пар  образует граф , скомпонованный из  и . Введем обозначения:

                      (57.36)

для графа и

                       (57.37)

для соответствующего ему отношения.

Заметим, что этот способ композиции двух бинарных отношений совпадает с тем, который определен в (13.10), и к тому же представляет собой только частный случай определения (13.9). На рис. 13.3 приведен один пример композиции, на рис. 57.33 - другой.

Рис. 57.33.

Композиция отображений. Предположим, что закон композиции двух бинарных отношений определен, как в (57.36) и (57.37), и рассматриваемые отношения есть функциональные отображения, или функции, соответственно либо сюръекции, либо инъекции, либо биекции. Тогда можно проверить:

На рис. 57.34 перечисленные в (57.38) свойства представлены в виде таблицы, где символами выбраны первые буквы соответствующих слов.

Рис. 57.34.

Если отображения ,  и  могут быть проведены последовательно, то закон композиции  необходимо ассоциативен:

.                      (57.39)

Для каждого отображения  существуют левая и правая единицы - это тождественные отображения  и , где :

.               (57.40)

Если для всех рассматриваемых отображений одно и то же множество служит как областью определения, так и областью значений, то существует единственная единица  и множество отображений образует моноид. Если все рассматриваемые отображения есть к тому же биективные функции, то для каждого отображения существует обратное к нему и множество этих биективных функций образует группу.

Композиций морфизмов.

Теорема 1. Пусть есть морфизм структуризованного множества  в ;  есть морфизм структуризованного множества  в ; тогда  есть морфизм  в .

Доказательство. Пусть  - закон, связанный с ,  - закон, связанный с . Поскольку отображение  - морфизм множества  в , то согласно (57.34) имеем

, где , .                   (57.41)

Пусть  - закон, связанный с . Поскольку  - морфизм  в , то мы должны иметь

, где .                 (57.42)

Из (57.41) и (57.42) получаем

.                  (57.43)

Но по определению

.                   (57.44)

Поэтому действительно имеем

.                        (57.45)

Мы рассмотрели случай функциональных отображений  или функций между структуризованными множествами. Аналогичное доказательство будет проведено для отображений, функциональных или нет, между упорядоченными множествами. Это составляет содержание следующей теоремы.

Теорема 2. Пусть  - морфизм упорядоченного множества  в ;  - морфизм упорядоченного множества  в ; тогда  есть морфизм  в .

Доказательство. Поскольку  -морфизм  в , то согласно свойству изотонностн получим

.               (57.46)

Так как  - морфизм  в , то согласно (57.19) получим

                     (57.47)

Отметим, что правую часть соотношения (57.47) можно переписать в виде

              (57.48)

или еще раз

.                       (57.49)

Поэтому в силу транзитивности импликаций можно записать

;                    (57.50)

теорема доказана.

Ассоциативность в законах композий морфизмов. Если закон композиции , определенный в (57.36) и (57.37) для обычных отношений, используется точно так же, как в приведенных выше рассмотрениях, но для композиции морфизмов, то этот закон обладает свойством ассоциативности. Таким образом, если ,  и  - морфизмы  в ,  в  и  в  соответственно, то получим

.                      (57.51)

Если закон композиции определен по-другому, то нужно проверять, выполняется ли для него свойство ассоциативности.

В данной работе законы композиции, которые мы будем рассматривать для морфизмов, будут ассоциативными.