Дискретно-непрерывная математика (стр. 61 )

(7.36)

для графа и

(7.37)

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

Заметим, что этот способ композиции двух бинарных отношений совпадает с тем, который определен ранее. На рис. 7.33 при­веден пример композиции.

Рис. 7.33

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

отображение ° отображение = отображение,

отображение ° сюръекция = отображение,

сюръекция ° отображение = отображение,

отображение ° инъекция = отображение,

инъекция ° отображение = отображение,

отображение ° биекция = отображение,

биекция о отображение = отображение,

сюръекция ° сюръекция = сюръекция,

сюръекция ° инъекция = отображение,

инъекция ° сюръекция = отображение,

сюръекция ° биекция = сюръекция, (7.38)

биекция ° сюръекция = сюръекция,

инъекция ° инъекция = инъекция,

инъекция ° биекция = инъекция,

биекция ° инъекция = инъекция,

биекция ° биекция = биекция.

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

Рис.7.34

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

(7.39)

Для каждого отображения Г существуют левая и правая единицы — это тождественные отображения 1Х и 1Y, где Y = ГХ:

(7.40)

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

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

Теорема 1. Пусть Г1 есть морфизм структуризованного множества X в Y; Г2 есть морфизм стpуктуризованного множества Y в Z; тогда

Г1,2 =Г2 °Г1 есть морфизм X в Z.

Доказательство. Пусть * — закон, связанный с Х, *' — закон, связанный с Y. Поскольку отображение Г1— морфизм множест­ва X в Y, то согласно (7.34) имеем

(7.41)

Пусть *" — закон, связанный с Z. Поскольку Г2 — морфизм Y в Z, то мы должны иметь

(7.42).

Из (7.41) и (7.42) получаем

(7.43)

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

(7.44)

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

(7.45)

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

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

Г2 — морфизм упорядоченного множества Y в Z; тогда Г1,2 =Г2 °Г1 есть морфизм X в Z.

Доказательство Поскольку Г1 —морфизм X в Y, то со­гласно свойству изотонности получим

(7.46)

Так как Г2 — морфизм Y в Z, то согласно (7.19) получим

(7.47)

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

(7.48)

или еще раз

(7.49)

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

(7.50)

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

Ассоциативность в законах композий морфизмов. Если закон композиции °, определенный в (7.36) и (7.37) для обычных отноше­ний, используется точно так же, как в приведенных выше рассмотре­ниях, но для композиции морфизмов, то этот закон обладает свойством ассоциативности. Таким образом, если Г1, Г2 и Г3 — морфизмы X bY, Y b Z и Z b V соответственно, то получим

(7.51)

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

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

4.8. Понятие категории

Категория С есть множество объектов, таких, что для любой упо­рядоченной пары (X, Y), X С, Y С существует множество мор­физмов Г из X в Y, обладающих определенным свойством и обозначае­мых MOR (X, Y) (допускается возможность, что множество

MOR (X, Y) может быть пустым). Эти морфизмы называются

С-морфизмами и об­ладают по определению следующими свойствами:

тогда и только тогда, ког­да (X, Y) Ф (Х'У). (8.1)

2. Предполагается, что морфизм Г1 из X в Y сочетается посредст­вом закона композиции ° с морфизмом Г2 из Y в Z (X С, Y С, Z С) так, что получается морфизм Г1,2 из X в Z. Закон °, конечно, должен быть определен. Если

то

3. Предполагается, что если и то

(8.2)

Другими словами, закон композиции ассоциативен.

4. Предполагается, что для любого X С существует морфизм, представляющий собой тождественное отображение X на себя. Этот Морфизм (обозначается Г0Х или 1) таков, что для любых

имеет место

(8.3)

Понятие категории очень широко распространено в математике. К категориям относятся следующие понятия:

— группа с групповыми морфизмами: группа, обозначаемая

где Е — множество, имеющее структуру группы, * — закон группы;

— множества и отображения между ними;

—решетки с морфизмами решеток; решетки обозначаются

где Е — множество, имеющее конфигурацию решетки,

— отношение порядка на решетке. Решетка может также опреде­ляться как где ∆ и — законы, определенные по­средством понятий нижней и верхней границ подмножества множе­ства Е соответственно;

— полурешетки

— топологические пространства с непрерывными отображения­ми;

— измеримые пространства с измеримыми преобразованиями; и т. д.

Рассмотрим несколько примеров.

Пример 1.

Пусть E и F — два упорядоченных множества (рис. 8.1).

Рис. 8.1

Они представляют собой две верхние полурешетки и состав-

ляют множество объектов категории С, изучением которой мы займемся.

Эти две верхние полурешетки можно также рассматривать как струк-туризованные множества, на которых определены операции и ′ взятия верхней грани двух упорядоченных пар элементов из Е и F соответственно (рис. 8.2).

Рис. 8.2

На рис. 8.3 приведены четыре множества: