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

Чтобы узнать о других вариантах использования Cover в математике, см. Cover (математика) .

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

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

Определение

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

Позволять $x$ и $y$ быть элементами $X$.

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

Когда $x\lessdot y$, сказано, что $y$ это обложка $x$. Некоторые авторы также используют термин «обложка» для обозначения любой такой пары. $(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 .