Покрывающее отношение

В математике , особенно в теории порядка , отношение покрытия — частично упорядоченного множества это бинарное отношение , которое сохраняется между сравнимыми элементами, которые являются непосредственными соседями. Отношение покрытия обычно используется для графического выражения частичного порядка с помощью диаграммы Хассе .
Определение [ править ]
Позволять быть множеством с частичным порядком .Как обычно, пусть быть отношением к такой, что тогда и только тогда, когда и .
Позволять и быть элементами .
Затем обложки , написано ,если и нет элемента такой, что . Эквивалентно, обложки если интервал это набор из двух элементов .
Когда , сказано, что это обложка . Некоторые авторы также используют термин «обложка» для обозначения любой такой пары. в покрывающем отношении.
Примеры [ править ]
- В конечном линейно упорядоченном множестве {1, 2, ..., n } i + 1 покрывает i для всех i от 1 до n − 1 (и других накрывающих отношений нет).
- В булевой алгебре степенного множества множества S подмножество B из S покрывает подмножество A из S тогда и только тогда, когда B получено из A добавлением одного элемента, не входящего A. в
- В решетке Юнга , образованной разбиениями всех неотрицательных целых чисел, разбиение λ покрывает разбиение µ тогда и только тогда, когда Юнга диаграмма λ получается из диаграммы Юнга µ путем добавления дополнительной ячейки.
- изображающая накрывающее отношение решетки Тамари, представляет собой скелет ассоциаэдра Диаграмма Хассе , .
- Накрывающее отношение любой конечной дистрибутивной решетки образует медианный граф .
- У вещественных чисел обычного общего порядка ≤ множество покрытий пусто: ни одно число не покрывает другое.
Свойства [ править ]
- Если частично упорядоченное множество конечно, его накрывающее отношение является транзитивной редукцией отношения частичного порядка. Таким образом, такие частично упорядоченные множества полностью описываются диаграммами Хассе. С другой стороны, в плотном порядке , таком как рациональные числа стандартного порядка, ни один элемент не закрывает другой.
Ссылки [ править ]
- Кнут, Дональд Э. (2006), Искусство компьютерного программирования , Том 4, Глава 4 , Аддисон-Уэсли, ISBN 0-321-33570-8 .
- Стэнли, Ричард П. (1997), Перечислительная комбинаторика , том. 1 (2-е изд.), Издательство Кембриджского университета , ISBN 0-521-55309-1 .
- Брайан А. Дэйви; Хилари Энн Пристли (2002), Введение в решетки и порядок (2-е изд.), Cambridge University Press, ISBN 0-521-78451-4 , LCCN 2001043910 .