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

Изотонные отображения упорядоченных множеств. Предположим, что множества E1 и Е2 упорядочены отношением порядка, обозначен-ным . (Вообще множества E1 и Е2 могут быть различными, как могут отличать­ся друг от друга и отношения порядка, связанные с ними; поэтому было бы умест­но различать их с помощью какого-нибудь символа, например Но мы используем один и тот же символ независимо от того, каким мо­жет быть отношение. Аналогично поступают, например, в случае, когда исполь­зуют один и тот же символ «+» для целых и комплексных чисел —двух совер­шенно разных понятий.)

Отображение E1 и Е2 называется изотонным, если оно сохраняет порядок, т. е. если

(7.19)

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

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

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

Рассмотрим, например, элементы b и с. Имеем b < с. С другой сто­роны, Г {b} = {В} и Г {с} = {В, D}; действительно имеем и Если провести проверку для других пар элементов Е1, то удо­стоверимся, что здесь действительно имеет место монотонное неубы­вающее отображение E1 в Е2.

Рис. 7. 8 Рис. 7. 9

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

(7.20)

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

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

(7.21)

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

В качестве упражнения читатель должен найти антитонное отобра­жение Ех в Е2 на рис. 7.9.

Морфизм упорядоченных множеств. Изотонное отображение Г упо­рядоченного множества Е1 в упорядоченное множество Е2 называется морфизмом. На рис. 7.8 и 7.9 изображены морфизмы.

Рис. 7.10 Морфизм, но не эпимор- Рис. 7.11 Это отображение, физм и не мономорфизм но не морфизм

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

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

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

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

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

(7. 22)

Итак, мы убедились, что действительно имеем морфизм Е1 в Е2. Бу­дет ли Г эпиморфизмом? Априори нет, так как не во все Y Е2 входит по крайней мере одна дуга (в D дуга не входит). Будет ли Г мономор­физмом? Для этого необходимо проверить, изотонно ли обратное ото­бражение Е'2 = {А, В, С, Е, F} в Е1.

Имеем

(7.23)

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

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

(7.24)

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

Пример 3 (см. рис. 7.12). Множества Е1 и Е2 те же, что на рис. 7.10 и 7.11, но Е2 упорядочено по-другому.

Рис. 7.12. Эпиморфизм Рис. 7.13. Другой эпиморфизм

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

(7.25)

Следовательно, данное отображение есть морфизм. Далее, Г— эпи­морфизм, так как это отображение сюръективно (в каждый элемент

Y Е2 входит по крайней мере одна дуга). Посмотрим, будет ли это отображение мономорфизмом. Определенно нет, потому что отображе­ние не инъективно: имеется элемент Y Е2, в который входит более одной дуги.

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

(7.26)

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

Y 2 Е2, в который входит более одной дуги).

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

(7.27)

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

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

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

(7.28)

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

Первое условие выполняется: ни в один элемент Y Е2 не входит более одной дуги, но необходимо, чтобы отображение Г-1 подмно­жества Е′2, где Е′2 = {А, В, D, Е}, было бы также изотонным отно­сительно Ех. Проверим это:

(7.29)

Таким образом, отображение Г-1 подмножества Е′2 в E1 действи­тельно изотонно. Поэтому отображение Г — мономорфизм.

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

(7.30)

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

Рис. 7. 16. Изоморфизм Рис. 7.17. Изоморфизм

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