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

Математическое отношение внутри порядков

Диаграмма Хассе степенного набора из трех элементов, частично упорядоченных по включению .

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

Определение

Пусть — множество с частичным порядком . Как обычно, пусть будет отношение такое, что тогда и только тогда, когда и . ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle <}$ ${\displaystyle X}$ ${\displaystyle x<y}$ ${\displaystyle x\leq y}$ ${\displaystyle x\neq y}$

Пусть и являются элементами . ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle X}$

Тогда накрывается , пишется , если и нет такого элемента, что . Эквивалентно, охватывает , если интервал представляет собой набор из двух элементов . ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x\lessdot y}$ ${\displaystyle x<y}$ ${\displaystyle z}$ ${\displaystyle x<z<y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle [x,y]}$ ${\displaystyle \{x,y\}}$

Когда говорят, что это обложка . Некоторые авторы также используют термин «покрытие» для обозначения любой такой пары в отношении покрытия. ${\displaystyle x\lessdot y}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle (x,y)}$

Примеры

• В конечном линейно упорядоченном множестве {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.